Using ambiguous rules in the yacc program

A set of grammar rules is ambiguous if any possible input string can be structured in two or more different ways.

For example, the following grammar rule states a rule that forms an arithmetic expression by putting two other expressions together with a minus sign between them.

expr : expr '-' expr

Unfortunately, this grammar rule does not specify how to structure all complex inputs. For example, if the input is:

expr - expr - expr

a program could structure this input as either left associative:

( expr - expr ) - expr

or as right associative:

expr - ( expr - expr )

and produce different results.

Parser conflicts

When the parser tries to handle an ambiguous rule, confusion can occur over which of its four actions to perform when processing the input. The following major types of conflict develop:

Conflict	Description
shift/reduce conflict	A rule can be evaluated correctly using either a shift action or a reduce action, but the result is different.
reduce/reduce conflict	A rule can be evaluated correctly using one of two different reduce actions, producing two different actions.

A shift/shift conflict is not possible. The shift/reduce and reduce/reduce conflicts result from a rule that is not completely stated. For example, using the ambiguous rule stated in the previous section, if the parser receives the input:

expr - expr - expr

after reading the first three parts, the parser has:

expr - expr

which matches the right side of the preceding grammar rule. The parser can reduce the input by applying this rule. After applying the rule, the input becomes:

expr

which is the left side of the rule. The parser then reads the final part of the input:

- expr

and reduces it. This produces a left-associative interpretation.

However, the parser can also look ahead in the input stream. If, when the parser receives the first three parts:

expr - expr

it reads the input stream until it has the next two parts, it then has the following input:

expr - expr - expr

Applying the rule to the rightmost three parts reduces them to expr. The parser then has the expression:

expr - expr

Reducing the expression once more produces a right-associative interpretation.

Therefore, at the point where the parser has read only the first three parts, it can take either of two valid actions: a shift or a reduce. If the parser has no rule to decide between the two actions, a shift/reduce conflict results.

A similar situation occurs if the parser can choose between two valid reduce actions, which is called a reduce/reduce conflict.

How the parser responds to conflicts

When shift/reduce or reduce/reduce conflicts occur, the yacc command produces a parser by selecting one of the valid steps wherever it has a choice. If you do not provide a rule that makes the choice, the yacc program uses the following rules:

In a shift/reduce conflict, choose the shift.
In a reduce/reduce conflict, reduce by the grammar rule that can be applied at the earliest point in the input stream.

Using actions within rules can cause conflicts if the action must be performed before the parser is sure which rule is being recognized. In such cases, the preceding rules result in an incorrect parser. For this reason, the yacc program reports the number of shift/reduce and reduce/reduce conflicts resolved by using the preceding rules.