如何解释 bison 中的 "shift/reduce" 冲突

Question

我正在编写一个小型 bison/flex 计算器，但我无法理解和调试冗长的输出

这是导致错误的代码：

%token NUM
%token NAME

%%
input:    '\n'
          | line '\n'
;

line:     expr                    {printf("%.10g\n", );}
          | NAME '=' expr         {Assign(table, yyname, );}
;

expr:     NUM                     {$$ = ;}
          | NAME                  {$$ = Lookup(table, yyname);}
          | expr '+' expr         {$$ =  + ;}
          | expr '-' expr         {$$ =  - ;}
          | expr '*' expr         {$$ =  * ;}
          | expr '/' expr         {$$ =  / ;}
          | expr '^' expr         {$$ = pow(, );}
          | '(' expr ')'          {$$ = ;}

详细错误输出为：

state 20

7 expr: expr . '+' expr
7     | expr '+' expr .
8     | expr . '-' expr
9     | expr . '*' expr
10     | expr . '/' expr
11     | expr . '^' expr

'+'  shift, and go to state 13
'-'  shift, and go to state 14
'*'  shift, and go to state 15
'/'  shift, and go to state 16
'^'  shift, and go to state 17

'+'       [reduce using rule 7 (expr)]
'-'       [reduce using rule 7 (expr)]
'*'       [reduce using rule 7 (expr)]
'/'       [reduce using rule 7 (expr)]
'^'       [reduce using rule 7 (expr)]
$default  reduce using rule 7 (expr)

...

state 24

7 expr: expr . '+' expr
8     | expr . '-' expr
9     | expr . '*' expr
10     | expr . '/' expr
11     | expr . '^' expr
11     | expr '^' expr .

'+'  shift, and go to state 13
'-'  shift, and go to state 14
'*'  shift, and go to state 15
'/'  shift, and go to state 16
'^'  shift, and go to state 17

'+'       [reduce using rule 11 (expr)]
'-'       [reduce using rule 11 (expr)]
'*'       [reduce using rule 11 (expr)]
'/'       [reduce using rule 11 (expr)]
'^'       [reduce using rule 11 (expr)]
$default  reduce using rule 11 (expr)

我对使用 bison 还很陌生，所以如果能提供任何帮助，我们将不胜感激，在此先感谢

Answer 1

bison 中的“冲突”告诉您所讨论的语法不是 LALR(1)——其中有些东西无法为只有 1 个标记前瞻的输入找到唯一的解析。

冗长的语法文件告诉您冲突的确切位置，但要理解它，您需要了解 shift-reduce 解析器如何识别输入。 shift-reduce 解析器基本上是一个耦合到堆栈（下推自动机或 PDA）的状态机，其中状态机跟踪哪些可能的（部分）规则生产到目前为止已经被识别，并且堆栈保存已经被识别的状态推迟。

在您的具体示例中，您有州规则：

7 expr: expr . '+' expr
7     | expr '+' expr .
8     | expr . '-' expr
9     | expr . '*' expr
10     | expr . '/' expr
11     | expr . '^' expr

这告诉您状态表示在出现 . 之前部分认可了任何这些规则。所以它可能已经识别了整个规则 expr + expr 或者它可能只是其他规则之一的初始 expr。这表明语法中存在歧义。每当您输入

形式的内容时

A + B * C

或

3 + 5 - 7

它可以将其识别为两个二进制操作，但它不知道哪个绑定更紧密——应该是 (A + B) * C 还是 A + (B * C)

Answer 2

Chris Dodd 的回答告诉您哪里出了问题。这个答案是关于如何修复它的。

你可以通过引入一堆expr产品的子产品来解决这个问题，这就是你在正式规范中经常看到的，例如

atom:   NUM | NAME | '(' expr ')'
pow:    atom '^' atom
muldiv: pow '*' pow | pow '/' pow
/* etc */

对于更复杂的语法，有时你必须这样做。但在这种情况下，使用 Bison 的 operator precedence 功能更容易。将这些行添加到 .y 文件的第一部分：

%left '+' '-'
%left '*' '/'
%left '^'

这告诉解析器生成器所有的算术运算符都是左关联的（也就是说，将 a + b + c 视为 (a + b) + c），* 和 /比 + 和 - 具有更高的优先级（即，将 a + b * c 视为 a + (b * c)），并且 ^ 仍然具有更高的优先级。这些额外信息足以消除所有冲突。

Answer 3

Bison 的部分运作方式是维护一堆符号，并在

之间反复选择

移动下一个符号从其输入到栈顶，或
减少一些符号从堆栈顶部到另一个符号。

它使用堆栈的当前内容和下一个输入符号的类型（如果有）来做出选择。

编写模棱两可的语法规则集非常容易，因为它们提供了可以进行移位或归约的状态。这是一个“shift/reduce”冲突，在你的情况下有很多这样的状态。考虑这个输入：

1 + 2 * 3

假设标记 1、2 和 3 被解析为 NUMs，我们有：

stack                input                         action
(empty)              `NUM` `+` `NUM` `*` `NUM`     shift
`NUM`                `+` `NUM` `*` `NUM`           reduce (1)
`expr`               `+` `NUM` `*` `NUM`           shift (2)
`expr` `+`           `NUM` `*` `NUM`               shift (3)
`expr` `+` `NUM`     `*` `NUM`                     reduce (1)
`expr` `+` `expr`    `*` `NUM`                       !!

我们有两个可行的选择：Bison 可以将堆栈顶部的三个符号减少为 expr，或者它可以将 * 移到堆栈上。事实上，虽然转移/减少冲突并不总是这样，但任何一种选择都可能导致成功解析，但选择很重要，因为它可以——在你的情况下确实——影响输入的解释。此时执行归约导致将输入解释为等同于 (1 + 2) * 3，而执行移位导致将输入解释为等同于 1 + (2 * 3).

在没有其他指导的情况下，Bison 默认在这些情况下移动。这通常会导致成功的解析，但并非总是如此，有时会导致成功但错误的解析。在上面的例子中，Bison 的默认设置是正确的，但在使用 1 * 2 + 3.

时会出错（相对于我们通常对运算符优先级的期望）

编写明确的语法规则显然是一项艰巨的任务。在这种情况下，需要打破表达式规则的对称性，以便左右操作数由不同的符号表示。要考虑运算符优先级，您还需要根据构成表达式的顶级运算符（如果有）区分不同类型的表达式。

备注：

(1) 没有处理 NUM 的规则，除非将其减少为 expr.

(2) 一个 expr 也可以减少到一个 line，但是 Bison 可以考虑下一个令牌类型，看看执行这样的减少会使它处于它无法继续。

(3) 没有规则可以减少以+结尾的一组符号。

如何解释 bison 中的 "shift/reduce" 冲突

how to interpret "shift/reduce" conflicts in bison

c

bison