share/doc/psd/15.yacc/ss9

   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 .\"     @(#)ss9 8.1 (Berkeley) 6/8/93
  38 .\"
  39 .\" $FreeBSD$
  40 .SH
  41 9: Hints for Preparing Specifications
  42 .PP
  43 This section contains miscellaneous hints on preparing efficient, easy to change,
  44 and clear specifications.
  45 The individual subsections are more or less
  46 independent.
  47 .SH
  48 Input Style
  49 .PP
  50 It is difficult to
  51 provide rules with substantial actions
  52 and still have a readable specification file.
  53 The following style hints owe much to Brian Kernighan.
  54 .IP a.
  55 Use all capital letters for token names, all lower case letters for
  56 nonterminal names.
  57 This rule comes under the heading of ``knowing who to blame when
  58 things go wrong.''
  59 .IP b.
  60 Put grammar rules and actions on separate lines.
  61 This allows either to be changed without
  62 an automatic need to change the other.
  63 .IP c.
  64 Put all rules with the same left hand side together.
  65 Put the left hand side in only once, and let all
  66 following rules begin with a vertical bar.
  67 .IP d.
  68 Put a semicolon only after the last rule with a given left hand side,
  69 and put the semicolon on a separate line.
  70 This allows new rules to be easily added.
  71 .IP e.
  72 Indent rule bodies by two tab stops, and action bodies by three
  73 tab stops.
  74 .PP
  75 The example in Appendix A is written following this style, as are
  76 the examples in the text of this paper (where space permits).
  77 The user must make up his own mind about these stylistic questions;
  78 the central problem, however, is to make the rules visible through
  79 the morass of action code.
  80 .SH
  81 Left Recursion
  82 .PP
  83 The algorithm used by the Yacc parser encourages so called ``left recursive''
  84 grammar rules: rules of the form
  85 .DS
  86 name    :       name  rest_of_rule  ;
  87 .DE
  88 These rules frequently arise when
  89 writing specifications of sequences and lists:
  90 .DS
  91 list    :       item
  92         |       list  \',\'  item
  93         ;
  94 .DE
  95 and
  96 .DS
  97 seq     :       item
  98         |       seq  item
  99         ;
 100 .DE
 101 In each of these cases, the first rule
 102 will be reduced for the first item only, and the second rule
 103 will be reduced for the second and all succeeding items.
 104 .PP
 105 With right recursive rules, such as
 106 .DS
 107 seq     :       item
 108         |       item  seq
 109         ;
 110 .DE
 111 the parser would be a bit bigger, and the items would be seen, and reduced,
 112 from right to left.
 113 More seriously, an internal stack in the parser
 114 would be in danger of overflowing if a very long sequence were read.
 115 Thus, the user should use left recursion wherever reasonable.
 116 .PP
 117 It is worth considering whether a sequence with zero
 118 elements has any meaning, and if so, consider writing
 119 the sequence specification with an empty rule:
 120 .DS
 121 seq     :       /* empty */
 122         |       seq  item
 123         ;
 124 .DE
 125 Once again, the first rule would always be reduced exactly once, before the
 126 first item was read,
 127 and then the second rule would be reduced once for each item read.
 128 Permitting empty sequences
 129 often leads to increased generality.
 130 However, conflicts might arise if Yacc is asked to decide
 131 which empty sequence it has seen, when it hasn't seen enough to
 132 know!
 133 .SH
 134 Lexical Tie-ins
 135 .PP
 136 Some lexical decisions depend on context.
 137 For example, the lexical analyzer might want to
 138 delete blanks normally, but not within quoted strings.
 139 Or names might be entered into a symbol table in declarations,
 140 but not in expressions.
 141 .PP
 142 One way of handling this situation is
 143 to create a global flag that is
 144 examined by the lexical analyzer, and set by actions.
 145 For example, suppose a program
 146 consists of 0 or more declarations, followed by 0 or more statements.
 147 Consider:
 148 .DS
 149 %{
 150         int dflag;
 151 %}
 152   ...  other declarations ...
 153
 154 %%
 155
 156 prog    :       decls  stats
 157         ;
 158
 159 decls   :       /* empty */
 160                         {       dflag = 1;  }
 161         |       decls  declaration
 162         ;
 163
 164 stats   :       /* empty */
 165                         {       dflag = 0;  }
 166         |       stats  statement
 167         ;
 168
 169     ...  other rules ...
 170 .DE
 171 The flag
 172 .I dflag
 173 is now 0 when reading statements, and 1 when reading declarations,
 174 .ul
 175 except for the first token in the first statement.
 176 This token must be seen by the parser before it can tell that
 177 the declaration section has ended and the statements have
 178 begun.
 179 In many cases, this single token exception does not
 180 affect the lexical scan.
 181 .PP
 182 This kind of ``backdoor'' approach can be elaborated
 183 to a noxious degree.
 184 Nevertheless, it represents a way of doing some things
 185 that are difficult, if not impossible, to
 186 do otherwise.
 187 .SH
 188 Reserved Words
 189 .PP
 190 Some programming languages
 191 permit the user to
 192 use words like ``if'', which are normally reserved,
 193 as label or variable names, provided that such use does not
 194 conflict with the legal use of these names in the programming language.
 195 This is extremely hard to do in the framework of Yacc;
 196 it is difficult to pass information to the lexical analyzer
 197 telling it ``this instance of `if' is a keyword, and that instance is a variable''.
 198 The user can make a stab at it, using the
 199 mechanism described in the last subsection,
 200 but it is difficult.
 201 .PP
 202 A number of ways of making this easier are under advisement.
 203 Until then, it is better that the keywords be
 204 .I reserved \|;
 205 that is, be forbidden for use as variable names.
 206 There are powerful stylistic reasons for preferring this, anyway.