Shift reduce conflict resolution
From Compiler writing
Shift/reduce and reduce/reduce conflicts are properties of a grammar. A developer has three possible ways of resolving the conflict:
- Transform the grammar so that the conflict no longer occurs.
- Specify that one of the possibilities is the default behavior. This decision may be based on knowledge of the language semantics that the possibility chosen is the only possible sensible parse, or it might have been decided to make a choice while parsing that can be fixed up later, if necessary, during semantic processing of the AST.
- Use a more sophisticated parser generator that is capable of looking further ahead in the token stream to resolve conflicts.
The first task is to understand why the conflict occurs...
The following is an example of a commonly encountered shift/reduce conflict.
stmt: IF '(' c_expr ')' stmt | IF '(' c_expr ')' stmt ELSE stmt | IDENT ';' ; c_expr: IDENT ;
when a parser based on this grammar encounters the token sequence:
if ( x ) if ( y ) a ; else b ;
it would not know whether the
else should be reduced as part of the second
if forming a
stmt or should be shifted for later reduction as part of the first
The semantics of most languages specify that the
else is associated with the closest unassociated
if, so one option is to specify that a reduce is the default behavior.
Another options is to rewrite the grammar so that the conflict does not occur...