Reduce-Reduce Conflict

Overview

A Reduce-Reduce error is a caused when a grammar allows two or more different rules to be reduced at the same time, for the same token. When this happens, the grammar becomes ambiguous since a program can be interpreted more than one way. This error can be caused when the same rule is reached by more than one path.

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.