.\" @(#)ss5 6.1 (Berkeley) 5/8/86
5: Ambiguity and Conflicts
A set of grammar rules is
if there is some input string that can be structured in two or more different ways.
For example, the grammar rule
is 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
For example, if the input is
the rule allows this input to be structured as either
.I "right association" ).
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
When the parser has read the second expr, the input that it has seen:
matches the right side of the grammar rule above.
the input by applying this rule;
The parser would then read the final part of the input:
The effect of this is to take the left associative interpretation.
Alternatively, when the parser has seen
it could defer the immediate application of the rule, and continue reading
the input until it had seen
It could then apply the rule to the rightmost three symbols, reducing them to
Now the rule can be reduced once more; the effect is to
take the right associative interpretation.
the parser can do two legal things, a shift or a reduction, and has no way of
.I "shift / reduce conflict" .
It may also happen that the parser has a choice of two legal reductions;
.I "reduce / reduce conflict" .
Note that there are never any ``Shift/shift'' conflicts.
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
.I "disambiguating rule" .
Yacc invokes two disambiguating rules by default:
In a shift/reduce conflict, the default is to do the shift.
In a reduce/reduce conflict, the default is to reduce by the
grammar rule (in the input sequence).
Rule 1 implies that reductions are deferred whenever there is a choice,
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.
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
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
is a nonterminal symbol describing
conditional (logical) expressions, and
is a nonterminal symbol describing statements.
The first rule will be called the
These two rules form an ambiguous construction, since input of the form
IF ( C1 ) IF ( C2 ) S1 ELSE S2
can be structured according to these rules in two ways:
The second interpretation is the one given in most programming languages
is associated with the last preceding
In this example, consider the situation where the parser has seen
by the simple-if rule to get
and then read the remaining input,
This leads to the first of the above groupings of the input.
read, and then the right hand portion of
IF ( C1 ) IF ( C2 ) S1 ELSE S2
can be reduced by the if-else rule to get
which can be reduced by the simple-if rule.
This leads to the second of the above groupings of the input, which
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,
and particular inputs already seen, such as
In 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
The conflict messages of Yacc are best understood
by examining the verbose (\fB\-v\fR) option output file.
For example, the output corresponding to the above
23: shift/reduce conflict (shift 45, reduce 18) on ELSE
stat : IF ( cond ) stat\_ (18)
stat : IF ( cond ) stat\_ELSE stat
The 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
and the two grammar rules shown are active at this time.
The parser can do two possible things.
it is possible to shift into state
State 45 will have, as part of its description, the line
stat : IF ( cond ) stat ELSE\_stat
will have been shifted in this state.
Back in state 23, the alternative action, described by ``\fB.\fR'',
is to be done if the input symbol is not mentioned explicitly in the above actions; thus,
in this case, if the input symbol is not
the parser reduces by grammar rule 18:
stat : IF \'(\' cond \')\' stat
Once again, notice that the numbers following ``shift'' commands refer to other states,
while the numbers following ``reduce'' commands refer to grammar
file, the rule numbers are printed after those rules which can be reduced.
In most one states, there will be at most reduce action possible in the
state, and this will be the default command.
The user who encounters unexpected shift/reduce conflicts will probably want to
look at the verbose output to decide whether the default actions are appropriate.
In really tough cases, the user might need to know more about
the behavior and construction of the parser than can be covered here.
In this case, one of the theoretical references
Aho Johnson Surveys Parsing
Aho Johnson Ullman Deterministic Ambiguous
Aho Ullman Principles Design
might be consulted; the services of a local guru might also be appropriate.