Shift Reduce Conflict for arithmetic expressions in yacc

Question

This grammar has given me conflict despite specifying precedence of operators. Even in the Dragon book it's been resolved in such a way(the way implemented as first 7 lines below) but it still gets conflict! Below is the code implemented in yacc

%right THEN_KW
%right ELSE_KW
%left XOR_KW OR_KW
%right '='
%left AND_KW ALSO_KW
%left EQ_KW LT_KW GT_KW LE_KW GE_KW
%left PLUS_KW MINUS_KW
%left MULT_KW DIV_KW MOD_KW
%right NOT_KW
arthlogicexpr -> operand | arthlogicexpr arthop arthlogicexpr

arthop -> '+' | '-' | '*' | '/' |'%'

operand -> variable

variable -> IDENTIFIER

erro in parser.output is :

state 141

   78 arthlogicexpr: arthlogicexpr . arthop arthlogicexpr
   78              | arthlogicexpr arthop arthlogicexpr .

    '+'    shift, and go to state 103
    '-'    shift, and go to state 104
    '*'    shift, and go to state 105
    '/'    shift, and go to state 106
    '%'    shift, and go to state 107

    '+'    [reduce using rule 78 (arthlogicexpr)]
    '-'    [reduce using rule 78 (arthlogicexpr)]
    '*'    [reduce using rule 78 (arthlogicexpr)]
    '/'    [reduce using rule 78 (arthlogicexpr)]
    '%'    [reduce using rule 78 (arthlogicexpr)]
    $default  reduce using rule 78 (arthlogicexpr)

    arthop  go to state 109

more info about other states :

state 103

   79 arthop: '+' .

    $default  reduce using rule 79 (arthop)


state 104

   80 arthop: '-' .

    $default  reduce using rule 80 (arthop)


state 105

   81 arthop: '*' .

    $default  reduce using rule 81 (arthop)


state 106

   82 arthop: '/' .

    $default  reduce using rule 82 (arthop)


state 107

   83 arthop: '%' .

    $default  reduce using rule 83 (arthop)

Possible duplicate of Bison Shift/reduce error for C-like language — rici

akim akim · Accepted Answer · 2017-11-23T08:21:35

Because of the way the conflict resolution is performed, you cannot factor the operators as you just did. Because you are going to specify precedences between rules and tokens, you need to tell the difference between rules that must not be treated the same way. And you do not want to treat exp: exp "+" exp as equivalent to exp: exp "*" exp.

So keep four rules, one for each operator.

If you really want to factor something you could define one rule per precedence level, but that's going to be more complex for no real added value IMHO.

A proper tool should tell you that your precedence directives (%right, etc.) are useless here. That's an hint the conflict resolution cannot use them (because of the way you wrote the grammar). I venture Bison would warn.

You should also have a look there:

Shift Reduce Conflict for arithmetic expressions in yacc

2 Answers