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