]> git.saurik.com Git - bison.git/blob - doc/bison.texinfo
* tests/Makefile.am ($(srcdir)/$(TESTSUITE)): No longer depend upon package.m4.
[bison.git] / doc / bison.texinfo
1 \input texinfo @c -*-texinfo-*-
2 @comment %**start of header
3 @setfilename bison.info
4 @include version.texi
5 @settitle Bison @value{VERSION}
6 @setchapternewpage odd
7
8 @iftex
9 @finalout
10 @end iftex
11
12 @c SMALL BOOK version
13 @c This edition has been formatted so that you can format and print it in
14 @c the smallbook format.
15 @c @smallbook
16
17 @c Set following if you have the new `shorttitlepage' command
18 @c @clear shorttitlepage-enabled
19 @c @set shorttitlepage-enabled
20
21 @c ISPELL CHECK: done, 14 Jan 1993 --bob
22
23 @c Check COPYRIGHT dates. should be updated in the titlepage, ifinfo
24 @c titlepage; should NOT be changed in the GPL. --mew
25
26 @iftex
27 @syncodeindex fn cp
28 @syncodeindex vr cp
29 @syncodeindex tp cp
30 @end iftex
31 @ifinfo
32 @synindex fn cp
33 @synindex vr cp
34 @synindex tp cp
35 @end ifinfo
36 @comment %**end of header
37
38 @ifinfo
39 @format
40 START-INFO-DIR-ENTRY
41 * bison: (bison). GNU Project parser generator (yacc replacement).
42 END-INFO-DIR-ENTRY
43 @end format
44 @end ifinfo
45
46 @ifinfo
47 This file documents the Bison parser generator.
48
49 Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998, 1999,
50 2000, 2001
51 Free Software Foundation, Inc.
52
53 Permission is granted to make and distribute verbatim copies of
54 this manual provided the copyright notice and this permission notice
55 are preserved on all copies.
56
57 @ignore
58 Permission is granted to process this file through Tex and print the
59 results, provided the printed document carries copying permission
60 notice identical to this one except for the removal of this paragraph
61 (this paragraph not being relevant to the printed manual).
62
63 @end ignore
64 Permission is granted to copy and distribute modified versions of this
65 manual under the conditions for verbatim copying, provided also that the
66 sections entitled ``GNU General Public License'' and ``Conditions for
67 Using Bison'' are included exactly as in the original, and provided that
68 the entire resulting derived work is distributed under the terms of a
69 permission notice identical to this one.
70
71 Permission is granted to copy and distribute translations of this manual
72 into another language, under the above conditions for modified versions,
73 except that the sections entitled ``GNU General Public License'',
74 ``Conditions for Using Bison'' and this permission notice may be
75 included in translations approved by the Free Software Foundation
76 instead of in the original English.
77 @end ifinfo
78
79 @ifset shorttitlepage-enabled
80 @shorttitlepage Bison
81 @end ifset
82 @titlepage
83 @title Bison
84 @subtitle The YACC-compatible Parser Generator
85 @subtitle @value{UPDATED}, Bison Version @value{VERSION}
86
87 @author by Charles Donnelly and Richard Stallman
88
89 @page
90 @vskip 0pt plus 1filll
91 Copyright @copyright{} 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998,
92 1999, 2000, 2001
93 Free Software Foundation, Inc.
94
95 @sp 2
96 Published by the Free Software Foundation @*
97 59 Temple Place, Suite 330 @*
98 Boston, MA 02111-1307 USA @*
99 Printed copies are available from the Free Software Foundation.@*
100 ISBN 1-882114-44-2
101
102 Permission is granted to make and distribute verbatim copies of
103 this manual provided the copyright notice and this permission notice
104 are preserved on all copies.
105
106 @ignore
107 Permission is granted to process this file through TeX and print the
108 results, provided the printed document carries copying permission
109 notice identical to this one except for the removal of this paragraph
110 (this paragraph not being relevant to the printed manual).
111
112 @end ignore
113 Permission is granted to copy and distribute modified versions of this
114 manual under the conditions for verbatim copying, provided also that the
115 sections entitled ``GNU General Public License'' and ``Conditions for
116 Using Bison'' are included exactly as in the original, and provided that
117 the entire resulting derived work is distributed under the terms of a
118 permission notice identical to this one.
119
120 Permission is granted to copy and distribute translations of this manual
121 into another language, under the above conditions for modified versions,
122 except that the sections entitled ``GNU General Public License'',
123 ``Conditions for Using Bison'' and this permission notice may be
124 included in translations approved by the Free Software Foundation
125 instead of in the original English.
126 @sp 2
127 Cover art by Etienne Suvasa.
128 @end titlepage
129
130 @contents
131
132 @ifnottex
133 @node Top
134 @top Bison
135
136 This manual documents version @value{VERSION} of Bison, updated
137 @value{UPDATED}.
138 @end ifnottex
139
140 @menu
141 * Introduction::
142 * Conditions::
143 * Copying:: The GNU General Public License says
144 how you can copy and share Bison
145
146 Tutorial sections:
147 * Concepts:: Basic concepts for understanding Bison.
148 * Examples:: Three simple explained examples of using Bison.
149
150 Reference sections:
151 * Grammar File:: Writing Bison declarations and rules.
152 * Interface:: C-language interface to the parser function @code{yyparse}.
153 * Algorithm:: How the Bison parser works at run-time.
154 * Error Recovery:: Writing rules for error recovery.
155 * Context Dependency:: What to do if your language syntax is too
156 messy for Bison to handle straightforwardly.
157 * Debugging:: Debugging Bison parsers that parse wrong.
158 * Invocation:: How to run Bison (to produce the parser source file).
159 * Table of Symbols:: All the keywords of the Bison language are explained.
160 * Glossary:: Basic concepts are explained.
161 * Copying This Manual:: License for copying this manual.
162 * Index:: Cross-references to the text.
163
164 @detailmenu --- The Detailed Node Listing ---
165
166 The Concepts of Bison
167
168 * Language and Grammar:: Languages and context-free grammars,
169 as mathematical ideas.
170 * Grammar in Bison:: How we represent grammars for Bison's sake.
171 * Semantic Values:: Each token or syntactic grouping can have
172 a semantic value (the value of an integer,
173 the name of an identifier, etc.).
174 * Semantic Actions:: Each rule can have an action containing C code.
175 * Bison Parser:: What are Bison's input and output,
176 how is the output used?
177 * Stages:: Stages in writing and running Bison grammars.
178 * Grammar Layout:: Overall structure of a Bison grammar file.
179
180 Examples
181
182 * RPN Calc:: Reverse polish notation calculator;
183 a first example with no operator precedence.
184 * Infix Calc:: Infix (algebraic) notation calculator.
185 Operator precedence is introduced.
186 * Simple Error Recovery:: Continuing after syntax errors.
187 * Location Tracking Calc:: Demonstrating the use of @@@var{n} and @@$.
188 * Multi-function Calc:: Calculator with memory and trig functions.
189 It uses multiple data-types for semantic values.
190 * Exercises:: Ideas for improving the multi-function calculator.
191
192 Reverse Polish Notation Calculator
193
194 * Decls: Rpcalc Decls. Bison and C declarations for rpcalc.
195 * Rules: Rpcalc Rules. Grammar Rules for rpcalc, with explanation.
196 * Lexer: Rpcalc Lexer. The lexical analyzer.
197 * Main: Rpcalc Main. The controlling function.
198 * Error: Rpcalc Error. The error reporting function.
199 * Gen: Rpcalc Gen. Running Bison on the grammar file.
200 * Comp: Rpcalc Compile. Run the C compiler on the output code.
201
202 Grammar Rules for @code{rpcalc}
203
204 * Rpcalc Input::
205 * Rpcalc Line::
206 * Rpcalc Expr::
207
208 Location Tracking Calculator: @code{ltcalc}
209
210 * Decls: Ltcalc Decls. Bison and C declarations for ltcalc.
211 * Rules: Ltcalc Rules. Grammar rules for ltcalc, with explanations.
212 * Lexer: Ltcalc Lexer. The lexical analyzer.
213
214 Multi-Function Calculator: @code{mfcalc}
215
216 * Decl: Mfcalc Decl. Bison declarations for multi-function calculator.
217 * Rules: Mfcalc Rules. Grammar rules for the calculator.
218 * Symtab: Mfcalc Symtab. Symbol table management subroutines.
219
220 Bison Grammar Files
221
222 * Grammar Outline:: Overall layout of the grammar file.
223 * Symbols:: Terminal and nonterminal symbols.
224 * Rules:: How to write grammar rules.
225 * Recursion:: Writing recursive rules.
226 * Semantics:: Semantic values and actions.
227 * Declarations:: All kinds of Bison declarations are described here.
228 * Multiple Parsers:: Putting more than one Bison parser in one program.
229
230 Outline of a Bison Grammar
231
232 * C Declarations:: Syntax and usage of the C declarations section.
233 * Bison Declarations:: Syntax and usage of the Bison declarations section.
234 * Grammar Rules:: Syntax and usage of the grammar rules section.
235 * C Code:: Syntax and usage of the additional C code section.
236
237 Defining Language Semantics
238
239 * Value Type:: Specifying one data type for all semantic values.
240 * Multiple Types:: Specifying several alternative data types.
241 * Actions:: An action is the semantic definition of a grammar rule.
242 * Action Types:: Specifying data types for actions to operate on.
243 * Mid-Rule Actions:: Most actions go at the end of a rule.
244 This says when, why and how to use the exceptional
245 action in the middle of a rule.
246
247 Bison Declarations
248
249 * Token Decl:: Declaring terminal symbols.
250 * Precedence Decl:: Declaring terminals with precedence and associativity.
251 * Union Decl:: Declaring the set of all semantic value types.
252 * Type Decl:: Declaring the choice of type for a nonterminal symbol.
253 * Expect Decl:: Suppressing warnings about shift/reduce conflicts.
254 * Start Decl:: Specifying the start symbol.
255 * Pure Decl:: Requesting a reentrant parser.
256 * Decl Summary:: Table of all Bison declarations.
257
258 Parser C-Language Interface
259
260 * Parser Function:: How to call @code{yyparse} and what it returns.
261 * Lexical:: You must supply a function @code{yylex}
262 which reads tokens.
263 * Error Reporting:: You must supply a function @code{yyerror}.
264 * Action Features:: Special features for use in actions.
265
266 The Lexical Analyzer Function @code{yylex}
267
268 * Calling Convention:: How @code{yyparse} calls @code{yylex}.
269 * Token Values:: How @code{yylex} must return the semantic value
270 of the token it has read.
271 * Token Positions:: How @code{yylex} must return the text position
272 (line number, etc.) of the token, if the
273 actions want that.
274 * Pure Calling:: How the calling convention differs
275 in a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}).
276
277 The Bison Parser Algorithm
278
279 * Look-Ahead:: Parser looks one token ahead when deciding what to do.
280 * Shift/Reduce:: Conflicts: when either shifting or reduction is valid.
281 * Precedence:: Operator precedence works by resolving conflicts.
282 * Contextual Precedence:: When an operator's precedence depends on context.
283 * Parser States:: The parser is a finite-state-machine with stack.
284 * Reduce/Reduce:: When two rules are applicable in the same situation.
285 * Mystery Conflicts:: Reduce/reduce conflicts that look unjustified.
286 * Stack Overflow:: What happens when stack gets full. How to avoid it.
287
288 Operator Precedence
289
290 * Why Precedence:: An example showing why precedence is needed.
291 * Using Precedence:: How to specify precedence in Bison grammars.
292 * Precedence Examples:: How these features are used in the previous example.
293 * How Precedence:: How they work.
294
295 Handling Context Dependencies
296
297 * Semantic Tokens:: Token parsing can depend on the semantic context.
298 * Lexical Tie-ins:: Token parsing can depend on the syntactic context.
299 * Tie-in Recovery:: Lexical tie-ins have implications for how
300 error recovery rules must be written.
301
302 Invoking Bison
303
304 * Bison Options:: All the options described in detail,
305 in alphabetical order by short options.
306 * Option Cross Key:: Alphabetical list of long options.
307 * VMS Invocation:: Bison command syntax on VMS.
308
309 Copying This Manual
310
311 * GNU Free Documentation License:: License for copying this manual.
312
313 @end detailmenu
314 @end menu
315
316 @node Introduction
317 @unnumbered Introduction
318 @cindex introduction
319
320 @dfn{Bison} is a general-purpose parser generator that converts a
321 grammar description for an LALR(1) context-free grammar into a C
322 program to parse that grammar. Once you are proficient with Bison,
323 you may use it to develop a wide range of language parsers, from those
324 used in simple desk calculators to complex programming languages.
325
326 Bison is upward compatible with Yacc: all properly-written Yacc grammars
327 ought to work with Bison with no change. Anyone familiar with Yacc
328 should be able to use Bison with little trouble. You need to be fluent in
329 C programming in order to use Bison or to understand this manual.
330
331 We begin with tutorial chapters that explain the basic concepts of using
332 Bison and show three explained examples, each building on the last. If you
333 don't know Bison or Yacc, start by reading these chapters. Reference
334 chapters follow which describe specific aspects of Bison in detail.
335
336 Bison was written primarily by Robert Corbett; Richard Stallman made it
337 Yacc-compatible. Wilfred Hansen of Carnegie Mellon University added
338 multi-character string literals and other features.
339
340 This edition corresponds to version @value{VERSION} of Bison.
341
342 @node Conditions
343 @unnumbered Conditions for Using Bison
344
345 As of Bison version 1.24, we have changed the distribution terms for
346 @code{yyparse} to permit using Bison's output in nonfree programs.
347 Formerly, Bison parsers could be used only in programs that were free
348 software.
349
350 The other GNU programming tools, such as the GNU C compiler, have never
351 had such a requirement. They could always be used for nonfree
352 software. The reason Bison was different was not due to a special
353 policy decision; it resulted from applying the usual General Public
354 License to all of the Bison source code.
355
356 The output of the Bison utility---the Bison parser file---contains a
357 verbatim copy of a sizable piece of Bison, which is the code for the
358 @code{yyparse} function. (The actions from your grammar are inserted
359 into this function at one point, but the rest of the function is not
360 changed.) When we applied the GPL terms to the code for @code{yyparse},
361 the effect was to restrict the use of Bison output to free software.
362
363 We didn't change the terms because of sympathy for people who want to
364 make software proprietary. @strong{Software should be free.} But we
365 concluded that limiting Bison's use to free software was doing little to
366 encourage people to make other software free. So we decided to make the
367 practical conditions for using Bison match the practical conditions for
368 using the other GNU tools.
369
370 @include gpl.texi
371
372 @node Concepts
373 @chapter The Concepts of Bison
374
375 This chapter introduces many of the basic concepts without which the
376 details of Bison will not make sense. If you do not already know how to
377 use Bison or Yacc, we suggest you start by reading this chapter carefully.
378
379 @menu
380 * Language and Grammar:: Languages and context-free grammars,
381 as mathematical ideas.
382 * Grammar in Bison:: How we represent grammars for Bison's sake.
383 * Semantic Values:: Each token or syntactic grouping can have
384 a semantic value (the value of an integer,
385 the name of an identifier, etc.).
386 * Semantic Actions:: Each rule can have an action containing C code.
387 * Locations Overview:: Tracking Locations.
388 * Bison Parser:: What are Bison's input and output,
389 how is the output used?
390 * Stages:: Stages in writing and running Bison grammars.
391 * Grammar Layout:: Overall structure of a Bison grammar file.
392 @end menu
393
394 @node Language and Grammar
395 @section Languages and Context-Free Grammars
396
397 @cindex context-free grammar
398 @cindex grammar, context-free
399 In order for Bison to parse a language, it must be described by a
400 @dfn{context-free grammar}. This means that you specify one or more
401 @dfn{syntactic groupings} and give rules for constructing them from their
402 parts. For example, in the C language, one kind of grouping is called an
403 `expression'. One rule for making an expression might be, ``An expression
404 can be made of a minus sign and another expression''. Another would be,
405 ``An expression can be an integer''. As you can see, rules are often
406 recursive, but there must be at least one rule which leads out of the
407 recursion.
408
409 @cindex BNF
410 @cindex Backus-Naur form
411 The most common formal system for presenting such rules for humans to read
412 is @dfn{Backus-Naur Form} or ``BNF'', which was developed in order to
413 specify the language Algol 60. Any grammar expressed in BNF is a
414 context-free grammar. The input to Bison is essentially machine-readable
415 BNF.
416
417 Not all context-free languages can be handled by Bison, only those
418 that are LALR(1). In brief, this means that it must be possible to
419 tell how to parse any portion of an input string with just a single
420 token of look-ahead. Strictly speaking, that is a description of an
421 LR(1) grammar, and LALR(1) involves additional restrictions that are
422 hard to explain simply; but it is rare in actual practice to find an
423 LR(1) grammar that fails to be LALR(1). @xref{Mystery Conflicts, ,
424 Mysterious Reduce/Reduce Conflicts}, for more information on this.
425
426 @cindex symbols (abstract)
427 @cindex token
428 @cindex syntactic grouping
429 @cindex grouping, syntactic
430 In the formal grammatical rules for a language, each kind of syntactic unit
431 or grouping is named by a @dfn{symbol}. Those which are built by grouping
432 smaller constructs according to grammatical rules are called
433 @dfn{nonterminal symbols}; those which can't be subdivided are called
434 @dfn{terminal symbols} or @dfn{token types}. We call a piece of input
435 corresponding to a single terminal symbol a @dfn{token}, and a piece
436 corresponding to a single nonterminal symbol a @dfn{grouping}.@refill
437
438 We can use the C language as an example of what symbols, terminal and
439 nonterminal, mean. The tokens of C are identifiers, constants (numeric and
440 string), and the various keywords, arithmetic operators and punctuation
441 marks. So the terminal symbols of a grammar for C include `identifier',
442 `number', `string', plus one symbol for each keyword, operator or
443 punctuation mark: `if', `return', `const', `static', `int', `char',
444 `plus-sign', `open-brace', `close-brace', `comma' and many more. (These
445 tokens can be subdivided into characters, but that is a matter of
446 lexicography, not grammar.)
447
448 Here is a simple C function subdivided into tokens:
449
450 @example
451 int /* @r{keyword `int'} */
452 square (x) /* @r{identifier, open-paren,} */
453 /* @r{identifier, close-paren} */
454 int x; /* @r{keyword `int', identifier, semicolon} */
455 @{ /* @r{open-brace} */
456 return x * x; /* @r{keyword `return', identifier,} */
457 /* @r{asterisk, identifier, semicolon} */
458 @} /* @r{close-brace} */
459 @end example
460
461 The syntactic groupings of C include the expression, the statement, the
462 declaration, and the function definition. These are represented in the
463 grammar of C by nonterminal symbols `expression', `statement',
464 `declaration' and `function definition'. The full grammar uses dozens of
465 additional language constructs, each with its own nonterminal symbol, in
466 order to express the meanings of these four. The example above is a
467 function definition; it contains one declaration, and one statement. In
468 the statement, each @samp{x} is an expression and so is @samp{x * x}.
469
470 Each nonterminal symbol must have grammatical rules showing how it is made
471 out of simpler constructs. For example, one kind of C statement is the
472 @code{return} statement; this would be described with a grammar rule which
473 reads informally as follows:
474
475 @quotation
476 A `statement' can be made of a `return' keyword, an `expression' and a
477 `semicolon'.
478 @end quotation
479
480 @noindent
481 There would be many other rules for `statement', one for each kind of
482 statement in C.
483
484 @cindex start symbol
485 One nonterminal symbol must be distinguished as the special one which
486 defines a complete utterance in the language. It is called the @dfn{start
487 symbol}. In a compiler, this means a complete input program. In the C
488 language, the nonterminal symbol `sequence of definitions and declarations'
489 plays this role.
490
491 For example, @samp{1 + 2} is a valid C expression---a valid part of a C
492 program---but it is not valid as an @emph{entire} C program. In the
493 context-free grammar of C, this follows from the fact that `expression' is
494 not the start symbol.
495
496 The Bison parser reads a sequence of tokens as its input, and groups the
497 tokens using the grammar rules. If the input is valid, the end result is
498 that the entire token sequence reduces to a single grouping whose symbol is
499 the grammar's start symbol. If we use a grammar for C, the entire input
500 must be a `sequence of definitions and declarations'. If not, the parser
501 reports a syntax error.
502
503 @node Grammar in Bison
504 @section From Formal Rules to Bison Input
505 @cindex Bison grammar
506 @cindex grammar, Bison
507 @cindex formal grammar
508
509 A formal grammar is a mathematical construct. To define the language
510 for Bison, you must write a file expressing the grammar in Bison syntax:
511 a @dfn{Bison grammar} file. @xref{Grammar File, ,Bison Grammar Files}.
512
513 A nonterminal symbol in the formal grammar is represented in Bison input
514 as an identifier, like an identifier in C. By convention, it should be
515 in lower case, such as @code{expr}, @code{stmt} or @code{declaration}.
516
517 The Bison representation for a terminal symbol is also called a @dfn{token
518 type}. Token types as well can be represented as C-like identifiers. By
519 convention, these identifiers should be upper case to distinguish them from
520 nonterminals: for example, @code{INTEGER}, @code{IDENTIFIER}, @code{IF} or
521 @code{RETURN}. A terminal symbol that stands for a particular keyword in
522 the language should be named after that keyword converted to upper case.
523 The terminal symbol @code{error} is reserved for error recovery.
524 @xref{Symbols}.
525
526 A terminal symbol can also be represented as a character literal, just like
527 a C character constant. You should do this whenever a token is just a
528 single character (parenthesis, plus-sign, etc.): use that same character in
529 a literal as the terminal symbol for that token.
530
531 A third way to represent a terminal symbol is with a C string constant
532 containing several characters. @xref{Symbols}, for more information.
533
534 The grammar rules also have an expression in Bison syntax. For example,
535 here is the Bison rule for a C @code{return} statement. The semicolon in
536 quotes is a literal character token, representing part of the C syntax for
537 the statement; the naked semicolon, and the colon, are Bison punctuation
538 used in every rule.
539
540 @example
541 stmt: RETURN expr ';'
542 ;
543 @end example
544
545 @noindent
546 @xref{Rules, ,Syntax of Grammar Rules}.
547
548 @node Semantic Values
549 @section Semantic Values
550 @cindex semantic value
551 @cindex value, semantic
552
553 A formal grammar selects tokens only by their classifications: for example,
554 if a rule mentions the terminal symbol `integer constant', it means that
555 @emph{any} integer constant is grammatically valid in that position. The
556 precise value of the constant is irrelevant to how to parse the input: if
557 @samp{x+4} is grammatical then @samp{x+1} or @samp{x+3989} is equally
558 grammatical.@refill
559
560 But the precise value is very important for what the input means once it is
561 parsed. A compiler is useless if it fails to distinguish between 4, 1 and
562 3989 as constants in the program! Therefore, each token in a Bison grammar
563 has both a token type and a @dfn{semantic value}. @xref{Semantics, ,Defining Language Semantics},
564 for details.
565
566 The token type is a terminal symbol defined in the grammar, such as
567 @code{INTEGER}, @code{IDENTIFIER} or @code{','}. It tells everything
568 you need to know to decide where the token may validly appear and how to
569 group it with other tokens. The grammar rules know nothing about tokens
570 except their types.@refill
571
572 The semantic value has all the rest of the information about the
573 meaning of the token, such as the value of an integer, or the name of an
574 identifier. (A token such as @code{','} which is just punctuation doesn't
575 need to have any semantic value.)
576
577 For example, an input token might be classified as token type
578 @code{INTEGER} and have the semantic value 4. Another input token might
579 have the same token type @code{INTEGER} but value 3989. When a grammar
580 rule says that @code{INTEGER} is allowed, either of these tokens is
581 acceptable because each is an @code{INTEGER}. When the parser accepts the
582 token, it keeps track of the token's semantic value.
583
584 Each grouping can also have a semantic value as well as its nonterminal
585 symbol. For example, in a calculator, an expression typically has a
586 semantic value that is a number. In a compiler for a programming
587 language, an expression typically has a semantic value that is a tree
588 structure describing the meaning of the expression.
589
590 @node Semantic Actions
591 @section Semantic Actions
592 @cindex semantic actions
593 @cindex actions, semantic
594
595 In order to be useful, a program must do more than parse input; it must
596 also produce some output based on the input. In a Bison grammar, a grammar
597 rule can have an @dfn{action} made up of C statements. Each time the
598 parser recognizes a match for that rule, the action is executed.
599 @xref{Actions}.
600
601 Most of the time, the purpose of an action is to compute the semantic value
602 of the whole construct from the semantic values of its parts. For example,
603 suppose we have a rule which says an expression can be the sum of two
604 expressions. When the parser recognizes such a sum, each of the
605 subexpressions has a semantic value which describes how it was built up.
606 The action for this rule should create a similar sort of value for the
607 newly recognized larger expression.
608
609 For example, here is a rule that says an expression can be the sum of
610 two subexpressions:
611
612 @example
613 expr: expr '+' expr @{ $$ = $1 + $3; @}
614 ;
615 @end example
616
617 @noindent
618 The action says how to produce the semantic value of the sum expression
619 from the values of the two subexpressions.
620
621 @node Locations Overview
622 @section Locations
623 @cindex location
624 @cindex textual position
625 @cindex position, textual
626
627 Many applications, like interpreters or compilers, have to produce verbose
628 and useful error messages. To achieve this, one must be able to keep track of
629 the @dfn{textual position}, or @dfn{location}, of each syntactic construct.
630 Bison provides a mechanism for handling these locations.
631
632 Each token has a semantic value. In a similar fashion, each token has an
633 associated location, but the type of locations is the same for all tokens and
634 groupings. Moreover, the output parser is equipped with a default data
635 structure for storing locations (@pxref{Locations}, for more details).
636
637 Like semantic values, locations can be reached in actions using a dedicated
638 set of constructs. In the example above, the location of the whole grouping
639 is @code{@@$}, while the locations of the subexpressions are @code{@@1} and
640 @code{@@3}.
641
642 When a rule is matched, a default action is used to compute the semantic value
643 of its left hand side (@pxref{Actions}). In the same way, another default
644 action is used for locations. However, the action for locations is general
645 enough for most cases, meaning there is usually no need to describe for each
646 rule how @code{@@$} should be formed. When building a new location for a given
647 grouping, the default behavior of the output parser is to take the beginning
648 of the first symbol, and the end of the last symbol.
649
650 @node Bison Parser
651 @section Bison Output: the Parser File
652 @cindex Bison parser
653 @cindex Bison utility
654 @cindex lexical analyzer, purpose
655 @cindex parser
656
657 When you run Bison, you give it a Bison grammar file as input. The output
658 is a C source file that parses the language described by the grammar.
659 This file is called a @dfn{Bison parser}. Keep in mind that the Bison
660 utility and the Bison parser are two distinct programs: the Bison utility
661 is a program whose output is the Bison parser that becomes part of your
662 program.
663
664 The job of the Bison parser is to group tokens into groupings according to
665 the grammar rules---for example, to build identifiers and operators into
666 expressions. As it does this, it runs the actions for the grammar rules it
667 uses.
668
669 The tokens come from a function called the @dfn{lexical analyzer} that you
670 must supply in some fashion (such as by writing it in C). The Bison parser
671 calls the lexical analyzer each time it wants a new token. It doesn't know
672 what is ``inside'' the tokens (though their semantic values may reflect
673 this). Typically the lexical analyzer makes the tokens by parsing
674 characters of text, but Bison does not depend on this. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
675
676 The Bison parser file is C code which defines a function named
677 @code{yyparse} which implements that grammar. This function does not make
678 a complete C program: you must supply some additional functions. One is
679 the lexical analyzer. Another is an error-reporting function which the
680 parser calls to report an error. In addition, a complete C program must
681 start with a function called @code{main}; you have to provide this, and
682 arrange for it to call @code{yyparse} or the parser will never run.
683 @xref{Interface, ,Parser C-Language Interface}.
684
685 Aside from the token type names and the symbols in the actions you
686 write, all variable and function names used in the Bison parser file
687 begin with @samp{yy} or @samp{YY}. This includes interface functions
688 such as the lexical analyzer function @code{yylex}, the error reporting
689 function @code{yyerror} and the parser function @code{yyparse} itself.
690 This also includes numerous identifiers used for internal purposes.
691 Therefore, you should avoid using C identifiers starting with @samp{yy}
692 or @samp{YY} in the Bison grammar file except for the ones defined in
693 this manual.
694
695 @node Stages
696 @section Stages in Using Bison
697 @cindex stages in using Bison
698 @cindex using Bison
699
700 The actual language-design process using Bison, from grammar specification
701 to a working compiler or interpreter, has these parts:
702
703 @enumerate
704 @item
705 Formally specify the grammar in a form recognized by Bison
706 (@pxref{Grammar File, ,Bison Grammar Files}). For each grammatical rule in the language,
707 describe the action that is to be taken when an instance of that rule
708 is recognized. The action is described by a sequence of C statements.
709
710 @item
711 Write a lexical analyzer to process input and pass tokens to the
712 parser. The lexical analyzer may be written by hand in C
713 (@pxref{Lexical, ,The Lexical Analyzer Function @code{yylex}}). It could also be produced using Lex, but the use
714 of Lex is not discussed in this manual.
715
716 @item
717 Write a controlling function that calls the Bison-produced parser.
718
719 @item
720 Write error-reporting routines.
721 @end enumerate
722
723 To turn this source code as written into a runnable program, you
724 must follow these steps:
725
726 @enumerate
727 @item
728 Run Bison on the grammar to produce the parser.
729
730 @item
731 Compile the code output by Bison, as well as any other source files.
732
733 @item
734 Link the object files to produce the finished product.
735 @end enumerate
736
737 @node Grammar Layout
738 @section The Overall Layout of a Bison Grammar
739 @cindex grammar file
740 @cindex file format
741 @cindex format of grammar file
742 @cindex layout of Bison grammar
743
744 The input file for the Bison utility is a @dfn{Bison grammar file}. The
745 general form of a Bison grammar file is as follows:
746
747 @example
748 %@{
749 @var{C declarations}
750 %@}
751
752 @var{Bison declarations}
753
754 %%
755 @var{Grammar rules}
756 %%
757 @var{Additional C code}
758 @end example
759
760 @noindent
761 The @samp{%%}, @samp{%@{} and @samp{%@}} are punctuation that appears
762 in every Bison grammar file to separate the sections.
763
764 The C declarations may define types and variables used in the actions.
765 You can also use preprocessor commands to define macros used there, and use
766 @code{#include} to include header files that do any of these things.
767
768 The Bison declarations declare the names of the terminal and nonterminal
769 symbols, and may also describe operator precedence and the data types of
770 semantic values of various symbols.
771
772 The grammar rules define how to construct each nonterminal symbol from its
773 parts.
774
775 The additional C code can contain any C code you want to use. Often the
776 definition of the lexical analyzer @code{yylex} goes here, plus subroutines
777 called by the actions in the grammar rules. In a simple program, all the
778 rest of the program can go here.
779
780 @node Examples
781 @chapter Examples
782 @cindex simple examples
783 @cindex examples, simple
784
785 Now we show and explain three sample programs written using Bison: a
786 reverse polish notation calculator, an algebraic (infix) notation
787 calculator, and a multi-function calculator. All three have been tested
788 under BSD Unix 4.3; each produces a usable, though limited, interactive
789 desk-top calculator.
790
791 These examples are simple, but Bison grammars for real programming
792 languages are written the same way.
793 @ifinfo
794 You can copy these examples out of the Info file and into a source file
795 to try them.
796 @end ifinfo
797
798 @menu
799 * RPN Calc:: Reverse polish notation calculator;
800 a first example with no operator precedence.
801 * Infix Calc:: Infix (algebraic) notation calculator.
802 Operator precedence is introduced.
803 * Simple Error Recovery:: Continuing after syntax errors.
804 * Location Tracking Calc:: Demonstrating the use of @@@var{n} and @@$.
805 * Multi-function Calc:: Calculator with memory and trig functions.
806 It uses multiple data-types for semantic values.
807 * Exercises:: Ideas for improving the multi-function calculator.
808 @end menu
809
810 @node RPN Calc
811 @section Reverse Polish Notation Calculator
812 @cindex reverse polish notation
813 @cindex polish notation calculator
814 @cindex @code{rpcalc}
815 @cindex calculator, simple
816
817 The first example is that of a simple double-precision @dfn{reverse polish
818 notation} calculator (a calculator using postfix operators). This example
819 provides a good starting point, since operator precedence is not an issue.
820 The second example will illustrate how operator precedence is handled.
821
822 The source code for this calculator is named @file{rpcalc.y}. The
823 @samp{.y} extension is a convention used for Bison input files.
824
825 @menu
826 * Decls: Rpcalc Decls. Bison and C declarations for rpcalc.
827 * Rules: Rpcalc Rules. Grammar Rules for rpcalc, with explanation.
828 * Lexer: Rpcalc Lexer. The lexical analyzer.
829 * Main: Rpcalc Main. The controlling function.
830 * Error: Rpcalc Error. The error reporting function.
831 * Gen: Rpcalc Gen. Running Bison on the grammar file.
832 * Comp: Rpcalc Compile. Run the C compiler on the output code.
833 @end menu
834
835 @node Rpcalc Decls
836 @subsection Declarations for @code{rpcalc}
837
838 Here are the C and Bison declarations for the reverse polish notation
839 calculator. As in C, comments are placed between @samp{/*@dots{}*/}.
840
841 @example
842 /* Reverse polish notation calculator. */
843
844 %@{
845 #define YYSTYPE double
846 #include <math.h>
847 %@}
848
849 %token NUM
850
851 %% /* Grammar rules and actions follow */
852 @end example
853
854 The C declarations section (@pxref{C Declarations, ,The C Declarations Section}) contains two
855 preprocessor directives.
856
857 The @code{#define} directive defines the macro @code{YYSTYPE}, thus
858 specifying the C data type for semantic values of both tokens and groupings
859 (@pxref{Value Type, ,Data Types of Semantic Values}). The Bison parser will use whatever type
860 @code{YYSTYPE} is defined as; if you don't define it, @code{int} is the
861 default. Because we specify @code{double}, each token and each expression
862 has an associated value, which is a floating point number.
863
864 The @code{#include} directive is used to declare the exponentiation
865 function @code{pow}.
866
867 The second section, Bison declarations, provides information to Bison about
868 the token types (@pxref{Bison Declarations, ,The Bison Declarations Section}). Each terminal symbol that is
869 not a single-character literal must be declared here. (Single-character
870 literals normally don't need to be declared.) In this example, all the
871 arithmetic operators are designated by single-character literals, so the
872 only terminal symbol that needs to be declared is @code{NUM}, the token
873 type for numeric constants.
874
875 @node Rpcalc Rules
876 @subsection Grammar Rules for @code{rpcalc}
877
878 Here are the grammar rules for the reverse polish notation calculator.
879
880 @example
881 input: /* empty */
882 | input line
883 ;
884
885 line: '\n'
886 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
887 ;
888
889 exp: NUM @{ $$ = $1; @}
890 | exp exp '+' @{ $$ = $1 + $2; @}
891 | exp exp '-' @{ $$ = $1 - $2; @}
892 | exp exp '*' @{ $$ = $1 * $2; @}
893 | exp exp '/' @{ $$ = $1 / $2; @}
894 /* Exponentiation */
895 | exp exp '^' @{ $$ = pow ($1, $2); @}
896 /* Unary minus */
897 | exp 'n' @{ $$ = -$1; @}
898 ;
899 %%
900 @end example
901
902 The groupings of the rpcalc ``language'' defined here are the expression
903 (given the name @code{exp}), the line of input (@code{line}), and the
904 complete input transcript (@code{input}). Each of these nonterminal
905 symbols has several alternate rules, joined by the @samp{|} punctuator
906 which is read as ``or''. The following sections explain what these rules
907 mean.
908
909 The semantics of the language is determined by the actions taken when a
910 grouping is recognized. The actions are the C code that appears inside
911 braces. @xref{Actions}.
912
913 You must specify these actions in C, but Bison provides the means for
914 passing semantic values between the rules. In each action, the
915 pseudo-variable @code{$$} stands for the semantic value for the grouping
916 that the rule is going to construct. Assigning a value to @code{$$} is the
917 main job of most actions. The semantic values of the components of the
918 rule are referred to as @code{$1}, @code{$2}, and so on.
919
920 @menu
921 * Rpcalc Input::
922 * Rpcalc Line::
923 * Rpcalc Expr::
924 @end menu
925
926 @node Rpcalc Input
927 @subsubsection Explanation of @code{input}
928
929 Consider the definition of @code{input}:
930
931 @example
932 input: /* empty */
933 | input line
934 ;
935 @end example
936
937 This definition reads as follows: ``A complete input is either an empty
938 string, or a complete input followed by an input line''. Notice that
939 ``complete input'' is defined in terms of itself. This definition is said
940 to be @dfn{left recursive} since @code{input} appears always as the
941 leftmost symbol in the sequence. @xref{Recursion, ,Recursive Rules}.
942
943 The first alternative is empty because there are no symbols between the
944 colon and the first @samp{|}; this means that @code{input} can match an
945 empty string of input (no tokens). We write the rules this way because it
946 is legitimate to type @kbd{Ctrl-d} right after you start the calculator.
947 It's conventional to put an empty alternative first and write the comment
948 @samp{/* empty */} in it.
949
950 The second alternate rule (@code{input line}) handles all nontrivial input.
951 It means, ``After reading any number of lines, read one more line if
952 possible.'' The left recursion makes this rule into a loop. Since the
953 first alternative matches empty input, the loop can be executed zero or
954 more times.
955
956 The parser function @code{yyparse} continues to process input until a
957 grammatical error is seen or the lexical analyzer says there are no more
958 input tokens; we will arrange for the latter to happen at end of file.
959
960 @node Rpcalc Line
961 @subsubsection Explanation of @code{line}
962
963 Now consider the definition of @code{line}:
964
965 @example
966 line: '\n'
967 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
968 ;
969 @end example
970
971 The first alternative is a token which is a newline character; this means
972 that rpcalc accepts a blank line (and ignores it, since there is no
973 action). The second alternative is an expression followed by a newline.
974 This is the alternative that makes rpcalc useful. The semantic value of
975 the @code{exp} grouping is the value of @code{$1} because the @code{exp} in
976 question is the first symbol in the alternative. The action prints this
977 value, which is the result of the computation the user asked for.
978
979 This action is unusual because it does not assign a value to @code{$$}. As
980 a consequence, the semantic value associated with the @code{line} is
981 uninitialized (its value will be unpredictable). This would be a bug if
982 that value were ever used, but we don't use it: once rpcalc has printed the
983 value of the user's input line, that value is no longer needed.
984
985 @node Rpcalc Expr
986 @subsubsection Explanation of @code{expr}
987
988 The @code{exp} grouping has several rules, one for each kind of expression.
989 The first rule handles the simplest expressions: those that are just numbers.
990 The second handles an addition-expression, which looks like two expressions
991 followed by a plus-sign. The third handles subtraction, and so on.
992
993 @example
994 exp: NUM
995 | exp exp '+' @{ $$ = $1 + $2; @}
996 | exp exp '-' @{ $$ = $1 - $2; @}
997 @dots{}
998 ;
999 @end example
1000
1001 We have used @samp{|} to join all the rules for @code{exp}, but we could
1002 equally well have written them separately:
1003
1004 @example
1005 exp: NUM ;
1006 exp: exp exp '+' @{ $$ = $1 + $2; @} ;
1007 exp: exp exp '-' @{ $$ = $1 - $2; @} ;
1008 @dots{}
1009 @end example
1010
1011 Most of the rules have actions that compute the value of the expression in
1012 terms of the value of its parts. For example, in the rule for addition,
1013 @code{$1} refers to the first component @code{exp} and @code{$2} refers to
1014 the second one. The third component, @code{'+'}, has no meaningful
1015 associated semantic value, but if it had one you could refer to it as
1016 @code{$3}. When @code{yyparse} recognizes a sum expression using this
1017 rule, the sum of the two subexpressions' values is produced as the value of
1018 the entire expression. @xref{Actions}.
1019
1020 You don't have to give an action for every rule. When a rule has no
1021 action, Bison by default copies the value of @code{$1} into @code{$$}.
1022 This is what happens in the first rule (the one that uses @code{NUM}).
1023
1024 The formatting shown here is the recommended convention, but Bison does
1025 not require it. You can add or change whitespace as much as you wish.
1026 For example, this:
1027
1028 @example
1029 exp : NUM | exp exp '+' @{$$ = $1 + $2; @} | @dots{}
1030 @end example
1031
1032 @noindent
1033 means the same thing as this:
1034
1035 @example
1036 exp: NUM
1037 | exp exp '+' @{ $$ = $1 + $2; @}
1038 | @dots{}
1039 @end example
1040
1041 @noindent
1042 The latter, however, is much more readable.
1043
1044 @node Rpcalc Lexer
1045 @subsection The @code{rpcalc} Lexical Analyzer
1046 @cindex writing a lexical analyzer
1047 @cindex lexical analyzer, writing
1048
1049 The lexical analyzer's job is low-level parsing: converting characters or
1050 sequences of characters into tokens. The Bison parser gets its tokens by
1051 calling the lexical analyzer. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
1052
1053 Only a simple lexical analyzer is needed for the RPN calculator. This
1054 lexical analyzer skips blanks and tabs, then reads in numbers as
1055 @code{double} and returns them as @code{NUM} tokens. Any other character
1056 that isn't part of a number is a separate token. Note that the token-code
1057 for such a single-character token is the character itself.
1058
1059 The return value of the lexical analyzer function is a numeric code which
1060 represents a token type. The same text used in Bison rules to stand for
1061 this token type is also a C expression for the numeric code for the type.
1062 This works in two ways. If the token type is a character literal, then its
1063 numeric code is the ASCII code for that character; you can use the same
1064 character literal in the lexical analyzer to express the number. If the
1065 token type is an identifier, that identifier is defined by Bison as a C
1066 macro whose definition is the appropriate number. In this example,
1067 therefore, @code{NUM} becomes a macro for @code{yylex} to use.
1068
1069 The semantic value of the token (if it has one) is stored into the global
1070 variable @code{yylval}, which is where the Bison parser will look for it.
1071 (The C data type of @code{yylval} is @code{YYSTYPE}, which was defined
1072 at the beginning of the grammar; @pxref{Rpcalc Decls, ,Declarations for @code{rpcalc}}.)
1073
1074 A token type code of zero is returned if the end-of-file is encountered.
1075 (Bison recognizes any nonpositive value as indicating the end of the
1076 input.)
1077
1078 Here is the code for the lexical analyzer:
1079
1080 @example
1081 @group
1082 /* Lexical analyzer returns a double floating point
1083 number on the stack and the token NUM, or the ASCII
1084 character read if not a number. Skips all blanks
1085 and tabs, returns 0 for EOF. */
1086
1087 #include <ctype.h>
1088 @end group
1089
1090 @group
1091 int
1092 yylex (void)
1093 @{
1094 int c;
1095
1096 /* skip white space */
1097 while ((c = getchar ()) == ' ' || c == '\t')
1098 ;
1099 @end group
1100 @group
1101 /* process numbers */
1102 if (c == '.' || isdigit (c))
1103 @{
1104 ungetc (c, stdin);
1105 scanf ("%lf", &yylval);
1106 return NUM;
1107 @}
1108 @end group
1109 @group
1110 /* return end-of-file */
1111 if (c == EOF)
1112 return 0;
1113 /* return single chars */
1114 return c;
1115 @}
1116 @end group
1117 @end example
1118
1119 @node Rpcalc Main
1120 @subsection The Controlling Function
1121 @cindex controlling function
1122 @cindex main function in simple example
1123
1124 In keeping with the spirit of this example, the controlling function is
1125 kept to the bare minimum. The only requirement is that it call
1126 @code{yyparse} to start the process of parsing.
1127
1128 @example
1129 @group
1130 int
1131 main (void)
1132 @{
1133 return yyparse ();
1134 @}
1135 @end group
1136 @end example
1137
1138 @node Rpcalc Error
1139 @subsection The Error Reporting Routine
1140 @cindex error reporting routine
1141
1142 When @code{yyparse} detects a syntax error, it calls the error reporting
1143 function @code{yyerror} to print an error message (usually but not
1144 always @code{"parse error"}). It is up to the programmer to supply
1145 @code{yyerror} (@pxref{Interface, ,Parser C-Language Interface}), so
1146 here is the definition we will use:
1147
1148 @example
1149 @group
1150 #include <stdio.h>
1151
1152 void
1153 yyerror (const char *s) /* Called by yyparse on error */
1154 @{
1155 printf ("%s\n", s);
1156 @}
1157 @end group
1158 @end example
1159
1160 After @code{yyerror} returns, the Bison parser may recover from the error
1161 and continue parsing if the grammar contains a suitable error rule
1162 (@pxref{Error Recovery}). Otherwise, @code{yyparse} returns nonzero. We
1163 have not written any error rules in this example, so any invalid input will
1164 cause the calculator program to exit. This is not clean behavior for a
1165 real calculator, but it is adequate for the first example.
1166
1167 @node Rpcalc Gen
1168 @subsection Running Bison to Make the Parser
1169 @cindex running Bison (introduction)
1170
1171 Before running Bison to produce a parser, we need to decide how to
1172 arrange all the source code in one or more source files. For such a
1173 simple example, the easiest thing is to put everything in one file. The
1174 definitions of @code{yylex}, @code{yyerror} and @code{main} go at the
1175 end, in the ``additional C code'' section of the file (@pxref{Grammar
1176 Layout, ,The Overall Layout of a Bison Grammar}).
1177
1178 For a large project, you would probably have several source files, and use
1179 @code{make} to arrange to recompile them.
1180
1181 With all the source in a single file, you use the following command to
1182 convert it into a parser file:
1183
1184 @example
1185 bison @var{file_name}.y
1186 @end example
1187
1188 @noindent
1189 In this example the file was called @file{rpcalc.y} (for ``Reverse Polish
1190 CALCulator''). Bison produces a file named @file{@var{file_name}.tab.c},
1191 removing the @samp{.y} from the original file name. The file output by
1192 Bison contains the source code for @code{yyparse}. The additional
1193 functions in the input file (@code{yylex}, @code{yyerror} and @code{main})
1194 are copied verbatim to the output.
1195
1196 @node Rpcalc Compile
1197 @subsection Compiling the Parser File
1198 @cindex compiling the parser
1199
1200 Here is how to compile and run the parser file:
1201
1202 @example
1203 @group
1204 # @r{List files in current directory.}
1205 % ls
1206 rpcalc.tab.c rpcalc.y
1207 @end group
1208
1209 @group
1210 # @r{Compile the Bison parser.}
1211 # @r{@samp{-lm} tells compiler to search math library for @code{pow}.}
1212 % cc rpcalc.tab.c -lm -o rpcalc
1213 @end group
1214
1215 @group
1216 # @r{List files again.}
1217 % ls
1218 rpcalc rpcalc.tab.c rpcalc.y
1219 @end group
1220 @end example
1221
1222 The file @file{rpcalc} now contains the executable code. Here is an
1223 example session using @code{rpcalc}.
1224
1225 @example
1226 % rpcalc
1227 4 9 +
1228 13
1229 3 7 + 3 4 5 *+-
1230 -13
1231 3 7 + 3 4 5 * + - n @r{Note the unary minus, @samp{n}}
1232 13
1233 5 6 / 4 n +
1234 -3.166666667
1235 3 4 ^ @r{Exponentiation}
1236 81
1237 ^D @r{End-of-file indicator}
1238 %
1239 @end example
1240
1241 @node Infix Calc
1242 @section Infix Notation Calculator: @code{calc}
1243 @cindex infix notation calculator
1244 @cindex @code{calc}
1245 @cindex calculator, infix notation
1246
1247 We now modify rpcalc to handle infix operators instead of postfix. Infix
1248 notation involves the concept of operator precedence and the need for
1249 parentheses nested to arbitrary depth. Here is the Bison code for
1250 @file{calc.y}, an infix desk-top calculator.
1251
1252 @example
1253 /* Infix notation calculator--calc */
1254
1255 %@{
1256 #define YYSTYPE double
1257 #include <math.h>
1258 %@}
1259
1260 /* BISON Declarations */
1261 %token NUM
1262 %left '-' '+'
1263 %left '*' '/'
1264 %left NEG /* negation--unary minus */
1265 %right '^' /* exponentiation */
1266
1267 /* Grammar follows */
1268 %%
1269 input: /* empty string */
1270 | input line
1271 ;
1272
1273 line: '\n'
1274 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1275 ;
1276
1277 exp: NUM @{ $$ = $1; @}
1278 | exp '+' exp @{ $$ = $1 + $3; @}
1279 | exp '-' exp @{ $$ = $1 - $3; @}
1280 | exp '*' exp @{ $$ = $1 * $3; @}
1281 | exp '/' exp @{ $$ = $1 / $3; @}
1282 | '-' exp %prec NEG @{ $$ = -$2; @}
1283 | exp '^' exp @{ $$ = pow ($1, $3); @}
1284 | '(' exp ')' @{ $$ = $2; @}
1285 ;
1286 %%
1287 @end example
1288
1289 @noindent
1290 The functions @code{yylex}, @code{yyerror} and @code{main} can be the
1291 same as before.
1292
1293 There are two important new features shown in this code.
1294
1295 In the second section (Bison declarations), @code{%left} declares token
1296 types and says they are left-associative operators. The declarations
1297 @code{%left} and @code{%right} (right associativity) take the place of
1298 @code{%token} which is used to declare a token type name without
1299 associativity. (These tokens are single-character literals, which
1300 ordinarily don't need to be declared. We declare them here to specify
1301 the associativity.)
1302
1303 Operator precedence is determined by the line ordering of the
1304 declarations; the higher the line number of the declaration (lower on
1305 the page or screen), the higher the precedence. Hence, exponentiation
1306 has the highest precedence, unary minus (@code{NEG}) is next, followed
1307 by @samp{*} and @samp{/}, and so on. @xref{Precedence, ,Operator Precedence}.
1308
1309 The other important new feature is the @code{%prec} in the grammar section
1310 for the unary minus operator. The @code{%prec} simply instructs Bison that
1311 the rule @samp{| '-' exp} has the same precedence as @code{NEG}---in this
1312 case the next-to-highest. @xref{Contextual Precedence, ,Context-Dependent Precedence}.
1313
1314 Here is a sample run of @file{calc.y}:
1315
1316 @need 500
1317 @example
1318 % calc
1319 4 + 4.5 - (34/(8*3+-3))
1320 6.880952381
1321 -56 + 2
1322 -54
1323 3 ^ 2
1324 9
1325 @end example
1326
1327 @node Simple Error Recovery
1328 @section Simple Error Recovery
1329 @cindex error recovery, simple
1330
1331 Up to this point, this manual has not addressed the issue of @dfn{error
1332 recovery}---how to continue parsing after the parser detects a syntax
1333 error. All we have handled is error reporting with @code{yyerror}.
1334 Recall that by default @code{yyparse} returns after calling
1335 @code{yyerror}. This means that an erroneous input line causes the
1336 calculator program to exit. Now we show how to rectify this deficiency.
1337
1338 The Bison language itself includes the reserved word @code{error}, which
1339 may be included in the grammar rules. In the example below it has
1340 been added to one of the alternatives for @code{line}:
1341
1342 @example
1343 @group
1344 line: '\n'
1345 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1346 | error '\n' @{ yyerrok; @}
1347 ;
1348 @end group
1349 @end example
1350
1351 This addition to the grammar allows for simple error recovery in the
1352 event of a parse error. If an expression that cannot be evaluated is
1353 read, the error will be recognized by the third rule for @code{line},
1354 and parsing will continue. (The @code{yyerror} function is still called
1355 upon to print its message as well.) The action executes the statement
1356 @code{yyerrok}, a macro defined automatically by Bison; its meaning is
1357 that error recovery is complete (@pxref{Error Recovery}). Note the
1358 difference between @code{yyerrok} and @code{yyerror}; neither one is a
1359 misprint.@refill
1360
1361 This form of error recovery deals with syntax errors. There are other
1362 kinds of errors; for example, division by zero, which raises an exception
1363 signal that is normally fatal. A real calculator program must handle this
1364 signal and use @code{longjmp} to return to @code{main} and resume parsing
1365 input lines; it would also have to discard the rest of the current line of
1366 input. We won't discuss this issue further because it is not specific to
1367 Bison programs.
1368
1369 @node Location Tracking Calc
1370 @section Location Tracking Calculator: @code{ltcalc}
1371 @cindex location tracking calculator
1372 @cindex @code{ltcalc}
1373 @cindex calculator, location tracking
1374
1375 This example extends the infix notation calculator with location tracking.
1376 This feature will be used to improve error reporting, and provide better
1377 error messages.
1378
1379 For the sake of clarity, we will switch for this example to an integer
1380 calculator, since most of the work needed to use locations will be done
1381 in the lexical analyser.
1382
1383 @menu
1384 * Decls: Ltcalc Decls. Bison and C declarations for ltcalc.
1385 * Rules: Ltcalc Rules. Grammar rules for ltcalc, with explanations.
1386 * Lexer: Ltcalc Lexer. The lexical analyzer.
1387 @end menu
1388
1389 @node Ltcalc Decls
1390 @subsection Declarations for @code{ltcalc}
1391
1392 The C and Bison declarations for the location tracking calculator are the same
1393 as the declarations for the infix notation calculator.
1394
1395 @example
1396 /* Location tracking calculator. */
1397
1398 %@{
1399 #define YYSTYPE int
1400 #include <math.h>
1401 %@}
1402
1403 /* Bison declarations. */
1404 %token NUM
1405
1406 %left '-' '+'
1407 %left '*' '/'
1408 %left NEG
1409 %right '^'
1410
1411 %% /* Grammar follows */
1412 @end example
1413
1414 In the code above, there are no declarations specific to locations. Defining
1415 a data type for storing locations is not needed: we will use the type provided
1416 by default (@pxref{Location Type, ,Data Types of Locations}), which is a four
1417 member structure with the following integer fields: @code{first_line},
1418 @code{first_column}, @code{last_line} and @code{last_column}.
1419
1420 @node Ltcalc Rules
1421 @subsection Grammar Rules for @code{ltcalc}
1422
1423 Whether you choose to handle locations or not has no effect on the syntax of
1424 your language. Therefore, grammar rules for this example will be very close to
1425 those of the previous example: we will only modify them to benefit from the new
1426 informations we will have.
1427
1428 Here, we will use locations to report divisions by zero, and locate the wrong
1429 expressions or subexpressions.
1430
1431 @example
1432 @group
1433 input : /* empty */
1434 | input line
1435 ;
1436 @end group
1437
1438 @group
1439 line : '\n'
1440 | exp '\n' @{ printf ("%d\n", $1); @}
1441 ;
1442 @end group
1443
1444 @group
1445 exp : NUM @{ $$ = $1; @}
1446 | exp '+' exp @{ $$ = $1 + $3; @}
1447 | exp '-' exp @{ $$ = $1 - $3; @}
1448 | exp '*' exp @{ $$ = $1 * $3; @}
1449 @end group
1450 | exp '/' exp
1451 @group
1452 @{
1453 if ($3)
1454 $$ = $1 / $3;
1455 else
1456 @{
1457 $$ = 1;
1458 printf("Division by zero, l%d,c%d-l%d,c%d",
1459 @@3.first_line, @@3.first_column,
1460 @@3.last_line, @@3.last_column);
1461 @}
1462 @}
1463 @end group
1464 @group
1465 | '-' exp %preg NEG @{ $$ = -$2; @}
1466 | exp '^' exp @{ $$ = pow ($1, $3); @}
1467 | '(' exp ')' @{ $$ = $2; @}
1468 @end group
1469 @end example
1470
1471 This code shows how to reach locations inside of semantic actions, by
1472 using the pseudo-variables @code{@@@var{n}} for rule components, and the
1473 pseudo-variable @code{@@$} for groupings.
1474
1475 In this example, we never assign a value to @code{@@$}, because the
1476 output parser can do this automatically. By default, before executing
1477 the C code of each action, @code{@@$} is set to range from the beginning
1478 of @code{@@1} to the end of @code{@@@var{n}}, for a rule with @var{n}
1479 components.
1480
1481 Of course, this behavior can be redefined (@pxref{Location Default
1482 Action, , Default Action for Locations}), and for very specific rules,
1483 @code{@@$} can be computed by hand.
1484
1485 @node Ltcalc Lexer
1486 @subsection The @code{ltcalc} Lexical Analyzer.
1487
1488 Until now, we relied on Bison's defaults to enable location tracking. The next
1489 step is to rewrite the lexical analyser, and make it able to feed the parser
1490 with locations of tokens, as he already does for semantic values.
1491
1492 To do so, we must take into account every single character of the input text,
1493 to avoid the computed locations of being fuzzy or wrong:
1494
1495 @example
1496 @group
1497 int
1498 yylex (void)
1499 @{
1500 int c;
1501
1502 /* skip white space */
1503 while ((c = getchar ()) == ' ' || c == '\t')
1504 ++yylloc.last_column;
1505
1506 /* step */
1507 yylloc.first_line = yylloc.last_line;
1508 yylloc.first_column = yylloc.last_column;
1509 @end group
1510
1511 @group
1512 /* process numbers */
1513 if (isdigit (c))
1514 @{
1515 yylval = c - '0';
1516 ++yylloc.last_column;
1517 while (isdigit (c = getchar ()))
1518 @{
1519 ++yylloc.last_column;
1520 yylval = yylval * 10 + c - '0';
1521 @}
1522 ungetc (c, stdin);
1523 return NUM;
1524 @}
1525 @end group
1526
1527 /* return end-of-file */
1528 if (c == EOF)
1529 return 0;
1530
1531 /* return single chars and update location */
1532 if (c == '\n')
1533 @{
1534 ++yylloc.last_line;
1535 yylloc.last_column = 0;
1536 @}
1537 else
1538 ++yylloc.last_column;
1539 return c;
1540 @}
1541 @end example
1542
1543 Basically, the lexical analyzer does the same processing as before: it skips
1544 blanks and tabs, and reads numbers or single-character tokens. In addition
1545 to this, it updates the @code{yylloc} global variable (of type @code{YYLTYPE}),
1546 where the location of tokens is stored.
1547
1548 Now, each time this function returns a token, the parser has it's number as
1549 well as it's semantic value, and it's position in the text. The last needed
1550 change is to initialize @code{yylloc}, for example in the controlling
1551 function:
1552
1553 @example
1554 int
1555 main (void)
1556 @{
1557 yylloc.first_line = yylloc.last_line = 1;
1558 yylloc.first_column = yylloc.last_column = 0;
1559 return yyparse ();
1560 @}
1561 @end example
1562
1563 Remember that computing locations is not a matter of syntax. Every character
1564 must be associated to a location update, whether it is in valid input, in
1565 comments, in literal strings, and so on...
1566
1567 @node Multi-function Calc
1568 @section Multi-Function Calculator: @code{mfcalc}
1569 @cindex multi-function calculator
1570 @cindex @code{mfcalc}
1571 @cindex calculator, multi-function
1572
1573 Now that the basics of Bison have been discussed, it is time to move on to
1574 a more advanced problem. The above calculators provided only five
1575 functions, @samp{+}, @samp{-}, @samp{*}, @samp{/} and @samp{^}. It would
1576 be nice to have a calculator that provides other mathematical functions such
1577 as @code{sin}, @code{cos}, etc.
1578
1579 It is easy to add new operators to the infix calculator as long as they are
1580 only single-character literals. The lexical analyzer @code{yylex} passes
1581 back all nonnumber characters as tokens, so new grammar rules suffice for
1582 adding a new operator. But we want something more flexible: built-in
1583 functions whose syntax has this form:
1584
1585 @example
1586 @var{function_name} (@var{argument})
1587 @end example
1588
1589 @noindent
1590 At the same time, we will add memory to the calculator, by allowing you
1591 to create named variables, store values in them, and use them later.
1592 Here is a sample session with the multi-function calculator:
1593
1594 @example
1595 % mfcalc
1596 pi = 3.141592653589
1597 3.1415926536
1598 sin(pi)
1599 0.0000000000
1600 alpha = beta1 = 2.3
1601 2.3000000000
1602 alpha
1603 2.3000000000
1604 ln(alpha)
1605 0.8329091229
1606 exp(ln(beta1))
1607 2.3000000000
1608 %
1609 @end example
1610
1611 Note that multiple assignment and nested function calls are permitted.
1612
1613 @menu
1614 * Decl: Mfcalc Decl. Bison declarations for multi-function calculator.
1615 * Rules: Mfcalc Rules. Grammar rules for the calculator.
1616 * Symtab: Mfcalc Symtab. Symbol table management subroutines.
1617 @end menu
1618
1619 @node Mfcalc Decl
1620 @subsection Declarations for @code{mfcalc}
1621
1622 Here are the C and Bison declarations for the multi-function calculator.
1623
1624 @smallexample
1625 %@{
1626 #include <math.h> /* For math functions, cos(), sin(), etc. */
1627 #include "calc.h" /* Contains definition of `symrec' */
1628 %@}
1629 %union @{
1630 double val; /* For returning numbers. */
1631 symrec *tptr; /* For returning symbol-table pointers */
1632 @}
1633
1634 %token <val> NUM /* Simple double precision number */
1635 %token <tptr> VAR FNCT /* Variable and Function */
1636 %type <val> exp
1637
1638 %right '='
1639 %left '-' '+'
1640 %left '*' '/'
1641 %left NEG /* Negation--unary minus */
1642 %right '^' /* Exponentiation */
1643
1644 /* Grammar follows */
1645
1646 %%
1647 @end smallexample
1648
1649 The above grammar introduces only two new features of the Bison language.
1650 These features allow semantic values to have various data types
1651 (@pxref{Multiple Types, ,More Than One Value Type}).
1652
1653 The @code{%union} declaration specifies the entire list of possible types;
1654 this is instead of defining @code{YYSTYPE}. The allowable types are now
1655 double-floats (for @code{exp} and @code{NUM}) and pointers to entries in
1656 the symbol table. @xref{Union Decl, ,The Collection of Value Types}.
1657
1658 Since values can now have various types, it is necessary to associate a
1659 type with each grammar symbol whose semantic value is used. These symbols
1660 are @code{NUM}, @code{VAR}, @code{FNCT}, and @code{exp}. Their
1661 declarations are augmented with information about their data type (placed
1662 between angle brackets).
1663
1664 The Bison construct @code{%type} is used for declaring nonterminal symbols,
1665 just as @code{%token} is used for declaring token types. We have not used
1666 @code{%type} before because nonterminal symbols are normally declared
1667 implicitly by the rules that define them. But @code{exp} must be declared
1668 explicitly so we can specify its value type. @xref{Type Decl, ,Nonterminal Symbols}.
1669
1670 @node Mfcalc Rules
1671 @subsection Grammar Rules for @code{mfcalc}
1672
1673 Here are the grammar rules for the multi-function calculator.
1674 Most of them are copied directly from @code{calc}; three rules,
1675 those which mention @code{VAR} or @code{FNCT}, are new.
1676
1677 @smallexample
1678 input: /* empty */
1679 | input line
1680 ;
1681
1682 line:
1683 '\n'
1684 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1685 | error '\n' @{ yyerrok; @}
1686 ;
1687
1688 exp: NUM @{ $$ = $1; @}
1689 | VAR @{ $$ = $1->value.var; @}
1690 | VAR '=' exp @{ $$ = $3; $1->value.var = $3; @}
1691 | FNCT '(' exp ')' @{ $$ = (*($1->value.fnctptr))($3); @}
1692 | exp '+' exp @{ $$ = $1 + $3; @}
1693 | exp '-' exp @{ $$ = $1 - $3; @}
1694 | exp '*' exp @{ $$ = $1 * $3; @}
1695 | exp '/' exp @{ $$ = $1 / $3; @}
1696 | '-' exp %prec NEG @{ $$ = -$2; @}
1697 | exp '^' exp @{ $$ = pow ($1, $3); @}
1698 | '(' exp ')' @{ $$ = $2; @}
1699 ;
1700 /* End of grammar */
1701 %%
1702 @end smallexample
1703
1704 @node Mfcalc Symtab
1705 @subsection The @code{mfcalc} Symbol Table
1706 @cindex symbol table example
1707
1708 The multi-function calculator requires a symbol table to keep track of the
1709 names and meanings of variables and functions. This doesn't affect the
1710 grammar rules (except for the actions) or the Bison declarations, but it
1711 requires some additional C functions for support.
1712
1713 The symbol table itself consists of a linked list of records. Its
1714 definition, which is kept in the header @file{calc.h}, is as follows. It
1715 provides for either functions or variables to be placed in the table.
1716
1717 @smallexample
1718 @group
1719 /* Fonctions type. */
1720 typedef double (*func_t) (double);
1721
1722 /* Data type for links in the chain of symbols. */
1723 struct symrec
1724 @{
1725 char *name; /* name of symbol */
1726 int type; /* type of symbol: either VAR or FNCT */
1727 union
1728 @{
1729 double var; /* value of a VAR */
1730 func_t fnctptr; /* value of a FNCT */
1731 @} value;
1732 struct symrec *next; /* link field */
1733 @};
1734 @end group
1735
1736 @group
1737 typedef struct symrec symrec;
1738
1739 /* The symbol table: a chain of `struct symrec'. */
1740 extern symrec *sym_table;
1741
1742 symrec *putsym (const char *, func_t);
1743 symrec *getsym (const char *);
1744 @end group
1745 @end smallexample
1746
1747 The new version of @code{main} includes a call to @code{init_table}, a
1748 function that initializes the symbol table. Here it is, and
1749 @code{init_table} as well:
1750
1751 @smallexample
1752 @group
1753 #include <stdio.h>
1754
1755 int
1756 main (void)
1757 @{
1758 init_table ();
1759 return yyparse ();
1760 @}
1761 @end group
1762
1763 @group
1764 void
1765 yyerror (const char *s) /* Called by yyparse on error */
1766 @{
1767 printf ("%s\n", s);
1768 @}
1769
1770 struct init
1771 @{
1772 char *fname;
1773 double (*fnct)(double);
1774 @};
1775 @end group
1776
1777 @group
1778 struct init arith_fncts[] =
1779 @{
1780 "sin", sin,
1781 "cos", cos,
1782 "atan", atan,
1783 "ln", log,
1784 "exp", exp,
1785 "sqrt", sqrt,
1786 0, 0
1787 @};
1788
1789 /* The symbol table: a chain of `struct symrec'. */
1790 symrec *sym_table = (symrec *) 0;
1791 @end group
1792
1793 @group
1794 /* Put arithmetic functions in table. */
1795 void
1796 init_table (void)
1797 @{
1798 int i;
1799 symrec *ptr;
1800 for (i = 0; arith_fncts[i].fname != 0; i++)
1801 @{
1802 ptr = putsym (arith_fncts[i].fname, FNCT);
1803 ptr->value.fnctptr = arith_fncts[i].fnct;
1804 @}
1805 @}
1806 @end group
1807 @end smallexample
1808
1809 By simply editing the initialization list and adding the necessary include
1810 files, you can add additional functions to the calculator.
1811
1812 Two important functions allow look-up and installation of symbols in the
1813 symbol table. The function @code{putsym} is passed a name and the type
1814 (@code{VAR} or @code{FNCT}) of the object to be installed. The object is
1815 linked to the front of the list, and a pointer to the object is returned.
1816 The function @code{getsym} is passed the name of the symbol to look up. If
1817 found, a pointer to that symbol is returned; otherwise zero is returned.
1818
1819 @smallexample
1820 symrec *
1821 putsym (char *sym_name, int sym_type)
1822 @{
1823 symrec *ptr;
1824 ptr = (symrec *) malloc (sizeof (symrec));
1825 ptr->name = (char *) malloc (strlen (sym_name) + 1);
1826 strcpy (ptr->name,sym_name);
1827 ptr->type = sym_type;
1828 ptr->value.var = 0; /* set value to 0 even if fctn. */
1829 ptr->next = (struct symrec *)sym_table;
1830 sym_table = ptr;
1831 return ptr;
1832 @}
1833
1834 symrec *
1835 getsym (const char *sym_name)
1836 @{
1837 symrec *ptr;
1838 for (ptr = sym_table; ptr != (symrec *) 0;
1839 ptr = (symrec *)ptr->next)
1840 if (strcmp (ptr->name,sym_name) == 0)
1841 return ptr;
1842 return 0;
1843 @}
1844 @end smallexample
1845
1846 The function @code{yylex} must now recognize variables, numeric values, and
1847 the single-character arithmetic operators. Strings of alphanumeric
1848 characters with a leading non-digit are recognized as either variables or
1849 functions depending on what the symbol table says about them.
1850
1851 The string is passed to @code{getsym} for look up in the symbol table. If
1852 the name appears in the table, a pointer to its location and its type
1853 (@code{VAR} or @code{FNCT}) is returned to @code{yyparse}. If it is not
1854 already in the table, then it is installed as a @code{VAR} using
1855 @code{putsym}. Again, a pointer and its type (which must be @code{VAR}) is
1856 returned to @code{yyparse}.@refill
1857
1858 No change is needed in the handling of numeric values and arithmetic
1859 operators in @code{yylex}.
1860
1861 @smallexample
1862 @group
1863 #include <ctype.h>
1864
1865 int
1866 yylex (void)
1867 @{
1868 int c;
1869
1870 /* Ignore whitespace, get first nonwhite character. */
1871 while ((c = getchar ()) == ' ' || c == '\t');
1872
1873 if (c == EOF)
1874 return 0;
1875 @end group
1876
1877 @group
1878 /* Char starts a number => parse the number. */
1879 if (c == '.' || isdigit (c))
1880 @{
1881 ungetc (c, stdin);
1882 scanf ("%lf", &yylval.val);
1883 return NUM;
1884 @}
1885 @end group
1886
1887 @group
1888 /* Char starts an identifier => read the name. */
1889 if (isalpha (c))
1890 @{
1891 symrec *s;
1892 static char *symbuf = 0;
1893 static int length = 0;
1894 int i;
1895 @end group
1896
1897 @group
1898 /* Initially make the buffer long enough
1899 for a 40-character symbol name. */
1900 if (length == 0)
1901 length = 40, symbuf = (char *)malloc (length + 1);
1902
1903 i = 0;
1904 do
1905 @end group
1906 @group
1907 @{
1908 /* If buffer is full, make it bigger. */
1909 if (i == length)
1910 @{
1911 length *= 2;
1912 symbuf = (char *)realloc (symbuf, length + 1);
1913 @}
1914 /* Add this character to the buffer. */
1915 symbuf[i++] = c;
1916 /* Get another character. */
1917 c = getchar ();
1918 @}
1919 @end group
1920 @group
1921 while (c != EOF && isalnum (c));
1922
1923 ungetc (c, stdin);
1924 symbuf[i] = '\0';
1925 @end group
1926
1927 @group
1928 s = getsym (symbuf);
1929 if (s == 0)
1930 s = putsym (symbuf, VAR);
1931 yylval.tptr = s;
1932 return s->type;
1933 @}
1934
1935 /* Any other character is a token by itself. */
1936 return c;
1937 @}
1938 @end group
1939 @end smallexample
1940
1941 This program is both powerful and flexible. You may easily add new
1942 functions, and it is a simple job to modify this code to install predefined
1943 variables such as @code{pi} or @code{e} as well.
1944
1945 @node Exercises
1946 @section Exercises
1947 @cindex exercises
1948
1949 @enumerate
1950 @item
1951 Add some new functions from @file{math.h} to the initialization list.
1952
1953 @item
1954 Add another array that contains constants and their values. Then
1955 modify @code{init_table} to add these constants to the symbol table.
1956 It will be easiest to give the constants type @code{VAR}.
1957
1958 @item
1959 Make the program report an error if the user refers to an
1960 uninitialized variable in any way except to store a value in it.
1961 @end enumerate
1962
1963 @node Grammar File
1964 @chapter Bison Grammar Files
1965
1966 Bison takes as input a context-free grammar specification and produces a
1967 C-language function that recognizes correct instances of the grammar.
1968
1969 The Bison grammar input file conventionally has a name ending in @samp{.y}.
1970 @xref{Invocation, ,Invoking Bison}.
1971
1972 @menu
1973 * Grammar Outline:: Overall layout of the grammar file.
1974 * Symbols:: Terminal and nonterminal symbols.
1975 * Rules:: How to write grammar rules.
1976 * Recursion:: Writing recursive rules.
1977 * Semantics:: Semantic values and actions.
1978 * Locations:: Locations and actions.
1979 * Declarations:: All kinds of Bison declarations are described here.
1980 * Multiple Parsers:: Putting more than one Bison parser in one program.
1981 @end menu
1982
1983 @node Grammar Outline
1984 @section Outline of a Bison Grammar
1985
1986 A Bison grammar file has four main sections, shown here with the
1987 appropriate delimiters:
1988
1989 @example
1990 %@{
1991 @var{C declarations}
1992 %@}
1993
1994 @var{Bison declarations}
1995
1996 %%
1997 @var{Grammar rules}
1998 %%
1999
2000 @var{Additional C code}
2001 @end example
2002
2003 Comments enclosed in @samp{/* @dots{} */} may appear in any of the sections.
2004
2005 @menu
2006 * C Declarations:: Syntax and usage of the C declarations section.
2007 * Bison Declarations:: Syntax and usage of the Bison declarations section.
2008 * Grammar Rules:: Syntax and usage of the grammar rules section.
2009 * C Code:: Syntax and usage of the additional C code section.
2010 @end menu
2011
2012 @node C Declarations
2013 @subsection The C Declarations Section
2014 @cindex C declarations section
2015 @cindex declarations, C
2016
2017 The @var{C declarations} section contains macro definitions and
2018 declarations of functions and variables that are used in the actions in the
2019 grammar rules. These are copied to the beginning of the parser file so
2020 that they precede the definition of @code{yyparse}. You can use
2021 @samp{#include} to get the declarations from a header file. If you don't
2022 need any C declarations, you may omit the @samp{%@{} and @samp{%@}}
2023 delimiters that bracket this section.
2024
2025 @node Bison Declarations
2026 @subsection The Bison Declarations Section
2027 @cindex Bison declarations (introduction)
2028 @cindex declarations, Bison (introduction)
2029
2030 The @var{Bison declarations} section contains declarations that define
2031 terminal and nonterminal symbols, specify precedence, and so on.
2032 In some simple grammars you may not need any declarations.
2033 @xref{Declarations, ,Bison Declarations}.
2034
2035 @node Grammar Rules
2036 @subsection The Grammar Rules Section
2037 @cindex grammar rules section
2038 @cindex rules section for grammar
2039
2040 The @dfn{grammar rules} section contains one or more Bison grammar
2041 rules, and nothing else. @xref{Rules, ,Syntax of Grammar Rules}.
2042
2043 There must always be at least one grammar rule, and the first
2044 @samp{%%} (which precedes the grammar rules) may never be omitted even
2045 if it is the first thing in the file.
2046
2047 @node C Code
2048 @subsection The Additional C Code Section
2049 @cindex additional C code section
2050 @cindex C code, section for additional
2051
2052 The @var{additional C code} section is copied verbatim to the end of the
2053 parser file, just as the @var{C declarations} section is copied to the
2054 beginning. This is the most convenient place to put anything that you
2055 want to have in the parser file but which need not come before the
2056 definition of @code{yyparse}. For example, the definitions of
2057 @code{yylex} and @code{yyerror} often go here. @xref{Interface, ,Parser
2058 C-Language Interface}.
2059
2060 If the last section is empty, you may omit the @samp{%%} that separates it
2061 from the grammar rules.
2062
2063 The Bison parser itself contains many static variables whose names start
2064 with @samp{yy} and many macros whose names start with @samp{YY}. It is a
2065 good idea to avoid using any such names (except those documented in this
2066 manual) in the additional C code section of the grammar file.
2067
2068 @node Symbols
2069 @section Symbols, Terminal and Nonterminal
2070 @cindex nonterminal symbol
2071 @cindex terminal symbol
2072 @cindex token type
2073 @cindex symbol
2074
2075 @dfn{Symbols} in Bison grammars represent the grammatical classifications
2076 of the language.
2077
2078 A @dfn{terminal symbol} (also known as a @dfn{token type}) represents a
2079 class of syntactically equivalent tokens. You use the symbol in grammar
2080 rules to mean that a token in that class is allowed. The symbol is
2081 represented in the Bison parser by a numeric code, and the @code{yylex}
2082 function returns a token type code to indicate what kind of token has been
2083 read. You don't need to know what the code value is; you can use the
2084 symbol to stand for it.
2085
2086 A @dfn{nonterminal symbol} stands for a class of syntactically equivalent
2087 groupings. The symbol name is used in writing grammar rules. By convention,
2088 it should be all lower case.
2089
2090 Symbol names can contain letters, digits (not at the beginning),
2091 underscores and periods. Periods make sense only in nonterminals.
2092
2093 There are three ways of writing terminal symbols in the grammar:
2094
2095 @itemize @bullet
2096 @item
2097 A @dfn{named token type} is written with an identifier, like an
2098 identifier in C. By convention, it should be all upper case. Each
2099 such name must be defined with a Bison declaration such as
2100 @code{%token}. @xref{Token Decl, ,Token Type Names}.
2101
2102 @item
2103 @cindex character token
2104 @cindex literal token
2105 @cindex single-character literal
2106 A @dfn{character token type} (or @dfn{literal character token}) is
2107 written in the grammar using the same syntax used in C for character
2108 constants; for example, @code{'+'} is a character token type. A
2109 character token type doesn't need to be declared unless you need to
2110 specify its semantic value data type (@pxref{Value Type, ,Data Types of
2111 Semantic Values}), associativity, or precedence (@pxref{Precedence,
2112 ,Operator Precedence}).
2113
2114 By convention, a character token type is used only to represent a
2115 token that consists of that particular character. Thus, the token
2116 type @code{'+'} is used to represent the character @samp{+} as a
2117 token. Nothing enforces this convention, but if you depart from it,
2118 your program will confuse other readers.
2119
2120 All the usual escape sequences used in character literals in C can be
2121 used in Bison as well, but you must not use the null character as a
2122 character literal because its ASCII code, zero, is the code @code{yylex}
2123 returns for end-of-input (@pxref{Calling Convention, ,Calling Convention
2124 for @code{yylex}}).
2125
2126 @item
2127 @cindex string token
2128 @cindex literal string token
2129 @cindex multicharacter literal
2130 A @dfn{literal string token} is written like a C string constant; for
2131 example, @code{"<="} is a literal string token. A literal string token
2132 doesn't need to be declared unless you need to specify its semantic
2133 value data type (@pxref{Value Type}), associativity, or precedence
2134 (@pxref{Precedence}).
2135
2136 You can associate the literal string token with a symbolic name as an
2137 alias, using the @code{%token} declaration (@pxref{Token Decl, ,Token
2138 Declarations}). If you don't do that, the lexical analyzer has to
2139 retrieve the token number for the literal string token from the
2140 @code{yytname} table (@pxref{Calling Convention}).
2141
2142 @strong{WARNING}: literal string tokens do not work in Yacc.
2143
2144 By convention, a literal string token is used only to represent a token
2145 that consists of that particular string. Thus, you should use the token
2146 type @code{"<="} to represent the string @samp{<=} as a token. Bison
2147 does not enforce this convention, but if you depart from it, people who
2148 read your program will be confused.
2149
2150 All the escape sequences used in string literals in C can be used in
2151 Bison as well. A literal string token must contain two or more
2152 characters; for a token containing just one character, use a character
2153 token (see above).
2154 @end itemize
2155
2156 How you choose to write a terminal symbol has no effect on its
2157 grammatical meaning. That depends only on where it appears in rules and
2158 on when the parser function returns that symbol.
2159
2160 The value returned by @code{yylex} is always one of the terminal symbols
2161 (or 0 for end-of-input). Whichever way you write the token type in the
2162 grammar rules, you write it the same way in the definition of @code{yylex}.
2163 The numeric code for a character token type is simply the ASCII code for
2164 the character, so @code{yylex} can use the identical character constant to
2165 generate the requisite code. Each named token type becomes a C macro in
2166 the parser file, so @code{yylex} can use the name to stand for the code.
2167 (This is why periods don't make sense in terminal symbols.)
2168 @xref{Calling Convention, ,Calling Convention for @code{yylex}}.
2169
2170 If @code{yylex} is defined in a separate file, you need to arrange for the
2171 token-type macro definitions to be available there. Use the @samp{-d}
2172 option when you run Bison, so that it will write these macro definitions
2173 into a separate header file @file{@var{name}.tab.h} which you can include
2174 in the other source files that need it. @xref{Invocation, ,Invoking Bison}.
2175
2176 The symbol @code{error} is a terminal symbol reserved for error recovery
2177 (@pxref{Error Recovery}); you shouldn't use it for any other purpose.
2178 In particular, @code{yylex} should never return this value.
2179
2180 @node Rules
2181 @section Syntax of Grammar Rules
2182 @cindex rule syntax
2183 @cindex grammar rule syntax
2184 @cindex syntax of grammar rules
2185
2186 A Bison grammar rule has the following general form:
2187
2188 @example
2189 @group
2190 @var{result}: @var{components}@dots{}
2191 ;
2192 @end group
2193 @end example
2194
2195 @noindent
2196 where @var{result} is the nonterminal symbol that this rule describes,
2197 and @var{components} are various terminal and nonterminal symbols that
2198 are put together by this rule (@pxref{Symbols}).
2199
2200 For example,
2201
2202 @example
2203 @group
2204 exp: exp '+' exp
2205 ;
2206 @end group
2207 @end example
2208
2209 @noindent
2210 says that two groupings of type @code{exp}, with a @samp{+} token in between,
2211 can be combined into a larger grouping of type @code{exp}.
2212
2213 Whitespace in rules is significant only to separate symbols. You can add
2214 extra whitespace as you wish.
2215
2216 Scattered among the components can be @var{actions} that determine
2217 the semantics of the rule. An action looks like this:
2218
2219 @example
2220 @{@var{C statements}@}
2221 @end example
2222
2223 @noindent
2224 Usually there is only one action and it follows the components.
2225 @xref{Actions}.
2226
2227 @findex |
2228 Multiple rules for the same @var{result} can be written separately or can
2229 be joined with the vertical-bar character @samp{|} as follows:
2230
2231 @ifinfo
2232 @example
2233 @var{result}: @var{rule1-components}@dots{}
2234 | @var{rule2-components}@dots{}
2235 @dots{}
2236 ;
2237 @end example
2238 @end ifinfo
2239 @iftex
2240 @example
2241 @group
2242 @var{result}: @var{rule1-components}@dots{}
2243 | @var{rule2-components}@dots{}
2244 @dots{}
2245 ;
2246 @end group
2247 @end example
2248 @end iftex
2249
2250 @noindent
2251 They are still considered distinct rules even when joined in this way.
2252
2253 If @var{components} in a rule is empty, it means that @var{result} can
2254 match the empty string. For example, here is how to define a
2255 comma-separated sequence of zero or more @code{exp} groupings:
2256
2257 @example
2258 @group
2259 expseq: /* empty */
2260 | expseq1
2261 ;
2262 @end group
2263
2264 @group
2265 expseq1: exp
2266 | expseq1 ',' exp
2267 ;
2268 @end group
2269 @end example
2270
2271 @noindent
2272 It is customary to write a comment @samp{/* empty */} in each rule
2273 with no components.
2274
2275 @node Recursion
2276 @section Recursive Rules
2277 @cindex recursive rule
2278
2279 A rule is called @dfn{recursive} when its @var{result} nonterminal appears
2280 also on its right hand side. Nearly all Bison grammars need to use
2281 recursion, because that is the only way to define a sequence of any number
2282 of a particular thing. Consider this recursive definition of a
2283 comma-separated sequence of one or more expressions:
2284
2285 @example
2286 @group
2287 expseq1: exp
2288 | expseq1 ',' exp
2289 ;
2290 @end group
2291 @end example
2292
2293 @cindex left recursion
2294 @cindex right recursion
2295 @noindent
2296 Since the recursive use of @code{expseq1} is the leftmost symbol in the
2297 right hand side, we call this @dfn{left recursion}. By contrast, here
2298 the same construct is defined using @dfn{right recursion}:
2299
2300 @example
2301 @group
2302 expseq1: exp
2303 | exp ',' expseq1
2304 ;
2305 @end group
2306 @end example
2307
2308 @noindent
2309 Any kind of sequence can be defined using either left recursion or
2310 right recursion, but you should always use left recursion, because it
2311 can parse a sequence of any number of elements with bounded stack
2312 space. Right recursion uses up space on the Bison stack in proportion
2313 to the number of elements in the sequence, because all the elements
2314 must be shifted onto the stack before the rule can be applied even
2315 once. @xref{Algorithm, ,The Bison Parser Algorithm }, for
2316 further explanation of this.
2317
2318 @cindex mutual recursion
2319 @dfn{Indirect} or @dfn{mutual} recursion occurs when the result of the
2320 rule does not appear directly on its right hand side, but does appear
2321 in rules for other nonterminals which do appear on its right hand
2322 side.
2323
2324 For example:
2325
2326 @example
2327 @group
2328 expr: primary
2329 | primary '+' primary
2330 ;
2331 @end group
2332
2333 @group
2334 primary: constant
2335 | '(' expr ')'
2336 ;
2337 @end group
2338 @end example
2339
2340 @noindent
2341 defines two mutually-recursive nonterminals, since each refers to the
2342 other.
2343
2344 @node Semantics
2345 @section Defining Language Semantics
2346 @cindex defining language semantics
2347 @cindex language semantics, defining
2348
2349 The grammar rules for a language determine only the syntax. The semantics
2350 are determined by the semantic values associated with various tokens and
2351 groupings, and by the actions taken when various groupings are recognized.
2352
2353 For example, the calculator calculates properly because the value
2354 associated with each expression is the proper number; it adds properly
2355 because the action for the grouping @w{@samp{@var{x} + @var{y}}} is to add
2356 the numbers associated with @var{x} and @var{y}.
2357
2358 @menu
2359 * Value Type:: Specifying one data type for all semantic values.
2360 * Multiple Types:: Specifying several alternative data types.
2361 * Actions:: An action is the semantic definition of a grammar rule.
2362 * Action Types:: Specifying data types for actions to operate on.
2363 * Mid-Rule Actions:: Most actions go at the end of a rule.
2364 This says when, why and how to use the exceptional
2365 action in the middle of a rule.
2366 @end menu
2367
2368 @node Value Type
2369 @subsection Data Types of Semantic Values
2370 @cindex semantic value type
2371 @cindex value type, semantic
2372 @cindex data types of semantic values
2373 @cindex default data type
2374
2375 In a simple program it may be sufficient to use the same data type for
2376 the semantic values of all language constructs. This was true in the
2377 RPN and infix calculator examples (@pxref{RPN Calc, ,Reverse Polish Notation Calculator}).
2378
2379 Bison's default is to use type @code{int} for all semantic values. To
2380 specify some other type, define @code{YYSTYPE} as a macro, like this:
2381
2382 @example
2383 #define YYSTYPE double
2384 @end example
2385
2386 @noindent
2387 This macro definition must go in the C declarations section of the grammar
2388 file (@pxref{Grammar Outline, ,Outline of a Bison Grammar}).
2389
2390 @node Multiple Types
2391 @subsection More Than One Value Type
2392
2393 In most programs, you will need different data types for different kinds
2394 of tokens and groupings. For example, a numeric constant may need type
2395 @code{int} or @code{long}, while a string constant needs type @code{char *},
2396 and an identifier might need a pointer to an entry in the symbol table.
2397
2398 To use more than one data type for semantic values in one parser, Bison
2399 requires you to do two things:
2400
2401 @itemize @bullet
2402 @item
2403 Specify the entire collection of possible data types, with the
2404 @code{%union} Bison declaration (@pxref{Union Decl, ,The Collection of Value Types}).
2405
2406 @item
2407 Choose one of those types for each symbol (terminal or nonterminal) for
2408 which semantic values are used. This is done for tokens with the
2409 @code{%token} Bison declaration (@pxref{Token Decl, ,Token Type Names})
2410 and for groupings with the @code{%type} Bison declaration (@pxref{Type
2411 Decl, ,Nonterminal Symbols}).
2412 @end itemize
2413
2414 @node Actions
2415 @subsection Actions
2416 @cindex action
2417 @vindex $$
2418 @vindex $@var{n}
2419
2420 An action accompanies a syntactic rule and contains C code to be executed
2421 each time an instance of that rule is recognized. The task of most actions
2422 is to compute a semantic value for the grouping built by the rule from the
2423 semantic values associated with tokens or smaller groupings.
2424
2425 An action consists of C statements surrounded by braces, much like a
2426 compound statement in C. It can be placed at any position in the rule; it
2427 is executed at that position. Most rules have just one action at the end
2428 of the rule, following all the components. Actions in the middle of a rule
2429 are tricky and used only for special purposes (@pxref{Mid-Rule Actions, ,Actions in Mid-Rule}).
2430
2431 The C code in an action can refer to the semantic values of the components
2432 matched by the rule with the construct @code{$@var{n}}, which stands for
2433 the value of the @var{n}th component. The semantic value for the grouping
2434 being constructed is @code{$$}. (Bison translates both of these constructs
2435 into array element references when it copies the actions into the parser
2436 file.)
2437
2438 Here is a typical example:
2439
2440 @example
2441 @group
2442 exp: @dots{}
2443 | exp '+' exp
2444 @{ $$ = $1 + $3; @}
2445 @end group
2446 @end example
2447
2448 @noindent
2449 This rule constructs an @code{exp} from two smaller @code{exp} groupings
2450 connected by a plus-sign token. In the action, @code{$1} and @code{$3}
2451 refer to the semantic values of the two component @code{exp} groupings,
2452 which are the first and third symbols on the right hand side of the rule.
2453 The sum is stored into @code{$$} so that it becomes the semantic value of
2454 the addition-expression just recognized by the rule. If there were a
2455 useful semantic value associated with the @samp{+} token, it could be
2456 referred to as @code{$2}.@refill
2457
2458 @cindex default action
2459 If you don't specify an action for a rule, Bison supplies a default:
2460 @w{@code{$$ = $1}.} Thus, the value of the first symbol in the rule becomes
2461 the value of the whole rule. Of course, the default rule is valid only
2462 if the two data types match. There is no meaningful default action for
2463 an empty rule; every empty rule must have an explicit action unless the
2464 rule's value does not matter.
2465
2466 @code{$@var{n}} with @var{n} zero or negative is allowed for reference
2467 to tokens and groupings on the stack @emph{before} those that match the
2468 current rule. This is a very risky practice, and to use it reliably
2469 you must be certain of the context in which the rule is applied. Here
2470 is a case in which you can use this reliably:
2471
2472 @example
2473 @group
2474 foo: expr bar '+' expr @{ @dots{} @}
2475 | expr bar '-' expr @{ @dots{} @}
2476 ;
2477 @end group
2478
2479 @group
2480 bar: /* empty */
2481 @{ previous_expr = $0; @}
2482 ;
2483 @end group
2484 @end example
2485
2486 As long as @code{bar} is used only in the fashion shown here, @code{$0}
2487 always refers to the @code{expr} which precedes @code{bar} in the
2488 definition of @code{foo}.
2489
2490 @node Action Types
2491 @subsection Data Types of Values in Actions
2492 @cindex action data types
2493 @cindex data types in actions
2494
2495 If you have chosen a single data type for semantic values, the @code{$$}
2496 and @code{$@var{n}} constructs always have that data type.
2497
2498 If you have used @code{%union} to specify a variety of data types, then you
2499 must declare a choice among these types for each terminal or nonterminal
2500 symbol that can have a semantic value. Then each time you use @code{$$} or
2501 @code{$@var{n}}, its data type is determined by which symbol it refers to
2502 in the rule. In this example,@refill
2503
2504 @example
2505 @group
2506 exp: @dots{}
2507 | exp '+' exp
2508 @{ $$ = $1 + $3; @}
2509 @end group
2510 @end example
2511
2512 @noindent
2513 @code{$1} and @code{$3} refer to instances of @code{exp}, so they all
2514 have the data type declared for the nonterminal symbol @code{exp}. If
2515 @code{$2} were used, it would have the data type declared for the
2516 terminal symbol @code{'+'}, whatever that might be.@refill
2517
2518 Alternatively, you can specify the data type when you refer to the value,
2519 by inserting @samp{<@var{type}>} after the @samp{$} at the beginning of the
2520 reference. For example, if you have defined types as shown here:
2521
2522 @example
2523 @group
2524 %union @{
2525 int itype;
2526 double dtype;
2527 @}
2528 @end group
2529 @end example
2530
2531 @noindent
2532 then you can write @code{$<itype>1} to refer to the first subunit of the
2533 rule as an integer, or @code{$<dtype>1} to refer to it as a double.
2534
2535 @node Mid-Rule Actions
2536 @subsection Actions in Mid-Rule
2537 @cindex actions in mid-rule
2538 @cindex mid-rule actions
2539
2540 Occasionally it is useful to put an action in the middle of a rule.
2541 These actions are written just like usual end-of-rule actions, but they
2542 are executed before the parser even recognizes the following components.
2543
2544 A mid-rule action may refer to the components preceding it using
2545 @code{$@var{n}}, but it may not refer to subsequent components because
2546 it is run before they are parsed.
2547
2548 The mid-rule action itself counts as one of the components of the rule.
2549 This makes a difference when there is another action later in the same rule
2550 (and usually there is another at the end): you have to count the actions
2551 along with the symbols when working out which number @var{n} to use in
2552 @code{$@var{n}}.
2553
2554 The mid-rule action can also have a semantic value. The action can set
2555 its value with an assignment to @code{$$}, and actions later in the rule
2556 can refer to the value using @code{$@var{n}}. Since there is no symbol
2557 to name the action, there is no way to declare a data type for the value
2558 in advance, so you must use the @samp{$<@dots{}>@var{n}} construct to
2559 specify a data type each time you refer to this value.
2560
2561 There is no way to set the value of the entire rule with a mid-rule
2562 action, because assignments to @code{$$} do not have that effect. The
2563 only way to set the value for the entire rule is with an ordinary action
2564 at the end of the rule.
2565
2566 Here is an example from a hypothetical compiler, handling a @code{let}
2567 statement that looks like @samp{let (@var{variable}) @var{statement}} and
2568 serves to create a variable named @var{variable} temporarily for the
2569 duration of @var{statement}. To parse this construct, we must put
2570 @var{variable} into the symbol table while @var{statement} is parsed, then
2571 remove it afterward. Here is how it is done:
2572
2573 @example
2574 @group
2575 stmt: LET '(' var ')'
2576 @{ $<context>$ = push_context ();
2577 declare_variable ($3); @}
2578 stmt @{ $$ = $6;
2579 pop_context ($<context>5); @}
2580 @end group
2581 @end example
2582
2583 @noindent
2584 As soon as @samp{let (@var{variable})} has been recognized, the first
2585 action is run. It saves a copy of the current semantic context (the
2586 list of accessible variables) as its semantic value, using alternative
2587 @code{context} in the data-type union. Then it calls
2588 @code{declare_variable} to add the new variable to that list. Once the
2589 first action is finished, the embedded statement @code{stmt} can be
2590 parsed. Note that the mid-rule action is component number 5, so the
2591 @samp{stmt} is component number 6.
2592
2593 After the embedded statement is parsed, its semantic value becomes the
2594 value of the entire @code{let}-statement. Then the semantic value from the
2595 earlier action is used to restore the prior list of variables. This
2596 removes the temporary @code{let}-variable from the list so that it won't
2597 appear to exist while the rest of the program is parsed.
2598
2599 Taking action before a rule is completely recognized often leads to
2600 conflicts since the parser must commit to a parse in order to execute the
2601 action. For example, the following two rules, without mid-rule actions,
2602 can coexist in a working parser because the parser can shift the open-brace
2603 token and look at what follows before deciding whether there is a
2604 declaration or not:
2605
2606 @example
2607 @group
2608 compound: '@{' declarations statements '@}'
2609 | '@{' statements '@}'
2610 ;
2611 @end group
2612 @end example
2613
2614 @noindent
2615 But when we add a mid-rule action as follows, the rules become nonfunctional:
2616
2617 @example
2618 @group
2619 compound: @{ prepare_for_local_variables (); @}
2620 '@{' declarations statements '@}'
2621 @end group
2622 @group
2623 | '@{' statements '@}'
2624 ;
2625 @end group
2626 @end example
2627
2628 @noindent
2629 Now the parser is forced to decide whether to run the mid-rule action
2630 when it has read no farther than the open-brace. In other words, it
2631 must commit to using one rule or the other, without sufficient
2632 information to do it correctly. (The open-brace token is what is called
2633 the @dfn{look-ahead} token at this time, since the parser is still
2634 deciding what to do about it. @xref{Look-Ahead, ,Look-Ahead Tokens}.)
2635
2636 You might think that you could correct the problem by putting identical
2637 actions into the two rules, like this:
2638
2639 @example
2640 @group
2641 compound: @{ prepare_for_local_variables (); @}
2642 '@{' declarations statements '@}'
2643 | @{ prepare_for_local_variables (); @}
2644 '@{' statements '@}'
2645 ;
2646 @end group
2647 @end example
2648
2649 @noindent
2650 But this does not help, because Bison does not realize that the two actions
2651 are identical. (Bison never tries to understand the C code in an action.)
2652
2653 If the grammar is such that a declaration can be distinguished from a
2654 statement by the first token (which is true in C), then one solution which
2655 does work is to put the action after the open-brace, like this:
2656
2657 @example
2658 @group
2659 compound: '@{' @{ prepare_for_local_variables (); @}
2660 declarations statements '@}'
2661 | '@{' statements '@}'
2662 ;
2663 @end group
2664 @end example
2665
2666 @noindent
2667 Now the first token of the following declaration or statement,
2668 which would in any case tell Bison which rule to use, can still do so.
2669
2670 Another solution is to bury the action inside a nonterminal symbol which
2671 serves as a subroutine:
2672
2673 @example
2674 @group
2675 subroutine: /* empty */
2676 @{ prepare_for_local_variables (); @}
2677 ;
2678
2679 @end group
2680
2681 @group
2682 compound: subroutine
2683 '@{' declarations statements '@}'
2684 | subroutine
2685 '@{' statements '@}'
2686 ;
2687 @end group
2688 @end example
2689
2690 @noindent
2691 Now Bison can execute the action in the rule for @code{subroutine} without
2692 deciding which rule for @code{compound} it will eventually use. Note that
2693 the action is now at the end of its rule. Any mid-rule action can be
2694 converted to an end-of-rule action in this way, and this is what Bison
2695 actually does to implement mid-rule actions.
2696
2697 @node Locations
2698 @section Tracking Locations
2699 @cindex location
2700 @cindex textual position
2701 @cindex position, textual
2702
2703 Though grammar rules and semantic actions are enough to write a fully
2704 functional parser, it can be useful to process some additionnal informations,
2705 especially symbol locations.
2706
2707 @c (terminal or not) ?
2708
2709 The way locations are handled is defined by providing a data type, and actions
2710 to take when rules are matched.
2711
2712 @menu
2713 * Location Type:: Specifying a data type for locations.
2714 * Actions and Locations:: Using locations in actions.
2715 * Location Default Action:: Defining a general way to compute locations.
2716 @end menu
2717
2718 @node Location Type
2719 @subsection Data Type of Locations
2720 @cindex data type of locations
2721 @cindex default location type
2722
2723 Defining a data type for locations is much simpler than for semantic values,
2724 since all tokens and groupings always use the same type.
2725
2726 The type of locations is specified by defining a macro called @code{YYLTYPE}.
2727 When @code{YYLTYPE} is not defined, Bison uses a default structure type with
2728 four members:
2729
2730 @example
2731 struct
2732 @{
2733 int first_line;
2734 int first_column;
2735 int last_line;
2736 int last_column;
2737 @}
2738 @end example
2739
2740 @node Actions and Locations
2741 @subsection Actions and Locations
2742 @cindex location actions
2743 @cindex actions, location
2744 @vindex @@$
2745 @vindex @@@var{n}
2746
2747 Actions are not only useful for defining language semantics, but also for
2748 describing the behavior of the output parser with locations.
2749
2750 The most obvious way for building locations of syntactic groupings is very
2751 similar to the way semantic values are computed. In a given rule, several
2752 constructs can be used to access the locations of the elements being matched.
2753 The location of the @var{n}th component of the right hand side is
2754 @code{@@@var{n}}, while the location of the left hand side grouping is
2755 @code{@@$}.
2756
2757 Here is a basic example using the default data type for locations:
2758
2759 @example
2760 @group
2761 exp: @dots{}
2762 | exp '/' exp
2763 @{
2764 @@$.first_column = @@1.first_column;
2765 @@$.first_line = @@1.first_line;
2766 @@$.last_column = @@3.last_column;
2767 @@$.last_line = @@3.last_line;
2768 if ($3)
2769 $$ = $1 / $3;
2770 else
2771 @{
2772 $$ = 1;
2773 printf("Division by zero, l%d,c%d-l%d,c%d",
2774 @@3.first_line, @@3.first_column,
2775 @@3.last_line, @@3.last_column);
2776 @}
2777 @}
2778 @end group
2779 @end example
2780
2781 As for semantic values, there is a default action for locations that is
2782 run each time a rule is matched. It sets the beginning of @code{@@$} to the
2783 beginning of the first symbol, and the end of @code{@@$} to the end of the
2784 last symbol.
2785
2786 With this default action, the location tracking can be fully automatic. The
2787 example above simply rewrites this way:
2788
2789 @example
2790 @group
2791 exp: @dots{}
2792 | exp '/' exp
2793 @{
2794 if ($3)
2795 $$ = $1 / $3;
2796 else
2797 @{
2798 $$ = 1;
2799 printf("Division by zero, l%d,c%d-l%d,c%d",
2800 @@3.first_line, @@3.first_column,
2801 @@3.last_line, @@3.last_column);
2802 @}
2803 @}
2804 @end group
2805 @end example
2806
2807 @node Location Default Action
2808 @subsection Default Action for Locations
2809 @vindex YYLLOC_DEFAULT
2810
2811 Actually, actions are not the best place to compute locations. Since locations
2812 are much more general than semantic values, there is room in the output parser
2813 to redefine the default action to take for each rule. The
2814 @code{YYLLOC_DEFAULT} macro is called each time a rule is matched, before the
2815 associated action is run.
2816
2817 Most of the time, this macro is general enough to suppress location
2818 dedicated code from semantic actions.
2819
2820 The @code{YYLLOC_DEFAULT} macro takes three parameters. The first one is
2821 the location of the grouping (the result of the computation). The second one
2822 is an array holding locations of all right hand side elements of the rule
2823 being matched. The last one is the size of the right hand side rule.
2824
2825 By default, it is defined this way:
2826
2827 @example
2828 @group
2829 #define YYLLOC_DEFAULT(Current, Rhs, N) \
2830 Current.last_line = Rhs[N].last_line; \
2831 Current.last_column = Rhs[N].last_column;
2832 @end group
2833 @end example
2834
2835 When defining @code{YYLLOC_DEFAULT}, you should consider that:
2836
2837 @itemize @bullet
2838 @item
2839 All arguments are free of side-effects. However, only the first one (the
2840 result) should be modified by @code{YYLLOC_DEFAULT}.
2841
2842 @item
2843 Before @code{YYLLOC_DEFAULT} is executed, the output parser sets @code{@@$}
2844 to @code{@@1}.
2845
2846 @item
2847 For consistency with semantic actions, valid indexes for the location array
2848 range from 1 to @var{n}.
2849 @end itemize
2850
2851 @node Declarations
2852 @section Bison Declarations
2853 @cindex declarations, Bison
2854 @cindex Bison declarations
2855
2856 The @dfn{Bison declarations} section of a Bison grammar defines the symbols
2857 used in formulating the grammar and the data types of semantic values.
2858 @xref{Symbols}.
2859
2860 All token type names (but not single-character literal tokens such as
2861 @code{'+'} and @code{'*'}) must be declared. Nonterminal symbols must be
2862 declared if you need to specify which data type to use for the semantic
2863 value (@pxref{Multiple Types, ,More Than One Value Type}).
2864
2865 The first rule in the file also specifies the start symbol, by default.
2866 If you want some other symbol to be the start symbol, you must declare
2867 it explicitly (@pxref{Language and Grammar, ,Languages and Context-Free Grammars}).
2868
2869 @menu
2870 * Token Decl:: Declaring terminal symbols.
2871 * Precedence Decl:: Declaring terminals with precedence and associativity.
2872 * Union Decl:: Declaring the set of all semantic value types.
2873 * Type Decl:: Declaring the choice of type for a nonterminal symbol.
2874 * Expect Decl:: Suppressing warnings about shift/reduce conflicts.
2875 * Start Decl:: Specifying the start symbol.
2876 * Pure Decl:: Requesting a reentrant parser.
2877 * Decl Summary:: Table of all Bison declarations.
2878 @end menu
2879
2880 @node Token Decl
2881 @subsection Token Type Names
2882 @cindex declaring token type names
2883 @cindex token type names, declaring
2884 @cindex declaring literal string tokens
2885 @findex %token
2886
2887 The basic way to declare a token type name (terminal symbol) is as follows:
2888
2889 @example
2890 %token @var{name}
2891 @end example
2892
2893 Bison will convert this into a @code{#define} directive in
2894 the parser, so that the function @code{yylex} (if it is in this file)
2895 can use the name @var{name} to stand for this token type's code.
2896
2897 Alternatively, you can use @code{%left}, @code{%right}, or
2898 @code{%nonassoc} instead of @code{%token}, if you wish to specify
2899 associativity and precedence. @xref{Precedence Decl, ,Operator
2900 Precedence}.
2901
2902 You can explicitly specify the numeric code for a token type by appending
2903 an integer value in the field immediately following the token name:
2904
2905 @example
2906 %token NUM 300
2907 @end example
2908
2909 @noindent
2910 It is generally best, however, to let Bison choose the numeric codes for
2911 all token types. Bison will automatically select codes that don't conflict
2912 with each other or with ASCII characters.
2913
2914 In the event that the stack type is a union, you must augment the
2915 @code{%token} or other token declaration to include the data type
2916 alternative delimited by angle-brackets (@pxref{Multiple Types, ,More Than One Value Type}).
2917
2918 For example:
2919
2920 @example
2921 @group
2922 %union @{ /* define stack type */
2923 double val;
2924 symrec *tptr;
2925 @}
2926 %token <val> NUM /* define token NUM and its type */
2927 @end group
2928 @end example
2929
2930 You can associate a literal string token with a token type name by
2931 writing the literal string at the end of a @code{%token}
2932 declaration which declares the name. For example:
2933
2934 @example
2935 %token arrow "=>"
2936 @end example
2937
2938 @noindent
2939 For example, a grammar for the C language might specify these names with
2940 equivalent literal string tokens:
2941
2942 @example
2943 %token <operator> OR "||"
2944 %token <operator> LE 134 "<="
2945 %left OR "<="
2946 @end example
2947
2948 @noindent
2949 Once you equate the literal string and the token name, you can use them
2950 interchangeably in further declarations or the grammar rules. The
2951 @code{yylex} function can use the token name or the literal string to
2952 obtain the token type code number (@pxref{Calling Convention}).
2953
2954 @node Precedence Decl
2955 @subsection Operator Precedence
2956 @cindex precedence declarations
2957 @cindex declaring operator precedence
2958 @cindex operator precedence, declaring
2959
2960 Use the @code{%left}, @code{%right} or @code{%nonassoc} declaration to
2961 declare a token and specify its precedence and associativity, all at
2962 once. These are called @dfn{precedence declarations}.
2963 @xref{Precedence, ,Operator Precedence}, for general information on operator precedence.
2964
2965 The syntax of a precedence declaration is the same as that of
2966 @code{%token}: either
2967
2968 @example
2969 %left @var{symbols}@dots{}
2970 @end example
2971
2972 @noindent
2973 or
2974
2975 @example
2976 %left <@var{type}> @var{symbols}@dots{}
2977 @end example
2978
2979 And indeed any of these declarations serves the purposes of @code{%token}.
2980 But in addition, they specify the associativity and relative precedence for
2981 all the @var{symbols}:
2982
2983 @itemize @bullet
2984 @item
2985 The associativity of an operator @var{op} determines how repeated uses
2986 of the operator nest: whether @samp{@var{x} @var{op} @var{y} @var{op}
2987 @var{z}} is parsed by grouping @var{x} with @var{y} first or by
2988 grouping @var{y} with @var{z} first. @code{%left} specifies
2989 left-associativity (grouping @var{x} with @var{y} first) and
2990 @code{%right} specifies right-associativity (grouping @var{y} with
2991 @var{z} first). @code{%nonassoc} specifies no associativity, which
2992 means that @samp{@var{x} @var{op} @var{y} @var{op} @var{z}} is
2993 considered a syntax error.
2994
2995 @item
2996 The precedence of an operator determines how it nests with other operators.
2997 All the tokens declared in a single precedence declaration have equal
2998 precedence and nest together according to their associativity.
2999 When two tokens declared in different precedence declarations associate,
3000 the one declared later has the higher precedence and is grouped first.
3001 @end itemize
3002
3003 @node Union Decl
3004 @subsection The Collection of Value Types
3005 @cindex declaring value types
3006 @cindex value types, declaring
3007 @findex %union
3008
3009 The @code{%union} declaration specifies the entire collection of possible
3010 data types for semantic values. The keyword @code{%union} is followed by a
3011 pair of braces containing the same thing that goes inside a @code{union} in
3012 C.
3013
3014 For example:
3015
3016 @example
3017 @group
3018 %union @{
3019 double val;
3020 symrec *tptr;
3021 @}
3022 @end group
3023 @end example
3024
3025 @noindent
3026 This says that the two alternative types are @code{double} and @code{symrec
3027 *}. They are given names @code{val} and @code{tptr}; these names are used
3028 in the @code{%token} and @code{%type} declarations to pick one of the types
3029 for a terminal or nonterminal symbol (@pxref{Type Decl, ,Nonterminal Symbols}).
3030
3031 Note that, unlike making a @code{union} declaration in C, you do not write
3032 a semicolon after the closing brace.
3033
3034 @node Type Decl
3035 @subsection Nonterminal Symbols
3036 @cindex declaring value types, nonterminals
3037 @cindex value types, nonterminals, declaring
3038 @findex %type
3039
3040 @noindent
3041 When you use @code{%union} to specify multiple value types, you must
3042 declare the value type of each nonterminal symbol for which values are
3043 used. This is done with a @code{%type} declaration, like this:
3044
3045 @example
3046 %type <@var{type}> @var{nonterminal}@dots{}
3047 @end example
3048
3049 @noindent
3050 Here @var{nonterminal} is the name of a nonterminal symbol, and @var{type}
3051 is the name given in the @code{%union} to the alternative that you want
3052 (@pxref{Union Decl, ,The Collection of Value Types}). You can give any number of nonterminal symbols in
3053 the same @code{%type} declaration, if they have the same value type. Use
3054 spaces to separate the symbol names.
3055
3056 You can also declare the value type of a terminal symbol. To do this,
3057 use the same @code{<@var{type}>} construction in a declaration for the
3058 terminal symbol. All kinds of token declarations allow
3059 @code{<@var{type}>}.
3060
3061 @node Expect Decl
3062 @subsection Suppressing Conflict Warnings
3063 @cindex suppressing conflict warnings
3064 @cindex preventing warnings about conflicts
3065 @cindex warnings, preventing
3066 @cindex conflicts, suppressing warnings of
3067 @findex %expect
3068
3069 Bison normally warns if there are any conflicts in the grammar
3070 (@pxref{Shift/Reduce, ,Shift/Reduce Conflicts}), but most real grammars have harmless shift/reduce
3071 conflicts which are resolved in a predictable way and would be difficult to
3072 eliminate. It is desirable to suppress the warning about these conflicts
3073 unless the number of conflicts changes. You can do this with the
3074 @code{%expect} declaration.
3075
3076 The declaration looks like this:
3077
3078 @example
3079 %expect @var{n}
3080 @end example
3081
3082 Here @var{n} is a decimal integer. The declaration says there should be no
3083 warning if there are @var{n} shift/reduce conflicts and no reduce/reduce
3084 conflicts. The usual warning is given if there are either more or fewer
3085 conflicts, or if there are any reduce/reduce conflicts.
3086
3087 In general, using @code{%expect} involves these steps:
3088
3089 @itemize @bullet
3090 @item
3091 Compile your grammar without @code{%expect}. Use the @samp{-v} option
3092 to get a verbose list of where the conflicts occur. Bison will also
3093 print the number of conflicts.
3094
3095 @item
3096 Check each of the conflicts to make sure that Bison's default
3097 resolution is what you really want. If not, rewrite the grammar and
3098 go back to the beginning.
3099
3100 @item
3101 Add an @code{%expect} declaration, copying the number @var{n} from the
3102 number which Bison printed.
3103 @end itemize
3104
3105 Now Bison will stop annoying you about the conflicts you have checked, but
3106 it will warn you again if changes in the grammar result in additional
3107 conflicts.
3108
3109 @node Start Decl
3110 @subsection The Start-Symbol
3111 @cindex declaring the start symbol
3112 @cindex start symbol, declaring
3113 @cindex default start symbol
3114 @findex %start
3115
3116 Bison assumes by default that the start symbol for the grammar is the first
3117 nonterminal specified in the grammar specification section. The programmer
3118 may override this restriction with the @code{%start} declaration as follows:
3119
3120 @example
3121 %start @var{symbol}
3122 @end example
3123
3124 @node Pure Decl
3125 @subsection A Pure (Reentrant) Parser
3126 @cindex reentrant parser
3127 @cindex pure parser
3128 @findex %pure_parser
3129
3130 A @dfn{reentrant} program is one which does not alter in the course of
3131 execution; in other words, it consists entirely of @dfn{pure} (read-only)
3132 code. Reentrancy is important whenever asynchronous execution is possible;
3133 for example, a non-reentrant program may not be safe to call from a signal
3134 handler. In systems with multiple threads of control, a non-reentrant
3135 program must be called only within interlocks.
3136
3137 Normally, Bison generates a parser which is not reentrant. This is
3138 suitable for most uses, and it permits compatibility with YACC. (The
3139 standard YACC interfaces are inherently nonreentrant, because they use
3140 statically allocated variables for communication with @code{yylex},
3141 including @code{yylval} and @code{yylloc}.)
3142
3143 Alternatively, you can generate a pure, reentrant parser. The Bison
3144 declaration @code{%pure_parser} says that you want the parser to be
3145 reentrant. It looks like this:
3146
3147 @example
3148 %pure_parser
3149 @end example
3150
3151 The result is that the communication variables @code{yylval} and
3152 @code{yylloc} become local variables in @code{yyparse}, and a different
3153 calling convention is used for the lexical analyzer function
3154 @code{yylex}. @xref{Pure Calling, ,Calling Conventions for Pure
3155 Parsers}, for the details of this. The variable @code{yynerrs} also
3156 becomes local in @code{yyparse} (@pxref{Error Reporting, ,The Error
3157 Reporting Function @code{yyerror}}). The convention for calling
3158 @code{yyparse} itself is unchanged.
3159
3160 Whether the parser is pure has nothing to do with the grammar rules.
3161 You can generate either a pure parser or a nonreentrant parser from any
3162 valid grammar.
3163
3164 @node Decl Summary
3165 @subsection Bison Declaration Summary
3166 @cindex Bison declaration summary
3167 @cindex declaration summary
3168 @cindex summary, Bison declaration
3169
3170 Here is a summary of all Bison declarations:
3171
3172 @table @code
3173 @item %union
3174 Declare the collection of data types that semantic values may have
3175 (@pxref{Union Decl, ,The Collection of Value Types}).
3176
3177 @item %token
3178 Declare a terminal symbol (token type name) with no precedence
3179 or associativity specified (@pxref{Token Decl, ,Token Type Names}).
3180
3181 @item %right
3182 Declare a terminal symbol (token type name) that is right-associative
3183 (@pxref{Precedence Decl, ,Operator Precedence}).
3184
3185 @item %left
3186 Declare a terminal symbol (token type name) that is left-associative
3187 (@pxref{Precedence Decl, ,Operator Precedence}).
3188
3189 @item %nonassoc
3190 Declare a terminal symbol (token type name) that is nonassociative
3191 (using it in a way that would be associative is a syntax error)
3192 (@pxref{Precedence Decl, ,Operator Precedence}).
3193
3194 @item %type
3195 Declare the type of semantic values for a nonterminal symbol
3196 (@pxref{Type Decl, ,Nonterminal Symbols}).
3197
3198 @item %start
3199 Specify the grammar's start symbol (@pxref{Start Decl, ,The
3200 Start-Symbol}).
3201
3202 @item %expect
3203 Declare the expected number of shift-reduce conflicts
3204 (@pxref{Expect Decl, ,Suppressing Conflict Warnings}).
3205
3206 @item %yacc
3207 @itemx %fixed_output_files
3208 Pretend the option @option{--yacc} was given, i.e., imitate Yacc,
3209 including its naming conventions. @xref{Bison Options}, for more.
3210
3211 @item %locations
3212 Generate the code processing the locations (@pxref{Action Features,
3213 ,Special Features for Use in Actions}). This mode is enabled as soon as
3214 the grammar uses the special @samp{@@@var{n}} tokens, but if your
3215 grammar does not use it, using @samp{%locations} allows for more
3216 accurate parse error messages.
3217
3218 @item %pure_parser
3219 Request a pure (reentrant) parser program (@pxref{Pure Decl, ,A Pure
3220 (Reentrant) Parser}).
3221
3222 @item %no_parser
3223 Do not include any C code in the parser file; generate tables only. The
3224 parser file contains just @code{#define} directives and static variable
3225 declarations.
3226
3227 This option also tells Bison to write the C code for the grammar actions
3228 into a file named @file{@var{filename}.act}, in the form of a
3229 brace-surrounded body fit for a @code{switch} statement.
3230
3231 @item %no_lines
3232 Don't generate any @code{#line} preprocessor commands in the parser
3233 file. Ordinarily Bison writes these commands in the parser file so that
3234 the C compiler and debuggers will associate errors and object code with
3235 your source file (the grammar file). This directive causes them to
3236 associate errors with the parser file, treating it an independent source
3237 file in its own right.
3238
3239 @item %debug
3240 Output a definition of the macro @code{YYDEBUG} into the parser file, so
3241 that the debugging facilities are compiled. @xref{Debugging, ,Debugging
3242 Your Parser}.
3243
3244 @item %defines
3245 Write an extra output file containing macro definitions for the token
3246 type names defined in the grammar and the semantic value type
3247 @code{YYSTYPE}, as well as a few @code{extern} variable declarations.
3248
3249 If the parser output file is named @file{@var{name}.c} then this file
3250 is named @file{@var{name}.h}.@refill
3251
3252 This output file is essential if you wish to put the definition of
3253 @code{yylex} in a separate source file, because @code{yylex} needs to
3254 be able to refer to token type codes and the variable
3255 @code{yylval}. @xref{Token Values, ,Semantic Values of Tokens}.@refill
3256
3257 @c @item %source_extension
3258 @c Specify the extension of the parser output file.
3259 @c
3260 @c For example, a grammar file named @file{foo.yy} and containing a
3261 @c @code{%source_extension .cpp} directive will produce a parser file
3262 @c named @file{foo.tab.cpp}
3263 @c
3264 @c @item %header_extension
3265 @c Specify the extension of the parser header file generated when
3266 @c @code{%define} or @samp{-d} are used.
3267 @c
3268 @c For example, a garmmar file named @file{foo.ypp} and containing a
3269 @c @code{%header_extension .hh} directive will produce a header file
3270 @c named @file{foo.tab.hh}
3271
3272 @item %verbose
3273 Write an extra output file containing verbose descriptions of the
3274 parser states and what is done for each type of look-ahead token in
3275 that state.
3276
3277 This file also describes all the conflicts, both those resolved by
3278 operator precedence and the unresolved ones.
3279
3280 The file's name is made by removing @samp{.tab.c} or @samp{.c} from
3281 the parser output file name, and adding @samp{.output} instead.@refill
3282
3283 Therefore, if the input file is @file{foo.y}, then the parser file is
3284 called @file{foo.tab.c} by default. As a consequence, the verbose
3285 output file is called @file{foo.output}.@refill
3286
3287 @item %token_table
3288 Generate an array of token names in the parser file. The name of the
3289 array is @code{yytname}; @code{yytname[@var{i}]} is the name of the
3290 token whose internal Bison token code number is @var{i}. The first three
3291 elements of @code{yytname} are always @code{"$"}, @code{"error"}, and
3292 @code{"$illegal"}; after these come the symbols defined in the grammar
3293 file.
3294
3295 For single-character literal tokens and literal string tokens, the name
3296 in the table includes the single-quote or double-quote characters: for
3297 example, @code{"'+'"} is a single-character literal and @code{"\"<=\""}
3298 is a literal string token. All the characters of the literal string
3299 token appear verbatim in the string found in the table; even
3300 double-quote characters are not escaped. For example, if the token
3301 consists of three characters @samp{*"*}, its string in @code{yytname}
3302 contains @samp{"*"*"}. (In C, that would be written as
3303 @code{"\"*\"*\""}).
3304
3305 When you specify @code{%token_table}, Bison also generates macro
3306 definitions for macros @code{YYNTOKENS}, @code{YYNNTS}, and
3307 @code{YYNRULES}, and @code{YYNSTATES}:
3308
3309 @table @code
3310 @item YYNTOKENS
3311 The highest token number, plus one.
3312 @item YYNNTS
3313 The number of nonterminal symbols.
3314 @item YYNRULES
3315 The number of grammar rules,
3316 @item YYNSTATES
3317 The number of parser states (@pxref{Parser States}).
3318 @end table
3319 @end table
3320
3321 @node Multiple Parsers
3322 @section Multiple Parsers in the Same Program
3323
3324 Most programs that use Bison parse only one language and therefore contain
3325 only one Bison parser. But what if you want to parse more than one
3326 language with the same program? Then you need to avoid a name conflict
3327 between different definitions of @code{yyparse}, @code{yylval}, and so on.
3328
3329 The easy way to do this is to use the option @samp{-p @var{prefix}}
3330 (@pxref{Invocation, ,Invoking Bison}). This renames the interface functions and
3331 variables of the Bison parser to start with @var{prefix} instead of
3332 @samp{yy}. You can use this to give each parser distinct names that do
3333 not conflict.
3334
3335 The precise list of symbols renamed is @code{yyparse}, @code{yylex},
3336 @code{yyerror}, @code{yynerrs}, @code{yylval}, @code{yychar} and
3337 @code{yydebug}. For example, if you use @samp{-p c}, the names become
3338 @code{cparse}, @code{clex}, and so on.
3339
3340 @strong{All the other variables and macros associated with Bison are not
3341 renamed.} These others are not global; there is no conflict if the same
3342 name is used in different parsers. For example, @code{YYSTYPE} is not
3343 renamed, but defining this in different ways in different parsers causes
3344 no trouble (@pxref{Value Type, ,Data Types of Semantic Values}).
3345
3346 The @samp{-p} option works by adding macro definitions to the beginning
3347 of the parser source file, defining @code{yyparse} as
3348 @code{@var{prefix}parse}, and so on. This effectively substitutes one
3349 name for the other in the entire parser file.
3350
3351 @node Interface
3352 @chapter Parser C-Language Interface
3353 @cindex C-language interface
3354 @cindex interface
3355
3356 The Bison parser is actually a C function named @code{yyparse}. Here we
3357 describe the interface conventions of @code{yyparse} and the other
3358 functions that it needs to use.
3359
3360 Keep in mind that the parser uses many C identifiers starting with
3361 @samp{yy} and @samp{YY} for internal purposes. If you use such an
3362 identifier (aside from those in this manual) in an action or in additional
3363 C code in the grammar file, you are likely to run into trouble.
3364
3365 @menu
3366 * Parser Function:: How to call @code{yyparse} and what it returns.
3367 * Lexical:: You must supply a function @code{yylex}
3368 which reads tokens.
3369 * Error Reporting:: You must supply a function @code{yyerror}.
3370 * Action Features:: Special features for use in actions.
3371 @end menu
3372
3373 @node Parser Function
3374 @section The Parser Function @code{yyparse}
3375 @findex yyparse
3376
3377 You call the function @code{yyparse} to cause parsing to occur. This
3378 function reads tokens, executes actions, and ultimately returns when it
3379 encounters end-of-input or an unrecoverable syntax error. You can also
3380 write an action which directs @code{yyparse} to return immediately
3381 without reading further.
3382
3383 The value returned by @code{yyparse} is 0 if parsing was successful (return
3384 is due to end-of-input).
3385
3386 The value is 1 if parsing failed (return is due to a syntax error).
3387
3388 In an action, you can cause immediate return from @code{yyparse} by using
3389 these macros:
3390
3391 @table @code
3392 @item YYACCEPT
3393 @findex YYACCEPT
3394 Return immediately with value 0 (to report success).
3395
3396 @item YYABORT
3397 @findex YYABORT
3398 Return immediately with value 1 (to report failure).
3399 @end table
3400
3401 @node Lexical
3402 @section The Lexical Analyzer Function @code{yylex}
3403 @findex yylex
3404 @cindex lexical analyzer
3405
3406 The @dfn{lexical analyzer} function, @code{yylex}, recognizes tokens from
3407 the input stream and returns them to the parser. Bison does not create
3408 this function automatically; you must write it so that @code{yyparse} can
3409 call it. The function is sometimes referred to as a lexical scanner.
3410
3411 In simple programs, @code{yylex} is often defined at the end of the Bison
3412 grammar file. If @code{yylex} is defined in a separate source file, you
3413 need to arrange for the token-type macro definitions to be available there.
3414 To do this, use the @samp{-d} option when you run Bison, so that it will
3415 write these macro definitions into a separate header file
3416 @file{@var{name}.tab.h} which you can include in the other source files
3417 that need it. @xref{Invocation, ,Invoking Bison}.@refill
3418
3419 @menu
3420 * Calling Convention:: How @code{yyparse} calls @code{yylex}.
3421 * Token Values:: How @code{yylex} must return the semantic value
3422 of the token it has read.
3423 * Token Positions:: How @code{yylex} must return the text position
3424 (line number, etc.) of the token, if the
3425 actions want that.
3426 * Pure Calling:: How the calling convention differs
3427 in a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}).
3428 @end menu
3429
3430 @node Calling Convention
3431 @subsection Calling Convention for @code{yylex}
3432
3433 The value that @code{yylex} returns must be the numeric code for the type
3434 of token it has just found, or 0 for end-of-input.
3435
3436 When a token is referred to in the grammar rules by a name, that name
3437 in the parser file becomes a C macro whose definition is the proper
3438 numeric code for that token type. So @code{yylex} can use the name
3439 to indicate that type. @xref{Symbols}.
3440
3441 When a token is referred to in the grammar rules by a character literal,
3442 the numeric code for that character is also the code for the token type.
3443 So @code{yylex} can simply return that character code. The null character
3444 must not be used this way, because its code is zero and that is what
3445 signifies end-of-input.
3446
3447 Here is an example showing these things:
3448
3449 @example
3450 int
3451 yylex (void)
3452 @{
3453 @dots{}
3454 if (c == EOF) /* Detect end of file. */
3455 return 0;
3456 @dots{}
3457 if (c == '+' || c == '-')
3458 return c; /* Assume token type for `+' is '+'. */
3459 @dots{}
3460 return INT; /* Return the type of the token. */
3461 @dots{}
3462 @}
3463 @end example
3464
3465 @noindent
3466 This interface has been designed so that the output from the @code{lex}
3467 utility can be used without change as the definition of @code{yylex}.
3468
3469 If the grammar uses literal string tokens, there are two ways that
3470 @code{yylex} can determine the token type codes for them:
3471
3472 @itemize @bullet
3473 @item
3474 If the grammar defines symbolic token names as aliases for the
3475 literal string tokens, @code{yylex} can use these symbolic names like
3476 all others. In this case, the use of the literal string tokens in
3477 the grammar file has no effect on @code{yylex}.
3478
3479 @item
3480 @code{yylex} can find the multicharacter token in the @code{yytname}
3481 table. The index of the token in the table is the token type's code.
3482 The name of a multicharacter token is recorded in @code{yytname} with a
3483 double-quote, the token's characters, and another double-quote. The
3484 token's characters are not escaped in any way; they appear verbatim in
3485 the contents of the string in the table.
3486
3487 Here's code for looking up a token in @code{yytname}, assuming that the
3488 characters of the token are stored in @code{token_buffer}.
3489
3490 @smallexample
3491 for (i = 0; i < YYNTOKENS; i++)
3492 @{
3493 if (yytname[i] != 0
3494 && yytname[i][0] == '"'
3495 && strncmp (yytname[i] + 1, token_buffer,
3496 strlen (token_buffer))
3497 && yytname[i][strlen (token_buffer) + 1] == '"'
3498 && yytname[i][strlen (token_buffer) + 2] == 0)
3499 break;
3500 @}
3501 @end smallexample
3502
3503 The @code{yytname} table is generated only if you use the
3504 @code{%token_table} declaration. @xref{Decl Summary}.
3505 @end itemize
3506
3507 @node Token Values
3508 @subsection Semantic Values of Tokens
3509
3510 @vindex yylval
3511 In an ordinary (non-reentrant) parser, the semantic value of the token must
3512 be stored into the global variable @code{yylval}. When you are using
3513 just one data type for semantic values, @code{yylval} has that type.
3514 Thus, if the type is @code{int} (the default), you might write this in
3515 @code{yylex}:
3516
3517 @example
3518 @group
3519 @dots{}
3520 yylval = value; /* Put value onto Bison stack. */
3521 return INT; /* Return the type of the token. */
3522 @dots{}
3523 @end group
3524 @end example
3525
3526 When you are using multiple data types, @code{yylval}'s type is a union
3527 made from the @code{%union} declaration (@pxref{Union Decl, ,The Collection of Value Types}). So when
3528 you store a token's value, you must use the proper member of the union.
3529 If the @code{%union} declaration looks like this:
3530
3531 @example
3532 @group
3533 %union @{
3534 int intval;
3535 double val;
3536 symrec *tptr;
3537 @}
3538 @end group
3539 @end example
3540
3541 @noindent
3542 then the code in @code{yylex} might look like this:
3543
3544 @example
3545 @group
3546 @dots{}
3547 yylval.intval = value; /* Put value onto Bison stack. */
3548 return INT; /* Return the type of the token. */
3549 @dots{}
3550 @end group
3551 @end example
3552
3553 @node Token Positions
3554 @subsection Textual Positions of Tokens
3555
3556 @vindex yylloc
3557 If you are using the @samp{@@@var{n}}-feature (@pxref{Locations, ,
3558 Tracking Locations}) in actions to keep track of the
3559 textual locations of tokens and groupings, then you must provide this
3560 information in @code{yylex}. The function @code{yyparse} expects to
3561 find the textual location of a token just parsed in the global variable
3562 @code{yylloc}. So @code{yylex} must store the proper data in that
3563 variable.
3564
3565 By default, the value of @code{yylloc} is a structure and you need only
3566 initialize the members that are going to be used by the actions. The
3567 four members are called @code{first_line}, @code{first_column},
3568 @code{last_line} and @code{last_column}. Note that the use of this
3569 feature makes the parser noticeably slower.
3570
3571 @tindex YYLTYPE
3572 The data type of @code{yylloc} has the name @code{YYLTYPE}.
3573
3574 @node Pure Calling
3575 @subsection Calling Conventions for Pure Parsers
3576
3577 When you use the Bison declaration @code{%pure_parser} to request a
3578 pure, reentrant parser, the global communication variables @code{yylval}
3579 and @code{yylloc} cannot be used. (@xref{Pure Decl, ,A Pure (Reentrant)
3580 Parser}.) In such parsers the two global variables are replaced by
3581 pointers passed as arguments to @code{yylex}. You must declare them as
3582 shown here, and pass the information back by storing it through those
3583 pointers.
3584
3585 @example
3586 int
3587 yylex (YYSTYPE *lvalp, YYLTYPE *llocp)
3588 @{
3589 @dots{}
3590 *lvalp = value; /* Put value onto Bison stack. */
3591 return INT; /* Return the type of the token. */
3592 @dots{}
3593 @}
3594 @end example
3595
3596 If the grammar file does not use the @samp{@@} constructs to refer to
3597 textual positions, then the type @code{YYLTYPE} will not be defined. In
3598 this case, omit the second argument; @code{yylex} will be called with
3599 only one argument.
3600
3601 @vindex YYPARSE_PARAM
3602 If you use a reentrant parser, you can optionally pass additional
3603 parameter information to it in a reentrant way. To do so, define the
3604 macro @code{YYPARSE_PARAM} as a variable name. This modifies the
3605 @code{yyparse} function to accept one argument, of type @code{void *},
3606 with that name.
3607
3608 When you call @code{yyparse}, pass the address of an object, casting the
3609 address to @code{void *}. The grammar actions can refer to the contents
3610 of the object by casting the pointer value back to its proper type and
3611 then dereferencing it. Here's an example. Write this in the parser:
3612
3613 @example
3614 %@{
3615 struct parser_control
3616 @{
3617 int nastiness;
3618 int randomness;
3619 @};
3620
3621 #define YYPARSE_PARAM parm
3622 %@}
3623 @end example
3624
3625 @noindent
3626 Then call the parser like this:
3627
3628 @example
3629 struct parser_control
3630 @{
3631 int nastiness;
3632 int randomness;
3633 @};
3634
3635 @dots{}
3636
3637 @{
3638 struct parser_control foo;
3639 @dots{} /* @r{Store proper data in @code{foo}.} */
3640 value = yyparse ((void *) &foo);
3641 @dots{}
3642 @}
3643 @end example
3644
3645 @noindent
3646 In the grammar actions, use expressions like this to refer to the data:
3647
3648 @example
3649 ((struct parser_control *) parm)->randomness
3650 @end example
3651
3652 @vindex YYLEX_PARAM
3653 If you wish to pass the additional parameter data to @code{yylex},
3654 define the macro @code{YYLEX_PARAM} just like @code{YYPARSE_PARAM}, as
3655 shown here:
3656
3657 @example
3658 %@{
3659 struct parser_control
3660 @{
3661 int nastiness;
3662 int randomness;
3663 @};
3664
3665 #define YYPARSE_PARAM parm
3666 #define YYLEX_PARAM parm
3667 %@}
3668 @end example
3669
3670 You should then define @code{yylex} to accept one additional
3671 argument---the value of @code{parm}. (This makes either two or three
3672 arguments in total, depending on whether an argument of type
3673 @code{YYLTYPE} is passed.) You can declare the argument as a pointer to
3674 the proper object type, or you can declare it as @code{void *} and
3675 access the contents as shown above.
3676
3677 You can use @samp{%pure_parser} to request a reentrant parser without
3678 also using @code{YYPARSE_PARAM}. Then you should call @code{yyparse}
3679 with no arguments, as usual.
3680
3681 @node Error Reporting
3682 @section The Error Reporting Function @code{yyerror}
3683 @cindex error reporting function
3684 @findex yyerror
3685 @cindex parse error
3686 @cindex syntax error
3687
3688 The Bison parser detects a @dfn{parse error} or @dfn{syntax error}
3689 whenever it reads a token which cannot satisfy any syntax rule. An
3690 action in the grammar can also explicitly proclaim an error, using the
3691 macro @code{YYERROR} (@pxref{Action Features, ,Special Features for Use
3692 in Actions}).
3693
3694 The Bison parser expects to report the error by calling an error
3695 reporting function named @code{yyerror}, which you must supply. It is
3696 called by @code{yyparse} whenever a syntax error is found, and it
3697 receives one argument. For a parse error, the string is normally
3698 @w{@code{"parse error"}}.
3699
3700 @findex YYERROR_VERBOSE
3701 If you define the macro @code{YYERROR_VERBOSE} in the Bison declarations
3702 section (@pxref{Bison Declarations, ,The Bison Declarations Section}),
3703 then Bison provides a more verbose and specific error message string
3704 instead of just plain @w{@code{"parse error"}}. It doesn't matter what
3705 definition you use for @code{YYERROR_VERBOSE}, just whether you define
3706 it.
3707
3708 The parser can detect one other kind of error: stack overflow. This
3709 happens when the input contains constructions that are very deeply
3710 nested. It isn't likely you will encounter this, since the Bison
3711 parser extends its stack automatically up to a very large limit. But
3712 if overflow happens, @code{yyparse} calls @code{yyerror} in the usual
3713 fashion, except that the argument string is @w{@code{"parser stack
3714 overflow"}}.
3715
3716 The following definition suffices in simple programs:
3717
3718 @example
3719 @group
3720 void
3721 yyerror (char *s)
3722 @{
3723 @end group
3724 @group
3725 fprintf (stderr, "%s\n", s);
3726 @}
3727 @end group
3728 @end example
3729
3730 After @code{yyerror} returns to @code{yyparse}, the latter will attempt
3731 error recovery if you have written suitable error recovery grammar rules
3732 (@pxref{Error Recovery}). If recovery is impossible, @code{yyparse} will
3733 immediately return 1.
3734
3735 @vindex yynerrs
3736 The variable @code{yynerrs} contains the number of syntax errors
3737 encountered so far. Normally this variable is global; but if you
3738 request a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}) then it is a local variable
3739 which only the actions can access.
3740
3741 @node Action Features
3742 @section Special Features for Use in Actions
3743 @cindex summary, action features
3744 @cindex action features summary
3745
3746 Here is a table of Bison constructs, variables and macros that
3747 are useful in actions.
3748
3749 @table @samp
3750 @item $$
3751 Acts like a variable that contains the semantic value for the
3752 grouping made by the current rule. @xref{Actions}.
3753
3754 @item $@var{n}
3755 Acts like a variable that contains the semantic value for the
3756 @var{n}th component of the current rule. @xref{Actions}.
3757
3758 @item $<@var{typealt}>$
3759 Like @code{$$} but specifies alternative @var{typealt} in the union
3760 specified by the @code{%union} declaration. @xref{Action Types, ,Data Types of Values in Actions}.
3761
3762 @item $<@var{typealt}>@var{n}
3763 Like @code{$@var{n}} but specifies alternative @var{typealt} in the
3764 union specified by the @code{%union} declaration.
3765 @xref{Action Types, ,Data Types of Values in Actions}.@refill
3766
3767 @item YYABORT;
3768 Return immediately from @code{yyparse}, indicating failure.
3769 @xref{Parser Function, ,The Parser Function @code{yyparse}}.
3770
3771 @item YYACCEPT;
3772 Return immediately from @code{yyparse}, indicating success.
3773 @xref{Parser Function, ,The Parser Function @code{yyparse}}.
3774
3775 @item YYBACKUP (@var{token}, @var{value});
3776 @findex YYBACKUP
3777 Unshift a token. This macro is allowed only for rules that reduce
3778 a single value, and only when there is no look-ahead token.
3779 It installs a look-ahead token with token type @var{token} and
3780 semantic value @var{value}; then it discards the value that was
3781 going to be reduced by this rule.
3782
3783 If the macro is used when it is not valid, such as when there is
3784 a look-ahead token already, then it reports a syntax error with
3785 a message @samp{cannot back up} and performs ordinary error
3786 recovery.
3787
3788 In either case, the rest of the action is not executed.
3789
3790 @item YYEMPTY
3791 @vindex YYEMPTY
3792 Value stored in @code{yychar} when there is no look-ahead token.
3793
3794 @item YYERROR;
3795 @findex YYERROR
3796 Cause an immediate syntax error. This statement initiates error
3797 recovery just as if the parser itself had detected an error; however, it
3798 does not call @code{yyerror}, and does not print any message. If you
3799 want to print an error message, call @code{yyerror} explicitly before
3800 the @samp{YYERROR;} statement. @xref{Error Recovery}.
3801
3802 @item YYRECOVERING
3803 This macro stands for an expression that has the value 1 when the parser
3804 is recovering from a syntax error, and 0 the rest of the time.
3805 @xref{Error Recovery}.
3806
3807 @item yychar
3808 Variable containing the current look-ahead token. (In a pure parser,
3809 this is actually a local variable within @code{yyparse}.) When there is
3810 no look-ahead token, the value @code{YYEMPTY} is stored in the variable.
3811 @xref{Look-Ahead, ,Look-Ahead Tokens}.
3812
3813 @item yyclearin;
3814 Discard the current look-ahead token. This is useful primarily in
3815 error rules. @xref{Error Recovery}.
3816
3817 @item yyerrok;
3818 Resume generating error messages immediately for subsequent syntax
3819 errors. This is useful primarily in error rules.
3820 @xref{Error Recovery}.
3821
3822 @item @@$
3823 @findex @@$
3824 Acts like a structure variable containing information on the textual position
3825 of the grouping made by the current rule. @xref{Locations, ,
3826 Tracking Locations}.
3827
3828 @c Check if those paragraphs are still useful or not.
3829
3830 @c @example
3831 @c struct @{
3832 @c int first_line, last_line;
3833 @c int first_column, last_column;
3834 @c @};
3835 @c @end example
3836
3837 @c Thus, to get the starting line number of the third component, you would
3838 @c use @samp{@@3.first_line}.
3839
3840 @c In order for the members of this structure to contain valid information,
3841 @c you must make @code{yylex} supply this information about each token.
3842 @c If you need only certain members, then @code{yylex} need only fill in
3843 @c those members.
3844
3845 @c The use of this feature makes the parser noticeably slower.
3846
3847 @item @@@var{n}
3848 @findex @@@var{n}
3849 Acts like a structure variable containing information on the textual position
3850 of the @var{n}th component of the current rule. @xref{Locations, ,
3851 Tracking Locations}.
3852
3853 @end table
3854
3855 @node Algorithm
3856 @chapter The Bison Parser Algorithm
3857 @cindex Bison parser algorithm
3858 @cindex algorithm of parser
3859 @cindex shifting
3860 @cindex reduction
3861 @cindex parser stack
3862 @cindex stack, parser
3863
3864 As Bison reads tokens, it pushes them onto a stack along with their
3865 semantic values. The stack is called the @dfn{parser stack}. Pushing a
3866 token is traditionally called @dfn{shifting}.
3867
3868 For example, suppose the infix calculator has read @samp{1 + 5 *}, with a
3869 @samp{3} to come. The stack will have four elements, one for each token
3870 that was shifted.
3871
3872 But the stack does not always have an element for each token read. When
3873 the last @var{n} tokens and groupings shifted match the components of a
3874 grammar rule, they can be combined according to that rule. This is called
3875 @dfn{reduction}. Those tokens and groupings are replaced on the stack by a
3876 single grouping whose symbol is the result (left hand side) of that rule.
3877 Running the rule's action is part of the process of reduction, because this
3878 is what computes the semantic value of the resulting grouping.
3879
3880 For example, if the infix calculator's parser stack contains this:
3881
3882 @example
3883 1 + 5 * 3
3884 @end example
3885
3886 @noindent
3887 and the next input token is a newline character, then the last three
3888 elements can be reduced to 15 via the rule:
3889
3890 @example
3891 expr: expr '*' expr;
3892 @end example
3893
3894 @noindent
3895 Then the stack contains just these three elements:
3896
3897 @example
3898 1 + 15
3899 @end example
3900
3901 @noindent
3902 At this point, another reduction can be made, resulting in the single value
3903 16. Then the newline token can be shifted.
3904
3905 The parser tries, by shifts and reductions, to reduce the entire input down
3906 to a single grouping whose symbol is the grammar's start-symbol
3907 (@pxref{Language and Grammar, ,Languages and Context-Free Grammars}).
3908
3909 This kind of parser is known in the literature as a bottom-up parser.
3910
3911 @menu
3912 * Look-Ahead:: Parser looks one token ahead when deciding what to do.
3913 * Shift/Reduce:: Conflicts: when either shifting or reduction is valid.
3914 * Precedence:: Operator precedence works by resolving conflicts.
3915 * Contextual Precedence:: When an operator's precedence depends on context.
3916 * Parser States:: The parser is a finite-state-machine with stack.
3917 * Reduce/Reduce:: When two rules are applicable in the same situation.
3918 * Mystery Conflicts:: Reduce/reduce conflicts that look unjustified.
3919 * Stack Overflow:: What happens when stack gets full. How to avoid it.
3920 @end menu
3921
3922 @node Look-Ahead
3923 @section Look-Ahead Tokens
3924 @cindex look-ahead token
3925
3926 The Bison parser does @emph{not} always reduce immediately as soon as the
3927 last @var{n} tokens and groupings match a rule. This is because such a
3928 simple strategy is inadequate to handle most languages. Instead, when a
3929 reduction is possible, the parser sometimes ``looks ahead'' at the next
3930 token in order to decide what to do.
3931
3932 When a token is read, it is not immediately shifted; first it becomes the
3933 @dfn{look-ahead token}, which is not on the stack. Now the parser can
3934 perform one or more reductions of tokens and groupings on the stack, while
3935 the look-ahead token remains off to the side. When no more reductions
3936 should take place, the look-ahead token is shifted onto the stack. This
3937 does not mean that all possible reductions have been done; depending on the
3938 token type of the look-ahead token, some rules may choose to delay their
3939 application.
3940
3941 Here is a simple case where look-ahead is needed. These three rules define
3942 expressions which contain binary addition operators and postfix unary
3943 factorial operators (@samp{!}), and allow parentheses for grouping.
3944
3945 @example
3946 @group
3947 expr: term '+' expr
3948 | term
3949 ;
3950 @end group
3951
3952 @group
3953 term: '(' expr ')'
3954 | term '!'
3955 | NUMBER
3956 ;
3957 @end group
3958 @end example
3959
3960 Suppose that the tokens @w{@samp{1 + 2}} have been read and shifted; what
3961 should be done? If the following token is @samp{)}, then the first three
3962 tokens must be reduced to form an @code{expr}. This is the only valid
3963 course, because shifting the @samp{)} would produce a sequence of symbols
3964 @w{@code{term ')'}}, and no rule allows this.
3965
3966 If the following token is @samp{!}, then it must be shifted immediately so
3967 that @w{@samp{2 !}} can be reduced to make a @code{term}. If instead the
3968 parser were to reduce before shifting, @w{@samp{1 + 2}} would become an
3969 @code{expr}. It would then be impossible to shift the @samp{!} because
3970 doing so would produce on the stack the sequence of symbols @code{expr
3971 '!'}. No rule allows that sequence.
3972
3973 @vindex yychar
3974 The current look-ahead token is stored in the variable @code{yychar}.
3975 @xref{Action Features, ,Special Features for Use in Actions}.
3976
3977 @node Shift/Reduce
3978 @section Shift/Reduce Conflicts
3979 @cindex conflicts
3980 @cindex shift/reduce conflicts
3981 @cindex dangling @code{else}
3982 @cindex @code{else}, dangling
3983
3984 Suppose we are parsing a language which has if-then and if-then-else
3985 statements, with a pair of rules like this:
3986
3987 @example
3988 @group
3989 if_stmt:
3990 IF expr THEN stmt
3991 | IF expr THEN stmt ELSE stmt
3992 ;
3993 @end group
3994 @end example
3995
3996 @noindent
3997 Here we assume that @code{IF}, @code{THEN} and @code{ELSE} are
3998 terminal symbols for specific keyword tokens.
3999
4000 When the @code{ELSE} token is read and becomes the look-ahead token, the
4001 contents of the stack (assuming the input is valid) are just right for
4002 reduction by the first rule. But it is also legitimate to shift the
4003 @code{ELSE}, because that would lead to eventual reduction by the second
4004 rule.
4005
4006 This situation, where either a shift or a reduction would be valid, is
4007 called a @dfn{shift/reduce conflict}. Bison is designed to resolve
4008 these conflicts by choosing to shift, unless otherwise directed by
4009 operator precedence declarations. To see the reason for this, let's
4010 contrast it with the other alternative.
4011
4012 Since the parser prefers to shift the @code{ELSE}, the result is to attach
4013 the else-clause to the innermost if-statement, making these two inputs
4014 equivalent:
4015
4016 @example
4017 if x then if y then win (); else lose;
4018
4019 if x then do; if y then win (); else lose; end;
4020 @end example
4021
4022 But if the parser chose to reduce when possible rather than shift, the
4023 result would be to attach the else-clause to the outermost if-statement,
4024 making these two inputs equivalent:
4025
4026 @example
4027 if x then if y then win (); else lose;
4028
4029 if x then do; if y then win (); end; else lose;
4030 @end example
4031
4032 The conflict exists because the grammar as written is ambiguous: either
4033 parsing of the simple nested if-statement is legitimate. The established
4034 convention is that these ambiguities are resolved by attaching the
4035 else-clause to the innermost if-statement; this is what Bison accomplishes
4036 by choosing to shift rather than reduce. (It would ideally be cleaner to
4037 write an unambiguous grammar, but that is very hard to do in this case.)
4038 This particular ambiguity was first encountered in the specifications of
4039 Algol 60 and is called the ``dangling @code{else}'' ambiguity.
4040
4041 To avoid warnings from Bison about predictable, legitimate shift/reduce
4042 conflicts, use the @code{%expect @var{n}} declaration. There will be no
4043 warning as long as the number of shift/reduce conflicts is exactly @var{n}.
4044 @xref{Expect Decl, ,Suppressing Conflict Warnings}.
4045
4046 The definition of @code{if_stmt} above is solely to blame for the
4047 conflict, but the conflict does not actually appear without additional
4048 rules. Here is a complete Bison input file that actually manifests the
4049 conflict:
4050
4051 @example
4052 @group
4053 %token IF THEN ELSE variable
4054 %%
4055 @end group
4056 @group
4057 stmt: expr
4058 | if_stmt
4059 ;
4060 @end group
4061
4062 @group
4063 if_stmt:
4064 IF expr THEN stmt
4065 | IF expr THEN stmt ELSE stmt
4066 ;
4067 @end group
4068
4069 expr: variable
4070 ;
4071 @end example
4072
4073 @node Precedence
4074 @section Operator Precedence
4075 @cindex operator precedence
4076 @cindex precedence of operators
4077
4078 Another situation where shift/reduce conflicts appear is in arithmetic
4079 expressions. Here shifting is not always the preferred resolution; the
4080 Bison declarations for operator precedence allow you to specify when to
4081 shift and when to reduce.
4082
4083 @menu
4084 * Why Precedence:: An example showing why precedence is needed.
4085 * Using Precedence:: How to specify precedence in Bison grammars.
4086 * Precedence Examples:: How these features are used in the previous example.
4087 * How Precedence:: How they work.
4088 @end menu
4089
4090 @node Why Precedence
4091 @subsection When Precedence is Needed
4092
4093 Consider the following ambiguous grammar fragment (ambiguous because the
4094 input @w{@samp{1 - 2 * 3}} can be parsed in two different ways):
4095
4096 @example
4097 @group
4098 expr: expr '-' expr
4099 | expr '*' expr
4100 | expr '<' expr
4101 | '(' expr ')'
4102 @dots{}
4103 ;
4104 @end group
4105 @end example
4106
4107 @noindent
4108 Suppose the parser has seen the tokens @samp{1}, @samp{-} and @samp{2};
4109 should it reduce them via the rule for the subtraction operator? It
4110 depends on the next token. Of course, if the next token is @samp{)}, we
4111 must reduce; shifting is invalid because no single rule can reduce the
4112 token sequence @w{@samp{- 2 )}} or anything starting with that. But if
4113 the next token is @samp{*} or @samp{<}, we have a choice: either
4114 shifting or reduction would allow the parse to complete, but with
4115 different results.
4116
4117 To decide which one Bison should do, we must consider the results. If
4118 the next operator token @var{op} is shifted, then it must be reduced
4119 first in order to permit another opportunity to reduce the difference.
4120 The result is (in effect) @w{@samp{1 - (2 @var{op} 3)}}. On the other
4121 hand, if the subtraction is reduced before shifting @var{op}, the result
4122 is @w{@samp{(1 - 2) @var{op} 3}}. Clearly, then, the choice of shift or
4123 reduce should depend on the relative precedence of the operators
4124 @samp{-} and @var{op}: @samp{*} should be shifted first, but not
4125 @samp{<}.
4126
4127 @cindex associativity
4128 What about input such as @w{@samp{1 - 2 - 5}}; should this be
4129 @w{@samp{(1 - 2) - 5}} or should it be @w{@samp{1 - (2 - 5)}}? For most
4130 operators we prefer the former, which is called @dfn{left association}.
4131 The latter alternative, @dfn{right association}, is desirable for
4132 assignment operators. The choice of left or right association is a
4133 matter of whether the parser chooses to shift or reduce when the stack
4134 contains @w{@samp{1 - 2}} and the look-ahead token is @samp{-}: shifting
4135 makes right-associativity.
4136
4137 @node Using Precedence
4138 @subsection Specifying Operator Precedence
4139 @findex %left
4140 @findex %right
4141 @findex %nonassoc
4142
4143 Bison allows you to specify these choices with the operator precedence
4144 declarations @code{%left} and @code{%right}. Each such declaration
4145 contains a list of tokens, which are operators whose precedence and
4146 associativity is being declared. The @code{%left} declaration makes all
4147 those operators left-associative and the @code{%right} declaration makes
4148 them right-associative. A third alternative is @code{%nonassoc}, which
4149 declares that it is a syntax error to find the same operator twice ``in a
4150 row''.
4151
4152 The relative precedence of different operators is controlled by the
4153 order in which they are declared. The first @code{%left} or
4154 @code{%right} declaration in the file declares the operators whose
4155 precedence is lowest, the next such declaration declares the operators
4156 whose precedence is a little higher, and so on.
4157
4158 @node Precedence Examples
4159 @subsection Precedence Examples
4160
4161 In our example, we would want the following declarations:
4162
4163 @example
4164 %left '<'
4165 %left '-'
4166 %left '*'
4167 @end example
4168
4169 In a more complete example, which supports other operators as well, we
4170 would declare them in groups of equal precedence. For example, @code{'+'} is
4171 declared with @code{'-'}:
4172
4173 @example
4174 %left '<' '>' '=' NE LE GE
4175 %left '+' '-'
4176 %left '*' '/'
4177 @end example
4178
4179 @noindent
4180 (Here @code{NE} and so on stand for the operators for ``not equal''
4181 and so on. We assume that these tokens are more than one character long
4182 and therefore are represented by names, not character literals.)
4183
4184 @node How Precedence
4185 @subsection How Precedence Works
4186
4187 The first effect of the precedence declarations is to assign precedence
4188 levels to the terminal symbols declared. The second effect is to assign
4189 precedence levels to certain rules: each rule gets its precedence from the
4190 last terminal symbol mentioned in the components. (You can also specify
4191 explicitly the precedence of a rule. @xref{Contextual Precedence, ,Context-Dependent Precedence}.)
4192
4193 Finally, the resolution of conflicts works by comparing the
4194 precedence of the rule being considered with that of the
4195 look-ahead token. If the token's precedence is higher, the
4196 choice is to shift. If the rule's precedence is higher, the
4197 choice is to reduce. If they have equal precedence, the choice
4198 is made based on the associativity of that precedence level. The
4199 verbose output file made by @samp{-v} (@pxref{Invocation, ,Invoking Bison}) says
4200 how each conflict was resolved.
4201
4202 Not all rules and not all tokens have precedence. If either the rule or
4203 the look-ahead token has no precedence, then the default is to shift.
4204
4205 @node Contextual Precedence
4206 @section Context-Dependent Precedence
4207 @cindex context-dependent precedence
4208 @cindex unary operator precedence
4209 @cindex precedence, context-dependent
4210 @cindex precedence, unary operator
4211 @findex %prec
4212
4213 Often the precedence of an operator depends on the context. This sounds
4214 outlandish at first, but it is really very common. For example, a minus
4215 sign typically has a very high precedence as a unary operator, and a
4216 somewhat lower precedence (lower than multiplication) as a binary operator.
4217
4218 The Bison precedence declarations, @code{%left}, @code{%right} and
4219 @code{%nonassoc}, can only be used once for a given token; so a token has
4220 only one precedence declared in this way. For context-dependent
4221 precedence, you need to use an additional mechanism: the @code{%prec}
4222 modifier for rules.@refill
4223
4224 The @code{%prec} modifier declares the precedence of a particular rule by
4225 specifying a terminal symbol whose precedence should be used for that rule.
4226 It's not necessary for that symbol to appear otherwise in the rule. The
4227 modifier's syntax is:
4228
4229 @example
4230 %prec @var{terminal-symbol}
4231 @end example
4232
4233 @noindent
4234 and it is written after the components of the rule. Its effect is to
4235 assign the rule the precedence of @var{terminal-symbol}, overriding
4236 the precedence that would be deduced for it in the ordinary way. The
4237 altered rule precedence then affects how conflicts involving that rule
4238 are resolved (@pxref{Precedence, ,Operator Precedence}).
4239
4240 Here is how @code{%prec} solves the problem of unary minus. First, declare
4241 a precedence for a fictitious terminal symbol named @code{UMINUS}. There
4242 are no tokens of this type, but the symbol serves to stand for its
4243 precedence:
4244
4245 @example
4246 @dots{}
4247 %left '+' '-'
4248 %left '*'
4249 %left UMINUS
4250 @end example
4251
4252 Now the precedence of @code{UMINUS} can be used in specific rules:
4253
4254 @example
4255 @group
4256 exp: @dots{}
4257 | exp '-' exp
4258 @dots{}
4259 | '-' exp %prec UMINUS
4260 @end group
4261 @end example
4262
4263 @node Parser States
4264 @section Parser States
4265 @cindex finite-state machine
4266 @cindex parser state
4267 @cindex state (of parser)
4268
4269 The function @code{yyparse} is implemented using a finite-state machine.
4270 The values pushed on the parser stack are not simply token type codes; they
4271 represent the entire sequence of terminal and nonterminal symbols at or
4272 near the top of the stack. The current state collects all the information
4273 about previous input which is relevant to deciding what to do next.
4274
4275 Each time a look-ahead token is read, the current parser state together
4276 with the type of look-ahead token are looked up in a table. This table
4277 entry can say, ``Shift the look-ahead token.'' In this case, it also
4278 specifies the new parser state, which is pushed onto the top of the
4279 parser stack. Or it can say, ``Reduce using rule number @var{n}.''
4280 This means that a certain number of tokens or groupings are taken off
4281 the top of the stack, and replaced by one grouping. In other words,
4282 that number of states are popped from the stack, and one new state is
4283 pushed.
4284
4285 There is one other alternative: the table can say that the look-ahead token
4286 is erroneous in the current state. This causes error processing to begin
4287 (@pxref{Error Recovery}).
4288
4289 @node Reduce/Reduce
4290 @section Reduce/Reduce Conflicts
4291 @cindex reduce/reduce conflict
4292 @cindex conflicts, reduce/reduce
4293
4294 A reduce/reduce conflict occurs if there are two or more rules that apply
4295 to the same sequence of input. This usually indicates a serious error
4296 in the grammar.
4297
4298 For example, here is an erroneous attempt to define a sequence
4299 of zero or more @code{word} groupings.
4300
4301 @example
4302 sequence: /* empty */
4303 @{ printf ("empty sequence\n"); @}
4304 | maybeword
4305 | sequence word
4306 @{ printf ("added word %s\n", $2); @}
4307 ;
4308
4309 maybeword: /* empty */
4310 @{ printf ("empty maybeword\n"); @}
4311 | word
4312 @{ printf ("single word %s\n", $1); @}
4313 ;
4314 @end example
4315
4316 @noindent
4317 The error is an ambiguity: there is more than one way to parse a single
4318 @code{word} into a @code{sequence}. It could be reduced to a
4319 @code{maybeword} and then into a @code{sequence} via the second rule.
4320 Alternatively, nothing-at-all could be reduced into a @code{sequence}
4321 via the first rule, and this could be combined with the @code{word}
4322 using the third rule for @code{sequence}.
4323
4324 There is also more than one way to reduce nothing-at-all into a
4325 @code{sequence}. This can be done directly via the first rule,
4326 or indirectly via @code{maybeword} and then the second rule.
4327
4328 You might think that this is a distinction without a difference, because it
4329 does not change whether any particular input is valid or not. But it does
4330 affect which actions are run. One parsing order runs the second rule's
4331 action; the other runs the first rule's action and the third rule's action.
4332 In this example, the output of the program changes.
4333
4334 Bison resolves a reduce/reduce conflict by choosing to use the rule that
4335 appears first in the grammar, but it is very risky to rely on this. Every
4336 reduce/reduce conflict must be studied and usually eliminated. Here is the
4337 proper way to define @code{sequence}:
4338
4339 @example
4340 sequence: /* empty */
4341 @{ printf ("empty sequence\n"); @}
4342 | sequence word
4343 @{ printf ("added word %s\n", $2); @}
4344 ;
4345 @end example
4346
4347 Here is another common error that yields a reduce/reduce conflict:
4348
4349 @example
4350 sequence: /* empty */
4351 | sequence words
4352 | sequence redirects
4353 ;
4354
4355 words: /* empty */
4356 | words word
4357 ;
4358
4359 redirects:/* empty */
4360 | redirects redirect
4361 ;
4362 @end example
4363
4364 @noindent
4365 The intention here is to define a sequence which can contain either
4366 @code{word} or @code{redirect} groupings. The individual definitions of
4367 @code{sequence}, @code{words} and @code{redirects} are error-free, but the
4368 three together make a subtle ambiguity: even an empty input can be parsed
4369 in infinitely many ways!
4370
4371 Consider: nothing-at-all could be a @code{words}. Or it could be two
4372 @code{words} in a row, or three, or any number. It could equally well be a
4373 @code{redirects}, or two, or any number. Or it could be a @code{words}
4374 followed by three @code{redirects} and another @code{words}. And so on.
4375
4376 Here are two ways to correct these rules. First, to make it a single level
4377 of sequence:
4378
4379 @example
4380 sequence: /* empty */
4381 | sequence word
4382 | sequence redirect
4383 ;
4384 @end example
4385
4386 Second, to prevent either a @code{words} or a @code{redirects}
4387 from being empty:
4388
4389 @example
4390 sequence: /* empty */
4391 | sequence words
4392 | sequence redirects
4393 ;
4394
4395 words: word
4396 | words word
4397 ;
4398
4399 redirects:redirect
4400 | redirects redirect
4401 ;
4402 @end example
4403
4404 @node Mystery Conflicts
4405 @section Mysterious Reduce/Reduce Conflicts
4406
4407 Sometimes reduce/reduce conflicts can occur that don't look warranted.
4408 Here is an example:
4409
4410 @example
4411 @group
4412 %token ID
4413
4414 %%
4415 def: param_spec return_spec ','
4416 ;
4417 param_spec:
4418 type
4419 | name_list ':' type
4420 ;
4421 @end group
4422 @group
4423 return_spec:
4424 type
4425 | name ':' type
4426 ;
4427 @end group
4428 @group
4429 type: ID
4430 ;
4431 @end group
4432 @group
4433 name: ID
4434 ;
4435 name_list:
4436 name
4437 | name ',' name_list
4438 ;
4439 @end group
4440 @end example
4441
4442 It would seem that this grammar can be parsed with only a single token
4443 of look-ahead: when a @code{param_spec} is being read, an @code{ID} is
4444 a @code{name} if a comma or colon follows, or a @code{type} if another
4445 @code{ID} follows. In other words, this grammar is LR(1).
4446
4447 @cindex LR(1)
4448 @cindex LALR(1)
4449 However, Bison, like most parser generators, cannot actually handle all
4450 LR(1) grammars. In this grammar, two contexts, that after an @code{ID}
4451 at the beginning of a @code{param_spec} and likewise at the beginning of
4452 a @code{return_spec}, are similar enough that Bison assumes they are the
4453 same. They appear similar because the same set of rules would be
4454 active---the rule for reducing to a @code{name} and that for reducing to
4455 a @code{type}. Bison is unable to determine at that stage of processing
4456 that the rules would require different look-ahead tokens in the two
4457 contexts, so it makes a single parser state for them both. Combining
4458 the two contexts causes a conflict later. In parser terminology, this
4459 occurrence means that the grammar is not LALR(1).
4460
4461 In general, it is better to fix deficiencies than to document them. But
4462 this particular deficiency is intrinsically hard to fix; parser
4463 generators that can handle LR(1) grammars are hard to write and tend to
4464 produce parsers that are very large. In practice, Bison is more useful
4465 as it is now.
4466
4467 When the problem arises, you can often fix it by identifying the two
4468 parser states that are being confused, and adding something to make them
4469 look distinct. In the above example, adding one rule to
4470 @code{return_spec} as follows makes the problem go away:
4471
4472 @example
4473 @group
4474 %token BOGUS
4475 @dots{}
4476 %%
4477 @dots{}
4478 return_spec:
4479 type
4480 | name ':' type
4481 /* This rule is never used. */
4482 | ID BOGUS
4483 ;
4484 @end group
4485 @end example
4486
4487 This corrects the problem because it introduces the possibility of an
4488 additional active rule in the context after the @code{ID} at the beginning of
4489 @code{return_spec}. This rule is not active in the corresponding context
4490 in a @code{param_spec}, so the two contexts receive distinct parser states.
4491 As long as the token @code{BOGUS} is never generated by @code{yylex},
4492 the added rule cannot alter the way actual input is parsed.
4493
4494 In this particular example, there is another way to solve the problem:
4495 rewrite the rule for @code{return_spec} to use @code{ID} directly
4496 instead of via @code{name}. This also causes the two confusing
4497 contexts to have different sets of active rules, because the one for
4498 @code{return_spec} activates the altered rule for @code{return_spec}
4499 rather than the one for @code{name}.
4500
4501 @example
4502 param_spec:
4503 type
4504 | name_list ':' type
4505 ;
4506 return_spec:
4507 type
4508 | ID ':' type
4509 ;
4510 @end example
4511
4512 @node Stack Overflow
4513 @section Stack Overflow, and How to Avoid It
4514 @cindex stack overflow
4515 @cindex parser stack overflow
4516 @cindex overflow of parser stack
4517
4518 The Bison parser stack can overflow if too many tokens are shifted and
4519 not reduced. When this happens, the parser function @code{yyparse}
4520 returns a nonzero value, pausing only to call @code{yyerror} to report
4521 the overflow.
4522
4523 @vindex YYMAXDEPTH
4524 By defining the macro @code{YYMAXDEPTH}, you can control how deep the
4525 parser stack can become before a stack overflow occurs. Define the
4526 macro with a value that is an integer. This value is the maximum number
4527 of tokens that can be shifted (and not reduced) before overflow.
4528 It must be a constant expression whose value is known at compile time.
4529
4530 The stack space allowed is not necessarily allocated. If you specify a
4531 large value for @code{YYMAXDEPTH}, the parser actually allocates a small
4532 stack at first, and then makes it bigger by stages as needed. This
4533 increasing allocation happens automatically and silently. Therefore,
4534 you do not need to make @code{YYMAXDEPTH} painfully small merely to save
4535 space for ordinary inputs that do not need much stack.
4536
4537 @cindex default stack limit
4538 The default value of @code{YYMAXDEPTH}, if you do not define it, is
4539 10000.
4540
4541 @vindex YYINITDEPTH
4542 You can control how much stack is allocated initially by defining the
4543 macro @code{YYINITDEPTH}. This value too must be a compile-time
4544 constant integer. The default is 200.
4545
4546 @node Error Recovery
4547 @chapter Error Recovery
4548 @cindex error recovery
4549 @cindex recovery from errors
4550
4551 It is not usually acceptable to have a program terminate on a parse
4552 error. For example, a compiler should recover sufficiently to parse the
4553 rest of the input file and check it for errors; a calculator should accept
4554 another expression.
4555
4556 In a simple interactive command parser where each input is one line, it may
4557 be sufficient to allow @code{yyparse} to return 1 on error and have the
4558 caller ignore the rest of the input line when that happens (and then call
4559 @code{yyparse} again). But this is inadequate for a compiler, because it
4560 forgets all the syntactic context leading up to the error. A syntax error
4561 deep within a function in the compiler input should not cause the compiler
4562 to treat the following line like the beginning of a source file.
4563
4564 @findex error
4565 You can define how to recover from a syntax error by writing rules to
4566 recognize the special token @code{error}. This is a terminal symbol that
4567 is always defined (you need not declare it) and reserved for error
4568 handling. The Bison parser generates an @code{error} token whenever a
4569 syntax error happens; if you have provided a rule to recognize this token
4570 in the current context, the parse can continue.
4571
4572 For example:
4573
4574 @example
4575 stmnts: /* empty string */
4576 | stmnts '\n'
4577 | stmnts exp '\n'
4578 | stmnts error '\n'
4579 @end example
4580
4581 The fourth rule in this example says that an error followed by a newline
4582 makes a valid addition to any @code{stmnts}.
4583
4584 What happens if a syntax error occurs in the middle of an @code{exp}? The
4585 error recovery rule, interpreted strictly, applies to the precise sequence
4586 of a @code{stmnts}, an @code{error} and a newline. If an error occurs in
4587 the middle of an @code{exp}, there will probably be some additional tokens
4588 and subexpressions on the stack after the last @code{stmnts}, and there
4589 will be tokens to read before the next newline. So the rule is not
4590 applicable in the ordinary way.
4591
4592 But Bison can force the situation to fit the rule, by discarding part of
4593 the semantic context and part of the input. First it discards states and
4594 objects from the stack until it gets back to a state in which the
4595 @code{error} token is acceptable. (This means that the subexpressions
4596 already parsed are discarded, back to the last complete @code{stmnts}.) At
4597 this point the @code{error} token can be shifted. Then, if the old
4598 look-ahead token is not acceptable to be shifted next, the parser reads
4599 tokens and discards them until it finds a token which is acceptable. In
4600 this example, Bison reads and discards input until the next newline
4601 so that the fourth rule can apply.
4602
4603 The choice of error rules in the grammar is a choice of strategies for
4604 error recovery. A simple and useful strategy is simply to skip the rest of
4605 the current input line or current statement if an error is detected:
4606
4607 @example
4608 stmnt: error ';' /* on error, skip until ';' is read */
4609 @end example
4610
4611 It is also useful to recover to the matching close-delimiter of an
4612 opening-delimiter that has already been parsed. Otherwise the
4613 close-delimiter will probably appear to be unmatched, and generate another,
4614 spurious error message:
4615
4616 @example
4617 primary: '(' expr ')'
4618 | '(' error ')'
4619 @dots{}
4620 ;
4621 @end example
4622
4623 Error recovery strategies are necessarily guesses. When they guess wrong,
4624 one syntax error often leads to another. In the above example, the error
4625 recovery rule guesses that an error is due to bad input within one
4626 @code{stmnt}. Suppose that instead a spurious semicolon is inserted in the
4627 middle of a valid @code{stmnt}. After the error recovery rule recovers
4628 from the first error, another syntax error will be found straightaway,
4629 since the text following the spurious semicolon is also an invalid
4630 @code{stmnt}.
4631
4632 To prevent an outpouring of error messages, the parser will output no error
4633 message for another syntax error that happens shortly after the first; only
4634 after three consecutive input tokens have been successfully shifted will
4635 error messages resume.
4636
4637 Note that rules which accept the @code{error} token may have actions, just
4638 as any other rules can.
4639
4640 @findex yyerrok
4641 You can make error messages resume immediately by using the macro
4642 @code{yyerrok} in an action. If you do this in the error rule's action, no
4643 error messages will be suppressed. This macro requires no arguments;
4644 @samp{yyerrok;} is a valid C statement.
4645
4646 @findex yyclearin
4647 The previous look-ahead token is reanalyzed immediately after an error. If
4648 this is unacceptable, then the macro @code{yyclearin} may be used to clear
4649 this token. Write the statement @samp{yyclearin;} in the error rule's
4650 action.
4651
4652 For example, suppose that on a parse error, an error handling routine is
4653 called that advances the input stream to some point where parsing should
4654 once again commence. The next symbol returned by the lexical scanner is
4655 probably correct. The previous look-ahead token ought to be discarded
4656 with @samp{yyclearin;}.
4657
4658 @vindex YYRECOVERING
4659 The macro @code{YYRECOVERING} stands for an expression that has the
4660 value 1 when the parser is recovering from a syntax error, and 0 the
4661 rest of the time. A value of 1 indicates that error messages are
4662 currently suppressed for new syntax errors.
4663
4664 @node Context Dependency
4665 @chapter Handling Context Dependencies
4666
4667 The Bison paradigm is to parse tokens first, then group them into larger
4668 syntactic units. In many languages, the meaning of a token is affected by
4669 its context. Although this violates the Bison paradigm, certain techniques
4670 (known as @dfn{kludges}) may enable you to write Bison parsers for such
4671 languages.
4672
4673 @menu
4674 * Semantic Tokens:: Token parsing can depend on the semantic context.
4675 * Lexical Tie-ins:: Token parsing can depend on the syntactic context.
4676 * Tie-in Recovery:: Lexical tie-ins have implications for how
4677 error recovery rules must be written.
4678 @end menu
4679
4680 (Actually, ``kludge'' means any technique that gets its job done but is
4681 neither clean nor robust.)
4682
4683 @node Semantic Tokens
4684 @section Semantic Info in Token Types
4685
4686 The C language has a context dependency: the way an identifier is used
4687 depends on what its current meaning is. For example, consider this:
4688
4689 @example
4690 foo (x);
4691 @end example
4692
4693 This looks like a function call statement, but if @code{foo} is a typedef
4694 name, then this is actually a declaration of @code{x}. How can a Bison
4695 parser for C decide how to parse this input?
4696
4697 The method used in GNU C is to have two different token types,
4698 @code{IDENTIFIER} and @code{TYPENAME}. When @code{yylex} finds an
4699 identifier, it looks up the current declaration of the identifier in order
4700 to decide which token type to return: @code{TYPENAME} if the identifier is
4701 declared as a typedef, @code{IDENTIFIER} otherwise.
4702
4703 The grammar rules can then express the context dependency by the choice of
4704 token type to recognize. @code{IDENTIFIER} is accepted as an expression,
4705 but @code{TYPENAME} is not. @code{TYPENAME} can start a declaration, but
4706 @code{IDENTIFIER} cannot. In contexts where the meaning of the identifier
4707 is @emph{not} significant, such as in declarations that can shadow a
4708 typedef name, either @code{TYPENAME} or @code{IDENTIFIER} is
4709 accepted---there is one rule for each of the two token types.
4710
4711 This technique is simple to use if the decision of which kinds of
4712 identifiers to allow is made at a place close to where the identifier is
4713 parsed. But in C this is not always so: C allows a declaration to
4714 redeclare a typedef name provided an explicit type has been specified
4715 earlier:
4716
4717 @example
4718 typedef int foo, bar, lose;
4719 static foo (bar); /* @r{redeclare @code{bar} as static variable} */
4720 static int foo (lose); /* @r{redeclare @code{foo} as function} */
4721 @end example
4722
4723 Unfortunately, the name being declared is separated from the declaration
4724 construct itself by a complicated syntactic structure---the ``declarator''.
4725
4726 As a result, part of the Bison parser for C needs to be duplicated, with
4727 all the nonterminal names changed: once for parsing a declaration in
4728 which a typedef name can be redefined, and once for parsing a
4729 declaration in which that can't be done. Here is a part of the
4730 duplication, with actions omitted for brevity:
4731
4732 @example
4733 initdcl:
4734 declarator maybeasm '='
4735 init
4736 | declarator maybeasm
4737 ;
4738
4739 notype_initdcl:
4740 notype_declarator maybeasm '='
4741 init
4742 | notype_declarator maybeasm
4743 ;
4744 @end example
4745
4746 @noindent
4747 Here @code{initdcl} can redeclare a typedef name, but @code{notype_initdcl}
4748 cannot. The distinction between @code{declarator} and
4749 @code{notype_declarator} is the same sort of thing.
4750
4751 There is some similarity between this technique and a lexical tie-in
4752 (described next), in that information which alters the lexical analysis is
4753 changed during parsing by other parts of the program. The difference is
4754 here the information is global, and is used for other purposes in the
4755 program. A true lexical tie-in has a special-purpose flag controlled by
4756 the syntactic context.
4757
4758 @node Lexical Tie-ins
4759 @section Lexical Tie-ins
4760 @cindex lexical tie-in
4761
4762 One way to handle context-dependency is the @dfn{lexical tie-in}: a flag
4763 which is set by Bison actions, whose purpose is to alter the way tokens are
4764 parsed.
4765
4766 For example, suppose we have a language vaguely like C, but with a special
4767 construct @samp{hex (@var{hex-expr})}. After the keyword @code{hex} comes
4768 an expression in parentheses in which all integers are hexadecimal. In
4769 particular, the token @samp{a1b} must be treated as an integer rather than
4770 as an identifier if it appears in that context. Here is how you can do it:
4771
4772 @example
4773 @group
4774 %@{
4775 int hexflag;
4776 %@}
4777 %%
4778 @dots{}
4779 @end group
4780 @group
4781 expr: IDENTIFIER
4782 | constant
4783 | HEX '('
4784 @{ hexflag = 1; @}
4785 expr ')'
4786 @{ hexflag = 0;
4787 $$ = $4; @}
4788 | expr '+' expr
4789 @{ $$ = make_sum ($1, $3); @}
4790 @dots{}
4791 ;
4792 @end group
4793
4794 @group
4795 constant:
4796 INTEGER
4797 | STRING
4798 ;
4799 @end group
4800 @end example
4801
4802 @noindent
4803 Here we assume that @code{yylex} looks at the value of @code{hexflag}; when
4804 it is nonzero, all integers are parsed in hexadecimal, and tokens starting
4805 with letters are parsed as integers if possible.
4806
4807 The declaration of @code{hexflag} shown in the C declarations section of
4808 the parser file is needed to make it accessible to the actions
4809 (@pxref{C Declarations, ,The C Declarations Section}). You must also write the code in @code{yylex}
4810 to obey the flag.
4811
4812 @node Tie-in Recovery
4813 @section Lexical Tie-ins and Error Recovery
4814
4815 Lexical tie-ins make strict demands on any error recovery rules you have.
4816 @xref{Error Recovery}.
4817
4818 The reason for this is that the purpose of an error recovery rule is to
4819 abort the parsing of one construct and resume in some larger construct.
4820 For example, in C-like languages, a typical error recovery rule is to skip
4821 tokens until the next semicolon, and then start a new statement, like this:
4822
4823 @example
4824 stmt: expr ';'
4825 | IF '(' expr ')' stmt @{ @dots{} @}
4826 @dots{}
4827 error ';'
4828 @{ hexflag = 0; @}
4829 ;
4830 @end example
4831
4832 If there is a syntax error in the middle of a @samp{hex (@var{expr})}
4833 construct, this error rule will apply, and then the action for the
4834 completed @samp{hex (@var{expr})} will never run. So @code{hexflag} would
4835 remain set for the entire rest of the input, or until the next @code{hex}
4836 keyword, causing identifiers to be misinterpreted as integers.
4837
4838 To avoid this problem the error recovery rule itself clears @code{hexflag}.
4839
4840 There may also be an error recovery rule that works within expressions.
4841 For example, there could be a rule which applies within parentheses
4842 and skips to the close-parenthesis:
4843
4844 @example
4845 @group
4846 expr: @dots{}
4847 | '(' expr ')'
4848 @{ $$ = $2; @}
4849 | '(' error ')'
4850 @dots{}
4851 @end group
4852 @end example
4853
4854 If this rule acts within the @code{hex} construct, it is not going to abort
4855 that construct (since it applies to an inner level of parentheses within
4856 the construct). Therefore, it should not clear the flag: the rest of
4857 the @code{hex} construct should be parsed with the flag still in effect.
4858
4859 What if there is an error recovery rule which might abort out of the
4860 @code{hex} construct or might not, depending on circumstances? There is no
4861 way you can write the action to determine whether a @code{hex} construct is
4862 being aborted or not. So if you are using a lexical tie-in, you had better
4863 make sure your error recovery rules are not of this kind. Each rule must
4864 be such that you can be sure that it always will, or always won't, have to
4865 clear the flag.
4866
4867 @node Debugging
4868 @chapter Debugging Your Parser
4869 @findex YYDEBUG
4870 @findex yydebug
4871 @cindex debugging
4872 @cindex tracing the parser
4873
4874 If a Bison grammar compiles properly but doesn't do what you want when it
4875 runs, the @code{yydebug} parser-trace feature can help you figure out why.
4876
4877 To enable compilation of trace facilities, you must define the macro
4878 @code{YYDEBUG} when you compile the parser. You could use
4879 @samp{-DYYDEBUG=1} as a compiler option or you could put @samp{#define
4880 YYDEBUG 1} in the C declarations section of the grammar file
4881 (@pxref{C Declarations, ,The C Declarations Section}). Alternatively, use the @samp{-t} option when
4882 you run Bison (@pxref{Invocation, ,Invoking Bison}). We always define @code{YYDEBUG} so that
4883 debugging is always possible.
4884
4885 The trace facility uses @code{stderr}, so you must add @w{@code{#include
4886 <stdio.h>}} to the C declarations section unless it is already there.
4887
4888 Once you have compiled the program with trace facilities, the way to
4889 request a trace is to store a nonzero value in the variable @code{yydebug}.
4890 You can do this by making the C code do it (in @code{main}, perhaps), or
4891 you can alter the value with a C debugger.
4892
4893 Each step taken by the parser when @code{yydebug} is nonzero produces a
4894 line or two of trace information, written on @code{stderr}. The trace
4895 messages tell you these things:
4896
4897 @itemize @bullet
4898 @item
4899 Each time the parser calls @code{yylex}, what kind of token was read.
4900
4901 @item
4902 Each time a token is shifted, the depth and complete contents of the
4903 state stack (@pxref{Parser States}).
4904
4905 @item
4906 Each time a rule is reduced, which rule it is, and the complete contents
4907 of the state stack afterward.
4908 @end itemize
4909
4910 To make sense of this information, it helps to refer to the listing file
4911 produced by the Bison @samp{-v} option (@pxref{Invocation, ,Invoking Bison}). This file
4912 shows the meaning of each state in terms of positions in various rules, and
4913 also what each state will do with each possible input token. As you read
4914 the successive trace messages, you can see that the parser is functioning
4915 according to its specification in the listing file. Eventually you will
4916 arrive at the place where something undesirable happens, and you will see
4917 which parts of the grammar are to blame.
4918
4919 The parser file is a C program and you can use C debuggers on it, but it's
4920 not easy to interpret what it is doing. The parser function is a
4921 finite-state machine interpreter, and aside from the actions it executes
4922 the same code over and over. Only the values of variables show where in
4923 the grammar it is working.
4924
4925 @findex YYPRINT
4926 The debugging information normally gives the token type of each token
4927 read, but not its semantic value. You can optionally define a macro
4928 named @code{YYPRINT} to provide a way to print the value. If you define
4929 @code{YYPRINT}, it should take three arguments. The parser will pass a
4930 standard I/O stream, the numeric code for the token type, and the token
4931 value (from @code{yylval}).
4932
4933 Here is an example of @code{YYPRINT} suitable for the multi-function
4934 calculator (@pxref{Mfcalc Decl, ,Declarations for @code{mfcalc}}):
4935
4936 @smallexample
4937 #define YYPRINT(file, type, value) yyprint (file, type, value)
4938
4939 static void
4940 yyprint (FILE *file, int type, YYSTYPE value)
4941 @{
4942 if (type == VAR)
4943 fprintf (file, " %s", value.tptr->name);
4944 else if (type == NUM)
4945 fprintf (file, " %d", value.val);
4946 @}
4947 @end smallexample
4948
4949 @node Invocation
4950 @chapter Invoking Bison
4951 @cindex invoking Bison
4952 @cindex Bison invocation
4953 @cindex options for invoking Bison
4954
4955 The usual way to invoke Bison is as follows:
4956
4957 @example
4958 bison @var{infile}
4959 @end example
4960
4961 Here @var{infile} is the grammar file name, which usually ends in
4962 @samp{.y}. The parser file's name is made by replacing the @samp{.y}
4963 with @samp{.tab.c}. Thus, the @samp{bison foo.y} filename yields
4964 @file{foo.tab.c}, and the @samp{bison hack/foo.y} filename yields
4965 @file{hack/foo.tab.c}. It's is also possible, in case you are writting
4966 C++ code instead of C in your grammar file, to name it @file{foo.ypp}
4967 or @file{foo.y++}. Then, the output files will take an extention like
4968 the given one as input (repectively @file{foo.tab.cpp} and @file{foo.tab.c++}).
4969 This feature takes effect with all options that manipulate filenames like
4970 @samp{-o} or @samp{-d}.
4971
4972 For example :
4973
4974 @example
4975 bison -d @var{infile.yxx}
4976 @end example
4977 @noindent
4978 will produce @file{infile.tab.cxx} and @file{infile.tab.hxx}. and
4979
4980 @example
4981 bison -d @var{infile.y} -o @var{output.c++}
4982 @end example
4983 @noindent
4984 will produce @file{output.c++} and @file{outfile.h++}.
4985
4986
4987 @menu
4988 * Bison Options:: All the options described in detail,
4989 in alphabetical order by short options.
4990 * Environment Variables:: Variables which affect Bison execution.
4991 * Option Cross Key:: Alphabetical list of long options.
4992 * VMS Invocation:: Bison command syntax on VMS.
4993 @end menu
4994
4995 @node Bison Options
4996 @section Bison Options
4997
4998 Bison supports both traditional single-letter options and mnemonic long
4999 option names. Long option names are indicated with @samp{--} instead of
5000 @samp{-}. Abbreviations for option names are allowed as long as they
5001 are unique. When a long option takes an argument, like
5002 @samp{--file-prefix}, connect the option name and the argument with
5003 @samp{=}.
5004
5005 Here is a list of options that can be used with Bison, alphabetized by
5006 short option. It is followed by a cross key alphabetized by long
5007 option.
5008
5009 @c Please, keep this ordered as in `bison --help'.
5010 @noindent
5011 Operations modes:
5012 @table @option
5013 @item -h
5014 @itemx --help
5015 Print a summary of the command-line options to Bison and exit.
5016
5017 @item -V
5018 @itemx --version
5019 Print the version number of Bison and exit.
5020
5021 @need 1750
5022 @item -y
5023 @itemx --yacc
5024 @itemx --fixed-output-files
5025 Equivalent to @samp{-o y.tab.c}; the parser output file is called
5026 @file{y.tab.c}, and the other outputs are called @file{y.output} and
5027 @file{y.tab.h}. The purpose of this option is to imitate Yacc's output
5028 file name conventions. Thus, the following shell script can substitute
5029 for Yacc:@refill
5030
5031 @example
5032 bison -y $*
5033 @end example
5034 @end table
5035
5036 @noindent
5037 Tuning the parser:
5038
5039 @table @option
5040 @item -S @var{file}
5041 @itemx --skeleton=@var{file}
5042 Specify the skeleton to use. You probably don't need this option unless
5043 you are developing Bison.
5044
5045 @item -t
5046 @itemx --debug
5047 Output a definition of the macro @code{YYDEBUG} into the parser file, so
5048 that the debugging facilities are compiled. @xref{Debugging, ,Debugging
5049 Your Parser}.
5050
5051 @item --locations
5052 Pretend that @code{%locactions} was specified. @xref{Decl Summary}.
5053
5054 @item -p @var{prefix}
5055 @itemx --name-prefix=@var{prefix}
5056 Rename the external symbols used in the parser so that they start with
5057 @var{prefix} instead of @samp{yy}. The precise list of symbols renamed
5058 is @code{yyparse}, @code{yylex}, @code{yyerror}, @code{yynerrs},
5059 @code{yylval}, @code{yychar} and @code{yydebug}.
5060
5061 For example, if you use @samp{-p c}, the names become @code{cparse},
5062 @code{clex}, and so on.
5063
5064 @xref{Multiple Parsers, ,Multiple Parsers in the Same Program}.
5065
5066 @item -l
5067 @itemx --no-lines
5068 Don't put any @code{#line} preprocessor commands in the parser file.
5069 Ordinarily Bison puts them in the parser file so that the C compiler
5070 and debuggers will associate errors with your source file, the
5071 grammar file. This option causes them to associate errors with the
5072 parser file, treating it as an independent source file in its own right.
5073
5074 @item -n
5075 @itemx --no-parser
5076 Pretend that @code{%no_parser} was specified. @xref{Decl Summary}.
5077
5078 @item -k
5079 @itemx --token-table
5080 Pretend that @code{%token_table} was specified. @xref{Decl Summary}.
5081 @end table
5082
5083 @noindent
5084 Adjust the output:
5085
5086 @table @option
5087 @item -d
5088 Pretend that @code{%verbose} was specified, i.e., write an extra output
5089 file containing macro definitions for the token type names defined in
5090 the grammar and the semantic value type @code{YYSTYPE}, as well as a few
5091 @code{extern} variable declarations. @xref{Decl Summary}.
5092
5093 @item --defines=@var{defines-file}
5094 The behaviour of @var{--defines} is the same than @samp{-d}. The only
5095 difference is that it has an optionnal argument which is the name of
5096 the output filename.
5097
5098 @item -b @var{file-prefix}
5099 @itemx --file-prefix=@var{prefix}
5100 Specify a prefix to use for all Bison output file names. The names are
5101 chosen as if the input file were named @file{@var{prefix}.c}.
5102
5103 @item -v
5104 @itemx --verbose
5105 Pretend that @code{%verbose} was specified, i.e, write an extra output
5106 file containing verbose descriptions of the grammar and
5107 parser. @xref{Decl Summary}, for more.
5108
5109 @item -o @var{outfile}
5110 @itemx --output-file=@var{outfile}
5111 Specify the name @var{outfile} for the parser file.
5112
5113 The other output files' names are constructed from @var{outfile}
5114 as described under the @samp{-v} and @samp{-d} options.
5115
5116 @item -g
5117 Output a VCG definition of the LALR(1) grammar automaton computed by
5118 Bison. If the grammar file is @file{foo.y}, the VCG output file will
5119 be @file{foo.vcg}.
5120
5121 @item --graph=@var{graph-file}
5122 The behaviour of @var{--graph} is the same than @samp{-g}. The only
5123 difference is that it has an optionnal argument which is the name of
5124 the output graph filename.
5125 @end table
5126
5127 @node Environment Variables
5128 @section Environment Variables
5129 @cindex environment variables
5130 @cindex BISON_HAIRY
5131 @cindex BISON_SIMPLE
5132
5133 Here is a list of environment variables which affect the way Bison
5134 runs.
5135
5136 @table @samp
5137 @item BISON_SIMPLE
5138 @itemx BISON_HAIRY
5139 Much of the parser generated by Bison is copied verbatim from a file
5140 called @file{bison.simple}. If Bison cannot find that file, or if you
5141 would like to direct Bison to use a different copy, setting the
5142 environment variable @code{BISON_SIMPLE} to the path of the file will
5143 cause Bison to use that copy instead.
5144
5145 When the @samp{%semantic_parser} declaration is used, Bison copies from
5146 a file called @file{bison.hairy} instead. The location of this file can
5147 also be specified or overridden in a similar fashion, with the
5148 @code{BISON_HAIRY} environment variable.
5149
5150 @end table
5151
5152 @node Option Cross Key
5153 @section Option Cross Key
5154
5155 Here is a list of options, alphabetized by long option, to help you find
5156 the corresponding short option.
5157
5158 @tex
5159 \def\leaderfill{\leaders\hbox to 1em{\hss.\hss}\hfill}
5160
5161 {\tt
5162 \line{ --debug \leaderfill -t}
5163 \line{ --defines \leaderfill -d}
5164 \line{ --file-prefix \leaderfill -b}
5165 \line{ --fixed-output-files \leaderfill -y}
5166 \line{ --graph \leaderfill -g}
5167 \line{ --help \leaderfill -h}
5168 \line{ --name-prefix \leaderfill -p}
5169 \line{ --no-lines \leaderfill -l}
5170 \line{ --no-parser \leaderfill -n}
5171 \line{ --output-file \leaderfill -o}
5172 \line{ --token-table \leaderfill -k}
5173 \line{ --verbose \leaderfill -v}
5174 \line{ --version \leaderfill -V}
5175 \line{ --yacc \leaderfill -y}
5176 }
5177 @end tex
5178
5179 @ifinfo
5180 @example
5181 --debug -t
5182 --defines=@var{defines-file} -d
5183 --file-prefix=@var{prefix} -b @var{file-prefix}
5184 --fixed-output-files --yacc -y
5185 --graph=@var{graph-file} -d
5186 --help -h
5187 --name-prefix=@var{prefix} -p @var{name-prefix}
5188 --no-lines -l
5189 --no-parser -n
5190 --output-file=@var{outfile} -o @var{outfile}
5191 --token-table -k
5192 --verbose -v
5193 --version -V
5194 @end example
5195 @end ifinfo
5196
5197 @node VMS Invocation
5198 @section Invoking Bison under VMS
5199 @cindex invoking Bison under VMS
5200 @cindex VMS
5201
5202 The command line syntax for Bison on VMS is a variant of the usual
5203 Bison command syntax---adapted to fit VMS conventions.
5204
5205 To find the VMS equivalent for any Bison option, start with the long
5206 option, and substitute a @samp{/} for the leading @samp{--}, and
5207 substitute a @samp{_} for each @samp{-} in the name of the long option.
5208 For example, the following invocation under VMS:
5209
5210 @example
5211 bison /debug/name_prefix=bar foo.y
5212 @end example
5213
5214 @noindent
5215 is equivalent to the following command under POSIX.
5216
5217 @example
5218 bison --debug --name-prefix=bar foo.y
5219 @end example
5220
5221 The VMS file system does not permit filenames such as
5222 @file{foo.tab.c}. In the above example, the output file
5223 would instead be named @file{foo_tab.c}.
5224
5225 @node Table of Symbols
5226 @appendix Bison Symbols
5227 @cindex Bison symbols, table of
5228 @cindex symbols in Bison, table of
5229
5230 @table @code
5231 @item error
5232 A token name reserved for error recovery. This token may be used in
5233 grammar rules so as to allow the Bison parser to recognize an error in
5234 the grammar without halting the process. In effect, a sentence
5235 containing an error may be recognized as valid. On a parse error, the
5236 token @code{error} becomes the current look-ahead token. Actions
5237 corresponding to @code{error} are then executed, and the look-ahead
5238 token is reset to the token that originally caused the violation.
5239 @xref{Error Recovery}.
5240
5241 @item YYABORT
5242 Macro to pretend that an unrecoverable syntax error has occurred, by
5243 making @code{yyparse} return 1 immediately. The error reporting
5244 function @code{yyerror} is not called. @xref{Parser Function, ,The
5245 Parser Function @code{yyparse}}.
5246
5247 @item YYACCEPT
5248 Macro to pretend that a complete utterance of the language has been
5249 read, by making @code{yyparse} return 0 immediately.
5250 @xref{Parser Function, ,The Parser Function @code{yyparse}}.
5251
5252 @item YYBACKUP
5253 Macro to discard a value from the parser stack and fake a look-ahead
5254 token. @xref{Action Features, ,Special Features for Use in Actions}.
5255
5256 @item YYERROR
5257 Macro to pretend that a syntax error has just been detected: call
5258 @code{yyerror} and then perform normal error recovery if possible
5259 (@pxref{Error Recovery}), or (if recovery is impossible) make
5260 @code{yyparse} return 1. @xref{Error Recovery}.
5261
5262 @item YYERROR_VERBOSE
5263 Macro that you define with @code{#define} in the Bison declarations
5264 section to request verbose, specific error message strings when
5265 @code{yyerror} is called.
5266
5267 @item YYINITDEPTH
5268 Macro for specifying the initial size of the parser stack.
5269 @xref{Stack Overflow}.
5270
5271 @item YYLEX_PARAM
5272 Macro for specifying an extra argument (or list of extra arguments) for
5273 @code{yyparse} to pass to @code{yylex}. @xref{Pure Calling,, Calling
5274 Conventions for Pure Parsers}.
5275
5276 @item YYLTYPE
5277 Macro for the data type of @code{yylloc}; a structure with four
5278 members. @xref{Location Type, , Data Types of Locations}.
5279
5280 @item yyltype
5281 Default value for YYLTYPE.
5282
5283 @item YYMAXDEPTH
5284 Macro for specifying the maximum size of the parser stack.
5285 @xref{Stack Overflow}.
5286
5287 @item YYPARSE_PARAM
5288 Macro for specifying the name of a parameter that @code{yyparse} should
5289 accept. @xref{Pure Calling,, Calling Conventions for Pure Parsers}.
5290
5291 @item YYRECOVERING
5292 Macro whose value indicates whether the parser is recovering from a
5293 syntax error. @xref{Action Features, ,Special Features for Use in Actions}.
5294
5295 @item YYSTACK_USE_ALLOCA
5296 Macro used to control the use of @code{alloca}. If defined to @samp{0},
5297 the parser will not use @code{alloca} but @code{malloc} when trying to
5298 grow its internal stacks. Do @emph{not} define @code{YYSTACK_USE_ALLOCA}
5299 to anything else.
5300
5301 @item YYSTYPE
5302 Macro for the data type of semantic values; @code{int} by default.
5303 @xref{Value Type, ,Data Types of Semantic Values}.
5304
5305 @item yychar
5306 External integer variable that contains the integer value of the current
5307 look-ahead token. (In a pure parser, it is a local variable within
5308 @code{yyparse}.) Error-recovery rule actions may examine this variable.
5309 @xref{Action Features, ,Special Features for Use in Actions}.
5310
5311 @item yyclearin
5312 Macro used in error-recovery rule actions. It clears the previous
5313 look-ahead token. @xref{Error Recovery}.
5314
5315 @item yydebug
5316 External integer variable set to zero by default. If @code{yydebug}
5317 is given a nonzero value, the parser will output information on input
5318 symbols and parser action. @xref{Debugging, ,Debugging Your Parser}.
5319
5320 @item yyerrok
5321 Macro to cause parser to recover immediately to its normal mode
5322 after a parse error. @xref{Error Recovery}.
5323
5324 @item yyerror
5325 User-supplied function to be called by @code{yyparse} on error. The
5326 function receives one argument, a pointer to a character string
5327 containing an error message. @xref{Error Reporting, ,The Error
5328 Reporting Function @code{yyerror}}.
5329
5330 @item yylex
5331 User-supplied lexical analyzer function, called with no arguments
5332 to get the next token. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
5333
5334 @item yylval
5335 External variable in which @code{yylex} should place the semantic
5336 value associated with a token. (In a pure parser, it is a local
5337 variable within @code{yyparse}, and its address is passed to
5338 @code{yylex}.) @xref{Token Values, ,Semantic Values of Tokens}.
5339
5340 @item yylloc
5341 External variable in which @code{yylex} should place the line and column
5342 numbers associated with a token. (In a pure parser, it is a local
5343 variable within @code{yyparse}, and its address is passed to
5344 @code{yylex}.) You can ignore this variable if you don't use the
5345 @samp{@@} feature in the grammar actions. @xref{Token Positions,
5346 ,Textual Positions of Tokens}.
5347
5348 @item yynerrs
5349 Global variable which Bison increments each time there is a parse error.
5350 (In a pure parser, it is a local variable within @code{yyparse}.)
5351 @xref{Error Reporting, ,The Error Reporting Function @code{yyerror}}.
5352
5353 @item yyparse
5354 The parser function produced by Bison; call this function to start
5355 parsing. @xref{Parser Function, ,The Parser Function @code{yyparse}}.
5356
5357 @item %debug
5358 Equip the parser for debugging. @xref{Decl Summary}.
5359
5360 @item %defines
5361 Bison declaration to create a header file meant for the scanner.
5362 @xref{Decl Summary}.
5363
5364 @c @item %source_extension
5365 @c Bison declaration to specify the generated parser output file extension.
5366 @c @xref{Decl Summary}.
5367 @c
5368 @c @item %header_extension
5369 @c Bison declaration to specify the generated parser header file extension
5370 @c if required. @xref{Decl Summary}.
5371
5372 @item %left
5373 Bison declaration to assign left associativity to token(s).
5374 @xref{Precedence Decl, ,Operator Precedence}.
5375
5376 @item %no_lines
5377 Bison declaration to avoid generating @code{#line} directives in the
5378 parser file. @xref{Decl Summary}.
5379
5380 @item %nonassoc
5381 Bison declaration to assign non-associativity to token(s).
5382 @xref{Precedence Decl, ,Operator Precedence}.
5383
5384 @item %prec
5385 Bison declaration to assign a precedence to a specific rule.
5386 @xref{Contextual Precedence, ,Context-Dependent Precedence}.
5387
5388 @item %pure_parser
5389 Bison declaration to request a pure (reentrant) parser.
5390 @xref{Pure Decl, ,A Pure (Reentrant) Parser}.
5391
5392 @item %right
5393 Bison declaration to assign right associativity to token(s).
5394 @xref{Precedence Decl, ,Operator Precedence}.
5395
5396 @item %start
5397 Bison declaration to specify the start symbol. @xref{Start Decl, ,The Start-Symbol}.
5398
5399 @item %token
5400 Bison declaration to declare token(s) without specifying precedence.
5401 @xref{Token Decl, ,Token Type Names}.
5402
5403 @item %token_table
5404 Bison declaration to include a token name table in the parser file.
5405 @xref{Decl Summary}.
5406
5407 @item %type
5408 Bison declaration to declare nonterminals. @xref{Type Decl, ,Nonterminal Symbols}.
5409
5410 @item %union
5411 Bison declaration to specify several possible data types for semantic
5412 values. @xref{Union Decl, ,The Collection of Value Types}.
5413 @end table
5414
5415 These are the punctuation and delimiters used in Bison input:
5416
5417 @table @samp
5418 @item %%
5419 Delimiter used to separate the grammar rule section from the
5420 Bison declarations section or the additional C code section.
5421 @xref{Grammar Layout, ,The Overall Layout of a Bison Grammar}.
5422
5423 @item %@{ %@}
5424 All code listed between @samp{%@{} and @samp{%@}} is copied directly to
5425 the output file uninterpreted. Such code forms the ``C declarations''
5426 section of the input file. @xref{Grammar Outline, ,Outline of a Bison
5427 Grammar}.
5428
5429 @item /*@dots{}*/
5430 Comment delimiters, as in C.
5431
5432 @item :
5433 Separates a rule's result from its components. @xref{Rules, ,Syntax of
5434 Grammar Rules}.
5435
5436 @item ;
5437 Terminates a rule. @xref{Rules, ,Syntax of Grammar Rules}.
5438
5439 @item |
5440 Separates alternate rules for the same result nonterminal.
5441 @xref{Rules, ,Syntax of Grammar Rules}.
5442 @end table
5443
5444 @node Glossary
5445 @appendix Glossary
5446 @cindex glossary
5447
5448 @table @asis
5449 @item Backus-Naur Form (BNF)
5450 Formal method of specifying context-free grammars. BNF was first used
5451 in the @cite{ALGOL-60} report, 1963. @xref{Language and Grammar,
5452 ,Languages and Context-Free Grammars}.
5453
5454 @item Context-free grammars
5455 Grammars specified as rules that can be applied regardless of context.
5456 Thus, if there is a rule which says that an integer can be used as an
5457 expression, integers are allowed @emph{anywhere} an expression is
5458 permitted. @xref{Language and Grammar, ,Languages and Context-Free
5459 Grammars}.
5460
5461 @item Dynamic allocation
5462 Allocation of memory that occurs during execution, rather than at
5463 compile time or on entry to a function.
5464
5465 @item Empty string
5466 Analogous to the empty set in set theory, the empty string is a
5467 character string of length zero.
5468
5469 @item Finite-state stack machine
5470 A ``machine'' that has discrete states in which it is said to exist at
5471 each instant in time. As input to the machine is processed, the
5472 machine moves from state to state as specified by the logic of the
5473 machine. In the case of the parser, the input is the language being
5474 parsed, and the states correspond to various stages in the grammar
5475 rules. @xref{Algorithm, ,The Bison Parser Algorithm }.
5476
5477 @item Grouping
5478 A language construct that is (in general) grammatically divisible;
5479 for example, `expression' or `declaration' in C.
5480 @xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5481
5482 @item Infix operator
5483 An arithmetic operator that is placed between the operands on which it
5484 performs some operation.
5485
5486 @item Input stream
5487 A continuous flow of data between devices or programs.
5488
5489 @item Language construct
5490 One of the typical usage schemas of the language. For example, one of
5491 the constructs of the C language is the @code{if} statement.
5492 @xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5493
5494 @item Left associativity
5495 Operators having left associativity are analyzed from left to right:
5496 @samp{a+b+c} first computes @samp{a+b} and then combines with
5497 @samp{c}. @xref{Precedence, ,Operator Precedence}.
5498
5499 @item Left recursion
5500 A rule whose result symbol is also its first component symbol; for
5501 example, @samp{expseq1 : expseq1 ',' exp;}. @xref{Recursion, ,Recursive
5502 Rules}.
5503
5504 @item Left-to-right parsing
5505 Parsing a sentence of a language by analyzing it token by token from
5506 left to right. @xref{Algorithm, ,The Bison Parser Algorithm }.
5507
5508 @item Lexical analyzer (scanner)
5509 A function that reads an input stream and returns tokens one by one.
5510 @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
5511
5512 @item Lexical tie-in
5513 A flag, set by actions in the grammar rules, which alters the way
5514 tokens are parsed. @xref{Lexical Tie-ins}.
5515
5516 @item Literal string token
5517 A token which consists of two or more fixed characters. @xref{Symbols}.
5518
5519 @item Look-ahead token
5520 A token already read but not yet shifted. @xref{Look-Ahead, ,Look-Ahead
5521 Tokens}.
5522
5523 @item LALR(1)
5524 The class of context-free grammars that Bison (like most other parser
5525 generators) can handle; a subset of LR(1). @xref{Mystery Conflicts, ,
5526 Mysterious Reduce/Reduce Conflicts}.
5527
5528 @item LR(1)
5529 The class of context-free grammars in which at most one token of
5530 look-ahead is needed to disambiguate the parsing of any piece of input.
5531
5532 @item Nonterminal symbol
5533 A grammar symbol standing for a grammatical construct that can
5534 be expressed through rules in terms of smaller constructs; in other
5535 words, a construct that is not a token. @xref{Symbols}.
5536
5537 @item Parse error
5538 An error encountered during parsing of an input stream due to invalid
5539 syntax. @xref{Error Recovery}.
5540
5541 @item Parser
5542 A function that recognizes valid sentences of a language by analyzing
5543 the syntax structure of a set of tokens passed to it from a lexical
5544 analyzer.
5545
5546 @item Postfix operator
5547 An arithmetic operator that is placed after the operands upon which it
5548 performs some operation.
5549
5550 @item Reduction
5551 Replacing a string of nonterminals and/or terminals with a single
5552 nonterminal, according to a grammar rule. @xref{Algorithm, ,The Bison
5553 Parser Algorithm }.
5554
5555 @item Reentrant
5556 A reentrant subprogram is a subprogram which can be in invoked any
5557 number of times in parallel, without interference between the various
5558 invocations. @xref{Pure Decl, ,A Pure (Reentrant) Parser}.
5559
5560 @item Reverse polish notation
5561 A language in which all operators are postfix operators.
5562
5563 @item Right recursion
5564 A rule whose result symbol is also its last component symbol; for
5565 example, @samp{expseq1: exp ',' expseq1;}. @xref{Recursion, ,Recursive
5566 Rules}.
5567
5568 @item Semantics
5569 In computer languages, the semantics are specified by the actions
5570 taken for each instance of the language, i.e., the meaning of
5571 each statement. @xref{Semantics, ,Defining Language Semantics}.
5572
5573 @item Shift
5574 A parser is said to shift when it makes the choice of analyzing
5575 further input from the stream rather than reducing immediately some
5576 already-recognized rule. @xref{Algorithm, ,The Bison Parser Algorithm }.
5577
5578 @item Single-character literal
5579 A single character that is recognized and interpreted as is.
5580 @xref{Grammar in Bison, ,From Formal Rules to Bison Input}.
5581
5582 @item Start symbol
5583 The nonterminal symbol that stands for a complete valid utterance in
5584 the language being parsed. The start symbol is usually listed as the
5585 first nonterminal symbol in a language specification.
5586 @xref{Start Decl, ,The Start-Symbol}.
5587
5588 @item Symbol table
5589 A data structure where symbol names and associated data are stored
5590 during parsing to allow for recognition and use of existing
5591 information in repeated uses of a symbol. @xref{Multi-function Calc}.
5592
5593 @item Token
5594 A basic, grammatically indivisible unit of a language. The symbol
5595 that describes a token in the grammar is a terminal symbol.
5596 The input of the Bison parser is a stream of tokens which comes from
5597 the lexical analyzer. @xref{Symbols}.
5598
5599 @item Terminal symbol
5600 A grammar symbol that has no rules in the grammar and therefore is
5601 grammatically indivisible. The piece of text it represents is a token.
5602 @xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5603 @end table
5604
5605 @node Copying This Manual
5606 @appendix Copying This Manual
5607
5608 @menu
5609 * GNU Free Documentation License:: License for copying this manual.
5610 @end menu
5611
5612 @include fdl.texi
5613
5614 @node Index
5615 @unnumbered Index
5616
5617 @printindex cp
5618
5619 @bye