bison shift reduce conflict, i don't know where

bison, conflict, parsing, reduce, shift

Solution

The y.output file tells you exactly where the conflicts are. The first one is in state 4, so if you go down to look at state 4, you see:

state 4

   99 compound_statement: '{' . '}'
  100                   | '{' . statement_list '}'

    IDENTIFIER      shift, and go to state 6
          :
    IDENTIFIER  [reduce using rule 1 (threat_as_ref)]
    IDENTIFIER  [reduce using rule 2 (func_call_start)]

This is telling you that in this state (parsing a `compound_statement`, having seen a `{`), and looking at the next token being `IDENTIFIER`, there are 3 possible things it could do -- shift the token (which would be the beginning of a `statement_list`), reduce the `threat_as_ref` empty production, or reduce the `func_call_start` empty production.

The brackets tell you that it has decided to never do those actions -- the default "prefer shift over reduce" conflict resolution means that it will always do the shift.

The problem with your grammar is these empty rules `threat_as_ref` and `func_call_start` -- they need to be reduced BEFORE shifting the IDENTIFIER, but in order to know if they're valid, the parser would need to see the tokens AFTER the identifer. `func_call_start` should only be reduced if this is the beginning of the function call (which depends on there being a `(` after the IDENTIFIER.) So the parser needs more lookahead to deal with your gramar. In your specific case, you grammar is LALR(2) (2 token lookahead would suffice), but not LALR(1), so bison can't deal with it.

Now you could fix it by just getting rid of those empty rules -- `func_call_start` has no action at all, and the action for `threat_as_ref` could be moved into the action for `variable`, but if you want those rules in the future that may be a problem.

Problem

Original source