cparsingbisonyaccshift-reduce-conflict

Why doesn't YACC generate shift-reduce conflict?

Trying to understand shift-reduce conflicts and fix them.

I have following YACC code, for which I was expecting shift-reduce conflict but Bison doesn't generate any such warnings

%%

lang_cons: /* empty */
         | declaraion // SEMI_COLON
         | func
    ;

declaraion : keyword ID
    ; 

func : keyword ID SEMI_COLON
    ; 

keyword : INT
    | FLOAT
    ;

%%

But if I uncomment SEMI_COLON in 2nd rule (i.e, | declaraion SEMI_COLON ), I get shift-reduce conflict. I was expecting reduce-reduce conflict in this case. Please help me understand this mess!

PS: Consider input, 

    1) int varName
    2) int func;
Solution

  • If you give bison the -v command line flag, it will produce an .output file containing the generated state machine, which will probably help you see what is going on.

    Note that bison actually parses the augmented grammar, which consists of your grammar with the additional rule

    start': start END

    where END is a special token whose code is 0, indicating the end of input, and start is whatever your grammar uses as a start symbol. (That ensures that the bison parser will not silently ignore garbage at the end of an otherwise valid input.)

    That makes your original grammar unambiguous; after varName is seen, the lookahead will be either END, in which case declaration is reduced, or ';', which will be shifted (followed by a reduction of func when the following END is seen).

    In your second grammar, the conflict involves the choice between reducing declaration or shifting the semicolon. If the semicolon were part of declaration, then you would see a reduce/reduce conflict.