yacc - bison shift/reduce 问题将 add op 移动到 subexpr

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: '+' | '-';