ML-Yacc Tiger解析器Reduce/Reduce错误

Question

在阿佩尔的“ML中的现代编译器实现”一书中，我正在进行生成Tiger解析器的Ch3编程练习。我的tiger.grm文件是here。我试图诊断的错误是一元和二元减号运算符的规则引起的reduce-reduce冲突。下面是yacc错误：

error:  state 128: reduce/reduce conflict between rule 48 and rule 46 on OR
error:  state 128: reduce/reduce conflict between rule 48 and rule 46 on AND
error:  state 128: reduce/reduce conflict between rule 48 and rule 46 on GE
error:  state 128: reduce/reduce conflict between rule 48 and rule 46 on GT
error:  state 128: reduce/reduce conflict between rule 48 and rule 46 on LE
error:  state 128: reduce/reduce conflict between rule 48 and rule 46 on LT
error:  state 128: reduce/reduce conflict between rule 48 and rule 46 on NEQ
error:  state 128: reduce/reduce conflict between rule 48 and rule 46 on EQ
error:  state 128: reduce/reduce conflict between rule 48 and rule 46 on DIVIDE
error:  state 128: reduce/reduce conflict between rule 48 and rule 46 on TIMES
error:  state 128: reduce/reduce conflict between rule 48 and rule 46 on MINUS
error:  state 128: reduce/reduce conflict between rule 48 and rule 46 on PLUS
error:  state 128: reduce/reduce conflict between rule 48 and rule 46 on RPAREN

state 128:

    boolean : exp . AND exp 
    boolean : exp . OR exp 
    arithmetic : MINUS exp .  (reduce by rule 46)
    arithmetic : exp . PLUS exp 
    arithmetic : exp . MINUS exp 
    arithmetic : exp MINUS exp .  (reduce by rule 48)
    arithmetic : exp . DIVIDE exp 
    arithmetic : exp . TIMES exp 
    comparison : exp . EQ exp 
    comparison : exp . NEQ exp 
    comparison : exp . GT exp 
    comparison : exp . LT exp 
    comparison : exp . LE exp 
    comparison : exp . GE exp 

我定义了优先级高于减号的UNARY，并在我的规则中使用%prec显式地设置了它。当然，当我删除这两条规则中的任何一条时，冲突都会消失，但是语法会错误地解析减号。

我无法诊断这个错误--有什么想法吗？

Answer 1

胡乱猜测:有没有可能您的某个规则允许exp为空？如果是这样，那么在exp可选的任何地方都会产生歧义--比如在- exp之前。

Answer 2

作为公认答案的后续(他/她是对的)-在允许exp去epsilon的序列的生产中存在错误。

下面是令人不快的代码(参见最后一行)：

sequence : LPAREN exp_sequence RPAREN ()
exp_sequence : (*epsilon*) ()
         | exp seq     ()

seq : (*epsilon*)                () (*an exp sequence can be empty*)
    | SEMICOLON exp exp_sequence () (*exps separated by semicolon*)

以下是更正后的代码：

sequence : LPAREN exp_sequence RPAREN ()
exp_sequence : (*epsilon*) ()
             | exp seq     ()

seq : (*epsilon*)                () (*an exp sequence can be empty*)
    | SEMICOLON exp seq () (*exps separated by semicolon*)