ML-Yacc 错误涉及涉及 EXP 的 12 个班次/减少冲突 -> EXP BINOP EXP

Question

这是错误：

    12 shift/reduce conflicts
error:  state 34: shift/reduce conflict (shift OR, reduce by rule 11)
error:  state 34: shift/reduce conflict (shift AND, reduce by rule 11)
error:  state 34: shift/reduce conflict (shift GE, reduce by rule 11)
error:  state 34: shift/reduce conflict (shift GT, reduce by rule 11)
error:  state 34: shift/reduce conflict (shift LE, reduce by rule 11)
error:  state 34: shift/reduce conflict (shift LT, reduce by rule 11)
error:  state 34: shift/reduce conflict (shift NEQ, reduce by rule 11)
error:  state 34: shift/reduce conflict (shift EQ, reduce by rule 11)
error:  state 34: shift/reduce conflict (shift DIVIDE, reduce by rule 11)
error:  state 34: shift/reduce conflict (shift TIMES, reduce by rule 11)
error:  state 34: shift/reduce conflict (shift MINUS, reduce by rule 11)
error:  state 34: shift/reduce conflict (shift PLUS, reduce by rule 11)

这是语法：

program : exp               ()
exp:
 exp binop exp             ()
|  ID                      ()
| lvalue                 ()
| STRING                    ()
| INT                       ()
| NIL                       ()
| LPAREN expseq RPAREN      ()
| lvalue ASSIGN exp         ()
| ID LPAREN explist RPAREN  ()
| LET declist IN expseq END ()
| IF exp THEN exp ELSE exp  ()
| IF exp THEN exp           ()

binop:
    EQ      ()
|   NEQ      ()
|   LT       ()
|   GT       ()
|   LE       ()
|   GE       ()
|   AND      ()
|   OR       ()
|   PLUS     ()
|   MINUS    ()
|   TIMES    ()
|   DIVIDE   ()

我该如何解决这个问题？我是否需要重新思考语法并找到另一种方法来描述这种语法？

我也尝试声明首选项顺序（尽管我使用这些经验非常少），例如：

%nonassoc OR NEQ EQ LT LE GT GE AND
%right PLUS MINUS
%right TIMES DIVIDE

但什么都没有。

Answer 1

这些冲突都来自exp: exp binop exp规则的混乱——像 a+b*c 这样具有两个二进制操作的输入可以解析为 （a+b）*c 或 a+（b*c）。

要解决此问题，最简单的方法是为令牌和所涉及的规则设置优先级。 您已经为令牌执行此操作，但尚未为规则exp: exp binop exp执行此操作。 遗憾的是，每个规则只能设置一个优先级，并且此规则需要不同的优先级，具体取决于与binop匹配的令牌。 最简单的解决方案是复制规则并摆脱binop：

exp : exp EQ exp
    | exp NEQ exp
    | exp LE exp
    | exp GT exp
    | exp LE exp
    | exp GE exp
    | exp AND exp
    | exp OR exp
    | exp PLUS exp
    | exp MINUS exp
    | exp TIMES exp
    | exp DIVIDE exp

现在每个令牌

都有自己的规则版本，每个规则都会自动从其中的单个令牌中获取其优先级，因此您甚至不需要显式设置规则的优先级，yacc 会为您完成。