share/doc/psd/15.yacc/ss0

   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 .\"     @(#)ss0 8.1 (Berkeley) 6/8/93
  38 .\"
  39 .\" $FreeBSD$
  40 .SH
  41 0: Introduction
  42 .PP
  43 Yacc provides a general tool for imposing structure on the input to a computer program.
  44 The Yacc user prepares a
  45 specification of the input process; this includes rules
  46 describing the input structure, code to be invoked when these
  47 rules are recognized, and a low-level routine to do the
  48 basic input.
  49 Yacc then generates a function to control the input process.
  50 This function, called a
  51 .I parser ,
  52 calls the user-supplied low-level input routine
  53 (the
  54 .I "lexical analyzer" )
  55 to pick up the basic items
  56 (called
  57 .I tokens )
  58 from the input stream.
  59 These tokens are organized according to the input structure rules,
  60 called
  61 .I "grammar rules" \|;
  62 when one of these rules has been recognized,
  63 then user code supplied for this rule, an
  64 .I action ,
  65 is invoked; actions have the ability to return values and
  66 make use of the values of other actions.
  67 .PP
  68 Yacc is written in a portable dialect of C
  69 .[
  70 Ritchie Kernighan Language Prentice
  71 .]
  72 and the actions, and output subroutine, are in C as well.
  73 Moreover, many of the syntactic conventions of Yacc follow C.
  74 .PP
  75 The heart of the input specification is a collection of grammar rules.
  76 Each rule describes an allowable structure and gives it a name.
  77 For example, one grammar rule might be
  78 .DS
  79 date  :  month\_name  day  \',\'  year   ;
  80 .DE
  81 Here,
  82 .I date ,
  83 .I month\_name ,
  84 .I day ,
  85 and
  86 .I year
  87 represent structures of interest in the input process;
  88 presumably,
  89 .I month\_name ,
  90 .I day ,
  91 and
  92 .I year
  93 are defined elsewhere.
  94 The comma ``,'' is enclosed in single quotes; this implies that the
  95 comma is to appear literally in the input.
  96 The colon and semicolon merely serve as punctuation in the rule, and have
  97 no significance in controlling the input.
  98 Thus, with proper definitions, the input
  99 .DS
 100 July  4, 1776
 101 .DE
 102 might be matched by the above rule.
 103 .PP
 104 An important part of the input process is carried out by the
 105 lexical analyzer.
 106 This user routine reads the input stream, recognizing the lower level structures,
 107 and communicates these tokens
 108 to the parser.
 109 For historical reasons, a structure recognized by the lexical analyzer is called a
 110 .I "terminal symbol" ,
 111 while the structure recognized by the parser is called a
 112 .I "nonterminal symbol" .
 113 To avoid confusion, terminal symbols will usually be referred to as
 114 .I tokens .
 115 .PP
 116 There is considerable leeway in deciding whether to recognize structures using the lexical
 117 analyzer or grammar rules.
 118 For example, the rules
 119 .DS
 120 month\_name  :  \'J\' \'a\' \'n\'   ;
 121 month\_name  :  \'F\' \'e\' \'b\'   ;
 122
 123          . . .
 124
 125 month\_name  :  \'D\' \'e\' \'c\'   ;
 126 .DE
 127 might be used in the above example.
 128 The lexical analyzer would only need to recognize individual letters, and
 129 .I month\_name
 130 would be a nonterminal symbol.
 131 Such low-level rules tend to waste time and space, and may
 132 complicate the specification beyond Yacc's ability to deal with it.
 133 Usually, the lexical analyzer would
 134 recognize the month names,
 135 and return an indication that a
 136 .I month\_name
 137 was seen; in this case,
 138 .I month\_name
 139 would be a token.
 140 .PP
 141 Literal characters such as ``,'' must also be passed through the lexical
 142 analyzer, and are also considered tokens.
 143 .PP
 144 Specification files are very flexible.
 145 It is realively easy to add to the above example the rule
 146 .DS
 147 date  :  month \'/\' day \'/\' year   ;
 148 .DE
 149 allowing
 150 .DS
 151 7 / 4 / 1776
 152 .DE
 153 as a synonym for
 154 .DS
 155 July 4, 1776
 156 .DE
 157 In most cases, this new rule could be ``slipped in'' to a working system with minimal effort,
 158 and little danger of disrupting existing input.
 159 .PP
 160 The input being read may not conform to the
 161 specifications.
 162 These input errors are detected as early as is theoretically possible with a
 163 left-to-right scan;
 164 thus, not only is the chance of reading and computing with bad
 165 input data substantially reduced, but the bad data can usually be quickly found.
 166 Error handling,
 167 provided as part of the input specifications,
 168 permits the reentry of bad data,
 169 or the continuation of the input process after skipping over the bad data.
 170 .PP
 171 In some cases, Yacc fails to produce a parser when given a set of
 172 specifications.
 173 For example, the specifications may be self contradictory, or they may
 174 require a more powerful recognition mechanism than that available to Yacc.
 175 The former cases represent design errors;
 176 the latter cases
 177 can often be corrected
 178 by making
 179 the lexical analyzer
 180 more powerful, or by rewriting some of the grammar rules.
 181 While Yacc cannot handle all possible specifications, its power
 182 compares favorably with similar systems;
 183 moreover, the
 184 constructions which are difficult for Yacc to handle are
 185 also frequently difficult for human beings to handle.
 186 Some users have reported that the discipline of formulating valid
 187 Yacc specifications for their input revealed errors of
 188 conception or design early in the program development.
 189 .PP
 190 The theory underlying Yacc has been described elsewhere.
 191 .[
 192 Aho Johnson Surveys LR Parsing
 193 .]
 194 .[
 195 Aho Johnson Ullman Ambiguous Grammars
 196 .]
 197 .[
 198 Aho Ullman Principles Compiler Design
 199 .]
 200 Yacc has been extensively used in numerous practical applications,
 201 including
 202 .I lint ,
 203 .[
 204 Johnson Lint
 205 .]
 206 the Portable C Compiler,
 207 .[
 208 Johnson Portable Compiler Theory
 209 .]
 210 and a system for typesetting mathematics.
 211 .[
 212 Kernighan Cherry typesetting system CACM
 213 .]
 214 .PP
 215 The next several sections describe the
 216 basic process of preparing a Yacc specification;
 217 Section 1 describes the preparation of grammar rules,
 218 Section 2 the preparation of the user supplied actions associated with these rules,
 219 and Section 3 the preparation of lexical analyzers.
 220 Section 4 describes the operation of the parser.
 221 Section 5 discusses various reasons why Yacc may be unable to produce a
 222 parser from a specification, and what to do about it.
 223 Section 6 describes a simple mechanism for
 224 handling operator precedences in arithmetic expressions.
 225 Section 7 discusses error detection and recovery.
 226 Section 8 discusses the operating environment and special features
 227 of the parsers Yacc produces.
 228 Section 9 gives some suggestions which should improve the
 229 style and efficiency of the specifications.
 230 Section 10 discusses some advanced topics, and Section 11 gives
 231 acknowledgements.
 232 Appendix A has a brief example, and Appendix B gives a
 233 summary of the Yacc input syntax.
 234 Appendix C gives an example using some of the more advanced
 235 features of Yacc, and, finally,
 236 Appendix D describes mechanisms and syntax
 237 no longer actively supported, but
 238 provided for historical continuity with older versions of Yacc.