1 .\" Copyright (C) Caldera International Inc. 2001-2002. All rights reserved.
3 .\" Redistribution and use in source and binary forms, with or without
4 .\" modification, are permitted provided that the following conditions are
7 .\" Redistributions of source code and documentation must retain the above
8 .\" copyright notice, this list of conditions and the following
11 .\" Redistributions in binary form must reproduce the above copyright
12 .\" notice, this list of conditions and the following disclaimer in the
13 .\" documentation and/or other materials provided with the distribution.
15 .\" All advertising materials mentioning features or use of this software
16 .\" must display the following acknowledgement:
18 .\" This product includes software developed or owned by Caldera
19 .\" International, Inc. Neither the name of Caldera International, Inc.
20 .\" nor the names of other contributors may be used to endorse or promote
21 .\" products derived from this software without specific prior written
24 .\" USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
25 .\" INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR
26 .\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
27 .\" WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
28 .\" DISCLAIMED. IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE
29 .\" FOR ANY DIRECT, INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 .\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 .\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
32 .\" BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
33 .\" WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
34 .\" OR OTHERWISE) RISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
35 .\" IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 .\" @(#)ss5 8.1 (Berkeley) 6/8/93
41 5: Ambiguity and Conflicts
43 A set of grammar rules is
45 if there is some input string that can be structured in two or more different ways.
46 For example, the grammar rule
48 expr : expr \'\-\' expr
50 is a natural way of expressing the fact that one way of forming an arithmetic expression
51 is to put two other expressions together with a minus sign between them.
52 Unfortunately, this grammar rule does not
53 completely specify the way that all complex inputs
55 For example, if the input is
59 the rule allows this input to be structured as either
61 ( expr \- expr ) \- expr
65 expr \- ( expr \- expr )
68 .I "left association" ,
70 .I "right association" ).
72 Yacc detects such ambiguities when it is attempting to build the parser.
73 It is instructive to consider the problem that confronts the parser when it is
74 given an input such as
78 When the parser has read the second expr, the input that it has seen:
82 matches the right side of the grammar rule above.
85 the input by applying this rule;
86 after applying the rule;
87 the input is reduced to
89 left side of the rule).
90 The parser would then read the final part of the input:
95 The effect of this is to take the left associative interpretation.
97 Alternatively, when the parser has seen
101 it could defer the immediate application of the rule, and continue reading
102 the input until it had seen
106 It could then apply the rule to the rightmost three symbols, reducing them to
112 Now the rule can be reduced once more; the effect is to
113 take the right associative interpretation.
118 the parser can do two legal things, a shift or a reduction, and has no way of
119 deciding between them.
121 .I "shift / reduce conflict" .
122 It may also happen that the parser has a choice of two legal reductions;
124 .I "reduce / reduce conflict" .
125 Note that there are never any ``Shift/shift'' conflicts.
127 When there are shift/reduce or reduce/reduce conflicts, Yacc still produces a parser.
128 It does this by selecting one of the valid steps wherever it has a choice.
129 A rule describing which choice to make in a given situation is called
131 .I "disambiguating rule" .
133 Yacc invokes two disambiguating rules by default:
135 In a shift/reduce conflict, the default is to do the shift.
137 In a reduce/reduce conflict, the default is to reduce by the
139 grammar rule (in the input sequence).
141 Rule 1 implies that reductions are deferred whenever there is a choice,
143 Rule 2 gives the user rather crude control over the behavior of the parser
144 in this situation, but reduce/reduce conflicts should be avoided whenever possible.
146 Conflicts may arise because of mistakes in input or logic, or because the grammar rules, while consistent,
147 require a more complex parser than Yacc can construct.
148 The use of actions within rules can also cause conflicts, if the action must
149 be done before the parser can be sure which rule is being recognized.
150 In these cases, the application of disambiguating rules is inappropriate,
151 and leads to an incorrect parser.
152 For this reason, Yacc
153 always reports the number of shift/reduce and reduce/reduce conflicts resolved by Rule 1 and Rule 2.
155 In general, whenever it is possible to apply disambiguating rules to produce a correct parser, it is also
156 possible to rewrite the grammar rules so that the same inputs are read but there are no
158 For this reason, most previous parser generators
159 have considered conflicts to be fatal errors.
160 Our experience has suggested that this rewriting is somewhat unnatural,
161 and produces slower parsers; thus, Yacc will produce parsers even in the presence of conflicts.
163 As an example of the power of disambiguating rules, consider a fragment from a programming
164 language involving an ``if-then-else'' construction:
166 stat : IF \'(\' cond \')\' stat
167 | IF \'(\' cond \')\' stat ELSE stat
176 is a nonterminal symbol describing
177 conditional (logical) expressions, and
179 is a nonterminal symbol describing statements.
180 The first rule will be called the
189 These two rules form an ambiguous construction, since input of the form
191 IF ( C1 ) IF ( C2 ) S1 ELSE S2
193 can be structured according to these rules in two ways:
207 The second interpretation is the one given in most programming languages
208 having this construct.
211 is associated with the last preceding
214 In this example, consider the situation where the parser has seen
216 IF ( C1 ) IF ( C2 ) S1
218 and is looking at the
222 by the simple-if rule to get
226 and then read the remaining input,
232 IF ( C1 ) stat ELSE S2
235 This leads to the first of the above groupings of the input.
237 On the other hand, the
241 read, and then the right hand portion of
243 IF ( C1 ) IF ( C2 ) S1 ELSE S2
245 can be reduced by the if-else rule to get
249 which can be reduced by the simple-if rule.
250 This leads to the second of the above groupings of the input, which
253 Once again the parser can do two valid things \- there is a shift/reduce conflict.
254 The application of disambiguating rule 1 tells the parser to shift in this case,
255 which leads to the desired grouping.
257 This shift/reduce conflict arises only when there is a particular current input symbol,
259 and particular inputs already seen, such as
261 IF ( C1 ) IF ( C2 ) S1
263 In general, there may be many conflicts, and each one
264 will be associated with an input symbol and
265 a set of previously read inputs.
266 The previously read inputs are characterized by the
270 The conflict messages of Yacc are best understood
271 by examining the verbose (\fB\-v\fR) option output file.
272 For example, the output corresponding to the above
273 conflict state might be:
275 23: shift/reduce conflict (shift 45, reduce 18) on ELSE
279 stat : IF ( cond ) stat\_ (18)
280 stat : IF ( cond ) stat\_ELSE stat
286 The first line describes the conflict, giving the state and the input symbol.
287 The ordinary state description follows, giving
288 the grammar rules active in the state, and the parser actions.
289 Recall that the underline marks the
290 portion of the grammar rules which has been seen.
291 Thus in the example, in state 23 the parser has seen input corresponding
296 and the two grammar rules shown are active at this time.
297 The parser can do two possible things.
298 If the input symbol is
300 it is possible to shift into state
302 State 45 will have, as part of its description, the line
304 stat : IF ( cond ) stat ELSE\_stat
308 will have been shifted in this state.
309 Back in state 23, the alternative action, described by ``\fB.\fR'',
310 is to be done if the input symbol is not mentioned explicitly in the above actions; thus,
311 in this case, if the input symbol is not
313 the parser reduces by grammar rule 18:
315 stat : IF \'(\' cond \')\' stat
317 Once again, notice that the numbers following ``shift'' commands refer to other states,
318 while the numbers following ``reduce'' commands refer to grammar
322 file, the rule numbers are printed after those rules which can be reduced.
323 In most one states, there will be at most reduce action possible in the
324 state, and this will be the default command.
325 The user who encounters unexpected shift/reduce conflicts will probably want to
326 look at the verbose output to decide whether the default actions are appropriate.
327 In really tough cases, the user might need to know more about
328 the behavior and construction of the parser than can be covered here.
329 In this case, one of the theoretical references
331 Aho Johnson Surveys Parsing
334 Aho Johnson Ullman Deterministic Ambiguous
337 Aho Ullman Principles Design
339 might be consulted; the services of a local guru might also be appropriate.