yacc

Ambiguity and conflicts

A set of grammar rules is ambiguous if there is some input string that can be structured in two or more different ways. For example, the following grammar rule is a natural way of expressing the fact that one way of forming an arithmetic expression is to join two other expressions with a minus sign.

   expr   :   expr  '-'  expr

Unfortunately, this grammar rule does not completely specify how all complex inputs should be structured.

The yacc program detects such ambiguities when it is attempting to build the parser.

Consider the problem that confronts the parser when it is given the input:

   expr  -  expr  -  expr

After the parser reads the second expr, the visible input is:

   expr  -  expr

This matches the right side of the preceding grammar rule. The parser can reduce the input by the rule. After applying this rule, the input is reduced to expr (the left side of the rule). The parser then reads the final part of the input:

   -  expr

A similar reduction then takes place. This interpretation of the rule is called the ``left associative'' interpretation.

Alternatively, the parser could defer the immediate application of the rule when it has seen:

   expr  -  expr

Instead, the parser can continue reading until it sees the whole input:

   expr  -  expr  -  expr

It can then apply the rule to the rightmost three symbols, reducing them to expr, leaving:

   expr  -  expr

Now the rule can be reduced once more. This interpretation is called ``right associative''.

Depending on which interpretation is used, the parser can do either a shift or a reduction after reading:

   expr  -  expr

This is called a shift-reduce conflict. The parser can also have a choice of two legal reductions, called a reduce-reduce conflict. There are no shift-shift conflicts.