COMMA shift/reduce error bison

Question

A: constant
 | OPENINGBRACES B C 
;

constant: INTEGER | REAL | CHARACTER ;

C: CLOSINGBRACES
 | COMMA CLOSINGBRACES
;

B: A
 | A COMMA B 
;

this grammer is producing shift/reduce error.after running it with -v option it shows conflict in state 7 ..

**
state 7

8 B: A .
9  | A . COMMA B

COMMA  shift, and go to state 10

COMMA     [reduce using rule 8 (B)]
$default  reduce using rule 8 (B)
**

rule 8 is
8 B: A

Chris Dodd Chris Dodd · Accepted Answer · 2013-10-20T18:43:21

A shift/reduce is a CONFLICT not an ERROR -- it tells you the grammar is not LALR(1), so the parser produced by bison may only recognize a subset of your language. That may be a problem, or it might not be.

In your case, the problem comes from the fact that C has an optional COMMA before the CLOSINGBRACES, but the grammar needs to complete(reduce) the B before it can go ahead to parse the C. So when you have an input like { INT , INT , }, when it gets to the second COMMA it doesn't know whether it should reduce the B (completing the list), or shift the COMMA to get another constant to add to the list. In this case it should reduce (because the COMMA shoud be part of the C rule), but it doesn't know that without two token lookahead to see the } after the ,.

In this case, the default resolution of the shift/reduce conflict as shift means that the parser will always expect another value after the comma, so will end up parsing the language without the optional comma (as if the rule C: COMMA CLOSINGBRACES did not exist)

One easy way to fix this is to make your B rule left-recursive instead of right-recursive:

B: A
 | B COMMA A
;

This way a B is a valid prefix of a B, so the parser can always reduce a B and then add additional As on to the end of it later (after shifting the COMMA and seeing what the next token is).

COMMA shift/reduce error bison

1 Answers