1 \input texinfo @c -*-texinfo-*-
2 @comment %**start of header
3 @setfilename bison.info
5 @settitle Bison @value{VERSION}
13 @c This edition has been formatted so that you can format and print it in
14 @c the smallbook format.
17 @c Set following if you have the new `shorttitlepage' command
18 @c @clear shorttitlepage-enabled
19 @c @set shorttitlepage-enabled
21 @c ISPELL CHECK: done, 14 Jan 1993 --bob
23 @c Check COPYRIGHT dates. should be updated in the titlepage, ifinfo
24 @c titlepage; should NOT be changed in the GPL. --mew
36 @comment %**end of header
41 * bison: (bison). GNU Project parser generator (yacc replacement).
47 This file documents the Bison parser generator.
49 Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998, 1999,
51 Free Software Foundation, Inc.
53 Permission is granted to make and distribute verbatim copies of
54 this manual provided the copyright notice and this permission notice
55 are preserved on all copies.
58 Permission is granted to process this file through Tex and print the
59 results, provided the printed document carries copying permission
60 notice identical to this one except for the removal of this paragraph
61 (this paragraph not being relevant to the printed manual).
64 Permission is granted to copy and distribute modified versions of this
65 manual under the conditions for verbatim copying, provided also that the
66 sections entitled ``GNU General Public License'' and ``Conditions for
67 Using Bison'' are included exactly as in the original, and provided that
68 the entire resulting derived work is distributed under the terms of a
69 permission notice identical to this one.
71 Permission is granted to copy and distribute translations of this manual
72 into another language, under the above conditions for modified versions,
73 except that the sections entitled ``GNU General Public License'',
74 ``Conditions for Using Bison'' and this permission notice may be
75 included in translations approved by the Free Software Foundation
76 instead of in the original English.
79 @ifset shorttitlepage-enabled
84 @subtitle The YACC-compatible Parser Generator
85 @subtitle @value{UPDATED}, Bison Version @value{VERSION}
87 @author by Charles Donnelly and Richard Stallman
90 @vskip 0pt plus 1filll
91 Copyright @copyright{} 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998,
93 Free Software Foundation, Inc.
96 Published by the Free Software Foundation @*
97 59 Temple Place, Suite 330 @*
98 Boston, MA 02111-1307 USA @*
99 Printed copies are available from the Free Software Foundation.@*
102 Permission is granted to make and distribute verbatim copies of
103 this manual provided the copyright notice and this permission notice
104 are preserved on all copies.
107 Permission is granted to process this file through TeX and print the
108 results, provided the printed document carries copying permission
109 notice identical to this one except for the removal of this paragraph
110 (this paragraph not being relevant to the printed manual).
113 Permission is granted to copy and distribute modified versions of this
114 manual under the conditions for verbatim copying, provided also that the
115 sections entitled ``GNU General Public License'' and ``Conditions for
116 Using Bison'' are included exactly as in the original, and provided that
117 the entire resulting derived work is distributed under the terms of a
118 permission notice identical to this one.
120 Permission is granted to copy and distribute translations of this manual
121 into another language, under the above conditions for modified versions,
122 except that the sections entitled ``GNU General Public License'',
123 ``Conditions for Using Bison'' and this permission notice may be
124 included in translations approved by the Free Software Foundation
125 instead of in the original English.
127 Cover art by Etienne Suvasa.
136 This manual documents version @value{VERSION} of Bison, updated
143 * Copying:: The GNU General Public License says
144 how you can copy and share Bison
147 * Concepts:: Basic concepts for understanding Bison.
148 * Examples:: Three simple explained examples of using Bison.
151 * Grammar File:: Writing Bison declarations and rules.
152 * Interface:: C-language interface to the parser function @code{yyparse}.
153 * Algorithm:: How the Bison parser works at run-time.
154 * Error Recovery:: Writing rules for error recovery.
155 * Context Dependency:: What to do if your language syntax is too
156 messy for Bison to handle straightforwardly.
157 * Debugging:: Debugging Bison parsers that parse wrong.
158 * Invocation:: How to run Bison (to produce the parser source file).
159 * Table of Symbols:: All the keywords of the Bison language are explained.
160 * Glossary:: Basic concepts are explained.
161 * Copying This Manual:: License for copying this manual.
162 * Index:: Cross-references to the text.
164 @detailmenu --- The Detailed Node Listing ---
166 The Concepts of Bison
168 * Language and Grammar:: Languages and context-free grammars,
169 as mathematical ideas.
170 * Grammar in Bison:: How we represent grammars for Bison's sake.
171 * Semantic Values:: Each token or syntactic grouping can have
172 a semantic value (the value of an integer,
173 the name of an identifier, etc.).
174 * Semantic Actions:: Each rule can have an action containing C code.
175 * Bison Parser:: What are Bison's input and output,
176 how is the output used?
177 * Stages:: Stages in writing and running Bison grammars.
178 * Grammar Layout:: Overall structure of a Bison grammar file.
182 * RPN Calc:: Reverse polish notation calculator;
183 a first example with no operator precedence.
184 * Infix Calc:: Infix (algebraic) notation calculator.
185 Operator precedence is introduced.
186 * Simple Error Recovery:: Continuing after syntax errors.
187 * Location Tracking Calc:: Demonstrating the use of @@@var{n} and @@$.
188 * Multi-function Calc:: Calculator with memory and trig functions.
189 It uses multiple data-types for semantic values.
190 * Exercises:: Ideas for improving the multi-function calculator.
192 Reverse Polish Notation Calculator
194 * Decls: Rpcalc Decls. Prologue (declarations) for rpcalc.
195 * Rules: Rpcalc Rules. Grammar Rules for rpcalc, with explanation.
196 * Lexer: Rpcalc Lexer. The lexical analyzer.
197 * Main: Rpcalc Main. The controlling function.
198 * Error: Rpcalc Error. The error reporting function.
199 * Gen: Rpcalc Gen. Running Bison on the grammar file.
200 * Comp: Rpcalc Compile. Run the C compiler on the output code.
202 Grammar Rules for @code{rpcalc}
208 Location Tracking Calculator: @code{ltcalc}
210 * Decls: Ltcalc Decls. Bison and C declarations for ltcalc.
211 * Rules: Ltcalc Rules. Grammar rules for ltcalc, with explanations.
212 * Lexer: Ltcalc Lexer. The lexical analyzer.
214 Multi-Function Calculator: @code{mfcalc}
216 * Decl: Mfcalc Decl. Bison declarations for multi-function calculator.
217 * Rules: Mfcalc Rules. Grammar rules for the calculator.
218 * Symtab: Mfcalc Symtab. Symbol table management subroutines.
222 * Grammar Outline:: Overall layout of the grammar file.
223 * Symbols:: Terminal and nonterminal symbols.
224 * Rules:: How to write grammar rules.
225 * Recursion:: Writing recursive rules.
226 * Semantics:: Semantic values and actions.
227 * Declarations:: All kinds of Bison declarations are described here.
228 * Multiple Parsers:: Putting more than one Bison parser in one program.
230 Outline of a Bison Grammar
232 * Prologue:: Syntax and usage of the prologue (declarations section).
233 * Bison Declarations:: Syntax and usage of the Bison declarations section.
234 * Grammar Rules:: Syntax and usage of the grammar rules section.
235 * Epilogue:: Syntax and usage of the epilogue (additional code section).
237 Defining Language Semantics
239 * Value Type:: Specifying one data type for all semantic values.
240 * Multiple Types:: Specifying several alternative data types.
241 * Actions:: An action is the semantic definition of a grammar rule.
242 * Action Types:: Specifying data types for actions to operate on.
243 * Mid-Rule Actions:: Most actions go at the end of a rule.
244 This says when, why and how to use the exceptional
245 action in the middle of a rule.
249 * Token Decl:: Declaring terminal symbols.
250 * Precedence Decl:: Declaring terminals with precedence and associativity.
251 * Union Decl:: Declaring the set of all semantic value types.
252 * Type Decl:: Declaring the choice of type for a nonterminal symbol.
253 * Expect Decl:: Suppressing warnings about shift/reduce conflicts.
254 * Start Decl:: Specifying the start symbol.
255 * Pure Decl:: Requesting a reentrant parser.
256 * Decl Summary:: Table of all Bison declarations.
258 Parser C-Language Interface
260 * Parser Function:: How to call @code{yyparse} and what it returns.
261 * Lexical:: You must supply a function @code{yylex}
263 * Error Reporting:: You must supply a function @code{yyerror}.
264 * Action Features:: Special features for use in actions.
266 The Lexical Analyzer Function @code{yylex}
268 * Calling Convention:: How @code{yyparse} calls @code{yylex}.
269 * Token Values:: How @code{yylex} must return the semantic value
270 of the token it has read.
271 * Token Positions:: How @code{yylex} must return the text position
272 (line number, etc.) of the token, if the
274 * Pure Calling:: How the calling convention differs
275 in a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}).
277 The Bison Parser Algorithm
279 * Look-Ahead:: Parser looks one token ahead when deciding what to do.
280 * Shift/Reduce:: Conflicts: when either shifting or reduction is valid.
281 * Precedence:: Operator precedence works by resolving conflicts.
282 * Contextual Precedence:: When an operator's precedence depends on context.
283 * Parser States:: The parser is a finite-state-machine with stack.
284 * Reduce/Reduce:: When two rules are applicable in the same situation.
285 * Mystery Conflicts:: Reduce/reduce conflicts that look unjustified.
286 * Stack Overflow:: What happens when stack gets full. How to avoid it.
290 * Why Precedence:: An example showing why precedence is needed.
291 * Using Precedence:: How to specify precedence in Bison grammars.
292 * Precedence Examples:: How these features are used in the previous example.
293 * How Precedence:: How they work.
295 Handling Context Dependencies
297 * Semantic Tokens:: Token parsing can depend on the semantic context.
298 * Lexical Tie-ins:: Token parsing can depend on the syntactic context.
299 * Tie-in Recovery:: Lexical tie-ins have implications for how
300 error recovery rules must be written.
304 * Bison Options:: All the options described in detail,
305 in alphabetical order by short options.
306 * Option Cross Key:: Alphabetical list of long options.
307 * VMS Invocation:: Bison command syntax on VMS.
311 * GNU Free Documentation License:: License for copying this manual.
317 @unnumbered Introduction
320 @dfn{Bison} is a general-purpose parser generator that converts a
321 grammar description for an LALR(1) context-free grammar into a C
322 program to parse that grammar. Once you are proficient with Bison,
323 you may use it to develop a wide range of language parsers, from those
324 used in simple desk calculators to complex programming languages.
326 Bison is upward compatible with Yacc: all properly-written Yacc grammars
327 ought to work with Bison with no change. Anyone familiar with Yacc
328 should be able to use Bison with little trouble. You need to be fluent in
329 C programming in order to use Bison or to understand this manual.
331 We begin with tutorial chapters that explain the basic concepts of using
332 Bison and show three explained examples, each building on the last. If you
333 don't know Bison or Yacc, start by reading these chapters. Reference
334 chapters follow which describe specific aspects of Bison in detail.
336 Bison was written primarily by Robert Corbett; Richard Stallman made it
337 Yacc-compatible. Wilfred Hansen of Carnegie Mellon University added
338 multi-character string literals and other features.
340 This edition corresponds to version @value{VERSION} of Bison.
343 @unnumbered Conditions for Using Bison
345 As of Bison version 1.24, we have changed the distribution terms for
346 @code{yyparse} to permit using Bison's output in nonfree programs.
347 Formerly, Bison parsers could be used only in programs that were free
350 The other GNU programming tools, such as the GNU C compiler, have never
351 had such a requirement. They could always be used for nonfree
352 software. The reason Bison was different was not due to a special
353 policy decision; it resulted from applying the usual General Public
354 License to all of the Bison source code.
356 The output of the Bison utility---the Bison parser file---contains a
357 verbatim copy of a sizable piece of Bison, which is the code for the
358 @code{yyparse} function. (The actions from your grammar are inserted
359 into this function at one point, but the rest of the function is not
360 changed.) When we applied the GPL terms to the code for @code{yyparse},
361 the effect was to restrict the use of Bison output to free software.
363 We didn't change the terms because of sympathy for people who want to
364 make software proprietary. @strong{Software should be free.} But we
365 concluded that limiting Bison's use to free software was doing little to
366 encourage people to make other software free. So we decided to make the
367 practical conditions for using Bison match the practical conditions for
368 using the other GNU tools.
373 @chapter The Concepts of Bison
375 This chapter introduces many of the basic concepts without which the
376 details of Bison will not make sense. If you do not already know how to
377 use Bison or Yacc, we suggest you start by reading this chapter carefully.
380 * Language and Grammar:: Languages and context-free grammars,
381 as mathematical ideas.
382 * Grammar in Bison:: How we represent grammars for Bison's sake.
383 * Semantic Values:: Each token or syntactic grouping can have
384 a semantic value (the value of an integer,
385 the name of an identifier, etc.).
386 * Semantic Actions:: Each rule can have an action containing C code.
387 * Locations Overview:: Tracking Locations.
388 * Bison Parser:: What are Bison's input and output,
389 how is the output used?
390 * Stages:: Stages in writing and running Bison grammars.
391 * Grammar Layout:: Overall structure of a Bison grammar file.
394 @node Language and Grammar
395 @section Languages and Context-Free Grammars
397 @cindex context-free grammar
398 @cindex grammar, context-free
399 In order for Bison to parse a language, it must be described by a
400 @dfn{context-free grammar}. This means that you specify one or more
401 @dfn{syntactic groupings} and give rules for constructing them from their
402 parts. For example, in the C language, one kind of grouping is called an
403 `expression'. One rule for making an expression might be, ``An expression
404 can be made of a minus sign and another expression''. Another would be,
405 ``An expression can be an integer''. As you can see, rules are often
406 recursive, but there must be at least one rule which leads out of the
410 @cindex Backus-Naur form
411 The most common formal system for presenting such rules for humans to read
412 is @dfn{Backus-Naur Form} or ``BNF'', which was developed in order to
413 specify the language Algol 60. Any grammar expressed in BNF is a
414 context-free grammar. The input to Bison is essentially machine-readable
417 Not all context-free languages can be handled by Bison, only those
418 that are LALR(1). In brief, this means that it must be possible to
419 tell how to parse any portion of an input string with just a single
420 token of look-ahead. Strictly speaking, that is a description of an
421 LR(1) grammar, and LALR(1) involves additional restrictions that are
422 hard to explain simply; but it is rare in actual practice to find an
423 LR(1) grammar that fails to be LALR(1). @xref{Mystery Conflicts, ,
424 Mysterious Reduce/Reduce Conflicts}, for more information on this.
426 @cindex symbols (abstract)
428 @cindex syntactic grouping
429 @cindex grouping, syntactic
430 In the formal grammatical rules for a language, each kind of syntactic unit
431 or grouping is named by a @dfn{symbol}. Those which are built by grouping
432 smaller constructs according to grammatical rules are called
433 @dfn{nonterminal symbols}; those which can't be subdivided are called
434 @dfn{terminal symbols} or @dfn{token types}. We call a piece of input
435 corresponding to a single terminal symbol a @dfn{token}, and a piece
436 corresponding to a single nonterminal symbol a @dfn{grouping}.@refill
438 We can use the C language as an example of what symbols, terminal and
439 nonterminal, mean. The tokens of C are identifiers, constants (numeric and
440 string), and the various keywords, arithmetic operators and punctuation
441 marks. So the terminal symbols of a grammar for C include `identifier',
442 `number', `string', plus one symbol for each keyword, operator or
443 punctuation mark: `if', `return', `const', `static', `int', `char',
444 `plus-sign', `open-brace', `close-brace', `comma' and many more. (These
445 tokens can be subdivided into characters, but that is a matter of
446 lexicography, not grammar.)
448 Here is a simple C function subdivided into tokens:
452 int /* @r{keyword `int'} */
453 square (int x) /* @r{identifier, open-paren, identifier,}
454 @r{identifier, close-paren} */
455 @{ /* @r{open-brace} */
456 return x * x; /* @r{keyword `return', identifier, asterisk,
457 identifier, semicolon} */
458 @} /* @r{close-brace} */
463 int /* @r{keyword `int'} */
464 square (int x) /* @r{identifier, open-paren, identifier, identifier, close-paren} */
465 @{ /* @r{open-brace} */
466 return x * x; /* @r{keyword `return', identifier, asterisk, identifier, semicolon} */
467 @} /* @r{close-brace} */
471 The syntactic groupings of C include the expression, the statement, the
472 declaration, and the function definition. These are represented in the
473 grammar of C by nonterminal symbols `expression', `statement',
474 `declaration' and `function definition'. The full grammar uses dozens of
475 additional language constructs, each with its own nonterminal symbol, in
476 order to express the meanings of these four. The example above is a
477 function definition; it contains one declaration, and one statement. In
478 the statement, each @samp{x} is an expression and so is @samp{x * x}.
480 Each nonterminal symbol must have grammatical rules showing how it is made
481 out of simpler constructs. For example, one kind of C statement is the
482 @code{return} statement; this would be described with a grammar rule which
483 reads informally as follows:
486 A `statement' can be made of a `return' keyword, an `expression' and a
491 There would be many other rules for `statement', one for each kind of
495 One nonterminal symbol must be distinguished as the special one which
496 defines a complete utterance in the language. It is called the @dfn{start
497 symbol}. In a compiler, this means a complete input program. In the C
498 language, the nonterminal symbol `sequence of definitions and declarations'
501 For example, @samp{1 + 2} is a valid C expression---a valid part of a C
502 program---but it is not valid as an @emph{entire} C program. In the
503 context-free grammar of C, this follows from the fact that `expression' is
504 not the start symbol.
506 The Bison parser reads a sequence of tokens as its input, and groups the
507 tokens using the grammar rules. If the input is valid, the end result is
508 that the entire token sequence reduces to a single grouping whose symbol is
509 the grammar's start symbol. If we use a grammar for C, the entire input
510 must be a `sequence of definitions and declarations'. If not, the parser
511 reports a syntax error.
513 @node Grammar in Bison
514 @section From Formal Rules to Bison Input
515 @cindex Bison grammar
516 @cindex grammar, Bison
517 @cindex formal grammar
519 A formal grammar is a mathematical construct. To define the language
520 for Bison, you must write a file expressing the grammar in Bison syntax:
521 a @dfn{Bison grammar} file. @xref{Grammar File, ,Bison Grammar Files}.
523 A nonterminal symbol in the formal grammar is represented in Bison input
524 as an identifier, like an identifier in C. By convention, it should be
525 in lower case, such as @code{expr}, @code{stmt} or @code{declaration}.
527 The Bison representation for a terminal symbol is also called a @dfn{token
528 type}. Token types as well can be represented as C-like identifiers. By
529 convention, these identifiers should be upper case to distinguish them from
530 nonterminals: for example, @code{INTEGER}, @code{IDENTIFIER}, @code{IF} or
531 @code{RETURN}. A terminal symbol that stands for a particular keyword in
532 the language should be named after that keyword converted to upper case.
533 The terminal symbol @code{error} is reserved for error recovery.
536 A terminal symbol can also be represented as a character literal, just like
537 a C character constant. You should do this whenever a token is just a
538 single character (parenthesis, plus-sign, etc.): use that same character in
539 a literal as the terminal symbol for that token.
541 A third way to represent a terminal symbol is with a C string constant
542 containing several characters. @xref{Symbols}, for more information.
544 The grammar rules also have an expression in Bison syntax. For example,
545 here is the Bison rule for a C @code{return} statement. The semicolon in
546 quotes is a literal character token, representing part of the C syntax for
547 the statement; the naked semicolon, and the colon, are Bison punctuation
551 stmt: RETURN expr ';'
556 @xref{Rules, ,Syntax of Grammar Rules}.
558 @node Semantic Values
559 @section Semantic Values
560 @cindex semantic value
561 @cindex value, semantic
563 A formal grammar selects tokens only by their classifications: for example,
564 if a rule mentions the terminal symbol `integer constant', it means that
565 @emph{any} integer constant is grammatically valid in that position. The
566 precise value of the constant is irrelevant to how to parse the input: if
567 @samp{x+4} is grammatical then @samp{x+1} or @samp{x+3989} is equally
570 But the precise value is very important for what the input means once it is
571 parsed. A compiler is useless if it fails to distinguish between 4, 1 and
572 3989 as constants in the program! Therefore, each token in a Bison grammar
573 has both a token type and a @dfn{semantic value}. @xref{Semantics, ,Defining Language Semantics},
576 The token type is a terminal symbol defined in the grammar, such as
577 @code{INTEGER}, @code{IDENTIFIER} or @code{','}. It tells everything
578 you need to know to decide where the token may validly appear and how to
579 group it with other tokens. The grammar rules know nothing about tokens
580 except their types.@refill
582 The semantic value has all the rest of the information about the
583 meaning of the token, such as the value of an integer, or the name of an
584 identifier. (A token such as @code{','} which is just punctuation doesn't
585 need to have any semantic value.)
587 For example, an input token might be classified as token type
588 @code{INTEGER} and have the semantic value 4. Another input token might
589 have the same token type @code{INTEGER} but value 3989. When a grammar
590 rule says that @code{INTEGER} is allowed, either of these tokens is
591 acceptable because each is an @code{INTEGER}. When the parser accepts the
592 token, it keeps track of the token's semantic value.
594 Each grouping can also have a semantic value as well as its nonterminal
595 symbol. For example, in a calculator, an expression typically has a
596 semantic value that is a number. In a compiler for a programming
597 language, an expression typically has a semantic value that is a tree
598 structure describing the meaning of the expression.
600 @node Semantic Actions
601 @section Semantic Actions
602 @cindex semantic actions
603 @cindex actions, semantic
605 In order to be useful, a program must do more than parse input; it must
606 also produce some output based on the input. In a Bison grammar, a grammar
607 rule can have an @dfn{action} made up of C statements. Each time the
608 parser recognizes a match for that rule, the action is executed.
611 Most of the time, the purpose of an action is to compute the semantic value
612 of the whole construct from the semantic values of its parts. For example,
613 suppose we have a rule which says an expression can be the sum of two
614 expressions. When the parser recognizes such a sum, each of the
615 subexpressions has a semantic value which describes how it was built up.
616 The action for this rule should create a similar sort of value for the
617 newly recognized larger expression.
619 For example, here is a rule that says an expression can be the sum of
623 expr: expr '+' expr @{ $$ = $1 + $3; @}
628 The action says how to produce the semantic value of the sum expression
629 from the values of the two subexpressions.
631 @node Locations Overview
634 @cindex textual position
635 @cindex position, textual
637 Many applications, like interpreters or compilers, have to produce verbose
638 and useful error messages. To achieve this, one must be able to keep track of
639 the @dfn{textual position}, or @dfn{location}, of each syntactic construct.
640 Bison provides a mechanism for handling these locations.
642 Each token has a semantic value. In a similar fashion, each token has an
643 associated location, but the type of locations is the same for all tokens and
644 groupings. Moreover, the output parser is equipped with a default data
645 structure for storing locations (@pxref{Locations}, for more details).
647 Like semantic values, locations can be reached in actions using a dedicated
648 set of constructs. In the example above, the location of the whole grouping
649 is @code{@@$}, while the locations of the subexpressions are @code{@@1} and
652 When a rule is matched, a default action is used to compute the semantic value
653 of its left hand side (@pxref{Actions}). In the same way, another default
654 action is used for locations. However, the action for locations is general
655 enough for most cases, meaning there is usually no need to describe for each
656 rule how @code{@@$} should be formed. When building a new location for a given
657 grouping, the default behavior of the output parser is to take the beginning
658 of the first symbol, and the end of the last symbol.
661 @section Bison Output: the Parser File
663 @cindex Bison utility
664 @cindex lexical analyzer, purpose
667 When you run Bison, you give it a Bison grammar file as input. The output
668 is a C source file that parses the language described by the grammar.
669 This file is called a @dfn{Bison parser}. Keep in mind that the Bison
670 utility and the Bison parser are two distinct programs: the Bison utility
671 is a program whose output is the Bison parser that becomes part of your
674 The job of the Bison parser is to group tokens into groupings according to
675 the grammar rules---for example, to build identifiers and operators into
676 expressions. As it does this, it runs the actions for the grammar rules it
679 The tokens come from a function called the @dfn{lexical analyzer} that you
680 must supply in some fashion (such as by writing it in C). The Bison parser
681 calls the lexical analyzer each time it wants a new token. It doesn't know
682 what is ``inside'' the tokens (though their semantic values may reflect
683 this). Typically the lexical analyzer makes the tokens by parsing
684 characters of text, but Bison does not depend on this. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
686 The Bison parser file is C code which defines a function named
687 @code{yyparse} which implements that grammar. This function does not make
688 a complete C program: you must supply some additional functions. One is
689 the lexical analyzer. Another is an error-reporting function which the
690 parser calls to report an error. In addition, a complete C program must
691 start with a function called @code{main}; you have to provide this, and
692 arrange for it to call @code{yyparse} or the parser will never run.
693 @xref{Interface, ,Parser C-Language Interface}.
695 Aside from the token type names and the symbols in the actions you
696 write, all symbols defined in the Bison parser file itself
697 begin with @samp{yy} or @samp{YY}. This includes interface functions
698 such as the lexical analyzer function @code{yylex}, the error reporting
699 function @code{yyerror} and the parser function @code{yyparse} itself.
700 This also includes numerous identifiers used for internal purposes.
701 Therefore, you should avoid using C identifiers starting with @samp{yy}
702 or @samp{YY} in the Bison grammar file except for the ones defined in
705 In some cases the Bison parser file includes system headers, and in
706 those cases your code should respect the identifiers reserved by those
707 headers. On some non-@sc{gnu} hosts, @code{<alloca.h>},
708 @code{<stddef.h>}, and @code{<stdlib.h>} are included as needed to
709 declare memory allocators and related types. In the same situation,
710 C++ parsers may include @code{<cstddef>} and @code{<cstdlib>} instead.
711 Other system headers may be included if you define @code{YYDEBUG}
712 (@pxref{Debugging, ,Debugging Your Parser}).
715 @section Stages in Using Bison
716 @cindex stages in using Bison
719 The actual language-design process using Bison, from grammar specification
720 to a working compiler or interpreter, has these parts:
724 Formally specify the grammar in a form recognized by Bison
725 (@pxref{Grammar File, ,Bison Grammar Files}). For each grammatical rule in the language,
726 describe the action that is to be taken when an instance of that rule
727 is recognized. The action is described by a sequence of C statements.
730 Write a lexical analyzer to process input and pass tokens to the
731 parser. The lexical analyzer may be written by hand in C
732 (@pxref{Lexical, ,The Lexical Analyzer Function @code{yylex}}). It could also be produced using Lex, but the use
733 of Lex is not discussed in this manual.
736 Write a controlling function that calls the Bison-produced parser.
739 Write error-reporting routines.
742 To turn this source code as written into a runnable program, you
743 must follow these steps:
747 Run Bison on the grammar to produce the parser.
750 Compile the code output by Bison, as well as any other source files.
753 Link the object files to produce the finished product.
757 @section The Overall Layout of a Bison Grammar
760 @cindex format of grammar file
761 @cindex layout of Bison grammar
763 The input file for the Bison utility is a @dfn{Bison grammar file}. The
764 general form of a Bison grammar file is as follows:
768 @var{Prologue (declarations)}
771 @var{Bison declarations}
776 @var{Epilogue (additional code)}
780 The @samp{%%}, @samp{%@{} and @samp{%@}} are punctuation that appears
781 in every Bison grammar file to separate the sections.
783 The prologue may define types and variables used in the actions. You can
784 also use preprocessor commands to define macros used there, and use
785 @code{#include} to include header files that do any of these things.
787 The Bison declarations declare the names of the terminal and nonterminal
788 symbols, and may also describe operator precedence and the data types of
789 semantic values of various symbols.
791 The grammar rules define how to construct each nonterminal symbol from its
794 The epilogue can contain any code you want to use. Often the definition of
795 the lexical analyzer @code{yylex} goes here, plus subroutines called by the
796 actions in the grammar rules. In a simple program, all the rest of the
801 @cindex simple examples
802 @cindex examples, simple
804 Now we show and explain three sample programs written using Bison: a
805 reverse polish notation calculator, an algebraic (infix) notation
806 calculator, and a multi-function calculator. All three have been tested
807 under BSD Unix 4.3; each produces a usable, though limited, interactive
810 These examples are simple, but Bison grammars for real programming
811 languages are written the same way.
813 You can copy these examples out of the Info file and into a source file
818 * RPN Calc:: Reverse polish notation calculator;
819 a first example with no operator precedence.
820 * Infix Calc:: Infix (algebraic) notation calculator.
821 Operator precedence is introduced.
822 * Simple Error Recovery:: Continuing after syntax errors.
823 * Location Tracking Calc:: Demonstrating the use of @@@var{n} and @@$.
824 * Multi-function Calc:: Calculator with memory and trig functions.
825 It uses multiple data-types for semantic values.
826 * Exercises:: Ideas for improving the multi-function calculator.
830 @section Reverse Polish Notation Calculator
831 @cindex reverse polish notation
832 @cindex polish notation calculator
833 @cindex @code{rpcalc}
834 @cindex calculator, simple
836 The first example is that of a simple double-precision @dfn{reverse polish
837 notation} calculator (a calculator using postfix operators). This example
838 provides a good starting point, since operator precedence is not an issue.
839 The second example will illustrate how operator precedence is handled.
841 The source code for this calculator is named @file{rpcalc.y}. The
842 @samp{.y} extension is a convention used for Bison input files.
845 * Decls: Rpcalc Decls. Prologue (declarations) for rpcalc.
846 * Rules: Rpcalc Rules. Grammar Rules for rpcalc, with explanation.
847 * Lexer: Rpcalc Lexer. The lexical analyzer.
848 * Main: Rpcalc Main. The controlling function.
849 * Error: Rpcalc Error. The error reporting function.
850 * Gen: Rpcalc Gen. Running Bison on the grammar file.
851 * Comp: Rpcalc Compile. Run the C compiler on the output code.
855 @subsection Declarations for @code{rpcalc}
857 Here are the C and Bison declarations for the reverse polish notation
858 calculator. As in C, comments are placed between @samp{/*@dots{}*/}.
861 /* Reverse polish notation calculator. */
864 #define YYSTYPE double
870 %% /* Grammar rules and actions follow */
873 The declarations section (@pxref{Prologue, , The prologue}) contains two
874 preprocessor directives.
876 The @code{#define} directive defines the macro @code{YYSTYPE}, thus
877 specifying the C data type for semantic values of both tokens and
878 groupings (@pxref{Value Type, ,Data Types of Semantic Values}). The
879 Bison parser will use whatever type @code{YYSTYPE} is defined as; if you
880 don't define it, @code{int} is the default. Because we specify
881 @code{double}, each token and each expression has an associated value,
882 which is a floating point number.
884 The @code{#include} directive is used to declare the exponentiation
887 The second section, Bison declarations, provides information to Bison about
888 the token types (@pxref{Bison Declarations, ,The Bison Declarations Section}). Each terminal symbol that is
889 not a single-character literal must be declared here. (Single-character
890 literals normally don't need to be declared.) In this example, all the
891 arithmetic operators are designated by single-character literals, so the
892 only terminal symbol that needs to be declared is @code{NUM}, the token
893 type for numeric constants.
896 @subsection Grammar Rules for @code{rpcalc}
898 Here are the grammar rules for the reverse polish notation calculator.
906 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
909 exp: NUM @{ $$ = $1; @}
910 | exp exp '+' @{ $$ = $1 + $2; @}
911 | exp exp '-' @{ $$ = $1 - $2; @}
912 | exp exp '*' @{ $$ = $1 * $2; @}
913 | exp exp '/' @{ $$ = $1 / $2; @}
915 | exp exp '^' @{ $$ = pow ($1, $2); @}
917 | exp 'n' @{ $$ = -$1; @}
922 The groupings of the rpcalc ``language'' defined here are the expression
923 (given the name @code{exp}), the line of input (@code{line}), and the
924 complete input transcript (@code{input}). Each of these nonterminal
925 symbols has several alternate rules, joined by the @samp{|} punctuator
926 which is read as ``or''. The following sections explain what these rules
929 The semantics of the language is determined by the actions taken when a
930 grouping is recognized. The actions are the C code that appears inside
931 braces. @xref{Actions}.
933 You must specify these actions in C, but Bison provides the means for
934 passing semantic values between the rules. In each action, the
935 pseudo-variable @code{$$} stands for the semantic value for the grouping
936 that the rule is going to construct. Assigning a value to @code{$$} is the
937 main job of most actions. The semantic values of the components of the
938 rule are referred to as @code{$1}, @code{$2}, and so on.
947 @subsubsection Explanation of @code{input}
949 Consider the definition of @code{input}:
957 This definition reads as follows: ``A complete input is either an empty
958 string, or a complete input followed by an input line''. Notice that
959 ``complete input'' is defined in terms of itself. This definition is said
960 to be @dfn{left recursive} since @code{input} appears always as the
961 leftmost symbol in the sequence. @xref{Recursion, ,Recursive Rules}.
963 The first alternative is empty because there are no symbols between the
964 colon and the first @samp{|}; this means that @code{input} can match an
965 empty string of input (no tokens). We write the rules this way because it
966 is legitimate to type @kbd{Ctrl-d} right after you start the calculator.
967 It's conventional to put an empty alternative first and write the comment
968 @samp{/* empty */} in it.
970 The second alternate rule (@code{input line}) handles all nontrivial input.
971 It means, ``After reading any number of lines, read one more line if
972 possible.'' The left recursion makes this rule into a loop. Since the
973 first alternative matches empty input, the loop can be executed zero or
976 The parser function @code{yyparse} continues to process input until a
977 grammatical error is seen or the lexical analyzer says there are no more
978 input tokens; we will arrange for the latter to happen at end of file.
981 @subsubsection Explanation of @code{line}
983 Now consider the definition of @code{line}:
987 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
991 The first alternative is a token which is a newline character; this means
992 that rpcalc accepts a blank line (and ignores it, since there is no
993 action). The second alternative is an expression followed by a newline.
994 This is the alternative that makes rpcalc useful. The semantic value of
995 the @code{exp} grouping is the value of @code{$1} because the @code{exp} in
996 question is the first symbol in the alternative. The action prints this
997 value, which is the result of the computation the user asked for.
999 This action is unusual because it does not assign a value to @code{$$}. As
1000 a consequence, the semantic value associated with the @code{line} is
1001 uninitialized (its value will be unpredictable). This would be a bug if
1002 that value were ever used, but we don't use it: once rpcalc has printed the
1003 value of the user's input line, that value is no longer needed.
1006 @subsubsection Explanation of @code{expr}
1008 The @code{exp} grouping has several rules, one for each kind of expression.
1009 The first rule handles the simplest expressions: those that are just numbers.
1010 The second handles an addition-expression, which looks like two expressions
1011 followed by a plus-sign. The third handles subtraction, and so on.
1015 | exp exp '+' @{ $$ = $1 + $2; @}
1016 | exp exp '-' @{ $$ = $1 - $2; @}
1021 We have used @samp{|} to join all the rules for @code{exp}, but we could
1022 equally well have written them separately:
1026 exp: exp exp '+' @{ $$ = $1 + $2; @} ;
1027 exp: exp exp '-' @{ $$ = $1 - $2; @} ;
1031 Most of the rules have actions that compute the value of the expression in
1032 terms of the value of its parts. For example, in the rule for addition,
1033 @code{$1} refers to the first component @code{exp} and @code{$2} refers to
1034 the second one. The third component, @code{'+'}, has no meaningful
1035 associated semantic value, but if it had one you could refer to it as
1036 @code{$3}. When @code{yyparse} recognizes a sum expression using this
1037 rule, the sum of the two subexpressions' values is produced as the value of
1038 the entire expression. @xref{Actions}.
1040 You don't have to give an action for every rule. When a rule has no
1041 action, Bison by default copies the value of @code{$1} into @code{$$}.
1042 This is what happens in the first rule (the one that uses @code{NUM}).
1044 The formatting shown here is the recommended convention, but Bison does
1045 not require it. You can add or change whitespace as much as you wish.
1049 exp : NUM | exp exp '+' @{$$ = $1 + $2; @} | @dots{}
1053 means the same thing as this:
1057 | exp exp '+' @{ $$ = $1 + $2; @}
1062 The latter, however, is much more readable.
1065 @subsection The @code{rpcalc} Lexical Analyzer
1066 @cindex writing a lexical analyzer
1067 @cindex lexical analyzer, writing
1069 The lexical analyzer's job is low-level parsing: converting characters or
1070 sequences of characters into tokens. The Bison parser gets its tokens by
1071 calling the lexical analyzer. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
1073 Only a simple lexical analyzer is needed for the RPN calculator. This
1074 lexical analyzer skips blanks and tabs, then reads in numbers as
1075 @code{double} and returns them as @code{NUM} tokens. Any other character
1076 that isn't part of a number is a separate token. Note that the token-code
1077 for such a single-character token is the character itself.
1079 The return value of the lexical analyzer function is a numeric code which
1080 represents a token type. The same text used in Bison rules to stand for
1081 this token type is also a C expression for the numeric code for the type.
1082 This works in two ways. If the token type is a character literal, then its
1083 numeric code is the ASCII code for that character; you can use the same
1084 character literal in the lexical analyzer to express the number. If the
1085 token type is an identifier, that identifier is defined by Bison as a C
1086 macro whose definition is the appropriate number. In this example,
1087 therefore, @code{NUM} becomes a macro for @code{yylex} to use.
1089 The semantic value of the token (if it has one) is stored into the
1090 global variable @code{yylval}, which is where the Bison parser will look
1091 for it. (The C data type of @code{yylval} is @code{YYSTYPE}, which was
1092 defined at the beginning of the grammar; @pxref{Rpcalc Decls,
1093 ,Declarations for @code{rpcalc}}.)
1095 A token type code of zero is returned if the end-of-file is encountered.
1096 (Bison recognizes any nonpositive value as indicating the end of the
1099 Here is the code for the lexical analyzer:
1103 /* Lexical analyzer returns a double floating point
1104 number on the stack and the token NUM, or the ASCII
1105 character read if not a number. Skips all blanks
1106 and tabs, returns 0 for EOF. */
1117 /* skip white space */
1118 while ((c = getchar ()) == ' ' || c == '\t')
1122 /* process numbers */
1123 if (c == '.' || isdigit (c))
1126 scanf ("%lf", &yylval);
1131 /* return end-of-file */
1134 /* return single chars */
1141 @subsection The Controlling Function
1142 @cindex controlling function
1143 @cindex main function in simple example
1145 In keeping with the spirit of this example, the controlling function is
1146 kept to the bare minimum. The only requirement is that it call
1147 @code{yyparse} to start the process of parsing.
1160 @subsection The Error Reporting Routine
1161 @cindex error reporting routine
1163 When @code{yyparse} detects a syntax error, it calls the error reporting
1164 function @code{yyerror} to print an error message (usually but not
1165 always @code{"parse error"}). It is up to the programmer to supply
1166 @code{yyerror} (@pxref{Interface, ,Parser C-Language Interface}), so
1167 here is the definition we will use:
1174 yyerror (const char *s) /* Called by yyparse on error */
1181 After @code{yyerror} returns, the Bison parser may recover from the error
1182 and continue parsing if the grammar contains a suitable error rule
1183 (@pxref{Error Recovery}). Otherwise, @code{yyparse} returns nonzero. We
1184 have not written any error rules in this example, so any invalid input will
1185 cause the calculator program to exit. This is not clean behavior for a
1186 real calculator, but it is adequate for the first example.
1189 @subsection Running Bison to Make the Parser
1190 @cindex running Bison (introduction)
1192 Before running Bison to produce a parser, we need to decide how to
1193 arrange all the source code in one or more source files. For such a
1194 simple example, the easiest thing is to put everything in one file. The
1195 definitions of @code{yylex}, @code{yyerror} and @code{main} go at the
1196 end, in the epilogue of the file
1197 (@pxref{Grammar Layout, ,The Overall Layout of a Bison Grammar}).
1199 For a large project, you would probably have several source files, and use
1200 @code{make} to arrange to recompile them.
1202 With all the source in a single file, you use the following command to
1203 convert it into a parser file:
1206 bison @var{file_name}.y
1210 In this example the file was called @file{rpcalc.y} (for ``Reverse Polish
1211 CALCulator''). Bison produces a file named @file{@var{file_name}.tab.c},
1212 removing the @samp{.y} from the original file name. The file output by
1213 Bison contains the source code for @code{yyparse}. The additional
1214 functions in the input file (@code{yylex}, @code{yyerror} and @code{main})
1215 are copied verbatim to the output.
1217 @node Rpcalc Compile
1218 @subsection Compiling the Parser File
1219 @cindex compiling the parser
1221 Here is how to compile and run the parser file:
1225 # @r{List files in current directory.}
1227 rpcalc.tab.c rpcalc.y
1231 # @r{Compile the Bison parser.}
1232 # @r{@samp{-lm} tells compiler to search math library for @code{pow}.}
1233 $ @kbd{cc rpcalc.tab.c -lm -o rpcalc}
1237 # @r{List files again.}
1239 rpcalc rpcalc.tab.c rpcalc.y
1243 The file @file{rpcalc} now contains the executable code. Here is an
1244 example session using @code{rpcalc}.
1250 @kbd{3 7 + 3 4 5 *+-}
1252 @kbd{3 7 + 3 4 5 * + - n} @r{Note the unary minus, @samp{n}}
1256 @kbd{3 4 ^} @r{Exponentiation}
1258 @kbd{^D} @r{End-of-file indicator}
1263 @section Infix Notation Calculator: @code{calc}
1264 @cindex infix notation calculator
1266 @cindex calculator, infix notation
1268 We now modify rpcalc to handle infix operators instead of postfix. Infix
1269 notation involves the concept of operator precedence and the need for
1270 parentheses nested to arbitrary depth. Here is the Bison code for
1271 @file{calc.y}, an infix desk-top calculator.
1274 /* Infix notation calculator--calc */
1277 #define YYSTYPE double
1281 /* BISON Declarations */
1285 %left NEG /* negation--unary minus */
1286 %right '^' /* exponentiation */
1288 /* Grammar follows */
1290 input: /* empty string */
1295 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1298 exp: NUM @{ $$ = $1; @}
1299 | exp '+' exp @{ $$ = $1 + $3; @}
1300 | exp '-' exp @{ $$ = $1 - $3; @}
1301 | exp '*' exp @{ $$ = $1 * $3; @}
1302 | exp '/' exp @{ $$ = $1 / $3; @}
1303 | '-' exp %prec NEG @{ $$ = -$2; @}
1304 | exp '^' exp @{ $$ = pow ($1, $3); @}
1305 | '(' exp ')' @{ $$ = $2; @}
1311 The functions @code{yylex}, @code{yyerror} and @code{main} can be the
1314 There are two important new features shown in this code.
1316 In the second section (Bison declarations), @code{%left} declares token
1317 types and says they are left-associative operators. The declarations
1318 @code{%left} and @code{%right} (right associativity) take the place of
1319 @code{%token} which is used to declare a token type name without
1320 associativity. (These tokens are single-character literals, which
1321 ordinarily don't need to be declared. We declare them here to specify
1324 Operator precedence is determined by the line ordering of the
1325 declarations; the higher the line number of the declaration (lower on
1326 the page or screen), the higher the precedence. Hence, exponentiation
1327 has the highest precedence, unary minus (@code{NEG}) is next, followed
1328 by @samp{*} and @samp{/}, and so on. @xref{Precedence, ,Operator Precedence}.
1330 The other important new feature is the @code{%prec} in the grammar section
1331 for the unary minus operator. The @code{%prec} simply instructs Bison that
1332 the rule @samp{| '-' exp} has the same precedence as @code{NEG}---in this
1333 case the next-to-highest. @xref{Contextual Precedence, ,Context-Dependent Precedence}.
1335 Here is a sample run of @file{calc.y}:
1340 @kbd{4 + 4.5 - (34/(8*3+-3))}
1348 @node Simple Error Recovery
1349 @section Simple Error Recovery
1350 @cindex error recovery, simple
1352 Up to this point, this manual has not addressed the issue of @dfn{error
1353 recovery}---how to continue parsing after the parser detects a syntax
1354 error. All we have handled is error reporting with @code{yyerror}.
1355 Recall that by default @code{yyparse} returns after calling
1356 @code{yyerror}. This means that an erroneous input line causes the
1357 calculator program to exit. Now we show how to rectify this deficiency.
1359 The Bison language itself includes the reserved word @code{error}, which
1360 may be included in the grammar rules. In the example below it has
1361 been added to one of the alternatives for @code{line}:
1366 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1367 | error '\n' @{ yyerrok; @}
1372 This addition to the grammar allows for simple error recovery in the
1373 event of a parse error. If an expression that cannot be evaluated is
1374 read, the error will be recognized by the third rule for @code{line},
1375 and parsing will continue. (The @code{yyerror} function is still called
1376 upon to print its message as well.) The action executes the statement
1377 @code{yyerrok}, a macro defined automatically by Bison; its meaning is
1378 that error recovery is complete (@pxref{Error Recovery}). Note the
1379 difference between @code{yyerrok} and @code{yyerror}; neither one is a
1382 This form of error recovery deals with syntax errors. There are other
1383 kinds of errors; for example, division by zero, which raises an exception
1384 signal that is normally fatal. A real calculator program must handle this
1385 signal and use @code{longjmp} to return to @code{main} and resume parsing
1386 input lines; it would also have to discard the rest of the current line of
1387 input. We won't discuss this issue further because it is not specific to
1390 @node Location Tracking Calc
1391 @section Location Tracking Calculator: @code{ltcalc}
1392 @cindex location tracking calculator
1393 @cindex @code{ltcalc}
1394 @cindex calculator, location tracking
1396 This example extends the infix notation calculator with location
1397 tracking. This feature will be used to improve the error messages. For
1398 the sake of clarity, this example is a simple integer calculator, since
1399 most of the work needed to use locations will be done in the lexical
1403 * Decls: Ltcalc Decls. Bison and C declarations for ltcalc.
1404 * Rules: Ltcalc Rules. Grammar rules for ltcalc, with explanations.
1405 * Lexer: Ltcalc Lexer. The lexical analyzer.
1409 @subsection Declarations for @code{ltcalc}
1411 The C and Bison declarations for the location tracking calculator are
1412 the same as the declarations for the infix notation calculator.
1415 /* Location tracking calculator. */
1422 /* Bison declarations. */
1430 %% /* Grammar follows */
1434 Note there are no declarations specific to locations. Defining a data
1435 type for storing locations is not needed: we will use the type provided
1436 by default (@pxref{Location Type, ,Data Types of Locations}), which is a
1437 four member structure with the following integer fields:
1438 @code{first_line}, @code{first_column}, @code{last_line} and
1442 @subsection Grammar Rules for @code{ltcalc}
1444 Whether handling locations or not has no effect on the syntax of your
1445 language. Therefore, grammar rules for this example will be very close
1446 to those of the previous example: we will only modify them to benefit
1447 from the new information.
1449 Here, we will use locations to report divisions by zero, and locate the
1450 wrong expressions or subexpressions.
1461 | exp '\n' @{ printf ("%d\n", $1); @}
1466 exp : NUM @{ $$ = $1; @}
1467 | exp '+' exp @{ $$ = $1 + $3; @}
1468 | exp '-' exp @{ $$ = $1 - $3; @}
1469 | exp '*' exp @{ $$ = $1 * $3; @}
1479 fprintf (stderr, "%d.%d-%d.%d: division by zero",
1480 @@3.first_line, @@3.first_column,
1481 @@3.last_line, @@3.last_column);
1486 | '-' exp %preg NEG @{ $$ = -$2; @}
1487 | exp '^' exp @{ $$ = pow ($1, $3); @}
1488 | '(' exp ')' @{ $$ = $2; @}
1492 This code shows how to reach locations inside of semantic actions, by
1493 using the pseudo-variables @code{@@@var{n}} for rule components, and the
1494 pseudo-variable @code{@@$} for groupings.
1496 We don't need to assign a value to @code{@@$}: the output parser does it
1497 automatically. By default, before executing the C code of each action,
1498 @code{@@$} is set to range from the beginning of @code{@@1} to the end
1499 of @code{@@@var{n}}, for a rule with @var{n} components. This behavior
1500 can be redefined (@pxref{Location Default Action, , Default Action for
1501 Locations}), and for very specific rules, @code{@@$} can be computed by
1505 @subsection The @code{ltcalc} Lexical Analyzer.
1507 Until now, we relied on Bison's defaults to enable location
1508 tracking. The next step is to rewrite the lexical analyser, and make it
1509 able to feed the parser with the token locations, as it already does for
1512 To this end, we must take into account every single character of the
1513 input text, to avoid the computed locations of being fuzzy or wrong:
1522 /* skip white space */
1523 while ((c = getchar ()) == ' ' || c == '\t')
1524 ++yylloc.last_column;
1527 yylloc.first_line = yylloc.last_line;
1528 yylloc.first_column = yylloc.last_column;
1532 /* process numbers */
1536 ++yylloc.last_column;
1537 while (isdigit (c = getchar ()))
1539 ++yylloc.last_column;
1540 yylval = yylval * 10 + c - '0';
1547 /* return end-of-file */
1551 /* return single chars and update location */
1555 yylloc.last_column = 0;
1558 ++yylloc.last_column;
1563 Basically, the lexical analyzer performs the same processing as before:
1564 it skips blanks and tabs, and reads numbers or single-character tokens.
1565 In addition, it updates @code{yylloc}, the global variable (of type
1566 @code{YYLTYPE}) containing the token's location.
1568 Now, each time this function returns a token, the parser has its number
1569 as well as its semantic value, and its location in the text. The last
1570 needed change is to initialize @code{yylloc}, for example in the
1571 controlling function:
1578 yylloc.first_line = yylloc.last_line = 1;
1579 yylloc.first_column = yylloc.last_column = 0;
1585 Remember that computing locations is not a matter of syntax. Every
1586 character must be associated to a location update, whether it is in
1587 valid input, in comments, in literal strings, and so on.
1589 @node Multi-function Calc
1590 @section Multi-Function Calculator: @code{mfcalc}
1591 @cindex multi-function calculator
1592 @cindex @code{mfcalc}
1593 @cindex calculator, multi-function
1595 Now that the basics of Bison have been discussed, it is time to move on to
1596 a more advanced problem. The above calculators provided only five
1597 functions, @samp{+}, @samp{-}, @samp{*}, @samp{/} and @samp{^}. It would
1598 be nice to have a calculator that provides other mathematical functions such
1599 as @code{sin}, @code{cos}, etc.
1601 It is easy to add new operators to the infix calculator as long as they are
1602 only single-character literals. The lexical analyzer @code{yylex} passes
1603 back all nonnumber characters as tokens, so new grammar rules suffice for
1604 adding a new operator. But we want something more flexible: built-in
1605 functions whose syntax has this form:
1608 @var{function_name} (@var{argument})
1612 At the same time, we will add memory to the calculator, by allowing you
1613 to create named variables, store values in them, and use them later.
1614 Here is a sample session with the multi-function calculator:
1618 @kbd{pi = 3.141592653589}
1622 @kbd{alpha = beta1 = 2.3}
1628 @kbd{exp(ln(beta1))}
1633 Note that multiple assignment and nested function calls are permitted.
1636 * Decl: Mfcalc Decl. Bison declarations for multi-function calculator.
1637 * Rules: Mfcalc Rules. Grammar rules for the calculator.
1638 * Symtab: Mfcalc Symtab. Symbol table management subroutines.
1642 @subsection Declarations for @code{mfcalc}
1644 Here are the C and Bison declarations for the multi-function calculator.
1648 #include <math.h> /* For math functions, cos(), sin(), etc. */
1649 #include "calc.h" /* Contains definition of `symrec' */
1652 double val; /* For returning numbers. */
1653 symrec *tptr; /* For returning symbol-table pointers */
1656 %token <val> NUM /* Simple double precision number */
1657 %token <tptr> VAR FNCT /* Variable and Function */
1663 %left NEG /* Negation--unary minus */
1664 %right '^' /* Exponentiation */
1666 /* Grammar follows */
1671 The above grammar introduces only two new features of the Bison language.
1672 These features allow semantic values to have various data types
1673 (@pxref{Multiple Types, ,More Than One Value Type}).
1675 The @code{%union} declaration specifies the entire list of possible types;
1676 this is instead of defining @code{YYSTYPE}. The allowable types are now
1677 double-floats (for @code{exp} and @code{NUM}) and pointers to entries in
1678 the symbol table. @xref{Union Decl, ,The Collection of Value Types}.
1680 Since values can now have various types, it is necessary to associate a
1681 type with each grammar symbol whose semantic value is used. These symbols
1682 are @code{NUM}, @code{VAR}, @code{FNCT}, and @code{exp}. Their
1683 declarations are augmented with information about their data type (placed
1684 between angle brackets).
1686 The Bison construct @code{%type} is used for declaring nonterminal symbols,
1687 just as @code{%token} is used for declaring token types. We have not used
1688 @code{%type} before because nonterminal symbols are normally declared
1689 implicitly by the rules that define them. But @code{exp} must be declared
1690 explicitly so we can specify its value type. @xref{Type Decl, ,Nonterminal Symbols}.
1693 @subsection Grammar Rules for @code{mfcalc}
1695 Here are the grammar rules for the multi-function calculator.
1696 Most of them are copied directly from @code{calc}; three rules,
1697 those which mention @code{VAR} or @code{FNCT}, are new.
1706 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1707 | error '\n' @{ yyerrok; @}
1710 exp: NUM @{ $$ = $1; @}
1711 | VAR @{ $$ = $1->value.var; @}
1712 | VAR '=' exp @{ $$ = $3; $1->value.var = $3; @}
1713 | FNCT '(' exp ')' @{ $$ = (*($1->value.fnctptr))($3); @}
1714 | exp '+' exp @{ $$ = $1 + $3; @}
1715 | exp '-' exp @{ $$ = $1 - $3; @}
1716 | exp '*' exp @{ $$ = $1 * $3; @}
1717 | exp '/' exp @{ $$ = $1 / $3; @}
1718 | '-' exp %prec NEG @{ $$ = -$2; @}
1719 | exp '^' exp @{ $$ = pow ($1, $3); @}
1720 | '(' exp ')' @{ $$ = $2; @}
1722 /* End of grammar */
1727 @subsection The @code{mfcalc} Symbol Table
1728 @cindex symbol table example
1730 The multi-function calculator requires a symbol table to keep track of the
1731 names and meanings of variables and functions. This doesn't affect the
1732 grammar rules (except for the actions) or the Bison declarations, but it
1733 requires some additional C functions for support.
1735 The symbol table itself consists of a linked list of records. Its
1736 definition, which is kept in the header @file{calc.h}, is as follows. It
1737 provides for either functions or variables to be placed in the table.
1741 /* Fonctions type. */
1742 typedef double (*func_t) (double);
1744 /* Data type for links in the chain of symbols. */
1747 char *name; /* name of symbol */
1748 int type; /* type of symbol: either VAR or FNCT */
1751 double var; /* value of a VAR */
1752 func_t fnctptr; /* value of a FNCT */
1754 struct symrec *next; /* link field */
1759 typedef struct symrec symrec;
1761 /* The symbol table: a chain of `struct symrec'. */
1762 extern symrec *sym_table;
1764 symrec *putsym (const char *, func_t);
1765 symrec *getsym (const char *);
1769 The new version of @code{main} includes a call to @code{init_table}, a
1770 function that initializes the symbol table. Here it is, and
1771 @code{init_table} as well:
1787 yyerror (const char *s) /* Called by yyparse on error */
1795 double (*fnct)(double);
1800 struct init arith_fncts[] =
1811 /* The symbol table: a chain of `struct symrec'. */
1812 symrec *sym_table = (symrec *) 0;
1816 /* Put arithmetic functions in table. */
1822 for (i = 0; arith_fncts[i].fname != 0; i++)
1824 ptr = putsym (arith_fncts[i].fname, FNCT);
1825 ptr->value.fnctptr = arith_fncts[i].fnct;
1831 By simply editing the initialization list and adding the necessary include
1832 files, you can add additional functions to the calculator.
1834 Two important functions allow look-up and installation of symbols in the
1835 symbol table. The function @code{putsym} is passed a name and the type
1836 (@code{VAR} or @code{FNCT}) of the object to be installed. The object is
1837 linked to the front of the list, and a pointer to the object is returned.
1838 The function @code{getsym} is passed the name of the symbol to look up. If
1839 found, a pointer to that symbol is returned; otherwise zero is returned.
1843 putsym (char *sym_name, int sym_type)
1846 ptr = (symrec *) malloc (sizeof (symrec));
1847 ptr->name = (char *) malloc (strlen (sym_name) + 1);
1848 strcpy (ptr->name,sym_name);
1849 ptr->type = sym_type;
1850 ptr->value.var = 0; /* set value to 0 even if fctn. */
1851 ptr->next = (struct symrec *)sym_table;
1857 getsym (const char *sym_name)
1860 for (ptr = sym_table; ptr != (symrec *) 0;
1861 ptr = (symrec *)ptr->next)
1862 if (strcmp (ptr->name,sym_name) == 0)
1868 The function @code{yylex} must now recognize variables, numeric values, and
1869 the single-character arithmetic operators. Strings of alphanumeric
1870 characters with a leading non-digit are recognized as either variables or
1871 functions depending on what the symbol table says about them.
1873 The string is passed to @code{getsym} for look up in the symbol table. If
1874 the name appears in the table, a pointer to its location and its type
1875 (@code{VAR} or @code{FNCT}) is returned to @code{yyparse}. If it is not
1876 already in the table, then it is installed as a @code{VAR} using
1877 @code{putsym}. Again, a pointer and its type (which must be @code{VAR}) is
1878 returned to @code{yyparse}.@refill
1880 No change is needed in the handling of numeric values and arithmetic
1881 operators in @code{yylex}.
1892 /* Ignore whitespace, get first nonwhite character. */
1893 while ((c = getchar ()) == ' ' || c == '\t');
1900 /* Char starts a number => parse the number. */
1901 if (c == '.' || isdigit (c))
1904 scanf ("%lf", &yylval.val);
1910 /* Char starts an identifier => read the name. */
1914 static char *symbuf = 0;
1915 static int length = 0;
1920 /* Initially make the buffer long enough
1921 for a 40-character symbol name. */
1923 length = 40, symbuf = (char *)malloc (length + 1);
1930 /* If buffer is full, make it bigger. */
1934 symbuf = (char *)realloc (symbuf, length + 1);
1936 /* Add this character to the buffer. */
1938 /* Get another character. */
1943 while (c != EOF && isalnum (c));
1950 s = getsym (symbuf);
1952 s = putsym (symbuf, VAR);
1957 /* Any other character is a token by itself. */
1963 This program is both powerful and flexible. You may easily add new
1964 functions, and it is a simple job to modify this code to install predefined
1965 variables such as @code{pi} or @code{e} as well.
1973 Add some new functions from @file{math.h} to the initialization list.
1976 Add another array that contains constants and their values. Then
1977 modify @code{init_table} to add these constants to the symbol table.
1978 It will be easiest to give the constants type @code{VAR}.
1981 Make the program report an error if the user refers to an
1982 uninitialized variable in any way except to store a value in it.
1986 @chapter Bison Grammar Files
1988 Bison takes as input a context-free grammar specification and produces a
1989 C-language function that recognizes correct instances of the grammar.
1991 The Bison grammar input file conventionally has a name ending in @samp{.y}.
1992 @xref{Invocation, ,Invoking Bison}.
1995 * Grammar Outline:: Overall layout of the grammar file.
1996 * Symbols:: Terminal and nonterminal symbols.
1997 * Rules:: How to write grammar rules.
1998 * Recursion:: Writing recursive rules.
1999 * Semantics:: Semantic values and actions.
2000 * Locations:: Locations and actions.
2001 * Declarations:: All kinds of Bison declarations are described here.
2002 * Multiple Parsers:: Putting more than one Bison parser in one program.
2005 @node Grammar Outline
2006 @section Outline of a Bison Grammar
2008 A Bison grammar file has four main sections, shown here with the
2009 appropriate delimiters:
2016 @var{Bison declarations}
2025 Comments enclosed in @samp{/* @dots{} */} may appear in any of the sections.
2028 * Prologue:: Syntax and usage of the prologue.
2029 * Bison Declarations:: Syntax and usage of the Bison declarations section.
2030 * Grammar Rules:: Syntax and usage of the grammar rules section.
2031 * Epilogue:: Syntax and usage of the epilogue.
2034 @node Prologue, Bison Declarations, , Grammar Outline
2035 @subsection The prologue
2036 @cindex declarations section
2038 @cindex declarations
2040 The @var{prologue} section contains macro definitions and
2041 declarations of functions and variables that are used in the actions in the
2042 grammar rules. These are copied to the beginning of the parser file so
2043 that they precede the definition of @code{yyparse}. You can use
2044 @samp{#include} to get the declarations from a header file. If you don't
2045 need any C declarations, you may omit the @samp{%@{} and @samp{%@}}
2046 delimiters that bracket this section.
2048 @node Bison Declarations
2049 @subsection The Bison Declarations Section
2050 @cindex Bison declarations (introduction)
2051 @cindex declarations, Bison (introduction)
2053 The @var{Bison declarations} section contains declarations that define
2054 terminal and nonterminal symbols, specify precedence, and so on.
2055 In some simple grammars you may not need any declarations.
2056 @xref{Declarations, ,Bison Declarations}.
2059 @subsection The Grammar Rules Section
2060 @cindex grammar rules section
2061 @cindex rules section for grammar
2063 The @dfn{grammar rules} section contains one or more Bison grammar
2064 rules, and nothing else. @xref{Rules, ,Syntax of Grammar Rules}.
2066 There must always be at least one grammar rule, and the first
2067 @samp{%%} (which precedes the grammar rules) may never be omitted even
2068 if it is the first thing in the file.
2070 @node Epilogue, , Grammar Rules, Grammar Outline
2071 @subsection The epilogue
2072 @cindex additional C code section
2074 @cindex C code, section for additional
2076 The @var{epilogue} is copied verbatim to the end of the parser file, just as
2077 the @var{prologue} is copied to the beginning. This is the most convenient
2078 place to put anything that you want to have in the parser file but which need
2079 not come before the definition of @code{yyparse}. For example, the
2080 definitions of @code{yylex} and @code{yyerror} often go here.
2081 @xref{Interface, ,Parser C-Language Interface}.
2083 If the last section is empty, you may omit the @samp{%%} that separates it
2084 from the grammar rules.
2086 The Bison parser itself contains many static variables whose names start
2087 with @samp{yy} and many macros whose names start with @samp{YY}. It is a
2088 good idea to avoid using any such names (except those documented in this
2089 manual) in the epilogue of the grammar file.
2092 @section Symbols, Terminal and Nonterminal
2093 @cindex nonterminal symbol
2094 @cindex terminal symbol
2098 @dfn{Symbols} in Bison grammars represent the grammatical classifications
2101 A @dfn{terminal symbol} (also known as a @dfn{token type}) represents a
2102 class of syntactically equivalent tokens. You use the symbol in grammar
2103 rules to mean that a token in that class is allowed. The symbol is
2104 represented in the Bison parser by a numeric code, and the @code{yylex}
2105 function returns a token type code to indicate what kind of token has been
2106 read. You don't need to know what the code value is; you can use the
2107 symbol to stand for it.
2109 A @dfn{nonterminal symbol} stands for a class of syntactically equivalent
2110 groupings. The symbol name is used in writing grammar rules. By convention,
2111 it should be all lower case.
2113 Symbol names can contain letters, digits (not at the beginning),
2114 underscores and periods. Periods make sense only in nonterminals.
2116 There are three ways of writing terminal symbols in the grammar:
2120 A @dfn{named token type} is written with an identifier, like an
2121 identifier in C. By convention, it should be all upper case. Each
2122 such name must be defined with a Bison declaration such as
2123 @code{%token}. @xref{Token Decl, ,Token Type Names}.
2126 @cindex character token
2127 @cindex literal token
2128 @cindex single-character literal
2129 A @dfn{character token type} (or @dfn{literal character token}) is
2130 written in the grammar using the same syntax used in C for character
2131 constants; for example, @code{'+'} is a character token type. A
2132 character token type doesn't need to be declared unless you need to
2133 specify its semantic value data type (@pxref{Value Type, ,Data Types of
2134 Semantic Values}), associativity, or precedence (@pxref{Precedence,
2135 ,Operator Precedence}).
2137 By convention, a character token type is used only to represent a
2138 token that consists of that particular character. Thus, the token
2139 type @code{'+'} is used to represent the character @samp{+} as a
2140 token. Nothing enforces this convention, but if you depart from it,
2141 your program will confuse other readers.
2143 All the usual escape sequences used in character literals in C can be
2144 used in Bison as well, but you must not use the null character as a
2145 character literal because its ASCII code, zero, is the code @code{yylex}
2146 returns for end-of-input (@pxref{Calling Convention, ,Calling Convention
2150 @cindex string token
2151 @cindex literal string token
2152 @cindex multicharacter literal
2153 A @dfn{literal string token} is written like a C string constant; for
2154 example, @code{"<="} is a literal string token. A literal string token
2155 doesn't need to be declared unless you need to specify its semantic
2156 value data type (@pxref{Value Type}), associativity, or precedence
2157 (@pxref{Precedence}).
2159 You can associate the literal string token with a symbolic name as an
2160 alias, using the @code{%token} declaration (@pxref{Token Decl, ,Token
2161 Declarations}). If you don't do that, the lexical analyzer has to
2162 retrieve the token number for the literal string token from the
2163 @code{yytname} table (@pxref{Calling Convention}).
2165 @strong{WARNING}: literal string tokens do not work in Yacc.
2167 By convention, a literal string token is used only to represent a token
2168 that consists of that particular string. Thus, you should use the token
2169 type @code{"<="} to represent the string @samp{<=} as a token. Bison
2170 does not enforce this convention, but if you depart from it, people who
2171 read your program will be confused.
2173 All the escape sequences used in string literals in C can be used in
2174 Bison as well. A literal string token must contain two or more
2175 characters; for a token containing just one character, use a character
2179 How you choose to write a terminal symbol has no effect on its
2180 grammatical meaning. That depends only on where it appears in rules and
2181 on when the parser function returns that symbol.
2183 The value returned by @code{yylex} is always one of the terminal symbols
2184 (or 0 for end-of-input). Whichever way you write the token type in the
2185 grammar rules, you write it the same way in the definition of @code{yylex}.
2186 The numeric code for a character token type is simply the ASCII code for
2187 the character, so @code{yylex} can use the identical character constant to
2188 generate the requisite code. Each named token type becomes a C macro in
2189 the parser file, so @code{yylex} can use the name to stand for the code.
2190 (This is why periods don't make sense in terminal symbols.)
2191 @xref{Calling Convention, ,Calling Convention for @code{yylex}}.
2193 If @code{yylex} is defined in a separate file, you need to arrange for the
2194 token-type macro definitions to be available there. Use the @samp{-d}
2195 option when you run Bison, so that it will write these macro definitions
2196 into a separate header file @file{@var{name}.tab.h} which you can include
2197 in the other source files that need it. @xref{Invocation, ,Invoking Bison}.
2199 The symbol @code{error} is a terminal symbol reserved for error recovery
2200 (@pxref{Error Recovery}); you shouldn't use it for any other purpose.
2201 In particular, @code{yylex} should never return this value.
2204 @section Syntax of Grammar Rules
2206 @cindex grammar rule syntax
2207 @cindex syntax of grammar rules
2209 A Bison grammar rule has the following general form:
2213 @var{result}: @var{components}@dots{}
2219 where @var{result} is the nonterminal symbol that this rule describes,
2220 and @var{components} are various terminal and nonterminal symbols that
2221 are put together by this rule (@pxref{Symbols}).
2233 says that two groupings of type @code{exp}, with a @samp{+} token in between,
2234 can be combined into a larger grouping of type @code{exp}.
2236 Whitespace in rules is significant only to separate symbols. You can add
2237 extra whitespace as you wish.
2239 Scattered among the components can be @var{actions} that determine
2240 the semantics of the rule. An action looks like this:
2243 @{@var{C statements}@}
2247 Usually there is only one action and it follows the components.
2251 Multiple rules for the same @var{result} can be written separately or can
2252 be joined with the vertical-bar character @samp{|} as follows:
2256 @var{result}: @var{rule1-components}@dots{}
2257 | @var{rule2-components}@dots{}
2265 @var{result}: @var{rule1-components}@dots{}
2266 | @var{rule2-components}@dots{}
2274 They are still considered distinct rules even when joined in this way.
2276 If @var{components} in a rule is empty, it means that @var{result} can
2277 match the empty string. For example, here is how to define a
2278 comma-separated sequence of zero or more @code{exp} groupings:
2295 It is customary to write a comment @samp{/* empty */} in each rule
2299 @section Recursive Rules
2300 @cindex recursive rule
2302 A rule is called @dfn{recursive} when its @var{result} nonterminal appears
2303 also on its right hand side. Nearly all Bison grammars need to use
2304 recursion, because that is the only way to define a sequence of any number
2305 of a particular thing. Consider this recursive definition of a
2306 comma-separated sequence of one or more expressions:
2316 @cindex left recursion
2317 @cindex right recursion
2319 Since the recursive use of @code{expseq1} is the leftmost symbol in the
2320 right hand side, we call this @dfn{left recursion}. By contrast, here
2321 the same construct is defined using @dfn{right recursion}:
2332 Any kind of sequence can be defined using either left recursion or
2333 right recursion, but you should always use left recursion, because it
2334 can parse a sequence of any number of elements with bounded stack
2335 space. Right recursion uses up space on the Bison stack in proportion
2336 to the number of elements in the sequence, because all the elements
2337 must be shifted onto the stack before the rule can be applied even
2338 once. @xref{Algorithm, ,The Bison Parser Algorithm }, for
2339 further explanation of this.
2341 @cindex mutual recursion
2342 @dfn{Indirect} or @dfn{mutual} recursion occurs when the result of the
2343 rule does not appear directly on its right hand side, but does appear
2344 in rules for other nonterminals which do appear on its right hand
2352 | primary '+' primary
2364 defines two mutually-recursive nonterminals, since each refers to the
2368 @section Defining Language Semantics
2369 @cindex defining language semantics
2370 @cindex language semantics, defining
2372 The grammar rules for a language determine only the syntax. The semantics
2373 are determined by the semantic values associated with various tokens and
2374 groupings, and by the actions taken when various groupings are recognized.
2376 For example, the calculator calculates properly because the value
2377 associated with each expression is the proper number; it adds properly
2378 because the action for the grouping @w{@samp{@var{x} + @var{y}}} is to add
2379 the numbers associated with @var{x} and @var{y}.
2382 * Value Type:: Specifying one data type for all semantic values.
2383 * Multiple Types:: Specifying several alternative data types.
2384 * Actions:: An action is the semantic definition of a grammar rule.
2385 * Action Types:: Specifying data types for actions to operate on.
2386 * Mid-Rule Actions:: Most actions go at the end of a rule.
2387 This says when, why and how to use the exceptional
2388 action in the middle of a rule.
2392 @subsection Data Types of Semantic Values
2393 @cindex semantic value type
2394 @cindex value type, semantic
2395 @cindex data types of semantic values
2396 @cindex default data type
2398 In a simple program it may be sufficient to use the same data type for
2399 the semantic values of all language constructs. This was true in the
2400 RPN and infix calculator examples (@pxref{RPN Calc, ,Reverse Polish
2401 Notation Calculator}).
2403 Bison's default is to use type @code{int} for all semantic values. To
2404 specify some other type, define @code{YYSTYPE} as a macro, like this:
2407 #define YYSTYPE double
2411 This macro definition must go in the prologue of the grammar file
2412 (@pxref{Grammar Outline, ,Outline of a Bison Grammar}).
2414 @node Multiple Types
2415 @subsection More Than One Value Type
2417 In most programs, you will need different data types for different kinds
2418 of tokens and groupings. For example, a numeric constant may need type
2419 @code{int} or @code{long}, while a string constant needs type @code{char *},
2420 and an identifier might need a pointer to an entry in the symbol table.
2422 To use more than one data type for semantic values in one parser, Bison
2423 requires you to do two things:
2427 Specify the entire collection of possible data types, with the
2428 @code{%union} Bison declaration (@pxref{Union Decl, ,The Collection of Value Types}).
2431 Choose one of those types for each symbol (terminal or nonterminal) for
2432 which semantic values are used. This is done for tokens with the
2433 @code{%token} Bison declaration (@pxref{Token Decl, ,Token Type Names})
2434 and for groupings with the @code{%type} Bison declaration (@pxref{Type
2435 Decl, ,Nonterminal Symbols}).
2444 An action accompanies a syntactic rule and contains C code to be executed
2445 each time an instance of that rule is recognized. The task of most actions
2446 is to compute a semantic value for the grouping built by the rule from the
2447 semantic values associated with tokens or smaller groupings.
2449 An action consists of C statements surrounded by braces, much like a
2450 compound statement in C. It can be placed at any position in the rule; it
2451 is executed at that position. Most rules have just one action at the end
2452 of the rule, following all the components. Actions in the middle of a rule
2453 are tricky and used only for special purposes (@pxref{Mid-Rule Actions, ,Actions in Mid-Rule}).
2455 The C code in an action can refer to the semantic values of the components
2456 matched by the rule with the construct @code{$@var{n}}, which stands for
2457 the value of the @var{n}th component. The semantic value for the grouping
2458 being constructed is @code{$$}. (Bison translates both of these constructs
2459 into array element references when it copies the actions into the parser
2462 Here is a typical example:
2473 This rule constructs an @code{exp} from two smaller @code{exp} groupings
2474 connected by a plus-sign token. In the action, @code{$1} and @code{$3}
2475 refer to the semantic values of the two component @code{exp} groupings,
2476 which are the first and third symbols on the right hand side of the rule.
2477 The sum is stored into @code{$$} so that it becomes the semantic value of
2478 the addition-expression just recognized by the rule. If there were a
2479 useful semantic value associated with the @samp{+} token, it could be
2480 referred to as @code{$2}.@refill
2482 @cindex default action
2483 If you don't specify an action for a rule, Bison supplies a default:
2484 @w{@code{$$ = $1}.} Thus, the value of the first symbol in the rule becomes
2485 the value of the whole rule. Of course, the default rule is valid only
2486 if the two data types match. There is no meaningful default action for
2487 an empty rule; every empty rule must have an explicit action unless the
2488 rule's value does not matter.
2490 @code{$@var{n}} with @var{n} zero or negative is allowed for reference
2491 to tokens and groupings on the stack @emph{before} those that match the
2492 current rule. This is a very risky practice, and to use it reliably
2493 you must be certain of the context in which the rule is applied. Here
2494 is a case in which you can use this reliably:
2498 foo: expr bar '+' expr @{ @dots{} @}
2499 | expr bar '-' expr @{ @dots{} @}
2505 @{ previous_expr = $0; @}
2510 As long as @code{bar} is used only in the fashion shown here, @code{$0}
2511 always refers to the @code{expr} which precedes @code{bar} in the
2512 definition of @code{foo}.
2515 @subsection Data Types of Values in Actions
2516 @cindex action data types
2517 @cindex data types in actions
2519 If you have chosen a single data type for semantic values, the @code{$$}
2520 and @code{$@var{n}} constructs always have that data type.
2522 If you have used @code{%union} to specify a variety of data types, then you
2523 must declare a choice among these types for each terminal or nonterminal
2524 symbol that can have a semantic value. Then each time you use @code{$$} or
2525 @code{$@var{n}}, its data type is determined by which symbol it refers to
2526 in the rule. In this example,@refill
2537 @code{$1} and @code{$3} refer to instances of @code{exp}, so they all
2538 have the data type declared for the nonterminal symbol @code{exp}. If
2539 @code{$2} were used, it would have the data type declared for the
2540 terminal symbol @code{'+'}, whatever that might be.@refill
2542 Alternatively, you can specify the data type when you refer to the value,
2543 by inserting @samp{<@var{type}>} after the @samp{$} at the beginning of the
2544 reference. For example, if you have defined types as shown here:
2556 then you can write @code{$<itype>1} to refer to the first subunit of the
2557 rule as an integer, or @code{$<dtype>1} to refer to it as a double.
2559 @node Mid-Rule Actions
2560 @subsection Actions in Mid-Rule
2561 @cindex actions in mid-rule
2562 @cindex mid-rule actions
2564 Occasionally it is useful to put an action in the middle of a rule.
2565 These actions are written just like usual end-of-rule actions, but they
2566 are executed before the parser even recognizes the following components.
2568 A mid-rule action may refer to the components preceding it using
2569 @code{$@var{n}}, but it may not refer to subsequent components because
2570 it is run before they are parsed.
2572 The mid-rule action itself counts as one of the components of the rule.
2573 This makes a difference when there is another action later in the same rule
2574 (and usually there is another at the end): you have to count the actions
2575 along with the symbols when working out which number @var{n} to use in
2578 The mid-rule action can also have a semantic value. The action can set
2579 its value with an assignment to @code{$$}, and actions later in the rule
2580 can refer to the value using @code{$@var{n}}. Since there is no symbol
2581 to name the action, there is no way to declare a data type for the value
2582 in advance, so you must use the @samp{$<@dots{}>@var{n}} construct to
2583 specify a data type each time you refer to this value.
2585 There is no way to set the value of the entire rule with a mid-rule
2586 action, because assignments to @code{$$} do not have that effect. The
2587 only way to set the value for the entire rule is with an ordinary action
2588 at the end of the rule.
2590 Here is an example from a hypothetical compiler, handling a @code{let}
2591 statement that looks like @samp{let (@var{variable}) @var{statement}} and
2592 serves to create a variable named @var{variable} temporarily for the
2593 duration of @var{statement}. To parse this construct, we must put
2594 @var{variable} into the symbol table while @var{statement} is parsed, then
2595 remove it afterward. Here is how it is done:
2599 stmt: LET '(' var ')'
2600 @{ $<context>$ = push_context ();
2601 declare_variable ($3); @}
2603 pop_context ($<context>5); @}
2608 As soon as @samp{let (@var{variable})} has been recognized, the first
2609 action is run. It saves a copy of the current semantic context (the
2610 list of accessible variables) as its semantic value, using alternative
2611 @code{context} in the data-type union. Then it calls
2612 @code{declare_variable} to add the new variable to that list. Once the
2613 first action is finished, the embedded statement @code{stmt} can be
2614 parsed. Note that the mid-rule action is component number 5, so the
2615 @samp{stmt} is component number 6.
2617 After the embedded statement is parsed, its semantic value becomes the
2618 value of the entire @code{let}-statement. Then the semantic value from the
2619 earlier action is used to restore the prior list of variables. This
2620 removes the temporary @code{let}-variable from the list so that it won't
2621 appear to exist while the rest of the program is parsed.
2623 Taking action before a rule is completely recognized often leads to
2624 conflicts since the parser must commit to a parse in order to execute the
2625 action. For example, the following two rules, without mid-rule actions,
2626 can coexist in a working parser because the parser can shift the open-brace
2627 token and look at what follows before deciding whether there is a
2632 compound: '@{' declarations statements '@}'
2633 | '@{' statements '@}'
2639 But when we add a mid-rule action as follows, the rules become nonfunctional:
2643 compound: @{ prepare_for_local_variables (); @}
2644 '@{' declarations statements '@}'
2647 | '@{' statements '@}'
2653 Now the parser is forced to decide whether to run the mid-rule action
2654 when it has read no farther than the open-brace. In other words, it
2655 must commit to using one rule or the other, without sufficient
2656 information to do it correctly. (The open-brace token is what is called
2657 the @dfn{look-ahead} token at this time, since the parser is still
2658 deciding what to do about it. @xref{Look-Ahead, ,Look-Ahead Tokens}.)
2660 You might think that you could correct the problem by putting identical
2661 actions into the two rules, like this:
2665 compound: @{ prepare_for_local_variables (); @}
2666 '@{' declarations statements '@}'
2667 | @{ prepare_for_local_variables (); @}
2668 '@{' statements '@}'
2674 But this does not help, because Bison does not realize that the two actions
2675 are identical. (Bison never tries to understand the C code in an action.)
2677 If the grammar is such that a declaration can be distinguished from a
2678 statement by the first token (which is true in C), then one solution which
2679 does work is to put the action after the open-brace, like this:
2683 compound: '@{' @{ prepare_for_local_variables (); @}
2684 declarations statements '@}'
2685 | '@{' statements '@}'
2691 Now the first token of the following declaration or statement,
2692 which would in any case tell Bison which rule to use, can still do so.
2694 Another solution is to bury the action inside a nonterminal symbol which
2695 serves as a subroutine:
2699 subroutine: /* empty */
2700 @{ prepare_for_local_variables (); @}
2706 compound: subroutine
2707 '@{' declarations statements '@}'
2709 '@{' statements '@}'
2715 Now Bison can execute the action in the rule for @code{subroutine} without
2716 deciding which rule for @code{compound} it will eventually use. Note that
2717 the action is now at the end of its rule. Any mid-rule action can be
2718 converted to an end-of-rule action in this way, and this is what Bison
2719 actually does to implement mid-rule actions.
2722 @section Tracking Locations
2724 @cindex textual position
2725 @cindex position, textual
2727 Though grammar rules and semantic actions are enough to write a fully
2728 functional parser, it can be useful to process some additionnal informations,
2729 especially symbol locations.
2731 @c (terminal or not) ?
2733 The way locations are handled is defined by providing a data type, and actions
2734 to take when rules are matched.
2737 * Location Type:: Specifying a data type for locations.
2738 * Actions and Locations:: Using locations in actions.
2739 * Location Default Action:: Defining a general way to compute locations.
2743 @subsection Data Type of Locations
2744 @cindex data type of locations
2745 @cindex default location type
2747 Defining a data type for locations is much simpler than for semantic values,
2748 since all tokens and groupings always use the same type.
2750 The type of locations is specified by defining a macro called @code{YYLTYPE}.
2751 When @code{YYLTYPE} is not defined, Bison uses a default structure type with
2764 @node Actions and Locations
2765 @subsection Actions and Locations
2766 @cindex location actions
2767 @cindex actions, location
2771 Actions are not only useful for defining language semantics, but also for
2772 describing the behavior of the output parser with locations.
2774 The most obvious way for building locations of syntactic groupings is very
2775 similar to the way semantic values are computed. In a given rule, several
2776 constructs can be used to access the locations of the elements being matched.
2777 The location of the @var{n}th component of the right hand side is
2778 @code{@@@var{n}}, while the location of the left hand side grouping is
2781 Here is a basic example using the default data type for locations:
2788 @@$.first_column = @@1.first_column;
2789 @@$.first_line = @@1.first_line;
2790 @@$.last_column = @@3.last_column;
2791 @@$.last_line = @@3.last_line;
2797 printf("Division by zero, l%d,c%d-l%d,c%d",
2798 @@3.first_line, @@3.first_column,
2799 @@3.last_line, @@3.last_column);
2805 As for semantic values, there is a default action for locations that is
2806 run each time a rule is matched. It sets the beginning of @code{@@$} to the
2807 beginning of the first symbol, and the end of @code{@@$} to the end of the
2810 With this default action, the location tracking can be fully automatic. The
2811 example above simply rewrites this way:
2823 printf("Division by zero, l%d,c%d-l%d,c%d",
2824 @@3.first_line, @@3.first_column,
2825 @@3.last_line, @@3.last_column);
2831 @node Location Default Action
2832 @subsection Default Action for Locations
2833 @vindex YYLLOC_DEFAULT
2835 Actually, actions are not the best place to compute locations. Since locations
2836 are much more general than semantic values, there is room in the output parser
2837 to redefine the default action to take for each rule. The
2838 @code{YYLLOC_DEFAULT} macro is called each time a rule is matched, before the
2839 associated action is run.
2841 Most of the time, this macro is general enough to suppress location
2842 dedicated code from semantic actions.
2844 The @code{YYLLOC_DEFAULT} macro takes three parameters. The first one is
2845 the location of the grouping (the result of the computation). The second one
2846 is an array holding locations of all right hand side elements of the rule
2847 being matched. The last one is the size of the right hand side rule.
2849 By default, it is defined this way:
2853 #define YYLLOC_DEFAULT(Current, Rhs, N) \
2854 Current.last_line = Rhs[N].last_line; \
2855 Current.last_column = Rhs[N].last_column;
2859 When defining @code{YYLLOC_DEFAULT}, you should consider that:
2863 All arguments are free of side-effects. However, only the first one (the
2864 result) should be modified by @code{YYLLOC_DEFAULT}.
2867 Before @code{YYLLOC_DEFAULT} is executed, the output parser sets @code{@@$}
2871 For consistency with semantic actions, valid indexes for the location array
2872 range from 1 to @var{n}.
2876 @section Bison Declarations
2877 @cindex declarations, Bison
2878 @cindex Bison declarations
2880 The @dfn{Bison declarations} section of a Bison grammar defines the symbols
2881 used in formulating the grammar and the data types of semantic values.
2884 All token type names (but not single-character literal tokens such as
2885 @code{'+'} and @code{'*'}) must be declared. Nonterminal symbols must be
2886 declared if you need to specify which data type to use for the semantic
2887 value (@pxref{Multiple Types, ,More Than One Value Type}).
2889 The first rule in the file also specifies the start symbol, by default.
2890 If you want some other symbol to be the start symbol, you must declare
2891 it explicitly (@pxref{Language and Grammar, ,Languages and Context-Free Grammars}).
2894 * Token Decl:: Declaring terminal symbols.
2895 * Precedence Decl:: Declaring terminals with precedence and associativity.
2896 * Union Decl:: Declaring the set of all semantic value types.
2897 * Type Decl:: Declaring the choice of type for a nonterminal symbol.
2898 * Expect Decl:: Suppressing warnings about shift/reduce conflicts.
2899 * Start Decl:: Specifying the start symbol.
2900 * Pure Decl:: Requesting a reentrant parser.
2901 * Decl Summary:: Table of all Bison declarations.
2905 @subsection Token Type Names
2906 @cindex declaring token type names
2907 @cindex token type names, declaring
2908 @cindex declaring literal string tokens
2911 The basic way to declare a token type name (terminal symbol) is as follows:
2917 Bison will convert this into a @code{#define} directive in
2918 the parser, so that the function @code{yylex} (if it is in this file)
2919 can use the name @var{name} to stand for this token type's code.
2921 Alternatively, you can use @code{%left}, @code{%right}, or
2922 @code{%nonassoc} instead of @code{%token}, if you wish to specify
2923 associativity and precedence. @xref{Precedence Decl, ,Operator
2926 You can explicitly specify the numeric code for a token type by appending
2927 an integer value in the field immediately following the token name:
2934 It is generally best, however, to let Bison choose the numeric codes for
2935 all token types. Bison will automatically select codes that don't conflict
2936 with each other or with ASCII characters.
2938 In the event that the stack type is a union, you must augment the
2939 @code{%token} or other token declaration to include the data type
2940 alternative delimited by angle-brackets (@pxref{Multiple Types, ,More Than One Value Type}).
2946 %union @{ /* define stack type */
2950 %token <val> NUM /* define token NUM and its type */
2954 You can associate a literal string token with a token type name by
2955 writing the literal string at the end of a @code{%token}
2956 declaration which declares the name. For example:
2963 For example, a grammar for the C language might specify these names with
2964 equivalent literal string tokens:
2967 %token <operator> OR "||"
2968 %token <operator> LE 134 "<="
2973 Once you equate the literal string and the token name, you can use them
2974 interchangeably in further declarations or the grammar rules. The
2975 @code{yylex} function can use the token name or the literal string to
2976 obtain the token type code number (@pxref{Calling Convention}).
2978 @node Precedence Decl
2979 @subsection Operator Precedence
2980 @cindex precedence declarations
2981 @cindex declaring operator precedence
2982 @cindex operator precedence, declaring
2984 Use the @code{%left}, @code{%right} or @code{%nonassoc} declaration to
2985 declare a token and specify its precedence and associativity, all at
2986 once. These are called @dfn{precedence declarations}.
2987 @xref{Precedence, ,Operator Precedence}, for general information on operator precedence.
2989 The syntax of a precedence declaration is the same as that of
2990 @code{%token}: either
2993 %left @var{symbols}@dots{}
3000 %left <@var{type}> @var{symbols}@dots{}
3003 And indeed any of these declarations serves the purposes of @code{%token}.
3004 But in addition, they specify the associativity and relative precedence for
3005 all the @var{symbols}:
3009 The associativity of an operator @var{op} determines how repeated uses
3010 of the operator nest: whether @samp{@var{x} @var{op} @var{y} @var{op}
3011 @var{z}} is parsed by grouping @var{x} with @var{y} first or by
3012 grouping @var{y} with @var{z} first. @code{%left} specifies
3013 left-associativity (grouping @var{x} with @var{y} first) and
3014 @code{%right} specifies right-associativity (grouping @var{y} with
3015 @var{z} first). @code{%nonassoc} specifies no associativity, which
3016 means that @samp{@var{x} @var{op} @var{y} @var{op} @var{z}} is
3017 considered a syntax error.
3020 The precedence of an operator determines how it nests with other operators.
3021 All the tokens declared in a single precedence declaration have equal
3022 precedence and nest together according to their associativity.
3023 When two tokens declared in different precedence declarations associate,
3024 the one declared later has the higher precedence and is grouped first.
3028 @subsection The Collection of Value Types
3029 @cindex declaring value types
3030 @cindex value types, declaring
3033 The @code{%union} declaration specifies the entire collection of possible
3034 data types for semantic values. The keyword @code{%union} is followed by a
3035 pair of braces containing the same thing that goes inside a @code{union} in
3050 This says that the two alternative types are @code{double} and @code{symrec
3051 *}. They are given names @code{val} and @code{tptr}; these names are used
3052 in the @code{%token} and @code{%type} declarations to pick one of the types
3053 for a terminal or nonterminal symbol (@pxref{Type Decl, ,Nonterminal Symbols}).
3055 Note that, unlike making a @code{union} declaration in C, you do not write
3056 a semicolon after the closing brace.
3059 @subsection Nonterminal Symbols
3060 @cindex declaring value types, nonterminals
3061 @cindex value types, nonterminals, declaring
3065 When you use @code{%union} to specify multiple value types, you must
3066 declare the value type of each nonterminal symbol for which values are
3067 used. This is done with a @code{%type} declaration, like this:
3070 %type <@var{type}> @var{nonterminal}@dots{}
3074 Here @var{nonterminal} is the name of a nonterminal symbol, and @var{type}
3075 is the name given in the @code{%union} to the alternative that you want
3076 (@pxref{Union Decl, ,The Collection of Value Types}). You can give any number of nonterminal symbols in
3077 the same @code{%type} declaration, if they have the same value type. Use
3078 spaces to separate the symbol names.
3080 You can also declare the value type of a terminal symbol. To do this,
3081 use the same @code{<@var{type}>} construction in a declaration for the
3082 terminal symbol. All kinds of token declarations allow
3083 @code{<@var{type}>}.
3086 @subsection Suppressing Conflict Warnings
3087 @cindex suppressing conflict warnings
3088 @cindex preventing warnings about conflicts
3089 @cindex warnings, preventing
3090 @cindex conflicts, suppressing warnings of
3093 Bison normally warns if there are any conflicts in the grammar
3094 (@pxref{Shift/Reduce, ,Shift/Reduce Conflicts}), but most real grammars
3095 have harmless shift/reduce conflicts which are resolved in a predictable
3096 way and would be difficult to eliminate. It is desirable to suppress
3097 the warning about these conflicts unless the number of conflicts
3098 changes. You can do this with the @code{%expect} declaration.
3100 The declaration looks like this:
3106 Here @var{n} is a decimal integer. The declaration says there should be
3107 no warning if there are @var{n} shift/reduce conflicts and no
3108 reduce/reduce conflicts. An error, instead of the usual warning, is
3109 given if there are either more or fewer conflicts, or if there are any
3110 reduce/reduce conflicts.
3112 In general, using @code{%expect} involves these steps:
3116 Compile your grammar without @code{%expect}. Use the @samp{-v} option
3117 to get a verbose list of where the conflicts occur. Bison will also
3118 print the number of conflicts.
3121 Check each of the conflicts to make sure that Bison's default
3122 resolution is what you really want. If not, rewrite the grammar and
3123 go back to the beginning.
3126 Add an @code{%expect} declaration, copying the number @var{n} from the
3127 number which Bison printed.
3130 Now Bison will stop annoying you about the conflicts you have checked, but
3131 it will warn you again if changes in the grammar result in additional
3135 @subsection The Start-Symbol
3136 @cindex declaring the start symbol
3137 @cindex start symbol, declaring
3138 @cindex default start symbol
3141 Bison assumes by default that the start symbol for the grammar is the first
3142 nonterminal specified in the grammar specification section. The programmer
3143 may override this restriction with the @code{%start} declaration as follows:
3150 @subsection A Pure (Reentrant) Parser
3151 @cindex reentrant parser
3153 @findex %pure_parser
3155 A @dfn{reentrant} program is one which does not alter in the course of
3156 execution; in other words, it consists entirely of @dfn{pure} (read-only)
3157 code. Reentrancy is important whenever asynchronous execution is possible;
3158 for example, a non-reentrant program may not be safe to call from a signal
3159 handler. In systems with multiple threads of control, a non-reentrant
3160 program must be called only within interlocks.
3162 Normally, Bison generates a parser which is not reentrant. This is
3163 suitable for most uses, and it permits compatibility with YACC. (The
3164 standard YACC interfaces are inherently nonreentrant, because they use
3165 statically allocated variables for communication with @code{yylex},
3166 including @code{yylval} and @code{yylloc}.)
3168 Alternatively, you can generate a pure, reentrant parser. The Bison
3169 declaration @code{%pure_parser} says that you want the parser to be
3170 reentrant. It looks like this:
3176 The result is that the communication variables @code{yylval} and
3177 @code{yylloc} become local variables in @code{yyparse}, and a different
3178 calling convention is used for the lexical analyzer function
3179 @code{yylex}. @xref{Pure Calling, ,Calling Conventions for Pure
3180 Parsers}, for the details of this. The variable @code{yynerrs} also
3181 becomes local in @code{yyparse} (@pxref{Error Reporting, ,The Error
3182 Reporting Function @code{yyerror}}). The convention for calling
3183 @code{yyparse} itself is unchanged.
3185 Whether the parser is pure has nothing to do with the grammar rules.
3186 You can generate either a pure parser or a nonreentrant parser from any
3190 @subsection Bison Declaration Summary
3191 @cindex Bison declaration summary
3192 @cindex declaration summary
3193 @cindex summary, Bison declaration
3195 Here is a summary of the declarations used to define a grammar:
3199 Declare the collection of data types that semantic values may have
3200 (@pxref{Union Decl, ,The Collection of Value Types}).
3203 Declare a terminal symbol (token type name) with no precedence
3204 or associativity specified (@pxref{Token Decl, ,Token Type Names}).
3207 Declare a terminal symbol (token type name) that is right-associative
3208 (@pxref{Precedence Decl, ,Operator Precedence}).
3211 Declare a terminal symbol (token type name) that is left-associative
3212 (@pxref{Precedence Decl, ,Operator Precedence}).
3215 Declare a terminal symbol (token type name) that is nonassociative
3216 (using it in a way that would be associative is a syntax error)
3217 (@pxref{Precedence Decl, ,Operator Precedence}).
3220 Declare the type of semantic values for a nonterminal symbol
3221 (@pxref{Type Decl, ,Nonterminal Symbols}).
3224 Specify the grammar's start symbol (@pxref{Start Decl, ,The
3228 Declare the expected number of shift-reduce conflicts
3229 (@pxref{Expect Decl, ,Suppressing Conflict Warnings}).
3234 In order to change the behavior of @command{bison}, use the following
3239 Output a definition of the macro @code{YYDEBUG} into the parser file, so
3240 that the debugging facilities are compiled. @xref{Debugging, ,Debugging
3244 Write an extra output file containing macro definitions for the token
3245 type names defined in the grammar and the semantic value type
3246 @code{YYSTYPE}, as well as a few @code{extern} variable declarations.
3248 If the parser output file is named @file{@var{name}.c} then this file
3249 is named @file{@var{name}.h}.@refill
3251 This output file is essential if you wish to put the definition of
3252 @code{yylex} in a separate source file, because @code{yylex} needs to
3253 be able to refer to token type codes and the variable
3254 @code{yylval}. @xref{Token Values, ,Semantic Values of Tokens}.@refill
3256 @item %file-prefix="@var{prefix}"
3257 Specify a prefix to use for all Bison output file names. The names are
3258 chosen as if the input file were named @file{@var{prefix}.y}.
3260 @c @item %header_extension
3261 @c Specify the extension of the parser header file generated when
3262 @c @code{%define} or @samp{-d} are used.
3264 @c For example, a grammar file named @file{foo.ypp} and containing a
3265 @c @code{%header_extension .hh} directive will produce a header file
3266 @c named @file{foo.tab.hh}
3269 Generate the code processing the locations (@pxref{Action Features,
3270 ,Special Features for Use in Actions}). This mode is enabled as soon as
3271 the grammar uses the special @samp{@@@var{n}} tokens, but if your
3272 grammar does not use it, using @samp{%locations} allows for more
3273 accurate parse error messages.
3275 @item %name-prefix="@var{prefix}"
3276 Rename the external symbols used in the parser so that they start with
3277 @var{prefix} instead of @samp{yy}. The precise list of symbols renamed
3278 is @code{yyparse}, @code{yylex}, @code{yyerror}, @code{yynerrs},
3279 @code{yylval}, @code{yychar} and @code{yydebug}. For example, if you
3280 use @samp{%name-prefix="c_"}, the names become @code{c_parse},
3281 @code{c_lex}, and so on. @xref{Multiple Parsers, ,Multiple Parsers in
3285 Do not include any C code in the parser file; generate tables only. The
3286 parser file contains just @code{#define} directives and static variable
3289 This option also tells Bison to write the C code for the grammar actions
3290 into a file named @file{@var{filename}.act}, in the form of a
3291 brace-surrounded body fit for a @code{switch} statement.
3294 Don't generate any @code{#line} preprocessor commands in the parser
3295 file. Ordinarily Bison writes these commands in the parser file so that
3296 the C compiler and debuggers will associate errors and object code with
3297 your source file (the grammar file). This directive causes them to
3298 associate errors with the parser file, treating it an independent source
3299 file in its own right.
3301 @item %output="@var{filename}"
3302 Specify the @var{filename} for the parser file.
3305 Request a pure (reentrant) parser program (@pxref{Pure Decl, ,A Pure
3306 (Reentrant) Parser}).
3308 @c @item %source_extension
3309 @c Specify the extension of the parser output file.
3311 @c For example, a grammar file named @file{foo.yy} and containing a
3312 @c @code{%source_extension .cpp} directive will produce a parser file
3313 @c named @file{foo.tab.cpp}
3316 Generate an array of token names in the parser file. The name of the
3317 array is @code{yytname}; @code{yytname[@var{i}]} is the name of the
3318 token whose internal Bison token code number is @var{i}. The first three
3319 elements of @code{yytname} are always @code{"$"}, @code{"error"}, and
3320 @code{"$illegal"}; after these come the symbols defined in the grammar
3323 For single-character literal tokens and literal string tokens, the name
3324 in the table includes the single-quote or double-quote characters: for
3325 example, @code{"'+'"} is a single-character literal and @code{"\"<=\""}
3326 is a literal string token. All the characters of the literal string
3327 token appear verbatim in the string found in the table; even
3328 double-quote characters are not escaped. For example, if the token
3329 consists of three characters @samp{*"*}, its string in @code{yytname}
3330 contains @samp{"*"*"}. (In C, that would be written as
3333 When you specify @code{%token_table}, Bison also generates macro
3334 definitions for macros @code{YYNTOKENS}, @code{YYNNTS}, and
3335 @code{YYNRULES}, and @code{YYNSTATES}:
3339 The highest token number, plus one.
3341 The number of nonterminal symbols.
3343 The number of grammar rules,
3345 The number of parser states (@pxref{Parser States}).
3349 Write an extra output file containing verbose descriptions of the
3350 parser states and what is done for each type of look-ahead token in
3353 This file also describes all the conflicts, both those resolved by
3354 operator precedence and the unresolved ones.
3356 The file's name is made by removing @samp{.tab.c} or @samp{.c} from
3357 the parser output file name, and adding @samp{.output} instead.@refill
3359 Therefore, if the input file is @file{foo.y}, then the parser file is
3360 called @file{foo.tab.c} by default. As a consequence, the verbose
3361 output file is called @file{foo.output}.@refill
3364 @itemx %fixed-output-files
3365 Pretend the option @option{--yacc} was given, i.e., imitate Yacc,
3366 including its naming conventions. @xref{Bison Options}, for more.
3372 @node Multiple Parsers
3373 @section Multiple Parsers in the Same Program
3375 Most programs that use Bison parse only one language and therefore contain
3376 only one Bison parser. But what if you want to parse more than one
3377 language with the same program? Then you need to avoid a name conflict
3378 between different definitions of @code{yyparse}, @code{yylval}, and so on.
3380 The easy way to do this is to use the option @samp{-p @var{prefix}}
3381 (@pxref{Invocation, ,Invoking Bison}). This renames the interface functions and
3382 variables of the Bison parser to start with @var{prefix} instead of
3383 @samp{yy}. You can use this to give each parser distinct names that do
3386 The precise list of symbols renamed is @code{yyparse}, @code{yylex},
3387 @code{yyerror}, @code{yynerrs}, @code{yylval}, @code{yychar} and
3388 @code{yydebug}. For example, if you use @samp{-p c}, the names become
3389 @code{cparse}, @code{clex}, and so on.
3391 @strong{All the other variables and macros associated with Bison are not
3392 renamed.} These others are not global; there is no conflict if the same
3393 name is used in different parsers. For example, @code{YYSTYPE} is not
3394 renamed, but defining this in different ways in different parsers causes
3395 no trouble (@pxref{Value Type, ,Data Types of Semantic Values}).
3397 The @samp{-p} option works by adding macro definitions to the beginning
3398 of the parser source file, defining @code{yyparse} as
3399 @code{@var{prefix}parse}, and so on. This effectively substitutes one
3400 name for the other in the entire parser file.
3403 @chapter Parser C-Language Interface
3404 @cindex C-language interface
3407 The Bison parser is actually a C function named @code{yyparse}. Here we
3408 describe the interface conventions of @code{yyparse} and the other
3409 functions that it needs to use.
3411 Keep in mind that the parser uses many C identifiers starting with
3412 @samp{yy} and @samp{YY} for internal purposes. If you use such an
3413 identifier (aside from those in this manual) in an action or in epilogue
3414 in the grammar file, you are likely to run into trouble.
3417 * Parser Function:: How to call @code{yyparse} and what it returns.
3418 * Lexical:: You must supply a function @code{yylex}
3420 * Error Reporting:: You must supply a function @code{yyerror}.
3421 * Action Features:: Special features for use in actions.
3424 @node Parser Function
3425 @section The Parser Function @code{yyparse}
3428 You call the function @code{yyparse} to cause parsing to occur. This
3429 function reads tokens, executes actions, and ultimately returns when it
3430 encounters end-of-input or an unrecoverable syntax error. You can also
3431 write an action which directs @code{yyparse} to return immediately
3432 without reading further.
3434 The value returned by @code{yyparse} is 0 if parsing was successful (return
3435 is due to end-of-input).
3437 The value is 1 if parsing failed (return is due to a syntax error).
3439 In an action, you can cause immediate return from @code{yyparse} by using
3445 Return immediately with value 0 (to report success).
3449 Return immediately with value 1 (to report failure).
3453 @section The Lexical Analyzer Function @code{yylex}
3455 @cindex lexical analyzer
3457 The @dfn{lexical analyzer} function, @code{yylex}, recognizes tokens from
3458 the input stream and returns them to the parser. Bison does not create
3459 this function automatically; you must write it so that @code{yyparse} can
3460 call it. The function is sometimes referred to as a lexical scanner.
3462 In simple programs, @code{yylex} is often defined at the end of the Bison
3463 grammar file. If @code{yylex} is defined in a separate source file, you
3464 need to arrange for the token-type macro definitions to be available there.
3465 To do this, use the @samp{-d} option when you run Bison, so that it will
3466 write these macro definitions into a separate header file
3467 @file{@var{name}.tab.h} which you can include in the other source files
3468 that need it. @xref{Invocation, ,Invoking Bison}.@refill
3471 * Calling Convention:: How @code{yyparse} calls @code{yylex}.
3472 * Token Values:: How @code{yylex} must return the semantic value
3473 of the token it has read.
3474 * Token Positions:: How @code{yylex} must return the text position
3475 (line number, etc.) of the token, if the
3477 * Pure Calling:: How the calling convention differs
3478 in a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}).
3481 @node Calling Convention
3482 @subsection Calling Convention for @code{yylex}
3484 The value that @code{yylex} returns must be the numeric code for the type
3485 of token it has just found, or 0 for end-of-input.
3487 When a token is referred to in the grammar rules by a name, that name
3488 in the parser file becomes a C macro whose definition is the proper
3489 numeric code for that token type. So @code{yylex} can use the name
3490 to indicate that type. @xref{Symbols}.
3492 When a token is referred to in the grammar rules by a character literal,
3493 the numeric code for that character is also the code for the token type.
3494 So @code{yylex} can simply return that character code. The null character
3495 must not be used this way, because its code is zero and that is what
3496 signifies end-of-input.
3498 Here is an example showing these things:
3505 if (c == EOF) /* Detect end of file. */
3508 if (c == '+' || c == '-')
3509 return c; /* Assume token type for `+' is '+'. */
3511 return INT; /* Return the type of the token. */
3517 This interface has been designed so that the output from the @code{lex}
3518 utility can be used without change as the definition of @code{yylex}.
3520 If the grammar uses literal string tokens, there are two ways that
3521 @code{yylex} can determine the token type codes for them:
3525 If the grammar defines symbolic token names as aliases for the
3526 literal string tokens, @code{yylex} can use these symbolic names like
3527 all others. In this case, the use of the literal string tokens in
3528 the grammar file has no effect on @code{yylex}.
3531 @code{yylex} can find the multicharacter token in the @code{yytname}
3532 table. The index of the token in the table is the token type's code.
3533 The name of a multicharacter token is recorded in @code{yytname} with a
3534 double-quote, the token's characters, and another double-quote. The
3535 token's characters are not escaped in any way; they appear verbatim in
3536 the contents of the string in the table.
3538 Here's code for looking up a token in @code{yytname}, assuming that the
3539 characters of the token are stored in @code{token_buffer}.
3542 for (i = 0; i < YYNTOKENS; i++)
3545 && yytname[i][0] == '"'
3546 && strncmp (yytname[i] + 1, token_buffer,
3547 strlen (token_buffer))
3548 && yytname[i][strlen (token_buffer) + 1] == '"'
3549 && yytname[i][strlen (token_buffer) + 2] == 0)
3554 The @code{yytname} table is generated only if you use the
3555 @code{%token_table} declaration. @xref{Decl Summary}.
3559 @subsection Semantic Values of Tokens
3562 In an ordinary (non-reentrant) parser, the semantic value of the token must
3563 be stored into the global variable @code{yylval}. When you are using
3564 just one data type for semantic values, @code{yylval} has that type.
3565 Thus, if the type is @code{int} (the default), you might write this in
3571 yylval = value; /* Put value onto Bison stack. */
3572 return INT; /* Return the type of the token. */
3577 When you are using multiple data types, @code{yylval}'s type is a union
3578 made from the @code{%union} declaration (@pxref{Union Decl, ,The Collection of Value Types}). So when
3579 you store a token's value, you must use the proper member of the union.
3580 If the @code{%union} declaration looks like this:
3593 then the code in @code{yylex} might look like this:
3598 yylval.intval = value; /* Put value onto Bison stack. */
3599 return INT; /* Return the type of the token. */
3604 @node Token Positions
3605 @subsection Textual Positions of Tokens
3608 If you are using the @samp{@@@var{n}}-feature (@pxref{Locations, ,
3609 Tracking Locations}) in actions to keep track of the
3610 textual locations of tokens and groupings, then you must provide this
3611 information in @code{yylex}. The function @code{yyparse} expects to
3612 find the textual location of a token just parsed in the global variable
3613 @code{yylloc}. So @code{yylex} must store the proper data in that
3616 By default, the value of @code{yylloc} is a structure and you need only
3617 initialize the members that are going to be used by the actions. The
3618 four members are called @code{first_line}, @code{first_column},
3619 @code{last_line} and @code{last_column}. Note that the use of this
3620 feature makes the parser noticeably slower.
3623 The data type of @code{yylloc} has the name @code{YYLTYPE}.
3626 @subsection Calling Conventions for Pure Parsers
3628 When you use the Bison declaration @code{%pure_parser} to request a
3629 pure, reentrant parser, the global communication variables @code{yylval}
3630 and @code{yylloc} cannot be used. (@xref{Pure Decl, ,A Pure (Reentrant)
3631 Parser}.) In such parsers the two global variables are replaced by
3632 pointers passed as arguments to @code{yylex}. You must declare them as
3633 shown here, and pass the information back by storing it through those
3638 yylex (YYSTYPE *lvalp, YYLTYPE *llocp)
3641 *lvalp = value; /* Put value onto Bison stack. */
3642 return INT; /* Return the type of the token. */
3647 If the grammar file does not use the @samp{@@} constructs to refer to
3648 textual positions, then the type @code{YYLTYPE} will not be defined. In
3649 this case, omit the second argument; @code{yylex} will be called with
3652 @vindex YYPARSE_PARAM
3653 If you use a reentrant parser, you can optionally pass additional
3654 parameter information to it in a reentrant way. To do so, define the
3655 macro @code{YYPARSE_PARAM} as a variable name. This modifies the
3656 @code{yyparse} function to accept one argument, of type @code{void *},
3659 When you call @code{yyparse}, pass the address of an object, casting the
3660 address to @code{void *}. The grammar actions can refer to the contents
3661 of the object by casting the pointer value back to its proper type and
3662 then dereferencing it. Here's an example. Write this in the parser:
3666 struct parser_control
3672 #define YYPARSE_PARAM parm
3677 Then call the parser like this:
3680 struct parser_control
3689 struct parser_control foo;
3690 @dots{} /* @r{Store proper data in @code{foo}.} */
3691 value = yyparse ((void *) &foo);
3697 In the grammar actions, use expressions like this to refer to the data:
3700 ((struct parser_control *) parm)->randomness
3704 If you wish to pass the additional parameter data to @code{yylex},
3705 define the macro @code{YYLEX_PARAM} just like @code{YYPARSE_PARAM}, as
3710 struct parser_control
3716 #define YYPARSE_PARAM parm
3717 #define YYLEX_PARAM parm
3721 You should then define @code{yylex} to accept one additional
3722 argument---the value of @code{parm}. (This makes either two or three
3723 arguments in total, depending on whether an argument of type
3724 @code{YYLTYPE} is passed.) You can declare the argument as a pointer to
3725 the proper object type, or you can declare it as @code{void *} and
3726 access the contents as shown above.
3728 You can use @samp{%pure_parser} to request a reentrant parser without
3729 also using @code{YYPARSE_PARAM}. Then you should call @code{yyparse}
3730 with no arguments, as usual.
3732 @node Error Reporting
3733 @section The Error Reporting Function @code{yyerror}
3734 @cindex error reporting function
3737 @cindex syntax error
3739 The Bison parser detects a @dfn{parse error} or @dfn{syntax error}
3740 whenever it reads a token which cannot satisfy any syntax rule. An
3741 action in the grammar can also explicitly proclaim an error, using the
3742 macro @code{YYERROR} (@pxref{Action Features, ,Special Features for Use
3745 The Bison parser expects to report the error by calling an error
3746 reporting function named @code{yyerror}, which you must supply. It is
3747 called by @code{yyparse} whenever a syntax error is found, and it
3748 receives one argument. For a parse error, the string is normally
3749 @w{@code{"parse error"}}.
3751 @findex YYERROR_VERBOSE
3752 If you define the macro @code{YYERROR_VERBOSE} in the Bison declarations
3753 section (@pxref{Bison Declarations, ,The Bison Declarations Section}),
3754 then Bison provides a more verbose and specific error message string
3755 instead of just plain @w{@code{"parse error"}}. It doesn't matter what
3756 definition you use for @code{YYERROR_VERBOSE}, just whether you define
3759 The parser can detect one other kind of error: stack overflow. This
3760 happens when the input contains constructions that are very deeply
3761 nested. It isn't likely you will encounter this, since the Bison
3762 parser extends its stack automatically up to a very large limit. But
3763 if overflow happens, @code{yyparse} calls @code{yyerror} in the usual
3764 fashion, except that the argument string is @w{@code{"parser stack
3767 The following definition suffices in simple programs:
3776 fprintf (stderr, "%s\n", s);
3781 After @code{yyerror} returns to @code{yyparse}, the latter will attempt
3782 error recovery if you have written suitable error recovery grammar rules
3783 (@pxref{Error Recovery}). If recovery is impossible, @code{yyparse} will
3784 immediately return 1.
3787 The variable @code{yynerrs} contains the number of syntax errors
3788 encountered so far. Normally this variable is global; but if you
3789 request a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}) then it is a local variable
3790 which only the actions can access.
3792 @node Action Features
3793 @section Special Features for Use in Actions
3794 @cindex summary, action features
3795 @cindex action features summary
3797 Here is a table of Bison constructs, variables and macros that
3798 are useful in actions.
3802 Acts like a variable that contains the semantic value for the
3803 grouping made by the current rule. @xref{Actions}.
3806 Acts like a variable that contains the semantic value for the
3807 @var{n}th component of the current rule. @xref{Actions}.
3809 @item $<@var{typealt}>$
3810 Like @code{$$} but specifies alternative @var{typealt} in the union
3811 specified by the @code{%union} declaration. @xref{Action Types, ,Data Types of Values in Actions}.
3813 @item $<@var{typealt}>@var{n}
3814 Like @code{$@var{n}} but specifies alternative @var{typealt} in the
3815 union specified by the @code{%union} declaration.
3816 @xref{Action Types, ,Data Types of Values in Actions}.@refill
3819 Return immediately from @code{yyparse}, indicating failure.
3820 @xref{Parser Function, ,The Parser Function @code{yyparse}}.
3823 Return immediately from @code{yyparse}, indicating success.
3824 @xref{Parser Function, ,The Parser Function @code{yyparse}}.
3826 @item YYBACKUP (@var{token}, @var{value});
3828 Unshift a token. This macro is allowed only for rules that reduce
3829 a single value, and only when there is no look-ahead token.
3830 It installs a look-ahead token with token type @var{token} and
3831 semantic value @var{value}; then it discards the value that was
3832 going to be reduced by this rule.
3834 If the macro is used when it is not valid, such as when there is
3835 a look-ahead token already, then it reports a syntax error with
3836 a message @samp{cannot back up} and performs ordinary error
3839 In either case, the rest of the action is not executed.
3843 Value stored in @code{yychar} when there is no look-ahead token.
3847 Cause an immediate syntax error. This statement initiates error
3848 recovery just as if the parser itself had detected an error; however, it
3849 does not call @code{yyerror}, and does not print any message. If you
3850 want to print an error message, call @code{yyerror} explicitly before
3851 the @samp{YYERROR;} statement. @xref{Error Recovery}.
3854 This macro stands for an expression that has the value 1 when the parser
3855 is recovering from a syntax error, and 0 the rest of the time.
3856 @xref{Error Recovery}.
3859 Variable containing the current look-ahead token. (In a pure parser,
3860 this is actually a local variable within @code{yyparse}.) When there is
3861 no look-ahead token, the value @code{YYEMPTY} is stored in the variable.
3862 @xref{Look-Ahead, ,Look-Ahead Tokens}.
3865 Discard the current look-ahead token. This is useful primarily in
3866 error rules. @xref{Error Recovery}.
3869 Resume generating error messages immediately for subsequent syntax
3870 errors. This is useful primarily in error rules.
3871 @xref{Error Recovery}.
3875 Acts like a structure variable containing information on the textual position
3876 of the grouping made by the current rule. @xref{Locations, ,
3877 Tracking Locations}.
3879 @c Check if those paragraphs are still useful or not.
3883 @c int first_line, last_line;
3884 @c int first_column, last_column;
3888 @c Thus, to get the starting line number of the third component, you would
3889 @c use @samp{@@3.first_line}.
3891 @c In order for the members of this structure to contain valid information,
3892 @c you must make @code{yylex} supply this information about each token.
3893 @c If you need only certain members, then @code{yylex} need only fill in
3896 @c The use of this feature makes the parser noticeably slower.
3900 Acts like a structure variable containing information on the textual position
3901 of the @var{n}th component of the current rule. @xref{Locations, ,
3902 Tracking Locations}.
3907 @chapter The Bison Parser Algorithm
3908 @cindex Bison parser algorithm
3909 @cindex algorithm of parser
3912 @cindex parser stack
3913 @cindex stack, parser
3915 As Bison reads tokens, it pushes them onto a stack along with their
3916 semantic values. The stack is called the @dfn{parser stack}. Pushing a
3917 token is traditionally called @dfn{shifting}.
3919 For example, suppose the infix calculator has read @samp{1 + 5 *}, with a
3920 @samp{3} to come. The stack will have four elements, one for each token
3923 But the stack does not always have an element for each token read. When
3924 the last @var{n} tokens and groupings shifted match the components of a
3925 grammar rule, they can be combined according to that rule. This is called
3926 @dfn{reduction}. Those tokens and groupings are replaced on the stack by a
3927 single grouping whose symbol is the result (left hand side) of that rule.
3928 Running the rule's action is part of the process of reduction, because this
3929 is what computes the semantic value of the resulting grouping.
3931 For example, if the infix calculator's parser stack contains this:
3938 and the next input token is a newline character, then the last three
3939 elements can be reduced to 15 via the rule:
3942 expr: expr '*' expr;
3946 Then the stack contains just these three elements:
3953 At this point, another reduction can be made, resulting in the single value
3954 16. Then the newline token can be shifted.
3956 The parser tries, by shifts and reductions, to reduce the entire input down
3957 to a single grouping whose symbol is the grammar's start-symbol
3958 (@pxref{Language and Grammar, ,Languages and Context-Free Grammars}).
3960 This kind of parser is known in the literature as a bottom-up parser.
3963 * Look-Ahead:: Parser looks one token ahead when deciding what to do.
3964 * Shift/Reduce:: Conflicts: when either shifting or reduction is valid.
3965 * Precedence:: Operator precedence works by resolving conflicts.
3966 * Contextual Precedence:: When an operator's precedence depends on context.
3967 * Parser States:: The parser is a finite-state-machine with stack.
3968 * Reduce/Reduce:: When two rules are applicable in the same situation.
3969 * Mystery Conflicts:: Reduce/reduce conflicts that look unjustified.
3970 * Stack Overflow:: What happens when stack gets full. How to avoid it.
3974 @section Look-Ahead Tokens
3975 @cindex look-ahead token
3977 The Bison parser does @emph{not} always reduce immediately as soon as the
3978 last @var{n} tokens and groupings match a rule. This is because such a
3979 simple strategy is inadequate to handle most languages. Instead, when a
3980 reduction is possible, the parser sometimes ``looks ahead'' at the next
3981 token in order to decide what to do.
3983 When a token is read, it is not immediately shifted; first it becomes the
3984 @dfn{look-ahead token}, which is not on the stack. Now the parser can
3985 perform one or more reductions of tokens and groupings on the stack, while
3986 the look-ahead token remains off to the side. When no more reductions
3987 should take place, the look-ahead token is shifted onto the stack. This
3988 does not mean that all possible reductions have been done; depending on the
3989 token type of the look-ahead token, some rules may choose to delay their
3992 Here is a simple case where look-ahead is needed. These three rules define
3993 expressions which contain binary addition operators and postfix unary
3994 factorial operators (@samp{!}), and allow parentheses for grouping.
4011 Suppose that the tokens @w{@samp{1 + 2}} have been read and shifted; what
4012 should be done? If the following token is @samp{)}, then the first three
4013 tokens must be reduced to form an @code{expr}. This is the only valid
4014 course, because shifting the @samp{)} would produce a sequence of symbols
4015 @w{@code{term ')'}}, and no rule allows this.
4017 If the following token is @samp{!}, then it must be shifted immediately so
4018 that @w{@samp{2 !}} can be reduced to make a @code{term}. If instead the
4019 parser were to reduce before shifting, @w{@samp{1 + 2}} would become an
4020 @code{expr}. It would then be impossible to shift the @samp{!} because
4021 doing so would produce on the stack the sequence of symbols @code{expr
4022 '!'}. No rule allows that sequence.
4025 The current look-ahead token is stored in the variable @code{yychar}.
4026 @xref{Action Features, ,Special Features for Use in Actions}.
4029 @section Shift/Reduce Conflicts
4031 @cindex shift/reduce conflicts
4032 @cindex dangling @code{else}
4033 @cindex @code{else}, dangling
4035 Suppose we are parsing a language which has if-then and if-then-else
4036 statements, with a pair of rules like this:
4042 | IF expr THEN stmt ELSE stmt
4048 Here we assume that @code{IF}, @code{THEN} and @code{ELSE} are
4049 terminal symbols for specific keyword tokens.
4051 When the @code{ELSE} token is read and becomes the look-ahead token, the
4052 contents of the stack (assuming the input is valid) are just right for
4053 reduction by the first rule. But it is also legitimate to shift the
4054 @code{ELSE}, because that would lead to eventual reduction by the second
4057 This situation, where either a shift or a reduction would be valid, is
4058 called a @dfn{shift/reduce conflict}. Bison is designed to resolve
4059 these conflicts by choosing to shift, unless otherwise directed by
4060 operator precedence declarations. To see the reason for this, let's
4061 contrast it with the other alternative.
4063 Since the parser prefers to shift the @code{ELSE}, the result is to attach
4064 the else-clause to the innermost if-statement, making these two inputs
4068 if x then if y then win (); else lose;
4070 if x then do; if y then win (); else lose; end;
4073 But if the parser chose to reduce when possible rather than shift, the
4074 result would be to attach the else-clause to the outermost if-statement,
4075 making these two inputs equivalent:
4078 if x then if y then win (); else lose;
4080 if x then do; if y then win (); end; else lose;
4083 The conflict exists because the grammar as written is ambiguous: either
4084 parsing of the simple nested if-statement is legitimate. The established
4085 convention is that these ambiguities are resolved by attaching the
4086 else-clause to the innermost if-statement; this is what Bison accomplishes
4087 by choosing to shift rather than reduce. (It would ideally be cleaner to
4088 write an unambiguous grammar, but that is very hard to do in this case.)
4089 This particular ambiguity was first encountered in the specifications of
4090 Algol 60 and is called the ``dangling @code{else}'' ambiguity.
4092 To avoid warnings from Bison about predictable, legitimate shift/reduce
4093 conflicts, use the @code{%expect @var{n}} declaration. There will be no
4094 warning as long as the number of shift/reduce conflicts is exactly @var{n}.
4095 @xref{Expect Decl, ,Suppressing Conflict Warnings}.
4097 The definition of @code{if_stmt} above is solely to blame for the
4098 conflict, but the conflict does not actually appear without additional
4099 rules. Here is a complete Bison input file that actually manifests the
4104 %token IF THEN ELSE variable
4116 | IF expr THEN stmt ELSE stmt
4125 @section Operator Precedence
4126 @cindex operator precedence
4127 @cindex precedence of operators
4129 Another situation where shift/reduce conflicts appear is in arithmetic
4130 expressions. Here shifting is not always the preferred resolution; the
4131 Bison declarations for operator precedence allow you to specify when to
4132 shift and when to reduce.
4135 * Why Precedence:: An example showing why precedence is needed.
4136 * Using Precedence:: How to specify precedence in Bison grammars.
4137 * Precedence Examples:: How these features are used in the previous example.
4138 * How Precedence:: How they work.
4141 @node Why Precedence
4142 @subsection When Precedence is Needed
4144 Consider the following ambiguous grammar fragment (ambiguous because the
4145 input @w{@samp{1 - 2 * 3}} can be parsed in two different ways):
4159 Suppose the parser has seen the tokens @samp{1}, @samp{-} and @samp{2};
4160 should it reduce them via the rule for the subtraction operator? It
4161 depends on the next token. Of course, if the next token is @samp{)}, we
4162 must reduce; shifting is invalid because no single rule can reduce the
4163 token sequence @w{@samp{- 2 )}} or anything starting with that. But if
4164 the next token is @samp{*} or @samp{<}, we have a choice: either
4165 shifting or reduction would allow the parse to complete, but with
4168 To decide which one Bison should do, we must consider the results. If
4169 the next operator token @var{op} is shifted, then it must be reduced
4170 first in order to permit another opportunity to reduce the difference.
4171 The result is (in effect) @w{@samp{1 - (2 @var{op} 3)}}. On the other
4172 hand, if the subtraction is reduced before shifting @var{op}, the result
4173 is @w{@samp{(1 - 2) @var{op} 3}}. Clearly, then, the choice of shift or
4174 reduce should depend on the relative precedence of the operators
4175 @samp{-} and @var{op}: @samp{*} should be shifted first, but not
4178 @cindex associativity
4179 What about input such as @w{@samp{1 - 2 - 5}}; should this be
4180 @w{@samp{(1 - 2) - 5}} or should it be @w{@samp{1 - (2 - 5)}}? For most
4181 operators we prefer the former, which is called @dfn{left association}.
4182 The latter alternative, @dfn{right association}, is desirable for
4183 assignment operators. The choice of left or right association is a
4184 matter of whether the parser chooses to shift or reduce when the stack
4185 contains @w{@samp{1 - 2}} and the look-ahead token is @samp{-}: shifting
4186 makes right-associativity.
4188 @node Using Precedence
4189 @subsection Specifying Operator Precedence
4194 Bison allows you to specify these choices with the operator precedence
4195 declarations @code{%left} and @code{%right}. Each such declaration
4196 contains a list of tokens, which are operators whose precedence and
4197 associativity is being declared. The @code{%left} declaration makes all
4198 those operators left-associative and the @code{%right} declaration makes
4199 them right-associative. A third alternative is @code{%nonassoc}, which
4200 declares that it is a syntax error to find the same operator twice ``in a
4203 The relative precedence of different operators is controlled by the
4204 order in which they are declared. The first @code{%left} or
4205 @code{%right} declaration in the file declares the operators whose
4206 precedence is lowest, the next such declaration declares the operators
4207 whose precedence is a little higher, and so on.
4209 @node Precedence Examples
4210 @subsection Precedence Examples
4212 In our example, we would want the following declarations:
4220 In a more complete example, which supports other operators as well, we
4221 would declare them in groups of equal precedence. For example, @code{'+'} is
4222 declared with @code{'-'}:
4225 %left '<' '>' '=' NE LE GE
4231 (Here @code{NE} and so on stand for the operators for ``not equal''
4232 and so on. We assume that these tokens are more than one character long
4233 and therefore are represented by names, not character literals.)
4235 @node How Precedence
4236 @subsection How Precedence Works
4238 The first effect of the precedence declarations is to assign precedence
4239 levels to the terminal symbols declared. The second effect is to assign
4240 precedence levels to certain rules: each rule gets its precedence from the
4241 last terminal symbol mentioned in the components. (You can also specify
4242 explicitly the precedence of a rule. @xref{Contextual Precedence, ,Context-Dependent Precedence}.)
4244 Finally, the resolution of conflicts works by comparing the
4245 precedence of the rule being considered with that of the
4246 look-ahead token. If the token's precedence is higher, the
4247 choice is to shift. If the rule's precedence is higher, the
4248 choice is to reduce. If they have equal precedence, the choice
4249 is made based on the associativity of that precedence level. The
4250 verbose output file made by @samp{-v} (@pxref{Invocation, ,Invoking Bison}) says
4251 how each conflict was resolved.
4253 Not all rules and not all tokens have precedence. If either the rule or
4254 the look-ahead token has no precedence, then the default is to shift.
4256 @node Contextual Precedence
4257 @section Context-Dependent Precedence
4258 @cindex context-dependent precedence
4259 @cindex unary operator precedence
4260 @cindex precedence, context-dependent
4261 @cindex precedence, unary operator
4264 Often the precedence of an operator depends on the context. This sounds
4265 outlandish at first, but it is really very common. For example, a minus
4266 sign typically has a very high precedence as a unary operator, and a
4267 somewhat lower precedence (lower than multiplication) as a binary operator.
4269 The Bison precedence declarations, @code{%left}, @code{%right} and
4270 @code{%nonassoc}, can only be used once for a given token; so a token has
4271 only one precedence declared in this way. For context-dependent
4272 precedence, you need to use an additional mechanism: the @code{%prec}
4273 modifier for rules.@refill
4275 The @code{%prec} modifier declares the precedence of a particular rule by
4276 specifying a terminal symbol whose precedence should be used for that rule.
4277 It's not necessary for that symbol to appear otherwise in the rule. The
4278 modifier's syntax is:
4281 %prec @var{terminal-symbol}
4285 and it is written after the components of the rule. Its effect is to
4286 assign the rule the precedence of @var{terminal-symbol}, overriding
4287 the precedence that would be deduced for it in the ordinary way. The
4288 altered rule precedence then affects how conflicts involving that rule
4289 are resolved (@pxref{Precedence, ,Operator Precedence}).
4291 Here is how @code{%prec} solves the problem of unary minus. First, declare
4292 a precedence for a fictitious terminal symbol named @code{UMINUS}. There
4293 are no tokens of this type, but the symbol serves to stand for its
4303 Now the precedence of @code{UMINUS} can be used in specific rules:
4310 | '-' exp %prec UMINUS
4315 @section Parser States
4316 @cindex finite-state machine
4317 @cindex parser state
4318 @cindex state (of parser)
4320 The function @code{yyparse} is implemented using a finite-state machine.
4321 The values pushed on the parser stack are not simply token type codes; they
4322 represent the entire sequence of terminal and nonterminal symbols at or
4323 near the top of the stack. The current state collects all the information
4324 about previous input which is relevant to deciding what to do next.
4326 Each time a look-ahead token is read, the current parser state together
4327 with the type of look-ahead token are looked up in a table. This table
4328 entry can say, ``Shift the look-ahead token.'' In this case, it also
4329 specifies the new parser state, which is pushed onto the top of the
4330 parser stack. Or it can say, ``Reduce using rule number @var{n}.''
4331 This means that a certain number of tokens or groupings are taken off
4332 the top of the stack, and replaced by one grouping. In other words,
4333 that number of states are popped from the stack, and one new state is
4336 There is one other alternative: the table can say that the look-ahead token
4337 is erroneous in the current state. This causes error processing to begin
4338 (@pxref{Error Recovery}).
4341 @section Reduce/Reduce Conflicts
4342 @cindex reduce/reduce conflict
4343 @cindex conflicts, reduce/reduce
4345 A reduce/reduce conflict occurs if there are two or more rules that apply
4346 to the same sequence of input. This usually indicates a serious error
4349 For example, here is an erroneous attempt to define a sequence
4350 of zero or more @code{word} groupings.
4353 sequence: /* empty */
4354 @{ printf ("empty sequence\n"); @}
4357 @{ printf ("added word %s\n", $2); @}
4360 maybeword: /* empty */
4361 @{ printf ("empty maybeword\n"); @}
4363 @{ printf ("single word %s\n", $1); @}
4368 The error is an ambiguity: there is more than one way to parse a single
4369 @code{word} into a @code{sequence}. It could be reduced to a
4370 @code{maybeword} and then into a @code{sequence} via the second rule.
4371 Alternatively, nothing-at-all could be reduced into a @code{sequence}
4372 via the first rule, and this could be combined with the @code{word}
4373 using the third rule for @code{sequence}.
4375 There is also more than one way to reduce nothing-at-all into a
4376 @code{sequence}. This can be done directly via the first rule,
4377 or indirectly via @code{maybeword} and then the second rule.
4379 You might think that this is a distinction without a difference, because it
4380 does not change whether any particular input is valid or not. But it does
4381 affect which actions are run. One parsing order runs the second rule's
4382 action; the other runs the first rule's action and the third rule's action.
4383 In this example, the output of the program changes.
4385 Bison resolves a reduce/reduce conflict by choosing to use the rule that
4386 appears first in the grammar, but it is very risky to rely on this. Every
4387 reduce/reduce conflict must be studied and usually eliminated. Here is the
4388 proper way to define @code{sequence}:
4391 sequence: /* empty */
4392 @{ printf ("empty sequence\n"); @}
4394 @{ printf ("added word %s\n", $2); @}
4398 Here is another common error that yields a reduce/reduce conflict:
4401 sequence: /* empty */
4403 | sequence redirects
4410 redirects:/* empty */
4411 | redirects redirect
4416 The intention here is to define a sequence which can contain either
4417 @code{word} or @code{redirect} groupings. The individual definitions of
4418 @code{sequence}, @code{words} and @code{redirects} are error-free, but the
4419 three together make a subtle ambiguity: even an empty input can be parsed
4420 in infinitely many ways!
4422 Consider: nothing-at-all could be a @code{words}. Or it could be two
4423 @code{words} in a row, or three, or any number. It could equally well be a
4424 @code{redirects}, or two, or any number. Or it could be a @code{words}
4425 followed by three @code{redirects} and another @code{words}. And so on.
4427 Here are two ways to correct these rules. First, to make it a single level
4431 sequence: /* empty */
4437 Second, to prevent either a @code{words} or a @code{redirects}
4441 sequence: /* empty */
4443 | sequence redirects
4451 | redirects redirect
4455 @node Mystery Conflicts
4456 @section Mysterious Reduce/Reduce Conflicts
4458 Sometimes reduce/reduce conflicts can occur that don't look warranted.
4466 def: param_spec return_spec ','
4470 | name_list ':' type
4488 | name ',' name_list
4493 It would seem that this grammar can be parsed with only a single token
4494 of look-ahead: when a @code{param_spec} is being read, an @code{ID} is
4495 a @code{name} if a comma or colon follows, or a @code{type} if another
4496 @code{ID} follows. In other words, this grammar is LR(1).
4500 However, Bison, like most parser generators, cannot actually handle all
4501 LR(1) grammars. In this grammar, two contexts, that after an @code{ID}
4502 at the beginning of a @code{param_spec} and likewise at the beginning of
4503 a @code{return_spec}, are similar enough that Bison assumes they are the
4504 same. They appear similar because the same set of rules would be
4505 active---the rule for reducing to a @code{name} and that for reducing to
4506 a @code{type}. Bison is unable to determine at that stage of processing
4507 that the rules would require different look-ahead tokens in the two
4508 contexts, so it makes a single parser state for them both. Combining
4509 the two contexts causes a conflict later. In parser terminology, this
4510 occurrence means that the grammar is not LALR(1).
4512 In general, it is better to fix deficiencies than to document them. But
4513 this particular deficiency is intrinsically hard to fix; parser
4514 generators that can handle LR(1) grammars are hard to write and tend to
4515 produce parsers that are very large. In practice, Bison is more useful
4518 When the problem arises, you can often fix it by identifying the two
4519 parser states that are being confused, and adding something to make them
4520 look distinct. In the above example, adding one rule to
4521 @code{return_spec} as follows makes the problem go away:
4532 /* This rule is never used. */
4538 This corrects the problem because it introduces the possibility of an
4539 additional active rule in the context after the @code{ID} at the beginning of
4540 @code{return_spec}. This rule is not active in the corresponding context
4541 in a @code{param_spec}, so the two contexts receive distinct parser states.
4542 As long as the token @code{BOGUS} is never generated by @code{yylex},
4543 the added rule cannot alter the way actual input is parsed.
4545 In this particular example, there is another way to solve the problem:
4546 rewrite the rule for @code{return_spec} to use @code{ID} directly
4547 instead of via @code{name}. This also causes the two confusing
4548 contexts to have different sets of active rules, because the one for
4549 @code{return_spec} activates the altered rule for @code{return_spec}
4550 rather than the one for @code{name}.
4555 | name_list ':' type
4563 @node Stack Overflow
4564 @section Stack Overflow, and How to Avoid It
4565 @cindex stack overflow
4566 @cindex parser stack overflow
4567 @cindex overflow of parser stack
4569 The Bison parser stack can overflow if too many tokens are shifted and
4570 not reduced. When this happens, the parser function @code{yyparse}
4571 returns a nonzero value, pausing only to call @code{yyerror} to report
4575 By defining the macro @code{YYMAXDEPTH}, you can control how deep the
4576 parser stack can become before a stack overflow occurs. Define the
4577 macro with a value that is an integer. This value is the maximum number
4578 of tokens that can be shifted (and not reduced) before overflow.
4579 It must be a constant expression whose value is known at compile time.
4581 The stack space allowed is not necessarily allocated. If you specify a
4582 large value for @code{YYMAXDEPTH}, the parser actually allocates a small
4583 stack at first, and then makes it bigger by stages as needed. This
4584 increasing allocation happens automatically and silently. Therefore,
4585 you do not need to make @code{YYMAXDEPTH} painfully small merely to save
4586 space for ordinary inputs that do not need much stack.
4588 @cindex default stack limit
4589 The default value of @code{YYMAXDEPTH}, if you do not define it, is
4593 You can control how much stack is allocated initially by defining the
4594 macro @code{YYINITDEPTH}. This value too must be a compile-time
4595 constant integer. The default is 200.
4597 @node Error Recovery
4598 @chapter Error Recovery
4599 @cindex error recovery
4600 @cindex recovery from errors
4602 It is not usually acceptable to have a program terminate on a parse
4603 error. For example, a compiler should recover sufficiently to parse the
4604 rest of the input file and check it for errors; a calculator should accept
4607 In a simple interactive command parser where each input is one line, it may
4608 be sufficient to allow @code{yyparse} to return 1 on error and have the
4609 caller ignore the rest of the input line when that happens (and then call
4610 @code{yyparse} again). But this is inadequate for a compiler, because it
4611 forgets all the syntactic context leading up to the error. A syntax error
4612 deep within a function in the compiler input should not cause the compiler
4613 to treat the following line like the beginning of a source file.
4616 You can define how to recover from a syntax error by writing rules to
4617 recognize the special token @code{error}. This is a terminal symbol that
4618 is always defined (you need not declare it) and reserved for error
4619 handling. The Bison parser generates an @code{error} token whenever a
4620 syntax error happens; if you have provided a rule to recognize this token
4621 in the current context, the parse can continue.
4626 stmnts: /* empty string */
4632 The fourth rule in this example says that an error followed by a newline
4633 makes a valid addition to any @code{stmnts}.
4635 What happens if a syntax error occurs in the middle of an @code{exp}? The
4636 error recovery rule, interpreted strictly, applies to the precise sequence
4637 of a @code{stmnts}, an @code{error} and a newline. If an error occurs in
4638 the middle of an @code{exp}, there will probably be some additional tokens
4639 and subexpressions on the stack after the last @code{stmnts}, and there
4640 will be tokens to read before the next newline. So the rule is not
4641 applicable in the ordinary way.
4643 But Bison can force the situation to fit the rule, by discarding part of
4644 the semantic context and part of the input. First it discards states and
4645 objects from the stack until it gets back to a state in which the
4646 @code{error} token is acceptable. (This means that the subexpressions
4647 already parsed are discarded, back to the last complete @code{stmnts}.) At
4648 this point the @code{error} token can be shifted. Then, if the old
4649 look-ahead token is not acceptable to be shifted next, the parser reads
4650 tokens and discards them until it finds a token which is acceptable. In
4651 this example, Bison reads and discards input until the next newline
4652 so that the fourth rule can apply.
4654 The choice of error rules in the grammar is a choice of strategies for
4655 error recovery. A simple and useful strategy is simply to skip the rest of
4656 the current input line or current statement if an error is detected:
4659 stmnt: error ';' /* on error, skip until ';' is read */
4662 It is also useful to recover to the matching close-delimiter of an
4663 opening-delimiter that has already been parsed. Otherwise the
4664 close-delimiter will probably appear to be unmatched, and generate another,
4665 spurious error message:
4668 primary: '(' expr ')'
4674 Error recovery strategies are necessarily guesses. When they guess wrong,
4675 one syntax error often leads to another. In the above example, the error
4676 recovery rule guesses that an error is due to bad input within one
4677 @code{stmnt}. Suppose that instead a spurious semicolon is inserted in the
4678 middle of a valid @code{stmnt}. After the error recovery rule recovers
4679 from the first error, another syntax error will be found straightaway,
4680 since the text following the spurious semicolon is also an invalid
4683 To prevent an outpouring of error messages, the parser will output no error
4684 message for another syntax error that happens shortly after the first; only
4685 after three consecutive input tokens have been successfully shifted will
4686 error messages resume.
4688 Note that rules which accept the @code{error} token may have actions, just
4689 as any other rules can.
4692 You can make error messages resume immediately by using the macro
4693 @code{yyerrok} in an action. If you do this in the error rule's action, no
4694 error messages will be suppressed. This macro requires no arguments;
4695 @samp{yyerrok;} is a valid C statement.
4698 The previous look-ahead token is reanalyzed immediately after an error. If
4699 this is unacceptable, then the macro @code{yyclearin} may be used to clear
4700 this token. Write the statement @samp{yyclearin;} in the error rule's
4703 For example, suppose that on a parse error, an error handling routine is
4704 called that advances the input stream to some point where parsing should
4705 once again commence. The next symbol returned by the lexical scanner is
4706 probably correct. The previous look-ahead token ought to be discarded
4707 with @samp{yyclearin;}.
4709 @vindex YYRECOVERING
4710 The macro @code{YYRECOVERING} stands for an expression that has the
4711 value 1 when the parser is recovering from a syntax error, and 0 the
4712 rest of the time. A value of 1 indicates that error messages are
4713 currently suppressed for new syntax errors.
4715 @node Context Dependency
4716 @chapter Handling Context Dependencies
4718 The Bison paradigm is to parse tokens first, then group them into larger
4719 syntactic units. In many languages, the meaning of a token is affected by
4720 its context. Although this violates the Bison paradigm, certain techniques
4721 (known as @dfn{kludges}) may enable you to write Bison parsers for such
4725 * Semantic Tokens:: Token parsing can depend on the semantic context.
4726 * Lexical Tie-ins:: Token parsing can depend on the syntactic context.
4727 * Tie-in Recovery:: Lexical tie-ins have implications for how
4728 error recovery rules must be written.
4731 (Actually, ``kludge'' means any technique that gets its job done but is
4732 neither clean nor robust.)
4734 @node Semantic Tokens
4735 @section Semantic Info in Token Types
4737 The C language has a context dependency: the way an identifier is used
4738 depends on what its current meaning is. For example, consider this:
4744 This looks like a function call statement, but if @code{foo} is a typedef
4745 name, then this is actually a declaration of @code{x}. How can a Bison
4746 parser for C decide how to parse this input?
4748 The method used in GNU C is to have two different token types,
4749 @code{IDENTIFIER} and @code{TYPENAME}. When @code{yylex} finds an
4750 identifier, it looks up the current declaration of the identifier in order
4751 to decide which token type to return: @code{TYPENAME} if the identifier is
4752 declared as a typedef, @code{IDENTIFIER} otherwise.
4754 The grammar rules can then express the context dependency by the choice of
4755 token type to recognize. @code{IDENTIFIER} is accepted as an expression,
4756 but @code{TYPENAME} is not. @code{TYPENAME} can start a declaration, but
4757 @code{IDENTIFIER} cannot. In contexts where the meaning of the identifier
4758 is @emph{not} significant, such as in declarations that can shadow a
4759 typedef name, either @code{TYPENAME} or @code{IDENTIFIER} is
4760 accepted---there is one rule for each of the two token types.
4762 This technique is simple to use if the decision of which kinds of
4763 identifiers to allow is made at a place close to where the identifier is
4764 parsed. But in C this is not always so: C allows a declaration to
4765 redeclare a typedef name provided an explicit type has been specified
4769 typedef int foo, bar, lose;
4770 static foo (bar); /* @r{redeclare @code{bar} as static variable} */
4771 static int foo (lose); /* @r{redeclare @code{foo} as function} */
4774 Unfortunately, the name being declared is separated from the declaration
4775 construct itself by a complicated syntactic structure---the ``declarator''.
4777 As a result, part of the Bison parser for C needs to be duplicated, with
4778 all the nonterminal names changed: once for parsing a declaration in
4779 which a typedef name can be redefined, and once for parsing a
4780 declaration in which that can't be done. Here is a part of the
4781 duplication, with actions omitted for brevity:
4785 declarator maybeasm '='
4787 | declarator maybeasm
4791 notype_declarator maybeasm '='
4793 | notype_declarator maybeasm
4798 Here @code{initdcl} can redeclare a typedef name, but @code{notype_initdcl}
4799 cannot. The distinction between @code{declarator} and
4800 @code{notype_declarator} is the same sort of thing.
4802 There is some similarity between this technique and a lexical tie-in
4803 (described next), in that information which alters the lexical analysis is
4804 changed during parsing by other parts of the program. The difference is
4805 here the information is global, and is used for other purposes in the
4806 program. A true lexical tie-in has a special-purpose flag controlled by
4807 the syntactic context.
4809 @node Lexical Tie-ins
4810 @section Lexical Tie-ins
4811 @cindex lexical tie-in
4813 One way to handle context-dependency is the @dfn{lexical tie-in}: a flag
4814 which is set by Bison actions, whose purpose is to alter the way tokens are
4817 For example, suppose we have a language vaguely like C, but with a special
4818 construct @samp{hex (@var{hex-expr})}. After the keyword @code{hex} comes
4819 an expression in parentheses in which all integers are hexadecimal. In
4820 particular, the token @samp{a1b} must be treated as an integer rather than
4821 as an identifier if it appears in that context. Here is how you can do it:
4840 @{ $$ = make_sum ($1, $3); @}
4854 Here we assume that @code{yylex} looks at the value of @code{hexflag}; when
4855 it is nonzero, all integers are parsed in hexadecimal, and tokens starting
4856 with letters are parsed as integers if possible.
4858 The declaration of @code{hexflag} shown in the prologue of the parser file
4859 is needed to make it accessible to the actions (@pxref{Prologue, ,The Prologue}).
4860 You must also write the code in @code{yylex} to obey the flag.
4862 @node Tie-in Recovery
4863 @section Lexical Tie-ins and Error Recovery
4865 Lexical tie-ins make strict demands on any error recovery rules you have.
4866 @xref{Error Recovery}.
4868 The reason for this is that the purpose of an error recovery rule is to
4869 abort the parsing of one construct and resume in some larger construct.
4870 For example, in C-like languages, a typical error recovery rule is to skip
4871 tokens until the next semicolon, and then start a new statement, like this:
4875 | IF '(' expr ')' stmt @{ @dots{} @}
4882 If there is a syntax error in the middle of a @samp{hex (@var{expr})}
4883 construct, this error rule will apply, and then the action for the
4884 completed @samp{hex (@var{expr})} will never run. So @code{hexflag} would
4885 remain set for the entire rest of the input, or until the next @code{hex}
4886 keyword, causing identifiers to be misinterpreted as integers.
4888 To avoid this problem the error recovery rule itself clears @code{hexflag}.
4890 There may also be an error recovery rule that works within expressions.
4891 For example, there could be a rule which applies within parentheses
4892 and skips to the close-parenthesis:
4904 If this rule acts within the @code{hex} construct, it is not going to abort
4905 that construct (since it applies to an inner level of parentheses within
4906 the construct). Therefore, it should not clear the flag: the rest of
4907 the @code{hex} construct should be parsed with the flag still in effect.
4909 What if there is an error recovery rule which might abort out of the
4910 @code{hex} construct or might not, depending on circumstances? There is no
4911 way you can write the action to determine whether a @code{hex} construct is
4912 being aborted or not. So if you are using a lexical tie-in, you had better
4913 make sure your error recovery rules are not of this kind. Each rule must
4914 be such that you can be sure that it always will, or always won't, have to
4918 @chapter Debugging Your Parser
4922 @cindex tracing the parser
4924 If a Bison grammar compiles properly but doesn't do what you want when it
4925 runs, the @code{yydebug} parser-trace feature can help you figure out why.
4927 To enable compilation of trace facilities, you must define the macro
4928 @code{YYDEBUG} when you compile the parser. You could use @samp{-DYYDEBUG=1}
4929 as a compiler option or you could put @samp{#define YYDEBUG 1} in the prologue
4930 of the grammar file (@pxref{Prologue, , The Prologue}). Alternatively, use the
4931 @samp{-t} option when you run Bison (@pxref{Invocation, ,Invoking Bison}).
4932 We always define @code{YYDEBUG} so that debugging is always possible.
4934 The trace facility outputs messages with macro calls of the form
4935 @code{YYFPRINTF (YYSTDERR, @var{format}, @var{args})} where
4936 @var{format} and @var{args} are the usual @code{printf} format and
4937 arguments. If you define @code{YYDEBUG} but do not define
4938 @code{YYFPRINTF}, @code{<stdio.h>} is automatically included and the
4939 macros are defined to @code{fprintf} and @code{stderr}. In the same
4940 situation, C++ parsers include @code{<cstdio.h>} instead, and use
4941 @code{std::fprintf} and @code{std::stderr}.
4943 Once you have compiled the program with trace facilities, the way to
4944 request a trace is to store a nonzero value in the variable @code{yydebug}.
4945 You can do this by making the C code do it (in @code{main}, perhaps), or
4946 you can alter the value with a C debugger.
4948 Each step taken by the parser when @code{yydebug} is nonzero produces a
4949 line or two of trace information, written on @code{stderr}. The trace
4950 messages tell you these things:
4954 Each time the parser calls @code{yylex}, what kind of token was read.
4957 Each time a token is shifted, the depth and complete contents of the
4958 state stack (@pxref{Parser States}).
4961 Each time a rule is reduced, which rule it is, and the complete contents
4962 of the state stack afterward.
4965 To make sense of this information, it helps to refer to the listing file
4966 produced by the Bison @samp{-v} option (@pxref{Invocation, ,Invoking Bison}). This file
4967 shows the meaning of each state in terms of positions in various rules, and
4968 also what each state will do with each possible input token. As you read
4969 the successive trace messages, you can see that the parser is functioning
4970 according to its specification in the listing file. Eventually you will
4971 arrive at the place where something undesirable happens, and you will see
4972 which parts of the grammar are to blame.
4974 The parser file is a C program and you can use C debuggers on it, but it's
4975 not easy to interpret what it is doing. The parser function is a
4976 finite-state machine interpreter, and aside from the actions it executes
4977 the same code over and over. Only the values of variables show where in
4978 the grammar it is working.
4981 The debugging information normally gives the token type of each token
4982 read, but not its semantic value. You can optionally define a macro
4983 named @code{YYPRINT} to provide a way to print the value. If you define
4984 @code{YYPRINT}, it should take three arguments. The parser will pass a
4985 standard I/O stream, the numeric code for the token type, and the token
4986 value (from @code{yylval}).
4988 Here is an example of @code{YYPRINT} suitable for the multi-function
4989 calculator (@pxref{Mfcalc Decl, ,Declarations for @code{mfcalc}}):
4992 #define YYPRINT(file, type, value) yyprint (file, type, value)
4995 yyprint (FILE *file, int type, YYSTYPE value)
4998 fprintf (file, " %s", value.tptr->name);
4999 else if (type == NUM)
5000 fprintf (file, " %d", value.val);
5005 @chapter Invoking Bison
5006 @cindex invoking Bison
5007 @cindex Bison invocation
5008 @cindex options for invoking Bison
5010 The usual way to invoke Bison is as follows:
5016 Here @var{infile} is the grammar file name, which usually ends in
5017 @samp{.y}. The parser file's name is made by replacing the @samp{.y}
5018 with @samp{.tab.c}. Thus, the @samp{bison foo.y} filename yields
5019 @file{foo.tab.c}, and the @samp{bison hack/foo.y} filename yields
5020 @file{hack/foo.tab.c}. It's is also possible, in case you are writing
5021 C++ code instead of C in your grammar file, to name it @file{foo.ypp}
5022 or @file{foo.y++}. Then, the output files will take an extention like
5023 the given one as input (repectively @file{foo.tab.cpp} and @file{foo.tab.c++}).
5024 This feature takes effect with all options that manipulate filenames like
5025 @samp{-o} or @samp{-d}.
5030 bison -d @var{infile.yxx}
5033 will produce @file{infile.tab.cxx} and @file{infile.tab.hxx}. and
5036 bison -d @var{infile.y} -o @var{output.c++}
5039 will produce @file{output.c++} and @file{outfile.h++}.
5043 * Bison Options:: All the options described in detail,
5044 in alphabetical order by short options.
5045 * Environment Variables:: Variables which affect Bison execution.
5046 * Option Cross Key:: Alphabetical list of long options.
5047 * VMS Invocation:: Bison command syntax on VMS.
5051 @section Bison Options
5053 Bison supports both traditional single-letter options and mnemonic long
5054 option names. Long option names are indicated with @samp{--} instead of
5055 @samp{-}. Abbreviations for option names are allowed as long as they
5056 are unique. When a long option takes an argument, like
5057 @samp{--file-prefix}, connect the option name and the argument with
5060 Here is a list of options that can be used with Bison, alphabetized by
5061 short option. It is followed by a cross key alphabetized by long
5064 @c Please, keep this ordered as in `bison --help'.
5070 Print a summary of the command-line options to Bison and exit.
5074 Print the version number of Bison and exit.
5079 @itemx --fixed-output-files
5080 Equivalent to @samp{-o y.tab.c}; the parser output file is called
5081 @file{y.tab.c}, and the other outputs are called @file{y.output} and
5082 @file{y.tab.h}. The purpose of this option is to imitate Yacc's output
5083 file name conventions. Thus, the following shell script can substitute
5096 @itemx --skeleton=@var{file}
5097 Specify the skeleton to use. You probably don't need this option unless
5098 you are developing Bison.
5102 Output a definition of the macro @code{YYDEBUG} into the parser file, so
5103 that the debugging facilities are compiled. @xref{Debugging, ,Debugging
5107 Pretend that @code{%locations} was specified. @xref{Decl Summary}.
5109 @item -p @var{prefix}
5110 @itemx --name-prefix=@var{prefix}
5111 Pretend that @code{%name-prefix="@var{prefix}"} was specified.
5112 @xref{Decl Summary}.
5116 Don't put any @code{#line} preprocessor commands in the parser file.
5117 Ordinarily Bison puts them in the parser file so that the C compiler
5118 and debuggers will associate errors with your source file, the
5119 grammar file. This option causes them to associate errors with the
5120 parser file, treating it as an independent source file in its own right.
5124 Pretend that @code{%no-parser} was specified. @xref{Decl Summary}.
5127 @itemx --token-table
5128 Pretend that @code{%token-table} was specified. @xref{Decl Summary}.
5137 Pretend that @code{%defines} was specified, i.e., write an extra output
5138 file containing macro definitions for the token type names defined in
5139 the grammar and the semantic value type @code{YYSTYPE}, as well as a few
5140 @code{extern} variable declarations. @xref{Decl Summary}.
5142 @item --defines=@var{defines-file}
5143 Same as above, but save in the file @var{defines-file}.
5145 @item -b @var{file-prefix}
5146 @itemx --file-prefix=@var{prefix}
5147 Pretend that @code{%verbose} was specified, i.e, specify prefix to use
5148 for all Bison output file names. @xref{Decl Summary}.
5152 Pretend that @code{%verbose} was specified, i.e, write an extra output
5153 file containing verbose descriptions of the grammar and
5154 parser. @xref{Decl Summary}.
5156 @item -o @var{filename}
5157 @itemx --output=@var{filename}
5158 Specify the @var{filename} for the parser file.
5160 The other output files' names are constructed from @var{filename} as
5161 described under the @samp{-v} and @samp{-d} options.
5164 Output a VCG definition of the LALR(1) grammar automaton computed by
5165 Bison. If the grammar file is @file{foo.y}, the VCG output file will
5168 @item --graph=@var{graph-file}
5169 The behaviour of @var{--graph} is the same than @samp{-g}. The only
5170 difference is that it has an optionnal argument which is the name of
5171 the output graph filename.
5174 @node Environment Variables
5175 @section Environment Variables
5176 @cindex environment variables
5178 @cindex BISON_SIMPLE
5180 Here is a list of environment variables which affect the way Bison
5186 Much of the parser generated by Bison is copied verbatim from a file
5187 called @file{bison.simple}. If Bison cannot find that file, or if you
5188 would like to direct Bison to use a different copy, setting the
5189 environment variable @code{BISON_SIMPLE} to the path of the file will
5190 cause Bison to use that copy instead.
5192 When the @samp{%semantic_parser} declaration is used, Bison copies from
5193 a file called @file{bison.hairy} instead. The location of this file can
5194 also be specified or overridden in a similar fashion, with the
5195 @code{BISON_HAIRY} environment variable.
5199 @node Option Cross Key
5200 @section Option Cross Key
5202 Here is a list of options, alphabetized by long option, to help you find
5203 the corresponding short option.
5206 \def\leaderfill{\leaders\hbox to 1em{\hss.\hss}\hfill}
5209 \line{ --debug \leaderfill -t}
5210 \line{ --defines \leaderfill -d}
5211 \line{ --file-prefix \leaderfill -b}
5212 \line{ --fixed-output-files \leaderfill -y}
5213 \line{ --graph \leaderfill -g}
5214 \line{ --help \leaderfill -h}
5215 \line{ --name-prefix \leaderfill -p}
5216 \line{ --no-lines \leaderfill -l}
5217 \line{ --no-parser \leaderfill -n}
5218 \line{ --output \leaderfill -o}
5219 \line{ --token-table \leaderfill -k}
5220 \line{ --verbose \leaderfill -v}
5221 \line{ --version \leaderfill -V}
5222 \line{ --yacc \leaderfill -y}
5229 --defines=@var{defines-file} -d
5230 --file-prefix=@var{prefix} -b @var{file-prefix}
5231 --fixed-output-files --yacc -y
5232 --graph=@var{graph-file} -d
5234 --name-prefix=@var{prefix} -p @var{name-prefix}
5237 --output=@var{outfile} -o @var{outfile}
5244 @node VMS Invocation
5245 @section Invoking Bison under VMS
5246 @cindex invoking Bison under VMS
5249 The command line syntax for Bison on VMS is a variant of the usual
5250 Bison command syntax---adapted to fit VMS conventions.
5252 To find the VMS equivalent for any Bison option, start with the long
5253 option, and substitute a @samp{/} for the leading @samp{--}, and
5254 substitute a @samp{_} for each @samp{-} in the name of the long option.
5255 For example, the following invocation under VMS:
5258 bison /debug/name_prefix=bar foo.y
5262 is equivalent to the following command under POSIX.
5265 bison --debug --name-prefix=bar foo.y
5268 The VMS file system does not permit filenames such as
5269 @file{foo.tab.c}. In the above example, the output file
5270 would instead be named @file{foo_tab.c}.
5272 @node Table of Symbols
5273 @appendix Bison Symbols
5274 @cindex Bison symbols, table of
5275 @cindex symbols in Bison, table of
5279 A token name reserved for error recovery. This token may be used in
5280 grammar rules so as to allow the Bison parser to recognize an error in
5281 the grammar without halting the process. In effect, a sentence
5282 containing an error may be recognized as valid. On a parse error, the
5283 token @code{error} becomes the current look-ahead token. Actions
5284 corresponding to @code{error} are then executed, and the look-ahead
5285 token is reset to the token that originally caused the violation.
5286 @xref{Error Recovery}.
5289 Macro to pretend that an unrecoverable syntax error has occurred, by
5290 making @code{yyparse} return 1 immediately. The error reporting
5291 function @code{yyerror} is not called. @xref{Parser Function, ,The
5292 Parser Function @code{yyparse}}.
5295 Macro to pretend that a complete utterance of the language has been
5296 read, by making @code{yyparse} return 0 immediately.
5297 @xref{Parser Function, ,The Parser Function @code{yyparse}}.
5300 Macro to discard a value from the parser stack and fake a look-ahead
5301 token. @xref{Action Features, ,Special Features for Use in Actions}.
5304 Macro to pretend that a syntax error has just been detected: call
5305 @code{yyerror} and then perform normal error recovery if possible
5306 (@pxref{Error Recovery}), or (if recovery is impossible) make
5307 @code{yyparse} return 1. @xref{Error Recovery}.
5309 @item YYERROR_VERBOSE
5310 Macro that you define with @code{#define} in the Bison declarations
5311 section to request verbose, specific error message strings when
5312 @code{yyerror} is called.
5315 Macro for specifying the initial size of the parser stack.
5316 @xref{Stack Overflow}.
5319 Macro for specifying an extra argument (or list of extra arguments) for
5320 @code{yyparse} to pass to @code{yylex}. @xref{Pure Calling,, Calling
5321 Conventions for Pure Parsers}.
5324 Macro for the data type of @code{yylloc}; a structure with four
5325 members. @xref{Location Type, , Data Types of Locations}.
5328 Default value for YYLTYPE.
5331 Macro for specifying the maximum size of the parser stack.
5332 @xref{Stack Overflow}.
5335 Macro for specifying the name of a parameter that @code{yyparse} should
5336 accept. @xref{Pure Calling,, Calling Conventions for Pure Parsers}.
5339 Macro whose value indicates whether the parser is recovering from a
5340 syntax error. @xref{Action Features, ,Special Features for Use in Actions}.
5342 @item YYSTACK_USE_ALLOCA
5343 Macro used to control the use of @code{alloca}. If defined to @samp{0},
5344 the parser will not use @code{alloca} but @code{malloc} when trying to
5345 grow its internal stacks. Do @emph{not} define @code{YYSTACK_USE_ALLOCA}
5349 Macro for the data type of semantic values; @code{int} by default.
5350 @xref{Value Type, ,Data Types of Semantic Values}.
5353 External integer variable that contains the integer value of the current
5354 look-ahead token. (In a pure parser, it is a local variable within
5355 @code{yyparse}.) Error-recovery rule actions may examine this variable.
5356 @xref{Action Features, ,Special Features for Use in Actions}.
5359 Macro used in error-recovery rule actions. It clears the previous
5360 look-ahead token. @xref{Error Recovery}.
5363 External integer variable set to zero by default. If @code{yydebug}
5364 is given a nonzero value, the parser will output information on input
5365 symbols and parser action. @xref{Debugging, ,Debugging Your Parser}.
5368 Macro to cause parser to recover immediately to its normal mode
5369 after a parse error. @xref{Error Recovery}.
5372 User-supplied function to be called by @code{yyparse} on error. The
5373 function receives one argument, a pointer to a character string
5374 containing an error message. @xref{Error Reporting, ,The Error
5375 Reporting Function @code{yyerror}}.
5378 User-supplied lexical analyzer function, called with no arguments
5379 to get the next token. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
5382 External variable in which @code{yylex} should place the semantic
5383 value associated with a token. (In a pure parser, it is a local
5384 variable within @code{yyparse}, and its address is passed to
5385 @code{yylex}.) @xref{Token Values, ,Semantic Values of Tokens}.
5388 External variable in which @code{yylex} should place the line and column
5389 numbers associated with a token. (In a pure parser, it is a local
5390 variable within @code{yyparse}, and its address is passed to
5391 @code{yylex}.) You can ignore this variable if you don't use the
5392 @samp{@@} feature in the grammar actions. @xref{Token Positions,
5393 ,Textual Positions of Tokens}.
5396 Global variable which Bison increments each time there is a parse error.
5397 (In a pure parser, it is a local variable within @code{yyparse}.)
5398 @xref{Error Reporting, ,The Error Reporting Function @code{yyerror}}.
5401 The parser function produced by Bison; call this function to start
5402 parsing. @xref{Parser Function, ,The Parser Function @code{yyparse}}.
5405 Equip the parser for debugging. @xref{Decl Summary}.
5408 Bison declaration to create a header file meant for the scanner.
5409 @xref{Decl Summary}.
5411 @item %file-prefix="@var{prefix}"
5412 Bison declaration to set tge prefix of the output files. @xref{Decl
5415 @c @item %source_extension
5416 @c Bison declaration to specify the generated parser output file extension.
5417 @c @xref{Decl Summary}.
5419 @c @item %header_extension
5420 @c Bison declaration to specify the generated parser header file extension
5421 @c if required. @xref{Decl Summary}.
5424 Bison declaration to assign left associativity to token(s).
5425 @xref{Precedence Decl, ,Operator Precedence}.
5427 @item %name-prefix="@var{prefix}"
5428 Bison declaration to rename the external symbols. @xref{Decl Summary}.
5431 Bison declaration to avoid generating @code{#line} directives in the
5432 parser file. @xref{Decl Summary}.
5435 Bison declaration to assign non-associativity to token(s).
5436 @xref{Precedence Decl, ,Operator Precedence}.
5438 @item %output="@var{filename}"
5439 Bison declaration to set the name of the parser file. @xref{Decl
5443 Bison declaration to assign a precedence to a specific rule.
5444 @xref{Contextual Precedence, ,Context-Dependent Precedence}.
5447 Bison declaration to request a pure (reentrant) parser.
5448 @xref{Pure Decl, ,A Pure (Reentrant) Parser}.
5451 Bison declaration to assign right associativity to token(s).
5452 @xref{Precedence Decl, ,Operator Precedence}.
5455 Bison declaration to specify the start symbol. @xref{Start Decl, ,The Start-Symbol}.
5458 Bison declaration to declare token(s) without specifying precedence.
5459 @xref{Token Decl, ,Token Type Names}.
5462 Bison declaration to include a token name table in the parser file.
5463 @xref{Decl Summary}.
5466 Bison declaration to declare nonterminals. @xref{Type Decl, ,Nonterminal Symbols}.
5469 Bison declaration to specify several possible data types for semantic
5470 values. @xref{Union Decl, ,The Collection of Value Types}.
5473 These are the punctuation and delimiters used in Bison input:
5477 Delimiter used to separate the grammar rule section from the
5478 Bison declarations section or the epilogue.
5479 @xref{Grammar Layout, ,The Overall Layout of a Bison Grammar}.
5482 All code listed between @samp{%@{} and @samp{%@}} is copied directly to
5483 the output file uninterpreted. Such code forms the prologue of the input
5484 file. @xref{Grammar Outline, ,Outline of a Bison
5488 Comment delimiters, as in C.
5491 Separates a rule's result from its components. @xref{Rules, ,Syntax of
5495 Terminates a rule. @xref{Rules, ,Syntax of Grammar Rules}.
5498 Separates alternate rules for the same result nonterminal.
5499 @xref{Rules, ,Syntax of Grammar Rules}.
5507 @item Backus-Naur Form (BNF)
5508 Formal method of specifying context-free grammars. BNF was first used
5509 in the @cite{ALGOL-60} report, 1963. @xref{Language and Grammar,
5510 ,Languages and Context-Free Grammars}.
5512 @item Context-free grammars
5513 Grammars specified as rules that can be applied regardless of context.
5514 Thus, if there is a rule which says that an integer can be used as an
5515 expression, integers are allowed @emph{anywhere} an expression is
5516 permitted. @xref{Language and Grammar, ,Languages and Context-Free
5519 @item Dynamic allocation
5520 Allocation of memory that occurs during execution, rather than at
5521 compile time or on entry to a function.
5524 Analogous to the empty set in set theory, the empty string is a
5525 character string of length zero.
5527 @item Finite-state stack machine
5528 A ``machine'' that has discrete states in which it is said to exist at
5529 each instant in time. As input to the machine is processed, the
5530 machine moves from state to state as specified by the logic of the
5531 machine. In the case of the parser, the input is the language being
5532 parsed, and the states correspond to various stages in the grammar
5533 rules. @xref{Algorithm, ,The Bison Parser Algorithm }.
5536 A language construct that is (in general) grammatically divisible;
5537 for example, `expression' or `declaration' in C.
5538 @xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5540 @item Infix operator
5541 An arithmetic operator that is placed between the operands on which it
5542 performs some operation.
5545 A continuous flow of data between devices or programs.
5547 @item Language construct
5548 One of the typical usage schemas of the language. For example, one of
5549 the constructs of the C language is the @code{if} statement.
5550 @xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5552 @item Left associativity
5553 Operators having left associativity are analyzed from left to right:
5554 @samp{a+b+c} first computes @samp{a+b} and then combines with
5555 @samp{c}. @xref{Precedence, ,Operator Precedence}.
5557 @item Left recursion
5558 A rule whose result symbol is also its first component symbol; for
5559 example, @samp{expseq1 : expseq1 ',' exp;}. @xref{Recursion, ,Recursive
5562 @item Left-to-right parsing
5563 Parsing a sentence of a language by analyzing it token by token from
5564 left to right. @xref{Algorithm, ,The Bison Parser Algorithm }.
5566 @item Lexical analyzer (scanner)
5567 A function that reads an input stream and returns tokens one by one.
5568 @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
5570 @item Lexical tie-in
5571 A flag, set by actions in the grammar rules, which alters the way
5572 tokens are parsed. @xref{Lexical Tie-ins}.
5574 @item Literal string token
5575 A token which consists of two or more fixed characters. @xref{Symbols}.
5577 @item Look-ahead token
5578 A token already read but not yet shifted. @xref{Look-Ahead, ,Look-Ahead
5582 The class of context-free grammars that Bison (like most other parser
5583 generators) can handle; a subset of LR(1). @xref{Mystery Conflicts, ,
5584 Mysterious Reduce/Reduce Conflicts}.
5587 The class of context-free grammars in which at most one token of
5588 look-ahead is needed to disambiguate the parsing of any piece of input.
5590 @item Nonterminal symbol
5591 A grammar symbol standing for a grammatical construct that can
5592 be expressed through rules in terms of smaller constructs; in other
5593 words, a construct that is not a token. @xref{Symbols}.
5596 An error encountered during parsing of an input stream due to invalid
5597 syntax. @xref{Error Recovery}.
5600 A function that recognizes valid sentences of a language by analyzing
5601 the syntax structure of a set of tokens passed to it from a lexical
5604 @item Postfix operator
5605 An arithmetic operator that is placed after the operands upon which it
5606 performs some operation.
5609 Replacing a string of nonterminals and/or terminals with a single
5610 nonterminal, according to a grammar rule. @xref{Algorithm, ,The Bison
5614 A reentrant subprogram is a subprogram which can be in invoked any
5615 number of times in parallel, without interference between the various
5616 invocations. @xref{Pure Decl, ,A Pure (Reentrant) Parser}.
5618 @item Reverse polish notation
5619 A language in which all operators are postfix operators.
5621 @item Right recursion
5622 A rule whose result symbol is also its last component symbol; for
5623 example, @samp{expseq1: exp ',' expseq1;}. @xref{Recursion, ,Recursive
5627 In computer languages, the semantics are specified by the actions
5628 taken for each instance of the language, i.e., the meaning of
5629 each statement. @xref{Semantics, ,Defining Language Semantics}.
5632 A parser is said to shift when it makes the choice of analyzing
5633 further input from the stream rather than reducing immediately some
5634 already-recognized rule. @xref{Algorithm, ,The Bison Parser Algorithm }.
5636 @item Single-character literal
5637 A single character that is recognized and interpreted as is.
5638 @xref{Grammar in Bison, ,From Formal Rules to Bison Input}.
5641 The nonterminal symbol that stands for a complete valid utterance in
5642 the language being parsed. The start symbol is usually listed as the
5643 first nonterminal symbol in a language specification.
5644 @xref{Start Decl, ,The Start-Symbol}.
5647 A data structure where symbol names and associated data are stored
5648 during parsing to allow for recognition and use of existing
5649 information in repeated uses of a symbol. @xref{Multi-function Calc}.
5652 A basic, grammatically indivisible unit of a language. The symbol
5653 that describes a token in the grammar is a terminal symbol.
5654 The input of the Bison parser is a stream of tokens which comes from
5655 the lexical analyzer. @xref{Symbols}.
5657 @item Terminal symbol
5658 A grammar symbol that has no rules in the grammar and therefore is
5659 grammatically indivisible. The piece of text it represents is a token.
5660 @xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5663 @node Copying This Manual
5664 @appendix Copying This Manual
5667 * GNU Free Documentation License:: License for copying this manual.