Why doesn't YACC generate shift-reduce conflict?

Question

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;

Can you indicate which shift you were expecting to conflict with which reduce, and which two reduces you were expecting to conflict? — Angew is no longer proud of SO
When SEMI_COLON is the look-ahead token, the stack will be having (keyword and ID) which are sufficient to reduce with the rule "declaration" or "func" — Vijaymahantesh Sattigeri

rici rici · Accepted Answer · 2019-08-26T07:17:27

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.

Why doesn't YACC generate shift-reduce conflict?

1 Answers