bisoncontext-free-grammar

Shift/reduce issue in bison due to empty rule


I have the following grammar in bison that generates shift/reduce conflicts:

%token  a

%start A
%% 

A: a B C | /* empty */
;
B: D E
;
E: D E | /* empty */
;
D: error
;
C: error
;

How can I rewrite the grammar without using precedence?


Solution

  • The basic problem here is that you have an ambiguity in error recovery between C and D. After recovering the first error1 (as a D), any subsequent error can be recovered as either a C or a D, which is ambiguous. So you need to rethink what it is you are actually trying to do -- there are no (non-empty) inputs that can be recognized without an error, so it doesn't make much sense.


    1Actually, you can't even recover from the first error, as there's nothing that can legally follow a D, so it will immediately re-error (and throw away more tokens) -- the net result being that it will simply discard the rest of the input and then return a parse failure. You might be able to get something further with an action that explicitly set yyerrok, but its not clear what the point would be