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. Bison and C declarations for rpcalc.
195 * Rules: Rpcalc Rules. Grammar Rules for rpcalc, with explanation.
196 * Lexer: Rpcalc Lexer. The lexical analyzer.
197 * Main: Rpcalc Main. The controlling function.
198 * Error: Rpcalc Error. The error reporting function.
199 * Gen: Rpcalc Gen. Running Bison on the grammar file.
200 * Comp: Rpcalc Compile. Run the C compiler on the output code.
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 * C Declarations:: Syntax and usage of the C declarations section.
233 * Bison Declarations:: Syntax and usage of the Bison declarations section.
234 * Grammar Rules:: Syntax and usage of the grammar rules section.
235 * C Code:: Syntax and usage of the additional C code section.
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:
451 int /* @r{keyword `int'} */
452 square (x) /* @r{identifier, open-paren,} */
453 /* @r{identifier, close-paren} */
454 int x; /* @r{keyword `int', identifier, semicolon} */
455 @{ /* @r{open-brace} */
456 return x * x; /* @r{keyword `return', identifier,} */
457 /* @r{asterisk, identifier, semicolon} */
458 @} /* @r{close-brace} */
461 The syntactic groupings of C include the expression, the statement, the
462 declaration, and the function definition. These are represented in the
463 grammar of C by nonterminal symbols `expression', `statement',
464 `declaration' and `function definition'. The full grammar uses dozens of
465 additional language constructs, each with its own nonterminal symbol, in
466 order to express the meanings of these four. The example above is a
467 function definition; it contains one declaration, and one statement. In
468 the statement, each @samp{x} is an expression and so is @samp{x * x}.
470 Each nonterminal symbol must have grammatical rules showing how it is made
471 out of simpler constructs. For example, one kind of C statement is the
472 @code{return} statement; this would be described with a grammar rule which
473 reads informally as follows:
476 A `statement' can be made of a `return' keyword, an `expression' and a
481 There would be many other rules for `statement', one for each kind of
485 One nonterminal symbol must be distinguished as the special one which
486 defines a complete utterance in the language. It is called the @dfn{start
487 symbol}. In a compiler, this means a complete input program. In the C
488 language, the nonterminal symbol `sequence of definitions and declarations'
491 For example, @samp{1 + 2} is a valid C expression---a valid part of a C
492 program---but it is not valid as an @emph{entire} C program. In the
493 context-free grammar of C, this follows from the fact that `expression' is
494 not the start symbol.
496 The Bison parser reads a sequence of tokens as its input, and groups the
497 tokens using the grammar rules. If the input is valid, the end result is
498 that the entire token sequence reduces to a single grouping whose symbol is
499 the grammar's start symbol. If we use a grammar for C, the entire input
500 must be a `sequence of definitions and declarations'. If not, the parser
501 reports a syntax error.
503 @node Grammar in Bison
504 @section From Formal Rules to Bison Input
505 @cindex Bison grammar
506 @cindex grammar, Bison
507 @cindex formal grammar
509 A formal grammar is a mathematical construct. To define the language
510 for Bison, you must write a file expressing the grammar in Bison syntax:
511 a @dfn{Bison grammar} file. @xref{Grammar File, ,Bison Grammar Files}.
513 A nonterminal symbol in the formal grammar is represented in Bison input
514 as an identifier, like an identifier in C. By convention, it should be
515 in lower case, such as @code{expr}, @code{stmt} or @code{declaration}.
517 The Bison representation for a terminal symbol is also called a @dfn{token
518 type}. Token types as well can be represented as C-like identifiers. By
519 convention, these identifiers should be upper case to distinguish them from
520 nonterminals: for example, @code{INTEGER}, @code{IDENTIFIER}, @code{IF} or
521 @code{RETURN}. A terminal symbol that stands for a particular keyword in
522 the language should be named after that keyword converted to upper case.
523 The terminal symbol @code{error} is reserved for error recovery.
526 A terminal symbol can also be represented as a character literal, just like
527 a C character constant. You should do this whenever a token is just a
528 single character (parenthesis, plus-sign, etc.): use that same character in
529 a literal as the terminal symbol for that token.
531 A third way to represent a terminal symbol is with a C string constant
532 containing several characters. @xref{Symbols}, for more information.
534 The grammar rules also have an expression in Bison syntax. For example,
535 here is the Bison rule for a C @code{return} statement. The semicolon in
536 quotes is a literal character token, representing part of the C syntax for
537 the statement; the naked semicolon, and the colon, are Bison punctuation
541 stmt: RETURN expr ';'
546 @xref{Rules, ,Syntax of Grammar Rules}.
548 @node Semantic Values
549 @section Semantic Values
550 @cindex semantic value
551 @cindex value, semantic
553 A formal grammar selects tokens only by their classifications: for example,
554 if a rule mentions the terminal symbol `integer constant', it means that
555 @emph{any} integer constant is grammatically valid in that position. The
556 precise value of the constant is irrelevant to how to parse the input: if
557 @samp{x+4} is grammatical then @samp{x+1} or @samp{x+3989} is equally
560 But the precise value is very important for what the input means once it is
561 parsed. A compiler is useless if it fails to distinguish between 4, 1 and
562 3989 as constants in the program! Therefore, each token in a Bison grammar
563 has both a token type and a @dfn{semantic value}. @xref{Semantics, ,Defining Language Semantics},
566 The token type is a terminal symbol defined in the grammar, such as
567 @code{INTEGER}, @code{IDENTIFIER} or @code{','}. It tells everything
568 you need to know to decide where the token may validly appear and how to
569 group it with other tokens. The grammar rules know nothing about tokens
570 except their types.@refill
572 The semantic value has all the rest of the information about the
573 meaning of the token, such as the value of an integer, or the name of an
574 identifier. (A token such as @code{','} which is just punctuation doesn't
575 need to have any semantic value.)
577 For example, an input token might be classified as token type
578 @code{INTEGER} and have the semantic value 4. Another input token might
579 have the same token type @code{INTEGER} but value 3989. When a grammar
580 rule says that @code{INTEGER} is allowed, either of these tokens is
581 acceptable because each is an @code{INTEGER}. When the parser accepts the
582 token, it keeps track of the token's semantic value.
584 Each grouping can also have a semantic value as well as its nonterminal
585 symbol. For example, in a calculator, an expression typically has a
586 semantic value that is a number. In a compiler for a programming
587 language, an expression typically has a semantic value that is a tree
588 structure describing the meaning of the expression.
590 @node Semantic Actions
591 @section Semantic Actions
592 @cindex semantic actions
593 @cindex actions, semantic
595 In order to be useful, a program must do more than parse input; it must
596 also produce some output based on the input. In a Bison grammar, a grammar
597 rule can have an @dfn{action} made up of C statements. Each time the
598 parser recognizes a match for that rule, the action is executed.
601 Most of the time, the purpose of an action is to compute the semantic value
602 of the whole construct from the semantic values of its parts. For example,
603 suppose we have a rule which says an expression can be the sum of two
604 expressions. When the parser recognizes such a sum, each of the
605 subexpressions has a semantic value which describes how it was built up.
606 The action for this rule should create a similar sort of value for the
607 newly recognized larger expression.
609 For example, here is a rule that says an expression can be the sum of
613 expr: expr '+' expr @{ $$ = $1 + $3; @}
618 The action says how to produce the semantic value of the sum expression
619 from the values of the two subexpressions.
621 @node Locations Overview
624 @cindex textual position
625 @cindex position, textual
627 Many applications, like interpreters or compilers, have to produce verbose
628 and useful error messages. To achieve this, one must be able to keep track of
629 the @dfn{textual position}, or @dfn{location}, of each syntactic construct.
630 Bison provides a mechanism for handling these locations.
632 Each token has a semantic value. In a similar fashion, each token has an
633 associated location, but the type of locations is the same for all tokens and
634 groupings. Moreover, the output parser is equipped with a default data
635 structure for storing locations (@pxref{Locations}, for more details).
637 Like semantic values, locations can be reached in actions using a dedicated
638 set of constructs. In the example above, the location of the whole grouping
639 is @code{@@$}, while the locations of the subexpressions are @code{@@1} and
642 When a rule is matched, a default action is used to compute the semantic value
643 of its left hand side (@pxref{Actions}). In the same way, another default
644 action is used for locations. However, the action for locations is general
645 enough for most cases, meaning there is usually no need to describe for each
646 rule how @code{@@$} should be formed. When building a new location for a given
647 grouping, the default behavior of the output parser is to take the beginning
648 of the first symbol, and the end of the last symbol.
651 @section Bison Output: the Parser File
653 @cindex Bison utility
654 @cindex lexical analyzer, purpose
657 When you run Bison, you give it a Bison grammar file as input. The output
658 is a C source file that parses the language described by the grammar.
659 This file is called a @dfn{Bison parser}. Keep in mind that the Bison
660 utility and the Bison parser are two distinct programs: the Bison utility
661 is a program whose output is the Bison parser that becomes part of your
664 The job of the Bison parser is to group tokens into groupings according to
665 the grammar rules---for example, to build identifiers and operators into
666 expressions. As it does this, it runs the actions for the grammar rules it
669 The tokens come from a function called the @dfn{lexical analyzer} that you
670 must supply in some fashion (such as by writing it in C). The Bison parser
671 calls the lexical analyzer each time it wants a new token. It doesn't know
672 what is ``inside'' the tokens (though their semantic values may reflect
673 this). Typically the lexical analyzer makes the tokens by parsing
674 characters of text, but Bison does not depend on this. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
676 The Bison parser file is C code which defines a function named
677 @code{yyparse} which implements that grammar. This function does not make
678 a complete C program: you must supply some additional functions. One is
679 the lexical analyzer. Another is an error-reporting function which the
680 parser calls to report an error. In addition, a complete C program must
681 start with a function called @code{main}; you have to provide this, and
682 arrange for it to call @code{yyparse} or the parser will never run.
683 @xref{Interface, ,Parser C-Language Interface}.
685 Aside from the token type names and the symbols in the actions you
686 write, all variable and function names used in the Bison parser file
687 begin with @samp{yy} or @samp{YY}. This includes interface functions
688 such as the lexical analyzer function @code{yylex}, the error reporting
689 function @code{yyerror} and the parser function @code{yyparse} itself.
690 This also includes numerous identifiers used for internal purposes.
691 Therefore, you should avoid using C identifiers starting with @samp{yy}
692 or @samp{YY} in the Bison grammar file except for the ones defined in
696 @section Stages in Using Bison
697 @cindex stages in using Bison
700 The actual language-design process using Bison, from grammar specification
701 to a working compiler or interpreter, has these parts:
705 Formally specify the grammar in a form recognized by Bison
706 (@pxref{Grammar File, ,Bison Grammar Files}). For each grammatical rule in the language,
707 describe the action that is to be taken when an instance of that rule
708 is recognized. The action is described by a sequence of C statements.
711 Write a lexical analyzer to process input and pass tokens to the
712 parser. The lexical analyzer may be written by hand in C
713 (@pxref{Lexical, ,The Lexical Analyzer Function @code{yylex}}). It could also be produced using Lex, but the use
714 of Lex is not discussed in this manual.
717 Write a controlling function that calls the Bison-produced parser.
720 Write error-reporting routines.
723 To turn this source code as written into a runnable program, you
724 must follow these steps:
728 Run Bison on the grammar to produce the parser.
731 Compile the code output by Bison, as well as any other source files.
734 Link the object files to produce the finished product.
738 @section The Overall Layout of a Bison Grammar
741 @cindex format of grammar file
742 @cindex layout of Bison grammar
744 The input file for the Bison utility is a @dfn{Bison grammar file}. The
745 general form of a Bison grammar file is as follows:
752 @var{Bison declarations}
757 @var{Additional C code}
761 The @samp{%%}, @samp{%@{} and @samp{%@}} are punctuation that appears
762 in every Bison grammar file to separate the sections.
764 The C declarations may define types and variables used in the actions.
765 You can also use preprocessor commands to define macros used there, and use
766 @code{#include} to include header files that do any of these things.
768 The Bison declarations declare the names of the terminal and nonterminal
769 symbols, and may also describe operator precedence and the data types of
770 semantic values of various symbols.
772 The grammar rules define how to construct each nonterminal symbol from its
775 The additional C code can contain any C code you want to use. Often the
776 definition of the lexical analyzer @code{yylex} goes here, plus subroutines
777 called by the actions in the grammar rules. In a simple program, all the
778 rest of the program can go here.
782 @cindex simple examples
783 @cindex examples, simple
785 Now we show and explain three sample programs written using Bison: a
786 reverse polish notation calculator, an algebraic (infix) notation
787 calculator, and a multi-function calculator. All three have been tested
788 under BSD Unix 4.3; each produces a usable, though limited, interactive
791 These examples are simple, but Bison grammars for real programming
792 languages are written the same way.
794 You can copy these examples out of the Info file and into a source file
799 * RPN Calc:: Reverse polish notation calculator;
800 a first example with no operator precedence.
801 * Infix Calc:: Infix (algebraic) notation calculator.
802 Operator precedence is introduced.
803 * Simple Error Recovery:: Continuing after syntax errors.
804 * Location Tracking Calc:: Demonstrating the use of @@@var{n} and @@$.
805 * Multi-function Calc:: Calculator with memory and trig functions.
806 It uses multiple data-types for semantic values.
807 * Exercises:: Ideas for improving the multi-function calculator.
811 @section Reverse Polish Notation Calculator
812 @cindex reverse polish notation
813 @cindex polish notation calculator
814 @cindex @code{rpcalc}
815 @cindex calculator, simple
817 The first example is that of a simple double-precision @dfn{reverse polish
818 notation} calculator (a calculator using postfix operators). This example
819 provides a good starting point, since operator precedence is not an issue.
820 The second example will illustrate how operator precedence is handled.
822 The source code for this calculator is named @file{rpcalc.y}. The
823 @samp{.y} extension is a convention used for Bison input files.
826 * Decls: Rpcalc Decls. Bison and C declarations for rpcalc.
827 * Rules: Rpcalc Rules. Grammar Rules for rpcalc, with explanation.
828 * Lexer: Rpcalc Lexer. The lexical analyzer.
829 * Main: Rpcalc Main. The controlling function.
830 * Error: Rpcalc Error. The error reporting function.
831 * Gen: Rpcalc Gen. Running Bison on the grammar file.
832 * Comp: Rpcalc Compile. Run the C compiler on the output code.
836 @subsection Declarations for @code{rpcalc}
838 Here are the C and Bison declarations for the reverse polish notation
839 calculator. As in C, comments are placed between @samp{/*@dots{}*/}.
842 /* Reverse polish notation calculator. */
845 #define YYSTYPE double
851 %% /* Grammar rules and actions follow */
854 The C declarations section (@pxref{C Declarations, ,The C Declarations Section}) contains two
855 preprocessor directives.
857 The @code{#define} directive defines the macro @code{YYSTYPE}, thus
858 specifying the C data type for semantic values of both tokens and groupings
859 (@pxref{Value Type, ,Data Types of Semantic Values}). The Bison parser will use whatever type
860 @code{YYSTYPE} is defined as; if you don't define it, @code{int} is the
861 default. Because we specify @code{double}, each token and each expression
862 has an associated value, which is a floating point number.
864 The @code{#include} directive is used to declare the exponentiation
867 The second section, Bison declarations, provides information to Bison about
868 the token types (@pxref{Bison Declarations, ,The Bison Declarations Section}). Each terminal symbol that is
869 not a single-character literal must be declared here. (Single-character
870 literals normally don't need to be declared.) In this example, all the
871 arithmetic operators are designated by single-character literals, so the
872 only terminal symbol that needs to be declared is @code{NUM}, the token
873 type for numeric constants.
876 @subsection Grammar Rules for @code{rpcalc}
878 Here are the grammar rules for the reverse polish notation calculator.
886 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
889 exp: NUM @{ $$ = $1; @}
890 | exp exp '+' @{ $$ = $1 + $2; @}
891 | exp exp '-' @{ $$ = $1 - $2; @}
892 | exp exp '*' @{ $$ = $1 * $2; @}
893 | exp exp '/' @{ $$ = $1 / $2; @}
895 | exp exp '^' @{ $$ = pow ($1, $2); @}
897 | exp 'n' @{ $$ = -$1; @}
902 The groupings of the rpcalc ``language'' defined here are the expression
903 (given the name @code{exp}), the line of input (@code{line}), and the
904 complete input transcript (@code{input}). Each of these nonterminal
905 symbols has several alternate rules, joined by the @samp{|} punctuator
906 which is read as ``or''. The following sections explain what these rules
909 The semantics of the language is determined by the actions taken when a
910 grouping is recognized. The actions are the C code that appears inside
911 braces. @xref{Actions}.
913 You must specify these actions in C, but Bison provides the means for
914 passing semantic values between the rules. In each action, the
915 pseudo-variable @code{$$} stands for the semantic value for the grouping
916 that the rule is going to construct. Assigning a value to @code{$$} is the
917 main job of most actions. The semantic values of the components of the
918 rule are referred to as @code{$1}, @code{$2}, and so on.
927 @subsubsection Explanation of @code{input}
929 Consider the definition of @code{input}:
937 This definition reads as follows: ``A complete input is either an empty
938 string, or a complete input followed by an input line''. Notice that
939 ``complete input'' is defined in terms of itself. This definition is said
940 to be @dfn{left recursive} since @code{input} appears always as the
941 leftmost symbol in the sequence. @xref{Recursion, ,Recursive Rules}.
943 The first alternative is empty because there are no symbols between the
944 colon and the first @samp{|}; this means that @code{input} can match an
945 empty string of input (no tokens). We write the rules this way because it
946 is legitimate to type @kbd{Ctrl-d} right after you start the calculator.
947 It's conventional to put an empty alternative first and write the comment
948 @samp{/* empty */} in it.
950 The second alternate rule (@code{input line}) handles all nontrivial input.
951 It means, ``After reading any number of lines, read one more line if
952 possible.'' The left recursion makes this rule into a loop. Since the
953 first alternative matches empty input, the loop can be executed zero or
956 The parser function @code{yyparse} continues to process input until a
957 grammatical error is seen or the lexical analyzer says there are no more
958 input tokens; we will arrange for the latter to happen at end of file.
961 @subsubsection Explanation of @code{line}
963 Now consider the definition of @code{line}:
967 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
971 The first alternative is a token which is a newline character; this means
972 that rpcalc accepts a blank line (and ignores it, since there is no
973 action). The second alternative is an expression followed by a newline.
974 This is the alternative that makes rpcalc useful. The semantic value of
975 the @code{exp} grouping is the value of @code{$1} because the @code{exp} in
976 question is the first symbol in the alternative. The action prints this
977 value, which is the result of the computation the user asked for.
979 This action is unusual because it does not assign a value to @code{$$}. As
980 a consequence, the semantic value associated with the @code{line} is
981 uninitialized (its value will be unpredictable). This would be a bug if
982 that value were ever used, but we don't use it: once rpcalc has printed the
983 value of the user's input line, that value is no longer needed.
986 @subsubsection Explanation of @code{expr}
988 The @code{exp} grouping has several rules, one for each kind of expression.
989 The first rule handles the simplest expressions: those that are just numbers.
990 The second handles an addition-expression, which looks like two expressions
991 followed by a plus-sign. The third handles subtraction, and so on.
995 | exp exp '+' @{ $$ = $1 + $2; @}
996 | exp exp '-' @{ $$ = $1 - $2; @}
1001 We have used @samp{|} to join all the rules for @code{exp}, but we could
1002 equally well have written them separately:
1006 exp: exp exp '+' @{ $$ = $1 + $2; @} ;
1007 exp: exp exp '-' @{ $$ = $1 - $2; @} ;
1011 Most of the rules have actions that compute the value of the expression in
1012 terms of the value of its parts. For example, in the rule for addition,
1013 @code{$1} refers to the first component @code{exp} and @code{$2} refers to
1014 the second one. The third component, @code{'+'}, has no meaningful
1015 associated semantic value, but if it had one you could refer to it as
1016 @code{$3}. When @code{yyparse} recognizes a sum expression using this
1017 rule, the sum of the two subexpressions' values is produced as the value of
1018 the entire expression. @xref{Actions}.
1020 You don't have to give an action for every rule. When a rule has no
1021 action, Bison by default copies the value of @code{$1} into @code{$$}.
1022 This is what happens in the first rule (the one that uses @code{NUM}).
1024 The formatting shown here is the recommended convention, but Bison does
1025 not require it. You can add or change whitespace as much as you wish.
1029 exp : NUM | exp exp '+' @{$$ = $1 + $2; @} | @dots{}
1033 means the same thing as this:
1037 | exp exp '+' @{ $$ = $1 + $2; @}
1042 The latter, however, is much more readable.
1045 @subsection The @code{rpcalc} Lexical Analyzer
1046 @cindex writing a lexical analyzer
1047 @cindex lexical analyzer, writing
1049 The lexical analyzer's job is low-level parsing: converting characters or
1050 sequences of characters into tokens. The Bison parser gets its tokens by
1051 calling the lexical analyzer. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
1053 Only a simple lexical analyzer is needed for the RPN calculator. This
1054 lexical analyzer skips blanks and tabs, then reads in numbers as
1055 @code{double} and returns them as @code{NUM} tokens. Any other character
1056 that isn't part of a number is a separate token. Note that the token-code
1057 for such a single-character token is the character itself.
1059 The return value of the lexical analyzer function is a numeric code which
1060 represents a token type. The same text used in Bison rules to stand for
1061 this token type is also a C expression for the numeric code for the type.
1062 This works in two ways. If the token type is a character literal, then its
1063 numeric code is the ASCII code for that character; you can use the same
1064 character literal in the lexical analyzer to express the number. If the
1065 token type is an identifier, that identifier is defined by Bison as a C
1066 macro whose definition is the appropriate number. In this example,
1067 therefore, @code{NUM} becomes a macro for @code{yylex} to use.
1069 The semantic value of the token (if it has one) is stored into the global
1070 variable @code{yylval}, which is where the Bison parser will look for it.
1071 (The C data type of @code{yylval} is @code{YYSTYPE}, which was defined
1072 at the beginning of the grammar; @pxref{Rpcalc Decls, ,Declarations for @code{rpcalc}}.)
1074 A token type code of zero is returned if the end-of-file is encountered.
1075 (Bison recognizes any nonpositive value as indicating the end of the
1078 Here is the code for the lexical analyzer:
1082 /* Lexical analyzer returns a double floating point
1083 number on the stack and the token NUM, or the ASCII
1084 character read if not a number. Skips all blanks
1085 and tabs, returns 0 for EOF. */
1096 /* skip white space */
1097 while ((c = getchar ()) == ' ' || c == '\t')
1101 /* process numbers */
1102 if (c == '.' || isdigit (c))
1105 scanf ("%lf", &yylval);
1110 /* return end-of-file */
1113 /* return single chars */
1120 @subsection The Controlling Function
1121 @cindex controlling function
1122 @cindex main function in simple example
1124 In keeping with the spirit of this example, the controlling function is
1125 kept to the bare minimum. The only requirement is that it call
1126 @code{yyparse} to start the process of parsing.
1139 @subsection The Error Reporting Routine
1140 @cindex error reporting routine
1142 When @code{yyparse} detects a syntax error, it calls the error reporting
1143 function @code{yyerror} to print an error message (usually but not
1144 always @code{"parse error"}). It is up to the programmer to supply
1145 @code{yyerror} (@pxref{Interface, ,Parser C-Language Interface}), so
1146 here is the definition we will use:
1153 yyerror (const char *s) /* Called by yyparse on error */
1160 After @code{yyerror} returns, the Bison parser may recover from the error
1161 and continue parsing if the grammar contains a suitable error rule
1162 (@pxref{Error Recovery}). Otherwise, @code{yyparse} returns nonzero. We
1163 have not written any error rules in this example, so any invalid input will
1164 cause the calculator program to exit. This is not clean behavior for a
1165 real calculator, but it is adequate for the first example.
1168 @subsection Running Bison to Make the Parser
1169 @cindex running Bison (introduction)
1171 Before running Bison to produce a parser, we need to decide how to
1172 arrange all the source code in one or more source files. For such a
1173 simple example, the easiest thing is to put everything in one file. The
1174 definitions of @code{yylex}, @code{yyerror} and @code{main} go at the
1175 end, in the ``additional C code'' section of the file (@pxref{Grammar
1176 Layout, ,The Overall Layout of a Bison Grammar}).
1178 For a large project, you would probably have several source files, and use
1179 @code{make} to arrange to recompile them.
1181 With all the source in a single file, you use the following command to
1182 convert it into a parser file:
1185 bison @var{file_name}.y
1189 In this example the file was called @file{rpcalc.y} (for ``Reverse Polish
1190 CALCulator''). Bison produces a file named @file{@var{file_name}.tab.c},
1191 removing the @samp{.y} from the original file name. The file output by
1192 Bison contains the source code for @code{yyparse}. The additional
1193 functions in the input file (@code{yylex}, @code{yyerror} and @code{main})
1194 are copied verbatim to the output.
1196 @node Rpcalc Compile
1197 @subsection Compiling the Parser File
1198 @cindex compiling the parser
1200 Here is how to compile and run the parser file:
1204 # @r{List files in current directory.}
1206 rpcalc.tab.c rpcalc.y
1210 # @r{Compile the Bison parser.}
1211 # @r{@samp{-lm} tells compiler to search math library for @code{pow}.}
1212 % cc rpcalc.tab.c -lm -o rpcalc
1216 # @r{List files again.}
1218 rpcalc rpcalc.tab.c rpcalc.y
1222 The file @file{rpcalc} now contains the executable code. Here is an
1223 example session using @code{rpcalc}.
1231 3 7 + 3 4 5 * + - n @r{Note the unary minus, @samp{n}}
1235 3 4 ^ @r{Exponentiation}
1237 ^D @r{End-of-file indicator}
1242 @section Infix Notation Calculator: @code{calc}
1243 @cindex infix notation calculator
1245 @cindex calculator, infix notation
1247 We now modify rpcalc to handle infix operators instead of postfix. Infix
1248 notation involves the concept of operator precedence and the need for
1249 parentheses nested to arbitrary depth. Here is the Bison code for
1250 @file{calc.y}, an infix desk-top calculator.
1253 /* Infix notation calculator--calc */
1256 #define YYSTYPE double
1260 /* BISON Declarations */
1264 %left NEG /* negation--unary minus */
1265 %right '^' /* exponentiation */
1267 /* Grammar follows */
1269 input: /* empty string */
1274 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1277 exp: NUM @{ $$ = $1; @}
1278 | exp '+' exp @{ $$ = $1 + $3; @}
1279 | exp '-' exp @{ $$ = $1 - $3; @}
1280 | exp '*' exp @{ $$ = $1 * $3; @}
1281 | exp '/' exp @{ $$ = $1 / $3; @}
1282 | '-' exp %prec NEG @{ $$ = -$2; @}
1283 | exp '^' exp @{ $$ = pow ($1, $3); @}
1284 | '(' exp ')' @{ $$ = $2; @}
1290 The functions @code{yylex}, @code{yyerror} and @code{main} can be the
1293 There are two important new features shown in this code.
1295 In the second section (Bison declarations), @code{%left} declares token
1296 types and says they are left-associative operators. The declarations
1297 @code{%left} and @code{%right} (right associativity) take the place of
1298 @code{%token} which is used to declare a token type name without
1299 associativity. (These tokens are single-character literals, which
1300 ordinarily don't need to be declared. We declare them here to specify
1303 Operator precedence is determined by the line ordering of the
1304 declarations; the higher the line number of the declaration (lower on
1305 the page or screen), the higher the precedence. Hence, exponentiation
1306 has the highest precedence, unary minus (@code{NEG}) is next, followed
1307 by @samp{*} and @samp{/}, and so on. @xref{Precedence, ,Operator Precedence}.
1309 The other important new feature is the @code{%prec} in the grammar section
1310 for the unary minus operator. The @code{%prec} simply instructs Bison that
1311 the rule @samp{| '-' exp} has the same precedence as @code{NEG}---in this
1312 case the next-to-highest. @xref{Contextual Precedence, ,Context-Dependent Precedence}.
1314 Here is a sample run of @file{calc.y}:
1319 4 + 4.5 - (34/(8*3+-3))
1327 @node Simple Error Recovery
1328 @section Simple Error Recovery
1329 @cindex error recovery, simple
1331 Up to this point, this manual has not addressed the issue of @dfn{error
1332 recovery}---how to continue parsing after the parser detects a syntax
1333 error. All we have handled is error reporting with @code{yyerror}.
1334 Recall that by default @code{yyparse} returns after calling
1335 @code{yyerror}. This means that an erroneous input line causes the
1336 calculator program to exit. Now we show how to rectify this deficiency.
1338 The Bison language itself includes the reserved word @code{error}, which
1339 may be included in the grammar rules. In the example below it has
1340 been added to one of the alternatives for @code{line}:
1345 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1346 | error '\n' @{ yyerrok; @}
1351 This addition to the grammar allows for simple error recovery in the
1352 event of a parse error. If an expression that cannot be evaluated is
1353 read, the error will be recognized by the third rule for @code{line},
1354 and parsing will continue. (The @code{yyerror} function is still called
1355 upon to print its message as well.) The action executes the statement
1356 @code{yyerrok}, a macro defined automatically by Bison; its meaning is
1357 that error recovery is complete (@pxref{Error Recovery}). Note the
1358 difference between @code{yyerrok} and @code{yyerror}; neither one is a
1361 This form of error recovery deals with syntax errors. There are other
1362 kinds of errors; for example, division by zero, which raises an exception
1363 signal that is normally fatal. A real calculator program must handle this
1364 signal and use @code{longjmp} to return to @code{main} and resume parsing
1365 input lines; it would also have to discard the rest of the current line of
1366 input. We won't discuss this issue further because it is not specific to
1369 @node Location Tracking Calc
1370 @section Location Tracking Calculator: @code{ltcalc}
1371 @cindex location tracking calculator
1372 @cindex @code{ltcalc}
1373 @cindex calculator, location tracking
1375 This example extends the infix notation calculator with location tracking.
1376 This feature will be used to improve error reporting, and provide better
1379 For the sake of clarity, we will switch for this example to an integer
1380 calculator, since most of the work needed to use locations will be done
1381 in the lexical analyser.
1384 * Decls: Ltcalc Decls. Bison and C declarations for ltcalc.
1385 * Rules: Ltcalc Rules. Grammar rules for ltcalc, with explanations.
1386 * Lexer: Ltcalc Lexer. The lexical analyzer.
1390 @subsection Declarations for @code{ltcalc}
1392 The C and Bison declarations for the location tracking calculator are the same
1393 as the declarations for the infix notation calculator.
1396 /* Location tracking calculator. */
1403 /* Bison declarations. */
1411 %% /* Grammar follows */
1414 In the code above, there are no declarations specific to locations. Defining
1415 a data type for storing locations is not needed: we will use the type provided
1416 by default (@pxref{Location Type, ,Data Types of Locations}), which is a four
1417 member structure with the following integer fields: @code{first_line},
1418 @code{first_column}, @code{last_line} and @code{last_column}.
1421 @subsection Grammar Rules for @code{ltcalc}
1423 Whether you choose to handle locations or not has no effect on the syntax of
1424 your language. Therefore, grammar rules for this example will be very close to
1425 those of the previous example: we will only modify them to benefit from the new
1426 informations we will have.
1428 Here, we will use locations to report divisions by zero, and locate the wrong
1429 expressions or subexpressions.
1440 | exp '\n' @{ printf ("%d\n", $1); @}
1445 exp : NUM @{ $$ = $1; @}
1446 | exp '+' exp @{ $$ = $1 + $3; @}
1447 | exp '-' exp @{ $$ = $1 - $3; @}
1448 | exp '*' exp @{ $$ = $1 * $3; @}
1458 printf("Division by zero, l%d,c%d-l%d,c%d",
1459 @@3.first_line, @@3.first_column,
1460 @@3.last_line, @@3.last_column);
1465 | '-' exp %preg NEG @{ $$ = -$2; @}
1466 | exp '^' exp @{ $$ = pow ($1, $3); @}
1467 | '(' exp ')' @{ $$ = $2; @}
1471 This code shows how to reach locations inside of semantic actions, by
1472 using the pseudo-variables @code{@@@var{n}} for rule components, and the
1473 pseudo-variable @code{@@$} for groupings.
1475 In this example, we never assign a value to @code{@@$}, because the
1476 output parser can do this automatically. By default, before executing
1477 the C code of each action, @code{@@$} is set to range from the beginning
1478 of @code{@@1} to the end of @code{@@@var{n}}, for a rule with @var{n}
1481 Of course, this behavior can be redefined (@pxref{Location Default
1482 Action, , Default Action for Locations}), and for very specific rules,
1483 @code{@@$} can be computed by hand.
1486 @subsection The @code{ltcalc} Lexical Analyzer.
1488 Until now, we relied on Bison's defaults to enable location tracking. The next
1489 step is to rewrite the lexical analyser, and make it able to feed the parser
1490 with locations of tokens, as he already does for semantic values.
1492 To do so, we must take into account every single character of the input text,
1493 to avoid the computed locations of being fuzzy or wrong:
1502 /* skip white space */
1503 while ((c = getchar ()) == ' ' || c == '\t')
1504 ++yylloc.last_column;
1507 yylloc.first_line = yylloc.last_line;
1508 yylloc.first_column = yylloc.last_column;
1512 /* process numbers */
1516 ++yylloc.last_column;
1517 while (isdigit (c = getchar ()))
1519 ++yylloc.last_column;
1520 yylval = yylval * 10 + c - '0';
1527 /* return end-of-file */
1531 /* return single chars and update location */
1535 yylloc.last_column = 0;
1538 ++yylloc.last_column;
1543 Basically, the lexical analyzer does the same processing as before: it skips
1544 blanks and tabs, and reads numbers or single-character tokens. In addition
1545 to this, it updates the @code{yylloc} global variable (of type @code{YYLTYPE}),
1546 where the location of tokens is stored.
1548 Now, each time this function returns a token, the parser has it's number as
1549 well as it's semantic value, and it's position in the text. The last needed
1550 change is to initialize @code{yylloc}, for example in the controlling
1557 yylloc.first_line = yylloc.last_line = 1;
1558 yylloc.first_column = yylloc.last_column = 0;
1563 Remember that computing locations is not a matter of syntax. Every character
1564 must be associated to a location update, whether it is in valid input, in
1565 comments, in literal strings, and so on...
1567 @node Multi-function Calc
1568 @section Multi-Function Calculator: @code{mfcalc}
1569 @cindex multi-function calculator
1570 @cindex @code{mfcalc}
1571 @cindex calculator, multi-function
1573 Now that the basics of Bison have been discussed, it is time to move on to
1574 a more advanced problem. The above calculators provided only five
1575 functions, @samp{+}, @samp{-}, @samp{*}, @samp{/} and @samp{^}. It would
1576 be nice to have a calculator that provides other mathematical functions such
1577 as @code{sin}, @code{cos}, etc.
1579 It is easy to add new operators to the infix calculator as long as they are
1580 only single-character literals. The lexical analyzer @code{yylex} passes
1581 back all nonnumber characters as tokens, so new grammar rules suffice for
1582 adding a new operator. But we want something more flexible: built-in
1583 functions whose syntax has this form:
1586 @var{function_name} (@var{argument})
1590 At the same time, we will add memory to the calculator, by allowing you
1591 to create named variables, store values in them, and use them later.
1592 Here is a sample session with the multi-function calculator:
1611 Note that multiple assignment and nested function calls are permitted.
1614 * Decl: Mfcalc Decl. Bison declarations for multi-function calculator.
1615 * Rules: Mfcalc Rules. Grammar rules for the calculator.
1616 * Symtab: Mfcalc Symtab. Symbol table management subroutines.
1620 @subsection Declarations for @code{mfcalc}
1622 Here are the C and Bison declarations for the multi-function calculator.
1626 #include <math.h> /* For math functions, cos(), sin(), etc. */
1627 #include "calc.h" /* Contains definition of `symrec' */
1630 double val; /* For returning numbers. */
1631 symrec *tptr; /* For returning symbol-table pointers */
1634 %token <val> NUM /* Simple double precision number */
1635 %token <tptr> VAR FNCT /* Variable and Function */
1641 %left NEG /* Negation--unary minus */
1642 %right '^' /* Exponentiation */
1644 /* Grammar follows */
1649 The above grammar introduces only two new features of the Bison language.
1650 These features allow semantic values to have various data types
1651 (@pxref{Multiple Types, ,More Than One Value Type}).
1653 The @code{%union} declaration specifies the entire list of possible types;
1654 this is instead of defining @code{YYSTYPE}. The allowable types are now
1655 double-floats (for @code{exp} and @code{NUM}) and pointers to entries in
1656 the symbol table. @xref{Union Decl, ,The Collection of Value Types}.
1658 Since values can now have various types, it is necessary to associate a
1659 type with each grammar symbol whose semantic value is used. These symbols
1660 are @code{NUM}, @code{VAR}, @code{FNCT}, and @code{exp}. Their
1661 declarations are augmented with information about their data type (placed
1662 between angle brackets).
1664 The Bison construct @code{%type} is used for declaring nonterminal symbols,
1665 just as @code{%token} is used for declaring token types. We have not used
1666 @code{%type} before because nonterminal symbols are normally declared
1667 implicitly by the rules that define them. But @code{exp} must be declared
1668 explicitly so we can specify its value type. @xref{Type Decl, ,Nonterminal Symbols}.
1671 @subsection Grammar Rules for @code{mfcalc}
1673 Here are the grammar rules for the multi-function calculator.
1674 Most of them are copied directly from @code{calc}; three rules,
1675 those which mention @code{VAR} or @code{FNCT}, are new.
1684 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1685 | error '\n' @{ yyerrok; @}
1688 exp: NUM @{ $$ = $1; @}
1689 | VAR @{ $$ = $1->value.var; @}
1690 | VAR '=' exp @{ $$ = $3; $1->value.var = $3; @}
1691 | FNCT '(' exp ')' @{ $$ = (*($1->value.fnctptr))($3); @}
1692 | exp '+' exp @{ $$ = $1 + $3; @}
1693 | exp '-' exp @{ $$ = $1 - $3; @}
1694 | exp '*' exp @{ $$ = $1 * $3; @}
1695 | exp '/' exp @{ $$ = $1 / $3; @}
1696 | '-' exp %prec NEG @{ $$ = -$2; @}
1697 | exp '^' exp @{ $$ = pow ($1, $3); @}
1698 | '(' exp ')' @{ $$ = $2; @}
1700 /* End of grammar */
1705 @subsection The @code{mfcalc} Symbol Table
1706 @cindex symbol table example
1708 The multi-function calculator requires a symbol table to keep track of the
1709 names and meanings of variables and functions. This doesn't affect the
1710 grammar rules (except for the actions) or the Bison declarations, but it
1711 requires some additional C functions for support.
1713 The symbol table itself consists of a linked list of records. Its
1714 definition, which is kept in the header @file{calc.h}, is as follows. It
1715 provides for either functions or variables to be placed in the table.
1719 /* Fonctions type. */
1720 typedef double (*func_t) (double);
1722 /* Data type for links in the chain of symbols. */
1725 char *name; /* name of symbol */
1726 int type; /* type of symbol: either VAR or FNCT */
1729 double var; /* value of a VAR */
1730 func_t fnctptr; /* value of a FNCT */
1732 struct symrec *next; /* link field */
1737 typedef struct symrec symrec;
1739 /* The symbol table: a chain of `struct symrec'. */
1740 extern symrec *sym_table;
1742 symrec *putsym (const char *, func_t);
1743 symrec *getsym (const char *);
1747 The new version of @code{main} includes a call to @code{init_table}, a
1748 function that initializes the symbol table. Here it is, and
1749 @code{init_table} as well:
1765 yyerror (const char *s) /* Called by yyparse on error */
1773 double (*fnct)(double);
1778 struct init arith_fncts[] =
1789 /* The symbol table: a chain of `struct symrec'. */
1790 symrec *sym_table = (symrec *) 0;
1794 /* Put arithmetic functions in table. */
1800 for (i = 0; arith_fncts[i].fname != 0; i++)
1802 ptr = putsym (arith_fncts[i].fname, FNCT);
1803 ptr->value.fnctptr = arith_fncts[i].fnct;
1809 By simply editing the initialization list and adding the necessary include
1810 files, you can add additional functions to the calculator.
1812 Two important functions allow look-up and installation of symbols in the
1813 symbol table. The function @code{putsym} is passed a name and the type
1814 (@code{VAR} or @code{FNCT}) of the object to be installed. The object is
1815 linked to the front of the list, and a pointer to the object is returned.
1816 The function @code{getsym} is passed the name of the symbol to look up. If
1817 found, a pointer to that symbol is returned; otherwise zero is returned.
1821 putsym (char *sym_name, int sym_type)
1824 ptr = (symrec *) malloc (sizeof (symrec));
1825 ptr->name = (char *) malloc (strlen (sym_name) + 1);
1826 strcpy (ptr->name,sym_name);
1827 ptr->type = sym_type;
1828 ptr->value.var = 0; /* set value to 0 even if fctn. */
1829 ptr->next = (struct symrec *)sym_table;
1835 getsym (const char *sym_name)
1838 for (ptr = sym_table; ptr != (symrec *) 0;
1839 ptr = (symrec *)ptr->next)
1840 if (strcmp (ptr->name,sym_name) == 0)
1846 The function @code{yylex} must now recognize variables, numeric values, and
1847 the single-character arithmetic operators. Strings of alphanumeric
1848 characters with a leading non-digit are recognized as either variables or
1849 functions depending on what the symbol table says about them.
1851 The string is passed to @code{getsym} for look up in the symbol table. If
1852 the name appears in the table, a pointer to its location and its type
1853 (@code{VAR} or @code{FNCT}) is returned to @code{yyparse}. If it is not
1854 already in the table, then it is installed as a @code{VAR} using
1855 @code{putsym}. Again, a pointer and its type (which must be @code{VAR}) is
1856 returned to @code{yyparse}.@refill
1858 No change is needed in the handling of numeric values and arithmetic
1859 operators in @code{yylex}.
1870 /* Ignore whitespace, get first nonwhite character. */
1871 while ((c = getchar ()) == ' ' || c == '\t');
1878 /* Char starts a number => parse the number. */
1879 if (c == '.' || isdigit (c))
1882 scanf ("%lf", &yylval.val);
1888 /* Char starts an identifier => read the name. */
1892 static char *symbuf = 0;
1893 static int length = 0;
1898 /* Initially make the buffer long enough
1899 for a 40-character symbol name. */
1901 length = 40, symbuf = (char *)malloc (length + 1);
1908 /* If buffer is full, make it bigger. */
1912 symbuf = (char *)realloc (symbuf, length + 1);
1914 /* Add this character to the buffer. */
1916 /* Get another character. */
1921 while (c != EOF && isalnum (c));
1928 s = getsym (symbuf);
1930 s = putsym (symbuf, VAR);
1935 /* Any other character is a token by itself. */
1941 This program is both powerful and flexible. You may easily add new
1942 functions, and it is a simple job to modify this code to install predefined
1943 variables such as @code{pi} or @code{e} as well.
1951 Add some new functions from @file{math.h} to the initialization list.
1954 Add another array that contains constants and their values. Then
1955 modify @code{init_table} to add these constants to the symbol table.
1956 It will be easiest to give the constants type @code{VAR}.
1959 Make the program report an error if the user refers to an
1960 uninitialized variable in any way except to store a value in it.
1964 @chapter Bison Grammar Files
1966 Bison takes as input a context-free grammar specification and produces a
1967 C-language function that recognizes correct instances of the grammar.
1969 The Bison grammar input file conventionally has a name ending in @samp{.y}.
1970 @xref{Invocation, ,Invoking Bison}.
1973 * Grammar Outline:: Overall layout of the grammar file.
1974 * Symbols:: Terminal and nonterminal symbols.
1975 * Rules:: How to write grammar rules.
1976 * Recursion:: Writing recursive rules.
1977 * Semantics:: Semantic values and actions.
1978 * Locations:: Locations and actions.
1979 * Declarations:: All kinds of Bison declarations are described here.
1980 * Multiple Parsers:: Putting more than one Bison parser in one program.
1983 @node Grammar Outline
1984 @section Outline of a Bison Grammar
1986 A Bison grammar file has four main sections, shown here with the
1987 appropriate delimiters:
1991 @var{C declarations}
1994 @var{Bison declarations}
2000 @var{Additional C code}
2003 Comments enclosed in @samp{/* @dots{} */} may appear in any of the sections.
2006 * C Declarations:: Syntax and usage of the C declarations section.
2007 * Bison Declarations:: Syntax and usage of the Bison declarations section.
2008 * Grammar Rules:: Syntax and usage of the grammar rules section.
2009 * C Code:: Syntax and usage of the additional C code section.
2012 @node C Declarations
2013 @subsection The C Declarations Section
2014 @cindex C declarations section
2015 @cindex declarations, C
2017 The @var{C declarations} section contains macro definitions and
2018 declarations of functions and variables that are used in the actions in the
2019 grammar rules. These are copied to the beginning of the parser file so
2020 that they precede the definition of @code{yyparse}. You can use
2021 @samp{#include} to get the declarations from a header file. If you don't
2022 need any C declarations, you may omit the @samp{%@{} and @samp{%@}}
2023 delimiters that bracket this section.
2025 @node Bison Declarations
2026 @subsection The Bison Declarations Section
2027 @cindex Bison declarations (introduction)
2028 @cindex declarations, Bison (introduction)
2030 The @var{Bison declarations} section contains declarations that define
2031 terminal and nonterminal symbols, specify precedence, and so on.
2032 In some simple grammars you may not need any declarations.
2033 @xref{Declarations, ,Bison Declarations}.
2036 @subsection The Grammar Rules Section
2037 @cindex grammar rules section
2038 @cindex rules section for grammar
2040 The @dfn{grammar rules} section contains one or more Bison grammar
2041 rules, and nothing else. @xref{Rules, ,Syntax of Grammar Rules}.
2043 There must always be at least one grammar rule, and the first
2044 @samp{%%} (which precedes the grammar rules) may never be omitted even
2045 if it is the first thing in the file.
2048 @subsection The Additional C Code Section
2049 @cindex additional C code section
2050 @cindex C code, section for additional
2052 The @var{additional C code} section is copied verbatim to the end of the
2053 parser file, just as the @var{C declarations} section is copied to the
2054 beginning. This is the most convenient place to put anything that you
2055 want to have in the parser file but which need not come before the
2056 definition of @code{yyparse}. For example, the definitions of
2057 @code{yylex} and @code{yyerror} often go here. @xref{Interface, ,Parser
2058 C-Language Interface}.
2060 If the last section is empty, you may omit the @samp{%%} that separates it
2061 from the grammar rules.
2063 The Bison parser itself contains many static variables whose names start
2064 with @samp{yy} and many macros whose names start with @samp{YY}. It is a
2065 good idea to avoid using any such names (except those documented in this
2066 manual) in the additional C code section of the grammar file.
2069 @section Symbols, Terminal and Nonterminal
2070 @cindex nonterminal symbol
2071 @cindex terminal symbol
2075 @dfn{Symbols} in Bison grammars represent the grammatical classifications
2078 A @dfn{terminal symbol} (also known as a @dfn{token type}) represents a
2079 class of syntactically equivalent tokens. You use the symbol in grammar
2080 rules to mean that a token in that class is allowed. The symbol is
2081 represented in the Bison parser by a numeric code, and the @code{yylex}
2082 function returns a token type code to indicate what kind of token has been
2083 read. You don't need to know what the code value is; you can use the
2084 symbol to stand for it.
2086 A @dfn{nonterminal symbol} stands for a class of syntactically equivalent
2087 groupings. The symbol name is used in writing grammar rules. By convention,
2088 it should be all lower case.
2090 Symbol names can contain letters, digits (not at the beginning),
2091 underscores and periods. Periods make sense only in nonterminals.
2093 There are three ways of writing terminal symbols in the grammar:
2097 A @dfn{named token type} is written with an identifier, like an
2098 identifier in C. By convention, it should be all upper case. Each
2099 such name must be defined with a Bison declaration such as
2100 @code{%token}. @xref{Token Decl, ,Token Type Names}.
2103 @cindex character token
2104 @cindex literal token
2105 @cindex single-character literal
2106 A @dfn{character token type} (or @dfn{literal character token}) is
2107 written in the grammar using the same syntax used in C for character
2108 constants; for example, @code{'+'} is a character token type. A
2109 character token type doesn't need to be declared unless you need to
2110 specify its semantic value data type (@pxref{Value Type, ,Data Types of
2111 Semantic Values}), associativity, or precedence (@pxref{Precedence,
2112 ,Operator Precedence}).
2114 By convention, a character token type is used only to represent a
2115 token that consists of that particular character. Thus, the token
2116 type @code{'+'} is used to represent the character @samp{+} as a
2117 token. Nothing enforces this convention, but if you depart from it,
2118 your program will confuse other readers.
2120 All the usual escape sequences used in character literals in C can be
2121 used in Bison as well, but you must not use the null character as a
2122 character literal because its ASCII code, zero, is the code @code{yylex}
2123 returns for end-of-input (@pxref{Calling Convention, ,Calling Convention
2127 @cindex string token
2128 @cindex literal string token
2129 @cindex multicharacter literal
2130 A @dfn{literal string token} is written like a C string constant; for
2131 example, @code{"<="} is a literal string token. A literal string token
2132 doesn't need to be declared unless you need to specify its semantic
2133 value data type (@pxref{Value Type}), associativity, or precedence
2134 (@pxref{Precedence}).
2136 You can associate the literal string token with a symbolic name as an
2137 alias, using the @code{%token} declaration (@pxref{Token Decl, ,Token
2138 Declarations}). If you don't do that, the lexical analyzer has to
2139 retrieve the token number for the literal string token from the
2140 @code{yytname} table (@pxref{Calling Convention}).
2142 @strong{WARNING}: literal string tokens do not work in Yacc.
2144 By convention, a literal string token is used only to represent a token
2145 that consists of that particular string. Thus, you should use the token
2146 type @code{"<="} to represent the string @samp{<=} as a token. Bison
2147 does not enforce this convention, but if you depart from it, people who
2148 read your program will be confused.
2150 All the escape sequences used in string literals in C can be used in
2151 Bison as well. A literal string token must contain two or more
2152 characters; for a token containing just one character, use a character
2156 How you choose to write a terminal symbol has no effect on its
2157 grammatical meaning. That depends only on where it appears in rules and
2158 on when the parser function returns that symbol.
2160 The value returned by @code{yylex} is always one of the terminal symbols
2161 (or 0 for end-of-input). Whichever way you write the token type in the
2162 grammar rules, you write it the same way in the definition of @code{yylex}.
2163 The numeric code for a character token type is simply the ASCII code for
2164 the character, so @code{yylex} can use the identical character constant to
2165 generate the requisite code. Each named token type becomes a C macro in
2166 the parser file, so @code{yylex} can use the name to stand for the code.
2167 (This is why periods don't make sense in terminal symbols.)
2168 @xref{Calling Convention, ,Calling Convention for @code{yylex}}.
2170 If @code{yylex} is defined in a separate file, you need to arrange for the
2171 token-type macro definitions to be available there. Use the @samp{-d}
2172 option when you run Bison, so that it will write these macro definitions
2173 into a separate header file @file{@var{name}.tab.h} which you can include
2174 in the other source files that need it. @xref{Invocation, ,Invoking Bison}.
2176 The symbol @code{error} is a terminal symbol reserved for error recovery
2177 (@pxref{Error Recovery}); you shouldn't use it for any other purpose.
2178 In particular, @code{yylex} should never return this value.
2181 @section Syntax of Grammar Rules
2183 @cindex grammar rule syntax
2184 @cindex syntax of grammar rules
2186 A Bison grammar rule has the following general form:
2190 @var{result}: @var{components}@dots{}
2196 where @var{result} is the nonterminal symbol that this rule describes,
2197 and @var{components} are various terminal and nonterminal symbols that
2198 are put together by this rule (@pxref{Symbols}).
2210 says that two groupings of type @code{exp}, with a @samp{+} token in between,
2211 can be combined into a larger grouping of type @code{exp}.
2213 Whitespace in rules is significant only to separate symbols. You can add
2214 extra whitespace as you wish.
2216 Scattered among the components can be @var{actions} that determine
2217 the semantics of the rule. An action looks like this:
2220 @{@var{C statements}@}
2224 Usually there is only one action and it follows the components.
2228 Multiple rules for the same @var{result} can be written separately or can
2229 be joined with the vertical-bar character @samp{|} as follows:
2233 @var{result}: @var{rule1-components}@dots{}
2234 | @var{rule2-components}@dots{}
2242 @var{result}: @var{rule1-components}@dots{}
2243 | @var{rule2-components}@dots{}
2251 They are still considered distinct rules even when joined in this way.
2253 If @var{components} in a rule is empty, it means that @var{result} can
2254 match the empty string. For example, here is how to define a
2255 comma-separated sequence of zero or more @code{exp} groupings:
2272 It is customary to write a comment @samp{/* empty */} in each rule
2276 @section Recursive Rules
2277 @cindex recursive rule
2279 A rule is called @dfn{recursive} when its @var{result} nonterminal appears
2280 also on its right hand side. Nearly all Bison grammars need to use
2281 recursion, because that is the only way to define a sequence of any number
2282 of a particular thing. Consider this recursive definition of a
2283 comma-separated sequence of one or more expressions:
2293 @cindex left recursion
2294 @cindex right recursion
2296 Since the recursive use of @code{expseq1} is the leftmost symbol in the
2297 right hand side, we call this @dfn{left recursion}. By contrast, here
2298 the same construct is defined using @dfn{right recursion}:
2309 Any kind of sequence can be defined using either left recursion or
2310 right recursion, but you should always use left recursion, because it
2311 can parse a sequence of any number of elements with bounded stack
2312 space. Right recursion uses up space on the Bison stack in proportion
2313 to the number of elements in the sequence, because all the elements
2314 must be shifted onto the stack before the rule can be applied even
2315 once. @xref{Algorithm, ,The Bison Parser Algorithm }, for
2316 further explanation of this.
2318 @cindex mutual recursion
2319 @dfn{Indirect} or @dfn{mutual} recursion occurs when the result of the
2320 rule does not appear directly on its right hand side, but does appear
2321 in rules for other nonterminals which do appear on its right hand
2329 | primary '+' primary
2341 defines two mutually-recursive nonterminals, since each refers to the
2345 @section Defining Language Semantics
2346 @cindex defining language semantics
2347 @cindex language semantics, defining
2349 The grammar rules for a language determine only the syntax. The semantics
2350 are determined by the semantic values associated with various tokens and
2351 groupings, and by the actions taken when various groupings are recognized.
2353 For example, the calculator calculates properly because the value
2354 associated with each expression is the proper number; it adds properly
2355 because the action for the grouping @w{@samp{@var{x} + @var{y}}} is to add
2356 the numbers associated with @var{x} and @var{y}.
2359 * Value Type:: Specifying one data type for all semantic values.
2360 * Multiple Types:: Specifying several alternative data types.
2361 * Actions:: An action is the semantic definition of a grammar rule.
2362 * Action Types:: Specifying data types for actions to operate on.
2363 * Mid-Rule Actions:: Most actions go at the end of a rule.
2364 This says when, why and how to use the exceptional
2365 action in the middle of a rule.
2369 @subsection Data Types of Semantic Values
2370 @cindex semantic value type
2371 @cindex value type, semantic
2372 @cindex data types of semantic values
2373 @cindex default data type
2375 In a simple program it may be sufficient to use the same data type for
2376 the semantic values of all language constructs. This was true in the
2377 RPN and infix calculator examples (@pxref{RPN Calc, ,Reverse Polish Notation Calculator}).
2379 Bison's default is to use type @code{int} for all semantic values. To
2380 specify some other type, define @code{YYSTYPE} as a macro, like this:
2383 #define YYSTYPE double
2387 This macro definition must go in the C declarations section of the grammar
2388 file (@pxref{Grammar Outline, ,Outline of a Bison Grammar}).
2390 @node Multiple Types
2391 @subsection More Than One Value Type
2393 In most programs, you will need different data types for different kinds
2394 of tokens and groupings. For example, a numeric constant may need type
2395 @code{int} or @code{long}, while a string constant needs type @code{char *},
2396 and an identifier might need a pointer to an entry in the symbol table.
2398 To use more than one data type for semantic values in one parser, Bison
2399 requires you to do two things:
2403 Specify the entire collection of possible data types, with the
2404 @code{%union} Bison declaration (@pxref{Union Decl, ,The Collection of Value Types}).
2407 Choose one of those types for each symbol (terminal or nonterminal) for
2408 which semantic values are used. This is done for tokens with the
2409 @code{%token} Bison declaration (@pxref{Token Decl, ,Token Type Names})
2410 and for groupings with the @code{%type} Bison declaration (@pxref{Type
2411 Decl, ,Nonterminal Symbols}).
2420 An action accompanies a syntactic rule and contains C code to be executed
2421 each time an instance of that rule is recognized. The task of most actions
2422 is to compute a semantic value for the grouping built by the rule from the
2423 semantic values associated with tokens or smaller groupings.
2425 An action consists of C statements surrounded by braces, much like a
2426 compound statement in C. It can be placed at any position in the rule; it
2427 is executed at that position. Most rules have just one action at the end
2428 of the rule, following all the components. Actions in the middle of a rule
2429 are tricky and used only for special purposes (@pxref{Mid-Rule Actions, ,Actions in Mid-Rule}).
2431 The C code in an action can refer to the semantic values of the components
2432 matched by the rule with the construct @code{$@var{n}}, which stands for
2433 the value of the @var{n}th component. The semantic value for the grouping
2434 being constructed is @code{$$}. (Bison translates both of these constructs
2435 into array element references when it copies the actions into the parser
2438 Here is a typical example:
2449 This rule constructs an @code{exp} from two smaller @code{exp} groupings
2450 connected by a plus-sign token. In the action, @code{$1} and @code{$3}
2451 refer to the semantic values of the two component @code{exp} groupings,
2452 which are the first and third symbols on the right hand side of the rule.
2453 The sum is stored into @code{$$} so that it becomes the semantic value of
2454 the addition-expression just recognized by the rule. If there were a
2455 useful semantic value associated with the @samp{+} token, it could be
2456 referred to as @code{$2}.@refill
2458 @cindex default action
2459 If you don't specify an action for a rule, Bison supplies a default:
2460 @w{@code{$$ = $1}.} Thus, the value of the first symbol in the rule becomes
2461 the value of the whole rule. Of course, the default rule is valid only
2462 if the two data types match. There is no meaningful default action for
2463 an empty rule; every empty rule must have an explicit action unless the
2464 rule's value does not matter.
2466 @code{$@var{n}} with @var{n} zero or negative is allowed for reference
2467 to tokens and groupings on the stack @emph{before} those that match the
2468 current rule. This is a very risky practice, and to use it reliably
2469 you must be certain of the context in which the rule is applied. Here
2470 is a case in which you can use this reliably:
2474 foo: expr bar '+' expr @{ @dots{} @}
2475 | expr bar '-' expr @{ @dots{} @}
2481 @{ previous_expr = $0; @}
2486 As long as @code{bar} is used only in the fashion shown here, @code{$0}
2487 always refers to the @code{expr} which precedes @code{bar} in the
2488 definition of @code{foo}.
2491 @subsection Data Types of Values in Actions
2492 @cindex action data types
2493 @cindex data types in actions
2495 If you have chosen a single data type for semantic values, the @code{$$}
2496 and @code{$@var{n}} constructs always have that data type.
2498 If you have used @code{%union} to specify a variety of data types, then you
2499 must declare a choice among these types for each terminal or nonterminal
2500 symbol that can have a semantic value. Then each time you use @code{$$} or
2501 @code{$@var{n}}, its data type is determined by which symbol it refers to
2502 in the rule. In this example,@refill
2513 @code{$1} and @code{$3} refer to instances of @code{exp}, so they all
2514 have the data type declared for the nonterminal symbol @code{exp}. If
2515 @code{$2} were used, it would have the data type declared for the
2516 terminal symbol @code{'+'}, whatever that might be.@refill
2518 Alternatively, you can specify the data type when you refer to the value,
2519 by inserting @samp{<@var{type}>} after the @samp{$} at the beginning of the
2520 reference. For example, if you have defined types as shown here:
2532 then you can write @code{$<itype>1} to refer to the first subunit of the
2533 rule as an integer, or @code{$<dtype>1} to refer to it as a double.
2535 @node Mid-Rule Actions
2536 @subsection Actions in Mid-Rule
2537 @cindex actions in mid-rule
2538 @cindex mid-rule actions
2540 Occasionally it is useful to put an action in the middle of a rule.
2541 These actions are written just like usual end-of-rule actions, but they
2542 are executed before the parser even recognizes the following components.
2544 A mid-rule action may refer to the components preceding it using
2545 @code{$@var{n}}, but it may not refer to subsequent components because
2546 it is run before they are parsed.
2548 The mid-rule action itself counts as one of the components of the rule.
2549 This makes a difference when there is another action later in the same rule
2550 (and usually there is another at the end): you have to count the actions
2551 along with the symbols when working out which number @var{n} to use in
2554 The mid-rule action can also have a semantic value. The action can set
2555 its value with an assignment to @code{$$}, and actions later in the rule
2556 can refer to the value using @code{$@var{n}}. Since there is no symbol
2557 to name the action, there is no way to declare a data type for the value
2558 in advance, so you must use the @samp{$<@dots{}>@var{n}} construct to
2559 specify a data type each time you refer to this value.
2561 There is no way to set the value of the entire rule with a mid-rule
2562 action, because assignments to @code{$$} do not have that effect. The
2563 only way to set the value for the entire rule is with an ordinary action
2564 at the end of the rule.
2566 Here is an example from a hypothetical compiler, handling a @code{let}
2567 statement that looks like @samp{let (@var{variable}) @var{statement}} and
2568 serves to create a variable named @var{variable} temporarily for the
2569 duration of @var{statement}. To parse this construct, we must put
2570 @var{variable} into the symbol table while @var{statement} is parsed, then
2571 remove it afterward. Here is how it is done:
2575 stmt: LET '(' var ')'
2576 @{ $<context>$ = push_context ();
2577 declare_variable ($3); @}
2579 pop_context ($<context>5); @}
2584 As soon as @samp{let (@var{variable})} has been recognized, the first
2585 action is run. It saves a copy of the current semantic context (the
2586 list of accessible variables) as its semantic value, using alternative
2587 @code{context} in the data-type union. Then it calls
2588 @code{declare_variable} to add the new variable to that list. Once the
2589 first action is finished, the embedded statement @code{stmt} can be
2590 parsed. Note that the mid-rule action is component number 5, so the
2591 @samp{stmt} is component number 6.
2593 After the embedded statement is parsed, its semantic value becomes the
2594 value of the entire @code{let}-statement. Then the semantic value from the
2595 earlier action is used to restore the prior list of variables. This
2596 removes the temporary @code{let}-variable from the list so that it won't
2597 appear to exist while the rest of the program is parsed.
2599 Taking action before a rule is completely recognized often leads to
2600 conflicts since the parser must commit to a parse in order to execute the
2601 action. For example, the following two rules, without mid-rule actions,
2602 can coexist in a working parser because the parser can shift the open-brace
2603 token and look at what follows before deciding whether there is a
2608 compound: '@{' declarations statements '@}'
2609 | '@{' statements '@}'
2615 But when we add a mid-rule action as follows, the rules become nonfunctional:
2619 compound: @{ prepare_for_local_variables (); @}
2620 '@{' declarations statements '@}'
2623 | '@{' statements '@}'
2629 Now the parser is forced to decide whether to run the mid-rule action
2630 when it has read no farther than the open-brace. In other words, it
2631 must commit to using one rule or the other, without sufficient
2632 information to do it correctly. (The open-brace token is what is called
2633 the @dfn{look-ahead} token at this time, since the parser is still
2634 deciding what to do about it. @xref{Look-Ahead, ,Look-Ahead Tokens}.)
2636 You might think that you could correct the problem by putting identical
2637 actions into the two rules, like this:
2641 compound: @{ prepare_for_local_variables (); @}
2642 '@{' declarations statements '@}'
2643 | @{ prepare_for_local_variables (); @}
2644 '@{' statements '@}'
2650 But this does not help, because Bison does not realize that the two actions
2651 are identical. (Bison never tries to understand the C code in an action.)
2653 If the grammar is such that a declaration can be distinguished from a
2654 statement by the first token (which is true in C), then one solution which
2655 does work is to put the action after the open-brace, like this:
2659 compound: '@{' @{ prepare_for_local_variables (); @}
2660 declarations statements '@}'
2661 | '@{' statements '@}'
2667 Now the first token of the following declaration or statement,
2668 which would in any case tell Bison which rule to use, can still do so.
2670 Another solution is to bury the action inside a nonterminal symbol which
2671 serves as a subroutine:
2675 subroutine: /* empty */
2676 @{ prepare_for_local_variables (); @}
2682 compound: subroutine
2683 '@{' declarations statements '@}'
2685 '@{' statements '@}'
2691 Now Bison can execute the action in the rule for @code{subroutine} without
2692 deciding which rule for @code{compound} it will eventually use. Note that
2693 the action is now at the end of its rule. Any mid-rule action can be
2694 converted to an end-of-rule action in this way, and this is what Bison
2695 actually does to implement mid-rule actions.
2698 @section Tracking Locations
2700 @cindex textual position
2701 @cindex position, textual
2703 Though grammar rules and semantic actions are enough to write a fully
2704 functional parser, it can be useful to process some additionnal informations,
2705 especially symbol locations.
2707 @c (terminal or not) ?
2709 The way locations are handled is defined by providing a data type, and actions
2710 to take when rules are matched.
2713 * Location Type:: Specifying a data type for locations.
2714 * Actions and Locations:: Using locations in actions.
2715 * Location Default Action:: Defining a general way to compute locations.
2719 @subsection Data Type of Locations
2720 @cindex data type of locations
2721 @cindex default location type
2723 Defining a data type for locations is much simpler than for semantic values,
2724 since all tokens and groupings always use the same type.
2726 The type of locations is specified by defining a macro called @code{YYLTYPE}.
2727 When @code{YYLTYPE} is not defined, Bison uses a default structure type with
2740 @node Actions and Locations
2741 @subsection Actions and Locations
2742 @cindex location actions
2743 @cindex actions, location
2747 Actions are not only useful for defining language semantics, but also for
2748 describing the behavior of the output parser with locations.
2750 The most obvious way for building locations of syntactic groupings is very
2751 similar to the way semantic values are computed. In a given rule, several
2752 constructs can be used to access the locations of the elements being matched.
2753 The location of the @var{n}th component of the right hand side is
2754 @code{@@@var{n}}, while the location of the left hand side grouping is
2757 Here is a basic example using the default data type for locations:
2764 @@$.first_column = @@1.first_column;
2765 @@$.first_line = @@1.first_line;
2766 @@$.last_column = @@3.last_column;
2767 @@$.last_line = @@3.last_line;
2773 printf("Division by zero, l%d,c%d-l%d,c%d",
2774 @@3.first_line, @@3.first_column,
2775 @@3.last_line, @@3.last_column);
2781 As for semantic values, there is a default action for locations that is
2782 run each time a rule is matched. It sets the beginning of @code{@@$} to the
2783 beginning of the first symbol, and the end of @code{@@$} to the end of the
2786 With this default action, the location tracking can be fully automatic. The
2787 example above simply rewrites this way:
2799 printf("Division by zero, l%d,c%d-l%d,c%d",
2800 @@3.first_line, @@3.first_column,
2801 @@3.last_line, @@3.last_column);
2807 @node Location Default Action
2808 @subsection Default Action for Locations
2809 @vindex YYLLOC_DEFAULT
2811 Actually, actions are not the best place to compute locations. Since locations
2812 are much more general than semantic values, there is room in the output parser
2813 to redefine the default action to take for each rule. The
2814 @code{YYLLOC_DEFAULT} macro is called each time a rule is matched, before the
2815 associated action is run.
2817 Most of the time, this macro is general enough to suppress location
2818 dedicated code from semantic actions.
2820 The @code{YYLLOC_DEFAULT} macro takes three parameters. The first one is
2821 the location of the grouping (the result of the computation). The second one
2822 is an array holding locations of all right hand side elements of the rule
2823 being matched. The last one is the size of the right hand side rule.
2825 By default, it is defined this way:
2829 #define YYLLOC_DEFAULT(Current, Rhs, N) \
2830 Current.last_line = Rhs[N].last_line; \
2831 Current.last_column = Rhs[N].last_column;
2835 When defining @code{YYLLOC_DEFAULT}, you should consider that:
2839 All arguments are free of side-effects. However, only the first one (the
2840 result) should be modified by @code{YYLLOC_DEFAULT}.
2843 Before @code{YYLLOC_DEFAULT} is executed, the output parser sets @code{@@$}
2847 For consistency with semantic actions, valid indexes for the location array
2848 range from 1 to @var{n}.
2852 @section Bison Declarations
2853 @cindex declarations, Bison
2854 @cindex Bison declarations
2856 The @dfn{Bison declarations} section of a Bison grammar defines the symbols
2857 used in formulating the grammar and the data types of semantic values.
2860 All token type names (but not single-character literal tokens such as
2861 @code{'+'} and @code{'*'}) must be declared. Nonterminal symbols must be
2862 declared if you need to specify which data type to use for the semantic
2863 value (@pxref{Multiple Types, ,More Than One Value Type}).
2865 The first rule in the file also specifies the start symbol, by default.
2866 If you want some other symbol to be the start symbol, you must declare
2867 it explicitly (@pxref{Language and Grammar, ,Languages and Context-Free Grammars}).
2870 * Token Decl:: Declaring terminal symbols.
2871 * Precedence Decl:: Declaring terminals with precedence and associativity.
2872 * Union Decl:: Declaring the set of all semantic value types.
2873 * Type Decl:: Declaring the choice of type for a nonterminal symbol.
2874 * Expect Decl:: Suppressing warnings about shift/reduce conflicts.
2875 * Start Decl:: Specifying the start symbol.
2876 * Pure Decl:: Requesting a reentrant parser.
2877 * Decl Summary:: Table of all Bison declarations.
2881 @subsection Token Type Names
2882 @cindex declaring token type names
2883 @cindex token type names, declaring
2884 @cindex declaring literal string tokens
2887 The basic way to declare a token type name (terminal symbol) is as follows:
2893 Bison will convert this into a @code{#define} directive in
2894 the parser, so that the function @code{yylex} (if it is in this file)
2895 can use the name @var{name} to stand for this token type's code.
2897 Alternatively, you can use @code{%left}, @code{%right}, or
2898 @code{%nonassoc} instead of @code{%token}, if you wish to specify
2899 associativity and precedence. @xref{Precedence Decl, ,Operator
2902 You can explicitly specify the numeric code for a token type by appending
2903 an integer value in the field immediately following the token name:
2910 It is generally best, however, to let Bison choose the numeric codes for
2911 all token types. Bison will automatically select codes that don't conflict
2912 with each other or with ASCII characters.
2914 In the event that the stack type is a union, you must augment the
2915 @code{%token} or other token declaration to include the data type
2916 alternative delimited by angle-brackets (@pxref{Multiple Types, ,More Than One Value Type}).
2922 %union @{ /* define stack type */
2926 %token <val> NUM /* define token NUM and its type */
2930 You can associate a literal string token with a token type name by
2931 writing the literal string at the end of a @code{%token}
2932 declaration which declares the name. For example:
2939 For example, a grammar for the C language might specify these names with
2940 equivalent literal string tokens:
2943 %token <operator> OR "||"
2944 %token <operator> LE 134 "<="
2949 Once you equate the literal string and the token name, you can use them
2950 interchangeably in further declarations or the grammar rules. The
2951 @code{yylex} function can use the token name or the literal string to
2952 obtain the token type code number (@pxref{Calling Convention}).
2954 @node Precedence Decl
2955 @subsection Operator Precedence
2956 @cindex precedence declarations
2957 @cindex declaring operator precedence
2958 @cindex operator precedence, declaring
2960 Use the @code{%left}, @code{%right} or @code{%nonassoc} declaration to
2961 declare a token and specify its precedence and associativity, all at
2962 once. These are called @dfn{precedence declarations}.
2963 @xref{Precedence, ,Operator Precedence}, for general information on operator precedence.
2965 The syntax of a precedence declaration is the same as that of
2966 @code{%token}: either
2969 %left @var{symbols}@dots{}
2976 %left <@var{type}> @var{symbols}@dots{}
2979 And indeed any of these declarations serves the purposes of @code{%token}.
2980 But in addition, they specify the associativity and relative precedence for
2981 all the @var{symbols}:
2985 The associativity of an operator @var{op} determines how repeated uses
2986 of the operator nest: whether @samp{@var{x} @var{op} @var{y} @var{op}
2987 @var{z}} is parsed by grouping @var{x} with @var{y} first or by
2988 grouping @var{y} with @var{z} first. @code{%left} specifies
2989 left-associativity (grouping @var{x} with @var{y} first) and
2990 @code{%right} specifies right-associativity (grouping @var{y} with
2991 @var{z} first). @code{%nonassoc} specifies no associativity, which
2992 means that @samp{@var{x} @var{op} @var{y} @var{op} @var{z}} is
2993 considered a syntax error.
2996 The precedence of an operator determines how it nests with other operators.
2997 All the tokens declared in a single precedence declaration have equal
2998 precedence and nest together according to their associativity.
2999 When two tokens declared in different precedence declarations associate,
3000 the one declared later has the higher precedence and is grouped first.
3004 @subsection The Collection of Value Types
3005 @cindex declaring value types
3006 @cindex value types, declaring
3009 The @code{%union} declaration specifies the entire collection of possible
3010 data types for semantic values. The keyword @code{%union} is followed by a
3011 pair of braces containing the same thing that goes inside a @code{union} in
3026 This says that the two alternative types are @code{double} and @code{symrec
3027 *}. They are given names @code{val} and @code{tptr}; these names are used
3028 in the @code{%token} and @code{%type} declarations to pick one of the types
3029 for a terminal or nonterminal symbol (@pxref{Type Decl, ,Nonterminal Symbols}).
3031 Note that, unlike making a @code{union} declaration in C, you do not write
3032 a semicolon after the closing brace.
3035 @subsection Nonterminal Symbols
3036 @cindex declaring value types, nonterminals
3037 @cindex value types, nonterminals, declaring
3041 When you use @code{%union} to specify multiple value types, you must
3042 declare the value type of each nonterminal symbol for which values are
3043 used. This is done with a @code{%type} declaration, like this:
3046 %type <@var{type}> @var{nonterminal}@dots{}
3050 Here @var{nonterminal} is the name of a nonterminal symbol, and @var{type}
3051 is the name given in the @code{%union} to the alternative that you want
3052 (@pxref{Union Decl, ,The Collection of Value Types}). You can give any number of nonterminal symbols in
3053 the same @code{%type} declaration, if they have the same value type. Use
3054 spaces to separate the symbol names.
3056 You can also declare the value type of a terminal symbol. To do this,
3057 use the same @code{<@var{type}>} construction in a declaration for the
3058 terminal symbol. All kinds of token declarations allow
3059 @code{<@var{type}>}.
3062 @subsection Suppressing Conflict Warnings
3063 @cindex suppressing conflict warnings
3064 @cindex preventing warnings about conflicts
3065 @cindex warnings, preventing
3066 @cindex conflicts, suppressing warnings of
3069 Bison normally warns if there are any conflicts in the grammar
3070 (@pxref{Shift/Reduce, ,Shift/Reduce Conflicts}), but most real grammars have harmless shift/reduce
3071 conflicts which are resolved in a predictable way and would be difficult to
3072 eliminate. It is desirable to suppress the warning about these conflicts
3073 unless the number of conflicts changes. You can do this with the
3074 @code{%expect} declaration.
3076 The declaration looks like this:
3082 Here @var{n} is a decimal integer. The declaration says there should be no
3083 warning if there are @var{n} shift/reduce conflicts and no reduce/reduce
3084 conflicts. The usual warning is given if there are either more or fewer
3085 conflicts, or if there are any reduce/reduce conflicts.
3087 In general, using @code{%expect} involves these steps:
3091 Compile your grammar without @code{%expect}. Use the @samp{-v} option
3092 to get a verbose list of where the conflicts occur. Bison will also
3093 print the number of conflicts.
3096 Check each of the conflicts to make sure that Bison's default
3097 resolution is what you really want. If not, rewrite the grammar and
3098 go back to the beginning.
3101 Add an @code{%expect} declaration, copying the number @var{n} from the
3102 number which Bison printed.
3105 Now Bison will stop annoying you about the conflicts you have checked, but
3106 it will warn you again if changes in the grammar result in additional
3110 @subsection The Start-Symbol
3111 @cindex declaring the start symbol
3112 @cindex start symbol, declaring
3113 @cindex default start symbol
3116 Bison assumes by default that the start symbol for the grammar is the first
3117 nonterminal specified in the grammar specification section. The programmer
3118 may override this restriction with the @code{%start} declaration as follows:
3125 @subsection A Pure (Reentrant) Parser
3126 @cindex reentrant parser
3128 @findex %pure_parser
3130 A @dfn{reentrant} program is one which does not alter in the course of
3131 execution; in other words, it consists entirely of @dfn{pure} (read-only)
3132 code. Reentrancy is important whenever asynchronous execution is possible;
3133 for example, a non-reentrant program may not be safe to call from a signal
3134 handler. In systems with multiple threads of control, a non-reentrant
3135 program must be called only within interlocks.
3137 Normally, Bison generates a parser which is not reentrant. This is
3138 suitable for most uses, and it permits compatibility with YACC. (The
3139 standard YACC interfaces are inherently nonreentrant, because they use
3140 statically allocated variables for communication with @code{yylex},
3141 including @code{yylval} and @code{yylloc}.)
3143 Alternatively, you can generate a pure, reentrant parser. The Bison
3144 declaration @code{%pure_parser} says that you want the parser to be
3145 reentrant. It looks like this:
3151 The result is that the communication variables @code{yylval} and
3152 @code{yylloc} become local variables in @code{yyparse}, and a different
3153 calling convention is used for the lexical analyzer function
3154 @code{yylex}. @xref{Pure Calling, ,Calling Conventions for Pure
3155 Parsers}, for the details of this. The variable @code{yynerrs} also
3156 becomes local in @code{yyparse} (@pxref{Error Reporting, ,The Error
3157 Reporting Function @code{yyerror}}). The convention for calling
3158 @code{yyparse} itself is unchanged.
3160 Whether the parser is pure has nothing to do with the grammar rules.
3161 You can generate either a pure parser or a nonreentrant parser from any
3165 @subsection Bison Declaration Summary
3166 @cindex Bison declaration summary
3167 @cindex declaration summary
3168 @cindex summary, Bison declaration
3170 Here is a summary of all Bison declarations:
3174 Declare the collection of data types that semantic values may have
3175 (@pxref{Union Decl, ,The Collection of Value Types}).
3178 Declare a terminal symbol (token type name) with no precedence
3179 or associativity specified (@pxref{Token Decl, ,Token Type Names}).
3182 Declare a terminal symbol (token type name) that is right-associative
3183 (@pxref{Precedence Decl, ,Operator Precedence}).
3186 Declare a terminal symbol (token type name) that is left-associative
3187 (@pxref{Precedence Decl, ,Operator Precedence}).
3190 Declare a terminal symbol (token type name) that is nonassociative
3191 (using it in a way that would be associative is a syntax error)
3192 (@pxref{Precedence Decl, ,Operator Precedence}).
3195 Declare the type of semantic values for a nonterminal symbol
3196 (@pxref{Type Decl, ,Nonterminal Symbols}).
3199 Specify the grammar's start symbol (@pxref{Start Decl, ,The
3203 Declare the expected number of shift-reduce conflicts
3204 (@pxref{Expect Decl, ,Suppressing Conflict Warnings}).
3207 @itemx %fixed_output_files
3208 Pretend the option @option{--yacc} was given, i.e., imitate Yacc,
3209 including its naming conventions. @xref{Bison Options}, for more.
3212 Generate the code processing the locations (@pxref{Action Features,
3213 ,Special Features for Use in Actions}). This mode is enabled as soon as
3214 the grammar uses the special @samp{@@@var{n}} tokens, but if your
3215 grammar does not use it, using @samp{%locations} allows for more
3216 accurate parse error messages.
3219 Request a pure (reentrant) parser program (@pxref{Pure Decl, ,A Pure
3220 (Reentrant) Parser}).
3223 Do not include any C code in the parser file; generate tables only. The
3224 parser file contains just @code{#define} directives and static variable
3227 This option also tells Bison to write the C code for the grammar actions
3228 into a file named @file{@var{filename}.act}, in the form of a
3229 brace-surrounded body fit for a @code{switch} statement.
3232 Don't generate any @code{#line} preprocessor commands in the parser
3233 file. Ordinarily Bison writes these commands in the parser file so that
3234 the C compiler and debuggers will associate errors and object code with
3235 your source file (the grammar file). This directive causes them to
3236 associate errors with the parser file, treating it an independent source
3237 file in its own right.
3240 Output a definition of the macro @code{YYDEBUG} into the parser file, so
3241 that the debugging facilities are compiled. @xref{Debugging, ,Debugging
3245 Write an extra output file containing macro definitions for the token
3246 type names defined in the grammar and the semantic value type
3247 @code{YYSTYPE}, as well as a few @code{extern} variable declarations.
3249 If the parser output file is named @file{@var{name}.c} then this file
3250 is named @file{@var{name}.h}.@refill
3252 This output file is essential if you wish to put the definition of
3253 @code{yylex} in a separate source file, because @code{yylex} needs to
3254 be able to refer to token type codes and the variable
3255 @code{yylval}. @xref{Token Values, ,Semantic Values of Tokens}.@refill
3257 @c @item %source_extension
3258 @c Specify the extension of the parser output file.
3260 @c For example, a grammar file named @file{foo.yy} and containing a
3261 @c @code{%source_extension .cpp} directive will produce a parser file
3262 @c named @file{foo.tab.cpp}
3264 @c @item %header_extension
3265 @c Specify the extension of the parser header file generated when
3266 @c @code{%define} or @samp{-d} are used.
3268 @c For example, a garmmar file named @file{foo.ypp} and containing a
3269 @c @code{%header_extension .hh} directive will produce a header file
3270 @c named @file{foo.tab.hh}
3273 Write an extra output file containing verbose descriptions of the
3274 parser states and what is done for each type of look-ahead token in
3277 This file also describes all the conflicts, both those resolved by
3278 operator precedence and the unresolved ones.
3280 The file's name is made by removing @samp{.tab.c} or @samp{.c} from
3281 the parser output file name, and adding @samp{.output} instead.@refill
3283 Therefore, if the input file is @file{foo.y}, then the parser file is
3284 called @file{foo.tab.c} by default. As a consequence, the verbose
3285 output file is called @file{foo.output}.@refill
3288 Generate an array of token names in the parser file. The name of the
3289 array is @code{yytname}; @code{yytname[@var{i}]} is the name of the
3290 token whose internal Bison token code number is @var{i}. The first three
3291 elements of @code{yytname} are always @code{"$"}, @code{"error"}, and
3292 @code{"$illegal"}; after these come the symbols defined in the grammar
3295 For single-character literal tokens and literal string tokens, the name
3296 in the table includes the single-quote or double-quote characters: for
3297 example, @code{"'+'"} is a single-character literal and @code{"\"<=\""}
3298 is a literal string token. All the characters of the literal string
3299 token appear verbatim in the string found in the table; even
3300 double-quote characters are not escaped. For example, if the token
3301 consists of three characters @samp{*"*}, its string in @code{yytname}
3302 contains @samp{"*"*"}. (In C, that would be written as
3305 When you specify @code{%token_table}, Bison also generates macro
3306 definitions for macros @code{YYNTOKENS}, @code{YYNNTS}, and
3307 @code{YYNRULES}, and @code{YYNSTATES}:
3311 The highest token number, plus one.
3313 The number of nonterminal symbols.
3315 The number of grammar rules,
3317 The number of parser states (@pxref{Parser States}).
3321 @node Multiple Parsers
3322 @section Multiple Parsers in the Same Program
3324 Most programs that use Bison parse only one language and therefore contain
3325 only one Bison parser. But what if you want to parse more than one
3326 language with the same program? Then you need to avoid a name conflict
3327 between different definitions of @code{yyparse}, @code{yylval}, and so on.
3329 The easy way to do this is to use the option @samp{-p @var{prefix}}
3330 (@pxref{Invocation, ,Invoking Bison}). This renames the interface functions and
3331 variables of the Bison parser to start with @var{prefix} instead of
3332 @samp{yy}. You can use this to give each parser distinct names that do
3335 The precise list of symbols renamed is @code{yyparse}, @code{yylex},
3336 @code{yyerror}, @code{yynerrs}, @code{yylval}, @code{yychar} and
3337 @code{yydebug}. For example, if you use @samp{-p c}, the names become
3338 @code{cparse}, @code{clex}, and so on.
3340 @strong{All the other variables and macros associated with Bison are not
3341 renamed.} These others are not global; there is no conflict if the same
3342 name is used in different parsers. For example, @code{YYSTYPE} is not
3343 renamed, but defining this in different ways in different parsers causes
3344 no trouble (@pxref{Value Type, ,Data Types of Semantic Values}).
3346 The @samp{-p} option works by adding macro definitions to the beginning
3347 of the parser source file, defining @code{yyparse} as
3348 @code{@var{prefix}parse}, and so on. This effectively substitutes one
3349 name for the other in the entire parser file.
3352 @chapter Parser C-Language Interface
3353 @cindex C-language interface
3356 The Bison parser is actually a C function named @code{yyparse}. Here we
3357 describe the interface conventions of @code{yyparse} and the other
3358 functions that it needs to use.
3360 Keep in mind that the parser uses many C identifiers starting with
3361 @samp{yy} and @samp{YY} for internal purposes. If you use such an
3362 identifier (aside from those in this manual) in an action or in additional
3363 C code in the grammar file, you are likely to run into trouble.
3366 * Parser Function:: How to call @code{yyparse} and what it returns.
3367 * Lexical:: You must supply a function @code{yylex}
3369 * Error Reporting:: You must supply a function @code{yyerror}.
3370 * Action Features:: Special features for use in actions.
3373 @node Parser Function
3374 @section The Parser Function @code{yyparse}
3377 You call the function @code{yyparse} to cause parsing to occur. This
3378 function reads tokens, executes actions, and ultimately returns when it
3379 encounters end-of-input or an unrecoverable syntax error. You can also
3380 write an action which directs @code{yyparse} to return immediately
3381 without reading further.
3383 The value returned by @code{yyparse} is 0 if parsing was successful (return
3384 is due to end-of-input).
3386 The value is 1 if parsing failed (return is due to a syntax error).
3388 In an action, you can cause immediate return from @code{yyparse} by using
3394 Return immediately with value 0 (to report success).
3398 Return immediately with value 1 (to report failure).
3402 @section The Lexical Analyzer Function @code{yylex}
3404 @cindex lexical analyzer
3406 The @dfn{lexical analyzer} function, @code{yylex}, recognizes tokens from
3407 the input stream and returns them to the parser. Bison does not create
3408 this function automatically; you must write it so that @code{yyparse} can
3409 call it. The function is sometimes referred to as a lexical scanner.
3411 In simple programs, @code{yylex} is often defined at the end of the Bison
3412 grammar file. If @code{yylex} is defined in a separate source file, you
3413 need to arrange for the token-type macro definitions to be available there.
3414 To do this, use the @samp{-d} option when you run Bison, so that it will
3415 write these macro definitions into a separate header file
3416 @file{@var{name}.tab.h} which you can include in the other source files
3417 that need it. @xref{Invocation, ,Invoking Bison}.@refill
3420 * Calling Convention:: How @code{yyparse} calls @code{yylex}.
3421 * Token Values:: How @code{yylex} must return the semantic value
3422 of the token it has read.
3423 * Token Positions:: How @code{yylex} must return the text position
3424 (line number, etc.) of the token, if the
3426 * Pure Calling:: How the calling convention differs
3427 in a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}).
3430 @node Calling Convention
3431 @subsection Calling Convention for @code{yylex}
3433 The value that @code{yylex} returns must be the numeric code for the type
3434 of token it has just found, or 0 for end-of-input.
3436 When a token is referred to in the grammar rules by a name, that name
3437 in the parser file becomes a C macro whose definition is the proper
3438 numeric code for that token type. So @code{yylex} can use the name
3439 to indicate that type. @xref{Symbols}.
3441 When a token is referred to in the grammar rules by a character literal,
3442 the numeric code for that character is also the code for the token type.
3443 So @code{yylex} can simply return that character code. The null character
3444 must not be used this way, because its code is zero and that is what
3445 signifies end-of-input.
3447 Here is an example showing these things:
3454 if (c == EOF) /* Detect end of file. */
3457 if (c == '+' || c == '-')
3458 return c; /* Assume token type for `+' is '+'. */
3460 return INT; /* Return the type of the token. */
3466 This interface has been designed so that the output from the @code{lex}
3467 utility can be used without change as the definition of @code{yylex}.
3469 If the grammar uses literal string tokens, there are two ways that
3470 @code{yylex} can determine the token type codes for them:
3474 If the grammar defines symbolic token names as aliases for the
3475 literal string tokens, @code{yylex} can use these symbolic names like
3476 all others. In this case, the use of the literal string tokens in
3477 the grammar file has no effect on @code{yylex}.
3480 @code{yylex} can find the multicharacter token in the @code{yytname}
3481 table. The index of the token in the table is the token type's code.
3482 The name of a multicharacter token is recorded in @code{yytname} with a
3483 double-quote, the token's characters, and another double-quote. The
3484 token's characters are not escaped in any way; they appear verbatim in
3485 the contents of the string in the table.
3487 Here's code for looking up a token in @code{yytname}, assuming that the
3488 characters of the token are stored in @code{token_buffer}.
3491 for (i = 0; i < YYNTOKENS; i++)
3494 && yytname[i][0] == '"'
3495 && strncmp (yytname[i] + 1, token_buffer,
3496 strlen (token_buffer))
3497 && yytname[i][strlen (token_buffer) + 1] == '"'
3498 && yytname[i][strlen (token_buffer) + 2] == 0)
3503 The @code{yytname} table is generated only if you use the
3504 @code{%token_table} declaration. @xref{Decl Summary}.
3508 @subsection Semantic Values of Tokens
3511 In an ordinary (non-reentrant) parser, the semantic value of the token must
3512 be stored into the global variable @code{yylval}. When you are using
3513 just one data type for semantic values, @code{yylval} has that type.
3514 Thus, if the type is @code{int} (the default), you might write this in
3520 yylval = value; /* Put value onto Bison stack. */
3521 return INT; /* Return the type of the token. */
3526 When you are using multiple data types, @code{yylval}'s type is a union
3527 made from the @code{%union} declaration (@pxref{Union Decl, ,The Collection of Value Types}). So when
3528 you store a token's value, you must use the proper member of the union.
3529 If the @code{%union} declaration looks like this:
3542 then the code in @code{yylex} might look like this:
3547 yylval.intval = value; /* Put value onto Bison stack. */
3548 return INT; /* Return the type of the token. */
3553 @node Token Positions
3554 @subsection Textual Positions of Tokens
3557 If you are using the @samp{@@@var{n}}-feature (@pxref{Locations, ,
3558 Tracking Locations}) in actions to keep track of the
3559 textual locations of tokens and groupings, then you must provide this
3560 information in @code{yylex}. The function @code{yyparse} expects to
3561 find the textual location of a token just parsed in the global variable
3562 @code{yylloc}. So @code{yylex} must store the proper data in that
3565 By default, the value of @code{yylloc} is a structure and you need only
3566 initialize the members that are going to be used by the actions. The
3567 four members are called @code{first_line}, @code{first_column},
3568 @code{last_line} and @code{last_column}. Note that the use of this
3569 feature makes the parser noticeably slower.
3572 The data type of @code{yylloc} has the name @code{YYLTYPE}.
3575 @subsection Calling Conventions for Pure Parsers
3577 When you use the Bison declaration @code{%pure_parser} to request a
3578 pure, reentrant parser, the global communication variables @code{yylval}
3579 and @code{yylloc} cannot be used. (@xref{Pure Decl, ,A Pure (Reentrant)
3580 Parser}.) In such parsers the two global variables are replaced by
3581 pointers passed as arguments to @code{yylex}. You must declare them as
3582 shown here, and pass the information back by storing it through those
3587 yylex (YYSTYPE *lvalp, YYLTYPE *llocp)
3590 *lvalp = value; /* Put value onto Bison stack. */
3591 return INT; /* Return the type of the token. */
3596 If the grammar file does not use the @samp{@@} constructs to refer to
3597 textual positions, then the type @code{YYLTYPE} will not be defined. In
3598 this case, omit the second argument; @code{yylex} will be called with
3601 @vindex YYPARSE_PARAM
3602 If you use a reentrant parser, you can optionally pass additional
3603 parameter information to it in a reentrant way. To do so, define the
3604 macro @code{YYPARSE_PARAM} as a variable name. This modifies the
3605 @code{yyparse} function to accept one argument, of type @code{void *},
3608 When you call @code{yyparse}, pass the address of an object, casting the
3609 address to @code{void *}. The grammar actions can refer to the contents
3610 of the object by casting the pointer value back to its proper type and
3611 then dereferencing it. Here's an example. Write this in the parser:
3615 struct parser_control
3621 #define YYPARSE_PARAM parm
3626 Then call the parser like this:
3629 struct parser_control
3638 struct parser_control foo;
3639 @dots{} /* @r{Store proper data in @code{foo}.} */
3640 value = yyparse ((void *) &foo);
3646 In the grammar actions, use expressions like this to refer to the data:
3649 ((struct parser_control *) parm)->randomness
3653 If you wish to pass the additional parameter data to @code{yylex},
3654 define the macro @code{YYLEX_PARAM} just like @code{YYPARSE_PARAM}, as
3659 struct parser_control
3665 #define YYPARSE_PARAM parm
3666 #define YYLEX_PARAM parm
3670 You should then define @code{yylex} to accept one additional
3671 argument---the value of @code{parm}. (This makes either two or three
3672 arguments in total, depending on whether an argument of type
3673 @code{YYLTYPE} is passed.) You can declare the argument as a pointer to
3674 the proper object type, or you can declare it as @code{void *} and
3675 access the contents as shown above.
3677 You can use @samp{%pure_parser} to request a reentrant parser without
3678 also using @code{YYPARSE_PARAM}. Then you should call @code{yyparse}
3679 with no arguments, as usual.
3681 @node Error Reporting
3682 @section The Error Reporting Function @code{yyerror}
3683 @cindex error reporting function
3686 @cindex syntax error
3688 The Bison parser detects a @dfn{parse error} or @dfn{syntax error}
3689 whenever it reads a token which cannot satisfy any syntax rule. An
3690 action in the grammar can also explicitly proclaim an error, using the
3691 macro @code{YYERROR} (@pxref{Action Features, ,Special Features for Use
3694 The Bison parser expects to report the error by calling an error
3695 reporting function named @code{yyerror}, which you must supply. It is
3696 called by @code{yyparse} whenever a syntax error is found, and it
3697 receives one argument. For a parse error, the string is normally
3698 @w{@code{"parse error"}}.
3700 @findex YYERROR_VERBOSE
3701 If you define the macro @code{YYERROR_VERBOSE} in the Bison declarations
3702 section (@pxref{Bison Declarations, ,The Bison Declarations Section}),
3703 then Bison provides a more verbose and specific error message string
3704 instead of just plain @w{@code{"parse error"}}. It doesn't matter what
3705 definition you use for @code{YYERROR_VERBOSE}, just whether you define
3708 The parser can detect one other kind of error: stack overflow. This
3709 happens when the input contains constructions that are very deeply
3710 nested. It isn't likely you will encounter this, since the Bison
3711 parser extends its stack automatically up to a very large limit. But
3712 if overflow happens, @code{yyparse} calls @code{yyerror} in the usual
3713 fashion, except that the argument string is @w{@code{"parser stack
3716 The following definition suffices in simple programs:
3725 fprintf (stderr, "%s\n", s);
3730 After @code{yyerror} returns to @code{yyparse}, the latter will attempt
3731 error recovery if you have written suitable error recovery grammar rules
3732 (@pxref{Error Recovery}). If recovery is impossible, @code{yyparse} will
3733 immediately return 1.
3736 The variable @code{yynerrs} contains the number of syntax errors
3737 encountered so far. Normally this variable is global; but if you
3738 request a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}) then it is a local variable
3739 which only the actions can access.
3741 @node Action Features
3742 @section Special Features for Use in Actions
3743 @cindex summary, action features
3744 @cindex action features summary
3746 Here is a table of Bison constructs, variables and macros that
3747 are useful in actions.
3751 Acts like a variable that contains the semantic value for the
3752 grouping made by the current rule. @xref{Actions}.
3755 Acts like a variable that contains the semantic value for the
3756 @var{n}th component of the current rule. @xref{Actions}.
3758 @item $<@var{typealt}>$
3759 Like @code{$$} but specifies alternative @var{typealt} in the union
3760 specified by the @code{%union} declaration. @xref{Action Types, ,Data Types of Values in Actions}.
3762 @item $<@var{typealt}>@var{n}
3763 Like @code{$@var{n}} but specifies alternative @var{typealt} in the
3764 union specified by the @code{%union} declaration.
3765 @xref{Action Types, ,Data Types of Values in Actions}.@refill
3768 Return immediately from @code{yyparse}, indicating failure.
3769 @xref{Parser Function, ,The Parser Function @code{yyparse}}.
3772 Return immediately from @code{yyparse}, indicating success.
3773 @xref{Parser Function, ,The Parser Function @code{yyparse}}.
3775 @item YYBACKUP (@var{token}, @var{value});
3777 Unshift a token. This macro is allowed only for rules that reduce
3778 a single value, and only when there is no look-ahead token.
3779 It installs a look-ahead token with token type @var{token} and
3780 semantic value @var{value}; then it discards the value that was
3781 going to be reduced by this rule.
3783 If the macro is used when it is not valid, such as when there is
3784 a look-ahead token already, then it reports a syntax error with
3785 a message @samp{cannot back up} and performs ordinary error
3788 In either case, the rest of the action is not executed.
3792 Value stored in @code{yychar} when there is no look-ahead token.
3796 Cause an immediate syntax error. This statement initiates error
3797 recovery just as if the parser itself had detected an error; however, it
3798 does not call @code{yyerror}, and does not print any message. If you
3799 want to print an error message, call @code{yyerror} explicitly before
3800 the @samp{YYERROR;} statement. @xref{Error Recovery}.
3803 This macro stands for an expression that has the value 1 when the parser
3804 is recovering from a syntax error, and 0 the rest of the time.
3805 @xref{Error Recovery}.
3808 Variable containing the current look-ahead token. (In a pure parser,
3809 this is actually a local variable within @code{yyparse}.) When there is
3810 no look-ahead token, the value @code{YYEMPTY} is stored in the variable.
3811 @xref{Look-Ahead, ,Look-Ahead Tokens}.
3814 Discard the current look-ahead token. This is useful primarily in
3815 error rules. @xref{Error Recovery}.
3818 Resume generating error messages immediately for subsequent syntax
3819 errors. This is useful primarily in error rules.
3820 @xref{Error Recovery}.
3824 Acts like a structure variable containing information on the textual position
3825 of the grouping made by the current rule. @xref{Locations, ,
3826 Tracking Locations}.
3828 @c Check if those paragraphs are still useful or not.
3832 @c int first_line, last_line;
3833 @c int first_column, last_column;
3837 @c Thus, to get the starting line number of the third component, you would
3838 @c use @samp{@@3.first_line}.
3840 @c In order for the members of this structure to contain valid information,
3841 @c you must make @code{yylex} supply this information about each token.
3842 @c If you need only certain members, then @code{yylex} need only fill in
3845 @c The use of this feature makes the parser noticeably slower.
3849 Acts like a structure variable containing information on the textual position
3850 of the @var{n}th component of the current rule. @xref{Locations, ,
3851 Tracking Locations}.
3856 @chapter The Bison Parser Algorithm
3857 @cindex Bison parser algorithm
3858 @cindex algorithm of parser
3861 @cindex parser stack
3862 @cindex stack, parser
3864 As Bison reads tokens, it pushes them onto a stack along with their
3865 semantic values. The stack is called the @dfn{parser stack}. Pushing a
3866 token is traditionally called @dfn{shifting}.
3868 For example, suppose the infix calculator has read @samp{1 + 5 *}, with a
3869 @samp{3} to come. The stack will have four elements, one for each token
3872 But the stack does not always have an element for each token read. When
3873 the last @var{n} tokens and groupings shifted match the components of a
3874 grammar rule, they can be combined according to that rule. This is called
3875 @dfn{reduction}. Those tokens and groupings are replaced on the stack by a
3876 single grouping whose symbol is the result (left hand side) of that rule.
3877 Running the rule's action is part of the process of reduction, because this
3878 is what computes the semantic value of the resulting grouping.
3880 For example, if the infix calculator's parser stack contains this:
3887 and the next input token is a newline character, then the last three
3888 elements can be reduced to 15 via the rule:
3891 expr: expr '*' expr;
3895 Then the stack contains just these three elements:
3902 At this point, another reduction can be made, resulting in the single value
3903 16. Then the newline token can be shifted.
3905 The parser tries, by shifts and reductions, to reduce the entire input down
3906 to a single grouping whose symbol is the grammar's start-symbol
3907 (@pxref{Language and Grammar, ,Languages and Context-Free Grammars}).
3909 This kind of parser is known in the literature as a bottom-up parser.
3912 * Look-Ahead:: Parser looks one token ahead when deciding what to do.
3913 * Shift/Reduce:: Conflicts: when either shifting or reduction is valid.
3914 * Precedence:: Operator precedence works by resolving conflicts.
3915 * Contextual Precedence:: When an operator's precedence depends on context.
3916 * Parser States:: The parser is a finite-state-machine with stack.
3917 * Reduce/Reduce:: When two rules are applicable in the same situation.
3918 * Mystery Conflicts:: Reduce/reduce conflicts that look unjustified.
3919 * Stack Overflow:: What happens when stack gets full. How to avoid it.
3923 @section Look-Ahead Tokens
3924 @cindex look-ahead token
3926 The Bison parser does @emph{not} always reduce immediately as soon as the
3927 last @var{n} tokens and groupings match a rule. This is because such a
3928 simple strategy is inadequate to handle most languages. Instead, when a
3929 reduction is possible, the parser sometimes ``looks ahead'' at the next
3930 token in order to decide what to do.
3932 When a token is read, it is not immediately shifted; first it becomes the
3933 @dfn{look-ahead token}, which is not on the stack. Now the parser can
3934 perform one or more reductions of tokens and groupings on the stack, while
3935 the look-ahead token remains off to the side. When no more reductions
3936 should take place, the look-ahead token is shifted onto the stack. This
3937 does not mean that all possible reductions have been done; depending on the
3938 token type of the look-ahead token, some rules may choose to delay their
3941 Here is a simple case where look-ahead is needed. These three rules define
3942 expressions which contain binary addition operators and postfix unary
3943 factorial operators (@samp{!}), and allow parentheses for grouping.
3960 Suppose that the tokens @w{@samp{1 + 2}} have been read and shifted; what
3961 should be done? If the following token is @samp{)}, then the first three
3962 tokens must be reduced to form an @code{expr}. This is the only valid
3963 course, because shifting the @samp{)} would produce a sequence of symbols
3964 @w{@code{term ')'}}, and no rule allows this.
3966 If the following token is @samp{!}, then it must be shifted immediately so
3967 that @w{@samp{2 !}} can be reduced to make a @code{term}. If instead the
3968 parser were to reduce before shifting, @w{@samp{1 + 2}} would become an
3969 @code{expr}. It would then be impossible to shift the @samp{!} because
3970 doing so would produce on the stack the sequence of symbols @code{expr
3971 '!'}. No rule allows that sequence.
3974 The current look-ahead token is stored in the variable @code{yychar}.
3975 @xref{Action Features, ,Special Features for Use in Actions}.
3978 @section Shift/Reduce Conflicts
3980 @cindex shift/reduce conflicts
3981 @cindex dangling @code{else}
3982 @cindex @code{else}, dangling
3984 Suppose we are parsing a language which has if-then and if-then-else
3985 statements, with a pair of rules like this:
3991 | IF expr THEN stmt ELSE stmt
3997 Here we assume that @code{IF}, @code{THEN} and @code{ELSE} are
3998 terminal symbols for specific keyword tokens.
4000 When the @code{ELSE} token is read and becomes the look-ahead token, the
4001 contents of the stack (assuming the input is valid) are just right for
4002 reduction by the first rule. But it is also legitimate to shift the
4003 @code{ELSE}, because that would lead to eventual reduction by the second
4006 This situation, where either a shift or a reduction would be valid, is
4007 called a @dfn{shift/reduce conflict}. Bison is designed to resolve
4008 these conflicts by choosing to shift, unless otherwise directed by
4009 operator precedence declarations. To see the reason for this, let's
4010 contrast it with the other alternative.
4012 Since the parser prefers to shift the @code{ELSE}, the result is to attach
4013 the else-clause to the innermost if-statement, making these two inputs
4017 if x then if y then win (); else lose;
4019 if x then do; if y then win (); else lose; end;
4022 But if the parser chose to reduce when possible rather than shift, the
4023 result would be to attach the else-clause to the outermost if-statement,
4024 making these two inputs equivalent:
4027 if x then if y then win (); else lose;
4029 if x then do; if y then win (); end; else lose;
4032 The conflict exists because the grammar as written is ambiguous: either
4033 parsing of the simple nested if-statement is legitimate. The established
4034 convention is that these ambiguities are resolved by attaching the
4035 else-clause to the innermost if-statement; this is what Bison accomplishes
4036 by choosing to shift rather than reduce. (It would ideally be cleaner to
4037 write an unambiguous grammar, but that is very hard to do in this case.)
4038 This particular ambiguity was first encountered in the specifications of
4039 Algol 60 and is called the ``dangling @code{else}'' ambiguity.
4041 To avoid warnings from Bison about predictable, legitimate shift/reduce
4042 conflicts, use the @code{%expect @var{n}} declaration. There will be no
4043 warning as long as the number of shift/reduce conflicts is exactly @var{n}.
4044 @xref{Expect Decl, ,Suppressing Conflict Warnings}.
4046 The definition of @code{if_stmt} above is solely to blame for the
4047 conflict, but the conflict does not actually appear without additional
4048 rules. Here is a complete Bison input file that actually manifests the
4053 %token IF THEN ELSE variable
4065 | IF expr THEN stmt ELSE stmt
4074 @section Operator Precedence
4075 @cindex operator precedence
4076 @cindex precedence of operators
4078 Another situation where shift/reduce conflicts appear is in arithmetic
4079 expressions. Here shifting is not always the preferred resolution; the
4080 Bison declarations for operator precedence allow you to specify when to
4081 shift and when to reduce.
4084 * Why Precedence:: An example showing why precedence is needed.
4085 * Using Precedence:: How to specify precedence in Bison grammars.
4086 * Precedence Examples:: How these features are used in the previous example.
4087 * How Precedence:: How they work.
4090 @node Why Precedence
4091 @subsection When Precedence is Needed
4093 Consider the following ambiguous grammar fragment (ambiguous because the
4094 input @w{@samp{1 - 2 * 3}} can be parsed in two different ways):
4108 Suppose the parser has seen the tokens @samp{1}, @samp{-} and @samp{2};
4109 should it reduce them via the rule for the subtraction operator? It
4110 depends on the next token. Of course, if the next token is @samp{)}, we
4111 must reduce; shifting is invalid because no single rule can reduce the
4112 token sequence @w{@samp{- 2 )}} or anything starting with that. But if
4113 the next token is @samp{*} or @samp{<}, we have a choice: either
4114 shifting or reduction would allow the parse to complete, but with
4117 To decide which one Bison should do, we must consider the results. If
4118 the next operator token @var{op} is shifted, then it must be reduced
4119 first in order to permit another opportunity to reduce the difference.
4120 The result is (in effect) @w{@samp{1 - (2 @var{op} 3)}}. On the other
4121 hand, if the subtraction is reduced before shifting @var{op}, the result
4122 is @w{@samp{(1 - 2) @var{op} 3}}. Clearly, then, the choice of shift or
4123 reduce should depend on the relative precedence of the operators
4124 @samp{-} and @var{op}: @samp{*} should be shifted first, but not
4127 @cindex associativity
4128 What about input such as @w{@samp{1 - 2 - 5}}; should this be
4129 @w{@samp{(1 - 2) - 5}} or should it be @w{@samp{1 - (2 - 5)}}? For most
4130 operators we prefer the former, which is called @dfn{left association}.
4131 The latter alternative, @dfn{right association}, is desirable for
4132 assignment operators. The choice of left or right association is a
4133 matter of whether the parser chooses to shift or reduce when the stack
4134 contains @w{@samp{1 - 2}} and the look-ahead token is @samp{-}: shifting
4135 makes right-associativity.
4137 @node Using Precedence
4138 @subsection Specifying Operator Precedence
4143 Bison allows you to specify these choices with the operator precedence
4144 declarations @code{%left} and @code{%right}. Each such declaration
4145 contains a list of tokens, which are operators whose precedence and
4146 associativity is being declared. The @code{%left} declaration makes all
4147 those operators left-associative and the @code{%right} declaration makes
4148 them right-associative. A third alternative is @code{%nonassoc}, which
4149 declares that it is a syntax error to find the same operator twice ``in a
4152 The relative precedence of different operators is controlled by the
4153 order in which they are declared. The first @code{%left} or
4154 @code{%right} declaration in the file declares the operators whose
4155 precedence is lowest, the next such declaration declares the operators
4156 whose precedence is a little higher, and so on.
4158 @node Precedence Examples
4159 @subsection Precedence Examples
4161 In our example, we would want the following declarations:
4169 In a more complete example, which supports other operators as well, we
4170 would declare them in groups of equal precedence. For example, @code{'+'} is
4171 declared with @code{'-'}:
4174 %left '<' '>' '=' NE LE GE
4180 (Here @code{NE} and so on stand for the operators for ``not equal''
4181 and so on. We assume that these tokens are more than one character long
4182 and therefore are represented by names, not character literals.)
4184 @node How Precedence
4185 @subsection How Precedence Works
4187 The first effect of the precedence declarations is to assign precedence
4188 levels to the terminal symbols declared. The second effect is to assign
4189 precedence levels to certain rules: each rule gets its precedence from the
4190 last terminal symbol mentioned in the components. (You can also specify
4191 explicitly the precedence of a rule. @xref{Contextual Precedence, ,Context-Dependent Precedence}.)
4193 Finally, the resolution of conflicts works by comparing the
4194 precedence of the rule being considered with that of the
4195 look-ahead token. If the token's precedence is higher, the
4196 choice is to shift. If the rule's precedence is higher, the
4197 choice is to reduce. If they have equal precedence, the choice
4198 is made based on the associativity of that precedence level. The
4199 verbose output file made by @samp{-v} (@pxref{Invocation, ,Invoking Bison}) says
4200 how each conflict was resolved.
4202 Not all rules and not all tokens have precedence. If either the rule or
4203 the look-ahead token has no precedence, then the default is to shift.
4205 @node Contextual Precedence
4206 @section Context-Dependent Precedence
4207 @cindex context-dependent precedence
4208 @cindex unary operator precedence
4209 @cindex precedence, context-dependent
4210 @cindex precedence, unary operator
4213 Often the precedence of an operator depends on the context. This sounds
4214 outlandish at first, but it is really very common. For example, a minus
4215 sign typically has a very high precedence as a unary operator, and a
4216 somewhat lower precedence (lower than multiplication) as a binary operator.
4218 The Bison precedence declarations, @code{%left}, @code{%right} and
4219 @code{%nonassoc}, can only be used once for a given token; so a token has
4220 only one precedence declared in this way. For context-dependent
4221 precedence, you need to use an additional mechanism: the @code{%prec}
4222 modifier for rules.@refill
4224 The @code{%prec} modifier declares the precedence of a particular rule by
4225 specifying a terminal symbol whose precedence should be used for that rule.
4226 It's not necessary for that symbol to appear otherwise in the rule. The
4227 modifier's syntax is:
4230 %prec @var{terminal-symbol}
4234 and it is written after the components of the rule. Its effect is to
4235 assign the rule the precedence of @var{terminal-symbol}, overriding
4236 the precedence that would be deduced for it in the ordinary way. The
4237 altered rule precedence then affects how conflicts involving that rule
4238 are resolved (@pxref{Precedence, ,Operator Precedence}).
4240 Here is how @code{%prec} solves the problem of unary minus. First, declare
4241 a precedence for a fictitious terminal symbol named @code{UMINUS}. There
4242 are no tokens of this type, but the symbol serves to stand for its
4252 Now the precedence of @code{UMINUS} can be used in specific rules:
4259 | '-' exp %prec UMINUS
4264 @section Parser States
4265 @cindex finite-state machine
4266 @cindex parser state
4267 @cindex state (of parser)
4269 The function @code{yyparse} is implemented using a finite-state machine.
4270 The values pushed on the parser stack are not simply token type codes; they
4271 represent the entire sequence of terminal and nonterminal symbols at or
4272 near the top of the stack. The current state collects all the information
4273 about previous input which is relevant to deciding what to do next.
4275 Each time a look-ahead token is read, the current parser state together
4276 with the type of look-ahead token are looked up in a table. This table
4277 entry can say, ``Shift the look-ahead token.'' In this case, it also
4278 specifies the new parser state, which is pushed onto the top of the
4279 parser stack. Or it can say, ``Reduce using rule number @var{n}.''
4280 This means that a certain number of tokens or groupings are taken off
4281 the top of the stack, and replaced by one grouping. In other words,
4282 that number of states are popped from the stack, and one new state is
4285 There is one other alternative: the table can say that the look-ahead token
4286 is erroneous in the current state. This causes error processing to begin
4287 (@pxref{Error Recovery}).
4290 @section Reduce/Reduce Conflicts
4291 @cindex reduce/reduce conflict
4292 @cindex conflicts, reduce/reduce
4294 A reduce/reduce conflict occurs if there are two or more rules that apply
4295 to the same sequence of input. This usually indicates a serious error
4298 For example, here is an erroneous attempt to define a sequence
4299 of zero or more @code{word} groupings.
4302 sequence: /* empty */
4303 @{ printf ("empty sequence\n"); @}
4306 @{ printf ("added word %s\n", $2); @}
4309 maybeword: /* empty */
4310 @{ printf ("empty maybeword\n"); @}
4312 @{ printf ("single word %s\n", $1); @}
4317 The error is an ambiguity: there is more than one way to parse a single
4318 @code{word} into a @code{sequence}. It could be reduced to a
4319 @code{maybeword} and then into a @code{sequence} via the second rule.
4320 Alternatively, nothing-at-all could be reduced into a @code{sequence}
4321 via the first rule, and this could be combined with the @code{word}
4322 using the third rule for @code{sequence}.
4324 There is also more than one way to reduce nothing-at-all into a
4325 @code{sequence}. This can be done directly via the first rule,
4326 or indirectly via @code{maybeword} and then the second rule.
4328 You might think that this is a distinction without a difference, because it
4329 does not change whether any particular input is valid or not. But it does
4330 affect which actions are run. One parsing order runs the second rule's
4331 action; the other runs the first rule's action and the third rule's action.
4332 In this example, the output of the program changes.
4334 Bison resolves a reduce/reduce conflict by choosing to use the rule that
4335 appears first in the grammar, but it is very risky to rely on this. Every
4336 reduce/reduce conflict must be studied and usually eliminated. Here is the
4337 proper way to define @code{sequence}:
4340 sequence: /* empty */
4341 @{ printf ("empty sequence\n"); @}
4343 @{ printf ("added word %s\n", $2); @}
4347 Here is another common error that yields a reduce/reduce conflict:
4350 sequence: /* empty */
4352 | sequence redirects
4359 redirects:/* empty */
4360 | redirects redirect
4365 The intention here is to define a sequence which can contain either
4366 @code{word} or @code{redirect} groupings. The individual definitions of
4367 @code{sequence}, @code{words} and @code{redirects} are error-free, but the
4368 three together make a subtle ambiguity: even an empty input can be parsed
4369 in infinitely many ways!
4371 Consider: nothing-at-all could be a @code{words}. Or it could be two
4372 @code{words} in a row, or three, or any number. It could equally well be a
4373 @code{redirects}, or two, or any number. Or it could be a @code{words}
4374 followed by three @code{redirects} and another @code{words}. And so on.
4376 Here are two ways to correct these rules. First, to make it a single level
4380 sequence: /* empty */
4386 Second, to prevent either a @code{words} or a @code{redirects}
4390 sequence: /* empty */
4392 | sequence redirects
4400 | redirects redirect
4404 @node Mystery Conflicts
4405 @section Mysterious Reduce/Reduce Conflicts
4407 Sometimes reduce/reduce conflicts can occur that don't look warranted.
4415 def: param_spec return_spec ','
4419 | name_list ':' type
4437 | name ',' name_list
4442 It would seem that this grammar can be parsed with only a single token
4443 of look-ahead: when a @code{param_spec} is being read, an @code{ID} is
4444 a @code{name} if a comma or colon follows, or a @code{type} if another
4445 @code{ID} follows. In other words, this grammar is LR(1).
4449 However, Bison, like most parser generators, cannot actually handle all
4450 LR(1) grammars. In this grammar, two contexts, that after an @code{ID}
4451 at the beginning of a @code{param_spec} and likewise at the beginning of
4452 a @code{return_spec}, are similar enough that Bison assumes they are the
4453 same. They appear similar because the same set of rules would be
4454 active---the rule for reducing to a @code{name} and that for reducing to
4455 a @code{type}. Bison is unable to determine at that stage of processing
4456 that the rules would require different look-ahead tokens in the two
4457 contexts, so it makes a single parser state for them both. Combining
4458 the two contexts causes a conflict later. In parser terminology, this
4459 occurrence means that the grammar is not LALR(1).
4461 In general, it is better to fix deficiencies than to document them. But
4462 this particular deficiency is intrinsically hard to fix; parser
4463 generators that can handle LR(1) grammars are hard to write and tend to
4464 produce parsers that are very large. In practice, Bison is more useful
4467 When the problem arises, you can often fix it by identifying the two
4468 parser states that are being confused, and adding something to make them
4469 look distinct. In the above example, adding one rule to
4470 @code{return_spec} as follows makes the problem go away:
4481 /* This rule is never used. */
4487 This corrects the problem because it introduces the possibility of an
4488 additional active rule in the context after the @code{ID} at the beginning of
4489 @code{return_spec}. This rule is not active in the corresponding context
4490 in a @code{param_spec}, so the two contexts receive distinct parser states.
4491 As long as the token @code{BOGUS} is never generated by @code{yylex},
4492 the added rule cannot alter the way actual input is parsed.
4494 In this particular example, there is another way to solve the problem:
4495 rewrite the rule for @code{return_spec} to use @code{ID} directly
4496 instead of via @code{name}. This also causes the two confusing
4497 contexts to have different sets of active rules, because the one for
4498 @code{return_spec} activates the altered rule for @code{return_spec}
4499 rather than the one for @code{name}.
4504 | name_list ':' type
4512 @node Stack Overflow
4513 @section Stack Overflow, and How to Avoid It
4514 @cindex stack overflow
4515 @cindex parser stack overflow
4516 @cindex overflow of parser stack
4518 The Bison parser stack can overflow if too many tokens are shifted and
4519 not reduced. When this happens, the parser function @code{yyparse}
4520 returns a nonzero value, pausing only to call @code{yyerror} to report
4524 By defining the macro @code{YYMAXDEPTH}, you can control how deep the
4525 parser stack can become before a stack overflow occurs. Define the
4526 macro with a value that is an integer. This value is the maximum number
4527 of tokens that can be shifted (and not reduced) before overflow.
4528 It must be a constant expression whose value is known at compile time.
4530 The stack space allowed is not necessarily allocated. If you specify a
4531 large value for @code{YYMAXDEPTH}, the parser actually allocates a small
4532 stack at first, and then makes it bigger by stages as needed. This
4533 increasing allocation happens automatically and silently. Therefore,
4534 you do not need to make @code{YYMAXDEPTH} painfully small merely to save
4535 space for ordinary inputs that do not need much stack.
4537 @cindex default stack limit
4538 The default value of @code{YYMAXDEPTH}, if you do not define it, is
4542 You can control how much stack is allocated initially by defining the
4543 macro @code{YYINITDEPTH}. This value too must be a compile-time
4544 constant integer. The default is 200.
4546 @node Error Recovery
4547 @chapter Error Recovery
4548 @cindex error recovery
4549 @cindex recovery from errors
4551 It is not usually acceptable to have a program terminate on a parse
4552 error. For example, a compiler should recover sufficiently to parse the
4553 rest of the input file and check it for errors; a calculator should accept
4556 In a simple interactive command parser where each input is one line, it may
4557 be sufficient to allow @code{yyparse} to return 1 on error and have the
4558 caller ignore the rest of the input line when that happens (and then call
4559 @code{yyparse} again). But this is inadequate for a compiler, because it
4560 forgets all the syntactic context leading up to the error. A syntax error
4561 deep within a function in the compiler input should not cause the compiler
4562 to treat the following line like the beginning of a source file.
4565 You can define how to recover from a syntax error by writing rules to
4566 recognize the special token @code{error}. This is a terminal symbol that
4567 is always defined (you need not declare it) and reserved for error
4568 handling. The Bison parser generates an @code{error} token whenever a
4569 syntax error happens; if you have provided a rule to recognize this token
4570 in the current context, the parse can continue.
4575 stmnts: /* empty string */
4581 The fourth rule in this example says that an error followed by a newline
4582 makes a valid addition to any @code{stmnts}.
4584 What happens if a syntax error occurs in the middle of an @code{exp}? The
4585 error recovery rule, interpreted strictly, applies to the precise sequence
4586 of a @code{stmnts}, an @code{error} and a newline. If an error occurs in
4587 the middle of an @code{exp}, there will probably be some additional tokens
4588 and subexpressions on the stack after the last @code{stmnts}, and there
4589 will be tokens to read before the next newline. So the rule is not
4590 applicable in the ordinary way.
4592 But Bison can force the situation to fit the rule, by discarding part of
4593 the semantic context and part of the input. First it discards states and
4594 objects from the stack until it gets back to a state in which the
4595 @code{error} token is acceptable. (This means that the subexpressions
4596 already parsed are discarded, back to the last complete @code{stmnts}.) At
4597 this point the @code{error} token can be shifted. Then, if the old
4598 look-ahead token is not acceptable to be shifted next, the parser reads
4599 tokens and discards them until it finds a token which is acceptable. In
4600 this example, Bison reads and discards input until the next newline
4601 so that the fourth rule can apply.
4603 The choice of error rules in the grammar is a choice of strategies for
4604 error recovery. A simple and useful strategy is simply to skip the rest of
4605 the current input line or current statement if an error is detected:
4608 stmnt: error ';' /* on error, skip until ';' is read */
4611 It is also useful to recover to the matching close-delimiter of an
4612 opening-delimiter that has already been parsed. Otherwise the
4613 close-delimiter will probably appear to be unmatched, and generate another,
4614 spurious error message:
4617 primary: '(' expr ')'
4623 Error recovery strategies are necessarily guesses. When they guess wrong,
4624 one syntax error often leads to another. In the above example, the error
4625 recovery rule guesses that an error is due to bad input within one
4626 @code{stmnt}. Suppose that instead a spurious semicolon is inserted in the
4627 middle of a valid @code{stmnt}. After the error recovery rule recovers
4628 from the first error, another syntax error will be found straightaway,
4629 since the text following the spurious semicolon is also an invalid
4632 To prevent an outpouring of error messages, the parser will output no error
4633 message for another syntax error that happens shortly after the first; only
4634 after three consecutive input tokens have been successfully shifted will
4635 error messages resume.
4637 Note that rules which accept the @code{error} token may have actions, just
4638 as any other rules can.
4641 You can make error messages resume immediately by using the macro
4642 @code{yyerrok} in an action. If you do this in the error rule's action, no
4643 error messages will be suppressed. This macro requires no arguments;
4644 @samp{yyerrok;} is a valid C statement.
4647 The previous look-ahead token is reanalyzed immediately after an error. If
4648 this is unacceptable, then the macro @code{yyclearin} may be used to clear
4649 this token. Write the statement @samp{yyclearin;} in the error rule's
4652 For example, suppose that on a parse error, an error handling routine is
4653 called that advances the input stream to some point where parsing should
4654 once again commence. The next symbol returned by the lexical scanner is
4655 probably correct. The previous look-ahead token ought to be discarded
4656 with @samp{yyclearin;}.
4658 @vindex YYRECOVERING
4659 The macro @code{YYRECOVERING} stands for an expression that has the
4660 value 1 when the parser is recovering from a syntax error, and 0 the
4661 rest of the time. A value of 1 indicates that error messages are
4662 currently suppressed for new syntax errors.
4664 @node Context Dependency
4665 @chapter Handling Context Dependencies
4667 The Bison paradigm is to parse tokens first, then group them into larger
4668 syntactic units. In many languages, the meaning of a token is affected by
4669 its context. Although this violates the Bison paradigm, certain techniques
4670 (known as @dfn{kludges}) may enable you to write Bison parsers for such
4674 * Semantic Tokens:: Token parsing can depend on the semantic context.
4675 * Lexical Tie-ins:: Token parsing can depend on the syntactic context.
4676 * Tie-in Recovery:: Lexical tie-ins have implications for how
4677 error recovery rules must be written.
4680 (Actually, ``kludge'' means any technique that gets its job done but is
4681 neither clean nor robust.)
4683 @node Semantic Tokens
4684 @section Semantic Info in Token Types
4686 The C language has a context dependency: the way an identifier is used
4687 depends on what its current meaning is. For example, consider this:
4693 This looks like a function call statement, but if @code{foo} is a typedef
4694 name, then this is actually a declaration of @code{x}. How can a Bison
4695 parser for C decide how to parse this input?
4697 The method used in GNU C is to have two different token types,
4698 @code{IDENTIFIER} and @code{TYPENAME}. When @code{yylex} finds an
4699 identifier, it looks up the current declaration of the identifier in order
4700 to decide which token type to return: @code{TYPENAME} if the identifier is
4701 declared as a typedef, @code{IDENTIFIER} otherwise.
4703 The grammar rules can then express the context dependency by the choice of
4704 token type to recognize. @code{IDENTIFIER} is accepted as an expression,
4705 but @code{TYPENAME} is not. @code{TYPENAME} can start a declaration, but
4706 @code{IDENTIFIER} cannot. In contexts where the meaning of the identifier
4707 is @emph{not} significant, such as in declarations that can shadow a
4708 typedef name, either @code{TYPENAME} or @code{IDENTIFIER} is
4709 accepted---there is one rule for each of the two token types.
4711 This technique is simple to use if the decision of which kinds of
4712 identifiers to allow is made at a place close to where the identifier is
4713 parsed. But in C this is not always so: C allows a declaration to
4714 redeclare a typedef name provided an explicit type has been specified
4718 typedef int foo, bar, lose;
4719 static foo (bar); /* @r{redeclare @code{bar} as static variable} */
4720 static int foo (lose); /* @r{redeclare @code{foo} as function} */
4723 Unfortunately, the name being declared is separated from the declaration
4724 construct itself by a complicated syntactic structure---the ``declarator''.
4726 As a result, part of the Bison parser for C needs to be duplicated, with
4727 all the nonterminal names changed: once for parsing a declaration in
4728 which a typedef name can be redefined, and once for parsing a
4729 declaration in which that can't be done. Here is a part of the
4730 duplication, with actions omitted for brevity:
4734 declarator maybeasm '='
4736 | declarator maybeasm
4740 notype_declarator maybeasm '='
4742 | notype_declarator maybeasm
4747 Here @code{initdcl} can redeclare a typedef name, but @code{notype_initdcl}
4748 cannot. The distinction between @code{declarator} and
4749 @code{notype_declarator} is the same sort of thing.
4751 There is some similarity between this technique and a lexical tie-in
4752 (described next), in that information which alters the lexical analysis is
4753 changed during parsing by other parts of the program. The difference is
4754 here the information is global, and is used for other purposes in the
4755 program. A true lexical tie-in has a special-purpose flag controlled by
4756 the syntactic context.
4758 @node Lexical Tie-ins
4759 @section Lexical Tie-ins
4760 @cindex lexical tie-in
4762 One way to handle context-dependency is the @dfn{lexical tie-in}: a flag
4763 which is set by Bison actions, whose purpose is to alter the way tokens are
4766 For example, suppose we have a language vaguely like C, but with a special
4767 construct @samp{hex (@var{hex-expr})}. After the keyword @code{hex} comes
4768 an expression in parentheses in which all integers are hexadecimal. In
4769 particular, the token @samp{a1b} must be treated as an integer rather than
4770 as an identifier if it appears in that context. Here is how you can do it:
4789 @{ $$ = make_sum ($1, $3); @}
4803 Here we assume that @code{yylex} looks at the value of @code{hexflag}; when
4804 it is nonzero, all integers are parsed in hexadecimal, and tokens starting
4805 with letters are parsed as integers if possible.
4807 The declaration of @code{hexflag} shown in the C declarations section of
4808 the parser file is needed to make it accessible to the actions
4809 (@pxref{C Declarations, ,The C Declarations Section}). You must also write the code in @code{yylex}
4812 @node Tie-in Recovery
4813 @section Lexical Tie-ins and Error Recovery
4815 Lexical tie-ins make strict demands on any error recovery rules you have.
4816 @xref{Error Recovery}.
4818 The reason for this is that the purpose of an error recovery rule is to
4819 abort the parsing of one construct and resume in some larger construct.
4820 For example, in C-like languages, a typical error recovery rule is to skip
4821 tokens until the next semicolon, and then start a new statement, like this:
4825 | IF '(' expr ')' stmt @{ @dots{} @}
4832 If there is a syntax error in the middle of a @samp{hex (@var{expr})}
4833 construct, this error rule will apply, and then the action for the
4834 completed @samp{hex (@var{expr})} will never run. So @code{hexflag} would
4835 remain set for the entire rest of the input, or until the next @code{hex}
4836 keyword, causing identifiers to be misinterpreted as integers.
4838 To avoid this problem the error recovery rule itself clears @code{hexflag}.
4840 There may also be an error recovery rule that works within expressions.
4841 For example, there could be a rule which applies within parentheses
4842 and skips to the close-parenthesis:
4854 If this rule acts within the @code{hex} construct, it is not going to abort
4855 that construct (since it applies to an inner level of parentheses within
4856 the construct). Therefore, it should not clear the flag: the rest of
4857 the @code{hex} construct should be parsed with the flag still in effect.
4859 What if there is an error recovery rule which might abort out of the
4860 @code{hex} construct or might not, depending on circumstances? There is no
4861 way you can write the action to determine whether a @code{hex} construct is
4862 being aborted or not. So if you are using a lexical tie-in, you had better
4863 make sure your error recovery rules are not of this kind. Each rule must
4864 be such that you can be sure that it always will, or always won't, have to
4868 @chapter Debugging Your Parser
4872 @cindex tracing the parser
4874 If a Bison grammar compiles properly but doesn't do what you want when it
4875 runs, the @code{yydebug} parser-trace feature can help you figure out why.
4877 To enable compilation of trace facilities, you must define the macro
4878 @code{YYDEBUG} when you compile the parser. You could use
4879 @samp{-DYYDEBUG=1} as a compiler option or you could put @samp{#define
4880 YYDEBUG 1} in the C declarations section of the grammar file
4881 (@pxref{C Declarations, ,The C Declarations Section}). Alternatively, use the @samp{-t} option when
4882 you run Bison (@pxref{Invocation, ,Invoking Bison}). We always define @code{YYDEBUG} so that
4883 debugging is always possible.
4885 The trace facility uses @code{stderr}, so you must add @w{@code{#include
4886 <stdio.h>}} to the C declarations section unless it is already there.
4888 Once you have compiled the program with trace facilities, the way to
4889 request a trace is to store a nonzero value in the variable @code{yydebug}.
4890 You can do this by making the C code do it (in @code{main}, perhaps), or
4891 you can alter the value with a C debugger.
4893 Each step taken by the parser when @code{yydebug} is nonzero produces a
4894 line or two of trace information, written on @code{stderr}. The trace
4895 messages tell you these things:
4899 Each time the parser calls @code{yylex}, what kind of token was read.
4902 Each time a token is shifted, the depth and complete contents of the
4903 state stack (@pxref{Parser States}).
4906 Each time a rule is reduced, which rule it is, and the complete contents
4907 of the state stack afterward.
4910 To make sense of this information, it helps to refer to the listing file
4911 produced by the Bison @samp{-v} option (@pxref{Invocation, ,Invoking Bison}). This file
4912 shows the meaning of each state in terms of positions in various rules, and
4913 also what each state will do with each possible input token. As you read
4914 the successive trace messages, you can see that the parser is functioning
4915 according to its specification in the listing file. Eventually you will
4916 arrive at the place where something undesirable happens, and you will see
4917 which parts of the grammar are to blame.
4919 The parser file is a C program and you can use C debuggers on it, but it's
4920 not easy to interpret what it is doing. The parser function is a
4921 finite-state machine interpreter, and aside from the actions it executes
4922 the same code over and over. Only the values of variables show where in
4923 the grammar it is working.
4926 The debugging information normally gives the token type of each token
4927 read, but not its semantic value. You can optionally define a macro
4928 named @code{YYPRINT} to provide a way to print the value. If you define
4929 @code{YYPRINT}, it should take three arguments. The parser will pass a
4930 standard I/O stream, the numeric code for the token type, and the token
4931 value (from @code{yylval}).
4933 Here is an example of @code{YYPRINT} suitable for the multi-function
4934 calculator (@pxref{Mfcalc Decl, ,Declarations for @code{mfcalc}}):
4937 #define YYPRINT(file, type, value) yyprint (file, type, value)
4940 yyprint (FILE *file, int type, YYSTYPE value)
4943 fprintf (file, " %s", value.tptr->name);
4944 else if (type == NUM)
4945 fprintf (file, " %d", value.val);
4950 @chapter Invoking Bison
4951 @cindex invoking Bison
4952 @cindex Bison invocation
4953 @cindex options for invoking Bison
4955 The usual way to invoke Bison is as follows:
4961 Here @var{infile} is the grammar file name, which usually ends in
4962 @samp{.y}. The parser file's name is made by replacing the @samp{.y}
4963 with @samp{.tab.c}. Thus, the @samp{bison foo.y} filename yields
4964 @file{foo.tab.c}, and the @samp{bison hack/foo.y} filename yields
4965 @file{hack/foo.tab.c}. It's is also possible, in case you are writting
4966 C++ code instead of C in your grammar file, to name it @file{foo.ypp}
4967 or @file{foo.y++}. Then, the output files will take an extention like
4968 the given one as input (repectively @file{foo.tab.cpp} and @file{foo.tab.c++}).
4969 This feature takes effect with all options that manipulate filenames like
4970 @samp{-o} or @samp{-d}.
4975 bison -d @var{infile.yxx}
4978 will produce @file{infile.tab.cxx} and @file{infile.tab.hxx}. and
4981 bison -d @var{infile.y} -o @var{output.c++}
4984 will produce @file{output.c++} and @file{outfile.h++}.
4988 * Bison Options:: All the options described in detail,
4989 in alphabetical order by short options.
4990 * Environment Variables:: Variables which affect Bison execution.
4991 * Option Cross Key:: Alphabetical list of long options.
4992 * VMS Invocation:: Bison command syntax on VMS.
4996 @section Bison Options
4998 Bison supports both traditional single-letter options and mnemonic long
4999 option names. Long option names are indicated with @samp{--} instead of
5000 @samp{-}. Abbreviations for option names are allowed as long as they
5001 are unique. When a long option takes an argument, like
5002 @samp{--file-prefix}, connect the option name and the argument with
5005 Here is a list of options that can be used with Bison, alphabetized by
5006 short option. It is followed by a cross key alphabetized by long
5009 @c Please, keep this ordered as in `bison --help'.
5015 Print a summary of the command-line options to Bison and exit.
5019 Print the version number of Bison and exit.
5024 @itemx --fixed-output-files
5025 Equivalent to @samp{-o y.tab.c}; the parser output file is called
5026 @file{y.tab.c}, and the other outputs are called @file{y.output} and
5027 @file{y.tab.h}. The purpose of this option is to imitate Yacc's output
5028 file name conventions. Thus, the following shell script can substitute
5041 @itemx --skeleton=@var{file}
5042 Specify the skeleton to use. You probably don't need this option unless
5043 you are developing Bison.
5047 Output a definition of the macro @code{YYDEBUG} into the parser file, so
5048 that the debugging facilities are compiled. @xref{Debugging, ,Debugging
5052 Pretend that @code{%locactions} was specified. @xref{Decl Summary}.
5054 @item -p @var{prefix}
5055 @itemx --name-prefix=@var{prefix}
5056 Rename the external symbols used in the parser so that they start with
5057 @var{prefix} instead of @samp{yy}. The precise list of symbols renamed
5058 is @code{yyparse}, @code{yylex}, @code{yyerror}, @code{yynerrs},
5059 @code{yylval}, @code{yychar} and @code{yydebug}.
5061 For example, if you use @samp{-p c}, the names become @code{cparse},
5062 @code{clex}, and so on.
5064 @xref{Multiple Parsers, ,Multiple Parsers in the Same Program}.
5068 Don't put any @code{#line} preprocessor commands in the parser file.
5069 Ordinarily Bison puts them in the parser file so that the C compiler
5070 and debuggers will associate errors with your source file, the
5071 grammar file. This option causes them to associate errors with the
5072 parser file, treating it as an independent source file in its own right.
5076 Pretend that @code{%no_parser} was specified. @xref{Decl Summary}.
5079 @itemx --token-table
5080 Pretend that @code{%token_table} was specified. @xref{Decl Summary}.
5088 Pretend that @code{%verbose} was specified, i.e., write an extra output
5089 file containing macro definitions for the token type names defined in
5090 the grammar and the semantic value type @code{YYSTYPE}, as well as a few
5091 @code{extern} variable declarations. @xref{Decl Summary}.
5093 @item --defines=@var{defines-file}
5094 The behaviour of @var{--defines} is the same than @samp{-d}. The only
5095 difference is that it has an optionnal argument which is the name of
5096 the output filename.
5098 @item -b @var{file-prefix}
5099 @itemx --file-prefix=@var{prefix}
5100 Specify a prefix to use for all Bison output file names. The names are
5101 chosen as if the input file were named @file{@var{prefix}.c}.
5105 Pretend that @code{%verbose} was specified, i.e, write an extra output
5106 file containing verbose descriptions of the grammar and
5107 parser. @xref{Decl Summary}, for more.
5109 @item -o @var{outfile}
5110 @itemx --output-file=@var{outfile}
5111 Specify the name @var{outfile} for the parser file.
5113 The other output files' names are constructed from @var{outfile}
5114 as described under the @samp{-v} and @samp{-d} options.
5117 Output a VCG definition of the LALR(1) grammar automaton computed by
5118 Bison. If the grammar file is @file{foo.y}, the VCG output file will
5121 @item --graph=@var{graph-file}
5122 The behaviour of @var{--graph} is the same than @samp{-g}. The only
5123 difference is that it has an optionnal argument which is the name of
5124 the output graph filename.
5127 @node Environment Variables
5128 @section Environment Variables
5129 @cindex environment variables
5131 @cindex BISON_SIMPLE
5133 Here is a list of environment variables which affect the way Bison
5139 Much of the parser generated by Bison is copied verbatim from a file
5140 called @file{bison.simple}. If Bison cannot find that file, or if you
5141 would like to direct Bison to use a different copy, setting the
5142 environment variable @code{BISON_SIMPLE} to the path of the file will
5143 cause Bison to use that copy instead.
5145 When the @samp{%semantic_parser} declaration is used, Bison copies from
5146 a file called @file{bison.hairy} instead. The location of this file can
5147 also be specified or overridden in a similar fashion, with the
5148 @code{BISON_HAIRY} environment variable.
5152 @node Option Cross Key
5153 @section Option Cross Key
5155 Here is a list of options, alphabetized by long option, to help you find
5156 the corresponding short option.
5159 \def\leaderfill{\leaders\hbox to 1em{\hss.\hss}\hfill}
5162 \line{ --debug \leaderfill -t}
5163 \line{ --defines \leaderfill -d}
5164 \line{ --file-prefix \leaderfill -b}
5165 \line{ --fixed-output-files \leaderfill -y}
5166 \line{ --graph \leaderfill -g}
5167 \line{ --help \leaderfill -h}
5168 \line{ --name-prefix \leaderfill -p}
5169 \line{ --no-lines \leaderfill -l}
5170 \line{ --no-parser \leaderfill -n}
5171 \line{ --output-file \leaderfill -o}
5172 \line{ --token-table \leaderfill -k}
5173 \line{ --verbose \leaderfill -v}
5174 \line{ --version \leaderfill -V}
5175 \line{ --yacc \leaderfill -y}
5182 --defines=@var{defines-file} -d
5183 --file-prefix=@var{prefix} -b @var{file-prefix}
5184 --fixed-output-files --yacc -y
5185 --graph=@var{graph-file} -d
5187 --name-prefix=@var{prefix} -p @var{name-prefix}
5190 --output-file=@var{outfile} -o @var{outfile}
5197 @node VMS Invocation
5198 @section Invoking Bison under VMS
5199 @cindex invoking Bison under VMS
5202 The command line syntax for Bison on VMS is a variant of the usual
5203 Bison command syntax---adapted to fit VMS conventions.
5205 To find the VMS equivalent for any Bison option, start with the long
5206 option, and substitute a @samp{/} for the leading @samp{--}, and
5207 substitute a @samp{_} for each @samp{-} in the name of the long option.
5208 For example, the following invocation under VMS:
5211 bison /debug/name_prefix=bar foo.y
5215 is equivalent to the following command under POSIX.
5218 bison --debug --name-prefix=bar foo.y
5221 The VMS file system does not permit filenames such as
5222 @file{foo.tab.c}. In the above example, the output file
5223 would instead be named @file{foo_tab.c}.
5225 @node Table of Symbols
5226 @appendix Bison Symbols
5227 @cindex Bison symbols, table of
5228 @cindex symbols in Bison, table of
5232 A token name reserved for error recovery. This token may be used in
5233 grammar rules so as to allow the Bison parser to recognize an error in
5234 the grammar without halting the process. In effect, a sentence
5235 containing an error may be recognized as valid. On a parse error, the
5236 token @code{error} becomes the current look-ahead token. Actions
5237 corresponding to @code{error} are then executed, and the look-ahead
5238 token is reset to the token that originally caused the violation.
5239 @xref{Error Recovery}.
5242 Macro to pretend that an unrecoverable syntax error has occurred, by
5243 making @code{yyparse} return 1 immediately. The error reporting
5244 function @code{yyerror} is not called. @xref{Parser Function, ,The
5245 Parser Function @code{yyparse}}.
5248 Macro to pretend that a complete utterance of the language has been
5249 read, by making @code{yyparse} return 0 immediately.
5250 @xref{Parser Function, ,The Parser Function @code{yyparse}}.
5253 Macro to discard a value from the parser stack and fake a look-ahead
5254 token. @xref{Action Features, ,Special Features for Use in Actions}.
5257 Macro to pretend that a syntax error has just been detected: call
5258 @code{yyerror} and then perform normal error recovery if possible
5259 (@pxref{Error Recovery}), or (if recovery is impossible) make
5260 @code{yyparse} return 1. @xref{Error Recovery}.
5262 @item YYERROR_VERBOSE
5263 Macro that you define with @code{#define} in the Bison declarations
5264 section to request verbose, specific error message strings when
5265 @code{yyerror} is called.
5268 Macro for specifying the initial size of the parser stack.
5269 @xref{Stack Overflow}.
5272 Macro for specifying an extra argument (or list of extra arguments) for
5273 @code{yyparse} to pass to @code{yylex}. @xref{Pure Calling,, Calling
5274 Conventions for Pure Parsers}.
5277 Macro for the data type of @code{yylloc}; a structure with four
5278 members. @xref{Location Type, , Data Types of Locations}.
5281 Default value for YYLTYPE.
5284 Macro for specifying the maximum size of the parser stack.
5285 @xref{Stack Overflow}.
5288 Macro for specifying the name of a parameter that @code{yyparse} should
5289 accept. @xref{Pure Calling,, Calling Conventions for Pure Parsers}.
5292 Macro whose value indicates whether the parser is recovering from a
5293 syntax error. @xref{Action Features, ,Special Features for Use in Actions}.
5295 @item YYSTACK_USE_ALLOCA
5296 Macro used to control the use of @code{alloca}. If defined to @samp{0},
5297 the parser will not use @code{alloca} but @code{malloc} when trying to
5298 grow its internal stacks. Do @emph{not} define @code{YYSTACK_USE_ALLOCA}
5302 Macro for the data type of semantic values; @code{int} by default.
5303 @xref{Value Type, ,Data Types of Semantic Values}.
5306 External integer variable that contains the integer value of the current
5307 look-ahead token. (In a pure parser, it is a local variable within
5308 @code{yyparse}.) Error-recovery rule actions may examine this variable.
5309 @xref{Action Features, ,Special Features for Use in Actions}.
5312 Macro used in error-recovery rule actions. It clears the previous
5313 look-ahead token. @xref{Error Recovery}.
5316 External integer variable set to zero by default. If @code{yydebug}
5317 is given a nonzero value, the parser will output information on input
5318 symbols and parser action. @xref{Debugging, ,Debugging Your Parser}.
5321 Macro to cause parser to recover immediately to its normal mode
5322 after a parse error. @xref{Error Recovery}.
5325 User-supplied function to be called by @code{yyparse} on error. The
5326 function receives one argument, a pointer to a character string
5327 containing an error message. @xref{Error Reporting, ,The Error
5328 Reporting Function @code{yyerror}}.
5331 User-supplied lexical analyzer function, called with no arguments
5332 to get the next token. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
5335 External variable in which @code{yylex} should place the semantic
5336 value associated with a token. (In a pure parser, it is a local
5337 variable within @code{yyparse}, and its address is passed to
5338 @code{yylex}.) @xref{Token Values, ,Semantic Values of Tokens}.
5341 External variable in which @code{yylex} should place the line and column
5342 numbers associated with a token. (In a pure parser, it is a local
5343 variable within @code{yyparse}, and its address is passed to
5344 @code{yylex}.) You can ignore this variable if you don't use the
5345 @samp{@@} feature in the grammar actions. @xref{Token Positions,
5346 ,Textual Positions of Tokens}.
5349 Global variable which Bison increments each time there is a parse error.
5350 (In a pure parser, it is a local variable within @code{yyparse}.)
5351 @xref{Error Reporting, ,The Error Reporting Function @code{yyerror}}.
5354 The parser function produced by Bison; call this function to start
5355 parsing. @xref{Parser Function, ,The Parser Function @code{yyparse}}.
5358 Equip the parser for debugging. @xref{Decl Summary}.
5361 Bison declaration to create a header file meant for the scanner.
5362 @xref{Decl Summary}.
5364 @c @item %source_extension
5365 @c Bison declaration to specify the generated parser output file extension.
5366 @c @xref{Decl Summary}.
5368 @c @item %header_extension
5369 @c Bison declaration to specify the generated parser header file extension
5370 @c if required. @xref{Decl Summary}.
5373 Bison declaration to assign left associativity to token(s).
5374 @xref{Precedence Decl, ,Operator Precedence}.
5377 Bison declaration to avoid generating @code{#line} directives in the
5378 parser file. @xref{Decl Summary}.
5381 Bison declaration to assign non-associativity to token(s).
5382 @xref{Precedence Decl, ,Operator Precedence}.
5385 Bison declaration to assign a precedence to a specific rule.
5386 @xref{Contextual Precedence, ,Context-Dependent Precedence}.
5389 Bison declaration to request a pure (reentrant) parser.
5390 @xref{Pure Decl, ,A Pure (Reentrant) Parser}.
5393 Bison declaration to assign right associativity to token(s).
5394 @xref{Precedence Decl, ,Operator Precedence}.
5397 Bison declaration to specify the start symbol. @xref{Start Decl, ,The Start-Symbol}.
5400 Bison declaration to declare token(s) without specifying precedence.
5401 @xref{Token Decl, ,Token Type Names}.
5404 Bison declaration to include a token name table in the parser file.
5405 @xref{Decl Summary}.
5408 Bison declaration to declare nonterminals. @xref{Type Decl, ,Nonterminal Symbols}.
5411 Bison declaration to specify several possible data types for semantic
5412 values. @xref{Union Decl, ,The Collection of Value Types}.
5415 These are the punctuation and delimiters used in Bison input:
5419 Delimiter used to separate the grammar rule section from the
5420 Bison declarations section or the additional C code section.
5421 @xref{Grammar Layout, ,The Overall Layout of a Bison Grammar}.
5424 All code listed between @samp{%@{} and @samp{%@}} is copied directly to
5425 the output file uninterpreted. Such code forms the ``C declarations''
5426 section of the input file. @xref{Grammar Outline, ,Outline of a Bison
5430 Comment delimiters, as in C.
5433 Separates a rule's result from its components. @xref{Rules, ,Syntax of
5437 Terminates a rule. @xref{Rules, ,Syntax of Grammar Rules}.
5440 Separates alternate rules for the same result nonterminal.
5441 @xref{Rules, ,Syntax of Grammar Rules}.
5449 @item Backus-Naur Form (BNF)
5450 Formal method of specifying context-free grammars. BNF was first used
5451 in the @cite{ALGOL-60} report, 1963. @xref{Language and Grammar,
5452 ,Languages and Context-Free Grammars}.
5454 @item Context-free grammars
5455 Grammars specified as rules that can be applied regardless of context.
5456 Thus, if there is a rule which says that an integer can be used as an
5457 expression, integers are allowed @emph{anywhere} an expression is
5458 permitted. @xref{Language and Grammar, ,Languages and Context-Free
5461 @item Dynamic allocation
5462 Allocation of memory that occurs during execution, rather than at
5463 compile time or on entry to a function.
5466 Analogous to the empty set in set theory, the empty string is a
5467 character string of length zero.
5469 @item Finite-state stack machine
5470 A ``machine'' that has discrete states in which it is said to exist at
5471 each instant in time. As input to the machine is processed, the
5472 machine moves from state to state as specified by the logic of the
5473 machine. In the case of the parser, the input is the language being
5474 parsed, and the states correspond to various stages in the grammar
5475 rules. @xref{Algorithm, ,The Bison Parser Algorithm }.
5478 A language construct that is (in general) grammatically divisible;
5479 for example, `expression' or `declaration' in C.
5480 @xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5482 @item Infix operator
5483 An arithmetic operator that is placed between the operands on which it
5484 performs some operation.
5487 A continuous flow of data between devices or programs.
5489 @item Language construct
5490 One of the typical usage schemas of the language. For example, one of
5491 the constructs of the C language is the @code{if} statement.
5492 @xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5494 @item Left associativity
5495 Operators having left associativity are analyzed from left to right:
5496 @samp{a+b+c} first computes @samp{a+b} and then combines with
5497 @samp{c}. @xref{Precedence, ,Operator Precedence}.
5499 @item Left recursion
5500 A rule whose result symbol is also its first component symbol; for
5501 example, @samp{expseq1 : expseq1 ',' exp;}. @xref{Recursion, ,Recursive
5504 @item Left-to-right parsing
5505 Parsing a sentence of a language by analyzing it token by token from
5506 left to right. @xref{Algorithm, ,The Bison Parser Algorithm }.
5508 @item Lexical analyzer (scanner)
5509 A function that reads an input stream and returns tokens one by one.
5510 @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
5512 @item Lexical tie-in
5513 A flag, set by actions in the grammar rules, which alters the way
5514 tokens are parsed. @xref{Lexical Tie-ins}.
5516 @item Literal string token
5517 A token which consists of two or more fixed characters. @xref{Symbols}.
5519 @item Look-ahead token
5520 A token already read but not yet shifted. @xref{Look-Ahead, ,Look-Ahead
5524 The class of context-free grammars that Bison (like most other parser
5525 generators) can handle; a subset of LR(1). @xref{Mystery Conflicts, ,
5526 Mysterious Reduce/Reduce Conflicts}.
5529 The class of context-free grammars in which at most one token of
5530 look-ahead is needed to disambiguate the parsing of any piece of input.
5532 @item Nonterminal symbol
5533 A grammar symbol standing for a grammatical construct that can
5534 be expressed through rules in terms of smaller constructs; in other
5535 words, a construct that is not a token. @xref{Symbols}.
5538 An error encountered during parsing of an input stream due to invalid
5539 syntax. @xref{Error Recovery}.
5542 A function that recognizes valid sentences of a language by analyzing
5543 the syntax structure of a set of tokens passed to it from a lexical
5546 @item Postfix operator
5547 An arithmetic operator that is placed after the operands upon which it
5548 performs some operation.
5551 Replacing a string of nonterminals and/or terminals with a single
5552 nonterminal, according to a grammar rule. @xref{Algorithm, ,The Bison
5556 A reentrant subprogram is a subprogram which can be in invoked any
5557 number of times in parallel, without interference between the various
5558 invocations. @xref{Pure Decl, ,A Pure (Reentrant) Parser}.
5560 @item Reverse polish notation
5561 A language in which all operators are postfix operators.
5563 @item Right recursion
5564 A rule whose result symbol is also its last component symbol; for
5565 example, @samp{expseq1: exp ',' expseq1;}. @xref{Recursion, ,Recursive
5569 In computer languages, the semantics are specified by the actions
5570 taken for each instance of the language, i.e., the meaning of
5571 each statement. @xref{Semantics, ,Defining Language Semantics}.
5574 A parser is said to shift when it makes the choice of analyzing
5575 further input from the stream rather than reducing immediately some
5576 already-recognized rule. @xref{Algorithm, ,The Bison Parser Algorithm }.
5578 @item Single-character literal
5579 A single character that is recognized and interpreted as is.
5580 @xref{Grammar in Bison, ,From Formal Rules to Bison Input}.
5583 The nonterminal symbol that stands for a complete valid utterance in
5584 the language being parsed. The start symbol is usually listed as the
5585 first nonterminal symbol in a language specification.
5586 @xref{Start Decl, ,The Start-Symbol}.
5589 A data structure where symbol names and associated data are stored
5590 during parsing to allow for recognition and use of existing
5591 information in repeated uses of a symbol. @xref{Multi-function Calc}.
5594 A basic, grammatically indivisible unit of a language. The symbol
5595 that describes a token in the grammar is a terminal symbol.
5596 The input of the Bison parser is a stream of tokens which comes from
5597 the lexical analyzer. @xref{Symbols}.
5599 @item Terminal symbol
5600 A grammar symbol that has no rules in the grammar and therefore is
5601 grammatically indivisible. The piece of text it represents is a token.
5602 @xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5605 @node Copying This Manual
5606 @appendix Copying This Manual
5609 * GNU Free Documentation License:: License for copying this manual.