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

Question

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?

Answer 1

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.

Answer 2

When Bison sees the following:

expr '/' expr '.'

It doesn't know if this equates to:

1) expr opt_at_type '.'

OR

2) expr '/' expr opt_at_type '.'

For 1) it would reduce expr '/' expr to expr first and for 2) it would reduce /* Empty */ to opt_at_type first.

So we have discovered the ambiguity, to solve it you must determine what syntax you want. One solution would be to make the first expr rule a separate rule so that it could not be used inside the other expressions like so:

typeexpr: expr opt_at_type '.' TYPEID '(' opt_expr_list ')'