ML-Yacc ошибка относительно 12 сдвиг/свёртка с участием EXP -> EXP бинарным оператором 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

конфликтов все приходят от ambuguity из exp: exp binop exp правила - вход, как а + Ь * с с два binops может быть разобран либо как (а + б) * с или а + (б * 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 делает это за вас.