删除 shift/reduce 与点表达式和数组的冲突

Question

抱歉，我是 Bison 的新手。我不明白这个问题以及如何解决它。如果您能 "teach me how to fish" 同时指出问题和解决方案，我将不胜感激：

%left '.' '+'
%right '(' '['

%%
 OptionalExpressions
  : { $$ = nullptr; }
  | Expressions
  ;

Expressions
  : Expression
  | Expressions ',' Expression
  ;

Expression
  : Expression '+' Expression
  | ExpressionDot
  | TOKEN_ADDROF Expression
  | ExpressionIndexable
  | ExpressionFunctionCall
  | TOKEN_INTEGER
  | TOKEN_IDENTIFIER
  | '(' Expression ')'
  ;

ExpressionDot
  : Expression '.' Expression
  ;

ExpressionIndexable
  : Expression '[' Expression ']'
  ;

ExpressionFunctionCall
  : Expression '(' OptionalExpressions ')'
  ;
%%

谢谢。

Answer 1

在下一次钓鱼探险之前，您应该仔细阅读 Bison 手册中有关 using precedence declarations and perhaps some of the related SO answers. The Bison manual also has some very useful information 的部分，了解冲突以及 Bison 提供的帮助您的工具。在这里，我基本上是按照上一个 link.

中描述的过程进行的

第一步是要求 Bison 生成解析器状态的报告，这只需要给它 -v 选项（或者 --report=all 如果你想要更多信息，这偶尔会有用).结果 .output 文件的第一行告诉您哪些州有 shift/reduce 冲突：

State 12 conflicts: 4 shift/reduce

因此下一步是查看状态 12。冲突由括号中的解析器操作指示；我将它们加粗以使它们更明显。（括号内的动作是使用默认分辨率算法消除的野牛，手册中也有描述。）


    State 12

        5 Expression: Expression . '+' Expression
        7           | TOKEN_ADDROF Expression .
       13 ExpressionDot: Expression . '.' Expression
       14 ExpressionIndexable: Expression . '[' Expression ']'
       15 ExpressionFunctionCall: Expression . '(' OptionalExpressions ')'

        '.'  shift, and go to state 15
        '+'  shift, and go to state 16
        '('  shift, and go to state 17
        '['  shift, and go to state 18

<b>        '.'       [reduce using rule 7 (Expression)]</b>
<b>        '+'       [reduce using rule 7 (Expression)]</b>
<b>        '('       [reduce using rule 7 (Expression)]</b>
<b>        '['       [reduce using rule 7 (Expression)]</b>
        $default  reduce using rule 7 (Expression)

所以在这种状态下，野牛无法应用任何优先规则，来决定在规则 7 的减少适用的情况下做什么。报告中方便地转载了规则 7：

    7           | TOKEN_ADDROF Expression .

该规则的优先级将是 TOKEN_ADDROF 终端的优先级。但该优先级未定义，因为 TOKEN_ADDROF 未出现在任何优先级中。

我们可以尝试添加它：

%left '.' '+'
%precedence TOKEN_ADDROF
%precedence '(' '['

而且，嘿，太棒了！

可以公平地问为什么我把它放在我放的地方，为什么我使用 %precedence 而不是 %left 或 %right，对于它和另一个一元运算符。

开始第二题，%precedence表示"this precedence level involves operators which cannot have a conflict resolved with associativity, so I'm not going to declare any particular associativity."

在这种情况下也是如此：一元运算符没有结合性。 3-4-7中的-可以关联到左边（(3-4)-7)）或右边（3-(4-7)）。决议将基于具有优先级 - (Expression: Expression '-' Expression) 的 Expression 产生式和具有优先级 - (-).这显然会发生。相比之下，考虑 TOKEN_ADDROF 运算符（顺便说一下，这不是 & 吗？如果是，只需将其写为字符标记即可。）这里，相关产生式，如我们已经看到了，是

Expression: TOKEN_ADDROF Expression

现在，如果前瞻标记是 TOKEN_ADDROF 怎么办？答：是语法错误，因为TOKEN_ADDROF不是二元运算符，所以不能跟在表达式后面。（可能是你有一个拼写相同的二元运算符。但在那种情况下，你会把 %prec UNOP 放在上面的产品中，然后前瞻标记不可能是 UNOP 因为词法扫描器永远不会生成该标记。）所以没有允许移位的生成，因此没有冲突。

类似的推理适用于 post固定运算符，如函数应用和下标。（以及 post 递增和 post 递减，如果适用。）在这些情况下，可以使用以下 postfix 运算符，但在 Expression POSTFIX 之前不能移动它产量减少。同样，没有可能的冲突。

所以在 postfix 运算符的情况下，唯一的优先级比较将是 between 级别，而不是级别，并且关联性不适用。如果您不小心以允许关联性的方式错误输入了语法（例如，未能在需要的地方插入 %prec UNOP 声明）而不是默默地忽略错误，则不指定关联性将导致 bison 生成冲突警告.

在这个特定的语法中，将 '[' 和 '(' 放在优先级别是不必要的，因为这些标记不会直接用于任何 Expression 产生式。这意味着语法为这些运算符提供 显式优先级 。在同一语法中同时使用优先级声明和显式优先级通常表明语法的各个部分是从不同来源复制和粘贴的。（只是说'。）尽管有时是合理的，但它通常不被认为是好的风格。在这种情况下，我建议使用显式或显式声明的优先级。

所以让我们假设需要声明优先级别。在那种情况下，为什么我将 postfix 运算符放在末尾？答：因为 postfix 操作比前缀操作绑定得更紧密，这是一般准则（虽然不是绝对规则）。例如，-arr[i] 不是的意思 (-arr)[i]。这显然是正确的，以至于大多数人都没有考虑它，尽管他们有时无法将规则应用于 *arr[i] 和 *arr++，它们 完全相同 优先关系。

希望对您有所帮助。

删除 shift/reduce 与点表达式和数组的冲突

Remove shift/reduce conflicts with dot expression and arrays

yacc

bison