share/doc/psd/15.yacc/ss6

   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 .\"     @(#)ss6 8.1 (Berkeley) 6/8/93
  38 .\"
  39 .\" $FreeBSD$
  40 .SH
  41 6: Precedence
  42 .PP
  43 There is one common situation
  44 where the rules given above for resolving conflicts are not sufficient;
  45 this is in the parsing of arithmetic expressions.
  46 Most of the commonly used constructions for arithmetic expressions can be naturally
  47 described by the notion of
  48 .I precedence
  49 levels for operators, together with information about left
  50 or right associativity.
  51 It turns out that ambiguous grammars with appropriate disambiguating rules
  52 can be used to create parsers that are faster and easier to
  53 write than parsers constructed from unambiguous grammars.
  54 The basic notion is to write grammar rules
  55 of the form
  56 .DS
  57 expr  :  expr  OP  expr
  58 .DE
  59 and
  60 .DS
  61 expr  :  UNARY  expr
  62 .DE
  63 for all binary and unary operators desired.
  64 This creates a very ambiguous grammar, with many parsing conflicts.
  65 As disambiguating rules, the user specifies the precedence, or binding
  66 strength, of all the operators, and the associativity
  67 of the binary operators.
  68 This information is sufficient to allow Yacc to resolve the parsing conflicts
  69 in accordance with these rules, and construct a parser that realizes the desired
  70 precedences and associativities.
  71 .PP
  72 The precedences and associativities are attached to tokens in the declarations section.
  73 This is done by a series of lines beginning with a Yacc keyword: %left, %right,
  74 or %nonassoc, followed by a list of tokens.
  75 All of the tokens on the same line are assumed to have the same precedence level
  76 and associativity; the lines are listed in
  77 order of increasing precedence or binding strength.
  78 Thus,
  79 .DS
  80 %left  \'+\'  \'\-\'
  81 %left  \'*\'  \'/\'
  82 .DE
  83 describes the precedence and associativity of the four arithmetic operators.
  84 Plus and minus are left associative, and have lower precedence than
  85 star and slash, which are also left associative.
  86 The keyword %right is used to describe right associative operators,
  87 and the keyword %nonassoc is used to describe operators, like
  88 the operator .LT. in Fortran, that may not associate with themselves; thus,
  89 .DS
  90 A  .LT.  B  .LT.  C
  91 .DE
  92 is illegal in Fortran, and such an operator would be described with the keyword
  93 %nonassoc in Yacc.
  94 As an example of the behavior of these declarations, the description
  95 .DS
  96 %right  \'=\'
  97 %left  \'+\'  \'\-\'
  98 %left  \'*\'  \'/\'
  99
 100 %%
 101
 102 expr    :       expr  \'=\'  expr
 103         |       expr  \'+\'  expr
 104         |       expr  \'\-\'  expr
 105         |       expr  \'*\'  expr
 106         |       expr  \'/\'  expr
 107         |       NAME
 108         ;
 109 .DE
 110 might be used to structure the input
 111 .DS
 112 a  =  b  =  c*d  \-  e  \-  f*g
 113 .DE
 114 as follows:
 115 .DS
 116 a = ( b = ( ((c*d)\-e) \- (f*g) ) )
 117 .DE
 118 When this mechanism is used,
 119 unary operators must, in general, be given a precedence.
 120 Sometimes a unary operator and a binary operator
 121 have the same symbolic representation, but different precedences.
 122 An example is unary and binary \'\-\'; unary minus may be given the same
 123 strength as multiplication, or even higher, while binary minus has a lower strength than
 124 multiplication.
 125 The keyword, %prec, changes the precedence level associated with a particular grammar rule.
 126 %prec appears immediately after the body of the grammar rule, before the action or closing semicolon,
 127 and is followed by a token name or literal.
 128 It
 129 causes the precedence of the grammar rule to become that of the following token name or literal.
 130 For example, to make unary minus have the same precedence as multiplication the rules might resemble:
 131 .DS
 132 %left  \'+\'  \'\-\'
 133 %left  \'*\'  \'/\'
 134
 135 %%
 136
 137 expr    :       expr  \'+\'  expr
 138         |       expr  \'\-\'  expr
 139         |       expr  \'*\'  expr
 140         |       expr  \'/\'  expr
 141         |       \'\-\'  expr      %prec  \'*\'
 142         |       NAME
 143         ;
 144 .DE
 145 .PP
 146 A token declared
 147 by %left, %right, and %nonassoc need not be, but may be, declared by %token as well.
 148 .PP
 149 The precedences and associativities are used by Yacc to
 150 resolve parsing conflicts; they give rise to disambiguating rules.
 151 Formally, the rules work as follows:
 152 .IP 1.
 153 The precedences and associativities are recorded for those tokens and literals
 154 that have them.
 155 .IP 2.
 156 A precedence and associativity is associated with each grammar rule; it is the precedence
 157 and associativity of the last token or literal in the body of the rule.
 158 If the %prec construction is used, it overrides this default.
 159 Some grammar rules may have no precedence and associativity associated with them.
 160 .IP 3.
 161 When there is a reduce/reduce conflict, or there is a shift/reduce conflict
 162 and either the input symbol or the grammar rule has no precedence and associativity,
 163 then the two disambiguating rules given at the beginning of the section are used,
 164 and the conflicts are reported.
 165 .IP 4.
 166 If there is a shift/reduce conflict, and both the grammar rule and the input character
 167 have precedence and associativity associated with them, then the conflict is resolved
 168 in favor of the action (shift or reduce) associated with the higher precedence.
 169 If the precedences are the same, then the associativity is used; left
 170 associative implies reduce, right associative implies shift, and nonassociating
 171 implies error.
 172 .PP
 173 Conflicts resolved by precedence are not counted in the number of shift/reduce and reduce/reduce
 174 conflicts reported by Yacc.
 175 This means that mistakes in the specification of precedences may
 176 disguise errors in the input grammar; it is a good idea to be sparing
 177 with precedences, and use them in an essentially ``cookbook'' fashion,
 178 until some experience has been gained.
 179 The
 180 .I y.output
 181 file
 182 is very useful in deciding whether the parser is actually doing
 183 what was intended.