share/doc/psd/15.yacc/ss5

   1 .\" Copyright (C) Caldera International Inc. 2001-2002.  All rights reserved.
   2 .\"
   3 .\" Redistribution and use in source and binary forms, with or without
   4 .\" modification, are permitted provided that the following conditions are
   5 .\" met:
   6 .\"
   7 .\" Redistributions of source code and documentation must retain the above
   8 .\" copyright notice, this list of conditions and the following
   9 .\" disclaimer.
  10 .\"
  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.
  14 .\"
  15 .\" All advertising materials mentioning features or use of this software
  16 .\" must display the following acknowledgement:
  17 .\"
  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
  22 .\" permission.
  23 .\"
  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.
  36 .\"
  37 .\"     @(#)ss5 8.1 (Berkeley) 6/8/93
  38 .\"
  39 .\" $FreeBSD$
  40 .SH
  41 5: Ambiguity and Conflicts
  42 .PP
  43 A set of grammar rules is
  44 .I ambiguous
  45 if there is some input string that can be structured in two or more different ways.
  46 For example, the grammar rule
  47 .DS
  48 expr    :       expr  \'\-\'  expr
  49 .DE
  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
  54 should be structured.
  55 For example, if the input is
  56 .DS
  57 expr  \-  expr  \-  expr
  58 .DE
  59 the rule allows this input to be structured as either
  60 .DS
  61 (  expr  \-  expr  )  \-  expr
  62 .DE
  63 or as
  64 .DS
  65 expr  \-  (  expr  \-  expr  )
  66 .DE
  67 (The first is called
  68 .I "left association" ,
  69 the second
  70 .I "right association" ).
  71 .PP
  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
  75 .DS
  76 expr  \-  expr  \-  expr
  77 .DE
  78 When the parser has read the second expr, the input that it has seen:
  79 .DS
  80 expr  \-  expr
  81 .DE
  82 matches the right side of the grammar rule above.
  83 The parser could
  84 .I reduce
  85 the input by applying this rule;
  86 after applying the rule;
  87 the input is reduced to
  88 .I expr (the
  89 left side of the rule).
  90 The parser would then read the final part of the input:
  91 .DS
  92 \-  expr
  93 .DE
  94 and again reduce.
  95 The effect of this is to take the left associative interpretation.
  96 .PP
  97 Alternatively, when the parser has seen
  98 .DS
  99 expr  \-  expr
 100 .DE
 101 it could defer the immediate application of the rule, and continue reading
 102 the input until it had seen
 103 .DS
 104 expr  \-  expr  \-  expr
 105 .DE
 106 It could then apply the rule to the rightmost three symbols, reducing them to
 107 .I expr
 108 and leaving
 109 .DS
 110 expr  \-  expr
 111 .DE
 112 Now the rule can be reduced once more; the effect is to
 113 take the right associative interpretation.
 114 Thus, having read
 115 .DS
 116 expr  \-  expr
 117 .DE
 118 the parser can do two legal things, a shift or a reduction, and has no way of
 119 deciding between them.
 120 This is called a
 121 .I "shift / reduce conflict" .
 122 It may also happen that the parser has a choice of two legal reductions;
 123 this is called a
 124 .I "reduce / reduce conflict" .
 125 Note that there are never any ``Shift/shift'' conflicts.
 126 .PP
 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
 130 a
 131 .I "disambiguating rule" .
 132 .PP
 133 Yacc invokes two disambiguating rules by default:
 134 .IP 1.
 135 In a shift/reduce conflict, the default is to do the shift.
 136 .IP 2.
 137 In a reduce/reduce conflict, the default is to reduce by the
 138 .I earlier
 139 grammar rule (in the input sequence).
 140 .PP
 141 Rule 1 implies that reductions are deferred whenever there is a choice,
 142 in favor of shifts.
 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.
 145 .PP
 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.
 154 .PP
 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
 157 conflicts.
 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.
 162 .PP
 163 As an example of the power of disambiguating rules, consider a fragment from a programming
 164 language involving an ``if-then-else'' construction:
 165 .DS
 166 stat    :       IF  \'(\'  cond  \')\'  stat
 167         |       IF  \'(\'  cond  \')\'  stat  ELSE  stat
 168         ;
 169 .DE
 170 In these rules,
 171 .I IF
 172 and
 173 .I ELSE
 174 are tokens,
 175 .I cond
 176 is a nonterminal symbol describing
 177 conditional (logical) expressions, and
 178 .I stat
 179 is a nonterminal symbol describing statements.
 180 The first rule will be called the
 181 .ul
 182 simple-if
 183 rule, and the
 184 second the
 185 .ul
 186 if-else
 187 rule.
 188 .PP
 189 These two rules form an ambiguous construction, since input of the form
 190 .DS
 191 IF  (  C1  )  IF  (  C2  )  S1  ELSE  S2
 192 .DE
 193 can be structured according to these rules in two ways:
 194 .DS
 195 IF  (  C1  )  {
 196         IF  (  C2  )  S1
 197         }
 198 ELSE  S2
 199 .DE
 200 or
 201 .DS
 202 IF  (  C1  )  {
 203         IF  (  C2  )  S1
 204         ELSE  S2
 205         }
 206 .DE
 207 The second interpretation is the one given in most programming languages
 208 having this construct.
 209 Each
 210 .I ELSE
 211 is associated with the last preceding
 212 ``un-\fIELSE'\fRd''
 213 .I IF .
 214 In this example, consider the situation where the parser has seen
 215 .DS
 216 IF  (  C1  )  IF  (  C2  )  S1
 217 .DE
 218 and is looking at the
 219 .I ELSE .
 220 It can immediately
 221 reduce
 222 by the simple-if rule to get
 223 .DS
 224 IF  (  C1  )  stat
 225 .DE
 226 and then read the remaining input,
 227 .DS
 228 ELSE  S2
 229 .DE
 230 and reduce
 231 .DS
 232 IF  (  C1  )  stat  ELSE  S2
 233 .DE
 234 by the if-else rule.
 235 This leads to the first of the above groupings of the input.
 236 .PP
 237 On the other hand, the
 238 .I ELSE
 239 may be shifted,
 240 .I S2
 241 read, and then the right hand portion of
 242 .DS
 243 IF  (  C1  )  IF  (  C2  )  S1  ELSE  S2
 244 .DE
 245 can be reduced by the if-else rule to get
 246 .DS
 247 IF  (  C1  )  stat
 248 .DE
 249 which can be reduced by the simple-if rule.
 250 This leads to the second of the above groupings of the input, which
 251 is usually desired.
 252 .PP
 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.
 256 .PP
 257 This shift/reduce conflict arises only when there is a particular current input symbol,
 258 .I ELSE ,
 259 and particular inputs already seen, such as
 260 .DS
 261 IF  (  C1  )  IF  (  C2  )  S1
 262 .DE
 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
 267 state
 268 of the parser.
 269 .PP
 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:
 274 .DS L
 275 23: shift/reduce conflict (shift 45, reduce 18) on ELSE
 276
 277 state 23
 278
 279           stat  :  IF  (  cond  )  stat\_         (18)
 280           stat  :  IF  (  cond  )  stat\_ELSE  stat
 281
 282          ELSE     shift 45
 283          .        reduce 18
 284
 285 .DE
 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
 292 to
 293 .DS
 294 IF  (  cond  )  stat
 295 .DE
 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
 299 .I ELSE ,
 300 it is possible to shift into state
 301 45.
 302 State 45 will have, as part of its description, the line
 303 .DS
 304 stat  :  IF  (  cond  )  stat  ELSE\_stat
 305 .DE
 306 since the
 307 .I ELSE
 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
 312 .I ELSE ,
 313 the parser reduces by grammar rule 18:
 314 .DS
 315 stat  :  IF  \'(\'  cond  \')\'  stat
 316 .DE
 317 Once again, notice that the numbers following ``shift'' commands refer to other states,
 318 while the numbers following ``reduce'' commands refer to grammar
 319 rule numbers.
 320 In the
 321 .I y.output
 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
 330 .[
 331 Aho Johnson Surveys Parsing
 332 .]
 333 .[
 334 Aho Johnson Ullman Deterministic Ambiguous
 335 .]
 336 .[
 337 Aho Ullman Principles Design
 338 .]
 339 might be consulted; the services of a local guru might also be appropriate.