野牛移位/减少问题将添加操作移动到子表达式中

Question

最初在示例中，

expr:
        INTEGER
        | expr '+' expr           { $$ = $1 + $3; }
        | expr '-' expr           { $$ = $1 - $3; }
        ;

我希望它“更简单”，所以我写了这个（我意识到它会为加法和减法执行“+”。但这只是一个例子）

expr:
        INTEGER
        | expr addOp expr           { $$ = $1 + $3; }
        ;

addOp:
          '+' { $$ = $1; }
        | '-' { $$ = $1; }
        ;

现在我得到了一个移位/减少错误。应该是一模一样的-_-（对我来说）。我需要做什么来解决这个问题？

编辑：为了把事情说清楚。第一个没有警告/错误。我使用 %left 来设置优先级（并且我将使用 %right 来表示 = 和其他右操作）。然而，当进入子表达式时，它似乎不适用。

Answer 1

您确定冲突仅涉及这两条规则吗？第一个应该比第二个有更多的冲突。至少使用一个前瞻符号，第二次决定转移到堆栈上有 addOp 的状态会更容易。

更新（我相信我可以证明我的理论...:-)：

$ cat q2.y
%% expr: '1' | expr '+' expr | expr '-' expr;
$ cat q3.y
%%  expr: '1' | expr addOp expr;
    addOp: '+' | '-';
$ yacc q2.y
conflicts: 4 shift/reduce
$ yacc q3.y
conflicts: 2 shift/reduce

---

话虽如此，yacc 语法有歧义是正常的，任何现实生活中的系统都可能不仅仅是一个很少但实际上是数十的转移/减少冲突。根据定义，当存在完全有效的移位可用时，就会发生这种冲突，因此，如果您不介意解析器采用该移位，则不必担心。

现在，在 yacc 中，您应该更喜欢左递归规则。您可以通过以下方式实现这一点并消除语法歧义：

$ cat q4.y
%% expr: expr addOp '1' | '1';
  addOp: '+' | '-';
$ yacc q4.y
$ 

注意：上面的示例中没有冲突。如果您喜欢现有的语法，只需执行以下操作：

 %expect 2
%%  expr: '1' | expr addOp expr;
    addOp: '+' | '-';

Answer 2

问题是该规则

expr: expr addOp expr { ..action.. }

没有优先权。通常规则会获得 RHS 上第一个标记的优先级，但此规则的 RHS 上没有标记。您需要向其添加 %prec 指令：

expr: expr addOp expr %prec '+' { ..action.. }

以显式赋予规则优先级。

请注意，这样做并不能消除原始语法中存在的移位/归约冲突。它只是根据您指定的优先级规则来解析它，这意味着 bison 不会给您有关它的消息。一般来说，使用优先级来解决冲突可能很棘手，因为它可能隐藏您可能想要以不同方式解决的冲突，或者在您编写的语法中可能无法解决的冲突。

另请参阅我对这个问题的回答