bisonambiguityreduce-reduce-conflict

How do I solve this reduce/reduce conflict in Bison?


Here is an excerpt from [filename].output state 94

   32 expr: expr . opt_at_type '.' TYPEID '(' opt_expr_list ')'
   39     | expr . '+' expr
   40     | expr . '-' expr
   41     | expr . '*' expr
   42     | expr . '/' expr
   42     | expr '/' expr .
   44     | expr . '<' expr
   45     | expr . LE expr
   46     | expr . '=' expr

    '@'  shift, and go to state 73

    '.'       reduce using rule 23 (opt_at_type)
    '.'       [reduce using rule 42 (expr)]
    $default  reduce using rule 42 (expr)

    opt_at_type  go to state 74

opt_at_type is defined as:

    opt_at_type:
            { $$ = idtable.add_string("SELF_TYPE"); }
            |       '@' TYPEID
            { $$ = $2;   }
            ;

and can you enlighten me why it is happening?


Solution

  • The problem you're running into is that yacc precedence levels are only taken into account to resolve shift/reduce conflicts, not reduce/reduce. In this case, the opt_at_type rule can match an empty string (it's optional), leading to a reduce/reduce conflict.

    To fix it, you need to unfactor the rule to get rid of the epsilon production:

    expr: expr '.' TYPEID '(' opt_expr_list ')'
        | expr '@' TYPEID '.' TYPEID '(' opt_expr_list ')'
        | expr '+' expr
           :
    

    Without the epsilon production, it doesn't need an early reduce, so the conflict becomes a shift/reduce conflict which can be solved by yacc precedence normally.