涉及 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)*c 或 a+(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 为你.
这是错误:
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)*c 或 a+(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 为你.