Shift-Reduce Conflict


The Shift-Reduce Conflict is the most common type of conflict found in grammars. It is caused when the grammar allows a rule to be reduced  for particular token, but, at the same time, allowing another rule to be shifted for that same token. As a result, the grammar is ambiguous since a program can be interpreted more than one way. This error is often caused by recursive grammar definitions where the system cannot determine when one rule is complete and another is just started.

The Lookahead Set

The Lookahead Set is used by the LALR construction algorithm to determine when to "reduce" a rule. When a configuration is complete - (e.g. the cursor is past the last symbol), the LALR algorithm reduces the rule for each token in the set. This information is stored as a series of "reduce" actions in the LALR state.

When a token is read by the LALR algorithm, it looks up token in the current state and then performs the associated action. If an entry exists with a "shift" action, the system will push the token on an internal stack and jump to the specified state. If a "reduce" action is found, the associated rule is reduced and passed to the developer. If the token is not found in the state, a syntax error occurs.

Naturally, there can only be one action for any given state. For example, if a programming language contains a terminal for the reserved word "while", only one entry for "while" can exist in the state. A shift-reduce action, therefore, is caused when the system does not know if to "shift" or "reduce" for a given token.

For more information, please consult a book on compiler theory.


Versions 2.4 and later of the GOLD Parser Builder automatically fixes Shift-Reduce Conflicts by not "reducing" when it would cause a conflict. This is the same behavior of the YACC compiler-compiler. It is best to closely check these states to determine if the "shift" is the action wanted.

The error is commonly caused by ambiguous grammars. This may not be the fault of the language being defined. Modifying the grammar can ultimately resolve the conflict. For an example of how to resolve Shift-Reduce conflicts, please see the If Statement Example Page.