是什么决定解析器尝试哪种产生式？

Question

我正在尝试为桌面计算器构建一个解析器，并且正在为其使用以下 bison 代码。

%union{
    float f;
    char c;
    // int 
}

%token <f> NUM
%token <c> ID
%type <f> S E T F G

%%

C   :   S ';'
    |   C S ';'
    ;

S   :   ID '=' E    {fprintf(debug,"13\n");printf("%c has been assigned the value %f.",,);symbolTable[]=;}
    |   E           {fprintf(debug,"12\n");result = $$;}
    ;

E   :   E '+' T     {fprintf(debug,"11\n");$$ = +;}
    |   E '-' T     {fprintf(debug,"10\n");$$ = -;}
    |   T           {fprintf(debug,"9\n");$$ = ;}
    ;

T   :   T '*' F     {fprintf(debug,"7\n");$$ = *;}
    |   T '/' F     {fprintf(debug,"6\n");$$ = /;}
    |   F           {fprintf(debug,"5\n");$$ = ;}
    ; 

F   :   G '@' F     {fprintf(debug,"4\n");$$ = pow(,);}
    |   G           {fprintf(debug,"3\n");$$ = ;}
    ;

G   :   '(' E ')'   {fprintf(debug,"2\n");$$ = ;}
    |   NUM         {fprintf(debug,"1\n");$$ = ;}
    |   ID          {fprintf(debug,"0\n");$$ = symbolTable[];}
    ;

%%

我的 LEX 规则是

digit   [0-9]
num     {digit}+
alpha   [A-Za-z]
id      {alpha}({alpha}|{digit})*
white   [\ \t]

%%
let     {printf("let");return LET;}
{num}   {yylval.f = atoi(yytext);return NUM;}
{alpha} {yylval.c = yytext[0];return ID;}
[+\-\*/@\(\)]   {return yytext[0];}
.       {}
%%

我给的输入是a=2+3 当词法分析器 returns 和 ID（对于 'a'）时，解析器将使用 fprintf(debug,"0\n") 进行生产。但我希望它用于生产 fprintf(debug,"13\n").

所以，我想知道是什么让我的解析器减少生产 0，而不是将 = 转移到堆栈，我该如何控制它？

Answer 1

好吧，问题是我没有在我的 LEX 中将 = 识别为标记。

虽然听起来很傻，但它指出了yacc/Bison一个非常重要的概念。通过检查下一个符号（也称为先行）来回答是移动还是减少的问题。在这种情况下，由于我的错误 LEX 代码，前瞻是 NUM（对于 2）而不是 =。由于没有生产涉及 ID 后接 NUM，因此将减少到 G。

我是怎么想出来的，原来野牛有一个内置的 trace feature。它像日记条目一样整齐地排列，无论它在解析时做什么。每一步都被记录下来。

要启用它，

运行 bison 带有 -Dparse.trace 选项。

bison calc.y -d -Dparse.trace

在解析器的主函数中获取 extern yydebug 并将其设置为非零值。

int main(){
   extern int yydebug;
   yydebug = 1;
   .
   .
   .
}

Answer 2

你实际指定的是一个翻译语法，由以下给出：
C → S ';' 14 | CS ';' 8
S → ID '=' E 13 | 12
E → E '+' T 11 | E'-'T 10 | 9
T → T '*' F 7 | T "/" F 6 | F 5
F → G '@' F 4 | G 3
G → '(' E ')' 2 |数字 1 |编号 0
使用 top-level/start 配置 C。（为了完整起见，我添加了 8 和 14）。

C中只有一个词，通过这个翻译文法，包含ID '=' NUM '+' NUM作为input token的子词，即ID ('a') '=' NUM('2') 1 3 5 9 '+' NUM('3') 1 3 5 11 13 ';' 14，等于输入输出对（ID'='NUM'+'NUM';', 1 3 5 9 1 3 5 11 13 14）。因此，序列 1 3 5 9 1 3 5 11 13 14 是唯一的翻译。如果文法是 LALR(1)，那么就会产生这个翻译；语法是 LALR(1).

如果你没有得到这个结果，那么这只能意味着你实施了错误的任何你遗漏的描述：即词法分析器......或者你的语法处理器有一个错误或者你的机器有一个失败。

而且，不；实际上，您所做的是查看正在发生的事情的更好方法 - 只需在每个规则的右侧粘贴一个 printf 语句，然后运行以这种方式查看生成的翻译序列。出于这个原因，解析器生成器中的“跟踪”功能是多余的……至少它通常的实现方式是这样（更多内容见下文）。此外，您可以使用 -v 选项直接查看所有内容，该选项会生成带有 LALR(1) 注释的 LR(0) 表。

实际上更有用的内置测试工具——尤其是对于像这样的示例——正是我所描述的：一种回显输入与输出操作交错的工具。所以，当你在 "a = 2 + 3 ;" 上运行时，它会给你 ID('a') '=' NUM('2') 1 3 5 9 '+' NUM( '3') 1 3 5 11 13 ';' 14 打开回声，只有 1 3 5 9 1 3 5 11 13 14 关闭回声。将其作为内置功能实际上会更有用，而不是通常在 yacc 实现中看到的跟踪模式。

POSIX 规范实际上留下了如何在 yacc 的兼容实现中实现“YYDEBUG”、“yydebug”和“-t”的问题，以便为像这样的替代方法腾出空间.

是什么决定解析器尝试哪种产生式？

What decides which production the parser tries?

parsing

yacc

lex

bison