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 '-' exprUnfortunately, 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 - exprAfter the parser reads the second expr, the visible input is:
expr - exprThis 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:
- exprA 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 - exprInstead, the parser can continue reading until it sees the whole input:
expr - expr - exprIt can then apply the rule to the rightmost three symbols, reducing them to expr, leaving:
expr - exprNow 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 - exprThis 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.