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