Bison Shift Reduce Conflicts

Question

I am using Bison and my CFG has a Shift reduce conflict which is screwing up my precedence.

This is my code:

Decl      :  vartype T_Identifier T_Semicolon {
                                             // replace it with your implementation
                                             Identifier *id = new Identifier(@2, $2);
                                             $$ = new VarDecl(id, $1);
                                          }
      |  vartype T_Identifier T_Equal primaryExpr T_Semicolon {
                                                    Identifier *id = new Identifier(@2, $2);
                                                    $$ = new VarDecl(id, $1, $4);
                            }

      |  function_prototype T_Semicolon {$$ = $1;}
      ;

I have a shift reduce conflict for this particular rule. I want the last line (function_prototype ...) to have the highest precedence but the conflict shifts and sends me to another state. FYI, "function_prototype" is a nonterminal that has a rule of "vartype T_Identifier T_LeftParenth". This is the output file from bison:

State 28 conflicts: 1 shift/reduce
...
state 28

    4 Decl: vartype . T_Identifier T_Semicolon
    5     | vartype . T_Identifier T_Equal primaryExpr T_Semicolon
   11 fully_specified_type: vartype .

    T_Identifier  shift, and go to state 34

    T_Identifier  [reduce using rule 11 (fully_specified_type)]
...
state 34

    4 Decl: vartype T_Identifier . T_Semicolon
    5     | vartype T_Identifier . T_Equal primaryExpr T_Semicolon

    T_Equal      shift, and go to state 36
    T_Semicolon  shift, and go to state 37

State 34 skips over my "function prototype" rule! How do I fix this conflict and precedence problem?

Chris Dodd Chris Dodd · Accepted Answer · 2017-01-29T23:35:32

The conflict is between the Decl: vartype... rules and the fully_specified_type: vartype rule -- after seeing a vartype, when the lookahead is T_Identifier, it doesn't know whether this is a fully_specified type or not. So it shifts (default resolution), treating it as a simple vartype for a Decl.

In general, this sort of thing is usually a problem with more than one token lookahead being required to know how to parse things, but since you don't show anything relating to the fully_specified_type rule, its hard to say how to fix it. Most likely there is a way to refactor your grammar (perhaps just get rid of fully_qualified_type and just use vartype directly wherever it is used).

Bison Shift Reduce Conflicts

1 Answers