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 grammar rule

expr : expr '-' expris a natural way of expressing the fact that one way of forming an arithmetic expression is to put two other expressions together with a minus sign between them. Unfortunately, this grammar rule does not completely specify the way that all complex inputs should be structured. For example, if the input is

expr - expr - exprthe rule allows this input to be structured as either

( expr - expr ) - expror as

expr - ( expr - expr )(The first is called

Yacc detects such ambiguities when it is attempting to build the parser. It is instructive to consider the problem that confronts the parser when it is given an input such as

expr - expr - exprWhen the parser has read the second expr, the input that it has seen:

expr - exprmatches the right side of the grammar rule above. The parser could

- exprand again reduce. The effect of this is to take the left associative interpretation.

Alternatively, when the parser has seen

expr - exprit could defer the immediate application of the rule, and continue reading the input until it had seen

expr - expr - exprIt could then apply the rule to the rightmost three symbols, reducing them to

expr - exprNow the rule can be reduced once more; the effect is to take the right associative interpretation. Thus, having read

expr - exprthe parser can do two legal things, a shift or a reduction, and has no way of deciding between them. This is called a

When there are shift/reduce or reduce/reduce conflicts, Yacc still produces a parser.
It does this by selecting one of the valid steps wherever it has a choice.
A rule describing which choice to make in a given situation is called
a
*"disambiguating rule" .*

Yacc invokes two disambiguating rules by default:

**1.
**
In a shift/reduce conflict, the default is to do the shift.

**2.
**
In a reduce/reduce conflict, the default is to reduce by the
*earlier*
grammar rule (in the input sequence).

Rule 1 implies that reductions are deferred whenever there is a choice, in favor of shifts. Rule 2 gives the user rather crude control over the behavior of the parser in this situation, but reduce/reduce conflicts should be avoided whenever possible.

Conflicts may arise because of mistakes in input or logic, or because the grammar rules, while consistent, require a more complex parser than Yacc can construct. The use of actions within rules can also cause conflicts, if the action must be done before the parser can be sure which rule is being recognized. In these cases, the application of disambiguating rules is inappropriate, and leads to an incorrect parser. For this reason, Yacc always reports the number of shift/reduce and reduce/reduce conflicts resolved by Rule 1 and Rule 2.

In general, whenever it is possible to apply disambiguating rules to produce a correct parser, it is also possible to rewrite the grammar rules so that the same inputs are read but there are no conflicts. For this reason, most previous parser generators have considered conflicts to be fatal errors. Our experience has suggested that this rewriting is somewhat unnatural, and produces slower parsers; thus, Yacc will produce parsers even in the presence of conflicts.

As an example of the power of disambiguating rules, consider a fragment from a programming language involving an ``if-then-else'' construction:

stat : IF '(' cond ')' stat | IF '(' cond ')' stat ELSE stat ;In these rules,

These two rules form an ambiguous construction, since input of the form

IF ( C1 ) IF ( C2 ) S1 ELSE S2can be structured according to these rules in two ways:

IF ( C1 ) { IF ( C2 ) S1 } ELSE S2or

IF ( C1 ) { IF ( C2 ) S1 ELSE S2 }The second interpretation is the one given in most programming languages having this construct. Each

IF ( C1 ) IF ( C2 ) S1and is looking at the

IF ( C1 ) statand then read the remaining input,

ELSE S2and reduce

IF ( C1 ) stat ELSE S2by the if-else rule. This leads to the first of the above groupings of the input.

On the other hand, the
*ELSE*
may be shifted,
*S2*
read, and then the right hand portion of

IF ( C1 ) IF ( C2 ) S1 ELSE S2can be reduced by the if-else rule to get

IF ( C1 ) statwhich can be reduced by the simple-if rule. This leads to the second of the above groupings of the input, which is usually desired.

Once again the parser can do two valid things - there is a shift/reduce conflict. The application of disambiguating rule 1 tells the parser to shift in this case, which leads to the desired grouping.

This shift/reduce conflict arises only when there is a particular current input symbol,
*ELSE ,*
and particular inputs already seen, such as

IF ( C1 ) IF ( C2 ) S1In general, there may be many conflicts, and each one will be associated with an input symbol and a set of previously read inputs. The previously read inputs are characterized by the state of the parser.

The conflict messages of Yacc are best understood
by examining the verbose (**-v**) option output file.
For example, the output corresponding to the above
conflict state might be:

23: shift/reduce conflict (shift 45, reduce 18) on ELSE state 23 stat : IF ( cond ) stat_ (18) stat : IF ( cond ) stat_ELSE stat ELSE shift 45 . reduce 18The first line describes the conflict, giving the state and the input symbol. The ordinary state description follows, giving the grammar rules active in the state, and the parser actions. Recall that the underline marks the portion of the grammar rules which has been seen. Thus in the example, in state 23 the parser has seen input corresponding to

IF ( cond ) statand the two grammar rules shown are active at this time. The parser can do two possible things. If the input symbol is

stat : IF ( cond ) stat ELSE_statsince the

stat : IF '(' cond ')' statOnce again, notice that the numbers following ``shift'' commands refer to other states, while the numbers following ``reduce'' commands refer to grammar rule numbers. In the

UP PREVIOUS NEXT