Shift/Reduce conflicts

Sep 16, 2013 at 9:05 PM
I created a basic Yacc grammar, however, when I try to compile it using gppg, I get the following errors:
Shift/Reduce conflict, state 0 on NOTOPERAND
Shift/Reduce conflict, state 0 on LEFT_PAREN
Shift/Reduce conflict, state 0 on LITERAL
Shift/Reduce conflict, state 0 on EXPRESSION
The parser (with semantic actions removed) looks like this:
program: parameterList
             ;
             
parameterList: /* empty */
             | parameter
             | parameterList parameter
             ;

parameter: parameter CONJUNCTION criterion
         | parameter DISJUNCTION criterion
         | criterion
         ;

criterion: NOTOPERAND criterion
         | LEFT_PAREN criterion RIGHT_PAREN
         | LITERAL
         | EXPRESSION
         ;
I don't understand why those shift/reduce errors are being thrown.Any help would be appreciated.
Sep 27, 2013 at 5:50 PM
A Shift/Reduce conflict is a conflict where the parser has two options:
  • continuing adding charaters before folding.
  • Folding immediately
For instance:
EXPRESSION DISJUNCTION EXPRESSION
This can be parsed using in a large number of structures: for instance:
parameter(criterion(EXPRESSION),DISJUNCTION,cirterion(EXPRESSION))
parameter(parameter(criterion(EXPRESSION)),DISJUNCTION,criterion(EXPRESSION))
parameter(parameter(criterion(EXPRESSION)),DISJUNCTION,parameter(criterion(EXPRESSION)))
...
You see it can be nested infinitely deep:
(parameter(parameter(...(parameter(criterion(EXPRESSION))...)))
Shifting means you will add another token, reducing means you will close the level and process one level up. This means that if you give reducing priority, you will end up with infinite deep recursion.

Therefore a LALR parser gives priority to Shift instead of Reduce operations. A shift/reduce conflict is not an error, it is a warning that you should validate the parser will act like it is supposed to be.

Only Reduce/Reduce conflicts give errors.