Bison 中的运算符优先级如何工作？

Question

这可能是一个简单的问题，已经有人问过，但我很难理解 Bison，尤其是运算符优先级。如果我有这个代码并且 + 有 left association.

%left '+'
%%
S:
   S E ’\n’ { printf("%d\n", ); }
|
; 

E:
   num { $$ = ; }
| E '+' E {$$ =  + ;}
| E '*'  E {$$ =  * ;}
; 
%%

输入是2+3+4*5，输出是25，我的答案是45。

谁能一步步告诉我 Bison 是做什么的？我的意思是元素如何被推入堆栈以及它们如何以及何时被减少。如果可能的话，甚至是解析树。

Answer 1

查看语法中正在发生的事情的最简单方法是启用 bison 的跟踪工具，如 bison manual section on debugging parsers 中所述。在您读取跟踪时手边有状态机很有用，因为跟踪提供了通过状态机的路径。要查看状态机，请使用 bison 的 -v 选项，这将创建一个扩展名为 .output.

的文件

$ cat minimal.y
%{
#include <stdio.h>
#include <ctype.h>
int yylex(void);
void yyerror(const char* msg) {
  fprintf(stderr, "%s\n", msg);
}
%}
%token num
%left '+'
%%
S: S E '\n' { printf("%d\n", ); }
 |
E: num { $$ = ; }
 | E '+' E {$$ =  + ;}
 | E '*'  E {$$ =  * ;}
%%
int yylex(void) {
  int c;
  do c = getchar(); while (c == ' ');
  if (isdigit(c)) {
    yylval = c - '0';
    return num;
  }
  return c == EOF ? 0 : c;
}
int main(int argc, char* argv[]) {
#if YYDEBUG
  yydebug = 1;
#endif
  return yyparse();
}

编译并运行:

$ bison -t -v -o minimal.c minimal.y
minimal.y: warning: 3 shift/reduce conflicts [-Wconflicts-sr]
$ gcc -Wall -o minimal minimal.c
$ ./minimal <<<'2+3+4*5'
Starting parse
Entering state 0
Reducing stack by rule 2 (line 14):
-> $$ = nterm S ()
Stack now 0

我剪下了痕迹（尽管你可以在答案的底部看到它）。查看表示正在读取令牌 *:

的行的跟踪

Entering state 8
Reading a token: Next token is token '*' ()
Shifting token '*' ()
Entering state 7

这是来自 minimal.output 的状态 8 的定义，包括 shift-reduce 冲突（用方括号表示不会执行的操作）和默认解决方案：

State 8

    4 E: E . '+' E
    4  | E '+' E .
    5  | E . '*' E

    '*'  shift, and go to state 7

    '*'       [reduce using rule 4 (E)]
    $default  reduce using rule 4 (E)

这是完整的跟踪（尽管我强烈建议您在自己的机器上进行实验）：

Starting parse
Entering state 0
Reducing stack by rule 2 (line 14):
-> $$ = nterm S ()
Stack now 0
Entering state 1
Reading a token: Next token is token num ()
Shifting token num ()
Entering state 3
Reducing stack by rule 3 (line 16):
    = token num ()
-> $$ = nterm E ()
Stack now 0 1
Entering state 4
Reading a token: Next token is token '+' ()
Shifting token '+' ()
Entering state 5
Reading a token: Next token is token num ()
Shifting token num ()
Entering state 3
Reducing stack by rule 3 (line 16):
    = token num ()
-> $$ = nterm E ()
Stack now 0 1 4 5
Entering state 8
Reading a token: Next token is token '+' ()
Reducing stack by rule 4 (line 17):
    = nterm E ()
    = token '+' ()
    = nterm E ()
-> $$ = nterm E ()
Stack now 0 1
Entering state 4
Next token is token '+' ()
Shifting token '+' ()
Entering state 5
Reading a token: Next token is token num ()
Shifting token num ()
Entering state 3
Reducing stack by rule 3 (line 16):
    = token num ()
-> $$ = nterm E ()
Stack now 0 1 4 5
Entering state 8
Reading a token: Next token is token '*' ()
Shifting token '*' ()
Entering state 7
Reading a token: Next token is token num ()
Shifting token num ()
Entering state 3
Reducing stack by rule 3 (line 16):
    = token num ()
-> $$ = nterm E ()
Stack now 0 1 4 5 8 7
Entering state 9
Reading a token: Next token is token '\n' ()
Reducing stack by rule 5 (line 18):
    = nterm E ()
    = token '*' ()
    = nterm E ()
-> $$ = nterm E ()
Stack now 0 1 4 5
Entering state 8
Next token is token '\n' ()
Reducing stack by rule 4 (line 17):
    = nterm E ()
    = token '+' ()
    = nterm E ()
-> $$ = nterm E ()
Stack now 0 1
Entering state 4
Next token is token '\n' ()
Shifting token '\n' ()
Entering state 6
Reducing stack by rule 1 (line 13):
    = nterm S ()
    = nterm E ()
    = token '\n' ()
25
-> $$ = nterm S ()
Stack now 0
Entering state 1
Reading a token: Now at end of input.
Shifting token $end ()
Entering state 2
Stack now 0 1 2
Cleanup: popping token $end ()
Cleanup: popping nterm S ()

Bison 中的运算符优先级如何工作？

How does operator precedence in Bison work?

parsing

yacc

bison