bison shift reduce conflict, i don't know where

Question

Grammar: http://pastebin.com/ef2jt8Rg y.output: http://pastebin.com/AEKXrrRG

I don't know where is those conflicts, someone can help me with this?

Answer 1

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.