Shift reduce conflict resolution

From Compiler writing

Jump to: navigation, search

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.

Conflict examples

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 ;
     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 if.

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...

Personal tools