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.
Next topic: Disambiguating rules
Previous topic: Interpreting the y.output file

© 2003 Caldera International, Inc. All rights reserved.
SCO OpenServer Release 5.0.7 -- 11 February 2003