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

Question

This is the error:

    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)

This is the grammar:

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   ()

How do I solve this? Do I need to rethink the grammar and find another way to describe this grammar?

I have tried also declaring the preference order (although I have really minimal experience using these) such as:

%nonassoc OR NEQ EQ LT LE GT GE AND

%right PLUS MINUS
%right TIMES DIVIDE

but nothing.

Answer 1

The conflicts all come from the ambuguity of the exp: exp binop exp rule -- an input like a+b*c with two binops can be parsed as either (a+b)*c or a+(b*c).

To resolve this, the easiest way is to set precedences for the tokens AND the rules involved. You've done that for the tokens, but haven't done it for the rule exp: exp binop exp. Unfortunately, you can only set one precedence per rule, and this rule needs different precedences depending on which token matched binop. The easiest solution is to just replicate the rule and get rid of 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

Now each token has its own version of the rule, and each rule automatically gets its precedence from the single token in it, so you don't even need to explicitly set the precedence of the rules, yacc does it for you.