]> git.saurik.com Git - bison.git/blame_incremental - doc/bison.texinfo
[__sun && __i386]: Include alloca.h.
[bison.git] / doc / bison.texinfo
... / ...
CommitLineData
1\input texinfo @c -*-texinfo-*-
2@comment %**start of header
3@setfilename bison.info
4@settitle Bison 1.25
5@setchapternewpage odd
6
7@iftex
8@finalout
9@end iftex
10
11@c SMALL BOOK version
12@c This edition has been formatted so that you can format and print it in
13@c the smallbook format.
14@c @smallbook
15
16@c next time, consider using @set for edition number, etc...
17
18@c Set following if you have the new `shorttitlepage' command
19@c @clear shorttitlepage-enabled
20@c @set shorttitlepage-enabled
21
22@c ISPELL CHECK: done, 14 Jan 1993 --bob
23
24@c Check COPYRIGHT dates. should be updated in the titlepage, ifinfo
25@c titlepage; should NOT be changed in the GPL. --mew
26
27@iftex
28@syncodeindex fn cp
29@syncodeindex vr cp
30@syncodeindex tp cp
31@end iftex
32@ifinfo
33@synindex fn cp
34@synindex vr cp
35@synindex tp cp
36@end ifinfo
37@comment %**end of header
38
39@ifinfo
40This file documents the Bison parser generator.
41
42Copyright (C) 1988, 89, 90, 91, 92, 93, 1995 Free Software Foundation, Inc.
43
44Permission is granted to make and distribute verbatim copies of
45this manual provided the copyright notice and this permission notice
46are preserved on all copies.
47
48@ignore
49Permission is granted to process this file through Tex and print the
50results, provided the printed document carries copying permission
51notice identical to this one except for the removal of this paragraph
52(this paragraph not being relevant to the printed manual).
53
54@end ignore
55Permission is granted to copy and distribute modified versions of this
56manual under the conditions for verbatim copying, provided also that the
57sections entitled ``GNU General Public License'' and ``Conditions for
58Using Bison'' are included exactly as in the original, and provided that
59the entire resulting derived work is distributed under the terms of a
60permission notice identical to this one.
61
62Permission is granted to copy and distribute translations of this manual
63into another language, under the above conditions for modified versions,
64except that the sections entitled ``GNU General Public License'',
65``Conditions for Using Bison'' and this permission notice may be
66included in translations approved by the Free Software Foundation
67instead of in the original English.
68@end ifinfo
69
70@ifset shorttitlepage-enabled
71@shorttitlepage Bison
72@end ifset
73@titlepage
74@title Bison
75@subtitle The YACC-compatible Parser Generator
76@subtitle November 1995, Bison Version 1.25
77
78@author by Charles Donnelly and Richard Stallman
79
80@page
81@vskip 0pt plus 1filll
82Copyright @copyright{} 1988, 89, 90, 91, 92, 93, 1995 Free Software
83Foundation
84
85@sp 2
86Published by the Free Software Foundation @*
8759 Temple Place, Suite 330 @*
88Boston, MA 02111-1307 USA @*
89Printed copies are available for $15 each.@*
90ISBN 1-882114-45-0
91
92Permission is granted to make and distribute verbatim copies of
93this manual provided the copyright notice and this permission notice
94are preserved on all copies.
95
96@ignore
97Permission is granted to process this file through TeX and print the
98results, provided the printed document carries copying permission
99notice identical to this one except for the removal of this paragraph
100(this paragraph not being relevant to the printed manual).
101
102@end ignore
103Permission is granted to copy and distribute modified versions of this
104manual under the conditions for verbatim copying, provided also that the
105sections entitled ``GNU General Public License'' and ``Conditions for
106Using Bison'' are included exactly as in the original, and provided that
107the entire resulting derived work is distributed under the terms of a
108permission notice identical to this one.
109
110Permission is granted to copy and distribute translations of this manual
111into another language, under the above conditions for modified versions,
112except that the sections entitled ``GNU General Public License'',
113``Conditions for Using Bison'' and this permission notice may be
114included in translations approved by the Free Software Foundation
115instead of in the original English.
116@sp 2
117Cover art by Etienne Suvasa.
118@end titlepage
119@page
120
121@node Top, Introduction, (dir), (dir)
122
123@ifinfo
124This manual documents version 1.25 of Bison.
125@end ifinfo
126
127@menu
128* Introduction::
129* Conditions::
130* Copying:: The GNU General Public License says
131 how you can copy and share Bison
132
133Tutorial sections:
134* Concepts:: Basic concepts for understanding Bison.
135* Examples:: Three simple explained examples of using Bison.
136
137Reference sections:
138* Grammar File:: Writing Bison declarations and rules.
139* Interface:: C-language interface to the parser function @code{yyparse}.
140* Algorithm:: How the Bison parser works at run-time.
141* Error Recovery:: Writing rules for error recovery.
142* Context Dependency:: What to do if your language syntax is too
143 messy for Bison to handle straightforwardly.
144* Debugging:: Debugging Bison parsers that parse wrong.
145* Invocation:: How to run Bison (to produce the parser source file).
146* Table of Symbols:: All the keywords of the Bison language are explained.
147* Glossary:: Basic concepts are explained.
148* Index:: Cross-references to the text.
149
150 --- The Detailed Node Listing ---
151
152The Concepts of Bison
153
154* Language and Grammar:: Languages and context-free grammars,
155 as mathematical ideas.
156* Grammar in Bison:: How we represent grammars for Bison's sake.
157* Semantic Values:: Each token or syntactic grouping can have
158 a semantic value (the value of an integer,
159 the name of an identifier, etc.).
160* Semantic Actions:: Each rule can have an action containing C code.
161* Bison Parser:: What are Bison's input and output,
162 how is the output used?
163* Stages:: Stages in writing and running Bison grammars.
164* Grammar Layout:: Overall structure of a Bison grammar file.
165
166Examples
167
168* RPN Calc:: Reverse polish notation calculator;
169 a first example with no operator precedence.
170* Infix Calc:: Infix (algebraic) notation calculator.
171 Operator precedence is introduced.
172* Simple Error Recovery:: Continuing after syntax errors.
173* Multi-function Calc:: Calculator with memory and trig functions.
174 It uses multiple data-types for semantic values.
175* Exercises:: Ideas for improving the multi-function calculator.
176
177Reverse Polish Notation Calculator
178
179* Decls: Rpcalc Decls. Bison and C declarations for rpcalc.
180* Rules: Rpcalc Rules. Grammar Rules for rpcalc, with explanation.
181* Lexer: Rpcalc Lexer. The lexical analyzer.
182* Main: Rpcalc Main. The controlling function.
183* Error: Rpcalc Error. The error reporting function.
184* Gen: Rpcalc Gen. Running Bison on the grammar file.
185* Comp: Rpcalc Compile. Run the C compiler on the output code.
186
187Grammar Rules for @code{rpcalc}
188
189* Rpcalc Input::
190* Rpcalc Line::
191* Rpcalc Expr::
192
193Multi-Function Calculator: @code{mfcalc}
194
195* Decl: Mfcalc Decl. Bison declarations for multi-function calculator.
196* Rules: Mfcalc Rules. Grammar rules for the calculator.
197* Symtab: Mfcalc Symtab. Symbol table management subroutines.
198
199Bison Grammar Files
200
201* Grammar Outline:: Overall layout of the grammar file.
202* Symbols:: Terminal and nonterminal symbols.
203* Rules:: How to write grammar rules.
204* Recursion:: Writing recursive rules.
205* Semantics:: Semantic values and actions.
206* Declarations:: All kinds of Bison declarations are described here.
207* Multiple Parsers:: Putting more than one Bison parser in one program.
208
209Outline of a Bison Grammar
210
211* C Declarations:: Syntax and usage of the C declarations section.
212* Bison Declarations:: Syntax and usage of the Bison declarations section.
213* Grammar Rules:: Syntax and usage of the grammar rules section.
214* C Code:: Syntax and usage of the additional C code section.
215
216Defining Language Semantics
217
218* Value Type:: Specifying one data type for all semantic values.
219* Multiple Types:: Specifying several alternative data types.
220* Actions:: An action is the semantic definition of a grammar rule.
221* Action Types:: Specifying data types for actions to operate on.
222* Mid-Rule Actions:: Most actions go at the end of a rule.
223 This says when, why and how to use the exceptional
224 action in the middle of a rule.
225
226Bison Declarations
227
228* Token Decl:: Declaring terminal symbols.
229* Precedence Decl:: Declaring terminals with precedence and associativity.
230* Union Decl:: Declaring the set of all semantic value types.
231* Type Decl:: Declaring the choice of type for a nonterminal symbol.
232* Expect Decl:: Suppressing warnings about shift/reduce conflicts.
233* Start Decl:: Specifying the start symbol.
234* Pure Decl:: Requesting a reentrant parser.
235* Decl Summary:: Table of all Bison declarations.
236
237Parser C-Language Interface
238
239* Parser Function:: How to call @code{yyparse} and what it returns.
240* Lexical:: You must supply a function @code{yylex}
241 which reads tokens.
242* Error Reporting:: You must supply a function @code{yyerror}.
243* Action Features:: Special features for use in actions.
244
245The Lexical Analyzer Function @code{yylex}
246
247* Calling Convention:: How @code{yyparse} calls @code{yylex}.
248* Token Values:: How @code{yylex} must return the semantic value
249 of the token it has read.
250* Token Positions:: How @code{yylex} must return the text position
251 (line number, etc.) of the token, if the
252 actions want that.
253* Pure Calling:: How the calling convention differs
254 in a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}).
255
256The Bison Parser Algorithm
257
258* Look-Ahead:: Parser looks one token ahead when deciding what to do.
259* Shift/Reduce:: Conflicts: when either shifting or reduction is valid.
260* Precedence:: Operator precedence works by resolving conflicts.
261* Contextual Precedence:: When an operator's precedence depends on context.
262* Parser States:: The parser is a finite-state-machine with stack.
263* Reduce/Reduce:: When two rules are applicable in the same situation.
264* Mystery Conflicts:: Reduce/reduce conflicts that look unjustified.
265* Stack Overflow:: What happens when stack gets full. How to avoid it.
266
267Operator Precedence
268
269* Why Precedence:: An example showing why precedence is needed.
270* Using Precedence:: How to specify precedence in Bison grammars.
271* Precedence Examples:: How these features are used in the previous example.
272* How Precedence:: How they work.
273
274Handling Context Dependencies
275
276* Semantic Tokens:: Token parsing can depend on the semantic context.
277* Lexical Tie-ins:: Token parsing can depend on the syntactic context.
278* Tie-in Recovery:: Lexical tie-ins have implications for how
279 error recovery rules must be written.
280
281Invoking Bison
282
283* Bison Options:: All the options described in detail,
284 in alphabetical order by short options.
285* Option Cross Key:: Alphabetical list of long options.
286* VMS Invocation:: Bison command syntax on VMS.
287@end menu
288
289@node Introduction, Conditions, Top, Top
290@unnumbered Introduction
291@cindex introduction
292
293@dfn{Bison} is a general-purpose parser generator that converts a
294grammar description for an LALR(1) context-free grammar into a C
295program to parse that grammar. Once you are proficient with Bison,
296you may use it to develop a wide range of language parsers, from those
297used in simple desk calculators to complex programming languages.
298
299Bison is upward compatible with Yacc: all properly-written Yacc grammars
300ought to work with Bison with no change. Anyone familiar with Yacc
301should be able to use Bison with little trouble. You need to be fluent in
302C programming in order to use Bison or to understand this manual.
303
304We begin with tutorial chapters that explain the basic concepts of using
305Bison and show three explained examples, each building on the last. If you
306don't know Bison or Yacc, start by reading these chapters. Reference
307chapters follow which describe specific aspects of Bison in detail.
308
309Bison was written primarily by Robert Corbett; Richard Stallman made it
310Yacc-compatible. Wilfred Hansen of Carnegie Mellon University added
311multicharacter string literals and other features.
312
313This edition corresponds to version 1.25 of Bison.
314
315@node Conditions, Copying, Introduction, Top
316@unnumbered Conditions for Using Bison
317
318As of Bison version 1.24, we have changed the distribution terms for
319@code{yyparse} to permit using Bison's output in non-free programs.
320Formerly, Bison parsers could be used only in programs that were free
321software.
322
323The other GNU programming tools, such as the GNU C compiler, have never
324had such a requirement. They could always be used for non-free
325software. The reason Bison was different was not due to a special
326policy decision; it resulted from applying the usual General Public
327License to all of the Bison source code.
328
329The output of the Bison utility---the Bison parser file---contains a
330verbatim copy of a sizable piece of Bison, which is the code for the
331@code{yyparse} function. (The actions from your grammar are inserted
332into this function at one point, but the rest of the function is not
333changed.) When we applied the GPL terms to the code for @code{yyparse},
334the effect was to restrict the use of Bison output to free software.
335
336We didn't change the terms because of sympathy for people who want to
337make software proprietary. @strong{Software should be free.} But we
338concluded that limiting Bison's use to free software was doing little to
339encourage people to make other software free. So we decided to make the
340practical conditions for using Bison match the practical conditions for
341using the other GNU tools.
342
343@node Copying, Concepts, Conditions, Top
344@unnumbered GNU GENERAL PUBLIC LICENSE
345@center Version 2, June 1991
346
347@display
348Copyright @copyright{} 1989, 1991 Free Software Foundation, Inc.
349675 Mass Ave, Cambridge, MA 02139, USA
350
351Everyone is permitted to copy and distribute verbatim copies
352of this license document, but changing it is not allowed.
353@end display
354
355@unnumberedsec Preamble
356
357 The licenses for most software are designed to take away your
358freedom to share and change it. By contrast, the GNU General Public
359License is intended to guarantee your freedom to share and change free
360software---to make sure the software is free for all its users. This
361General Public License applies to most of the Free Software
362Foundation's software and to any other program whose authors commit to
363using it. (Some other Free Software Foundation software is covered by
364the GNU Library General Public License instead.) You can apply it to
365your programs, too.
366
367 When we speak of free software, we are referring to freedom, not
368price. Our General Public Licenses are designed to make sure that you
369have the freedom to distribute copies of free software (and charge for
370this service if you wish), that you receive source code or can get it
371if you want it, that you can change the software or use pieces of it
372in new free programs; and that you know you can do these things.
373
374 To protect your rights, we need to make restrictions that forbid
375anyone to deny you these rights or to ask you to surrender the rights.
376These restrictions translate to certain responsibilities for you if you
377distribute copies of the software, or if you modify it.
378
379 For example, if you distribute copies of such a program, whether
380gratis or for a fee, you must give the recipients all the rights that
381you have. You must make sure that they, too, receive or can get the
382source code. And you must show them these terms so they know their
383rights.
384
385 We protect your rights with two steps: (1) copyright the software, and
386(2) offer you this license which gives you legal permission to copy,
387distribute and/or modify the software.
388
389 Also, for each author's protection and ours, we want to make certain
390that everyone understands that there is no warranty for this free
391software. If the software is modified by someone else and passed on, we
392want its recipients to know that what they have is not the original, so
393that any problems introduced by others will not reflect on the original
394authors' reputations.
395
396 Finally, any free program is threatened constantly by software
397patents. We wish to avoid the danger that redistributors of a free
398program will individually obtain patent licenses, in effect making the
399program proprietary. To prevent this, we have made it clear that any
400patent must be licensed for everyone's free use or not licensed at all.
401
402 The precise terms and conditions for copying, distribution and
403modification follow.
404
405@iftex
406@unnumberedsec TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
407@end iftex
408@ifinfo
409@center TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
410@end ifinfo
411
412@enumerate 0
413@item
414This License applies to any program or other work which contains
415a notice placed by the copyright holder saying it may be distributed
416under the terms of this General Public License. The ``Program'', below,
417refers to any such program or work, and a ``work based on the Program''
418means either the Program or any derivative work under copyright law:
419that is to say, a work containing the Program or a portion of it,
420either verbatim or with modifications and/or translated into another
421language. (Hereinafter, translation is included without limitation in
422the term ``modification''.) Each licensee is addressed as ``you''.
423
424Activities other than copying, distribution and modification are not
425covered by this License; they are outside its scope. The act of
426running the Program is not restricted, and the output from the Program
427is covered only if its contents constitute a work based on the
428Program (independent of having been made by running the Program).
429Whether that is true depends on what the Program does.
430
431@item
432You may copy and distribute verbatim copies of the Program's
433source code as you receive it, in any medium, provided that you
434conspicuously and appropriately publish on each copy an appropriate
435copyright notice and disclaimer of warranty; keep intact all the
436notices that refer to this License and to the absence of any warranty;
437and give any other recipients of the Program a copy of this License
438along with the Program.
439
440You may charge a fee for the physical act of transferring a copy, and
441you may at your option offer warranty protection in exchange for a fee.
442
443@item
444You may modify your copy or copies of the Program or any portion
445of it, thus forming a work based on the Program, and copy and
446distribute such modifications or work under the terms of Section 1
447above, provided that you also meet all of these conditions:
448
449@enumerate a
450@item
451You must cause the modified files to carry prominent notices
452stating that you changed the files and the date of any change.
453
454@item
455You must cause any work that you distribute or publish, that in
456whole or in part contains or is derived from the Program or any
457part thereof, to be licensed as a whole at no charge to all third
458parties under the terms of this License.
459
460@item
461If the modified program normally reads commands interactively
462when run, you must cause it, when started running for such
463interactive use in the most ordinary way, to print or display an
464announcement including an appropriate copyright notice and a
465notice that there is no warranty (or else, saying that you provide
466a warranty) and that users may redistribute the program under
467these conditions, and telling the user how to view a copy of this
468License. (Exception: if the Program itself is interactive but
469does not normally print such an announcement, your work based on
470the Program is not required to print an announcement.)
471@end enumerate
472
473These requirements apply to the modified work as a whole. If
474identifiable sections of that work are not derived from the Program,
475and can be reasonably considered independent and separate works in
476themselves, then this License, and its terms, do not apply to those
477sections when you distribute them as separate works. But when you
478distribute the same sections as part of a whole which is a work based
479on the Program, the distribution of the whole must be on the terms of
480this License, whose permissions for other licensees extend to the
481entire whole, and thus to each and every part regardless of who wrote it.
482
483Thus, it is not the intent of this section to claim rights or contest
484your rights to work written entirely by you; rather, the intent is to
485exercise the right to control the distribution of derivative or
486collective works based on the Program.
487
488In addition, mere aggregation of another work not based on the Program
489with the Program (or with a work based on the Program) on a volume of
490a storage or distribution medium does not bring the other work under
491the scope of this License.
492
493@item
494You may copy and distribute the Program (or a work based on it,
495under Section 2) in object code or executable form under the terms of
496Sections 1 and 2 above provided that you also do one of the following:
497
498@enumerate a
499@item
500Accompany it with the complete corresponding machine-readable
501source code, which must be distributed under the terms of Sections
5021 and 2 above on a medium customarily used for software interchange; or,
503
504@item
505Accompany it with a written offer, valid for at least three
506years, to give any third party, for a charge no more than your
507cost of physically performing source distribution, a complete
508machine-readable copy of the corresponding source code, to be
509distributed under the terms of Sections 1 and 2 above on a medium
510customarily used for software interchange; or,
511
512@item
513Accompany it with the information you received as to the offer
514to distribute corresponding source code. (This alternative is
515allowed only for noncommercial distribution and only if you
516received the program in object code or executable form with such
517an offer, in accord with Subsection b above.)
518@end enumerate
519
520The source code for a work means the preferred form of the work for
521making modifications to it. For an executable work, complete source
522code means all the source code for all modules it contains, plus any
523associated interface definition files, plus the scripts used to
524control compilation and installation of the executable. However, as a
525special exception, the source code distributed need not include
526anything that is normally distributed (in either source or binary
527form) with the major components (compiler, kernel, and so on) of the
528operating system on which the executable runs, unless that component
529itself accompanies the executable.
530
531If distribution of executable or object code is made by offering
532access to copy from a designated place, then offering equivalent
533access to copy the source code from the same place counts as
534distribution of the source code, even though third parties are not
535compelled to copy the source along with the object code.
536
537@item
538You may not copy, modify, sublicense, or distribute the Program
539except as expressly provided under this License. Any attempt
540otherwise to copy, modify, sublicense or distribute the Program is
541void, and will automatically terminate your rights under this License.
542However, parties who have received copies, or rights, from you under
543this License will not have their licenses terminated so long as such
544parties remain in full compliance.
545
546@item
547You are not required to accept this License, since you have not
548signed it. However, nothing else grants you permission to modify or
549distribute the Program or its derivative works. These actions are
550prohibited by law if you do not accept this License. Therefore, by
551modifying or distributing the Program (or any work based on the
552Program), you indicate your acceptance of this License to do so, and
553all its terms and conditions for copying, distributing or modifying
554the Program or works based on it.
555
556@item
557Each time you redistribute the Program (or any work based on the
558Program), the recipient automatically receives a license from the
559original licensor to copy, distribute or modify the Program subject to
560these terms and conditions. You may not impose any further
561restrictions on the recipients' exercise of the rights granted herein.
562You are not responsible for enforcing compliance by third parties to
563this License.
564
565@item
566If, as a consequence of a court judgment or allegation of patent
567infringement or for any other reason (not limited to patent issues),
568conditions are imposed on you (whether by court order, agreement or
569otherwise) that contradict the conditions of this License, they do not
570excuse you from the conditions of this License. If you cannot
571distribute so as to satisfy simultaneously your obligations under this
572License and any other pertinent obligations, then as a consequence you
573may not distribute the Program at all. For example, if a patent
574license would not permit royalty-free redistribution of the Program by
575all those who receive copies directly or indirectly through you, then
576the only way you could satisfy both it and this License would be to
577refrain entirely from distribution of the Program.
578
579If any portion of this section is held invalid or unenforceable under
580any particular circumstance, the balance of the section is intended to
581apply and the section as a whole is intended to apply in other
582circumstances.
583
584It is not the purpose of this section to induce you to infringe any
585patents or other property right claims or to contest validity of any
586such claims; this section has the sole purpose of protecting the
587integrity of the free software distribution system, which is
588implemented by public license practices. Many people have made
589generous contributions to the wide range of software distributed
590through that system in reliance on consistent application of that
591system; it is up to the author/donor to decide if he or she is willing
592to distribute software through any other system and a licensee cannot
593impose that choice.
594
595This section is intended to make thoroughly clear what is believed to
596be a consequence of the rest of this License.
597
598@item
599If the distribution and/or use of the Program is restricted in
600certain countries either by patents or by copyrighted interfaces, the
601original copyright holder who places the Program under this License
602may add an explicit geographical distribution limitation excluding
603those countries, so that distribution is permitted only in or among
604countries not thus excluded. In such case, this License incorporates
605the limitation as if written in the body of this License.
606
607@item
608The Free Software Foundation may publish revised and/or new versions
609of the General Public License from time to time. Such new versions will
610be similar in spirit to the present version, but may differ in detail to
611address new problems or concerns.
612
613Each version is given a distinguishing version number. If the Program
614specifies a version number of this License which applies to it and ``any
615later version'', you have the option of following the terms and conditions
616either of that version or of any later version published by the Free
617Software Foundation. If the Program does not specify a version number of
618this License, you may choose any version ever published by the Free Software
619Foundation.
620
621@item
622If you wish to incorporate parts of the Program into other free
623programs whose distribution conditions are different, write to the author
624to ask for permission. For software which is copyrighted by the Free
625Software Foundation, write to the Free Software Foundation; we sometimes
626make exceptions for this. Our decision will be guided by the two goals
627of preserving the free status of all derivatives of our free software and
628of promoting the sharing and reuse of software generally.
629
630@iftex
631@heading NO WARRANTY
632@end iftex
633@ifinfo
634@center NO WARRANTY
635@end ifinfo
636
637@item
638BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
639FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN
640OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
641PROVIDE THE PROGRAM ``AS IS'' WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
642OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
643MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS
644TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE
645PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
646REPAIR OR CORRECTION.
647
648@item
649IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
650WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
651REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
652INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
653OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
654TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
655YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
656PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
657POSSIBILITY OF SUCH DAMAGES.
658@end enumerate
659
660@iftex
661@heading END OF TERMS AND CONDITIONS
662@end iftex
663@ifinfo
664@center END OF TERMS AND CONDITIONS
665@end ifinfo
666
667@page
668@unnumberedsec How to Apply These Terms to Your New Programs
669
670 If you develop a new program, and you want it to be of the greatest
671possible use to the public, the best way to achieve this is to make it
672free software which everyone can redistribute and change under these terms.
673
674 To do so, attach the following notices to the program. It is safest
675to attach them to the start of each source file to most effectively
676convey the exclusion of warranty; and each file should have at least
677the ``copyright'' line and a pointer to where the full notice is found.
678
679@smallexample
680@var{one line to give the program's name and a brief idea of what it does.}
681Copyright (C) 19@var{yy} @var{name of author}
682
683This program is free software; you can redistribute it and/or modify
684it under the terms of the GNU General Public License as published by
685the Free Software Foundation; either version 2 of the License, or
686(at your option) any later version.
687
688This program is distributed in the hope that it will be useful,
689but WITHOUT ANY WARRANTY; without even the implied warranty of
690MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
691GNU General Public License for more details.
692
693You should have received a copy of the GNU General Public License
694along with this program; if not, write to the Free Software
695Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
696@end smallexample
697
698Also add information on how to contact you by electronic and paper mail.
699
700If the program is interactive, make it output a short notice like this
701when it starts in an interactive mode:
702
703@smallexample
704Gnomovision version 69, Copyright (C) 19@var{yy} @var{name of author}
705Gnomovision comes with ABSOLUTELY NO WARRANTY; for details
706type `show w'.
707This is free software, and you are welcome to redistribute it
708under certain conditions; type `show c' for details.
709@end smallexample
710
711The hypothetical commands @samp{show w} and @samp{show c} should show
712the appropriate parts of the General Public License. Of course, the
713commands you use may be called something other than @samp{show w} and
714@samp{show c}; they could even be mouse-clicks or menu items---whatever
715suits your program.
716
717You should also get your employer (if you work as a programmer) or your
718school, if any, to sign a ``copyright disclaimer'' for the program, if
719necessary. Here is a sample; alter the names:
720
721@smallexample
722Yoyodyne, Inc., hereby disclaims all copyright interest in the program
723`Gnomovision' (which makes passes at compilers) written by James Hacker.
724
725@var{signature of Ty Coon}, 1 April 1989
726Ty Coon, President of Vice
727@end smallexample
728
729This General Public License does not permit incorporating your program into
730proprietary programs. If your program is a subroutine library, you may
731consider it more useful to permit linking proprietary applications with the
732library. If this is what you want to do, use the GNU Library General
733Public License instead of this License.
734
735@node Concepts, Examples, Copying, Top
736@chapter The Concepts of Bison
737
738This chapter introduces many of the basic concepts without which the
739details of Bison will not make sense. If you do not already know how to
740use Bison or Yacc, we suggest you start by reading this chapter carefully.
741
742@menu
743* Language and Grammar:: Languages and context-free grammars,
744 as mathematical ideas.
745* Grammar in Bison:: How we represent grammars for Bison's sake.
746* Semantic Values:: Each token or syntactic grouping can have
747 a semantic value (the value of an integer,
748 the name of an identifier, etc.).
749* Semantic Actions:: Each rule can have an action containing C code.
750* Bison Parser:: What are Bison's input and output,
751 how is the output used?
752* Stages:: Stages in writing and running Bison grammars.
753* Grammar Layout:: Overall structure of a Bison grammar file.
754@end menu
755
756@node Language and Grammar, Grammar in Bison, , Concepts
757@section Languages and Context-Free Grammars
758
759@cindex context-free grammar
760@cindex grammar, context-free
761In order for Bison to parse a language, it must be described by a
762@dfn{context-free grammar}. This means that you specify one or more
763@dfn{syntactic groupings} and give rules for constructing them from their
764parts. For example, in the C language, one kind of grouping is called an
765`expression'. One rule for making an expression might be, ``An expression
766can be made of a minus sign and another expression''. Another would be,
767``An expression can be an integer''. As you can see, rules are often
768recursive, but there must be at least one rule which leads out of the
769recursion.
770
771@cindex BNF
772@cindex Backus-Naur form
773The most common formal system for presenting such rules for humans to read
774is @dfn{Backus-Naur Form} or ``BNF'', which was developed in order to
775specify the language Algol 60. Any grammar expressed in BNF is a
776context-free grammar. The input to Bison is essentially machine-readable
777BNF.
778
779Not all context-free languages can be handled by Bison, only those
780that are LALR(1). In brief, this means that it must be possible to
781tell how to parse any portion of an input string with just a single
782token of look-ahead. Strictly speaking, that is a description of an
783LR(1) grammar, and LALR(1) involves additional restrictions that are
784hard to explain simply; but it is rare in actual practice to find an
785LR(1) grammar that fails to be LALR(1). @xref{Mystery Conflicts, ,
786Mysterious Reduce/Reduce Conflicts}, for more information on this.
787
788@cindex symbols (abstract)
789@cindex token
790@cindex syntactic grouping
791@cindex grouping, syntactic
792In the formal grammatical rules for a language, each kind of syntactic unit
793or grouping is named by a @dfn{symbol}. Those which are built by grouping
794smaller constructs according to grammatical rules are called
795@dfn{nonterminal symbols}; those which can't be subdivided are called
796@dfn{terminal symbols} or @dfn{token types}. We call a piece of input
797corresponding to a single terminal symbol a @dfn{token}, and a piece
798corresponding to a single nonterminal symbol a @dfn{grouping}.@refill
799
800We can use the C language as an example of what symbols, terminal and
801nonterminal, mean. The tokens of C are identifiers, constants (numeric and
802string), and the various keywords, arithmetic operators and punctuation
803marks. So the terminal symbols of a grammar for C include `identifier',
804`number', `string', plus one symbol for each keyword, operator or
805punctuation mark: `if', `return', `const', `static', `int', `char',
806`plus-sign', `open-brace', `close-brace', `comma' and many more. (These
807tokens can be subdivided into characters, but that is a matter of
808lexicography, not grammar.)
809
810Here is a simple C function subdivided into tokens:
811
812@example
813int /* @r{keyword `int'} */
814square (x) /* @r{identifier, open-paren,} */
815 /* @r{identifier, close-paren} */
816 int x; /* @r{keyword `int', identifier, semicolon} */
817@{ /* @r{open-brace} */
818 return x * x; /* @r{keyword `return', identifier,} */
819 /* @r{asterisk, identifier, semicolon} */
820@} /* @r{close-brace} */
821@end example
822
823The syntactic groupings of C include the expression, the statement, the
824declaration, and the function definition. These are represented in the
825grammar of C by nonterminal symbols `expression', `statement',
826`declaration' and `function definition'. The full grammar uses dozens of
827additional language constructs, each with its own nonterminal symbol, in
828order to express the meanings of these four. The example above is a
829function definition; it contains one declaration, and one statement. In
830the statement, each @samp{x} is an expression and so is @samp{x * x}.
831
832Each nonterminal symbol must have grammatical rules showing how it is made
833out of simpler constructs. For example, one kind of C statement is the
834@code{return} statement; this would be described with a grammar rule which
835reads informally as follows:
836
837@quotation
838A `statement' can be made of a `return' keyword, an `expression' and a
839`semicolon'.
840@end quotation
841
842@noindent
843There would be many other rules for `statement', one for each kind of
844statement in C.
845
846@cindex start symbol
847One nonterminal symbol must be distinguished as the special one which
848defines a complete utterance in the language. It is called the @dfn{start
849symbol}. In a compiler, this means a complete input program. In the C
850language, the nonterminal symbol `sequence of definitions and declarations'
851plays this role.
852
853For example, @samp{1 + 2} is a valid C expression---a valid part of a C
854program---but it is not valid as an @emph{entire} C program. In the
855context-free grammar of C, this follows from the fact that `expression' is
856not the start symbol.
857
858The Bison parser reads a sequence of tokens as its input, and groups the
859tokens using the grammar rules. If the input is valid, the end result is
860that the entire token sequence reduces to a single grouping whose symbol is
861the grammar's start symbol. If we use a grammar for C, the entire input
862must be a `sequence of definitions and declarations'. If not, the parser
863reports a syntax error.
864
865@node Grammar in Bison, Semantic Values, Language and Grammar, Concepts
866@section From Formal Rules to Bison Input
867@cindex Bison grammar
868@cindex grammar, Bison
869@cindex formal grammar
870
871A formal grammar is a mathematical construct. To define the language
872for Bison, you must write a file expressing the grammar in Bison syntax:
873a @dfn{Bison grammar} file. @xref{Grammar File, ,Bison Grammar Files}.
874
875A nonterminal symbol in the formal grammar is represented in Bison input
876as an identifier, like an identifier in C. By convention, it should be
877in lower case, such as @code{expr}, @code{stmt} or @code{declaration}.
878
879The Bison representation for a terminal symbol is also called a @dfn{token
880type}. Token types as well can be represented as C-like identifiers. By
881convention, these identifiers should be upper case to distinguish them from
882nonterminals: for example, @code{INTEGER}, @code{IDENTIFIER}, @code{IF} or
883@code{RETURN}. A terminal symbol that stands for a particular keyword in
884the language should be named after that keyword converted to upper case.
885The terminal symbol @code{error} is reserved for error recovery.
886@xref{Symbols}.
887
888A terminal symbol can also be represented as a character literal, just like
889a C character constant. You should do this whenever a token is just a
890single character (parenthesis, plus-sign, etc.): use that same character in
891a literal as the terminal symbol for that token.
892
893A third way to represent a terminal symbol is with a C string constant
894containing several characters. @xref{Symbols}, for more information.
895
896The grammar rules also have an expression in Bison syntax. For example,
897here is the Bison rule for a C @code{return} statement. The semicolon in
898quotes is a literal character token, representing part of the C syntax for
899the statement; the naked semicolon, and the colon, are Bison punctuation
900used in every rule.
901
902@example
903stmt: RETURN expr ';'
904 ;
905@end example
906
907@noindent
908@xref{Rules, ,Syntax of Grammar Rules}.
909
910@node Semantic Values, Semantic Actions, Grammar in Bison, Concepts
911@section Semantic Values
912@cindex semantic value
913@cindex value, semantic
914
915A formal grammar selects tokens only by their classifications: for example,
916if a rule mentions the terminal symbol `integer constant', it means that
917@emph{any} integer constant is grammatically valid in that position. The
918precise value of the constant is irrelevant to how to parse the input: if
919@samp{x+4} is grammatical then @samp{x+1} or @samp{x+3989} is equally
920grammatical.@refill
921
922But the precise value is very important for what the input means once it is
923parsed. A compiler is useless if it fails to distinguish between 4, 1 and
9243989 as constants in the program! Therefore, each token in a Bison grammar
925has both a token type and a @dfn{semantic value}. @xref{Semantics, ,Defining Language Semantics},
926for details.
927
928The token type is a terminal symbol defined in the grammar, such as
929@code{INTEGER}, @code{IDENTIFIER} or @code{','}. It tells everything
930you need to know to decide where the token may validly appear and how to
931group it with other tokens. The grammar rules know nothing about tokens
932except their types.@refill
933
934The semantic value has all the rest of the information about the
935meaning of the token, such as the value of an integer, or the name of an
936identifier. (A token such as @code{','} which is just punctuation doesn't
937need to have any semantic value.)
938
939For example, an input token might be classified as token type
940@code{INTEGER} and have the semantic value 4. Another input token might
941have the same token type @code{INTEGER} but value 3989. When a grammar
942rule says that @code{INTEGER} is allowed, either of these tokens is
943acceptable because each is an @code{INTEGER}. When the parser accepts the
944token, it keeps track of the token's semantic value.
945
946Each grouping can also have a semantic value as well as its nonterminal
947symbol. For example, in a calculator, an expression typically has a
948semantic value that is a number. In a compiler for a programming
949language, an expression typically has a semantic value that is a tree
950structure describing the meaning of the expression.
951
952@node Semantic Actions, Bison Parser, Semantic Values, Concepts
953@section Semantic Actions
954@cindex semantic actions
955@cindex actions, semantic
956
957In order to be useful, a program must do more than parse input; it must
958also produce some output based on the input. In a Bison grammar, a grammar
959rule can have an @dfn{action} made up of C statements. Each time the
960parser recognizes a match for that rule, the action is executed.
961@xref{Actions}.
962
963Most of the time, the purpose of an action is to compute the semantic value
964of the whole construct from the semantic values of its parts. For example,
965suppose we have a rule which says an expression can be the sum of two
966expressions. When the parser recognizes such a sum, each of the
967subexpressions has a semantic value which describes how it was built up.
968The action for this rule should create a similar sort of value for the
969newly recognized larger expression.
970
971For example, here is a rule that says an expression can be the sum of
972two subexpressions:
973
974@example
975expr: expr '+' expr @{ $$ = $1 + $3; @}
976 ;
977@end example
978
979@noindent
980The action says how to produce the semantic value of the sum expression
981from the values of the two subexpressions.
982
983@node Bison Parser, Stages, Semantic Actions, Concepts
984@section Bison Output: the Parser File
985@cindex Bison parser
986@cindex Bison utility
987@cindex lexical analyzer, purpose
988@cindex parser
989
990When you run Bison, you give it a Bison grammar file as input. The output
991is a C source file that parses the language described by the grammar.
992This file is called a @dfn{Bison parser}. Keep in mind that the Bison
993utility and the Bison parser are two distinct programs: the Bison utility
994is a program whose output is the Bison parser that becomes part of your
995program.
996
997The job of the Bison parser is to group tokens into groupings according to
998the grammar rules---for example, to build identifiers and operators into
999expressions. As it does this, it runs the actions for the grammar rules it
1000uses.
1001
1002The tokens come from a function called the @dfn{lexical analyzer} that you
1003must supply in some fashion (such as by writing it in C). The Bison parser
1004calls the lexical analyzer each time it wants a new token. It doesn't know
1005what is ``inside'' the tokens (though their semantic values may reflect
1006this). Typically the lexical analyzer makes the tokens by parsing
1007characters of text, but Bison does not depend on this. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
1008
1009The Bison parser file is C code which defines a function named
1010@code{yyparse} which implements that grammar. This function does not make
1011a complete C program: you must supply some additional functions. One is
1012the lexical analyzer. Another is an error-reporting function which the
1013parser calls to report an error. In addition, a complete C program must
1014start with a function called @code{main}; you have to provide this, and
1015arrange for it to call @code{yyparse} or the parser will never run.
1016@xref{Interface, ,Parser C-Language Interface}.
1017
1018Aside from the token type names and the symbols in the actions you
1019write, all variable and function names used in the Bison parser file
1020begin with @samp{yy} or @samp{YY}. This includes interface functions
1021such as the lexical analyzer function @code{yylex}, the error reporting
1022function @code{yyerror} and the parser function @code{yyparse} itself.
1023This also includes numerous identifiers used for internal purposes.
1024Therefore, you should avoid using C identifiers starting with @samp{yy}
1025or @samp{YY} in the Bison grammar file except for the ones defined in
1026this manual.
1027
1028@node Stages, Grammar Layout, Bison Parser, Concepts
1029@section Stages in Using Bison
1030@cindex stages in using Bison
1031@cindex using Bison
1032
1033The actual language-design process using Bison, from grammar specification
1034to a working compiler or interpreter, has these parts:
1035
1036@enumerate
1037@item
1038Formally specify the grammar in a form recognized by Bison
1039(@pxref{Grammar File, ,Bison Grammar Files}). For each grammatical rule in the language,
1040describe the action that is to be taken when an instance of that rule
1041is recognized. The action is described by a sequence of C statements.
1042
1043@item
1044Write a lexical analyzer to process input and pass tokens to the
1045parser. The lexical analyzer may be written by hand in C
1046(@pxref{Lexical, ,The Lexical Analyzer Function @code{yylex}}). It could also be produced using Lex, but the use
1047of Lex is not discussed in this manual.
1048
1049@item
1050Write a controlling function that calls the Bison-produced parser.
1051
1052@item
1053Write error-reporting routines.
1054@end enumerate
1055
1056To turn this source code as written into a runnable program, you
1057must follow these steps:
1058
1059@enumerate
1060@item
1061Run Bison on the grammar to produce the parser.
1062
1063@item
1064Compile the code output by Bison, as well as any other source files.
1065
1066@item
1067Link the object files to produce the finished product.
1068@end enumerate
1069
1070@node Grammar Layout, , Stages, Concepts
1071@section The Overall Layout of a Bison Grammar
1072@cindex grammar file
1073@cindex file format
1074@cindex format of grammar file
1075@cindex layout of Bison grammar
1076
1077The input file for the Bison utility is a @dfn{Bison grammar file}. The
1078general form of a Bison grammar file is as follows:
1079
1080@example
1081%@{
1082@var{C declarations}
1083%@}
1084
1085@var{Bison declarations}
1086
1087%%
1088@var{Grammar rules}
1089%%
1090@var{Additional C code}
1091@end example
1092
1093@noindent
1094The @samp{%%}, @samp{%@{} and @samp{%@}} are punctuation that appears
1095in every Bison grammar file to separate the sections.
1096
1097The C declarations may define types and variables used in the actions.
1098You can also use preprocessor commands to define macros used there, and use
1099@code{#include} to include header files that do any of these things.
1100
1101The Bison declarations declare the names of the terminal and nonterminal
1102symbols, and may also describe operator precedence and the data types of
1103semantic values of various symbols.
1104
1105The grammar rules define how to construct each nonterminal symbol from its
1106parts.
1107
1108The additional C code can contain any C code you want to use. Often the
1109definition of the lexical analyzer @code{yylex} goes here, plus subroutines
1110called by the actions in the grammar rules. In a simple program, all the
1111rest of the program can go here.
1112
1113@node Examples, Grammar File, Concepts, Top
1114@chapter Examples
1115@cindex simple examples
1116@cindex examples, simple
1117
1118Now we show and explain three sample programs written using Bison: a
1119reverse polish notation calculator, an algebraic (infix) notation
1120calculator, and a multi-function calculator. All three have been tested
1121under BSD Unix 4.3; each produces a usable, though limited, interactive
1122desk-top calculator.
1123
1124These examples are simple, but Bison grammars for real programming
1125languages are written the same way.
1126@ifinfo
1127You can copy these examples out of the Info file and into a source file
1128to try them.
1129@end ifinfo
1130
1131@menu
1132* RPN Calc:: Reverse polish notation calculator;
1133 a first example with no operator precedence.
1134* Infix Calc:: Infix (algebraic) notation calculator.
1135 Operator precedence is introduced.
1136* Simple Error Recovery:: Continuing after syntax errors.
1137* Multi-function Calc:: Calculator with memory and trig functions.
1138 It uses multiple data-types for semantic values.
1139* Exercises:: Ideas for improving the multi-function calculator.
1140@end menu
1141
1142@node RPN Calc, Infix Calc, , Examples
1143@section Reverse Polish Notation Calculator
1144@cindex reverse polish notation
1145@cindex polish notation calculator
1146@cindex @code{rpcalc}
1147@cindex calculator, simple
1148
1149The first example is that of a simple double-precision @dfn{reverse polish
1150notation} calculator (a calculator using postfix operators). This example
1151provides a good starting point, since operator precedence is not an issue.
1152The second example will illustrate how operator precedence is handled.
1153
1154The source code for this calculator is named @file{rpcalc.y}. The
1155@samp{.y} extension is a convention used for Bison input files.
1156
1157@menu
1158* Decls: Rpcalc Decls. Bison and C declarations for rpcalc.
1159* Rules: Rpcalc Rules. Grammar Rules for rpcalc, with explanation.
1160* Lexer: Rpcalc Lexer. The lexical analyzer.
1161* Main: Rpcalc Main. The controlling function.
1162* Error: Rpcalc Error. The error reporting function.
1163* Gen: Rpcalc Gen. Running Bison on the grammar file.
1164* Comp: Rpcalc Compile. Run the C compiler on the output code.
1165@end menu
1166
1167@node Rpcalc Decls, Rpcalc Rules, , RPN Calc
1168@subsection Declarations for @code{rpcalc}
1169
1170Here are the C and Bison declarations for the reverse polish notation
1171calculator. As in C, comments are placed between @samp{/*@dots{}*/}.
1172
1173@example
1174/* Reverse polish notation calculator. */
1175
1176%@{
1177#define YYSTYPE double
1178#include <math.h>
1179%@}
1180
1181%token NUM
1182
1183%% /* Grammar rules and actions follow */
1184@end example
1185
1186The C declarations section (@pxref{C Declarations, ,The C Declarations Section}) contains two
1187preprocessor directives.
1188
1189The @code{#define} directive defines the macro @code{YYSTYPE}, thus
1190specifying the C data type for semantic values of both tokens and groupings
1191(@pxref{Value Type, ,Data Types of Semantic Values}). The Bison parser will use whatever type
1192@code{YYSTYPE} is defined as; if you don't define it, @code{int} is the
1193default. Because we specify @code{double}, each token and each expression
1194has an associated value, which is a floating point number.
1195
1196The @code{#include} directive is used to declare the exponentiation
1197function @code{pow}.
1198
1199The second section, Bison declarations, provides information to Bison about
1200the token types (@pxref{Bison Declarations, ,The Bison Declarations Section}). Each terminal symbol that is
1201not a single-character literal must be declared here. (Single-character
1202literals normally don't need to be declared.) In this example, all the
1203arithmetic operators are designated by single-character literals, so the
1204only terminal symbol that needs to be declared is @code{NUM}, the token
1205type for numeric constants.
1206
1207@node Rpcalc Rules, Rpcalc Lexer, Rpcalc Decls, RPN Calc
1208@subsection Grammar Rules for @code{rpcalc}
1209
1210Here are the grammar rules for the reverse polish notation calculator.
1211
1212@example
1213input: /* empty */
1214 | input line
1215;
1216
1217line: '\n'
1218 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1219;
1220
1221exp: NUM @{ $$ = $1; @}
1222 | exp exp '+' @{ $$ = $1 + $2; @}
1223 | exp exp '-' @{ $$ = $1 - $2; @}
1224 | exp exp '*' @{ $$ = $1 * $2; @}
1225 | exp exp '/' @{ $$ = $1 / $2; @}
1226 /* Exponentiation */
1227 | exp exp '^' @{ $$ = pow ($1, $2); @}
1228 /* Unary minus */
1229 | exp 'n' @{ $$ = -$1; @}
1230;
1231%%
1232@end example
1233
1234The groupings of the rpcalc ``language'' defined here are the expression
1235(given the name @code{exp}), the line of input (@code{line}), and the
1236complete input transcript (@code{input}). Each of these nonterminal
1237symbols has several alternate rules, joined by the @samp{|} punctuator
1238which is read as ``or''. The following sections explain what these rules
1239mean.
1240
1241The semantics of the language is determined by the actions taken when a
1242grouping is recognized. The actions are the C code that appears inside
1243braces. @xref{Actions}.
1244
1245You must specify these actions in C, but Bison provides the means for
1246passing semantic values between the rules. In each action, the
1247pseudo-variable @code{$$} stands for the semantic value for the grouping
1248that the rule is going to construct. Assigning a value to @code{$$} is the
1249main job of most actions. The semantic values of the components of the
1250rule are referred to as @code{$1}, @code{$2}, and so on.
1251
1252@menu
1253* Rpcalc Input::
1254* Rpcalc Line::
1255* Rpcalc Expr::
1256@end menu
1257
1258@node Rpcalc Input, Rpcalc Line, , Rpcalc Rules
1259@subsubsection Explanation of @code{input}
1260
1261Consider the definition of @code{input}:
1262
1263@example
1264input: /* empty */
1265 | input line
1266;
1267@end example
1268
1269This definition reads as follows: ``A complete input is either an empty
1270string, or a complete input followed by an input line''. Notice that
1271``complete input'' is defined in terms of itself. This definition is said
1272to be @dfn{left recursive} since @code{input} appears always as the
1273leftmost symbol in the sequence. @xref{Recursion, ,Recursive Rules}.
1274
1275The first alternative is empty because there are no symbols between the
1276colon and the first @samp{|}; this means that @code{input} can match an
1277empty string of input (no tokens). We write the rules this way because it
1278is legitimate to type @kbd{Ctrl-d} right after you start the calculator.
1279It's conventional to put an empty alternative first and write the comment
1280@samp{/* empty */} in it.
1281
1282The second alternate rule (@code{input line}) handles all nontrivial input.
1283It means, ``After reading any number of lines, read one more line if
1284possible.'' The left recursion makes this rule into a loop. Since the
1285first alternative matches empty input, the loop can be executed zero or
1286more times.
1287
1288The parser function @code{yyparse} continues to process input until a
1289grammatical error is seen or the lexical analyzer says there are no more
1290input tokens; we will arrange for the latter to happen at end of file.
1291
1292@node Rpcalc Line, Rpcalc Expr, Rpcalc Input, Rpcalc Rules
1293@subsubsection Explanation of @code{line}
1294
1295Now consider the definition of @code{line}:
1296
1297@example
1298line: '\n'
1299 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1300;
1301@end example
1302
1303The first alternative is a token which is a newline character; this means
1304that rpcalc accepts a blank line (and ignores it, since there is no
1305action). The second alternative is an expression followed by a newline.
1306This is the alternative that makes rpcalc useful. The semantic value of
1307the @code{exp} grouping is the value of @code{$1} because the @code{exp} in
1308question is the first symbol in the alternative. The action prints this
1309value, which is the result of the computation the user asked for.
1310
1311This action is unusual because it does not assign a value to @code{$$}. As
1312a consequence, the semantic value associated with the @code{line} is
1313uninitialized (its value will be unpredictable). This would be a bug if
1314that value were ever used, but we don't use it: once rpcalc has printed the
1315value of the user's input line, that value is no longer needed.
1316
1317@node Rpcalc Expr, , Rpcalc Line, Rpcalc Rules
1318@subsubsection Explanation of @code{expr}
1319
1320The @code{exp} grouping has several rules, one for each kind of expression.
1321The first rule handles the simplest expressions: those that are just numbers.
1322The second handles an addition-expression, which looks like two expressions
1323followed by a plus-sign. The third handles subtraction, and so on.
1324
1325@example
1326exp: NUM
1327 | exp exp '+' @{ $$ = $1 + $2; @}
1328 | exp exp '-' @{ $$ = $1 - $2; @}
1329 @dots{}
1330 ;
1331@end example
1332
1333We have used @samp{|} to join all the rules for @code{exp}, but we could
1334equally well have written them separately:
1335
1336@example
1337exp: NUM ;
1338exp: exp exp '+' @{ $$ = $1 + $2; @} ;
1339exp: exp exp '-' @{ $$ = $1 - $2; @} ;
1340 @dots{}
1341@end example
1342
1343Most of the rules have actions that compute the value of the expression in
1344terms of the value of its parts. For example, in the rule for addition,
1345@code{$1} refers to the first component @code{exp} and @code{$2} refers to
1346the second one. The third component, @code{'+'}, has no meaningful
1347associated semantic value, but if it had one you could refer to it as
1348@code{$3}. When @code{yyparse} recognizes a sum expression using this
1349rule, the sum of the two subexpressions' values is produced as the value of
1350the entire expression. @xref{Actions}.
1351
1352You don't have to give an action for every rule. When a rule has no
1353action, Bison by default copies the value of @code{$1} into @code{$$}.
1354This is what happens in the first rule (the one that uses @code{NUM}).
1355
1356The formatting shown here is the recommended convention, but Bison does
1357not require it. You can add or change whitespace as much as you wish.
1358For example, this:
1359
1360@example
1361exp : NUM | exp exp '+' @{$$ = $1 + $2; @} | @dots{}
1362@end example
1363
1364@noindent
1365means the same thing as this:
1366
1367@example
1368exp: NUM
1369 | exp exp '+' @{ $$ = $1 + $2; @}
1370 | @dots{}
1371@end example
1372
1373@noindent
1374The latter, however, is much more readable.
1375
1376@node Rpcalc Lexer, Rpcalc Main, Rpcalc Rules, RPN Calc
1377@subsection The @code{rpcalc} Lexical Analyzer
1378@cindex writing a lexical analyzer
1379@cindex lexical analyzer, writing
1380
1381The lexical analyzer's job is low-level parsing: converting characters or
1382sequences of characters into tokens. The Bison parser gets its tokens by
1383calling the lexical analyzer. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
1384
1385Only a simple lexical analyzer is needed for the RPN calculator. This
1386lexical analyzer skips blanks and tabs, then reads in numbers as
1387@code{double} and returns them as @code{NUM} tokens. Any other character
1388that isn't part of a number is a separate token. Note that the token-code
1389for such a single-character token is the character itself.
1390
1391The return value of the lexical analyzer function is a numeric code which
1392represents a token type. The same text used in Bison rules to stand for
1393this token type is also a C expression for the numeric code for the type.
1394This works in two ways. If the token type is a character literal, then its
1395numeric code is the ASCII code for that character; you can use the same
1396character literal in the lexical analyzer to express the number. If the
1397token type is an identifier, that identifier is defined by Bison as a C
1398macro whose definition is the appropriate number. In this example,
1399therefore, @code{NUM} becomes a macro for @code{yylex} to use.
1400
1401The semantic value of the token (if it has one) is stored into the global
1402variable @code{yylval}, which is where the Bison parser will look for it.
1403(The C data type of @code{yylval} is @code{YYSTYPE}, which was defined
1404at the beginning of the grammar; @pxref{Rpcalc Decls, ,Declarations for @code{rpcalc}}.)
1405
1406A token type code of zero is returned if the end-of-file is encountered.
1407(Bison recognizes any nonpositive value as indicating the end of the
1408input.)
1409
1410Here is the code for the lexical analyzer:
1411
1412@example
1413@group
1414/* Lexical analyzer returns a double floating point
1415 number on the stack and the token NUM, or the ASCII
1416 character read if not a number. Skips all blanks
1417 and tabs, returns 0 for EOF. */
1418
1419#include <ctype.h>
1420@end group
1421
1422@group
1423yylex ()
1424@{
1425 int c;
1426
1427 /* skip white space */
1428 while ((c = getchar ()) == ' ' || c == '\t')
1429 ;
1430@end group
1431@group
1432 /* process numbers */
1433 if (c == '.' || isdigit (c))
1434 @{
1435 ungetc (c, stdin);
1436 scanf ("%lf", &yylval);
1437 return NUM;
1438 @}
1439@end group
1440@group
1441 /* return end-of-file */
1442 if (c == EOF)
1443 return 0;
1444 /* return single chars */
1445 return c;
1446@}
1447@end group
1448@end example
1449
1450@node Rpcalc Main, Rpcalc Error, Rpcalc Lexer, RPN Calc
1451@subsection The Controlling Function
1452@cindex controlling function
1453@cindex main function in simple example
1454
1455In keeping with the spirit of this example, the controlling function is
1456kept to the bare minimum. The only requirement is that it call
1457@code{yyparse} to start the process of parsing.
1458
1459@example
1460@group
1461main ()
1462@{
1463 yyparse ();
1464@}
1465@end group
1466@end example
1467
1468@node Rpcalc Error, Rpcalc Gen, Rpcalc Main, RPN Calc
1469@subsection The Error Reporting Routine
1470@cindex error reporting routine
1471
1472When @code{yyparse} detects a syntax error, it calls the error reporting
1473function @code{yyerror} to print an error message (usually but not always
1474@code{"parse error"}). It is up to the programmer to supply @code{yyerror}
1475(@pxref{Interface, ,Parser C-Language Interface}), so here is the definition we will use:
1476
1477@example
1478@group
1479#include <stdio.h>
1480
1481yyerror (s) /* Called by yyparse on error */
1482 char *s;
1483@{
1484 printf ("%s\n", s);
1485@}
1486@end group
1487@end example
1488
1489After @code{yyerror} returns, the Bison parser may recover from the error
1490and continue parsing if the grammar contains a suitable error rule
1491(@pxref{Error Recovery}). Otherwise, @code{yyparse} returns nonzero. We
1492have not written any error rules in this example, so any invalid input will
1493cause the calculator program to exit. This is not clean behavior for a
1494real calculator, but it is adequate in the first example.
1495
1496@node Rpcalc Gen, Rpcalc Compile, Rpcalc Error, RPN Calc
1497@subsection Running Bison to Make the Parser
1498@cindex running Bison (introduction)
1499
1500Before running Bison to produce a parser, we need to decide how to arrange
1501all the source code in one or more source files. For such a simple example,
1502the easiest thing is to put everything in one file. The definitions of
1503@code{yylex}, @code{yyerror} and @code{main} go at the end, in the
1504``additional C code'' section of the file (@pxref{Grammar Layout, ,The Overall Layout of a Bison Grammar}).
1505
1506For a large project, you would probably have several source files, and use
1507@code{make} to arrange to recompile them.
1508
1509With all the source in a single file, you use the following command to
1510convert it into a parser file:
1511
1512@example
1513bison @var{file_name}.y
1514@end example
1515
1516@noindent
1517In this example the file was called @file{rpcalc.y} (for ``Reverse Polish
1518CALCulator''). Bison produces a file named @file{@var{file_name}.tab.c},
1519removing the @samp{.y} from the original file name. The file output by
1520Bison contains the source code for @code{yyparse}. The additional
1521functions in the input file (@code{yylex}, @code{yyerror} and @code{main})
1522are copied verbatim to the output.
1523
1524@node Rpcalc Compile, , Rpcalc Gen, RPN Calc
1525@subsection Compiling the Parser File
1526@cindex compiling the parser
1527
1528Here is how to compile and run the parser file:
1529
1530@example
1531@group
1532# @r{List files in current directory.}
1533% ls
1534rpcalc.tab.c rpcalc.y
1535@end group
1536
1537@group
1538# @r{Compile the Bison parser.}
1539# @r{@samp{-lm} tells compiler to search math library for @code{pow}.}
1540% cc rpcalc.tab.c -lm -o rpcalc
1541@end group
1542
1543@group
1544# @r{List files again.}
1545% ls
1546rpcalc rpcalc.tab.c rpcalc.y
1547@end group
1548@end example
1549
1550The file @file{rpcalc} now contains the executable code. Here is an
1551example session using @code{rpcalc}.
1552
1553@example
1554% rpcalc
15554 9 +
155613
15573 7 + 3 4 5 *+-
1558-13
15593 7 + 3 4 5 * + - n @r{Note the unary minus, @samp{n}}
156013
15615 6 / 4 n +
1562-3.166666667
15633 4 ^ @r{Exponentiation}
156481
1565^D @r{End-of-file indicator}
1566%
1567@end example
1568
1569@node Infix Calc, Simple Error Recovery, RPN Calc, Examples
1570@section Infix Notation Calculator: @code{calc}
1571@cindex infix notation calculator
1572@cindex @code{calc}
1573@cindex calculator, infix notation
1574
1575We now modify rpcalc to handle infix operators instead of postfix. Infix
1576notation involves the concept of operator precedence and the need for
1577parentheses nested to arbitrary depth. Here is the Bison code for
1578@file{calc.y}, an infix desk-top calculator.
1579
1580@example
1581/* Infix notation calculator--calc */
1582
1583%@{
1584#define YYSTYPE double
1585#include <math.h>
1586%@}
1587
1588/* BISON Declarations */
1589%token NUM
1590%left '-' '+'
1591%left '*' '/'
1592%left NEG /* negation--unary minus */
1593%right '^' /* exponentiation */
1594
1595/* Grammar follows */
1596%%
1597input: /* empty string */
1598 | input line
1599;
1600
1601line: '\n'
1602 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1603;
1604
1605exp: NUM @{ $$ = $1; @}
1606 | exp '+' exp @{ $$ = $1 + $3; @}
1607 | exp '-' exp @{ $$ = $1 - $3; @}
1608 | exp '*' exp @{ $$ = $1 * $3; @}
1609 | exp '/' exp @{ $$ = $1 / $3; @}
1610 | '-' exp %prec NEG @{ $$ = -$2; @}
1611 | exp '^' exp @{ $$ = pow ($1, $3); @}
1612 | '(' exp ')' @{ $$ = $2; @}
1613;
1614%%
1615@end example
1616
1617@noindent
1618The functions @code{yylex}, @code{yyerror} and @code{main} can be the same
1619as before.
1620
1621There are two important new features shown in this code.
1622
1623In the second section (Bison declarations), @code{%left} declares token
1624types and says they are left-associative operators. The declarations
1625@code{%left} and @code{%right} (right associativity) take the place of
1626@code{%token} which is used to declare a token type name without
1627associativity. (These tokens are single-character literals, which
1628ordinarily don't need to be declared. We declare them here to specify
1629the associativity.)
1630
1631Operator precedence is determined by the line ordering of the
1632declarations; the higher the line number of the declaration (lower on
1633the page or screen), the higher the precedence. Hence, exponentiation
1634has the highest precedence, unary minus (@code{NEG}) is next, followed
1635by @samp{*} and @samp{/}, and so on. @xref{Precedence, ,Operator Precedence}.
1636
1637The other important new feature is the @code{%prec} in the grammar section
1638for the unary minus operator. The @code{%prec} simply instructs Bison that
1639the rule @samp{| '-' exp} has the same precedence as @code{NEG}---in this
1640case the next-to-highest. @xref{Contextual Precedence, ,Context-Dependent Precedence}.
1641
1642Here is a sample run of @file{calc.y}:
1643
1644@need 500
1645@example
1646% calc
16474 + 4.5 - (34/(8*3+-3))
16486.880952381
1649-56 + 2
1650-54
16513 ^ 2
16529
1653@end example
1654
1655@node Simple Error Recovery, Multi-function Calc, Infix Calc, Examples
1656@section Simple Error Recovery
1657@cindex error recovery, simple
1658
1659Up to this point, this manual has not addressed the issue of @dfn{error
1660recovery}---how to continue parsing after the parser detects a syntax
1661error. All we have handled is error reporting with @code{yyerror}. Recall
1662that by default @code{yyparse} returns after calling @code{yyerror}. This
1663means that an erroneous input line causes the calculator program to exit.
1664Now we show how to rectify this deficiency.
1665
1666The Bison language itself includes the reserved word @code{error}, which
1667may be included in the grammar rules. In the example below it has
1668been added to one of the alternatives for @code{line}:
1669
1670@example
1671@group
1672line: '\n'
1673 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1674 | error '\n' @{ yyerrok; @}
1675;
1676@end group
1677@end example
1678
1679This addition to the grammar allows for simple error recovery in the event
1680of a parse error. If an expression that cannot be evaluated is read, the
1681error will be recognized by the third rule for @code{line}, and parsing
1682will continue. (The @code{yyerror} function is still called upon to print
1683its message as well.) The action executes the statement @code{yyerrok}, a
1684macro defined automatically by Bison; its meaning is that error recovery is
1685complete (@pxref{Error Recovery}). Note the difference between
1686@code{yyerrok} and @code{yyerror}; neither one is a misprint.@refill
1687
1688This form of error recovery deals with syntax errors. There are other
1689kinds of errors; for example, division by zero, which raises an exception
1690signal that is normally fatal. A real calculator program must handle this
1691signal and use @code{longjmp} to return to @code{main} and resume parsing
1692input lines; it would also have to discard the rest of the current line of
1693input. We won't discuss this issue further because it is not specific to
1694Bison programs.
1695
1696@node Multi-function Calc, Exercises, Simple Error Recovery, Examples
1697@section Multi-Function Calculator: @code{mfcalc}
1698@cindex multi-function calculator
1699@cindex @code{mfcalc}
1700@cindex calculator, multi-function
1701
1702Now that the basics of Bison have been discussed, it is time to move on to
1703a more advanced problem. The above calculators provided only five
1704functions, @samp{+}, @samp{-}, @samp{*}, @samp{/} and @samp{^}. It would
1705be nice to have a calculator that provides other mathematical functions such
1706as @code{sin}, @code{cos}, etc.
1707
1708It is easy to add new operators to the infix calculator as long as they are
1709only single-character literals. The lexical analyzer @code{yylex} passes
1710back all non-number characters as tokens, so new grammar rules suffice for
1711adding a new operator. But we want something more flexible: built-in
1712functions whose syntax has this form:
1713
1714@example
1715@var{function_name} (@var{argument})
1716@end example
1717
1718@noindent
1719At the same time, we will add memory to the calculator, by allowing you
1720to create named variables, store values in them, and use them later.
1721Here is a sample session with the multi-function calculator:
1722
1723@example
1724% mfcalc
1725pi = 3.141592653589
17263.1415926536
1727sin(pi)
17280.0000000000
1729alpha = beta1 = 2.3
17302.3000000000
1731alpha
17322.3000000000
1733ln(alpha)
17340.8329091229
1735exp(ln(beta1))
17362.3000000000
1737%
1738@end example
1739
1740Note that multiple assignment and nested function calls are permitted.
1741
1742@menu
1743* Decl: Mfcalc Decl. Bison declarations for multi-function calculator.
1744* Rules: Mfcalc Rules. Grammar rules for the calculator.
1745* Symtab: Mfcalc Symtab. Symbol table management subroutines.
1746@end menu
1747
1748@node Mfcalc Decl, Mfcalc Rules, , Multi-function Calc
1749@subsection Declarations for @code{mfcalc}
1750
1751Here are the C and Bison declarations for the multi-function calculator.
1752
1753@smallexample
1754%@{
1755#include <math.h> /* For math functions, cos(), sin(), etc. */
1756#include "calc.h" /* Contains definition of `symrec' */
1757%@}
1758%union @{
1759double val; /* For returning numbers. */
1760symrec *tptr; /* For returning symbol-table pointers */
1761@}
1762
1763%token <val> NUM /* Simple double precision number */
1764%token <tptr> VAR FNCT /* Variable and Function */
1765%type <val> exp
1766
1767%right '='
1768%left '-' '+'
1769%left '*' '/'
1770%left NEG /* Negation--unary minus */
1771%right '^' /* Exponentiation */
1772
1773/* Grammar follows */
1774
1775%%
1776@end smallexample
1777
1778The above grammar introduces only two new features of the Bison language.
1779These features allow semantic values to have various data types
1780(@pxref{Multiple Types, ,More Than One Value Type}).
1781
1782The @code{%union} declaration specifies the entire list of possible types;
1783this is instead of defining @code{YYSTYPE}. The allowable types are now
1784double-floats (for @code{exp} and @code{NUM}) and pointers to entries in
1785the symbol table. @xref{Union Decl, ,The Collection of Value Types}.
1786
1787Since values can now have various types, it is necessary to associate a
1788type with each grammar symbol whose semantic value is used. These symbols
1789are @code{NUM}, @code{VAR}, @code{FNCT}, and @code{exp}. Their
1790declarations are augmented with information about their data type (placed
1791between angle brackets).
1792
1793The Bison construct @code{%type} is used for declaring nonterminal symbols,
1794just as @code{%token} is used for declaring token types. We have not used
1795@code{%type} before because nonterminal symbols are normally declared
1796implicitly by the rules that define them. But @code{exp} must be declared
1797explicitly so we can specify its value type. @xref{Type Decl, ,Nonterminal Symbols}.
1798
1799@node Mfcalc Rules, Mfcalc Symtab, Mfcalc Decl, Multi-function Calc
1800@subsection Grammar Rules for @code{mfcalc}
1801
1802Here are the grammar rules for the multi-function calculator.
1803Most of them are copied directly from @code{calc}; three rules,
1804those which mention @code{VAR} or @code{FNCT}, are new.
1805
1806@smallexample
1807input: /* empty */
1808 | input line
1809;
1810
1811line:
1812 '\n'
1813 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1814 | error '\n' @{ yyerrok; @}
1815;
1816
1817exp: NUM @{ $$ = $1; @}
1818 | VAR @{ $$ = $1->value.var; @}
1819 | VAR '=' exp @{ $$ = $3; $1->value.var = $3; @}
1820 | FNCT '(' exp ')' @{ $$ = (*($1->value.fnctptr))($3); @}
1821 | exp '+' exp @{ $$ = $1 + $3; @}
1822 | exp '-' exp @{ $$ = $1 - $3; @}
1823 | exp '*' exp @{ $$ = $1 * $3; @}
1824 | exp '/' exp @{ $$ = $1 / $3; @}
1825 | '-' exp %prec NEG @{ $$ = -$2; @}
1826 | exp '^' exp @{ $$ = pow ($1, $3); @}
1827 | '(' exp ')' @{ $$ = $2; @}
1828;
1829/* End of grammar */
1830%%
1831@end smallexample
1832
1833@node Mfcalc Symtab, , Mfcalc Rules, Multi-function Calc
1834@subsection The @code{mfcalc} Symbol Table
1835@cindex symbol table example
1836
1837The multi-function calculator requires a symbol table to keep track of the
1838names and meanings of variables and functions. This doesn't affect the
1839grammar rules (except for the actions) or the Bison declarations, but it
1840requires some additional C functions for support.
1841
1842The symbol table itself consists of a linked list of records. Its
1843definition, which is kept in the header @file{calc.h}, is as follows. It
1844provides for either functions or variables to be placed in the table.
1845
1846@smallexample
1847@group
1848/* Data type for links in the chain of symbols. */
1849struct symrec
1850@{
1851 char *name; /* name of symbol */
1852 int type; /* type of symbol: either VAR or FNCT */
1853 union @{
1854 double var; /* value of a VAR */
1855 double (*fnctptr)(); /* value of a FNCT */
1856 @} value;
1857 struct symrec *next; /* link field */
1858@};
1859@end group
1860
1861@group
1862typedef struct symrec symrec;
1863
1864/* The symbol table: a chain of `struct symrec'. */
1865extern symrec *sym_table;
1866
1867symrec *putsym ();
1868symrec *getsym ();
1869@end group
1870@end smallexample
1871
1872The new version of @code{main} includes a call to @code{init_table}, a
1873function that initializes the symbol table. Here it is, and
1874@code{init_table} as well:
1875
1876@smallexample
1877@group
1878#include <stdio.h>
1879
1880main ()
1881@{
1882 init_table ();
1883 yyparse ();
1884@}
1885@end group
1886
1887@group
1888yyerror (s) /* Called by yyparse on error */
1889 char *s;
1890@{
1891 printf ("%s\n", s);
1892@}
1893
1894struct init
1895@{
1896 char *fname;
1897 double (*fnct)();
1898@};
1899@end group
1900
1901@group
1902struct init arith_fncts[]
1903 = @{
1904 "sin", sin,
1905 "cos", cos,
1906 "atan", atan,
1907 "ln", log,
1908 "exp", exp,
1909 "sqrt", sqrt,
1910 0, 0
1911 @};
1912
1913/* The symbol table: a chain of `struct symrec'. */
1914symrec *sym_table = (symrec *)0;
1915@end group
1916
1917@group
1918init_table () /* puts arithmetic functions in table. */
1919@{
1920 int i;
1921 symrec *ptr;
1922 for (i = 0; arith_fncts[i].fname != 0; i++)
1923 @{
1924 ptr = putsym (arith_fncts[i].fname, FNCT);
1925 ptr->value.fnctptr = arith_fncts[i].fnct;
1926 @}
1927@}
1928@end group
1929@end smallexample
1930
1931By simply editing the initialization list and adding the necessary include
1932files, you can add additional functions to the calculator.
1933
1934Two important functions allow look-up and installation of symbols in the
1935symbol table. The function @code{putsym} is passed a name and the type
1936(@code{VAR} or @code{FNCT}) of the object to be installed. The object is
1937linked to the front of the list, and a pointer to the object is returned.
1938The function @code{getsym} is passed the name of the symbol to look up. If
1939found, a pointer to that symbol is returned; otherwise zero is returned.
1940
1941@smallexample
1942symrec *
1943putsym (sym_name,sym_type)
1944 char *sym_name;
1945 int sym_type;
1946@{
1947 symrec *ptr;
1948 ptr = (symrec *) malloc (sizeof (symrec));
1949 ptr->name = (char *) malloc (strlen (sym_name) + 1);
1950 strcpy (ptr->name,sym_name);
1951 ptr->type = sym_type;
1952 ptr->value.var = 0; /* set value to 0 even if fctn. */
1953 ptr->next = (struct symrec *)sym_table;
1954 sym_table = ptr;
1955 return ptr;
1956@}
1957
1958symrec *
1959getsym (sym_name)
1960 char *sym_name;
1961@{
1962 symrec *ptr;
1963 for (ptr = sym_table; ptr != (symrec *) 0;
1964 ptr = (symrec *)ptr->next)
1965 if (strcmp (ptr->name,sym_name) == 0)
1966 return ptr;
1967 return 0;
1968@}
1969@end smallexample
1970
1971The function @code{yylex} must now recognize variables, numeric values, and
1972the single-character arithmetic operators. Strings of alphanumeric
1973characters with a leading nondigit are recognized as either variables or
1974functions depending on what the symbol table says about them.
1975
1976The string is passed to @code{getsym} for look up in the symbol table. If
1977the name appears in the table, a pointer to its location and its type
1978(@code{VAR} or @code{FNCT}) is returned to @code{yyparse}. If it is not
1979already in the table, then it is installed as a @code{VAR} using
1980@code{putsym}. Again, a pointer and its type (which must be @code{VAR}) is
1981returned to @code{yyparse}.@refill
1982
1983No change is needed in the handling of numeric values and arithmetic
1984operators in @code{yylex}.
1985
1986@smallexample
1987@group
1988#include <ctype.h>
1989yylex ()
1990@{
1991 int c;
1992
1993 /* Ignore whitespace, get first nonwhite character. */
1994 while ((c = getchar ()) == ' ' || c == '\t');
1995
1996 if (c == EOF)
1997 return 0;
1998@end group
1999
2000@group
2001 /* Char starts a number => parse the number. */
2002 if (c == '.' || isdigit (c))
2003 @{
2004 ungetc (c, stdin);
2005 scanf ("%lf", &yylval.val);
2006 return NUM;
2007 @}
2008@end group
2009
2010@group
2011 /* Char starts an identifier => read the name. */
2012 if (isalpha (c))
2013 @{
2014 symrec *s;
2015 static char *symbuf = 0;
2016 static int length = 0;
2017 int i;
2018@end group
2019
2020@group
2021 /* Initially make the buffer long enough
2022 for a 40-character symbol name. */
2023 if (length == 0)
2024 length = 40, symbuf = (char *)malloc (length + 1);
2025
2026 i = 0;
2027 do
2028@end group
2029@group
2030 @{
2031 /* If buffer is full, make it bigger. */
2032 if (i == length)
2033 @{
2034 length *= 2;
2035 symbuf = (char *)realloc (symbuf, length + 1);
2036 @}
2037 /* Add this character to the buffer. */
2038 symbuf[i++] = c;
2039 /* Get another character. */
2040 c = getchar ();
2041 @}
2042@end group
2043@group
2044 while (c != EOF && isalnum (c));
2045
2046 ungetc (c, stdin);
2047 symbuf[i] = '\0';
2048@end group
2049
2050@group
2051 s = getsym (symbuf);
2052 if (s == 0)
2053 s = putsym (symbuf, VAR);
2054 yylval.tptr = s;
2055 return s->type;
2056 @}
2057
2058 /* Any other character is a token by itself. */
2059 return c;
2060@}
2061@end group
2062@end smallexample
2063
2064This program is both powerful and flexible. You may easily add new
2065functions, and it is a simple job to modify this code to install predefined
2066variables such as @code{pi} or @code{e} as well.
2067
2068@node Exercises, , Multi-function Calc, Examples
2069@section Exercises
2070@cindex exercises
2071
2072@enumerate
2073@item
2074Add some new functions from @file{math.h} to the initialization list.
2075
2076@item
2077Add another array that contains constants and their values. Then
2078modify @code{init_table} to add these constants to the symbol table.
2079It will be easiest to give the constants type @code{VAR}.
2080
2081@item
2082Make the program report an error if the user refers to an
2083uninitialized variable in any way except to store a value in it.
2084@end enumerate
2085
2086@node Grammar File, Interface, Examples, Top
2087@chapter Bison Grammar Files
2088
2089Bison takes as input a context-free grammar specification and produces a
2090C-language function that recognizes correct instances of the grammar.
2091
2092The Bison grammar input file conventionally has a name ending in @samp{.y}.
2093
2094@menu
2095* Grammar Outline:: Overall layout of the grammar file.
2096* Symbols:: Terminal and nonterminal symbols.
2097* Rules:: How to write grammar rules.
2098* Recursion:: Writing recursive rules.
2099* Semantics:: Semantic values and actions.
2100* Declarations:: All kinds of Bison declarations are described here.
2101* Multiple Parsers:: Putting more than one Bison parser in one program.
2102@end menu
2103
2104@node Grammar Outline, Symbols, , Grammar File
2105@section Outline of a Bison Grammar
2106
2107A Bison grammar file has four main sections, shown here with the
2108appropriate delimiters:
2109
2110@example
2111%@{
2112@var{C declarations}
2113%@}
2114
2115@var{Bison declarations}
2116
2117%%
2118@var{Grammar rules}
2119%%
2120
2121@var{Additional C code}
2122@end example
2123
2124Comments enclosed in @samp{/* @dots{} */} may appear in any of the sections.
2125
2126@menu
2127* C Declarations:: Syntax and usage of the C declarations section.
2128* Bison Declarations:: Syntax and usage of the Bison declarations section.
2129* Grammar Rules:: Syntax and usage of the grammar rules section.
2130* C Code:: Syntax and usage of the additional C code section.
2131@end menu
2132
2133@node C Declarations, Bison Declarations, , Grammar Outline
2134@subsection The C Declarations Section
2135@cindex C declarations section
2136@cindex declarations, C
2137
2138The @var{C declarations} section contains macro definitions and
2139declarations of functions and variables that are used in the actions in the
2140grammar rules. These are copied to the beginning of the parser file so
2141that they precede the definition of @code{yyparse}. You can use
2142@samp{#include} to get the declarations from a header file. If you don't
2143need any C declarations, you may omit the @samp{%@{} and @samp{%@}}
2144delimiters that bracket this section.
2145
2146@node Bison Declarations, Grammar Rules, C Declarations, Grammar Outline
2147@subsection The Bison Declarations Section
2148@cindex Bison declarations (introduction)
2149@cindex declarations, Bison (introduction)
2150
2151The @var{Bison declarations} section contains declarations that define
2152terminal and nonterminal symbols, specify precedence, and so on.
2153In some simple grammars you may not need any declarations.
2154@xref{Declarations, ,Bison Declarations}.
2155
2156@node Grammar Rules, C Code, Bison Declarations, Grammar Outline
2157@subsection The Grammar Rules Section
2158@cindex grammar rules section
2159@cindex rules section for grammar
2160
2161The @dfn{grammar rules} section contains one or more Bison grammar
2162rules, and nothing else. @xref{Rules, ,Syntax of Grammar Rules}.
2163
2164There must always be at least one grammar rule, and the first
2165@samp{%%} (which precedes the grammar rules) may never be omitted even
2166if it is the first thing in the file.
2167
2168@node C Code, , Grammar Rules, Grammar Outline
2169@subsection The Additional C Code Section
2170@cindex additional C code section
2171@cindex C code, section for additional
2172
2173The @var{additional C code} section is copied verbatim to the end of
2174the parser file, just as the @var{C declarations} section is copied to
2175the beginning. This is the most convenient place to put anything
2176that you want to have in the parser file but which need not come before
2177the definition of @code{yyparse}. For example, the definitions of
2178@code{yylex} and @code{yyerror} often go here. @xref{Interface, ,Parser C-Language Interface}.
2179
2180If the last section is empty, you may omit the @samp{%%} that separates it
2181from the grammar rules.
2182
2183The Bison parser itself contains many static variables whose names start
2184with @samp{yy} and many macros whose names start with @samp{YY}. It is a
2185good idea to avoid using any such names (except those documented in this
2186manual) in the additional C code section of the grammar file.
2187
2188@node Symbols, Rules, Grammar Outline, Grammar File
2189@section Symbols, Terminal and Nonterminal
2190@cindex nonterminal symbol
2191@cindex terminal symbol
2192@cindex token type
2193@cindex symbol
2194
2195@dfn{Symbols} in Bison grammars represent the grammatical classifications
2196of the language.
2197
2198A @dfn{terminal symbol} (also known as a @dfn{token type}) represents a
2199class of syntactically equivalent tokens. You use the symbol in grammar
2200rules to mean that a token in that class is allowed. The symbol is
2201represented in the Bison parser by a numeric code, and the @code{yylex}
2202function returns a token type code to indicate what kind of token has been
2203read. You don't need to know what the code value is; you can use the
2204symbol to stand for it.
2205
2206A @dfn{nonterminal symbol} stands for a class of syntactically equivalent
2207groupings. The symbol name is used in writing grammar rules. By convention,
2208it should be all lower case.
2209
2210Symbol names can contain letters, digits (not at the beginning),
2211underscores and periods. Periods make sense only in nonterminals.
2212
2213There are three ways of writing terminal symbols in the grammar:
2214
2215@itemize @bullet
2216@item
2217A @dfn{named token type} is written with an identifier, like an
2218identifier in C. By convention, it should be all upper case. Each
2219such name must be defined with a Bison declaration such as
2220@code{%token}. @xref{Token Decl, ,Token Type Names}.
2221
2222@item
2223@cindex character token
2224@cindex literal token
2225@cindex single-character literal
2226A @dfn{character token type} (or @dfn{literal character token}) is
2227written in the grammar using the same syntax used in C for character
2228constants; for example, @code{'+'} is a character token type. A
2229character token type doesn't need to be declared unless you need to
2230specify its semantic value data type (@pxref{Value Type, ,Data Types of
2231Semantic Values}), associativity, or precedence (@pxref{Precedence,
2232,Operator Precedence}).
2233
2234By convention, a character token type is used only to represent a
2235token that consists of that particular character. Thus, the token
2236type @code{'+'} is used to represent the character @samp{+} as a
2237token. Nothing enforces this convention, but if you depart from it,
2238your program will confuse other readers.
2239
2240All the usual escape sequences used in character literals in C can be
2241used in Bison as well, but you must not use the null character as a
2242character literal because its ASCII code, zero, is the code @code{yylex}
2243returns for end-of-input (@pxref{Calling Convention, ,Calling Convention
2244for @code{yylex}}).
2245
2246@item
2247@cindex string token
2248@cindex literal string token
2249@cindex multi-character literal
2250A @dfn{literal string token} is written like a C string constant; for
2251example, @code{"<="} is a literal string token. A literal string token
2252doesn't need to be declared unless you need to specify its semantic
2253value data type (@pxref{Value Type}), associativity, precedence
2254(@pxref{Precedence}).
2255
2256You can associate the literal string token with a symbolic name as an
2257alias, using the @code{%token} declaration (@pxref{Token Decl, ,Token
2258Declarations}). If you don't do that, the lexical analyzer has to
2259retrieve the token number for the literal string token from the
2260@code{yytname} table (@pxref{Calling Convention}).
2261
2262@strong{WARNING}: literal string tokens do not work in Yacc.
2263
2264By convention, a literal string token is used only to represent a token
2265that consists of that particular string. Thus, you should use the token
2266type @code{"<="} to represent the string @samp{<=} as a token. Bison
2267does not enforces this convention, but if you depart from it, people who
2268read your program will be confused.
2269
2270All the escape sequences used in string literals in C can be used in
2271Bison as well. A literal string token must contain two or more
2272characters; for a token containing just one character, use a character
2273token (see above).
2274@end itemize
2275
2276How you choose to write a terminal symbol has no effect on its
2277grammatical meaning. That depends only on where it appears in rules and
2278on when the parser function returns that symbol.
2279
2280The value returned by @code{yylex} is always one of the terminal symbols
2281(or 0 for end-of-input). Whichever way you write the token type in the
2282grammar rules, you write it the same way in the definition of @code{yylex}.
2283The numeric code for a character token type is simply the ASCII code for
2284the character, so @code{yylex} can use the identical character constant to
2285generate the requisite code. Each named token type becomes a C macro in
2286the parser file, so @code{yylex} can use the name to stand for the code.
2287(This is why periods don't make sense in terminal symbols.)
2288@xref{Calling Convention, ,Calling Convention for @code{yylex}}.
2289
2290If @code{yylex} is defined in a separate file, you need to arrange for the
2291token-type macro definitions to be available there. Use the @samp{-d}
2292option when you run Bison, so that it will write these macro definitions
2293into a separate header file @file{@var{name}.tab.h} which you can include
2294in the other source files that need it. @xref{Invocation, ,Invoking Bison}.
2295
2296The symbol @code{error} is a terminal symbol reserved for error recovery
2297(@pxref{Error Recovery}); you shouldn't use it for any other purpose.
2298In particular, @code{yylex} should never return this value.
2299
2300@node Rules, Recursion, Symbols, Grammar File
2301@section Syntax of Grammar Rules
2302@cindex rule syntax
2303@cindex grammar rule syntax
2304@cindex syntax of grammar rules
2305
2306A Bison grammar rule has the following general form:
2307
2308@example
2309@group
2310@var{result}: @var{components}@dots{}
2311 ;
2312@end group
2313@end example
2314
2315@noindent
2316where @var{result} is the nonterminal symbol that this rule describes
2317and @var{components} are various terminal and nonterminal symbols that
2318are put together by this rule (@pxref{Symbols}).
2319
2320For example,
2321
2322@example
2323@group
2324exp: exp '+' exp
2325 ;
2326@end group
2327@end example
2328
2329@noindent
2330says that two groupings of type @code{exp}, with a @samp{+} token in between,
2331can be combined into a larger grouping of type @code{exp}.
2332
2333Whitespace in rules is significant only to separate symbols. You can add
2334extra whitespace as you wish.
2335
2336Scattered among the components can be @var{actions} that determine
2337the semantics of the rule. An action looks like this:
2338
2339@example
2340@{@var{C statements}@}
2341@end example
2342
2343@noindent
2344Usually there is only one action and it follows the components.
2345@xref{Actions}.
2346
2347@findex |
2348Multiple rules for the same @var{result} can be written separately or can
2349be joined with the vertical-bar character @samp{|} as follows:
2350
2351@ifinfo
2352@example
2353@var{result}: @var{rule1-components}@dots{}
2354 | @var{rule2-components}@dots{}
2355 @dots{}
2356 ;
2357@end example
2358@end ifinfo
2359@iftex
2360@example
2361@group
2362@var{result}: @var{rule1-components}@dots{}
2363 | @var{rule2-components}@dots{}
2364 @dots{}
2365 ;
2366@end group
2367@end example
2368@end iftex
2369
2370@noindent
2371They are still considered distinct rules even when joined in this way.
2372
2373If @var{components} in a rule is empty, it means that @var{result} can
2374match the empty string. For example, here is how to define a
2375comma-separated sequence of zero or more @code{exp} groupings:
2376
2377@example
2378@group
2379expseq: /* empty */
2380 | expseq1
2381 ;
2382@end group
2383
2384@group
2385expseq1: exp
2386 | expseq1 ',' exp
2387 ;
2388@end group
2389@end example
2390
2391@noindent
2392It is customary to write a comment @samp{/* empty */} in each rule
2393with no components.
2394
2395@node Recursion, Semantics, Rules, Grammar File
2396@section Recursive Rules
2397@cindex recursive rule
2398
2399A rule is called @dfn{recursive} when its @var{result} nonterminal appears
2400also on its right hand side. Nearly all Bison grammars need to use
2401recursion, because that is the only way to define a sequence of any number
2402of somethings. Consider this recursive definition of a comma-separated
2403sequence of one or more expressions:
2404
2405@example
2406@group
2407expseq1: exp
2408 | expseq1 ',' exp
2409 ;
2410@end group
2411@end example
2412
2413@cindex left recursion
2414@cindex right recursion
2415@noindent
2416Since the recursive use of @code{expseq1} is the leftmost symbol in the
2417right hand side, we call this @dfn{left recursion}. By contrast, here
2418the same construct is defined using @dfn{right recursion}:
2419
2420@example
2421@group
2422expseq1: exp
2423 | exp ',' expseq1
2424 ;
2425@end group
2426@end example
2427
2428@noindent
2429Any kind of sequence can be defined using either left recursion or
2430right recursion, but you should always use left recursion, because it
2431can parse a sequence of any number of elements with bounded stack
2432space. Right recursion uses up space on the Bison stack in proportion
2433to the number of elements in the sequence, because all the elements
2434must be shifted onto the stack before the rule can be applied even
2435once. @xref{Algorithm, ,The Bison Parser Algorithm }, for
2436further explanation of this.
2437
2438@cindex mutual recursion
2439@dfn{Indirect} or @dfn{mutual} recursion occurs when the result of the
2440rule does not appear directly on its right hand side, but does appear
2441in rules for other nonterminals which do appear on its right hand
2442side.
2443
2444For example:
2445
2446@example
2447@group
2448expr: primary
2449 | primary '+' primary
2450 ;
2451@end group
2452
2453@group
2454primary: constant
2455 | '(' expr ')'
2456 ;
2457@end group
2458@end example
2459
2460@noindent
2461defines two mutually-recursive nonterminals, since each refers to the
2462other.
2463
2464@node Semantics, Declarations, Recursion, Grammar File
2465@section Defining Language Semantics
2466@cindex defining language semantics
2467@cindex language semantics, defining
2468
2469The grammar rules for a language determine only the syntax. The semantics
2470are determined by the semantic values associated with various tokens and
2471groupings, and by the actions taken when various groupings are recognized.
2472
2473For example, the calculator calculates properly because the value
2474associated with each expression is the proper number; it adds properly
2475because the action for the grouping @w{@samp{@var{x} + @var{y}}} is to add
2476the numbers associated with @var{x} and @var{y}.
2477
2478@menu
2479* Value Type:: Specifying one data type for all semantic values.
2480* Multiple Types:: Specifying several alternative data types.
2481* Actions:: An action is the semantic definition of a grammar rule.
2482* Action Types:: Specifying data types for actions to operate on.
2483* Mid-Rule Actions:: Most actions go at the end of a rule.
2484 This says when, why and how to use the exceptional
2485 action in the middle of a rule.
2486@end menu
2487
2488@node Value Type, Multiple Types, , Semantics
2489@subsection Data Types of Semantic Values
2490@cindex semantic value type
2491@cindex value type, semantic
2492@cindex data types of semantic values
2493@cindex default data type
2494
2495In a simple program it may be sufficient to use the same data type for
2496the semantic values of all language constructs. This was true in the
2497RPN and infix calculator examples (@pxref{RPN Calc, ,Reverse Polish Notation Calculator}).
2498
2499Bison's default is to use type @code{int} for all semantic values. To
2500specify some other type, define @code{YYSTYPE} as a macro, like this:
2501
2502@example
2503#define YYSTYPE double
2504@end example
2505
2506@noindent
2507This macro definition must go in the C declarations section of the grammar
2508file (@pxref{Grammar Outline, ,Outline of a Bison Grammar}).
2509
2510@node Multiple Types, Actions, Value Type, Semantics
2511@subsection More Than One Value Type
2512
2513In most programs, you will need different data types for different kinds
2514of tokens and groupings. For example, a numeric constant may need type
2515@code{int} or @code{long}, while a string constant needs type @code{char *},
2516and an identifier might need a pointer to an entry in the symbol table.
2517
2518To use more than one data type for semantic values in one parser, Bison
2519requires you to do two things:
2520
2521@itemize @bullet
2522@item
2523Specify the entire collection of possible data types, with the
2524@code{%union} Bison declaration (@pxref{Union Decl, ,The Collection of Value Types}).
2525
2526@item
2527Choose one of those types for each symbol (terminal or nonterminal)
2528for which semantic values are used. This is done for tokens with the
2529@code{%token} Bison declaration (@pxref{Token Decl, ,Token Type Names}) and for groupings
2530with the @code{%type} Bison declaration (@pxref{Type Decl, ,Nonterminal Symbols}).
2531@end itemize
2532
2533@node Actions, Action Types, Multiple Types, Semantics
2534@subsection Actions
2535@cindex action
2536@vindex $$
2537@vindex $@var{n}
2538
2539An action accompanies a syntactic rule and contains C code to be executed
2540each time an instance of that rule is recognized. The task of most actions
2541is to compute a semantic value for the grouping built by the rule from the
2542semantic values associated with tokens or smaller groupings.
2543
2544An action consists of C statements surrounded by braces, much like a
2545compound statement in C. It can be placed at any position in the rule; it
2546is executed at that position. Most rules have just one action at the end
2547of the rule, following all the components. Actions in the middle of a rule
2548are tricky and used only for special purposes (@pxref{Mid-Rule Actions, ,Actions in Mid-Rule}).
2549
2550The C code in an action can refer to the semantic values of the components
2551matched by the rule with the construct @code{$@var{n}}, which stands for
2552the value of the @var{n}th component. The semantic value for the grouping
2553being constructed is @code{$$}. (Bison translates both of these constructs
2554into array element references when it copies the actions into the parser
2555file.)
2556
2557Here is a typical example:
2558
2559@example
2560@group
2561exp: @dots{}
2562 | exp '+' exp
2563 @{ $$ = $1 + $3; @}
2564@end group
2565@end example
2566
2567@noindent
2568This rule constructs an @code{exp} from two smaller @code{exp} groupings
2569connected by a plus-sign token. In the action, @code{$1} and @code{$3}
2570refer to the semantic values of the two component @code{exp} groupings,
2571which are the first and third symbols on the right hand side of the rule.
2572The sum is stored into @code{$$} so that it becomes the semantic value of
2573the addition-expression just recognized by the rule. If there were a
2574useful semantic value associated with the @samp{+} token, it could be
2575referred to as @code{$2}.@refill
2576
2577@cindex default action
2578If you don't specify an action for a rule, Bison supplies a default:
2579@w{@code{$$ = $1}.} Thus, the value of the first symbol in the rule becomes
2580the value of the whole rule. Of course, the default rule is valid only
2581if the two data types match. There is no meaningful default action for
2582an empty rule; every empty rule must have an explicit action unless the
2583rule's value does not matter.
2584
2585@code{$@var{n}} with @var{n} zero or negative is allowed for reference
2586to tokens and groupings on the stack @emph{before} those that match the
2587current rule. This is a very risky practice, and to use it reliably
2588you must be certain of the context in which the rule is applied. Here
2589is a case in which you can use this reliably:
2590
2591@example
2592@group
2593foo: expr bar '+' expr @{ @dots{} @}
2594 | expr bar '-' expr @{ @dots{} @}
2595 ;
2596@end group
2597
2598@group
2599bar: /* empty */
2600 @{ previous_expr = $0; @}
2601 ;
2602@end group
2603@end example
2604
2605As long as @code{bar} is used only in the fashion shown here, @code{$0}
2606always refers to the @code{expr} which precedes @code{bar} in the
2607definition of @code{foo}.
2608
2609@node Action Types, Mid-Rule Actions, Actions, Semantics
2610@subsection Data Types of Values in Actions
2611@cindex action data types
2612@cindex data types in actions
2613
2614If you have chosen a single data type for semantic values, the @code{$$}
2615and @code{$@var{n}} constructs always have that data type.
2616
2617If you have used @code{%union} to specify a variety of data types, then you
2618must declare a choice among these types for each terminal or nonterminal
2619symbol that can have a semantic value. Then each time you use @code{$$} or
2620@code{$@var{n}}, its data type is determined by which symbol it refers to
2621in the rule. In this example,@refill
2622
2623@example
2624@group
2625exp: @dots{}
2626 | exp '+' exp
2627 @{ $$ = $1 + $3; @}
2628@end group
2629@end example
2630
2631@noindent
2632@code{$1} and @code{$3} refer to instances of @code{exp}, so they all
2633have the data type declared for the nonterminal symbol @code{exp}. If
2634@code{$2} were used, it would have the data type declared for the
2635terminal symbol @code{'+'}, whatever that might be.@refill
2636
2637Alternatively, you can specify the data type when you refer to the value,
2638by inserting @samp{<@var{type}>} after the @samp{$} at the beginning of the
2639reference. For example, if you have defined types as shown here:
2640
2641@example
2642@group
2643%union @{
2644 int itype;
2645 double dtype;
2646@}
2647@end group
2648@end example
2649
2650@noindent
2651then you can write @code{$<itype>1} to refer to the first subunit of the
2652rule as an integer, or @code{$<dtype>1} to refer to it as a double.
2653
2654@node Mid-Rule Actions, , Action Types, Semantics
2655@subsection Actions in Mid-Rule
2656@cindex actions in mid-rule
2657@cindex mid-rule actions
2658
2659Occasionally it is useful to put an action in the middle of a rule.
2660These actions are written just like usual end-of-rule actions, but they
2661are executed before the parser even recognizes the following components.
2662
2663A mid-rule action may refer to the components preceding it using
2664@code{$@var{n}}, but it may not refer to subsequent components because
2665it is run before they are parsed.
2666
2667The mid-rule action itself counts as one of the components of the rule.
2668This makes a difference when there is another action later in the same rule
2669(and usually there is another at the end): you have to count the actions
2670along with the symbols when working out which number @var{n} to use in
2671@code{$@var{n}}.
2672
2673The mid-rule action can also have a semantic value. The action can set
2674its value with an assignment to @code{$$}, and actions later in the rule
2675can refer to the value using @code{$@var{n}}. Since there is no symbol
2676to name the action, there is no way to declare a data type for the value
2677in advance, so you must use the @samp{$<@dots{}>} construct to specify a
2678data type each time you refer to this value.
2679
2680There is no way to set the value of the entire rule with a mid-rule
2681action, because assignments to @code{$$} do not have that effect. The
2682only way to set the value for the entire rule is with an ordinary action
2683at the end of the rule.
2684
2685Here is an example from a hypothetical compiler, handling a @code{let}
2686statement that looks like @samp{let (@var{variable}) @var{statement}} and
2687serves to create a variable named @var{variable} temporarily for the
2688duration of @var{statement}. To parse this construct, we must put
2689@var{variable} into the symbol table while @var{statement} is parsed, then
2690remove it afterward. Here is how it is done:
2691
2692@example
2693@group
2694stmt: LET '(' var ')'
2695 @{ $<context>$ = push_context ();
2696 declare_variable ($3); @}
2697 stmt @{ $$ = $6;
2698 pop_context ($<context>5); @}
2699@end group
2700@end example
2701
2702@noindent
2703As soon as @samp{let (@var{variable})} has been recognized, the first
2704action is run. It saves a copy of the current semantic context (the
2705list of accessible variables) as its semantic value, using alternative
2706@code{context} in the data-type union. Then it calls
2707@code{declare_variable} to add the new variable to that list. Once the
2708first action is finished, the embedded statement @code{stmt} can be
2709parsed. Note that the mid-rule action is component number 5, so the
2710@samp{stmt} is component number 6.
2711
2712After the embedded statement is parsed, its semantic value becomes the
2713value of the entire @code{let}-statement. Then the semantic value from the
2714earlier action is used to restore the prior list of variables. This
2715removes the temporary @code{let}-variable from the list so that it won't
2716appear to exist while the rest of the program is parsed.
2717
2718Taking action before a rule is completely recognized often leads to
2719conflicts since the parser must commit to a parse in order to execute the
2720action. For example, the following two rules, without mid-rule actions,
2721can coexist in a working parser because the parser can shift the open-brace
2722token and look at what follows before deciding whether there is a
2723declaration or not:
2724
2725@example
2726@group
2727compound: '@{' declarations statements '@}'
2728 | '@{' statements '@}'
2729 ;
2730@end group
2731@end example
2732
2733@noindent
2734But when we add a mid-rule action as follows, the rules become nonfunctional:
2735
2736@example
2737@group
2738compound: @{ prepare_for_local_variables (); @}
2739 '@{' declarations statements '@}'
2740@end group
2741@group
2742 | '@{' statements '@}'
2743 ;
2744@end group
2745@end example
2746
2747@noindent
2748Now the parser is forced to decide whether to run the mid-rule action
2749when it has read no farther than the open-brace. In other words, it
2750must commit to using one rule or the other, without sufficient
2751information to do it correctly. (The open-brace token is what is called
2752the @dfn{look-ahead} token at this time, since the parser is still
2753deciding what to do about it. @xref{Look-Ahead, ,Look-Ahead Tokens}.)
2754
2755You might think that you could correct the problem by putting identical
2756actions into the two rules, like this:
2757
2758@example
2759@group
2760compound: @{ prepare_for_local_variables (); @}
2761 '@{' declarations statements '@}'
2762 | @{ prepare_for_local_variables (); @}
2763 '@{' statements '@}'
2764 ;
2765@end group
2766@end example
2767
2768@noindent
2769But this does not help, because Bison does not realize that the two actions
2770are identical. (Bison never tries to understand the C code in an action.)
2771
2772If the grammar is such that a declaration can be distinguished from a
2773statement by the first token (which is true in C), then one solution which
2774does work is to put the action after the open-brace, like this:
2775
2776@example
2777@group
2778compound: '@{' @{ prepare_for_local_variables (); @}
2779 declarations statements '@}'
2780 | '@{' statements '@}'
2781 ;
2782@end group
2783@end example
2784
2785@noindent
2786Now the first token of the following declaration or statement,
2787which would in any case tell Bison which rule to use, can still do so.
2788
2789Another solution is to bury the action inside a nonterminal symbol which
2790serves as a subroutine:
2791
2792@example
2793@group
2794subroutine: /* empty */
2795 @{ prepare_for_local_variables (); @}
2796 ;
2797
2798@end group
2799
2800@group
2801compound: subroutine
2802 '@{' declarations statements '@}'
2803 | subroutine
2804 '@{' statements '@}'
2805 ;
2806@end group
2807@end example
2808
2809@noindent
2810Now Bison can execute the action in the rule for @code{subroutine} without
2811deciding which rule for @code{compound} it will eventually use. Note that
2812the action is now at the end of its rule. Any mid-rule action can be
2813converted to an end-of-rule action in this way, and this is what Bison
2814actually does to implement mid-rule actions.
2815
2816@node Declarations, Multiple Parsers, Semantics, Grammar File
2817@section Bison Declarations
2818@cindex declarations, Bison
2819@cindex Bison declarations
2820
2821The @dfn{Bison declarations} section of a Bison grammar defines the symbols
2822used in formulating the grammar and the data types of semantic values.
2823@xref{Symbols}.
2824
2825All token type names (but not single-character literal tokens such as
2826@code{'+'} and @code{'*'}) must be declared. Nonterminal symbols must be
2827declared if you need to specify which data type to use for the semantic
2828value (@pxref{Multiple Types, ,More Than One Value Type}).
2829
2830The first rule in the file also specifies the start symbol, by default.
2831If you want some other symbol to be the start symbol, you must declare
2832it explicitly (@pxref{Language and Grammar, ,Languages and Context-Free Grammars}).
2833
2834@menu
2835* Token Decl:: Declaring terminal symbols.
2836* Precedence Decl:: Declaring terminals with precedence and associativity.
2837* Union Decl:: Declaring the set of all semantic value types.
2838* Type Decl:: Declaring the choice of type for a nonterminal symbol.
2839* Expect Decl:: Suppressing warnings about shift/reduce conflicts.
2840* Start Decl:: Specifying the start symbol.
2841* Pure Decl:: Requesting a reentrant parser.
2842* Decl Summary:: Table of all Bison declarations.
2843@end menu
2844
2845@node Token Decl, Precedence Decl, , Declarations
2846@subsection Token Type Names
2847@cindex declaring token type names
2848@cindex token type names, declaring
2849@cindex declaring literal string tokens
2850@findex %token
2851
2852The basic way to declare a token type name (terminal symbol) is as follows:
2853
2854@example
2855%token @var{name}
2856@end example
2857
2858Bison will convert this into a @code{#define} directive in
2859the parser, so that the function @code{yylex} (if it is in this file)
2860can use the name @var{name} to stand for this token type's code.
2861
2862Alternatively, you can use @code{%left}, @code{%right}, or @code{%nonassoc}
2863instead of @code{%token}, if you wish to specify precedence.
2864@xref{Precedence Decl, ,Operator Precedence}.
2865
2866You can explicitly specify the numeric code for a token type by appending
2867an integer value in the field immediately following the token name:
2868
2869@example
2870%token NUM 300
2871@end example
2872
2873@noindent
2874It is generally best, however, to let Bison choose the numeric codes for
2875all token types. Bison will automatically select codes that don't conflict
2876with each other or with ASCII characters.
2877
2878In the event that the stack type is a union, you must augment the
2879@code{%token} or other token declaration to include the data type
2880alternative delimited by angle-brackets (@pxref{Multiple Types, ,More Than One Value Type}).
2881
2882For example:
2883
2884@example
2885@group
2886%union @{ /* define stack type */
2887 double val;
2888 symrec *tptr;
2889@}
2890%token <val> NUM /* define token NUM and its type */
2891@end group
2892@end example
2893
2894You can associate a literal string token with a token type name by
2895writing the literal string at the end of a @code{%token}
2896declaration which declares the name. For example:
2897
2898@example
2899%token arrow "=>"
2900@end example
2901
2902@noindent
2903For example, a grammar for the C language might specify these names with
2904equivalent literal string tokens:
2905
2906@example
2907%token <operator> OR "||"
2908%token <operator> LE 134 "<="
2909%left OR "<="
2910@end example
2911
2912@noindent
2913Once you equate the literal string and the token name, you can use them
2914interchangeably in further declarations or the grammar rules. The
2915@code{yylex} function can use the token name or the literal string to
2916obtain the token type code number (@pxref{Calling Convention}).
2917
2918@node Precedence Decl, Union Decl, Token Decl, Declarations
2919@subsection Operator Precedence
2920@cindex precedence declarations
2921@cindex declaring operator precedence
2922@cindex operator precedence, declaring
2923
2924Use the @code{%left}, @code{%right} or @code{%nonassoc} declaration to
2925declare a token and specify its precedence and associativity, all at
2926once. These are called @dfn{precedence declarations}.
2927@xref{Precedence, ,Operator Precedence}, for general information on operator precedence.
2928
2929The syntax of a precedence declaration is the same as that of
2930@code{%token}: either
2931
2932@example
2933%left @var{symbols}@dots{}
2934@end example
2935
2936@noindent
2937or
2938
2939@example
2940%left <@var{type}> @var{symbols}@dots{}
2941@end example
2942
2943And indeed any of these declarations serves the purposes of @code{%token}.
2944But in addition, they specify the associativity and relative precedence for
2945all the @var{symbols}:
2946
2947@itemize @bullet
2948@item
2949The associativity of an operator @var{op} determines how repeated uses
2950of the operator nest: whether @samp{@var{x} @var{op} @var{y} @var{op}
2951@var{z}} is parsed by grouping @var{x} with @var{y} first or by
2952grouping @var{y} with @var{z} first. @code{%left} specifies
2953left-associativity (grouping @var{x} with @var{y} first) and
2954@code{%right} specifies right-associativity (grouping @var{y} with
2955@var{z} first). @code{%nonassoc} specifies no associativity, which
2956means that @samp{@var{x} @var{op} @var{y} @var{op} @var{z}} is
2957considered a syntax error.
2958
2959@item
2960The precedence of an operator determines how it nests with other operators.
2961All the tokens declared in a single precedence declaration have equal
2962precedence and nest together according to their associativity.
2963When two tokens declared in different precedence declarations associate,
2964the one declared later has the higher precedence and is grouped first.
2965@end itemize
2966
2967@node Union Decl, Type Decl, Precedence Decl, Declarations
2968@subsection The Collection of Value Types
2969@cindex declaring value types
2970@cindex value types, declaring
2971@findex %union
2972
2973The @code{%union} declaration specifies the entire collection of possible
2974data types for semantic values. The keyword @code{%union} is followed by a
2975pair of braces containing the same thing that goes inside a @code{union} in
2976C.
2977
2978For example:
2979
2980@example
2981@group
2982%union @{
2983 double val;
2984 symrec *tptr;
2985@}
2986@end group
2987@end example
2988
2989@noindent
2990This says that the two alternative types are @code{double} and @code{symrec
2991*}. They are given names @code{val} and @code{tptr}; these names are used
2992in the @code{%token} and @code{%type} declarations to pick one of the types
2993for a terminal or nonterminal symbol (@pxref{Type Decl, ,Nonterminal Symbols}).
2994
2995Note that, unlike making a @code{union} declaration in C, you do not write
2996a semicolon after the closing brace.
2997
2998@node Type Decl, Expect Decl, Union Decl, Declarations
2999@subsection Nonterminal Symbols
3000@cindex declaring value types, nonterminals
3001@cindex value types, nonterminals, declaring
3002@findex %type
3003
3004@noindent
3005When you use @code{%union} to specify multiple value types, you must
3006declare the value type of each nonterminal symbol for which values are
3007used. This is done with a @code{%type} declaration, like this:
3008
3009@example
3010%type <@var{type}> @var{nonterminal}@dots{}
3011@end example
3012
3013@noindent
3014Here @var{nonterminal} is the name of a nonterminal symbol, and @var{type}
3015is the name given in the @code{%union} to the alternative that you want
3016(@pxref{Union Decl, ,The Collection of Value Types}). You can give any number of nonterminal symbols in
3017the same @code{%type} declaration, if they have the same value type. Use
3018spaces to separate the symbol names.
3019
3020You can also declare the value type of a terminal symbol. To do this,
3021use the same @code{<@var{type}>} construction in a declaration for the
3022terminal symbol. All kinds of token declarations allow
3023@code{<@var{type}>}.
3024
3025@node Expect Decl, Start Decl, Type Decl, Declarations
3026@subsection Suppressing Conflict Warnings
3027@cindex suppressing conflict warnings
3028@cindex preventing warnings about conflicts
3029@cindex warnings, preventing
3030@cindex conflicts, suppressing warnings of
3031@findex %expect
3032
3033Bison normally warns if there are any conflicts in the grammar
3034(@pxref{Shift/Reduce, ,Shift/Reduce Conflicts}), but most real grammars have harmless shift/reduce
3035conflicts which are resolved in a predictable way and would be difficult to
3036eliminate. It is desirable to suppress the warning about these conflicts
3037unless the number of conflicts changes. You can do this with the
3038@code{%expect} declaration.
3039
3040The declaration looks like this:
3041
3042@example
3043%expect @var{n}
3044@end example
3045
3046Here @var{n} is a decimal integer. The declaration says there should be no
3047warning if there are @var{n} shift/reduce conflicts and no reduce/reduce
3048conflicts. The usual warning is given if there are either more or fewer
3049conflicts, or if there are any reduce/reduce conflicts.
3050
3051In general, using @code{%expect} involves these steps:
3052
3053@itemize @bullet
3054@item
3055Compile your grammar without @code{%expect}. Use the @samp{-v} option
3056to get a verbose list of where the conflicts occur. Bison will also
3057print the number of conflicts.
3058
3059@item
3060Check each of the conflicts to make sure that Bison's default
3061resolution is what you really want. If not, rewrite the grammar and
3062go back to the beginning.
3063
3064@item
3065Add an @code{%expect} declaration, copying the number @var{n} from the
3066number which Bison printed.
3067@end itemize
3068
3069Now Bison will stop annoying you about the conflicts you have checked, but
3070it will warn you again if changes in the grammar result in additional
3071conflicts.
3072
3073@node Start Decl, Pure Decl, Expect Decl, Declarations
3074@subsection The Start-Symbol
3075@cindex declaring the start symbol
3076@cindex start symbol, declaring
3077@cindex default start symbol
3078@findex %start
3079
3080Bison assumes by default that the start symbol for the grammar is the first
3081nonterminal specified in the grammar specification section. The programmer
3082may override this restriction with the @code{%start} declaration as follows:
3083
3084@example
3085%start @var{symbol}
3086@end example
3087
3088@node Pure Decl, Decl Summary, Start Decl, Declarations
3089@subsection A Pure (Reentrant) Parser
3090@cindex reentrant parser
3091@cindex pure parser
3092@findex %pure_parser
3093
3094A @dfn{reentrant} program is one which does not alter in the course of
3095execution; in other words, it consists entirely of @dfn{pure} (read-only)
3096code. Reentrancy is important whenever asynchronous execution is possible;
3097for example, a nonreentrant program may not be safe to call from a signal
3098handler. In systems with multiple threads of control, a nonreentrant
3099program must be called only within interlocks.
3100
3101The Bison parser is not normally a reentrant program, because it uses
3102statically allocated variables for communication with @code{yylex}. These
3103variables include @code{yylval} and @code{yylloc}.
3104
3105The Bison declaration @code{%pure_parser} says that you want the parser
3106to be reentrant. It looks like this:
3107
3108@example
3109%pure_parser
3110@end example
3111
3112The effect is that the two communication variables become local
3113variables in @code{yyparse}, and a different calling convention is used
3114for the lexical analyzer function @code{yylex}. @xref{Pure Calling,
3115,Calling Conventions for Pure Parsers}, for the details of this. The
3116variable @code{yynerrs} also becomes local in @code{yyparse}
3117(@pxref{Error Reporting, ,The Error Reporting Function @code{yyerror}}).
3118The convention for calling @code{yyparse} itself is unchanged.
3119
3120@node Decl Summary, , Pure Decl, Declarations
3121@subsection Bison Declaration Summary
3122@cindex Bison declaration summary
3123@cindex declaration summary
3124@cindex summary, Bison declaration
3125
3126Here is a summary of all Bison declarations:
3127
3128@table @code
3129@item %union
3130Declare the collection of data types that semantic values may have
3131(@pxref{Union Decl, ,The Collection of Value Types}).
3132
3133@item %token
3134Declare a terminal symbol (token type name) with no precedence
3135or associativity specified (@pxref{Token Decl, ,Token Type Names}).
3136
3137@item %right
3138Declare a terminal symbol (token type name) that is right-associative
3139(@pxref{Precedence Decl, ,Operator Precedence}).
3140
3141@item %left
3142Declare a terminal symbol (token type name) that is left-associative
3143(@pxref{Precedence Decl, ,Operator Precedence}).
3144
3145@item %nonassoc
3146Declare a terminal symbol (token type name) that is nonassociative
3147(using it in a way that would be associative is a syntax error)
3148(@pxref{Precedence Decl, ,Operator Precedence}).
3149
3150@item %type
3151Declare the type of semantic values for a nonterminal symbol
3152(@pxref{Type Decl, ,Nonterminal Symbols}).
3153
3154@item %start
3155Specify the grammar's start symbol (@pxref{Start Decl, ,The Start-Symbol}).
3156
3157@item %expect
3158Declare the expected number of shift-reduce conflicts
3159(@pxref{Expect Decl, ,Suppressing Conflict Warnings}).
3160
3161@item %pure_parser
3162Request a pure (reentrant) parser program (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}).
3163
3164@item %no_lines
3165Don't generate any @code{#line} preprocessor commands in the parser
3166file. Ordinarily Bison writes these commands in the parser file so that
3167the C compiler and debuggers will associate errors and object code with
3168your source file (the grammar file). This directive causes them to
3169associate errors with the parser file, treating it an independent source
3170file in its own right.
3171
3172@item %raw
3173The output file @file{@var{name}.h} normally defines the tokens with
3174Yacc-compatible token numbers. If this option is specified, the
3175internal Bison numbers are used instead. (Yacc-compatible numbers start
3176at 257 except for single character tokens; Bison assigns token numbers
3177sequentially for all tokens starting at 3.)
3178
3179@item %token_table
3180Generate an array of token names in the parser file. The name of the
3181array is @code{yytname}; @code{yytname[@var{i}]} is the name of the
3182token whose internal Bison token code number is @var{i}. The first three
3183elements of @code{yytname} are always @code{"$"}, @code{"error"}, and
3184@code{"$illegal"}; after these come the symbols defined in the grammar
3185file.
3186
3187For single-character literal tokens and literal string tokens, the name
3188in the table includes the single-quote or double-quote characters: for
3189example, @code{"'+'"} is a single-character literal and @code{"\"<=\""}
3190is a literal string token. All the characters of the literal string
3191token appear verbatim in the string found in the table; even
3192double-quote characters are not escaped. For example, if the token
3193consists of three characters @samp{*"*}, its string in @code{yytname}
3194contains @samp{"*"*"}. (In C, that would be written as
3195@code{"\"*\"*\""}).
3196
3197When you specify @code{%token_table}, Bison also generates macro
3198definitions for macros @code{YYNTOKENS}, @code{YYNNTS}, and
3199@code{YYNRULES}, and @code{YYNSTATES}:
3200
3201@table @code
3202@item YYNTOKENS
3203The highest token number, plus one.
3204@item YYNNTS
3205The number of non-terminal symbols.
3206@item YYNRULES
3207The number of grammar rules,
3208@item YYNSTATES
3209The number of parser states (@pxref{Parser States}).
3210@end table
3211@end table
3212
3213@node Multiple Parsers,, Declarations, Grammar File
3214@section Multiple Parsers in the Same Program
3215
3216Most programs that use Bison parse only one language and therefore contain
3217only one Bison parser. But what if you want to parse more than one
3218language with the same program? Then you need to avoid a name conflict
3219between different definitions of @code{yyparse}, @code{yylval}, and so on.
3220
3221The easy way to do this is to use the option @samp{-p @var{prefix}}
3222(@pxref{Invocation, ,Invoking Bison}). This renames the interface functions and
3223variables of the Bison parser to start with @var{prefix} instead of
3224@samp{yy}. You can use this to give each parser distinct names that do
3225not conflict.
3226
3227The precise list of symbols renamed is @code{yyparse}, @code{yylex},
3228@code{yyerror}, @code{yynerrs}, @code{yylval}, @code{yychar} and
3229@code{yydebug}. For example, if you use @samp{-p c}, the names become
3230@code{cparse}, @code{clex}, and so on.
3231
3232@strong{All the other variables and macros associated with Bison are not
3233renamed.} These others are not global; there is no conflict if the same
3234name is used in different parsers. For example, @code{YYSTYPE} is not
3235renamed, but defining this in different ways in different parsers causes
3236no trouble (@pxref{Value Type, ,Data Types of Semantic Values}).
3237
3238The @samp{-p} option works by adding macro definitions to the beginning
3239of the parser source file, defining @code{yyparse} as
3240@code{@var{prefix}parse}, and so on. This effectively substitutes one
3241name for the other in the entire parser file.
3242
3243@node Interface, Algorithm, Grammar File, Top
3244@chapter Parser C-Language Interface
3245@cindex C-language interface
3246@cindex interface
3247
3248The Bison parser is actually a C function named @code{yyparse}. Here we
3249describe the interface conventions of @code{yyparse} and the other
3250functions that it needs to use.
3251
3252Keep in mind that the parser uses many C identifiers starting with
3253@samp{yy} and @samp{YY} for internal purposes. If you use such an
3254identifier (aside from those in this manual) in an action or in additional
3255C code in the grammar file, you are likely to run into trouble.
3256
3257@menu
3258* Parser Function:: How to call @code{yyparse} and what it returns.
3259* Lexical:: You must supply a function @code{yylex}
3260 which reads tokens.
3261* Error Reporting:: You must supply a function @code{yyerror}.
3262* Action Features:: Special features for use in actions.
3263@end menu
3264
3265@node Parser Function, Lexical, , Interface
3266@section The Parser Function @code{yyparse}
3267@findex yyparse
3268
3269You call the function @code{yyparse} to cause parsing to occur. This
3270function reads tokens, executes actions, and ultimately returns when it
3271encounters end-of-input or an unrecoverable syntax error. You can also
3272write an action which directs @code{yyparse} to return immediately without
3273reading further.
3274
3275The value returned by @code{yyparse} is 0 if parsing was successful (return
3276is due to end-of-input).
3277
3278The value is 1 if parsing failed (return is due to a syntax error).
3279
3280In an action, you can cause immediate return from @code{yyparse} by using
3281these macros:
3282
3283@table @code
3284@item YYACCEPT
3285@findex YYACCEPT
3286Return immediately with value 0 (to report success).
3287
3288@item YYABORT
3289@findex YYABORT
3290Return immediately with value 1 (to report failure).
3291@end table
3292
3293@node Lexical, Error Reporting, Parser Function, Interface
3294@section The Lexical Analyzer Function @code{yylex}
3295@findex yylex
3296@cindex lexical analyzer
3297
3298The @dfn{lexical analyzer} function, @code{yylex}, recognizes tokens from
3299the input stream and returns them to the parser. Bison does not create
3300this function automatically; you must write it so that @code{yyparse} can
3301call it. The function is sometimes referred to as a lexical scanner.
3302
3303In simple programs, @code{yylex} is often defined at the end of the Bison
3304grammar file. If @code{yylex} is defined in a separate source file, you
3305need to arrange for the token-type macro definitions to be available there.
3306To do this, use the @samp{-d} option when you run Bison, so that it will
3307write these macro definitions into a separate header file
3308@file{@var{name}.tab.h} which you can include in the other source files
3309that need it. @xref{Invocation, ,Invoking Bison}.@refill
3310
3311@menu
3312* Calling Convention:: How @code{yyparse} calls @code{yylex}.
3313* Token Values:: How @code{yylex} must return the semantic value
3314 of the token it has read.
3315* Token Positions:: How @code{yylex} must return the text position
3316 (line number, etc.) of the token, if the
3317 actions want that.
3318* Pure Calling:: How the calling convention differs
3319 in a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}).
3320@end menu
3321
3322@node Calling Convention, Token Values, , Lexical
3323@subsection Calling Convention for @code{yylex}
3324
3325The value that @code{yylex} returns must be the numeric code for the type
3326of token it has just found, or 0 for end-of-input.
3327
3328When a token is referred to in the grammar rules by a name, that name
3329in the parser file becomes a C macro whose definition is the proper
3330numeric code for that token type. So @code{yylex} can use the name
3331to indicate that type. @xref{Symbols}.
3332
3333When a token is referred to in the grammar rules by a character literal,
3334the numeric code for that character is also the code for the token type.
3335So @code{yylex} can simply return that character code. The null character
3336must not be used this way, because its code is zero and that is what
3337signifies end-of-input.
3338
3339Here is an example showing these things:
3340
3341@example
3342yylex ()
3343@{
3344 @dots{}
3345 if (c == EOF) /* Detect end of file. */
3346 return 0;
3347 @dots{}
3348 if (c == '+' || c == '-')
3349 return c; /* Assume token type for `+' is '+'. */
3350 @dots{}
3351 return INT; /* Return the type of the token. */
3352 @dots{}
3353@}
3354@end example
3355
3356@noindent
3357This interface has been designed so that the output from the @code{lex}
3358utility can be used without change as the definition of @code{yylex}.
3359
3360If the grammar uses literal string tokens, there are two ways that
3361@code{yylex} can determine the token type codes for them:
3362
3363@itemize @bullet
3364@item
3365If the grammar defines symbolic token names as aliases for the
3366literal string tokens, @code{yylex} can use these symbolic names like
3367all others. In this case, the use of the literal string tokens in
3368the grammar file has no effect on @code{yylex}.
3369
3370@item
3371@code{yylex} can find the multi-character token in the @code{yytname}
3372table. The index of the token in the table is the token type's code.
3373The name of a multi-character token is recorded in @code{yytname} with a
3374double-quote, the token's characters, and another double-quote. The
3375token's characters are not escaped in any way; they appear verbatim in
3376the contents of the string in the table.
3377
3378Here's code for looking up a token in @code{yytname}, assuming that the
3379characters of the token are stored in @code{token_buffer}.
3380
3381@smallexample
3382for (i = 0; i < YYNTOKENS; i++)
3383 @{
3384 if (yytname[i] != 0
3385 && yytname[i][0] == '"'
3386 && strncmp (yytname[i] + 1, token_buffer, strlen (token_buffer))
3387 && yytname[i][strlen (token_buffer) + 1] == '"'
3388 && yytname[i][strlen (token_buffer) + 2] == 0)
3389 break;
3390 @}
3391@end smallexample
3392
3393The @code{yytname} table is generated only if you use the
3394@code{%token_table} declaration. @xref{Decl Summary}.
3395@end itemize
3396
3397@node Token Values, Token Positions, Calling Convention, Lexical
3398@subsection Semantic Values of Tokens
3399
3400@vindex yylval
3401In an ordinary (nonreentrant) parser, the semantic value of the token must
3402be stored into the global variable @code{yylval}. When you are using
3403just one data type for semantic values, @code{yylval} has that type.
3404Thus, if the type is @code{int} (the default), you might write this in
3405@code{yylex}:
3406
3407@example
3408@group
3409 @dots{}
3410 yylval = value; /* Put value onto Bison stack. */
3411 return INT; /* Return the type of the token. */
3412 @dots{}
3413@end group
3414@end example
3415
3416When you are using multiple data types, @code{yylval}'s type is a union
3417made from the @code{%union} declaration (@pxref{Union Decl, ,The Collection of Value Types}). So when
3418you store a token's value, you must use the proper member of the union.
3419If the @code{%union} declaration looks like this:
3420
3421@example
3422@group
3423%union @{
3424 int intval;
3425 double val;
3426 symrec *tptr;
3427@}
3428@end group
3429@end example
3430
3431@noindent
3432then the code in @code{yylex} might look like this:
3433
3434@example
3435@group
3436 @dots{}
3437 yylval.intval = value; /* Put value onto Bison stack. */
3438 return INT; /* Return the type of the token. */
3439 @dots{}
3440@end group
3441@end example
3442
3443@node Token Positions, Pure Calling, Token Values, Lexical
3444@subsection Textual Positions of Tokens
3445
3446@vindex yylloc
3447If you are using the @samp{@@@var{n}}-feature (@pxref{Action Features, ,Special Features for Use in Actions}) in
3448actions to keep track of the textual locations of tokens and groupings,
3449then you must provide this information in @code{yylex}. The function
3450@code{yyparse} expects to find the textual location of a token just parsed
3451in the global variable @code{yylloc}. So @code{yylex} must store the
3452proper data in that variable. The value of @code{yylloc} is a structure
3453and you need only initialize the members that are going to be used by the
3454actions. The four members are called @code{first_line},
3455@code{first_column}, @code{last_line} and @code{last_column}. Note that
3456the use of this feature makes the parser noticeably slower.
3457
3458@tindex YYLTYPE
3459The data type of @code{yylloc} has the name @code{YYLTYPE}.
3460
3461@node Pure Calling, , Token Positions, Lexical
3462@subsection Calling Conventions for Pure Parsers
3463
3464When you use the Bison declaration @code{%pure_parser} to request a
3465pure, reentrant parser, the global communication variables @code{yylval}
3466and @code{yylloc} cannot be used. (@xref{Pure Decl, ,A Pure (Reentrant)
3467Parser}.) In such parsers the two global variables are replaced by
3468pointers passed as arguments to @code{yylex}. You must declare them as
3469shown here, and pass the information back by storing it through those
3470pointers.
3471
3472@example
3473yylex (lvalp, llocp)
3474 YYSTYPE *lvalp;
3475 YYLTYPE *llocp;
3476@{
3477 @dots{}
3478 *lvalp = value; /* Put value onto Bison stack. */
3479 return INT; /* Return the type of the token. */
3480 @dots{}
3481@}
3482@end example
3483
3484If the grammar file does not use the @samp{@@} constructs to refer to
3485textual positions, then the type @code{YYLTYPE} will not be defined. In
3486this case, omit the second argument; @code{yylex} will be called with
3487only one argument.
3488
3489@vindex YYPARSE_PARAM
3490If you use a reentrant parser, you can optionally pass additional
3491parameter information to it in a reentrant way. To do so, define the
3492macro @code{YYPARSE_PARAM} as a variable name. This modifies the
3493@code{yyparse} function to accept one argument, of type @code{void *},
3494with that name.
3495
3496When you call @code{yyparse}, pass the address of an object, casting the
3497address to @code{void *}. The grammar actions can refer to the contents
3498of the object by casting the pointer value back to its proper type and
3499then dereferencing it. Here's an example. Write this in the parser:
3500
3501@example
3502%@{
3503struct parser_control
3504@{
3505 int nastiness;
3506 int randomness;
3507@};
3508
3509#define YYPARSE_PARAM parm
3510%@}
3511@end example
3512
3513@noindent
3514Then call the parser like this:
3515
3516@example
3517struct parser_control
3518@{
3519 int nastiness;
3520 int randomness;
3521@};
3522
3523@dots{}
3524
3525@{
3526 struct parser_control foo;
3527 @dots{} /* @r{Store proper data in @code{foo}.} */
3528 value = yyparse ((void *) &foo);
3529 @dots{}
3530@}
3531@end example
3532
3533@noindent
3534In the grammar actions, use expressions like this to refer to the data:
3535
3536@example
3537((struct parser_control *) parm)->randomness
3538@end example
3539
3540@vindex YYLEX_PARAM
3541If you wish to pass the additional parameter data to @code{yylex},
3542define the macro @code{YYLEX_PARAM} just like @code{YYPARSE_PARAM}, as
3543shown here:
3544
3545@example
3546%@{
3547struct parser_control
3548@{
3549 int nastiness;
3550 int randomness;
3551@};
3552
3553#define YYPARSE_PARAM parm
3554#define YYLEX_PARAM parm
3555%@}
3556@end example
3557
3558You should then define @code{yylex} to accept one additional
3559argument---the value of @code{parm}. (This makes either two or three
3560arguments in total, depending on whether an argument of type
3561@code{YYLTYPE} is passed.) You can declare the argument as a pointer to
3562the proper object type, or you can declare it as @code{void *} and
3563access the contents as shown above.
3564
3565You can use @samp{%pure_parser} to request a reentrant parser without
3566also using @code{YYPARSE_PARAM}. Then you should call @code{yyparse}
3567with no arguments, as usual.
3568
3569@node Error Reporting, Action Features, Lexical, Interface
3570@section The Error Reporting Function @code{yyerror}
3571@cindex error reporting function
3572@findex yyerror
3573@cindex parse error
3574@cindex syntax error
3575
3576The Bison parser detects a @dfn{parse error} or @dfn{syntax error}
3577whenever it reads a token which cannot satisfy any syntax rule. A
3578action in the grammar can also explicitly proclaim an error, using the
3579macro @code{YYERROR} (@pxref{Action Features, ,Special Features for Use in Actions}).
3580
3581The Bison parser expects to report the error by calling an error
3582reporting function named @code{yyerror}, which you must supply. It is
3583called by @code{yyparse} whenever a syntax error is found, and it
3584receives one argument. For a parse error, the string is normally
3585@w{@code{"parse error"}}.
3586
3587@findex YYERROR_VERBOSE
3588If you define the macro @code{YYERROR_VERBOSE} in the Bison declarations
3589section (@pxref{Bison Declarations, ,The Bison Declarations Section}), then Bison provides a more verbose
3590and specific error message string instead of just plain @w{@code{"parse
3591error"}}. It doesn't matter what definition you use for
3592@code{YYERROR_VERBOSE}, just whether you define it.
3593
3594The parser can detect one other kind of error: stack overflow. This
3595happens when the input contains constructions that are very deeply
3596nested. It isn't likely you will encounter this, since the Bison
3597parser extends its stack automatically up to a very large limit. But
3598if overflow happens, @code{yyparse} calls @code{yyerror} in the usual
3599fashion, except that the argument string is @w{@code{"parser stack
3600overflow"}}.
3601
3602The following definition suffices in simple programs:
3603
3604@example
3605@group
3606yyerror (s)
3607 char *s;
3608@{
3609@end group
3610@group
3611 fprintf (stderr, "%s\n", s);
3612@}
3613@end group
3614@end example
3615
3616After @code{yyerror} returns to @code{yyparse}, the latter will attempt
3617error recovery if you have written suitable error recovery grammar rules
3618(@pxref{Error Recovery}). If recovery is impossible, @code{yyparse} will
3619immediately return 1.
3620
3621@vindex yynerrs
3622The variable @code{yynerrs} contains the number of syntax errors
3623encountered so far. Normally this variable is global; but if you
3624request a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}) then it is a local variable
3625which only the actions can access.
3626
3627@node Action Features, , Error Reporting, Interface
3628@section Special Features for Use in Actions
3629@cindex summary, action features
3630@cindex action features summary
3631
3632Here is a table of Bison constructs, variables and macros that
3633are useful in actions.
3634
3635@table @samp
3636@item $$
3637Acts like a variable that contains the semantic value for the
3638grouping made by the current rule. @xref{Actions}.
3639
3640@item $@var{n}
3641Acts like a variable that contains the semantic value for the
3642@var{n}th component of the current rule. @xref{Actions}.
3643
3644@item $<@var{typealt}>$
3645Like @code{$$} but specifies alternative @var{typealt} in the union
3646specified by the @code{%union} declaration. @xref{Action Types, ,Data Types of Values in Actions}.
3647
3648@item $<@var{typealt}>@var{n}
3649Like @code{$@var{n}} but specifies alternative @var{typealt} in the
3650union specified by the @code{%union} declaration.
3651@xref{Action Types, ,Data Types of Values in Actions}.@refill
3652
3653@item YYABORT;
3654Return immediately from @code{yyparse}, indicating failure.
3655@xref{Parser Function, ,The Parser Function @code{yyparse}}.
3656
3657@item YYACCEPT;
3658Return immediately from @code{yyparse}, indicating success.
3659@xref{Parser Function, ,The Parser Function @code{yyparse}}.
3660
3661@item YYBACKUP (@var{token}, @var{value});
3662@findex YYBACKUP
3663Unshift a token. This macro is allowed only for rules that reduce
3664a single value, and only when there is no look-ahead token.
3665It installs a look-ahead token with token type @var{token} and
3666semantic value @var{value}; then it discards the value that was
3667going to be reduced by this rule.
3668
3669If the macro is used when it is not valid, such as when there is
3670a look-ahead token already, then it reports a syntax error with
3671a message @samp{cannot back up} and performs ordinary error
3672recovery.
3673
3674In either case, the rest of the action is not executed.
3675
3676@item YYEMPTY
3677@vindex YYEMPTY
3678Value stored in @code{yychar} when there is no look-ahead token.
3679
3680@item YYERROR;
3681@findex YYERROR
3682Cause an immediate syntax error. This statement initiates error
3683recovery just as if the parser itself had detected an error; however, it
3684does not call @code{yyerror}, and does not print any message. If you
3685want to print an error message, call @code{yyerror} explicitly before
3686the @samp{YYERROR;} statement. @xref{Error Recovery}.
3687
3688@item YYRECOVERING
3689This macro stands for an expression that has the value 1 when the parser
3690is recovering from a syntax error, and 0 the rest of the time.
3691@xref{Error Recovery}.
3692
3693@item yychar
3694Variable containing the current look-ahead token. (In a pure parser,
3695this is actually a local variable within @code{yyparse}.) When there is
3696no look-ahead token, the value @code{YYEMPTY} is stored in the variable.
3697@xref{Look-Ahead, ,Look-Ahead Tokens}.
3698
3699@item yyclearin;
3700Discard the current look-ahead token. This is useful primarily in
3701error rules. @xref{Error Recovery}.
3702
3703@item yyerrok;
3704Resume generating error messages immediately for subsequent syntax
3705errors. This is useful primarily in error rules.
3706@xref{Error Recovery}.
3707
3708@item @@@var{n}
3709@findex @@@var{n}
3710Acts like a structure variable containing information on the line
3711numbers and column numbers of the @var{n}th component of the current
3712rule. The structure has four members, like this:
3713
3714@example
3715struct @{
3716 int first_line, last_line;
3717 int first_column, last_column;
3718@};
3719@end example
3720
3721Thus, to get the starting line number of the third component, use
3722@samp{@@3.first_line}.
3723
3724In order for the members of this structure to contain valid information,
3725you must make @code{yylex} supply this information about each token.
3726If you need only certain members, then @code{yylex} need only fill in
3727those members.
3728
3729The use of this feature makes the parser noticeably slower.
3730@end table
3731
3732@node Algorithm, Error Recovery, Interface, Top
3733@chapter The Bison Parser Algorithm
3734@cindex Bison parser algorithm
3735@cindex algorithm of parser
3736@cindex shifting
3737@cindex reduction
3738@cindex parser stack
3739@cindex stack, parser
3740
3741As Bison reads tokens, it pushes them onto a stack along with their
3742semantic values. The stack is called the @dfn{parser stack}. Pushing a
3743token is traditionally called @dfn{shifting}.
3744
3745For example, suppose the infix calculator has read @samp{1 + 5 *}, with a
3746@samp{3} to come. The stack will have four elements, one for each token
3747that was shifted.
3748
3749But the stack does not always have an element for each token read. When
3750the last @var{n} tokens and groupings shifted match the components of a
3751grammar rule, they can be combined according to that rule. This is called
3752@dfn{reduction}. Those tokens and groupings are replaced on the stack by a
3753single grouping whose symbol is the result (left hand side) of that rule.
3754Running the rule's action is part of the process of reduction, because this
3755is what computes the semantic value of the resulting grouping.
3756
3757For example, if the infix calculator's parser stack contains this:
3758
3759@example
37601 + 5 * 3
3761@end example
3762
3763@noindent
3764and the next input token is a newline character, then the last three
3765elements can be reduced to 15 via the rule:
3766
3767@example
3768expr: expr '*' expr;
3769@end example
3770
3771@noindent
3772Then the stack contains just these three elements:
3773
3774@example
37751 + 15
3776@end example
3777
3778@noindent
3779At this point, another reduction can be made, resulting in the single value
378016. Then the newline token can be shifted.
3781
3782The parser tries, by shifts and reductions, to reduce the entire input down
3783to a single grouping whose symbol is the grammar's start-symbol
3784(@pxref{Language and Grammar, ,Languages and Context-Free Grammars}).
3785
3786This kind of parser is known in the literature as a bottom-up parser.
3787
3788@menu
3789* Look-Ahead:: Parser looks one token ahead when deciding what to do.
3790* Shift/Reduce:: Conflicts: when either shifting or reduction is valid.
3791* Precedence:: Operator precedence works by resolving conflicts.
3792* Contextual Precedence:: When an operator's precedence depends on context.
3793* Parser States:: The parser is a finite-state-machine with stack.
3794* Reduce/Reduce:: When two rules are applicable in the same situation.
3795* Mystery Conflicts:: Reduce/reduce conflicts that look unjustified.
3796* Stack Overflow:: What happens when stack gets full. How to avoid it.
3797@end menu
3798
3799@node Look-Ahead, Shift/Reduce, , Algorithm
3800@section Look-Ahead Tokens
3801@cindex look-ahead token
3802
3803The Bison parser does @emph{not} always reduce immediately as soon as the
3804last @var{n} tokens and groupings match a rule. This is because such a
3805simple strategy is inadequate to handle most languages. Instead, when a
3806reduction is possible, the parser sometimes ``looks ahead'' at the next
3807token in order to decide what to do.
3808
3809When a token is read, it is not immediately shifted; first it becomes the
3810@dfn{look-ahead token}, which is not on the stack. Now the parser can
3811perform one or more reductions of tokens and groupings on the stack, while
3812the look-ahead token remains off to the side. When no more reductions
3813should take place, the look-ahead token is shifted onto the stack. This
3814does not mean that all possible reductions have been done; depending on the
3815token type of the look-ahead token, some rules may choose to delay their
3816application.
3817
3818Here is a simple case where look-ahead is needed. These three rules define
3819expressions which contain binary addition operators and postfix unary
3820factorial operators (@samp{!}), and allow parentheses for grouping.
3821
3822@example
3823@group
3824expr: term '+' expr
3825 | term
3826 ;
3827@end group
3828
3829@group
3830term: '(' expr ')'
3831 | term '!'
3832 | NUMBER
3833 ;
3834@end group
3835@end example
3836
3837Suppose that the tokens @w{@samp{1 + 2}} have been read and shifted; what
3838should be done? If the following token is @samp{)}, then the first three
3839tokens must be reduced to form an @code{expr}. This is the only valid
3840course, because shifting the @samp{)} would produce a sequence of symbols
3841@w{@code{term ')'}}, and no rule allows this.
3842
3843If the following token is @samp{!}, then it must be shifted immediately so
3844that @w{@samp{2 !}} can be reduced to make a @code{term}. If instead the
3845parser were to reduce before shifting, @w{@samp{1 + 2}} would become an
3846@code{expr}. It would then be impossible to shift the @samp{!} because
3847doing so would produce on the stack the sequence of symbols @code{expr
3848'!'}. No rule allows that sequence.
3849
3850@vindex yychar
3851The current look-ahead token is stored in the variable @code{yychar}.
3852@xref{Action Features, ,Special Features for Use in Actions}.
3853
3854@node Shift/Reduce, Precedence, Look-Ahead, Algorithm
3855@section Shift/Reduce Conflicts
3856@cindex conflicts
3857@cindex shift/reduce conflicts
3858@cindex dangling @code{else}
3859@cindex @code{else}, dangling
3860
3861Suppose we are parsing a language which has if-then and if-then-else
3862statements, with a pair of rules like this:
3863
3864@example
3865@group
3866if_stmt:
3867 IF expr THEN stmt
3868 | IF expr THEN stmt ELSE stmt
3869 ;
3870@end group
3871@end example
3872
3873@noindent
3874Here we assume that @code{IF}, @code{THEN} and @code{ELSE} are
3875terminal symbols for specific keyword tokens.
3876
3877When the @code{ELSE} token is read and becomes the look-ahead token, the
3878contents of the stack (assuming the input is valid) are just right for
3879reduction by the first rule. But it is also legitimate to shift the
3880@code{ELSE}, because that would lead to eventual reduction by the second
3881rule.
3882
3883This situation, where either a shift or a reduction would be valid, is
3884called a @dfn{shift/reduce conflict}. Bison is designed to resolve
3885these conflicts by choosing to shift, unless otherwise directed by
3886operator precedence declarations. To see the reason for this, let's
3887contrast it with the other alternative.
3888
3889Since the parser prefers to shift the @code{ELSE}, the result is to attach
3890the else-clause to the innermost if-statement, making these two inputs
3891equivalent:
3892
3893@example
3894if x then if y then win (); else lose;
3895
3896if x then do; if y then win (); else lose; end;
3897@end example
3898
3899But if the parser chose to reduce when possible rather than shift, the
3900result would be to attach the else-clause to the outermost if-statement,
3901making these two inputs equivalent:
3902
3903@example
3904if x then if y then win (); else lose;
3905
3906if x then do; if y then win (); end; else lose;
3907@end example
3908
3909The conflict exists because the grammar as written is ambiguous: either
3910parsing of the simple nested if-statement is legitimate. The established
3911convention is that these ambiguities are resolved by attaching the
3912else-clause to the innermost if-statement; this is what Bison accomplishes
3913by choosing to shift rather than reduce. (It would ideally be cleaner to
3914write an unambiguous grammar, but that is very hard to do in this case.)
3915This particular ambiguity was first encountered in the specifications of
3916Algol 60 and is called the ``dangling @code{else}'' ambiguity.
3917
3918To avoid warnings from Bison about predictable, legitimate shift/reduce
3919conflicts, use the @code{%expect @var{n}} declaration. There will be no
3920warning as long as the number of shift/reduce conflicts is exactly @var{n}.
3921@xref{Expect Decl, ,Suppressing Conflict Warnings}.
3922
3923The definition of @code{if_stmt} above is solely to blame for the
3924conflict, but the conflict does not actually appear without additional
3925rules. Here is a complete Bison input file that actually manifests the
3926conflict:
3927
3928@example
3929@group
3930%token IF THEN ELSE variable
3931%%
3932@end group
3933@group
3934stmt: expr
3935 | if_stmt
3936 ;
3937@end group
3938
3939@group
3940if_stmt:
3941 IF expr THEN stmt
3942 | IF expr THEN stmt ELSE stmt
3943 ;
3944@end group
3945
3946expr: variable
3947 ;
3948@end example
3949
3950@node Precedence, Contextual Precedence, Shift/Reduce, Algorithm
3951@section Operator Precedence
3952@cindex operator precedence
3953@cindex precedence of operators
3954
3955Another situation where shift/reduce conflicts appear is in arithmetic
3956expressions. Here shifting is not always the preferred resolution; the
3957Bison declarations for operator precedence allow you to specify when to
3958shift and when to reduce.
3959
3960@menu
3961* Why Precedence:: An example showing why precedence is needed.
3962* Using Precedence:: How to specify precedence in Bison grammars.
3963* Precedence Examples:: How these features are used in the previous example.
3964* How Precedence:: How they work.
3965@end menu
3966
3967@node Why Precedence, Using Precedence, , Precedence
3968@subsection When Precedence is Needed
3969
3970Consider the following ambiguous grammar fragment (ambiguous because the
3971input @w{@samp{1 - 2 * 3}} can be parsed in two different ways):
3972
3973@example
3974@group
3975expr: expr '-' expr
3976 | expr '*' expr
3977 | expr '<' expr
3978 | '(' expr ')'
3979 @dots{}
3980 ;
3981@end group
3982@end example
3983
3984@noindent
3985Suppose the parser has seen the tokens @samp{1}, @samp{-} and @samp{2};
3986should it reduce them via the rule for the addition operator? It depends
3987on the next token. Of course, if the next token is @samp{)}, we must
3988reduce; shifting is invalid because no single rule can reduce the token
3989sequence @w{@samp{- 2 )}} or anything starting with that. But if the next
3990token is @samp{*} or @samp{<}, we have a choice: either shifting or
3991reduction would allow the parse to complete, but with different
3992results.
3993
3994To decide which one Bison should do, we must consider the
3995results. If the next operator token @var{op} is shifted, then it
3996must be reduced first in order to permit another opportunity to
3997reduce the sum. The result is (in effect) @w{@samp{1 - (2
3998@var{op} 3)}}. On the other hand, if the subtraction is reduced
3999before shifting @var{op}, the result is @w{@samp{(1 - 2) @var{op}
40003}}. Clearly, then, the choice of shift or reduce should depend
4001on the relative precedence of the operators @samp{-} and
4002@var{op}: @samp{*} should be shifted first, but not @samp{<}.
4003
4004@cindex associativity
4005What about input such as @w{@samp{1 - 2 - 5}}; should this be
4006@w{@samp{(1 - 2) - 5}} or should it be @w{@samp{1 - (2 - 5)}}? For
4007most operators we prefer the former, which is called @dfn{left
4008association}. The latter alternative, @dfn{right association}, is
4009desirable for assignment operators. The choice of left or right
4010association is a matter of whether the parser chooses to shift or
4011reduce when the stack contains @w{@samp{1 - 2}} and the look-ahead
4012token is @samp{-}: shifting makes right-associativity.
4013
4014@node Using Precedence, Precedence Examples, Why Precedence, Precedence
4015@subsection Specifying Operator Precedence
4016@findex %left
4017@findex %right
4018@findex %nonassoc
4019
4020Bison allows you to specify these choices with the operator precedence
4021declarations @code{%left} and @code{%right}. Each such declaration
4022contains a list of tokens, which are operators whose precedence and
4023associativity is being declared. The @code{%left} declaration makes all
4024those operators left-associative and the @code{%right} declaration makes
4025them right-associative. A third alternative is @code{%nonassoc}, which
4026declares that it is a syntax error to find the same operator twice ``in a
4027row''.
4028
4029The relative precedence of different operators is controlled by the
4030order in which they are declared. The first @code{%left} or
4031@code{%right} declaration in the file declares the operators whose
4032precedence is lowest, the next such declaration declares the operators
4033whose precedence is a little higher, and so on.
4034
4035@node Precedence Examples, How Precedence, Using Precedence, Precedence
4036@subsection Precedence Examples
4037
4038In our example, we would want the following declarations:
4039
4040@example
4041%left '<'
4042%left '-'
4043%left '*'
4044@end example
4045
4046In a more complete example, which supports other operators as well, we
4047would declare them in groups of equal precedence. For example, @code{'+'} is
4048declared with @code{'-'}:
4049
4050@example
4051%left '<' '>' '=' NE LE GE
4052%left '+' '-'
4053%left '*' '/'
4054@end example
4055
4056@noindent
4057(Here @code{NE} and so on stand for the operators for ``not equal''
4058and so on. We assume that these tokens are more than one character long
4059and therefore are represented by names, not character literals.)
4060
4061@node How Precedence, , Precedence Examples, Precedence
4062@subsection How Precedence Works
4063
4064The first effect of the precedence declarations is to assign precedence
4065levels to the terminal symbols declared. The second effect is to assign
4066precedence levels to certain rules: each rule gets its precedence from the
4067last terminal symbol mentioned in the components. (You can also specify
4068explicitly the precedence of a rule. @xref{Contextual Precedence, ,Context-Dependent Precedence}.)
4069
4070Finally, the resolution of conflicts works by comparing the
4071precedence of the rule being considered with that of the
4072look-ahead token. If the token's precedence is higher, the
4073choice is to shift. If the rule's precedence is higher, the
4074choice is to reduce. If they have equal precedence, the choice
4075is made based on the associativity of that precedence level. The
4076verbose output file made by @samp{-v} (@pxref{Invocation, ,Invoking Bison}) says
4077how each conflict was resolved.
4078
4079Not all rules and not all tokens have precedence. If either the rule or
4080the look-ahead token has no precedence, then the default is to shift.
4081
4082@node Contextual Precedence, Parser States, Precedence, Algorithm
4083@section Context-Dependent Precedence
4084@cindex context-dependent precedence
4085@cindex unary operator precedence
4086@cindex precedence, context-dependent
4087@cindex precedence, unary operator
4088@findex %prec
4089
4090Often the precedence of an operator depends on the context. This sounds
4091outlandish at first, but it is really very common. For example, a minus
4092sign typically has a very high precedence as a unary operator, and a
4093somewhat lower precedence (lower than multiplication) as a binary operator.
4094
4095The Bison precedence declarations, @code{%left}, @code{%right} and
4096@code{%nonassoc}, can only be used once for a given token; so a token has
4097only one precedence declared in this way. For context-dependent
4098precedence, you need to use an additional mechanism: the @code{%prec}
4099modifier for rules.@refill
4100
4101The @code{%prec} modifier declares the precedence of a particular rule by
4102specifying a terminal symbol whose precedence should be used for that rule.
4103It's not necessary for that symbol to appear otherwise in the rule. The
4104modifier's syntax is:
4105
4106@example
4107%prec @var{terminal-symbol}
4108@end example
4109
4110@noindent
4111and it is written after the components of the rule. Its effect is to
4112assign the rule the precedence of @var{terminal-symbol}, overriding
4113the precedence that would be deduced for it in the ordinary way. The
4114altered rule precedence then affects how conflicts involving that rule
4115are resolved (@pxref{Precedence, ,Operator Precedence}).
4116
4117Here is how @code{%prec} solves the problem of unary minus. First, declare
4118a precedence for a fictitious terminal symbol named @code{UMINUS}. There
4119are no tokens of this type, but the symbol serves to stand for its
4120precedence:
4121
4122@example
4123@dots{}
4124%left '+' '-'
4125%left '*'
4126%left UMINUS
4127@end example
4128
4129Now the precedence of @code{UMINUS} can be used in specific rules:
4130
4131@example
4132@group
4133exp: @dots{}
4134 | exp '-' exp
4135 @dots{}
4136 | '-' exp %prec UMINUS
4137@end group
4138@end example
4139
4140@node Parser States, Reduce/Reduce, Contextual Precedence, Algorithm
4141@section Parser States
4142@cindex finite-state machine
4143@cindex parser state
4144@cindex state (of parser)
4145
4146The function @code{yyparse} is implemented using a finite-state machine.
4147The values pushed on the parser stack are not simply token type codes; they
4148represent the entire sequence of terminal and nonterminal symbols at or
4149near the top of the stack. The current state collects all the information
4150about previous input which is relevant to deciding what to do next.
4151
4152Each time a look-ahead token is read, the current parser state together
4153with the type of look-ahead token are looked up in a table. This table
4154entry can say, ``Shift the look-ahead token.'' In this case, it also
4155specifies the new parser state, which is pushed onto the top of the
4156parser stack. Or it can say, ``Reduce using rule number @var{n}.''
4157This means that a certain number of tokens or groupings are taken off
4158the top of the stack, and replaced by one grouping. In other words,
4159that number of states are popped from the stack, and one new state is
4160pushed.
4161
4162There is one other alternative: the table can say that the look-ahead token
4163is erroneous in the current state. This causes error processing to begin
4164(@pxref{Error Recovery}).
4165
4166@node Reduce/Reduce, Mystery Conflicts, Parser States, Algorithm
4167@section Reduce/Reduce Conflicts
4168@cindex reduce/reduce conflict
4169@cindex conflicts, reduce/reduce
4170
4171A reduce/reduce conflict occurs if there are two or more rules that apply
4172to the same sequence of input. This usually indicates a serious error
4173in the grammar.
4174
4175For example, here is an erroneous attempt to define a sequence
4176of zero or more @code{word} groupings.
4177
4178@example
4179sequence: /* empty */
4180 @{ printf ("empty sequence\n"); @}
4181 | maybeword
4182 | sequence word
4183 @{ printf ("added word %s\n", $2); @}
4184 ;
4185
4186maybeword: /* empty */
4187 @{ printf ("empty maybeword\n"); @}
4188 | word
4189 @{ printf ("single word %s\n", $1); @}
4190 ;
4191@end example
4192
4193@noindent
4194The error is an ambiguity: there is more than one way to parse a single
4195@code{word} into a @code{sequence}. It could be reduced to a
4196@code{maybeword} and then into a @code{sequence} via the second rule.
4197Alternatively, nothing-at-all could be reduced into a @code{sequence}
4198via the first rule, and this could be combined with the @code{word}
4199using the third rule for @code{sequence}.
4200
4201There is also more than one way to reduce nothing-at-all into a
4202@code{sequence}. This can be done directly via the first rule,
4203or indirectly via @code{maybeword} and then the second rule.
4204
4205You might think that this is a distinction without a difference, because it
4206does not change whether any particular input is valid or not. But it does
4207affect which actions are run. One parsing order runs the second rule's
4208action; the other runs the first rule's action and the third rule's action.
4209In this example, the output of the program changes.
4210
4211Bison resolves a reduce/reduce conflict by choosing to use the rule that
4212appears first in the grammar, but it is very risky to rely on this. Every
4213reduce/reduce conflict must be studied and usually eliminated. Here is the
4214proper way to define @code{sequence}:
4215
4216@example
4217sequence: /* empty */
4218 @{ printf ("empty sequence\n"); @}
4219 | sequence word
4220 @{ printf ("added word %s\n", $2); @}
4221 ;
4222@end example
4223
4224Here is another common error that yields a reduce/reduce conflict:
4225
4226@example
4227sequence: /* empty */
4228 | sequence words
4229 | sequence redirects
4230 ;
4231
4232words: /* empty */
4233 | words word
4234 ;
4235
4236redirects:/* empty */
4237 | redirects redirect
4238 ;
4239@end example
4240
4241@noindent
4242The intention here is to define a sequence which can contain either
4243@code{word} or @code{redirect} groupings. The individual definitions of
4244@code{sequence}, @code{words} and @code{redirects} are error-free, but the
4245three together make a subtle ambiguity: even an empty input can be parsed
4246in infinitely many ways!
4247
4248Consider: nothing-at-all could be a @code{words}. Or it could be two
4249@code{words} in a row, or three, or any number. It could equally well be a
4250@code{redirects}, or two, or any number. Or it could be a @code{words}
4251followed by three @code{redirects} and another @code{words}. And so on.
4252
4253Here are two ways to correct these rules. First, to make it a single level
4254of sequence:
4255
4256@example
4257sequence: /* empty */
4258 | sequence word
4259 | sequence redirect
4260 ;
4261@end example
4262
4263Second, to prevent either a @code{words} or a @code{redirects}
4264from being empty:
4265
4266@example
4267sequence: /* empty */
4268 | sequence words
4269 | sequence redirects
4270 ;
4271
4272words: word
4273 | words word
4274 ;
4275
4276redirects:redirect
4277 | redirects redirect
4278 ;
4279@end example
4280
4281@node Mystery Conflicts, Stack Overflow, Reduce/Reduce, Algorithm
4282@section Mysterious Reduce/Reduce Conflicts
4283
4284Sometimes reduce/reduce conflicts can occur that don't look warranted.
4285Here is an example:
4286
4287@example
4288@group
4289%token ID
4290
4291%%
4292def: param_spec return_spec ','
4293 ;
4294param_spec:
4295 type
4296 | name_list ':' type
4297 ;
4298@end group
4299@group
4300return_spec:
4301 type
4302 | name ':' type
4303 ;
4304@end group
4305@group
4306type: ID
4307 ;
4308@end group
4309@group
4310name: ID
4311 ;
4312name_list:
4313 name
4314 | name ',' name_list
4315 ;
4316@end group
4317@end example
4318
4319It would seem that this grammar can be parsed with only a single token
4320of look-ahead: when a @code{param_spec} is being read, an @code{ID} is
4321a @code{name} if a comma or colon follows, or a @code{type} if another
4322@code{ID} follows. In other words, this grammar is LR(1).
4323
4324@cindex LR(1)
4325@cindex LALR(1)
4326However, Bison, like most parser generators, cannot actually handle all
4327LR(1) grammars. In this grammar, two contexts, that after an @code{ID}
4328at the beginning of a @code{param_spec} and likewise at the beginning of
4329a @code{return_spec}, are similar enough that Bison assumes they are the
4330same. They appear similar because the same set of rules would be
4331active---the rule for reducing to a @code{name} and that for reducing to
4332a @code{type}. Bison is unable to determine at that stage of processing
4333that the rules would require different look-ahead tokens in the two
4334contexts, so it makes a single parser state for them both. Combining
4335the two contexts causes a conflict later. In parser terminology, this
4336occurrence means that the grammar is not LALR(1).
4337
4338In general, it is better to fix deficiencies than to document them. But
4339this particular deficiency is intrinsically hard to fix; parser
4340generators that can handle LR(1) grammars are hard to write and tend to
4341produce parsers that are very large. In practice, Bison is more useful
4342as it is now.
4343
4344When the problem arises, you can often fix it by identifying the two
4345parser states that are being confused, and adding something to make them
4346look distinct. In the above example, adding one rule to
4347@code{return_spec} as follows makes the problem go away:
4348
4349@example
4350@group
4351%token BOGUS
4352@dots{}
4353%%
4354@dots{}
4355return_spec:
4356 type
4357 | name ':' type
4358 /* This rule is never used. */
4359 | ID BOGUS
4360 ;
4361@end group
4362@end example
4363
4364This corrects the problem because it introduces the possibility of an
4365additional active rule in the context after the @code{ID} at the beginning of
4366@code{return_spec}. This rule is not active in the corresponding context
4367in a @code{param_spec}, so the two contexts receive distinct parser states.
4368As long as the token @code{BOGUS} is never generated by @code{yylex},
4369the added rule cannot alter the way actual input is parsed.
4370
4371In this particular example, there is another way to solve the problem:
4372rewrite the rule for @code{return_spec} to use @code{ID} directly
4373instead of via @code{name}. This also causes the two confusing
4374contexts to have different sets of active rules, because the one for
4375@code{return_spec} activates the altered rule for @code{return_spec}
4376rather than the one for @code{name}.
4377
4378@example
4379param_spec:
4380 type
4381 | name_list ':' type
4382 ;
4383return_spec:
4384 type
4385 | ID ':' type
4386 ;
4387@end example
4388
4389@node Stack Overflow, , Mystery Conflicts, Algorithm
4390@section Stack Overflow, and How to Avoid It
4391@cindex stack overflow
4392@cindex parser stack overflow
4393@cindex overflow of parser stack
4394
4395The Bison parser stack can overflow if too many tokens are shifted and
4396not reduced. When this happens, the parser function @code{yyparse}
4397returns a nonzero value, pausing only to call @code{yyerror} to report
4398the overflow.
4399
4400@vindex YYMAXDEPTH
4401By defining the macro @code{YYMAXDEPTH}, you can control how deep the
4402parser stack can become before a stack overflow occurs. Define the
4403macro with a value that is an integer. This value is the maximum number
4404of tokens that can be shifted (and not reduced) before overflow.
4405It must be a constant expression whose value is known at compile time.
4406
4407The stack space allowed is not necessarily allocated. If you specify a
4408large value for @code{YYMAXDEPTH}, the parser actually allocates a small
4409stack at first, and then makes it bigger by stages as needed. This
4410increasing allocation happens automatically and silently. Therefore,
4411you do not need to make @code{YYMAXDEPTH} painfully small merely to save
4412space for ordinary inputs that do not need much stack.
4413
4414@cindex default stack limit
4415The default value of @code{YYMAXDEPTH}, if you do not define it, is
441610000.
4417
4418@vindex YYINITDEPTH
4419You can control how much stack is allocated initially by defining the
4420macro @code{YYINITDEPTH}. This value too must be a compile-time
4421constant integer. The default is 200.
4422
4423@node Error Recovery, Context Dependency, Algorithm, Top
4424@chapter Error Recovery
4425@cindex error recovery
4426@cindex recovery from errors
4427
4428It is not usually acceptable to have a program terminate on a parse
4429error. For example, a compiler should recover sufficiently to parse the
4430rest of the input file and check it for errors; a calculator should accept
4431another expression.
4432
4433In a simple interactive command parser where each input is one line, it may
4434be sufficient to allow @code{yyparse} to return 1 on error and have the
4435caller ignore the rest of the input line when that happens (and then call
4436@code{yyparse} again). But this is inadequate for a compiler, because it
4437forgets all the syntactic context leading up to the error. A syntax error
4438deep within a function in the compiler input should not cause the compiler
4439to treat the following line like the beginning of a source file.
4440
4441@findex error
4442You can define how to recover from a syntax error by writing rules to
4443recognize the special token @code{error}. This is a terminal symbol that
4444is always defined (you need not declare it) and reserved for error
4445handling. The Bison parser generates an @code{error} token whenever a
4446syntax error happens; if you have provided a rule to recognize this token
4447in the current context, the parse can continue.
4448
4449For example:
4450
4451@example
4452stmnts: /* empty string */
4453 | stmnts '\n'
4454 | stmnts exp '\n'
4455 | stmnts error '\n'
4456@end example
4457
4458The fourth rule in this example says that an error followed by a newline
4459makes a valid addition to any @code{stmnts}.
4460
4461What happens if a syntax error occurs in the middle of an @code{exp}? The
4462error recovery rule, interpreted strictly, applies to the precise sequence
4463of a @code{stmnts}, an @code{error} and a newline. If an error occurs in
4464the middle of an @code{exp}, there will probably be some additional tokens
4465and subexpressions on the stack after the last @code{stmnts}, and there
4466will be tokens to read before the next newline. So the rule is not
4467applicable in the ordinary way.
4468
4469But Bison can force the situation to fit the rule, by discarding part of
4470the semantic context and part of the input. First it discards states and
4471objects from the stack until it gets back to a state in which the
4472@code{error} token is acceptable. (This means that the subexpressions
4473already parsed are discarded, back to the last complete @code{stmnts}.) At
4474this point the @code{error} token can be shifted. Then, if the old
4475look-ahead token is not acceptable to be shifted next, the parser reads
4476tokens and discards them until it finds a token which is acceptable. In
4477this example, Bison reads and discards input until the next newline
4478so that the fourth rule can apply.
4479
4480The choice of error rules in the grammar is a choice of strategies for
4481error recovery. A simple and useful strategy is simply to skip the rest of
4482the current input line or current statement if an error is detected:
4483
4484@example
4485stmnt: error ';' /* on error, skip until ';' is read */
4486@end example
4487
4488It is also useful to recover to the matching close-delimiter of an
4489opening-delimiter that has already been parsed. Otherwise the
4490close-delimiter will probably appear to be unmatched, and generate another,
4491spurious error message:
4492
4493@example
4494primary: '(' expr ')'
4495 | '(' error ')'
4496 @dots{}
4497 ;
4498@end example
4499
4500Error recovery strategies are necessarily guesses. When they guess wrong,
4501one syntax error often leads to another. In the above example, the error
4502recovery rule guesses that an error is due to bad input within one
4503@code{stmnt}. Suppose that instead a spurious semicolon is inserted in the
4504middle of a valid @code{stmnt}. After the error recovery rule recovers
4505from the first error, another syntax error will be found straightaway,
4506since the text following the spurious semicolon is also an invalid
4507@code{stmnt}.
4508
4509To prevent an outpouring of error messages, the parser will output no error
4510message for another syntax error that happens shortly after the first; only
4511after three consecutive input tokens have been successfully shifted will
4512error messages resume.
4513
4514Note that rules which accept the @code{error} token may have actions, just
4515as any other rules can.
4516
4517@findex yyerrok
4518You can make error messages resume immediately by using the macro
4519@code{yyerrok} in an action. If you do this in the error rule's action, no
4520error messages will be suppressed. This macro requires no arguments;
4521@samp{yyerrok;} is a valid C statement.
4522
4523@findex yyclearin
4524The previous look-ahead token is reanalyzed immediately after an error. If
4525this is unacceptable, then the macro @code{yyclearin} may be used to clear
4526this token. Write the statement @samp{yyclearin;} in the error rule's
4527action.
4528
4529For example, suppose that on a parse error, an error handling routine is
4530called that advances the input stream to some point where parsing should
4531once again commence. The next symbol returned by the lexical scanner is
4532probably correct. The previous look-ahead token ought to be discarded
4533with @samp{yyclearin;}.
4534
4535@vindex YYRECOVERING
4536The macro @code{YYRECOVERING} stands for an expression that has the
4537value 1 when the parser is recovering from a syntax error, and 0 the
4538rest of the time. A value of 1 indicates that error messages are
4539currently suppressed for new syntax errors.
4540
4541@node Context Dependency, Debugging, Error Recovery, Top
4542@chapter Handling Context Dependencies
4543
4544The Bison paradigm is to parse tokens first, then group them into larger
4545syntactic units. In many languages, the meaning of a token is affected by
4546its context. Although this violates the Bison paradigm, certain techniques
4547(known as @dfn{kludges}) may enable you to write Bison parsers for such
4548languages.
4549
4550@menu
4551* Semantic Tokens:: Token parsing can depend on the semantic context.
4552* Lexical Tie-ins:: Token parsing can depend on the syntactic context.
4553* Tie-in Recovery:: Lexical tie-ins have implications for how
4554 error recovery rules must be written.
4555@end menu
4556
4557(Actually, ``kludge'' means any technique that gets its job done but is
4558neither clean nor robust.)
4559
4560@node Semantic Tokens, Lexical Tie-ins, , Context Dependency
4561@section Semantic Info in Token Types
4562
4563The C language has a context dependency: the way an identifier is used
4564depends on what its current meaning is. For example, consider this:
4565
4566@example
4567foo (x);
4568@end example
4569
4570This looks like a function call statement, but if @code{foo} is a typedef
4571name, then this is actually a declaration of @code{x}. How can a Bison
4572parser for C decide how to parse this input?
4573
4574The method used in GNU C is to have two different token types,
4575@code{IDENTIFIER} and @code{TYPENAME}. When @code{yylex} finds an
4576identifier, it looks up the current declaration of the identifier in order
4577to decide which token type to return: @code{TYPENAME} if the identifier is
4578declared as a typedef, @code{IDENTIFIER} otherwise.
4579
4580The grammar rules can then express the context dependency by the choice of
4581token type to recognize. @code{IDENTIFIER} is accepted as an expression,
4582but @code{TYPENAME} is not. @code{TYPENAME} can start a declaration, but
4583@code{IDENTIFIER} cannot. In contexts where the meaning of the identifier
4584is @emph{not} significant, such as in declarations that can shadow a
4585typedef name, either @code{TYPENAME} or @code{IDENTIFIER} is
4586accepted---there is one rule for each of the two token types.
4587
4588This technique is simple to use if the decision of which kinds of
4589identifiers to allow is made at a place close to where the identifier is
4590parsed. But in C this is not always so: C allows a declaration to
4591redeclare a typedef name provided an explicit type has been specified
4592earlier:
4593
4594@example
4595typedef int foo, bar, lose;
4596static foo (bar); /* @r{redeclare @code{bar} as static variable} */
4597static int foo (lose); /* @r{redeclare @code{foo} as function} */
4598@end example
4599
4600Unfortunately, the name being declared is separated from the declaration
4601construct itself by a complicated syntactic structure---the ``declarator''.
4602
4603As a result, the part of Bison parser for C needs to be duplicated, with
4604all the nonterminal names changed: once for parsing a declaration in which
4605a typedef name can be redefined, and once for parsing a declaration in
4606which that can't be done. Here is a part of the duplication, with actions
4607omitted for brevity:
4608
4609@example
4610initdcl:
4611 declarator maybeasm '='
4612 init
4613 | declarator maybeasm
4614 ;
4615
4616notype_initdcl:
4617 notype_declarator maybeasm '='
4618 init
4619 | notype_declarator maybeasm
4620 ;
4621@end example
4622
4623@noindent
4624Here @code{initdcl} can redeclare a typedef name, but @code{notype_initdcl}
4625cannot. The distinction between @code{declarator} and
4626@code{notype_declarator} is the same sort of thing.
4627
4628There is some similarity between this technique and a lexical tie-in
4629(described next), in that information which alters the lexical analysis is
4630changed during parsing by other parts of the program. The difference is
4631here the information is global, and is used for other purposes in the
4632program. A true lexical tie-in has a special-purpose flag controlled by
4633the syntactic context.
4634
4635@node Lexical Tie-ins, Tie-in Recovery, Semantic Tokens, Context Dependency
4636@section Lexical Tie-ins
4637@cindex lexical tie-in
4638
4639One way to handle context-dependency is the @dfn{lexical tie-in}: a flag
4640which is set by Bison actions, whose purpose is to alter the way tokens are
4641parsed.
4642
4643For example, suppose we have a language vaguely like C, but with a special
4644construct @samp{hex (@var{hex-expr})}. After the keyword @code{hex} comes
4645an expression in parentheses in which all integers are hexadecimal. In
4646particular, the token @samp{a1b} must be treated as an integer rather than
4647as an identifier if it appears in that context. Here is how you can do it:
4648
4649@example
4650@group
4651%@{
4652int hexflag;
4653%@}
4654%%
4655@dots{}
4656@end group
4657@group
4658expr: IDENTIFIER
4659 | constant
4660 | HEX '('
4661 @{ hexflag = 1; @}
4662 expr ')'
4663 @{ hexflag = 0;
4664 $$ = $4; @}
4665 | expr '+' expr
4666 @{ $$ = make_sum ($1, $3); @}
4667 @dots{}
4668 ;
4669@end group
4670
4671@group
4672constant:
4673 INTEGER
4674 | STRING
4675 ;
4676@end group
4677@end example
4678
4679@noindent
4680Here we assume that @code{yylex} looks at the value of @code{hexflag}; when
4681it is nonzero, all integers are parsed in hexadecimal, and tokens starting
4682with letters are parsed as integers if possible.
4683
4684The declaration of @code{hexflag} shown in the C declarations section of
4685the parser file is needed to make it accessible to the actions
4686(@pxref{C Declarations, ,The C Declarations Section}). You must also write the code in @code{yylex}
4687to obey the flag.
4688
4689@node Tie-in Recovery, , Lexical Tie-ins, Context Dependency
4690@section Lexical Tie-ins and Error Recovery
4691
4692Lexical tie-ins make strict demands on any error recovery rules you have.
4693@xref{Error Recovery}.
4694
4695The reason for this is that the purpose of an error recovery rule is to
4696abort the parsing of one construct and resume in some larger construct.
4697For example, in C-like languages, a typical error recovery rule is to skip
4698tokens until the next semicolon, and then start a new statement, like this:
4699
4700@example
4701stmt: expr ';'
4702 | IF '(' expr ')' stmt @{ @dots{} @}
4703 @dots{}
4704 error ';'
4705 @{ hexflag = 0; @}
4706 ;
4707@end example
4708
4709If there is a syntax error in the middle of a @samp{hex (@var{expr})}
4710construct, this error rule will apply, and then the action for the
4711completed @samp{hex (@var{expr})} will never run. So @code{hexflag} would
4712remain set for the entire rest of the input, or until the next @code{hex}
4713keyword, causing identifiers to be misinterpreted as integers.
4714
4715To avoid this problem the error recovery rule itself clears @code{hexflag}.
4716
4717There may also be an error recovery rule that works within expressions.
4718For example, there could be a rule which applies within parentheses
4719and skips to the close-parenthesis:
4720
4721@example
4722@group
4723expr: @dots{}
4724 | '(' expr ')'
4725 @{ $$ = $2; @}
4726 | '(' error ')'
4727 @dots{}
4728@end group
4729@end example
4730
4731If this rule acts within the @code{hex} construct, it is not going to abort
4732that construct (since it applies to an inner level of parentheses within
4733the construct). Therefore, it should not clear the flag: the rest of
4734the @code{hex} construct should be parsed with the flag still in effect.
4735
4736What if there is an error recovery rule which might abort out of the
4737@code{hex} construct or might not, depending on circumstances? There is no
4738way you can write the action to determine whether a @code{hex} construct is
4739being aborted or not. So if you are using a lexical tie-in, you had better
4740make sure your error recovery rules are not of this kind. Each rule must
4741be such that you can be sure that it always will, or always won't, have to
4742clear the flag.
4743
4744@node Debugging, Invocation, Context Dependency, Top
4745@chapter Debugging Your Parser
4746@findex YYDEBUG
4747@findex yydebug
4748@cindex debugging
4749@cindex tracing the parser
4750
4751If a Bison grammar compiles properly but doesn't do what you want when it
4752runs, the @code{yydebug} parser-trace feature can help you figure out why.
4753
4754To enable compilation of trace facilities, you must define the macro
4755@code{YYDEBUG} when you compile the parser. You could use
4756@samp{-DYYDEBUG=1} as a compiler option or you could put @samp{#define
4757YYDEBUG 1} in the C declarations section of the grammar file
4758(@pxref{C Declarations, ,The C Declarations Section}). Alternatively, use the @samp{-t} option when
4759you run Bison (@pxref{Invocation, ,Invoking Bison}). We always define @code{YYDEBUG} so that
4760debugging is always possible.
4761
4762The trace facility uses @code{stderr}, so you must add @w{@code{#include
4763<stdio.h>}} to the C declarations section unless it is already there.
4764
4765Once you have compiled the program with trace facilities, the way to
4766request a trace is to store a nonzero value in the variable @code{yydebug}.
4767You can do this by making the C code do it (in @code{main}, perhaps), or
4768you can alter the value with a C debugger.
4769
4770Each step taken by the parser when @code{yydebug} is nonzero produces a
4771line or two of trace information, written on @code{stderr}. The trace
4772messages tell you these things:
4773
4774@itemize @bullet
4775@item
4776Each time the parser calls @code{yylex}, what kind of token was read.
4777
4778@item
4779Each time a token is shifted, the depth and complete contents of the
4780state stack (@pxref{Parser States}).
4781
4782@item
4783Each time a rule is reduced, which rule it is, and the complete contents
4784of the state stack afterward.
4785@end itemize
4786
4787To make sense of this information, it helps to refer to the listing file
4788produced by the Bison @samp{-v} option (@pxref{Invocation, ,Invoking Bison}). This file
4789shows the meaning of each state in terms of positions in various rules, and
4790also what each state will do with each possible input token. As you read
4791the successive trace messages, you can see that the parser is functioning
4792according to its specification in the listing file. Eventually you will
4793arrive at the place where something undesirable happens, and you will see
4794which parts of the grammar are to blame.
4795
4796The parser file is a C program and you can use C debuggers on it, but it's
4797not easy to interpret what it is doing. The parser function is a
4798finite-state machine interpreter, and aside from the actions it executes
4799the same code over and over. Only the values of variables show where in
4800the grammar it is working.
4801
4802@findex YYPRINT
4803The debugging information normally gives the token type of each token
4804read, but not its semantic value. You can optionally define a macro
4805named @code{YYPRINT} to provide a way to print the value. If you define
4806@code{YYPRINT}, it should take three arguments. The parser will pass a
4807standard I/O stream, the numeric code for the token type, and the token
4808value (from @code{yylval}).
4809
4810Here is an example of @code{YYPRINT} suitable for the multi-function
4811calculator (@pxref{Mfcalc Decl, ,Declarations for @code{mfcalc}}):
4812
4813@smallexample
4814#define YYPRINT(file, type, value) yyprint (file, type, value)
4815
4816static void
4817yyprint (file, type, value)
4818 FILE *file;
4819 int type;
4820 YYSTYPE value;
4821@{
4822 if (type == VAR)
4823 fprintf (file, " %s", value.tptr->name);
4824 else if (type == NUM)
4825 fprintf (file, " %d", value.val);
4826@}
4827@end smallexample
4828
4829@node Invocation, Table of Symbols, Debugging, Top
4830@chapter Invoking Bison
4831@cindex invoking Bison
4832@cindex Bison invocation
4833@cindex options for invoking Bison
4834
4835The usual way to invoke Bison is as follows:
4836
4837@example
4838bison @var{infile}
4839@end example
4840
4841Here @var{infile} is the grammar file name, which usually ends in
4842@samp{.y}. The parser file's name is made by replacing the @samp{.y}
4843with @samp{.tab.c}. Thus, the @samp{bison foo.y} filename yields
4844@file{foo.tab.c}, and the @samp{bison hack/foo.y} filename yields
4845@file{hack/foo.tab.c}.@refill
4846
4847@menu
4848* Bison Options:: All the options described in detail,
4849 in alphabetical order by short options.
4850* Option Cross Key:: Alphabetical list of long options.
4851* VMS Invocation:: Bison command syntax on VMS.
4852@end menu
4853
4854@node Bison Options, Option Cross Key, , Invocation
4855@section Bison Options
4856
4857Bison supports both traditional single-letter options and mnemonic long
4858option names. Long option names are indicated with @samp{--} instead of
4859@samp{-}. Abbreviations for option names are allowed as long as they
4860are unique. When a long option takes an argument, like
4861@samp{--file-prefix}, connect the option name and the argument with
4862@samp{=}.
4863
4864Here is a list of options that can be used with Bison, alphabetized by
4865short option. It is followed by a cross key alphabetized by long
4866option.
4867
4868@table @samp
4869@item -b @var{file-prefix}
4870@itemx --file-prefix=@var{prefix}
4871Specify a prefix to use for all Bison output file names. The names are
4872chosen as if the input file were named @file{@var{prefix}.c}.
4873
4874@item -d
4875@itemx --defines
4876Write an extra output file containing macro definitions for the token
4877type names defined in the grammar and the semantic value type
4878@code{YYSTYPE}, as well as a few @code{extern} variable declarations.
4879
4880If the parser output file is named @file{@var{name}.c} then this file
4881is named @file{@var{name}.h}.@refill
4882
4883This output file is essential if you wish to put the definition of
4884@code{yylex} in a separate source file, because @code{yylex} needs to
4885be able to refer to token type codes and the variable
4886@code{yylval}. @xref{Token Values, ,Semantic Values of Tokens}.@refill
4887
4888@item -l
4889@itemx --no-lines
4890Don't put any @code{#line} preprocessor commands in the parser file.
4891Ordinarily Bison puts them in the parser file so that the C compiler
4892and debuggers will associate errors with your source file, the
4893grammar file. This option causes them to associate errors with the
4894parser file, treating it as an independent source file in its own right.
4895
4896@item -n
4897@itemx --no-parser
4898Do not include any C code in the parser file; generate tables only. The
4899parser file contains just @code{#define} directives and static variable
4900declarations.
4901
4902This option also tells Bison to write the C code for the grammar actions
4903into a file named @file{@var{filename}.act}, in the form of a
4904brace-surrounded body fit for a @code{switch} statement.
4905
4906@item -o @var{outfile}
4907@itemx --output-file=@var{outfile}
4908Specify the name @var{outfile} for the parser file.
4909
4910The other output files' names are constructed from @var{outfile}
4911as described under the @samp{-v} and @samp{-d} options.
4912
4913@item -p @var{prefix}
4914@itemx --name-prefix=@var{prefix}
4915Rename the external symbols used in the parser so that they start with
4916@var{prefix} instead of @samp{yy}. The precise list of symbols renamed
4917is @code{yyparse}, @code{yylex}, @code{yyerror}, @code{yynerrs},
4918@code{yylval}, @code{yychar} and @code{yydebug}.
4919
4920For example, if you use @samp{-p c}, the names become @code{cparse},
4921@code{clex}, and so on.
4922
4923@xref{Multiple Parsers, ,Multiple Parsers in the Same Program}.
4924
4925@item -r
4926@itemx --raw
4927Pretend that @code{%raw} was specified. @xref{Decl Summary}.
4928
4929@item -t
4930@itemx --debug
4931Output a definition of the macro @code{YYDEBUG} into the parser file,
4932so that the debugging facilities are compiled. @xref{Debugging, ,Debugging Your Parser}.
4933
4934@item -v
4935@itemx --verbose
4936Write an extra output file containing verbose descriptions of the
4937parser states and what is done for each type of look-ahead token in
4938that state.
4939
4940This file also describes all the conflicts, both those resolved by
4941operator precedence and the unresolved ones.
4942
4943The file's name is made by removing @samp{.tab.c} or @samp{.c} from
4944the parser output file name, and adding @samp{.output} instead.@refill
4945
4946Therefore, if the input file is @file{foo.y}, then the parser file is
4947called @file{foo.tab.c} by default. As a consequence, the verbose
4948output file is called @file{foo.output}.@refill
4949
4950@item -V
4951@itemx --version
4952Print the version number of Bison and exit.
4953
4954@item -h
4955@itemx --help
4956Print a summary of the command-line options to Bison and exit.
4957
4958@need 1750
4959@item -y
4960@itemx --yacc
4961@itemx --fixed-output-files
4962Equivalent to @samp{-o y.tab.c}; the parser output file is called
4963@file{y.tab.c}, and the other outputs are called @file{y.output} and
4964@file{y.tab.h}. The purpose of this option is to imitate Yacc's output
4965file name conventions. Thus, the following shell script can substitute
4966for Yacc:@refill
4967
4968@example
4969bison -y $*
4970@end example
4971@end table
4972
4973@node Option Cross Key, VMS Invocation, Bison Options, Invocation
4974@section Option Cross Key
4975
4976Here is a list of options, alphabetized by long option, to help you find
4977the corresponding short option.
4978
4979@tex
4980\def\leaderfill{\leaders\hbox to 1em{\hss.\hss}\hfill}
4981
4982{\tt
4983\line{ --debug \leaderfill -t}
4984\line{ --defines \leaderfill -d}
4985\line{ --file-prefix \leaderfill -b}
4986\line{ --fixed-output-files \leaderfill -y}
4987\line{ --help \leaderfill -h}
4988\line{ --name-prefix \leaderfill -p}
4989\line{ --no-lines \leaderfill -l}
4990\line{ --no-parser \leaderfill -n}
4991\line{ --output-file \leaderfill -o}
4992\line{ --raw \leaderfill -r}
4993\line{ --token-table \leaderfill -k}
4994\line{ --verbose \leaderfill -v}
4995\line{ --version \leaderfill -V}
4996\line{ --yacc \leaderfill -y}
4997}
4998@end tex
4999
5000@ifinfo
5001@example
5002--debug -t
5003--defines -d
5004--file-prefix=@var{prefix} -b @var{file-prefix}
5005--fixed-output-files --yacc -y
5006--help -h
5007--name-prefix=@var{prefix} -p @var{name-prefix}
5008--no-lines -l
5009--no-parser -n
5010--output-file=@var{outfile} -o @var{outfile}
5011--raw -r
5012--token-table -k
5013--verbose -v
5014--version -V
5015@end example
5016@end ifinfo
5017
5018@node VMS Invocation, , Option Cross Key, Invocation
5019@section Invoking Bison under VMS
5020@cindex invoking Bison under VMS
5021@cindex VMS
5022
5023The command line syntax for Bison on VMS is a variant of the usual
5024Bison command syntax---adapted to fit VMS conventions.
5025
5026To find the VMS equivalent for any Bison option, start with the long
5027option, and substitute a @samp{/} for the leading @samp{--}, and
5028substitute a @samp{_} for each @samp{-} in the name of the long option.
5029For example, the following invocation under VMS:
5030
5031@example
5032bison /debug/name_prefix=bar foo.y
5033@end example
5034
5035@noindent
5036is equivalent to the following command under POSIX.
5037
5038@example
5039bison --debug --name-prefix=bar foo.y
5040@end example
5041
5042The VMS file system does not permit filenames such as
5043@file{foo.tab.c}. In the above example, the output file
5044would instead be named @file{foo_tab.c}.
5045
5046@node Table of Symbols, Glossary, Invocation, Top
5047@appendix Bison Symbols
5048@cindex Bison symbols, table of
5049@cindex symbols in Bison, table of
5050
5051@table @code
5052@item error
5053A token name reserved for error recovery. This token may be used in
5054grammar rules so as to allow the Bison parser to recognize an error in
5055the grammar without halting the process. In effect, a sentence
5056containing an error may be recognized as valid. On a parse error, the
5057token @code{error} becomes the current look-ahead token. Actions
5058corresponding to @code{error} are then executed, and the look-ahead
5059token is reset to the token that originally caused the violation.
5060@xref{Error Recovery}.
5061
5062@item YYABORT
5063Macro to pretend that an unrecoverable syntax error has occurred, by
5064making @code{yyparse} return 1 immediately. The error reporting
5065function @code{yyerror} is not called. @xref{Parser Function, ,The Parser Function @code{yyparse}}.
5066
5067@item YYACCEPT
5068Macro to pretend that a complete utterance of the language has been
5069read, by making @code{yyparse} return 0 immediately.
5070@xref{Parser Function, ,The Parser Function @code{yyparse}}.
5071
5072@item YYBACKUP
5073Macro to discard a value from the parser stack and fake a look-ahead
5074token. @xref{Action Features, ,Special Features for Use in Actions}.
5075
5076@item YYERROR
5077Macro to pretend that a syntax error has just been detected: call
5078@code{yyerror} and then perform normal error recovery if possible
5079(@pxref{Error Recovery}), or (if recovery is impossible) make
5080@code{yyparse} return 1. @xref{Error Recovery}.
5081
5082@item YYERROR_VERBOSE
5083Macro that you define with @code{#define} in the Bison declarations
5084section to request verbose, specific error message strings when
5085@code{yyerror} is called.
5086
5087@item YYINITDEPTH
5088Macro for specifying the initial size of the parser stack.
5089@xref{Stack Overflow}.
5090
5091@item YYLEX_PARAM
5092Macro for specifying an extra argument (or list of extra arguments) for
5093@code{yyparse} to pass to @code{yylex}. @xref{Pure Calling,, Calling
5094Conventions for Pure Parsers}.
5095
5096@item YYLTYPE
5097Macro for the data type of @code{yylloc}; a structure with four
5098members. @xref{Token Positions, ,Textual Positions of Tokens}.
5099
5100@item yyltype
5101Default value for YYLTYPE.
5102
5103@item YYMAXDEPTH
5104Macro for specifying the maximum size of the parser stack.
5105@xref{Stack Overflow}.
5106
5107@item YYPARSE_PARAM
5108Macro for specifying the name of a parameter that @code{yyparse} should
5109accept. @xref{Pure Calling,, Calling Conventions for Pure Parsers}.
5110
5111@item YYRECOVERING
5112Macro whose value indicates whether the parser is recovering from a
5113syntax error. @xref{Action Features, ,Special Features for Use in Actions}.
5114
5115@item YYSTYPE
5116Macro for the data type of semantic values; @code{int} by default.
5117@xref{Value Type, ,Data Types of Semantic Values}.
5118
5119@item yychar
5120External integer variable that contains the integer value of the
5121current look-ahead token. (In a pure parser, it is a local variable
5122within @code{yyparse}.) Error-recovery rule actions may examine this
5123variable. @xref{Action Features, ,Special Features for Use in Actions}.
5124
5125@item yyclearin
5126Macro used in error-recovery rule actions. It clears the previous
5127look-ahead token. @xref{Error Recovery}.
5128
5129@item yydebug
5130External integer variable set to zero by default. If @code{yydebug}
5131is given a nonzero value, the parser will output information on input
5132symbols and parser action. @xref{Debugging, ,Debugging Your Parser}.
5133
5134@item yyerrok
5135Macro to cause parser to recover immediately to its normal mode
5136after a parse error. @xref{Error Recovery}.
5137
5138@item yyerror
5139User-supplied function to be called by @code{yyparse} on error. The
5140function receives one argument, a pointer to a character string
5141containing an error message. @xref{Error Reporting, ,The Error Reporting Function @code{yyerror}}.
5142
5143@item yylex
5144User-supplied lexical analyzer function, called with no arguments
5145to get the next token. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
5146
5147@item yylval
5148External variable in which @code{yylex} should place the semantic
5149value associated with a token. (In a pure parser, it is a local
5150variable within @code{yyparse}, and its address is passed to
5151@code{yylex}.) @xref{Token Values, ,Semantic Values of Tokens}.
5152
5153@item yylloc
5154External variable in which @code{yylex} should place the line and
5155column numbers associated with a token. (In a pure parser, it is a
5156local variable within @code{yyparse}, and its address is passed to
5157@code{yylex}.) You can ignore this variable if you don't use the
5158@samp{@@} feature in the grammar actions. @xref{Token Positions, ,Textual Positions of Tokens}.
5159
5160@item yynerrs
5161Global variable which Bison increments each time there is a parse
5162error. (In a pure parser, it is a local variable within
5163@code{yyparse}.) @xref{Error Reporting, ,The Error Reporting Function @code{yyerror}}.
5164
5165@item yyparse
5166The parser function produced by Bison; call this function to start
5167parsing. @xref{Parser Function, ,The Parser Function @code{yyparse}}.
5168
5169@item %left
5170Bison declaration to assign left associativity to token(s).
5171@xref{Precedence Decl, ,Operator Precedence}.
5172
5173@item %no_lines
5174Bison declaration to avoid generating @code{#line} directives in the
5175parser file. @xref{Decl Summary}.
5176
5177@item %nonassoc
5178Bison declaration to assign nonassociativity to token(s).
5179@xref{Precedence Decl, ,Operator Precedence}.
5180
5181@item %prec
5182Bison declaration to assign a precedence to a specific rule.
5183@xref{Contextual Precedence, ,Context-Dependent Precedence}.
5184
5185@item %pure_parser
5186Bison declaration to request a pure (reentrant) parser.
5187@xref{Pure Decl, ,A Pure (Reentrant) Parser}.
5188
5189@item %raw
5190Bison declaration to use Bison internal token code numbers in token
5191tables instead of the usual Yacc-compatible token code numbers.
5192@xref{Decl Summary}.
5193
5194@item %right
5195Bison declaration to assign right associativity to token(s).
5196@xref{Precedence Decl, ,Operator Precedence}.
5197
5198@item %start
5199Bison declaration to specify the start symbol. @xref{Start Decl, ,The Start-Symbol}.
5200
5201@item %token
5202Bison declaration to declare token(s) without specifying precedence.
5203@xref{Token Decl, ,Token Type Names}.
5204
5205@item %token_table
5206Bison declaration to include a token name table in the parser file.
5207@xref{Decl Summary}.
5208
5209@item %type
5210Bison declaration to declare nonterminals. @xref{Type Decl, ,Nonterminal Symbols}.
5211
5212@item %union
5213Bison declaration to specify several possible data types for semantic
5214values. @xref{Union Decl, ,The Collection of Value Types}.
5215@end table
5216
5217These are the punctuation and delimiters used in Bison input:
5218
5219@table @samp
5220@item %%
5221Delimiter used to separate the grammar rule section from the
5222Bison declarations section or the additional C code section.
5223@xref{Grammar Layout, ,The Overall Layout of a Bison Grammar}.
5224
5225@item %@{ %@}
5226All code listed between @samp{%@{} and @samp{%@}} is copied directly
5227to the output file uninterpreted. Such code forms the ``C
5228declarations'' section of the input file. @xref{Grammar Outline, ,Outline of a Bison Grammar}.
5229
5230@item /*@dots{}*/
5231Comment delimiters, as in C.
5232
5233@item :
5234Separates a rule's result from its components. @xref{Rules, ,Syntax of Grammar Rules}.
5235
5236@item ;
5237Terminates a rule. @xref{Rules, ,Syntax of Grammar Rules}.
5238
5239@item |
5240Separates alternate rules for the same result nonterminal.
5241@xref{Rules, ,Syntax of Grammar Rules}.
5242@end table
5243
5244@node Glossary, Index, Table of Symbols, Top
5245@appendix Glossary
5246@cindex glossary
5247
5248@table @asis
5249@item Backus-Naur Form (BNF)
5250Formal method of specifying context-free grammars. BNF was first used
5251in the @cite{ALGOL-60} report, 1963. @xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5252
5253@item Context-free grammars
5254Grammars specified as rules that can be applied regardless of context.
5255Thus, if there is a rule which says that an integer can be used as an
5256expression, integers are allowed @emph{anywhere} an expression is
5257permitted. @xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5258
5259@item Dynamic allocation
5260Allocation of memory that occurs during execution, rather than at
5261compile time or on entry to a function.
5262
5263@item Empty string
5264Analogous to the empty set in set theory, the empty string is a
5265character string of length zero.
5266
5267@item Finite-state stack machine
5268A ``machine'' that has discrete states in which it is said to exist at
5269each instant in time. As input to the machine is processed, the
5270machine moves from state to state as specified by the logic of the
5271machine. In the case of the parser, the input is the language being
5272parsed, and the states correspond to various stages in the grammar
5273rules. @xref{Algorithm, ,The Bison Parser Algorithm }.
5274
5275@item Grouping
5276A language construct that is (in general) grammatically divisible;
5277for example, `expression' or `declaration' in C.
5278@xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5279
5280@item Infix operator
5281An arithmetic operator that is placed between the operands on which it
5282performs some operation.
5283
5284@item Input stream
5285A continuous flow of data between devices or programs.
5286
5287@item Language construct
5288One of the typical usage schemas of the language. For example, one of
5289the constructs of the C language is the @code{if} statement.
5290@xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5291
5292@item Left associativity
5293Operators having left associativity are analyzed from left to right:
5294@samp{a+b+c} first computes @samp{a+b} and then combines with
5295@samp{c}. @xref{Precedence, ,Operator Precedence}.
5296
5297@item Left recursion
5298A rule whose result symbol is also its first component symbol;
5299for example, @samp{expseq1 : expseq1 ',' exp;}. @xref{Recursion, ,Recursive Rules}.
5300
5301@item Left-to-right parsing
5302Parsing a sentence of a language by analyzing it token by token from
5303left to right. @xref{Algorithm, ,The Bison Parser Algorithm }.
5304
5305@item Lexical analyzer (scanner)
5306A function that reads an input stream and returns tokens one by one.
5307@xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
5308
5309@item Lexical tie-in
5310A flag, set by actions in the grammar rules, which alters the way
5311tokens are parsed. @xref{Lexical Tie-ins}.
5312
5313@item Literal string token
5314A token which constists of two or more fixed characters.
5315@xref{Symbols}.
5316
5317@item Look-ahead token
5318A token already read but not yet shifted. @xref{Look-Ahead, ,Look-Ahead Tokens}.
5319
5320@item LALR(1)
5321The class of context-free grammars that Bison (like most other parser
5322generators) can handle; a subset of LR(1). @xref{Mystery Conflicts, ,
5323Mysterious Reduce/Reduce Conflicts}.
5324
5325@item LR(1)
5326The class of context-free grammars in which at most one token of
5327look-ahead is needed to disambiguate the parsing of any piece of input.
5328
5329@item Nonterminal symbol
5330A grammar symbol standing for a grammatical construct that can
5331be expressed through rules in terms of smaller constructs; in other
5332words, a construct that is not a token. @xref{Symbols}.
5333
5334@item Parse error
5335An error encountered during parsing of an input stream due to invalid
5336syntax. @xref{Error Recovery}.
5337
5338@item Parser
5339A function that recognizes valid sentences of a language by analyzing
5340the syntax structure of a set of tokens passed to it from a lexical
5341analyzer.
5342
5343@item Postfix operator
5344An arithmetic operator that is placed after the operands upon which it
5345performs some operation.
5346
5347@item Reduction
5348Replacing a string of nonterminals and/or terminals with a single
5349nonterminal, according to a grammar rule. @xref{Algorithm, ,The Bison Parser Algorithm }.
5350
5351@item Reentrant
5352A reentrant subprogram is a subprogram which can be in invoked any
5353number of times in parallel, without interference between the various
5354invocations. @xref{Pure Decl, ,A Pure (Reentrant) Parser}.
5355
5356@item Reverse polish notation
5357A language in which all operators are postfix operators.
5358
5359@item Right recursion
5360A rule whose result symbol is also its last component symbol;
5361for example, @samp{expseq1: exp ',' expseq1;}. @xref{Recursion, ,Recursive Rules}.
5362
5363@item Semantics
5364In computer languages, the semantics are specified by the actions
5365taken for each instance of the language, i.e., the meaning of
5366each statement. @xref{Semantics, ,Defining Language Semantics}.
5367
5368@item Shift
5369A parser is said to shift when it makes the choice of analyzing
5370further input from the stream rather than reducing immediately some
5371already-recognized rule. @xref{Algorithm, ,The Bison Parser Algorithm }.
5372
5373@item Single-character literal
5374A single character that is recognized and interpreted as is.
5375@xref{Grammar in Bison, ,From Formal Rules to Bison Input}.
5376
5377@item Start symbol
5378The nonterminal symbol that stands for a complete valid utterance in
5379the language being parsed. The start symbol is usually listed as the
5380first nonterminal symbol in a language specification.
5381@xref{Start Decl, ,The Start-Symbol}.
5382
5383@item Symbol table
5384A data structure where symbol names and associated data are stored
5385during parsing to allow for recognition and use of existing
5386information in repeated uses of a symbol. @xref{Multi-function Calc}.
5387
5388@item Token
5389A basic, grammatically indivisible unit of a language. The symbol
5390that describes a token in the grammar is a terminal symbol.
5391The input of the Bison parser is a stream of tokens which comes from
5392the lexical analyzer. @xref{Symbols}.
5393
5394@item Terminal symbol
5395A grammar symbol that has no rules in the grammar and therefore
5396is grammatically indivisible. The piece of text it represents
5397is a token. @xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5398@end table
5399
5400@node Index, , Glossary, Top
5401@unnumbered Index
5402
5403@printindex cp
5404
5405@contents
5406
5407@bye
5408
5409
5410\f
5411
5412@c old menu
5413
5414* Introduction::
5415* Conditions::
5416* Copying:: The GNU General Public License says
5417 how you can copy and share Bison
5418
5419Tutorial sections:
5420* Concepts:: Basic concepts for understanding Bison.
5421* Examples:: Three simple explained examples of using Bison.
5422
5423Reference sections:
5424* Grammar File:: Writing Bison declarations and rules.
5425* Interface:: C-language interface to the parser function @code{yyparse}.
5426* Algorithm:: How the Bison parser works at run-time.
5427* Error Recovery:: Writing rules for error recovery.
5428* Context Dependency::What to do if your language syntax is too
5429 messy for Bison to handle straightforwardly.
5430* Debugging:: Debugging Bison parsers that parse wrong.
5431* Invocation:: How to run Bison (to produce the parser source file).
5432* Table of Symbols:: All the keywords of the Bison language are explained.
5433* Glossary:: Basic concepts are explained.
5434* Index:: Cross-references to the text.
5435