涉及 EXP -> EXP BINOP EXP 的 12 shift/reduce 冲突的 ML-Yacc 错误

ML-Yacc error concerning 12 shift/reduce conflicts involving EXP -> EXP BINOP EXP

这是错误:

    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

但什么都没有。

所有的冲突都来自于 exp: exp binop exp 规则的模糊性——像 a+b*c 这样的输入有两个 binops 可以被解析为 (a+b)*ca+(b*c).

要解决此问题,最简单的方法是为令牌设置优先级 AND 所涉及的规则。您已为令牌完成此操作,但尚未为规则 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 为你.