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