]> git.saurik.com Git - bison.git/blob - doc/bison.texinfo
Describe literal string tokens, %raw, %no_lines, %token_table.
[bison.git] / doc / bison.texinfo
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
40 This file documents the Bison parser generator.
41
42 Copyright (C) 1988, 89, 90, 91, 92, 93, 1995 Free Software Foundation, Inc.
43
44 Permission is granted to make and distribute verbatim copies of
45 this manual provided the copyright notice and this permission notice
46 are preserved on all copies.
47
48 @ignore
49 Permission is granted to process this file through Tex and print the
50 results, provided the printed document carries copying permission
51 notice 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
55 Permission is granted to copy and distribute modified versions of this
56 manual under the conditions for verbatim copying, provided also that the
57 sections entitled ``GNU General Public License'' and ``Conditions for
58 Using Bison'' are included exactly as in the original, and provided that
59 the entire resulting derived work is distributed under the terms of a
60 permission notice identical to this one.
61
62 Permission is granted to copy and distribute translations of this manual
63 into another language, under the above conditions for modified versions,
64 except that the sections entitled ``GNU General Public License'',
65 ``Conditions for Using Bison'' and this permission notice may be
66 included in translations approved by the Free Software Foundation
67 instead 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 August 1995, Bison Version 1.25
77
78 @author by Charles Donnelly and Richard Stallman
79
80 @page
81 @vskip 0pt plus 1filll
82 Copyright @copyright{} 1988, 89, 90, 91, 92, 93, 1995 Free Software
83 Foundation
84
85 @sp 2
86 Published by the Free Software Foundation @*
87 59 Temple Place, Suite 330 @*
88 Boston, MA 02111-1307 USA @*
89 Printed copies are available for $15 each.@*
90 ISBN 1-882114-45-0
91
92 Permission is granted to make and distribute verbatim copies of
93 this manual provided the copyright notice and this permission notice
94 are preserved on all copies.
95
96 @ignore
97 Permission is granted to process this file through TeX and print the
98 results, provided the printed document carries copying permission
99 notice 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
103 Permission is granted to copy and distribute modified versions of this
104 manual under the conditions for verbatim copying, provided also that the
105 sections entitled ``GNU General Public License'' and ``Conditions for
106 Using Bison'' are included exactly as in the original, and provided that
107 the entire resulting derived work is distributed under the terms of a
108 permission notice identical to this one.
109
110 Permission is granted to copy and distribute translations of this manual
111 into another language, under the above conditions for modified versions,
112 except that the sections entitled ``GNU General Public License'',
113 ``Conditions for Using Bison'' and this permission notice may be
114 included in translations approved by the Free Software Foundation
115 instead of in the original English.
116 @sp 2
117 Cover art by Etienne Suvasa.
118 @end titlepage
119 @page
120
121 @node Top, Introduction, (dir), (dir)
122
123 @ifinfo
124 This 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
133 Tutorial sections:
134 * Concepts:: Basic concepts for understanding Bison.
135 * Examples:: Three simple explained examples of using Bison.
136
137 Reference 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
152 The 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
166 Examples
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
177 Reverse 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
187 Grammar Rules for @code{rpcalc}
188
189 * Rpcalc Input::
190 * Rpcalc Line::
191 * Rpcalc Expr::
192
193 Multi-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
199 Bison 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
209 Outline 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
216 Defining 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
226 Bison 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
237 Parser 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
245 The 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
256 The 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
267 Operator 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
274 Handling 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
281 Invoking 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
294 grammar description for an LALR(1) context-free grammar into a C
295 program to parse that grammar. Once you are proficient with Bison,
296 you may use it to develop a wide range of language parsers, from those
297 used in simple desk calculators to complex programming languages.
298
299 Bison is upward compatible with Yacc: all properly-written Yacc grammars
300 ought to work with Bison with no change. Anyone familiar with Yacc
301 should be able to use Bison with little trouble. You need to be fluent in
302 C programming in order to use Bison or to understand this manual.
303
304 We begin with tutorial chapters that explain the basic concepts of using
305 Bison and show three explained examples, each building on the last. If you
306 don't know Bison or Yacc, start by reading these chapters. Reference
307 chapters follow which describe specific aspects of Bison in detail.
308
309 Bison was written primarily by Robert Corbett; Richard Stallman made it
310 Yacc-compatible. Wilfred Hansen of Carnegie Mellon University added
311 multicharacter string literals and other features.
312
313 This edition corresponds to version 1.25 of Bison.
314
315 @node Conditions, Copying, Introduction, Top
316 @unnumbered Conditions for Using Bison
317
318 As 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.
320 Formerly, Bison parsers could be used only in programs that were free
321 software.
322
323 The other GNU programming tools, such as the GNU C compiler, have never
324 had such a requirement. They could always be used for non-free
325 software. The reason Bison was different was not due to a special
326 policy decision; it resulted from applying the usual General Public
327 License to all of the Bison source code.
328
329 The output of the Bison utility---the Bison parser file---contains a
330 verbatim copy of a sizable piece of Bison, which is the code for the
331 @code{yyparse} function. (The actions from your grammar are inserted
332 into this function at one point, but the rest of the function is not
333 changed.) When we applied the GPL terms to the code for @code{yyparse},
334 the effect was to restrict the use of Bison output to free software.
335
336 We didn't change the terms because of sympathy for people who want to
337 make software proprietary. @strong{Software should be free.} But we
338 concluded that limiting Bison's use to free software was doing little to
339 encourage people to make other software free. So we decided to make the
340 practical conditions for using Bison match the practical conditions for
341 using 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
348 Copyright @copyright{} 1989, 1991 Free Software Foundation, Inc.
349 675 Mass Ave, Cambridge, MA 02139, USA
350
351 Everyone is permitted to copy and distribute verbatim copies
352 of 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
358 freedom to share and change it. By contrast, the GNU General Public
359 License is intended to guarantee your freedom to share and change free
360 software---to make sure the software is free for all its users. This
361 General Public License applies to most of the Free Software
362 Foundation's software and to any other program whose authors commit to
363 using it. (Some other Free Software Foundation software is covered by
364 the GNU Library General Public License instead.) You can apply it to
365 your programs, too.
366
367 When we speak of free software, we are referring to freedom, not
368 price. Our General Public Licenses are designed to make sure that you
369 have the freedom to distribute copies of free software (and charge for
370 this service if you wish), that you receive source code or can get it
371 if you want it, that you can change the software or use pieces of it
372 in 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
375 anyone to deny you these rights or to ask you to surrender the rights.
376 These restrictions translate to certain responsibilities for you if you
377 distribute copies of the software, or if you modify it.
378
379 For example, if you distribute copies of such a program, whether
380 gratis or for a fee, you must give the recipients all the rights that
381 you have. You must make sure that they, too, receive or can get the
382 source code. And you must show them these terms so they know their
383 rights.
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,
387 distribute and/or modify the software.
388
389 Also, for each author's protection and ours, we want to make certain
390 that everyone understands that there is no warranty for this free
391 software. If the software is modified by someone else and passed on, we
392 want its recipients to know that what they have is not the original, so
393 that any problems introduced by others will not reflect on the original
394 authors' reputations.
395
396 Finally, any free program is threatened constantly by software
397 patents. We wish to avoid the danger that redistributors of a free
398 program will individually obtain patent licenses, in effect making the
399 program proprietary. To prevent this, we have made it clear that any
400 patent must be licensed for everyone's free use or not licensed at all.
401
402 The precise terms and conditions for copying, distribution and
403 modification 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
414 This License applies to any program or other work which contains
415 a notice placed by the copyright holder saying it may be distributed
416 under the terms of this General Public License. The ``Program'', below,
417 refers to any such program or work, and a ``work based on the Program''
418 means either the Program or any derivative work under copyright law:
419 that is to say, a work containing the Program or a portion of it,
420 either verbatim or with modifications and/or translated into another
421 language. (Hereinafter, translation is included without limitation in
422 the term ``modification''.) Each licensee is addressed as ``you''.
423
424 Activities other than copying, distribution and modification are not
425 covered by this License; they are outside its scope. The act of
426 running the Program is not restricted, and the output from the Program
427 is covered only if its contents constitute a work based on the
428 Program (independent of having been made by running the Program).
429 Whether that is true depends on what the Program does.
430
431 @item
432 You may copy and distribute verbatim copies of the Program's
433 source code as you receive it, in any medium, provided that you
434 conspicuously and appropriately publish on each copy an appropriate
435 copyright notice and disclaimer of warranty; keep intact all the
436 notices that refer to this License and to the absence of any warranty;
437 and give any other recipients of the Program a copy of this License
438 along with the Program.
439
440 You may charge a fee for the physical act of transferring a copy, and
441 you may at your option offer warranty protection in exchange for a fee.
442
443 @item
444 You may modify your copy or copies of the Program or any portion
445 of it, thus forming a work based on the Program, and copy and
446 distribute such modifications or work under the terms of Section 1
447 above, provided that you also meet all of these conditions:
448
449 @enumerate a
450 @item
451 You must cause the modified files to carry prominent notices
452 stating that you changed the files and the date of any change.
453
454 @item
455 You must cause any work that you distribute or publish, that in
456 whole or in part contains or is derived from the Program or any
457 part thereof, to be licensed as a whole at no charge to all third
458 parties under the terms of this License.
459
460 @item
461 If the modified program normally reads commands interactively
462 when run, you must cause it, when started running for such
463 interactive use in the most ordinary way, to print or display an
464 announcement including an appropriate copyright notice and a
465 notice that there is no warranty (or else, saying that you provide
466 a warranty) and that users may redistribute the program under
467 these conditions, and telling the user how to view a copy of this
468 License. (Exception: if the Program itself is interactive but
469 does not normally print such an announcement, your work based on
470 the Program is not required to print an announcement.)
471 @end enumerate
472
473 These requirements apply to the modified work as a whole. If
474 identifiable sections of that work are not derived from the Program,
475 and can be reasonably considered independent and separate works in
476 themselves, then this License, and its terms, do not apply to those
477 sections when you distribute them as separate works. But when you
478 distribute the same sections as part of a whole which is a work based
479 on the Program, the distribution of the whole must be on the terms of
480 this License, whose permissions for other licensees extend to the
481 entire whole, and thus to each and every part regardless of who wrote it.
482
483 Thus, it is not the intent of this section to claim rights or contest
484 your rights to work written entirely by you; rather, the intent is to
485 exercise the right to control the distribution of derivative or
486 collective works based on the Program.
487
488 In addition, mere aggregation of another work not based on the Program
489 with the Program (or with a work based on the Program) on a volume of
490 a storage or distribution medium does not bring the other work under
491 the scope of this License.
492
493 @item
494 You may copy and distribute the Program (or a work based on it,
495 under Section 2) in object code or executable form under the terms of
496 Sections 1 and 2 above provided that you also do one of the following:
497
498 @enumerate a
499 @item
500 Accompany it with the complete corresponding machine-readable
501 source code, which must be distributed under the terms of Sections
502 1 and 2 above on a medium customarily used for software interchange; or,
503
504 @item
505 Accompany it with a written offer, valid for at least three
506 years, to give any third party, for a charge no more than your
507 cost of physically performing source distribution, a complete
508 machine-readable copy of the corresponding source code, to be
509 distributed under the terms of Sections 1 and 2 above on a medium
510 customarily used for software interchange; or,
511
512 @item
513 Accompany it with the information you received as to the offer
514 to distribute corresponding source code. (This alternative is
515 allowed only for noncommercial distribution and only if you
516 received the program in object code or executable form with such
517 an offer, in accord with Subsection b above.)
518 @end enumerate
519
520 The source code for a work means the preferred form of the work for
521 making modifications to it. For an executable work, complete source
522 code means all the source code for all modules it contains, plus any
523 associated interface definition files, plus the scripts used to
524 control compilation and installation of the executable. However, as a
525 special exception, the source code distributed need not include
526 anything that is normally distributed (in either source or binary
527 form) with the major components (compiler, kernel, and so on) of the
528 operating system on which the executable runs, unless that component
529 itself accompanies the executable.
530
531 If distribution of executable or object code is made by offering
532 access to copy from a designated place, then offering equivalent
533 access to copy the source code from the same place counts as
534 distribution of the source code, even though third parties are not
535 compelled to copy the source along with the object code.
536
537 @item
538 You may not copy, modify, sublicense, or distribute the Program
539 except as expressly provided under this License. Any attempt
540 otherwise to copy, modify, sublicense or distribute the Program is
541 void, and will automatically terminate your rights under this License.
542 However, parties who have received copies, or rights, from you under
543 this License will not have their licenses terminated so long as such
544 parties remain in full compliance.
545
546 @item
547 You are not required to accept this License, since you have not
548 signed it. However, nothing else grants you permission to modify or
549 distribute the Program or its derivative works. These actions are
550 prohibited by law if you do not accept this License. Therefore, by
551 modifying or distributing the Program (or any work based on the
552 Program), you indicate your acceptance of this License to do so, and
553 all its terms and conditions for copying, distributing or modifying
554 the Program or works based on it.
555
556 @item
557 Each time you redistribute the Program (or any work based on the
558 Program), the recipient automatically receives a license from the
559 original licensor to copy, distribute or modify the Program subject to
560 these terms and conditions. You may not impose any further
561 restrictions on the recipients' exercise of the rights granted herein.
562 You are not responsible for enforcing compliance by third parties to
563 this License.
564
565 @item
566 If, as a consequence of a court judgment or allegation of patent
567 infringement or for any other reason (not limited to patent issues),
568 conditions are imposed on you (whether by court order, agreement or
569 otherwise) that contradict the conditions of this License, they do not
570 excuse you from the conditions of this License. If you cannot
571 distribute so as to satisfy simultaneously your obligations under this
572 License and any other pertinent obligations, then as a consequence you
573 may not distribute the Program at all. For example, if a patent
574 license would not permit royalty-free redistribution of the Program by
575 all those who receive copies directly or indirectly through you, then
576 the only way you could satisfy both it and this License would be to
577 refrain entirely from distribution of the Program.
578
579 If any portion of this section is held invalid or unenforceable under
580 any particular circumstance, the balance of the section is intended to
581 apply and the section as a whole is intended to apply in other
582 circumstances.
583
584 It is not the purpose of this section to induce you to infringe any
585 patents or other property right claims or to contest validity of any
586 such claims; this section has the sole purpose of protecting the
587 integrity of the free software distribution system, which is
588 implemented by public license practices. Many people have made
589 generous contributions to the wide range of software distributed
590 through that system in reliance on consistent application of that
591 system; it is up to the author/donor to decide if he or she is willing
592 to distribute software through any other system and a licensee cannot
593 impose that choice.
594
595 This section is intended to make thoroughly clear what is believed to
596 be a consequence of the rest of this License.
597
598 @item
599 If the distribution and/or use of the Program is restricted in
600 certain countries either by patents or by copyrighted interfaces, the
601 original copyright holder who places the Program under this License
602 may add an explicit geographical distribution limitation excluding
603 those countries, so that distribution is permitted only in or among
604 countries not thus excluded. In such case, this License incorporates
605 the limitation as if written in the body of this License.
606
607 @item
608 The Free Software Foundation may publish revised and/or new versions
609 of the General Public License from time to time. Such new versions will
610 be similar in spirit to the present version, but may differ in detail to
611 address new problems or concerns.
612
613 Each version is given a distinguishing version number. If the Program
614 specifies a version number of this License which applies to it and ``any
615 later version'', you have the option of following the terms and conditions
616 either of that version or of any later version published by the Free
617 Software Foundation. If the Program does not specify a version number of
618 this License, you may choose any version ever published by the Free Software
619 Foundation.
620
621 @item
622 If you wish to incorporate parts of the Program into other free
623 programs whose distribution conditions are different, write to the author
624 to ask for permission. For software which is copyrighted by the Free
625 Software Foundation, write to the Free Software Foundation; we sometimes
626 make exceptions for this. Our decision will be guided by the two goals
627 of preserving the free status of all derivatives of our free software and
628 of 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
638 BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
639 FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN
640 OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
641 PROVIDE THE PROGRAM ``AS IS'' WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
642 OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
643 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS
644 TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE
645 PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
646 REPAIR OR CORRECTION.
647
648 @item
649 IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
650 WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
651 REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
652 INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
653 OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
654 TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
655 YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
656 PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
657 POSSIBILITY 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
671 possible use to the public, the best way to achieve this is to make it
672 free 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
675 to attach them to the start of each source file to most effectively
676 convey the exclusion of warranty; and each file should have at least
677 the ``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.}
681 Copyright (C) 19@var{yy} @var{name of author}
682
683 This program is free software; you can redistribute it and/or modify
684 it under the terms of the GNU General Public License as published by
685 the Free Software Foundation; either version 2 of the License, or
686 (at your option) any later version.
687
688 This program is distributed in the hope that it will be useful,
689 but WITHOUT ANY WARRANTY; without even the implied warranty of
690 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
691 GNU General Public License for more details.
692
693 You should have received a copy of the GNU General Public License
694 along with this program; if not, write to the Free Software
695 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
696 @end smallexample
697
698 Also add information on how to contact you by electronic and paper mail.
699
700 If the program is interactive, make it output a short notice like this
701 when it starts in an interactive mode:
702
703 @smallexample
704 Gnomovision version 69, Copyright (C) 19@var{yy} @var{name of author}
705 Gnomovision comes with ABSOLUTELY NO WARRANTY; for details
706 type `show w'.
707 This is free software, and you are welcome to redistribute it
708 under certain conditions; type `show c' for details.
709 @end smallexample
710
711 The hypothetical commands @samp{show w} and @samp{show c} should show
712 the appropriate parts of the General Public License. Of course, the
713 commands 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
715 suits your program.
716
717 You should also get your employer (if you work as a programmer) or your
718 school, if any, to sign a ``copyright disclaimer'' for the program, if
719 necessary. Here is a sample; alter the names:
720
721 @smallexample
722 Yoyodyne, 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
726 Ty Coon, President of Vice
727 @end smallexample
728
729 This General Public License does not permit incorporating your program into
730 proprietary programs. If your program is a subroutine library, you may
731 consider it more useful to permit linking proprietary applications with the
732 library. If this is what you want to do, use the GNU Library General
733 Public License instead of this License.
734
735 @node Concepts, Examples, Copying, Top
736 @chapter The Concepts of Bison
737
738 This chapter introduces many of the basic concepts without which the
739 details of Bison will not make sense. If you do not already know how to
740 use 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
761 In 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
764 parts. 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
766 can 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
768 recursive, but there must be at least one rule which leads out of the
769 recursion.
770
771 @cindex BNF
772 @cindex Backus-Naur form
773 The most common formal system for presenting such rules for humans to read
774 is @dfn{Backus-Naur Form} or ``BNF'', which was developed in order to
775 specify the language Algol 60. Any grammar expressed in BNF is a
776 context-free grammar. The input to Bison is essentially machine-readable
777 BNF.
778
779 Not all context-free languages can be handled by Bison, only those
780 that are LALR(1). In brief, this means that it must be possible to
781 tell how to parse any portion of an input string with just a single
782 token of look-ahead. Strictly speaking, that is a description of an
783 LR(1) grammar, and LALR(1) involves additional restrictions that are
784 hard to explain simply; but it is rare in actual practice to find an
785 LR(1) grammar that fails to be LALR(1). @xref{Mystery Conflicts, ,
786 Mysterious Reduce/Reduce Conflicts}, for more information on this.
787
788 @cindex symbols (abstract)
789 @cindex token
790 @cindex syntactic grouping
791 @cindex grouping, syntactic
792 In the formal grammatical rules for a language, each kind of syntactic unit
793 or grouping is named by a @dfn{symbol}. Those which are built by grouping
794 smaller 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
797 corresponding to a single terminal symbol a @dfn{token}, and a piece
798 corresponding to a single nonterminal symbol a @dfn{grouping}.@refill
799
800 We can use the C language as an example of what symbols, terminal and
801 nonterminal, mean. The tokens of C are identifiers, constants (numeric and
802 string), and the various keywords, arithmetic operators and punctuation
803 marks. So the terminal symbols of a grammar for C include `identifier',
804 `number', `string', plus one symbol for each keyword, operator or
805 punctuation mark: `if', `return', `const', `static', `int', `char',
806 `plus-sign', `open-brace', `close-brace', `comma' and many more. (These
807 tokens can be subdivided into characters, but that is a matter of
808 lexicography, not grammar.)
809
810 Here is a simple C function subdivided into tokens:
811
812 @example
813 int /* @r{keyword `int'} */
814 square (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
823 The syntactic groupings of C include the expression, the statement, the
824 declaration, and the function definition. These are represented in the
825 grammar of C by nonterminal symbols `expression', `statement',
826 `declaration' and `function definition'. The full grammar uses dozens of
827 additional language constructs, each with its own nonterminal symbol, in
828 order to express the meanings of these four. The example above is a
829 function definition; it contains one declaration, and one statement. In
830 the statement, each @samp{x} is an expression and so is @samp{x * x}.
831
832 Each nonterminal symbol must have grammatical rules showing how it is made
833 out 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
835 reads informally as follows:
836
837 @quotation
838 A `statement' can be made of a `return' keyword, an `expression' and a
839 `semicolon'.
840 @end quotation
841
842 @noindent
843 There would be many other rules for `statement', one for each kind of
844 statement in C.
845
846 @cindex start symbol
847 One nonterminal symbol must be distinguished as the special one which
848 defines a complete utterance in the language. It is called the @dfn{start
849 symbol}. In a compiler, this means a complete input program. In the C
850 language, the nonterminal symbol `sequence of definitions and declarations'
851 plays this role.
852
853 For example, @samp{1 + 2} is a valid C expression---a valid part of a C
854 program---but it is not valid as an @emph{entire} C program. In the
855 context-free grammar of C, this follows from the fact that `expression' is
856 not the start symbol.
857
858 The Bison parser reads a sequence of tokens as its input, and groups the
859 tokens using the grammar rules. If the input is valid, the end result is
860 that the entire token sequence reduces to a single grouping whose symbol is
861 the grammar's start symbol. If we use a grammar for C, the entire input
862 must be a `sequence of definitions and declarations'. If not, the parser
863 reports 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
871 A formal grammar is a mathematical construct. To define the language
872 for Bison, you must write a file expressing the grammar in Bison syntax:
873 a @dfn{Bison grammar} file. @xref{Grammar File, ,Bison Grammar Files}.
874
875 A nonterminal symbol in the formal grammar is represented in Bison input
876 as an identifier, like an identifier in C. By convention, it should be
877 in lower case, such as @code{expr}, @code{stmt} or @code{declaration}.
878
879 The Bison representation for a terminal symbol is also called a @dfn{token
880 type}. Token types as well can be represented as C-like identifiers. By
881 convention, these identifiers should be upper case to distinguish them from
882 nonterminals: for example, @code{INTEGER}, @code{IDENTIFIER}, @code{IF} or
883 @code{RETURN}. A terminal symbol that stands for a particular keyword in
884 the language should be named after that keyword converted to upper case.
885 The terminal symbol @code{error} is reserved for error recovery.
886 @xref{Symbols}.
887
888 A terminal symbol can also be represented as a character literal, just like
889 a C character constant. You should do this whenever a token is just a
890 single character (parenthesis, plus-sign, etc.): use that same character in
891 a literal as the terminal symbol for that token.
892
893 A third way to represent a terminal symbol is with a C string constant
894 containing several characters. @xref{Symbols}, for more information.
895
896 The grammar rules also have an expression in Bison syntax. For example,
897 here is the Bison rule for a C @code{return} statement. The semicolon in
898 quotes is a literal character token, representing part of the C syntax for
899 the statement; the naked semicolon, and the colon, are Bison punctuation
900 used in every rule.
901
902 @example
903 stmt: 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
915 A formal grammar selects tokens only by their classifications: for example,
916 if a rule mentions the terminal symbol `integer constant', it means that
917 @emph{any} integer constant is grammatically valid in that position. The
918 precise 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
920 grammatical.@refill
921
922 But the precise value is very important for what the input means once it is
923 parsed. A compiler is useless if it fails to distinguish between 4, 1 and
924 3989 as constants in the program! Therefore, each token in a Bison grammar
925 has both a token type and a @dfn{semantic value}. @xref{Semantics, ,Defining Language Semantics},
926 for details.
927
928 The token type is a terminal symbol defined in the grammar, such as
929 @code{INTEGER}, @code{IDENTIFIER} or @code{','}. It tells everything
930 you need to know to decide where the token may validly appear and how to
931 group it with other tokens. The grammar rules know nothing about tokens
932 except their types.@refill
933
934 The semantic value has all the rest of the information about the
935 meaning of the token, such as the value of an integer, or the name of an
936 identifier. (A token such as @code{','} which is just punctuation doesn't
937 need to have any semantic value.)
938
939 For example, an input token might be classified as token type
940 @code{INTEGER} and have the semantic value 4. Another input token might
941 have the same token type @code{INTEGER} but value 3989. When a grammar
942 rule says that @code{INTEGER} is allowed, either of these tokens is
943 acceptable because each is an @code{INTEGER}. When the parser accepts the
944 token, it keeps track of the token's semantic value.
945
946 Each grouping can also have a semantic value as well as its nonterminal
947 symbol. For example, in a calculator, an expression typically has a
948 semantic value that is a number. In a compiler for a programming
949 language, an expression typically has a semantic value that is a tree
950 structure 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
957 In order to be useful, a program must do more than parse input; it must
958 also produce some output based on the input. In a Bison grammar, a grammar
959 rule can have an @dfn{action} made up of C statements. Each time the
960 parser recognizes a match for that rule, the action is executed.
961 @xref{Actions}.
962
963 Most of the time, the purpose of an action is to compute the semantic value
964 of the whole construct from the semantic values of its parts. For example,
965 suppose we have a rule which says an expression can be the sum of two
966 expressions. When the parser recognizes such a sum, each of the
967 subexpressions has a semantic value which describes how it was built up.
968 The action for this rule should create a similar sort of value for the
969 newly recognized larger expression.
970
971 For example, here is a rule that says an expression can be the sum of
972 two subexpressions:
973
974 @example
975 expr: expr '+' expr @{ $$ = $1 + $3; @}
976 ;
977 @end example
978
979 @noindent
980 The action says how to produce the semantic value of the sum expression
981 from 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
990 When you run Bison, you give it a Bison grammar file as input. The output
991 is a C source file that parses the language described by the grammar.
992 This file is called a @dfn{Bison parser}. Keep in mind that the Bison
993 utility and the Bison parser are two distinct programs: the Bison utility
994 is a program whose output is the Bison parser that becomes part of your
995 program.
996
997 The job of the Bison parser is to group tokens into groupings according to
998 the grammar rules---for example, to build identifiers and operators into
999 expressions. As it does this, it runs the actions for the grammar rules it
1000 uses.
1001
1002 The tokens come from a function called the @dfn{lexical analyzer} that you
1003 must supply in some fashion (such as by writing it in C). The Bison parser
1004 calls the lexical analyzer each time it wants a new token. It doesn't know
1005 what is ``inside'' the tokens (though their semantic values may reflect
1006 this). Typically the lexical analyzer makes the tokens by parsing
1007 characters of text, but Bison does not depend on this. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
1008
1009 The Bison parser file is C code which defines a function named
1010 @code{yyparse} which implements that grammar. This function does not make
1011 a complete C program: you must supply some additional functions. One is
1012 the lexical analyzer. Another is an error-reporting function which the
1013 parser calls to report an error. In addition, a complete C program must
1014 start with a function called @code{main}; you have to provide this, and
1015 arrange for it to call @code{yyparse} or the parser will never run.
1016 @xref{Interface, ,Parser C-Language Interface}.
1017
1018 Aside from the token type names and the symbols in the actions you
1019 write, all variable and function names used in the Bison parser file
1020 begin with @samp{yy} or @samp{YY}. This includes interface functions
1021 such as the lexical analyzer function @code{yylex}, the error reporting
1022 function @code{yyerror} and the parser function @code{yyparse} itself.
1023 This also includes numerous identifiers used for internal purposes.
1024 Therefore, you should avoid using C identifiers starting with @samp{yy}
1025 or @samp{YY} in the Bison grammar file except for the ones defined in
1026 this 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
1033 The actual language-design process using Bison, from grammar specification
1034 to a working compiler or interpreter, has these parts:
1035
1036 @enumerate
1037 @item
1038 Formally specify the grammar in a form recognized by Bison
1039 (@pxref{Grammar File, ,Bison Grammar Files}). For each grammatical rule in the language,
1040 describe the action that is to be taken when an instance of that rule
1041 is recognized. The action is described by a sequence of C statements.
1042
1043 @item
1044 Write a lexical analyzer to process input and pass tokens to the
1045 parser. 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
1047 of Lex is not discussed in this manual.
1048
1049 @item
1050 Write a controlling function that calls the Bison-produced parser.
1051
1052 @item
1053 Write error-reporting routines.
1054 @end enumerate
1055
1056 To turn this source code as written into a runnable program, you
1057 must follow these steps:
1058
1059 @enumerate
1060 @item
1061 Run Bison on the grammar to produce the parser.
1062
1063 @item
1064 Compile the code output by Bison, as well as any other source files.
1065
1066 @item
1067 Link 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
1077 The input file for the Bison utility is a @dfn{Bison grammar file}. The
1078 general 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
1094 The @samp{%%}, @samp{%@{} and @samp{%@}} are punctuation that appears
1095 in every Bison grammar file to separate the sections.
1096
1097 The C declarations may define types and variables used in the actions.
1098 You 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
1101 The Bison declarations declare the names of the terminal and nonterminal
1102 symbols, and may also describe operator precedence and the data types of
1103 semantic values of various symbols.
1104
1105 The grammar rules define how to construct each nonterminal symbol from its
1106 parts.
1107
1108 The additional C code can contain any C code you want to use. Often the
1109 definition of the lexical analyzer @code{yylex} goes here, plus subroutines
1110 called by the actions in the grammar rules. In a simple program, all the
1111 rest 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
1118 Now we show and explain three sample programs written using Bison: a
1119 reverse polish notation calculator, an algebraic (infix) notation
1120 calculator, and a multi-function calculator. All three have been tested
1121 under BSD Unix 4.3; each produces a usable, though limited, interactive
1122 desk-top calculator.
1123
1124 These examples are simple, but Bison grammars for real programming
1125 languages are written the same way.
1126 @ifinfo
1127 You can copy these examples out of the Info file and into a source file
1128 to 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
1149 The first example is that of a simple double-precision @dfn{reverse polish
1150 notation} calculator (a calculator using postfix operators). This example
1151 provides a good starting point, since operator precedence is not an issue.
1152 The second example will illustrate how operator precedence is handled.
1153
1154 The 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
1170 Here are the C and Bison declarations for the reverse polish notation
1171 calculator. 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
1186 The C declarations section (@pxref{C Declarations, ,The C Declarations Section}) contains two
1187 preprocessor directives.
1188
1189 The @code{#define} directive defines the macro @code{YYSTYPE}, thus
1190 specifying 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
1193 default. Because we specify @code{double}, each token and each expression
1194 has an associated value, which is a floating point number.
1195
1196 The @code{#include} directive is used to declare the exponentiation
1197 function @code{pow}.
1198
1199 The second section, Bison declarations, provides information to Bison about
1200 the token types (@pxref{Bison Declarations, ,The Bison Declarations Section}). Each terminal symbol that is
1201 not a single-character literal must be declared here. (Single-character
1202 literals normally don't need to be declared.) In this example, all the
1203 arithmetic operators are designated by single-character literals, so the
1204 only terminal symbol that needs to be declared is @code{NUM}, the token
1205 type for numeric constants.
1206
1207 @node Rpcalc Rules, Rpcalc Lexer, Rpcalc Decls, RPN Calc
1208 @subsection Grammar Rules for @code{rpcalc}
1209
1210 Here are the grammar rules for the reverse polish notation calculator.
1211
1212 @example
1213 input: /* empty */
1214 | input line
1215 ;
1216
1217 line: '\n'
1218 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1219 ;
1220
1221 exp: 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
1234 The groupings of the rpcalc ``language'' defined here are the expression
1235 (given the name @code{exp}), the line of input (@code{line}), and the
1236 complete input transcript (@code{input}). Each of these nonterminal
1237 symbols has several alternate rules, joined by the @samp{|} punctuator
1238 which is read as ``or''. The following sections explain what these rules
1239 mean.
1240
1241 The semantics of the language is determined by the actions taken when a
1242 grouping is recognized. The actions are the C code that appears inside
1243 braces. @xref{Actions}.
1244
1245 You must specify these actions in C, but Bison provides the means for
1246 passing semantic values between the rules. In each action, the
1247 pseudo-variable @code{$$} stands for the semantic value for the grouping
1248 that the rule is going to construct. Assigning a value to @code{$$} is the
1249 main job of most actions. The semantic values of the components of the
1250 rule 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
1261 Consider the definition of @code{input}:
1262
1263 @example
1264 input: /* empty */
1265 | input line
1266 ;
1267 @end example
1268
1269 This definition reads as follows: ``A complete input is either an empty
1270 string, or a complete input followed by an input line''. Notice that
1271 ``complete input'' is defined in terms of itself. This definition is said
1272 to be @dfn{left recursive} since @code{input} appears always as the
1273 leftmost symbol in the sequence. @xref{Recursion, ,Recursive Rules}.
1274
1275 The first alternative is empty because there are no symbols between the
1276 colon and the first @samp{|}; this means that @code{input} can match an
1277 empty string of input (no tokens). We write the rules this way because it
1278 is legitimate to type @kbd{Ctrl-d} right after you start the calculator.
1279 It's conventional to put an empty alternative first and write the comment
1280 @samp{/* empty */} in it.
1281
1282 The second alternate rule (@code{input line}) handles all nontrivial input.
1283 It means, ``After reading any number of lines, read one more line if
1284 possible.'' The left recursion makes this rule into a loop. Since the
1285 first alternative matches empty input, the loop can be executed zero or
1286 more times.
1287
1288 The parser function @code{yyparse} continues to process input until a
1289 grammatical error is seen or the lexical analyzer says there are no more
1290 input 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
1295 Now consider the definition of @code{line}:
1296
1297 @example
1298 line: '\n'
1299 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1300 ;
1301 @end example
1302
1303 The first alternative is a token which is a newline character; this means
1304 that rpcalc accepts a blank line (and ignores it, since there is no
1305 action). The second alternative is an expression followed by a newline.
1306 This is the alternative that makes rpcalc useful. The semantic value of
1307 the @code{exp} grouping is the value of @code{$1} because the @code{exp} in
1308 question is the first symbol in the alternative. The action prints this
1309 value, which is the result of the computation the user asked for.
1310
1311 This action is unusual because it does not assign a value to @code{$$}. As
1312 a consequence, the semantic value associated with the @code{line} is
1313 uninitialized (its value will be unpredictable). This would be a bug if
1314 that value were ever used, but we don't use it: once rpcalc has printed the
1315 value 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
1320 The @code{exp} grouping has several rules, one for each kind of expression.
1321 The first rule handles the simplest expressions: those that are just numbers.
1322 The second handles an addition-expression, which looks like two expressions
1323 followed by a plus-sign. The third handles subtraction, and so on.
1324
1325 @example
1326 exp: NUM
1327 | exp exp '+' @{ $$ = $1 + $2; @}
1328 | exp exp '-' @{ $$ = $1 - $2; @}
1329 @dots{}
1330 ;
1331 @end example
1332
1333 We have used @samp{|} to join all the rules for @code{exp}, but we could
1334 equally well have written them separately:
1335
1336 @example
1337 exp: NUM ;
1338 exp: exp exp '+' @{ $$ = $1 + $2; @} ;
1339 exp: exp exp '-' @{ $$ = $1 - $2; @} ;
1340 @dots{}
1341 @end example
1342
1343 Most of the rules have actions that compute the value of the expression in
1344 terms 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
1346 the second one. The third component, @code{'+'}, has no meaningful
1347 associated 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
1349 rule, the sum of the two subexpressions' values is produced as the value of
1350 the entire expression. @xref{Actions}.
1351
1352 You don't have to give an action for every rule. When a rule has no
1353 action, Bison by default copies the value of @code{$1} into @code{$$}.
1354 This is what happens in the first rule (the one that uses @code{NUM}).
1355
1356 The formatting shown here is the recommended convention, but Bison does
1357 not require it. You can add or change whitespace as much as you wish.
1358 For example, this:
1359
1360 @example
1361 exp : NUM | exp exp '+' @{$$ = $1 + $2; @} | @dots{}
1362 @end example
1363
1364 @noindent
1365 means the same thing as this:
1366
1367 @example
1368 exp: NUM
1369 | exp exp '+' @{ $$ = $1 + $2; @}
1370 | @dots{}
1371 @end example
1372
1373 @noindent
1374 The 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
1381 The lexical analyzer's job is low-level parsing: converting characters or
1382 sequences of characters into tokens. The Bison parser gets its tokens by
1383 calling the lexical analyzer. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
1384
1385 Only a simple lexical analyzer is needed for the RPN calculator. This
1386 lexical analyzer skips blanks and tabs, then reads in numbers as
1387 @code{double} and returns them as @code{NUM} tokens. Any other character
1388 that isn't part of a number is a separate token. Note that the token-code
1389 for such a single-character token is the character itself.
1390
1391 The return value of the lexical analyzer function is a numeric code which
1392 represents a token type. The same text used in Bison rules to stand for
1393 this token type is also a C expression for the numeric code for the type.
1394 This works in two ways. If the token type is a character literal, then its
1395 numeric code is the ASCII code for that character; you can use the same
1396 character literal in the lexical analyzer to express the number. If the
1397 token type is an identifier, that identifier is defined by Bison as a C
1398 macro whose definition is the appropriate number. In this example,
1399 therefore, @code{NUM} becomes a macro for @code{yylex} to use.
1400
1401 The semantic value of the token (if it has one) is stored into the global
1402 variable @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
1404 at the beginning of the grammar; @pxref{Rpcalc Decls, ,Declarations for @code{rpcalc}}.)
1405
1406 A 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
1408 input.)
1409
1410 Here 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
1423 yylex ()
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
1455 In keeping with the spirit of this example, the controlling function is
1456 kept 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
1461 main ()
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
1472 When @code{yyparse} detects a syntax error, it calls the error reporting
1473 function @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
1481 yyerror (s) /* Called by yyparse on error */
1482 char *s;
1483 @{
1484 printf ("%s\n", s);
1485 @}
1486 @end group
1487 @end example
1488
1489 After @code{yyerror} returns, the Bison parser may recover from the error
1490 and continue parsing if the grammar contains a suitable error rule
1491 (@pxref{Error Recovery}). Otherwise, @code{yyparse} returns nonzero. We
1492 have not written any error rules in this example, so any invalid input will
1493 cause the calculator program to exit. This is not clean behavior for a
1494 real 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
1500 Before running Bison to produce a parser, we need to decide how to arrange
1501 all the source code in one or more source files. For such a simple example,
1502 the 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
1506 For a large project, you would probably have several source files, and use
1507 @code{make} to arrange to recompile them.
1508
1509 With all the source in a single file, you use the following command to
1510 convert it into a parser file:
1511
1512 @example
1513 bison @var{file_name}.y
1514 @end example
1515
1516 @noindent
1517 In this example the file was called @file{rpcalc.y} (for ``Reverse Polish
1518 CALCulator''). Bison produces a file named @file{@var{file_name}.tab.c},
1519 removing the @samp{.y} from the original file name. The file output by
1520 Bison contains the source code for @code{yyparse}. The additional
1521 functions in the input file (@code{yylex}, @code{yyerror} and @code{main})
1522 are 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
1528 Here is how to compile and run the parser file:
1529
1530 @example
1531 @group
1532 # @r{List files in current directory.}
1533 % ls
1534 rpcalc.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
1546 rpcalc rpcalc.tab.c rpcalc.y
1547 @end group
1548 @end example
1549
1550 The file @file{rpcalc} now contains the executable code. Here is an
1551 example session using @code{rpcalc}.
1552
1553 @example
1554 % rpcalc
1555 4 9 +
1556 13
1557 3 7 + 3 4 5 *+-
1558 -13
1559 3 7 + 3 4 5 * + - n @r{Note the unary minus, @samp{n}}
1560 13
1561 5 6 / 4 n +
1562 -3.166666667
1563 3 4 ^ @r{Exponentiation}
1564 81
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
1575 We now modify rpcalc to handle infix operators instead of postfix. Infix
1576 notation involves the concept of operator precedence and the need for
1577 parentheses 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 %%
1597 input: /* empty string */
1598 | input line
1599 ;
1600
1601 line: '\n'
1602 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1603 ;
1604
1605 exp: 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
1618 The functions @code{yylex}, @code{yyerror} and @code{main} can be the same
1619 as before.
1620
1621 There are two important new features shown in this code.
1622
1623 In the second section (Bison declarations), @code{%left} declares token
1624 types 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
1627 associativity. (These tokens are single-character literals, which
1628 ordinarily don't need to be declared. We declare them here to specify
1629 the associativity.)
1630
1631 Operator precedence is determined by the line ordering of the
1632 declarations; the higher the line number of the declaration (lower on
1633 the page or screen), the higher the precedence. Hence, exponentiation
1634 has the highest precedence, unary minus (@code{NEG}) is next, followed
1635 by @samp{*} and @samp{/}, and so on. @xref{Precedence, ,Operator Precedence}.
1636
1637 The other important new feature is the @code{%prec} in the grammar section
1638 for the unary minus operator. The @code{%prec} simply instructs Bison that
1639 the rule @samp{| '-' exp} has the same precedence as @code{NEG}---in this
1640 case the next-to-highest. @xref{Contextual Precedence, ,Context-Dependent Precedence}.
1641
1642 Here is a sample run of @file{calc.y}:
1643
1644 @need 500
1645 @example
1646 % calc
1647 4 + 4.5 - (34/(8*3+-3))
1648 6.880952381
1649 -56 + 2
1650 -54
1651 3 ^ 2
1652 9
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
1659 Up to this point, this manual has not addressed the issue of @dfn{error
1660 recovery}---how to continue parsing after the parser detects a syntax
1661 error. All we have handled is error reporting with @code{yyerror}. Recall
1662 that by default @code{yyparse} returns after calling @code{yyerror}. This
1663 means that an erroneous input line causes the calculator program to exit.
1664 Now we show how to rectify this deficiency.
1665
1666 The Bison language itself includes the reserved word @code{error}, which
1667 may be included in the grammar rules. In the example below it has
1668 been added to one of the alternatives for @code{line}:
1669
1670 @example
1671 @group
1672 line: '\n'
1673 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1674 | error '\n' @{ yyerrok; @}
1675 ;
1676 @end group
1677 @end example
1678
1679 This addition to the grammar allows for simple error recovery in the event
1680 of a parse error. If an expression that cannot be evaluated is read, the
1681 error will be recognized by the third rule for @code{line}, and parsing
1682 will continue. (The @code{yyerror} function is still called upon to print
1683 its message as well.) The action executes the statement @code{yyerrok}, a
1684 macro defined automatically by Bison; its meaning is that error recovery is
1685 complete (@pxref{Error Recovery}). Note the difference between
1686 @code{yyerrok} and @code{yyerror}; neither one is a misprint.@refill
1687
1688 This form of error recovery deals with syntax errors. There are other
1689 kinds of errors; for example, division by zero, which raises an exception
1690 signal that is normally fatal. A real calculator program must handle this
1691 signal and use @code{longjmp} to return to @code{main} and resume parsing
1692 input lines; it would also have to discard the rest of the current line of
1693 input. We won't discuss this issue further because it is not specific to
1694 Bison 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
1702 Now that the basics of Bison have been discussed, it is time to move on to
1703 a more advanced problem. The above calculators provided only five
1704 functions, @samp{+}, @samp{-}, @samp{*}, @samp{/} and @samp{^}. It would
1705 be nice to have a calculator that provides other mathematical functions such
1706 as @code{sin}, @code{cos}, etc.
1707
1708 It is easy to add new operators to the infix calculator as long as they are
1709 only single-character literals. The lexical analyzer @code{yylex} passes
1710 back all non-number characters as tokens, so new grammar rules suffice for
1711 adding a new operator. But we want something more flexible: built-in
1712 functions whose syntax has this form:
1713
1714 @example
1715 @var{function_name} (@var{argument})
1716 @end example
1717
1718 @noindent
1719 At the same time, we will add memory to the calculator, by allowing you
1720 to create named variables, store values in them, and use them later.
1721 Here is a sample session with the multi-function calculator:
1722
1723 @example
1724 % mfcalc
1725 pi = 3.141592653589
1726 3.1415926536
1727 sin(pi)
1728 0.0000000000
1729 alpha = beta1 = 2.3
1730 2.3000000000
1731 alpha
1732 2.3000000000
1733 ln(alpha)
1734 0.8329091229
1735 exp(ln(beta1))
1736 2.3000000000
1737 %
1738 @end example
1739
1740 Note 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
1751 Here 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 @{
1759 double val; /* For returning numbers. */
1760 symrec *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
1778 The above grammar introduces only two new features of the Bison language.
1779 These features allow semantic values to have various data types
1780 (@pxref{Multiple Types, ,More Than One Value Type}).
1781
1782 The @code{%union} declaration specifies the entire list of possible types;
1783 this is instead of defining @code{YYSTYPE}. The allowable types are now
1784 double-floats (for @code{exp} and @code{NUM}) and pointers to entries in
1785 the symbol table. @xref{Union Decl, ,The Collection of Value Types}.
1786
1787 Since values can now have various types, it is necessary to associate a
1788 type with each grammar symbol whose semantic value is used. These symbols
1789 are @code{NUM}, @code{VAR}, @code{FNCT}, and @code{exp}. Their
1790 declarations are augmented with information about their data type (placed
1791 between angle brackets).
1792
1793 The Bison construct @code{%type} is used for declaring nonterminal symbols,
1794 just as @code{%token} is used for declaring token types. We have not used
1795 @code{%type} before because nonterminal symbols are normally declared
1796 implicitly by the rules that define them. But @code{exp} must be declared
1797 explicitly 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
1802 Here are the grammar rules for the multi-function calculator.
1803 Most of them are copied directly from @code{calc}; three rules,
1804 those which mention @code{VAR} or @code{FNCT}, are new.
1805
1806 @smallexample
1807 input: /* empty */
1808 | input line
1809 ;
1810
1811 line:
1812 '\n'
1813 | exp '\n' @{ printf ("\t%.10g\n", $1); @}
1814 | error '\n' @{ yyerrok; @}
1815 ;
1816
1817 exp: 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
1837 The multi-function calculator requires a symbol table to keep track of the
1838 names and meanings of variables and functions. This doesn't affect the
1839 grammar rules (except for the actions) or the Bison declarations, but it
1840 requires some additional C functions for support.
1841
1842 The symbol table itself consists of a linked list of records. Its
1843 definition, which is kept in the header @file{calc.h}, is as follows. It
1844 provides 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. */
1849 struct 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
1862 typedef struct symrec symrec;
1863
1864 /* The symbol table: a chain of `struct symrec'. */
1865 extern symrec *sym_table;
1866
1867 symrec *putsym ();
1868 symrec *getsym ();
1869 @end group
1870 @end smallexample
1871
1872 The new version of @code{main} includes a call to @code{init_table}, a
1873 function 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
1880 main ()
1881 @{
1882 init_table ();
1883 yyparse ();
1884 @}
1885 @end group
1886
1887 @group
1888 yyerror (s) /* Called by yyparse on error */
1889 char *s;
1890 @{
1891 printf ("%s\n", s);
1892 @}
1893
1894 struct init
1895 @{
1896 char *fname;
1897 double (*fnct)();
1898 @};
1899 @end group
1900
1901 @group
1902 struct 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'. */
1914 symrec *sym_table = (symrec *)0;
1915 @end group
1916
1917 @group
1918 init_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
1931 By simply editing the initialization list and adding the necessary include
1932 files, you can add additional functions to the calculator.
1933
1934 Two important functions allow look-up and installation of symbols in the
1935 symbol 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
1937 linked to the front of the list, and a pointer to the object is returned.
1938 The function @code{getsym} is passed the name of the symbol to look up. If
1939 found, a pointer to that symbol is returned; otherwise zero is returned.
1940
1941 @smallexample
1942 symrec *
1943 putsym (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
1958 symrec *
1959 getsym (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
1971 The function @code{yylex} must now recognize variables, numeric values, and
1972 the single-character arithmetic operators. Strings of alphanumeric
1973 characters with a leading nondigit are recognized as either variables or
1974 functions depending on what the symbol table says about them.
1975
1976 The string is passed to @code{getsym} for look up in the symbol table. If
1977 the 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
1979 already 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
1981 returned to @code{yyparse}.@refill
1982
1983 No change is needed in the handling of numeric values and arithmetic
1984 operators in @code{yylex}.
1985
1986 @smallexample
1987 @group
1988 #include <ctype.h>
1989 yylex ()
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
2064 This program is both powerful and flexible. You may easily add new
2065 functions, and it is a simple job to modify this code to install predefined
2066 variables 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
2074 Add some new functions from @file{math.h} to the initialization list.
2075
2076 @item
2077 Add another array that contains constants and their values. Then
2078 modify @code{init_table} to add these constants to the symbol table.
2079 It will be easiest to give the constants type @code{VAR}.
2080
2081 @item
2082 Make the program report an error if the user refers to an
2083 uninitialized 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
2089 Bison takes as input a context-free grammar specification and produces a
2090 C-language function that recognizes correct instances of the grammar.
2091
2092 The 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
2107 A Bison grammar file has four main sections, shown here with the
2108 appropriate 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
2124 Comments 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
2138 The @var{C declarations} section contains macro definitions and
2139 declarations of functions and variables that are used in the actions in the
2140 grammar rules. These are copied to the beginning of the parser file so
2141 that 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
2143 need any C declarations, you may omit the @samp{%@{} and @samp{%@}}
2144 delimiters 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
2151 The @var{Bison declarations} section contains declarations that define
2152 terminal and nonterminal symbols, specify precedence, and so on.
2153 In 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
2161 The @dfn{grammar rules} section contains one or more Bison grammar
2162 rules, and nothing else. @xref{Rules, ,Syntax of Grammar Rules}.
2163
2164 There must always be at least one grammar rule, and the first
2165 @samp{%%} (which precedes the grammar rules) may never be omitted even
2166 if 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
2173 The @var{additional C code} section is copied verbatim to the end of
2174 the parser file, just as the @var{C declarations} section is copied to
2175 the beginning. This is the most convenient place to put anything
2176 that you want to have in the parser file but which need not come before
2177 the 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
2180 If the last section is empty, you may omit the @samp{%%} that separates it
2181 from the grammar rules.
2182
2183 The Bison parser itself contains many static variables whose names start
2184 with @samp{yy} and many macros whose names start with @samp{YY}. It is a
2185 good idea to avoid using any such names (except those documented in this
2186 manual) 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
2196 of the language.
2197
2198 A @dfn{terminal symbol} (also known as a @dfn{token type}) represents a
2199 class of syntactically equivalent tokens. You use the symbol in grammar
2200 rules to mean that a token in that class is allowed. The symbol is
2201 represented in the Bison parser by a numeric code, and the @code{yylex}
2202 function returns a token type code to indicate what kind of token has been
2203 read. You don't need to know what the code value is; you can use the
2204 symbol to stand for it.
2205
2206 A @dfn{nonterminal symbol} stands for a class of syntactically equivalent
2207 groupings. The symbol name is used in writing grammar rules. By convention,
2208 it should be all lower case.
2209
2210 Symbol names can contain letters, digits (not at the beginning),
2211 underscores and periods. Periods make sense only in nonterminals.
2212
2213 There are three ways of writing terminal symbols in the grammar:
2214
2215 @itemize @bullet
2216 @item
2217 A @dfn{named token type} is written with an identifier, like an
2218 identifier in C. By convention, it should be all upper case. Each
2219 such 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
2226 A @dfn{character token type} (or @dfn{literal character token}) is
2227 written in the grammar using the same syntax used in C for character
2228 constants; for example, @code{'+'} is a character token type. A
2229 character token type doesn't need to be declared unless you need to
2230 specify its semantic value data type (@pxref{Value Type, ,Data Types of
2231 Semantic Values}), associativity, or precedence (@pxref{Precedence,
2232 ,Operator Precedence}).
2233
2234 By convention, a character token type is used only to represent a
2235 token that consists of that particular character. Thus, the token
2236 type @code{'+'} is used to represent the character @samp{+} as a
2237 token. Nothing enforces this convention, but if you depart from it,
2238 your program will confuse other readers.
2239
2240 All the usual escape sequences used in character literals in C can be
2241 used in Bison as well, but you must not use the null character as a
2242 character literal because its ASCII code, zero, is the code @code{yylex}
2243 returns for end-of-input (@pxref{Calling Convention, ,Calling Convention
2244 for @code{yylex}}).
2245
2246 @item
2247 @cindex string token
2248 @cindex literal string token
2249 @cindex multi-character literal
2250 A @dfn{literal string token} is written like a C string constant; for
2251 example, @code{"<="} is a literal string token. A literal string token
2252 doesn't need to be declared unless you need to specify its semantic
2253 value data type (@pxref{Value Type}), associativity, precedence
2254 (@pxref{Precedence}).
2255
2256 You can associate the literal string token with a symbolic name as an
2257 alias, using the @code{%token} declaration (@pxref{Token Decl, ,Token
2258 Declarations}). If you don't do that, the lexical analyzer has to
2259 retrieve 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
2264 By convention, a literal string token is used only to represent a token
2265 that consists of that particular string. Thus, you should use the token
2266 type @code{"<="} to represent the string @samp{<=} as a token. Bison
2267 does not enforces this convention, but if you depart from it, people who
2268 read your program will be confused.
2269
2270 All the escape sequences used in string literals in C can be used in
2271 Bison as well. A literal string token must contain two or more
2272 characters; for a token containing just one character, use a character
2273 token (see above).
2274 @end itemize
2275
2276 How you choose to write a terminal symbol has no effect on its
2277 grammatical meaning. That depends only on where it appears in rules and
2278 on when the parser function returns that symbol.
2279
2280 The 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
2282 grammar rules, you write it the same way in the definition of @code{yylex}.
2283 The numeric code for a character token type is simply the ASCII code for
2284 the character, so @code{yylex} can use the identical character constant to
2285 generate the requisite code. Each named token type becomes a C macro in
2286 the 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
2290 If @code{yylex} is defined in a separate file, you need to arrange for the
2291 token-type macro definitions to be available there. Use the @samp{-d}
2292 option when you run Bison, so that it will write these macro definitions
2293 into a separate header file @file{@var{name}.tab.h} which you can include
2294 in the other source files that need it. @xref{Invocation, ,Invoking Bison}.
2295
2296 The symbol @code{error} is a terminal symbol reserved for error recovery
2297 (@pxref{Error Recovery}); you shouldn't use it for any other purpose.
2298 In 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
2306 A 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
2316 where @var{result} is the nonterminal symbol that this rule describes
2317 and @var{components} are various terminal and nonterminal symbols that
2318 are put together by this rule (@pxref{Symbols}).
2319
2320 For example,
2321
2322 @example
2323 @group
2324 exp: exp '+' exp
2325 ;
2326 @end group
2327 @end example
2328
2329 @noindent
2330 says that two groupings of type @code{exp}, with a @samp{+} token in between,
2331 can be combined into a larger grouping of type @code{exp}.
2332
2333 Whitespace in rules is significant only to separate symbols. You can add
2334 extra whitespace as you wish.
2335
2336 Scattered among the components can be @var{actions} that determine
2337 the semantics of the rule. An action looks like this:
2338
2339 @example
2340 @{@var{C statements}@}
2341 @end example
2342
2343 @noindent
2344 Usually there is only one action and it follows the components.
2345 @xref{Actions}.
2346
2347 @findex |
2348 Multiple rules for the same @var{result} can be written separately or can
2349 be 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
2371 They are still considered distinct rules even when joined in this way.
2372
2373 If @var{components} in a rule is empty, it means that @var{result} can
2374 match the empty string. For example, here is how to define a
2375 comma-separated sequence of zero or more @code{exp} groupings:
2376
2377 @example
2378 @group
2379 expseq: /* empty */
2380 | expseq1
2381 ;
2382 @end group
2383
2384 @group
2385 expseq1: exp
2386 | expseq1 ',' exp
2387 ;
2388 @end group
2389 @end example
2390
2391 @noindent
2392 It is customary to write a comment @samp{/* empty */} in each rule
2393 with no components.
2394
2395 @node Recursion, Semantics, Rules, Grammar File
2396 @section Recursive Rules
2397 @cindex recursive rule
2398
2399 A rule is called @dfn{recursive} when its @var{result} nonterminal appears
2400 also on its right hand side. Nearly all Bison grammars need to use
2401 recursion, because that is the only way to define a sequence of any number
2402 of somethings. Consider this recursive definition of a comma-separated
2403 sequence of one or more expressions:
2404
2405 @example
2406 @group
2407 expseq1: exp
2408 | expseq1 ',' exp
2409 ;
2410 @end group
2411 @end example
2412
2413 @cindex left recursion
2414 @cindex right recursion
2415 @noindent
2416 Since the recursive use of @code{expseq1} is the leftmost symbol in the
2417 right hand side, we call this @dfn{left recursion}. By contrast, here
2418 the same construct is defined using @dfn{right recursion}:
2419
2420 @example
2421 @group
2422 expseq1: exp
2423 | exp ',' expseq1
2424 ;
2425 @end group
2426 @end example
2427
2428 @noindent
2429 Any kind of sequence can be defined using either left recursion or
2430 right recursion, but you should always use left recursion, because it
2431 can parse a sequence of any number of elements with bounded stack
2432 space. Right recursion uses up space on the Bison stack in proportion
2433 to the number of elements in the sequence, because all the elements
2434 must be shifted onto the stack before the rule can be applied even
2435 once. @xref{Algorithm, ,The Bison Parser Algorithm }, for
2436 further explanation of this.
2437
2438 @cindex mutual recursion
2439 @dfn{Indirect} or @dfn{mutual} recursion occurs when the result of the
2440 rule does not appear directly on its right hand side, but does appear
2441 in rules for other nonterminals which do appear on its right hand
2442 side.
2443
2444 For example:
2445
2446 @example
2447 @group
2448 expr: primary
2449 | primary '+' primary
2450 ;
2451 @end group
2452
2453 @group
2454 primary: constant
2455 | '(' expr ')'
2456 ;
2457 @end group
2458 @end example
2459
2460 @noindent
2461 defines two mutually-recursive nonterminals, since each refers to the
2462 other.
2463
2464 @node Semantics, Declarations, Recursion, Grammar File
2465 @section Defining Language Semantics
2466 @cindex defining language semantics
2467 @cindex language semantics, defining
2468
2469 The grammar rules for a language determine only the syntax. The semantics
2470 are determined by the semantic values associated with various tokens and
2471 groupings, and by the actions taken when various groupings are recognized.
2472
2473 For example, the calculator calculates properly because the value
2474 associated with each expression is the proper number; it adds properly
2475 because the action for the grouping @w{@samp{@var{x} + @var{y}}} is to add
2476 the 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
2495 In a simple program it may be sufficient to use the same data type for
2496 the semantic values of all language constructs. This was true in the
2497 RPN and infix calculator examples (@pxref{RPN Calc, ,Reverse Polish Notation Calculator}).
2498
2499 Bison's default is to use type @code{int} for all semantic values. To
2500 specify some other type, define @code{YYSTYPE} as a macro, like this:
2501
2502 @example
2503 #define YYSTYPE double
2504 @end example
2505
2506 @noindent
2507 This macro definition must go in the C declarations section of the grammar
2508 file (@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
2513 In most programs, you will need different data types for different kinds
2514 of 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 *},
2516 and an identifier might need a pointer to an entry in the symbol table.
2517
2518 To use more than one data type for semantic values in one parser, Bison
2519 requires you to do two things:
2520
2521 @itemize @bullet
2522 @item
2523 Specify 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
2527 Choose one of those types for each symbol (terminal or nonterminal)
2528 for 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
2530 with 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
2539 An action accompanies a syntactic rule and contains C code to be executed
2540 each time an instance of that rule is recognized. The task of most actions
2541 is to compute a semantic value for the grouping built by the rule from the
2542 semantic values associated with tokens or smaller groupings.
2543
2544 An action consists of C statements surrounded by braces, much like a
2545 compound statement in C. It can be placed at any position in the rule; it
2546 is executed at that position. Most rules have just one action at the end
2547 of the rule, following all the components. Actions in the middle of a rule
2548 are tricky and used only for special purposes (@pxref{Mid-Rule Actions, ,Actions in Mid-Rule}).
2549
2550 The C code in an action can refer to the semantic values of the components
2551 matched by the rule with the construct @code{$@var{n}}, which stands for
2552 the value of the @var{n}th component. The semantic value for the grouping
2553 being constructed is @code{$$}. (Bison translates both of these constructs
2554 into array element references when it copies the actions into the parser
2555 file.)
2556
2557 Here is a typical example:
2558
2559 @example
2560 @group
2561 exp: @dots{}
2562 | exp '+' exp
2563 @{ $$ = $1 + $3; @}
2564 @end group
2565 @end example
2566
2567 @noindent
2568 This rule constructs an @code{exp} from two smaller @code{exp} groupings
2569 connected by a plus-sign token. In the action, @code{$1} and @code{$3}
2570 refer to the semantic values of the two component @code{exp} groupings,
2571 which are the first and third symbols on the right hand side of the rule.
2572 The sum is stored into @code{$$} so that it becomes the semantic value of
2573 the addition-expression just recognized by the rule. If there were a
2574 useful semantic value associated with the @samp{+} token, it could be
2575 referred to as @code{$2}.@refill
2576
2577 @cindex default action
2578 If 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
2580 the value of the whole rule. Of course, the default rule is valid only
2581 if the two data types match. There is no meaningful default action for
2582 an empty rule; every empty rule must have an explicit action unless the
2583 rule's value does not matter.
2584
2585 @code{$@var{n}} with @var{n} zero or negative is allowed for reference
2586 to tokens and groupings on the stack @emph{before} those that match the
2587 current rule. This is a very risky practice, and to use it reliably
2588 you must be certain of the context in which the rule is applied. Here
2589 is a case in which you can use this reliably:
2590
2591 @example
2592 @group
2593 foo: expr bar '+' expr @{ @dots{} @}
2594 | expr bar '-' expr @{ @dots{} @}
2595 ;
2596 @end group
2597
2598 @group
2599 bar: /* empty */
2600 @{ previous_expr = $0; @}
2601 ;
2602 @end group
2603 @end example
2604
2605 As long as @code{bar} is used only in the fashion shown here, @code{$0}
2606 always refers to the @code{expr} which precedes @code{bar} in the
2607 definition 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
2614 If you have chosen a single data type for semantic values, the @code{$$}
2615 and @code{$@var{n}} constructs always have that data type.
2616
2617 If you have used @code{%union} to specify a variety of data types, then you
2618 must declare a choice among these types for each terminal or nonterminal
2619 symbol 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
2621 in the rule. In this example,@refill
2622
2623 @example
2624 @group
2625 exp: @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
2633 have 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
2635 terminal symbol @code{'+'}, whatever that might be.@refill
2636
2637 Alternatively, you can specify the data type when you refer to the value,
2638 by inserting @samp{<@var{type}>} after the @samp{$} at the beginning of the
2639 reference. 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
2651 then you can write @code{$<itype>1} to refer to the first subunit of the
2652 rule 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
2659 Occasionally it is useful to put an action in the middle of a rule.
2660 These actions are written just like usual end-of-rule actions, but they
2661 are executed before the parser even recognizes the following components.
2662
2663 A mid-rule action may refer to the components preceding it using
2664 @code{$@var{n}}, but it may not refer to subsequent components because
2665 it is run before they are parsed.
2666
2667 The mid-rule action itself counts as one of the components of the rule.
2668 This 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
2670 along with the symbols when working out which number @var{n} to use in
2671 @code{$@var{n}}.
2672
2673 The mid-rule action can also have a semantic value. The action can set
2674 its value with an assignment to @code{$$}, and actions later in the rule
2675 can refer to the value using @code{$@var{n}}. Since there is no symbol
2676 to name the action, there is no way to declare a data type for the value
2677 in advance, so you must use the @samp{$<@dots{}>} construct to specify a
2678 data type each time you refer to this value.
2679
2680 There is no way to set the value of the entire rule with a mid-rule
2681 action, because assignments to @code{$$} do not have that effect. The
2682 only way to set the value for the entire rule is with an ordinary action
2683 at the end of the rule.
2684
2685 Here is an example from a hypothetical compiler, handling a @code{let}
2686 statement that looks like @samp{let (@var{variable}) @var{statement}} and
2687 serves to create a variable named @var{variable} temporarily for the
2688 duration of @var{statement}. To parse this construct, we must put
2689 @var{variable} into the symbol table while @var{statement} is parsed, then
2690 remove it afterward. Here is how it is done:
2691
2692 @example
2693 @group
2694 stmt: 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
2703 As soon as @samp{let (@var{variable})} has been recognized, the first
2704 action is run. It saves a copy of the current semantic context (the
2705 list 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
2708 first action is finished, the embedded statement @code{stmt} can be
2709 parsed. Note that the mid-rule action is component number 5, so the
2710 @samp{stmt} is component number 6.
2711
2712 After the embedded statement is parsed, its semantic value becomes the
2713 value of the entire @code{let}-statement. Then the semantic value from the
2714 earlier action is used to restore the prior list of variables. This
2715 removes the temporary @code{let}-variable from the list so that it won't
2716 appear to exist while the rest of the program is parsed.
2717
2718 Taking action before a rule is completely recognized often leads to
2719 conflicts since the parser must commit to a parse in order to execute the
2720 action. For example, the following two rules, without mid-rule actions,
2721 can coexist in a working parser because the parser can shift the open-brace
2722 token and look at what follows before deciding whether there is a
2723 declaration or not:
2724
2725 @example
2726 @group
2727 compound: '@{' declarations statements '@}'
2728 | '@{' statements '@}'
2729 ;
2730 @end group
2731 @end example
2732
2733 @noindent
2734 But when we add a mid-rule action as follows, the rules become nonfunctional:
2735
2736 @example
2737 @group
2738 compound: @{ prepare_for_local_variables (); @}
2739 '@{' declarations statements '@}'
2740 @end group
2741 @group
2742 | '@{' statements '@}'
2743 ;
2744 @end group
2745 @end example
2746
2747 @noindent
2748 Now the parser is forced to decide whether to run the mid-rule action
2749 when it has read no farther than the open-brace. In other words, it
2750 must commit to using one rule or the other, without sufficient
2751 information to do it correctly. (The open-brace token is what is called
2752 the @dfn{look-ahead} token at this time, since the parser is still
2753 deciding what to do about it. @xref{Look-Ahead, ,Look-Ahead Tokens}.)
2754
2755 You might think that you could correct the problem by putting identical
2756 actions into the two rules, like this:
2757
2758 @example
2759 @group
2760 compound: @{ prepare_for_local_variables (); @}
2761 '@{' declarations statements '@}'
2762 | @{ prepare_for_local_variables (); @}
2763 '@{' statements '@}'
2764 ;
2765 @end group
2766 @end example
2767
2768 @noindent
2769 But this does not help, because Bison does not realize that the two actions
2770 are identical. (Bison never tries to understand the C code in an action.)
2771
2772 If the grammar is such that a declaration can be distinguished from a
2773 statement by the first token (which is true in C), then one solution which
2774 does work is to put the action after the open-brace, like this:
2775
2776 @example
2777 @group
2778 compound: '@{' @{ prepare_for_local_variables (); @}
2779 declarations statements '@}'
2780 | '@{' statements '@}'
2781 ;
2782 @end group
2783 @end example
2784
2785 @noindent
2786 Now the first token of the following declaration or statement,
2787 which would in any case tell Bison which rule to use, can still do so.
2788
2789 Another solution is to bury the action inside a nonterminal symbol which
2790 serves as a subroutine:
2791
2792 @example
2793 @group
2794 subroutine: /* empty */
2795 @{ prepare_for_local_variables (); @}
2796 ;
2797
2798 @end group
2799
2800 @group
2801 compound: subroutine
2802 '@{' declarations statements '@}'
2803 | subroutine
2804 '@{' statements '@}'
2805 ;
2806 @end group
2807 @end example
2808
2809 @noindent
2810 Now Bison can execute the action in the rule for @code{subroutine} without
2811 deciding which rule for @code{compound} it will eventually use. Note that
2812 the action is now at the end of its rule. Any mid-rule action can be
2813 converted to an end-of-rule action in this way, and this is what Bison
2814 actually 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
2821 The @dfn{Bison declarations} section of a Bison grammar defines the symbols
2822 used in formulating the grammar and the data types of semantic values.
2823 @xref{Symbols}.
2824
2825 All token type names (but not single-character literal tokens such as
2826 @code{'+'} and @code{'*'}) must be declared. Nonterminal symbols must be
2827 declared if you need to specify which data type to use for the semantic
2828 value (@pxref{Multiple Types, ,More Than One Value Type}).
2829
2830 The first rule in the file also specifies the start symbol, by default.
2831 If you want some other symbol to be the start symbol, you must declare
2832 it 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
2852 The basic way to declare a token type name (terminal symbol) is as follows:
2853
2854 @example
2855 %token @var{name}
2856 @end example
2857
2858 Bison will convert this into a @code{#define} directive in
2859 the parser, so that the function @code{yylex} (if it is in this file)
2860 can use the name @var{name} to stand for this token type's code.
2861
2862 Alternatively, you can use @code{%left}, @code{%right}, or @code{%nonassoc}
2863 instead of @code{%token}, if you wish to specify precedence.
2864 @xref{Precedence Decl, ,Operator Precedence}.
2865
2866 You can explicitly specify the numeric code for a token type by appending
2867 an integer value in the field immediately following the token name:
2868
2869 @example
2870 %token NUM 300
2871 @end example
2872
2873 @noindent
2874 It is generally best, however, to let Bison choose the numeric codes for
2875 all token types. Bison will automatically select codes that don't conflict
2876 with each other or with ASCII characters.
2877
2878 In 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
2880 alternative delimited by angle-brackets (@pxref{Multiple Types, ,More Than One Value Type}).
2881
2882 For 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
2894 You can associate a literal string token with a token type name by
2895 writing the literal string at the end of a @code{%token}
2896 declaration which declares the name. For example:
2897
2898 @example
2899 %token arrow "=>"
2900 @end example
2901
2902 @noindent
2903 For example, a grammar for the C language might specify these names with
2904 equivalent literal string tokens:
2905
2906 @example
2907 %token <operator> OR "||"
2908 %token <operator> LE 134 "<="
2909 %left OR "<="
2910 @end example
2911
2912 @noindent
2913 Once you equate the literal string and the token name, you can use them
2914 interchangeably in further declarations or the grammar rules. The
2915 @code{yylex} function can use the token name or the literal string to
2916 obtain 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
2924 Use the @code{%left}, @code{%right} or @code{%nonassoc} declaration to
2925 declare a token and specify its precedence and associativity, all at
2926 once. These are called @dfn{precedence declarations}.
2927 @xref{Precedence, ,Operator Precedence}, for general information on operator precedence.
2928
2929 The 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
2937 or
2938
2939 @example
2940 %left <@var{type}> @var{symbols}@dots{}
2941 @end example
2942
2943 And indeed any of these declarations serves the purposes of @code{%token}.
2944 But in addition, they specify the associativity and relative precedence for
2945 all the @var{symbols}:
2946
2947 @itemize @bullet
2948 @item
2949 The associativity of an operator @var{op} determines how repeated uses
2950 of 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
2952 grouping @var{y} with @var{z} first. @code{%left} specifies
2953 left-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
2956 means that @samp{@var{x} @var{op} @var{y} @var{op} @var{z}} is
2957 considered a syntax error.
2958
2959 @item
2960 The precedence of an operator determines how it nests with other operators.
2961 All the tokens declared in a single precedence declaration have equal
2962 precedence and nest together according to their associativity.
2963 When two tokens declared in different precedence declarations associate,
2964 the 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
2973 The @code{%union} declaration specifies the entire collection of possible
2974 data types for semantic values. The keyword @code{%union} is followed by a
2975 pair of braces containing the same thing that goes inside a @code{union} in
2976 C.
2977
2978 For example:
2979
2980 @example
2981 @group
2982 %union @{
2983 double val;
2984 symrec *tptr;
2985 @}
2986 @end group
2987 @end example
2988
2989 @noindent
2990 This 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
2992 in the @code{%token} and @code{%type} declarations to pick one of the types
2993 for a terminal or nonterminal symbol (@pxref{Type Decl, ,Nonterminal Symbols}).
2994
2995 Note that, unlike making a @code{union} declaration in C, you do not write
2996 a 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
3005 When you use @code{%union} to specify multiple value types, you must
3006 declare the value type of each nonterminal symbol for which values are
3007 used. 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
3014 Here @var{nonterminal} is the name of a nonterminal symbol, and @var{type}
3015 is 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
3017 the same @code{%type} declaration, if they have the same value type. Use
3018 spaces to separate the symbol names.
3019
3020 You can also declare the value type of a terminal symbol. To do this,
3021 use the same @code{<@var{type}>} construction in a declaration for the
3022 terminal 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
3033 Bison 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
3035 conflicts which are resolved in a predictable way and would be difficult to
3036 eliminate. It is desirable to suppress the warning about these conflicts
3037 unless the number of conflicts changes. You can do this with the
3038 @code{%expect} declaration.
3039
3040 The declaration looks like this:
3041
3042 @example
3043 %expect @var{n}
3044 @end example
3045
3046 Here @var{n} is a decimal integer. The declaration says there should be no
3047 warning if there are @var{n} shift/reduce conflicts and no reduce/reduce
3048 conflicts. The usual warning is given if there are either more or fewer
3049 conflicts, or if there are any reduce/reduce conflicts.
3050
3051 In general, using @code{%expect} involves these steps:
3052
3053 @itemize @bullet
3054 @item
3055 Compile your grammar without @code{%expect}. Use the @samp{-v} option
3056 to get a verbose list of where the conflicts occur. Bison will also
3057 print the number of conflicts.
3058
3059 @item
3060 Check each of the conflicts to make sure that Bison's default
3061 resolution is what you really want. If not, rewrite the grammar and
3062 go back to the beginning.
3063
3064 @item
3065 Add an @code{%expect} declaration, copying the number @var{n} from the
3066 number which Bison printed.
3067 @end itemize
3068
3069 Now Bison will stop annoying you about the conflicts you have checked, but
3070 it will warn you again if changes in the grammar result in additional
3071 conflicts.
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
3080 Bison assumes by default that the start symbol for the grammar is the first
3081 nonterminal specified in the grammar specification section. The programmer
3082 may 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
3094 A @dfn{reentrant} program is one which does not alter in the course of
3095 execution; in other words, it consists entirely of @dfn{pure} (read-only)
3096 code. Reentrancy is important whenever asynchronous execution is possible;
3097 for example, a nonreentrant program may not be safe to call from a signal
3098 handler. In systems with multiple threads of control, a nonreentrant
3099 program must be called only within interlocks.
3100
3101 The Bison parser is not normally a reentrant program, because it uses
3102 statically allocated variables for communication with @code{yylex}. These
3103 variables include @code{yylval} and @code{yylloc}.
3104
3105 The Bison declaration @code{%pure_parser} says that you want the parser
3106 to be reentrant. It looks like this:
3107
3108 @example
3109 %pure_parser
3110 @end example
3111
3112 The effect is that the two communication variables become local
3113 variables in @code{yyparse}, and a different calling convention is used
3114 for the lexical analyzer function @code{yylex}. @xref{Pure Calling,
3115 ,Calling Conventions for Pure Parsers}, for the details of this. The
3116 variable @code{yynerrs} also becomes local in @code{yyparse}
3117 (@pxref{Error Reporting, ,The Error Reporting Function @code{yyerror}}).
3118 The 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
3126 Here is a summary of all Bison declarations:
3127
3128 @table @code
3129 @item %union
3130 Declare the collection of data types that semantic values may have
3131 (@pxref{Union Decl, ,The Collection of Value Types}).
3132
3133 @item %token
3134 Declare a terminal symbol (token type name) with no precedence
3135 or associativity specified (@pxref{Token Decl, ,Token Type Names}).
3136
3137 @item %right
3138 Declare a terminal symbol (token type name) that is right-associative
3139 (@pxref{Precedence Decl, ,Operator Precedence}).
3140
3141 @item %left
3142 Declare a terminal symbol (token type name) that is left-associative
3143 (@pxref{Precedence Decl, ,Operator Precedence}).
3144
3145 @item %nonassoc
3146 Declare 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
3151 Declare the type of semantic values for a nonterminal symbol
3152 (@pxref{Type Decl, ,Nonterminal Symbols}).
3153
3154 @item %start
3155 Specify the grammar's start symbol (@pxref{Start Decl, ,The Start-Symbol}).
3156
3157 @item %expect
3158 Declare the expected number of shift-reduce conflicts
3159 (@pxref{Expect Decl, ,Suppressing Conflict Warnings}).
3160
3161 @item %pure_parser
3162 Request a pure (reentrant) parser program (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}).
3163
3164 @item %no_lines
3165 Don't generate any @code{#line} preprocessor commands in the parser
3166 file. Ordinarily Bison writes these commands in the parser file so that
3167 the C compiler and debuggers will associate errors and object code with
3168 your source file (the grammar file). This directive causes them to
3169 associate errors with the parser file, treating it an independent source
3170 file in its own right.
3171
3172 @item %raw
3173 The output file @file{@var{name}.h} normally defines the tokens with
3174 Yacc-compatible token numbers. If this option is specified, the
3175 internal Bison numbers are used instead. (Yacc-compatible numbers start
3176 at 257 except for single character tokens; Bison assigns token numbers
3177 sequentially for all tokens starting at 3.)
3178
3179 @item %token_table
3180 Generate an array of token names in the parser file. The name of the
3181 array is @code{yytname}; @code{yytname[@var{i}]} is the name of the
3182 token whose internal Bison token code number is @var{i}. The first three
3183 elements of @code{yytname} are always @code{"$"}, @code{"error"}, and
3184 @code{"$illegal"}; after these come the symbols defined in the grammar
3185 file.
3186
3187 For single-character literal tokens and literal string tokens, the name
3188 in the table includes the single-quote or double-quote characters: for
3189 example, @code{"'+'"} is a single-character literal and @code{"\"<=\""}
3190 is a literal string token. All the characters of the literal string
3191 token appear verbatim in the string found in the table; even
3192 double-quote characters are not escaped. For example, if the token
3193 consists of three characters @samp{*"*}, its string in @code{yytname}
3194 contains @samp{"*"*"}. (In C, that would be written as
3195 @code{"\"*\"*\""}).
3196
3197 When you specify @code{%token_table}, Bison also generates macro
3198 definitions for macros @code{YYNTOKENS}, @code{YYNNTS}, and
3199 @code{YYNRULES}, and @code{YYNSTATES}:
3200
3201 @table @code
3202 @item YYNTOKENS
3203 The highest token number, plus one.
3204 @item YYNNTS
3205 The number of non-terminal symbols.
3206 @item YYNRULES
3207 The number of grammar rules,
3208 @item YYNSTATES
3209 The 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
3216 Most programs that use Bison parse only one language and therefore contain
3217 only one Bison parser. But what if you want to parse more than one
3218 language with the same program? Then you need to avoid a name conflict
3219 between different definitions of @code{yyparse}, @code{yylval}, and so on.
3220
3221 The 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
3223 variables 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
3225 not conflict.
3226
3227 The 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
3233 renamed.} These others are not global; there is no conflict if the same
3234 name is used in different parsers. For example, @code{YYSTYPE} is not
3235 renamed, but defining this in different ways in different parsers causes
3236 no trouble (@pxref{Value Type, ,Data Types of Semantic Values}).
3237
3238 The @samp{-p} option works by adding macro definitions to the beginning
3239 of the parser source file, defining @code{yyparse} as
3240 @code{@var{prefix}parse}, and so on. This effectively substitutes one
3241 name 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
3248 The Bison parser is actually a C function named @code{yyparse}. Here we
3249 describe the interface conventions of @code{yyparse} and the other
3250 functions that it needs to use.
3251
3252 Keep 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
3254 identifier (aside from those in this manual) in an action or in additional
3255 C 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
3269 You call the function @code{yyparse} to cause parsing to occur. This
3270 function reads tokens, executes actions, and ultimately returns when it
3271 encounters end-of-input or an unrecoverable syntax error. You can also
3272 write an action which directs @code{yyparse} to return immediately without
3273 reading further.
3274
3275 The value returned by @code{yyparse} is 0 if parsing was successful (return
3276 is due to end-of-input).
3277
3278 The value is 1 if parsing failed (return is due to a syntax error).
3279
3280 In an action, you can cause immediate return from @code{yyparse} by using
3281 these macros:
3282
3283 @table @code
3284 @item YYACCEPT
3285 @findex YYACCEPT
3286 Return immediately with value 0 (to report success).
3287
3288 @item YYABORT
3289 @findex YYABORT
3290 Return 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
3298 The @dfn{lexical analyzer} function, @code{yylex}, recognizes tokens from
3299 the input stream and returns them to the parser. Bison does not create
3300 this function automatically; you must write it so that @code{yyparse} can
3301 call it. The function is sometimes referred to as a lexical scanner.
3302
3303 In simple programs, @code{yylex} is often defined at the end of the Bison
3304 grammar file. If @code{yylex} is defined in a separate source file, you
3305 need to arrange for the token-type macro definitions to be available there.
3306 To do this, use the @samp{-d} option when you run Bison, so that it will
3307 write these macro definitions into a separate header file
3308 @file{@var{name}.tab.h} which you can include in the other source files
3309 that 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
3325 The value that @code{yylex} returns must be the numeric code for the type
3326 of token it has just found, or 0 for end-of-input.
3327
3328 When a token is referred to in the grammar rules by a name, that name
3329 in the parser file becomes a C macro whose definition is the proper
3330 numeric code for that token type. So @code{yylex} can use the name
3331 to indicate that type. @xref{Symbols}.
3332
3333 When a token is referred to in the grammar rules by a character literal,
3334 the numeric code for that character is also the code for the token type.
3335 So @code{yylex} can simply return that character code. The null character
3336 must not be used this way, because its code is zero and that is what
3337 signifies end-of-input.
3338
3339 Here is an example showing these things:
3340
3341 @example
3342 yylex ()
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
3357 This interface has been designed so that the output from the @code{lex}
3358 utility can be used without change as the definition of @code{yylex}.
3359
3360 If 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
3365 If the grammar defines symbolic token names as aliases for the
3366 literal string tokens, @code{yylex} can use these symbolic names like
3367 all others. In this case, the use of the literal string tokens in
3368 the grammar file has no effect on @code{yylex}.
3369
3370 @item
3371 @code{yylex} can find the multi-character token in the @code{yytname}
3372 table. The index of the token in the table is the token type's code.
3373 The name of a multi-character token is recorded in @code{yytname} with a
3374 double-quote, the token's characters, and another double-quote. The
3375 token's characters are not escaped in any way; they appear verbatim in
3376 the contents of the string in the table.
3377
3378 Here's code for looking up a token in @code{yytname}, assuming that the
3379 characters of the token are stored in @code{token_buffer}.
3380
3381 @smallexample
3382 for (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
3393 The @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
3401 In an ordinary (nonreentrant) parser, the semantic value of the token must
3402 be stored into the global variable @code{yylval}. When you are using
3403 just one data type for semantic values, @code{yylval} has that type.
3404 Thus, 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
3416 When you are using multiple data types, @code{yylval}'s type is a union
3417 made from the @code{%union} declaration (@pxref{Union Decl, ,The Collection of Value Types}). So when
3418 you store a token's value, you must use the proper member of the union.
3419 If 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
3432 then 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
3447 If you are using the @samp{@@@var{n}}-feature (@pxref{Action Features, ,Special Features for Use in Actions}) in
3448 actions to keep track of the textual locations of tokens and groupings,
3449 then you must provide this information in @code{yylex}. The function
3450 @code{yyparse} expects to find the textual location of a token just parsed
3451 in the global variable @code{yylloc}. So @code{yylex} must store the
3452 proper data in that variable. The value of @code{yylloc} is a structure
3453 and you need only initialize the members that are going to be used by the
3454 actions. The four members are called @code{first_line},
3455 @code{first_column}, @code{last_line} and @code{last_column}. Note that
3456 the use of this feature makes the parser noticeably slower.
3457
3458 @tindex YYLTYPE
3459 The 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
3464 When you use the Bison declaration @code{%pure_parser} to request a
3465 pure, reentrant parser, the global communication variables @code{yylval}
3466 and @code{yylloc} cannot be used. (@xref{Pure Decl, ,A Pure (Reentrant)
3467 Parser}.) In such parsers the two global variables are replaced by
3468 pointers passed as arguments to @code{yylex}. You must declare them as
3469 shown here, and pass the information back by storing it through those
3470 pointers.
3471
3472 @example
3473 yylex (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
3484 If the grammar file does not use the @samp{@@} constructs to refer to
3485 textual positions, then the type @code{YYLTYPE} will not be defined. In
3486 this case, omit the second argument; @code{yylex} will be called with
3487 only one argument.
3488
3489 @vindex YYPARSE_PARAM
3490 If you use a reentrant parser, you can optionally pass additional
3491 parameter information to it in a reentrant way. To do so, define the
3492 macro @code{YYPARSE_PARAM} as a variable name. This modifies the
3493 @code{yyparse} function to accept one argument, of type @code{void *},
3494 with that name.
3495
3496 When you call @code{yyparse}, pass the address of an object, casting the
3497 address to @code{void *}. The grammar actions can refer to the contents
3498 of the object by casting the pointer value back to its proper type and
3499 then dereferencing it. Here's an example. Write this in the parser:
3500
3501 @example
3502 %@{
3503 struct parser_control
3504 @{
3505 int nastiness;
3506 int randomness;
3507 @};
3508
3509 #define YYPARSE_PARAM parm
3510 %@}
3511 @end example
3512
3513 @noindent
3514 Then call the parser like this:
3515
3516 @example
3517 struct 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
3534 In 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
3541 If you wish to pass the additional parameter data to @code{yylex},
3542 define the macro @code{YYLEX_PARAM} just like @code{YYPARSE_PARAM}, as
3543 shown here:
3544
3545 @example
3546 %@{
3547 struct 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
3558 You should then define @code{yylex} to accept one additional
3559 argument---the value of @code{parm}. (This makes either two or three
3560 arguments in total, depending on whether an argument of type
3561 @code{YYLTYPE} is passed.) You can declare the argument as a pointer to
3562 the proper object type, or you can declare it as @code{void *} and
3563 access the contents as shown above.
3564
3565 You can use @samp{%pure_parser} to request a reentrant parser without
3566 also using @code{YYPARSE_PARAM}. Then you should call @code{yyparse}
3567 with 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
3576 The Bison parser detects a @dfn{parse error} or @dfn{syntax error}
3577 whenever it reads a token which cannot satisfy any syntax rule. A
3578 action in the grammar can also explicitly proclaim an error, using the
3579 macro @code{YYERROR} (@pxref{Action Features, ,Special Features for Use in Actions}).
3580
3581 The Bison parser expects to report the error by calling an error
3582 reporting function named @code{yyerror}, which you must supply. It is
3583 called by @code{yyparse} whenever a syntax error is found, and it
3584 receives one argument. For a parse error, the string is normally
3585 @w{@code{"parse error"}}.
3586
3587 @findex YYERROR_VERBOSE
3588 If you define the macro @code{YYERROR_VERBOSE} in the Bison declarations
3589 section (@pxref{Bison Declarations, ,The Bison Declarations Section}), then Bison provides a more verbose
3590 and specific error message string instead of just plain @w{@code{"parse
3591 error"}}. It doesn't matter what definition you use for
3592 @code{YYERROR_VERBOSE}, just whether you define it.
3593
3594 The parser can detect one other kind of error: stack overflow. This
3595 happens when the input contains constructions that are very deeply
3596 nested. It isn't likely you will encounter this, since the Bison
3597 parser extends its stack automatically up to a very large limit. But
3598 if overflow happens, @code{yyparse} calls @code{yyerror} in the usual
3599 fashion, except that the argument string is @w{@code{"parser stack
3600 overflow"}}.
3601
3602 The following definition suffices in simple programs:
3603
3604 @example
3605 @group
3606 yyerror (s)
3607 char *s;
3608 @{
3609 @end group
3610 @group
3611 fprintf (stderr, "%s\n", s);
3612 @}
3613 @end group
3614 @end example
3615
3616 After @code{yyerror} returns to @code{yyparse}, the latter will attempt
3617 error recovery if you have written suitable error recovery grammar rules
3618 (@pxref{Error Recovery}). If recovery is impossible, @code{yyparse} will
3619 immediately return 1.
3620
3621 @vindex yynerrs
3622 The variable @code{yynerrs} contains the number of syntax errors
3623 encountered so far. Normally this variable is global; but if you
3624 request a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}) then it is a local variable
3625 which 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
3632 Here is a table of Bison constructs, variables and macros that
3633 are useful in actions.
3634
3635 @table @samp
3636 @item $$
3637 Acts like a variable that contains the semantic value for the
3638 grouping made by the current rule. @xref{Actions}.
3639
3640 @item $@var{n}
3641 Acts 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}>$
3645 Like @code{$$} but specifies alternative @var{typealt} in the union
3646 specified by the @code{%union} declaration. @xref{Action Types, ,Data Types of Values in Actions}.
3647
3648 @item $<@var{typealt}>@var{n}
3649 Like @code{$@var{n}} but specifies alternative @var{typealt} in the
3650 union specified by the @code{%union} declaration.
3651 @xref{Action Types, ,Data Types of Values in Actions}.@refill
3652
3653 @item YYABORT;
3654 Return immediately from @code{yyparse}, indicating failure.
3655 @xref{Parser Function, ,The Parser Function @code{yyparse}}.
3656
3657 @item YYACCEPT;
3658 Return 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
3663 Unshift a token. This macro is allowed only for rules that reduce
3664 a single value, and only when there is no look-ahead token.
3665 It installs a look-ahead token with token type @var{token} and
3666 semantic value @var{value}; then it discards the value that was
3667 going to be reduced by this rule.
3668
3669 If the macro is used when it is not valid, such as when there is
3670 a look-ahead token already, then it reports a syntax error with
3671 a message @samp{cannot back up} and performs ordinary error
3672 recovery.
3673
3674 In either case, the rest of the action is not executed.
3675
3676 @item YYEMPTY
3677 @vindex YYEMPTY
3678 Value stored in @code{yychar} when there is no look-ahead token.
3679
3680 @item YYERROR;
3681 @findex YYERROR
3682 Cause an immediate syntax error. This statement initiates error
3683 recovery just as if the parser itself had detected an error; however, it
3684 does not call @code{yyerror}, and does not print any message. If you
3685 want to print an error message, call @code{yyerror} explicitly before
3686 the @samp{YYERROR;} statement. @xref{Error Recovery}.
3687
3688 @item YYRECOVERING
3689 This macro stands for an expression that has the value 1 when the parser
3690 is recovering from a syntax error, and 0 the rest of the time.
3691 @xref{Error Recovery}.
3692
3693 @item yychar
3694 Variable containing the current look-ahead token. (In a pure parser,
3695 this is actually a local variable within @code{yyparse}.) When there is
3696 no look-ahead token, the value @code{YYEMPTY} is stored in the variable.
3697 @xref{Look-Ahead, ,Look-Ahead Tokens}.
3698
3699 @item yyclearin;
3700 Discard the current look-ahead token. This is useful primarily in
3701 error rules. @xref{Error Recovery}.
3702
3703 @item yyerrok;
3704 Resume generating error messages immediately for subsequent syntax
3705 errors. This is useful primarily in error rules.
3706 @xref{Error Recovery}.
3707
3708 @item @@@var{n}
3709 @findex @@@var{n}
3710 Acts like a structure variable containing information on the line
3711 numbers and column numbers of the @var{n}th component of the current
3712 rule. The structure has four members, like this:
3713
3714 @example
3715 struct @{
3716 int first_line, last_line;
3717 int first_column, last_column;
3718 @};
3719 @end example
3720
3721 Thus, to get the starting line number of the third component, use
3722 @samp{@@3.first_line}.
3723
3724 In order for the members of this structure to contain valid information,
3725 you must make @code{yylex} supply this information about each token.
3726 If you need only certain members, then @code{yylex} need only fill in
3727 those members.
3728
3729 The 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
3741 As Bison reads tokens, it pushes them onto a stack along with their
3742 semantic values. The stack is called the @dfn{parser stack}. Pushing a
3743 token is traditionally called @dfn{shifting}.
3744
3745 For 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
3747 that was shifted.
3748
3749 But the stack does not always have an element for each token read. When
3750 the last @var{n} tokens and groupings shifted match the components of a
3751 grammar 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
3753 single grouping whose symbol is the result (left hand side) of that rule.
3754 Running the rule's action is part of the process of reduction, because this
3755 is what computes the semantic value of the resulting grouping.
3756
3757 For example, if the infix calculator's parser stack contains this:
3758
3759 @example
3760 1 + 5 * 3
3761 @end example
3762
3763 @noindent
3764 and the next input token is a newline character, then the last three
3765 elements can be reduced to 15 via the rule:
3766
3767 @example
3768 expr: expr '*' expr;
3769 @end example
3770
3771 @noindent
3772 Then the stack contains just these three elements:
3773
3774 @example
3775 1 + 15
3776 @end example
3777
3778 @noindent
3779 At this point, another reduction can be made, resulting in the single value
3780 16. Then the newline token can be shifted.
3781
3782 The parser tries, by shifts and reductions, to reduce the entire input down
3783 to a single grouping whose symbol is the grammar's start-symbol
3784 (@pxref{Language and Grammar, ,Languages and Context-Free Grammars}).
3785
3786 This 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
3803 The Bison parser does @emph{not} always reduce immediately as soon as the
3804 last @var{n} tokens and groupings match a rule. This is because such a
3805 simple strategy is inadequate to handle most languages. Instead, when a
3806 reduction is possible, the parser sometimes ``looks ahead'' at the next
3807 token in order to decide what to do.
3808
3809 When 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
3811 perform one or more reductions of tokens and groupings on the stack, while
3812 the look-ahead token remains off to the side. When no more reductions
3813 should take place, the look-ahead token is shifted onto the stack. This
3814 does not mean that all possible reductions have been done; depending on the
3815 token type of the look-ahead token, some rules may choose to delay their
3816 application.
3817
3818 Here is a simple case where look-ahead is needed. These three rules define
3819 expressions which contain binary addition operators and postfix unary
3820 factorial operators (@samp{!}), and allow parentheses for grouping.
3821
3822 @example
3823 @group
3824 expr: term '+' expr
3825 | term
3826 ;
3827 @end group
3828
3829 @group
3830 term: '(' expr ')'
3831 | term '!'
3832 | NUMBER
3833 ;
3834 @end group
3835 @end example
3836
3837 Suppose that the tokens @w{@samp{1 + 2}} have been read and shifted; what
3838 should be done? If the following token is @samp{)}, then the first three
3839 tokens must be reduced to form an @code{expr}. This is the only valid
3840 course, because shifting the @samp{)} would produce a sequence of symbols
3841 @w{@code{term ')'}}, and no rule allows this.
3842
3843 If the following token is @samp{!}, then it must be shifted immediately so
3844 that @w{@samp{2 !}} can be reduced to make a @code{term}. If instead the
3845 parser 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
3847 doing so would produce on the stack the sequence of symbols @code{expr
3848 '!'}. No rule allows that sequence.
3849
3850 @vindex yychar
3851 The 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
3861 Suppose we are parsing a language which has if-then and if-then-else
3862 statements, with a pair of rules like this:
3863
3864 @example
3865 @group
3866 if_stmt:
3867 IF expr THEN stmt
3868 | IF expr THEN stmt ELSE stmt
3869 ;
3870 @end group
3871 @end example
3872
3873 @noindent
3874 Here we assume that @code{IF}, @code{THEN} and @code{ELSE} are
3875 terminal symbols for specific keyword tokens.
3876
3877 When the @code{ELSE} token is read and becomes the look-ahead token, the
3878 contents of the stack (assuming the input is valid) are just right for
3879 reduction 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
3881 rule.
3882
3883 This situation, where either a shift or a reduction would be valid, is
3884 called a @dfn{shift/reduce conflict}. Bison is designed to resolve
3885 these conflicts by choosing to shift, unless otherwise directed by
3886 operator precedence declarations. To see the reason for this, let's
3887 contrast it with the other alternative.
3888
3889 Since the parser prefers to shift the @code{ELSE}, the result is to attach
3890 the else-clause to the innermost if-statement, making these two inputs
3891 equivalent:
3892
3893 @example
3894 if x then if y then win (); else lose;
3895
3896 if x then do; if y then win (); else lose; end;
3897 @end example
3898
3899 But if the parser chose to reduce when possible rather than shift, the
3900 result would be to attach the else-clause to the outermost if-statement,
3901 making these two inputs equivalent:
3902
3903 @example
3904 if x then if y then win (); else lose;
3905
3906 if x then do; if y then win (); end; else lose;
3907 @end example
3908
3909 The conflict exists because the grammar as written is ambiguous: either
3910 parsing of the simple nested if-statement is legitimate. The established
3911 convention is that these ambiguities are resolved by attaching the
3912 else-clause to the innermost if-statement; this is what Bison accomplishes
3913 by choosing to shift rather than reduce. (It would ideally be cleaner to
3914 write an unambiguous grammar, but that is very hard to do in this case.)
3915 This particular ambiguity was first encountered in the specifications of
3916 Algol 60 and is called the ``dangling @code{else}'' ambiguity.
3917
3918 To avoid warnings from Bison about predictable, legitimate shift/reduce
3919 conflicts, use the @code{%expect @var{n}} declaration. There will be no
3920 warning as long as the number of shift/reduce conflicts is exactly @var{n}.
3921 @xref{Expect Decl, ,Suppressing Conflict Warnings}.
3922
3923 The definition of @code{if_stmt} above is solely to blame for the
3924 conflict, but the conflict does not actually appear without additional
3925 rules. Here is a complete Bison input file that actually manifests the
3926 conflict:
3927
3928 @example
3929 @group
3930 %token IF THEN ELSE variable
3931 %%
3932 @end group
3933 @group
3934 stmt: expr
3935 | if_stmt
3936 ;
3937 @end group
3938
3939 @group
3940 if_stmt:
3941 IF expr THEN stmt
3942 | IF expr THEN stmt ELSE stmt
3943 ;
3944 @end group
3945
3946 expr: 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
3955 Another situation where shift/reduce conflicts appear is in arithmetic
3956 expressions. Here shifting is not always the preferred resolution; the
3957 Bison declarations for operator precedence allow you to specify when to
3958 shift 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
3970 Consider the following ambiguous grammar fragment (ambiguous because the
3971 input @w{@samp{1 - 2 * 3}} can be parsed in two different ways):
3972
3973 @example
3974 @group
3975 expr: expr '-' expr
3976 | expr '*' expr
3977 | expr '<' expr
3978 | '(' expr ')'
3979 @dots{}
3980 ;
3981 @end group
3982 @end example
3983
3984 @noindent
3985 Suppose the parser has seen the tokens @samp{1}, @samp{-} and @samp{2};
3986 should it reduce them via the rule for the addition operator? It depends
3987 on the next token. Of course, if the next token is @samp{)}, we must
3988 reduce; shifting is invalid because no single rule can reduce the token
3989 sequence @w{@samp{- 2 )}} or anything starting with that. But if the next
3990 token is @samp{*} or @samp{<}, we have a choice: either shifting or
3991 reduction would allow the parse to complete, but with different
3992 results.
3993
3994 To decide which one Bison should do, we must consider the
3995 results. If the next operator token @var{op} is shifted, then it
3996 must be reduced first in order to permit another opportunity to
3997 reduce the sum. The result is (in effect) @w{@samp{1 - (2
3998 @var{op} 3)}}. On the other hand, if the subtraction is reduced
3999 before shifting @var{op}, the result is @w{@samp{(1 - 2) @var{op}
4000 3}}. Clearly, then, the choice of shift or reduce should depend
4001 on the relative precedence of the operators @samp{-} and
4002 @var{op}: @samp{*} should be shifted first, but not @samp{<}.
4003
4004 @cindex associativity
4005 What 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
4007 most operators we prefer the former, which is called @dfn{left
4008 association}. The latter alternative, @dfn{right association}, is
4009 desirable for assignment operators. The choice of left or right
4010 association is a matter of whether the parser chooses to shift or
4011 reduce when the stack contains @w{@samp{1 - 2}} and the look-ahead
4012 token 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
4020 Bison allows you to specify these choices with the operator precedence
4021 declarations @code{%left} and @code{%right}. Each such declaration
4022 contains a list of tokens, which are operators whose precedence and
4023 associativity is being declared. The @code{%left} declaration makes all
4024 those operators left-associative and the @code{%right} declaration makes
4025 them right-associative. A third alternative is @code{%nonassoc}, which
4026 declares that it is a syntax error to find the same operator twice ``in a
4027 row''.
4028
4029 The relative precedence of different operators is controlled by the
4030 order in which they are declared. The first @code{%left} or
4031 @code{%right} declaration in the file declares the operators whose
4032 precedence is lowest, the next such declaration declares the operators
4033 whose precedence is a little higher, and so on.
4034
4035 @node Precedence Examples, How Precedence, Using Precedence, Precedence
4036 @subsection Precedence Examples
4037
4038 In our example, we would want the following declarations:
4039
4040 @example
4041 %left '<'
4042 %left '-'
4043 %left '*'
4044 @end example
4045
4046 In a more complete example, which supports other operators as well, we
4047 would declare them in groups of equal precedence. For example, @code{'+'} is
4048 declared 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''
4058 and so on. We assume that these tokens are more than one character long
4059 and therefore are represented by names, not character literals.)
4060
4061 @node How Precedence, , Precedence Examples, Precedence
4062 @subsection How Precedence Works
4063
4064 The first effect of the precedence declarations is to assign precedence
4065 levels to the terminal symbols declared. The second effect is to assign
4066 precedence levels to certain rules: each rule gets its precedence from the
4067 last terminal symbol mentioned in the components. (You can also specify
4068 explicitly the precedence of a rule. @xref{Contextual Precedence, ,Context-Dependent Precedence}.)
4069
4070 Finally, the resolution of conflicts works by comparing the
4071 precedence of the rule being considered with that of the
4072 look-ahead token. If the token's precedence is higher, the
4073 choice is to shift. If the rule's precedence is higher, the
4074 choice is to reduce. If they have equal precedence, the choice
4075 is made based on the associativity of that precedence level. The
4076 verbose output file made by @samp{-v} (@pxref{Invocation, ,Invoking Bison}) says
4077 how each conflict was resolved.
4078
4079 Not all rules and not all tokens have precedence. If either the rule or
4080 the 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
4090 Often the precedence of an operator depends on the context. This sounds
4091 outlandish at first, but it is really very common. For example, a minus
4092 sign typically has a very high precedence as a unary operator, and a
4093 somewhat lower precedence (lower than multiplication) as a binary operator.
4094
4095 The Bison precedence declarations, @code{%left}, @code{%right} and
4096 @code{%nonassoc}, can only be used once for a given token; so a token has
4097 only one precedence declared in this way. For context-dependent
4098 precedence, you need to use an additional mechanism: the @code{%prec}
4099 modifier for rules.@refill
4100
4101 The @code{%prec} modifier declares the precedence of a particular rule by
4102 specifying a terminal symbol whose precedence should be used for that rule.
4103 It's not necessary for that symbol to appear otherwise in the rule. The
4104 modifier's syntax is:
4105
4106 @example
4107 %prec @var{terminal-symbol}
4108 @end example
4109
4110 @noindent
4111 and it is written after the components of the rule. Its effect is to
4112 assign the rule the precedence of @var{terminal-symbol}, overriding
4113 the precedence that would be deduced for it in the ordinary way. The
4114 altered rule precedence then affects how conflicts involving that rule
4115 are resolved (@pxref{Precedence, ,Operator Precedence}).
4116
4117 Here is how @code{%prec} solves the problem of unary minus. First, declare
4118 a precedence for a fictitious terminal symbol named @code{UMINUS}. There
4119 are no tokens of this type, but the symbol serves to stand for its
4120 precedence:
4121
4122 @example
4123 @dots{}
4124 %left '+' '-'
4125 %left '*'
4126 %left UMINUS
4127 @end example
4128
4129 Now the precedence of @code{UMINUS} can be used in specific rules:
4130
4131 @example
4132 @group
4133 exp: @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
4146 The function @code{yyparse} is implemented using a finite-state machine.
4147 The values pushed on the parser stack are not simply token type codes; they
4148 represent the entire sequence of terminal and nonterminal symbols at or
4149 near the top of the stack. The current state collects all the information
4150 about previous input which is relevant to deciding what to do next.
4151
4152 Each time a look-ahead token is read, the current parser state together
4153 with the type of look-ahead token are looked up in a table. This table
4154 entry can say, ``Shift the look-ahead token.'' In this case, it also
4155 specifies the new parser state, which is pushed onto the top of the
4156 parser stack. Or it can say, ``Reduce using rule number @var{n}.''
4157 This means that a certain number of tokens or groupings are taken off
4158 the top of the stack, and replaced by one grouping. In other words,
4159 that number of states are popped from the stack, and one new state is
4160 pushed.
4161
4162 There is one other alternative: the table can say that the look-ahead token
4163 is 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
4171 A reduce/reduce conflict occurs if there are two or more rules that apply
4172 to the same sequence of input. This usually indicates a serious error
4173 in the grammar.
4174
4175 For example, here is an erroneous attempt to define a sequence
4176 of zero or more @code{word} groupings.
4177
4178 @example
4179 sequence: /* empty */
4180 @{ printf ("empty sequence\n"); @}
4181 | maybeword
4182 | sequence word
4183 @{ printf ("added word %s\n", $2); @}
4184 ;
4185
4186 maybeword: /* empty */
4187 @{ printf ("empty maybeword\n"); @}
4188 | word
4189 @{ printf ("single word %s\n", $1); @}
4190 ;
4191 @end example
4192
4193 @noindent
4194 The 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.
4197 Alternatively, nothing-at-all could be reduced into a @code{sequence}
4198 via the first rule, and this could be combined with the @code{word}
4199 using the third rule for @code{sequence}.
4200
4201 There 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,
4203 or indirectly via @code{maybeword} and then the second rule.
4204
4205 You might think that this is a distinction without a difference, because it
4206 does not change whether any particular input is valid or not. But it does
4207 affect which actions are run. One parsing order runs the second rule's
4208 action; the other runs the first rule's action and the third rule's action.
4209 In this example, the output of the program changes.
4210
4211 Bison resolves a reduce/reduce conflict by choosing to use the rule that
4212 appears first in the grammar, but it is very risky to rely on this. Every
4213 reduce/reduce conflict must be studied and usually eliminated. Here is the
4214 proper way to define @code{sequence}:
4215
4216 @example
4217 sequence: /* empty */
4218 @{ printf ("empty sequence\n"); @}
4219 | sequence word
4220 @{ printf ("added word %s\n", $2); @}
4221 ;
4222 @end example
4223
4224 Here is another common error that yields a reduce/reduce conflict:
4225
4226 @example
4227 sequence: /* empty */
4228 | sequence words
4229 | sequence redirects
4230 ;
4231
4232 words: /* empty */
4233 | words word
4234 ;
4235
4236 redirects:/* empty */
4237 | redirects redirect
4238 ;
4239 @end example
4240
4241 @noindent
4242 The 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
4245 three together make a subtle ambiguity: even an empty input can be parsed
4246 in infinitely many ways!
4247
4248 Consider: 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}
4251 followed by three @code{redirects} and another @code{words}. And so on.
4252
4253 Here are two ways to correct these rules. First, to make it a single level
4254 of sequence:
4255
4256 @example
4257 sequence: /* empty */
4258 | sequence word
4259 | sequence redirect
4260 ;
4261 @end example
4262
4263 Second, to prevent either a @code{words} or a @code{redirects}
4264 from being empty:
4265
4266 @example
4267 sequence: /* empty */
4268 | sequence words
4269 | sequence redirects
4270 ;
4271
4272 words: word
4273 | words word
4274 ;
4275
4276 redirects: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
4284 Sometimes reduce/reduce conflicts can occur that don't look warranted.
4285 Here is an example:
4286
4287 @example
4288 @group
4289 %token ID
4290
4291 %%
4292 def: param_spec return_spec ','
4293 ;
4294 param_spec:
4295 type
4296 | name_list ':' type
4297 ;
4298 @end group
4299 @group
4300 return_spec:
4301 type
4302 | name ':' type
4303 ;
4304 @end group
4305 @group
4306 type: ID
4307 ;
4308 @end group
4309 @group
4310 name: ID
4311 ;
4312 name_list:
4313 name
4314 | name ',' name_list
4315 ;
4316 @end group
4317 @end example
4318
4319 It would seem that this grammar can be parsed with only a single token
4320 of look-ahead: when a @code{param_spec} is being read, an @code{ID} is
4321 a @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)
4326 However, Bison, like most parser generators, cannot actually handle all
4327 LR(1) grammars. In this grammar, two contexts, that after an @code{ID}
4328 at the beginning of a @code{param_spec} and likewise at the beginning of
4329 a @code{return_spec}, are similar enough that Bison assumes they are the
4330 same. They appear similar because the same set of rules would be
4331 active---the rule for reducing to a @code{name} and that for reducing to
4332 a @code{type}. Bison is unable to determine at that stage of processing
4333 that the rules would require different look-ahead tokens in the two
4334 contexts, so it makes a single parser state for them both. Combining
4335 the two contexts causes a conflict later. In parser terminology, this
4336 occurrence means that the grammar is not LALR(1).
4337
4338 In general, it is better to fix deficiencies than to document them. But
4339 this particular deficiency is intrinsically hard to fix; parser
4340 generators that can handle LR(1) grammars are hard to write and tend to
4341 produce parsers that are very large. In practice, Bison is more useful
4342 as it is now.
4343
4344 When the problem arises, you can often fix it by identifying the two
4345 parser states that are being confused, and adding something to make them
4346 look 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{}
4355 return_spec:
4356 type
4357 | name ':' type
4358 /* This rule is never used. */
4359 | ID BOGUS
4360 ;
4361 @end group
4362 @end example
4363
4364 This corrects the problem because it introduces the possibility of an
4365 additional 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
4367 in a @code{param_spec}, so the two contexts receive distinct parser states.
4368 As long as the token @code{BOGUS} is never generated by @code{yylex},
4369 the added rule cannot alter the way actual input is parsed.
4370
4371 In this particular example, there is another way to solve the problem:
4372 rewrite the rule for @code{return_spec} to use @code{ID} directly
4373 instead of via @code{name}. This also causes the two confusing
4374 contexts to have different sets of active rules, because the one for
4375 @code{return_spec} activates the altered rule for @code{return_spec}
4376 rather than the one for @code{name}.
4377
4378 @example
4379 param_spec:
4380 type
4381 | name_list ':' type
4382 ;
4383 return_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
4395 The Bison parser stack can overflow if too many tokens are shifted and
4396 not reduced. When this happens, the parser function @code{yyparse}
4397 returns a nonzero value, pausing only to call @code{yyerror} to report
4398 the overflow.
4399
4400 @vindex YYMAXDEPTH
4401 By defining the macro @code{YYMAXDEPTH}, you can control how deep the
4402 parser stack can become before a stack overflow occurs. Define the
4403 macro with a value that is an integer. This value is the maximum number
4404 of tokens that can be shifted (and not reduced) before overflow.
4405 It must be a constant expression whose value is known at compile time.
4406
4407 The stack space allowed is not necessarily allocated. If you specify a
4408 large value for @code{YYMAXDEPTH}, the parser actually allocates a small
4409 stack at first, and then makes it bigger by stages as needed. This
4410 increasing allocation happens automatically and silently. Therefore,
4411 you do not need to make @code{YYMAXDEPTH} painfully small merely to save
4412 space for ordinary inputs that do not need much stack.
4413
4414 @cindex default stack limit
4415 The default value of @code{YYMAXDEPTH}, if you do not define it, is
4416 10000.
4417
4418 @vindex YYINITDEPTH
4419 You can control how much stack is allocated initially by defining the
4420 macro @code{YYINITDEPTH}. This value too must be a compile-time
4421 constant 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
4428 It is not usually acceptable to have a program terminate on a parse
4429 error. For example, a compiler should recover sufficiently to parse the
4430 rest of the input file and check it for errors; a calculator should accept
4431 another expression.
4432
4433 In a simple interactive command parser where each input is one line, it may
4434 be sufficient to allow @code{yyparse} to return 1 on error and have the
4435 caller 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
4437 forgets all the syntactic context leading up to the error. A syntax error
4438 deep within a function in the compiler input should not cause the compiler
4439 to treat the following line like the beginning of a source file.
4440
4441 @findex error
4442 You can define how to recover from a syntax error by writing rules to
4443 recognize the special token @code{error}. This is a terminal symbol that
4444 is always defined (you need not declare it) and reserved for error
4445 handling. The Bison parser generates an @code{error} token whenever a
4446 syntax error happens; if you have provided a rule to recognize this token
4447 in the current context, the parse can continue.
4448
4449 For example:
4450
4451 @example
4452 stmnts: /* empty string */
4453 | stmnts '\n'
4454 | stmnts exp '\n'
4455 | stmnts error '\n'
4456 @end example
4457
4458 The fourth rule in this example says that an error followed by a newline
4459 makes a valid addition to any @code{stmnts}.
4460
4461 What happens if a syntax error occurs in the middle of an @code{exp}? The
4462 error recovery rule, interpreted strictly, applies to the precise sequence
4463 of a @code{stmnts}, an @code{error} and a newline. If an error occurs in
4464 the middle of an @code{exp}, there will probably be some additional tokens
4465 and subexpressions on the stack after the last @code{stmnts}, and there
4466 will be tokens to read before the next newline. So the rule is not
4467 applicable in the ordinary way.
4468
4469 But Bison can force the situation to fit the rule, by discarding part of
4470 the semantic context and part of the input. First it discards states and
4471 objects from the stack until it gets back to a state in which the
4472 @code{error} token is acceptable. (This means that the subexpressions
4473 already parsed are discarded, back to the last complete @code{stmnts}.) At
4474 this point the @code{error} token can be shifted. Then, if the old
4475 look-ahead token is not acceptable to be shifted next, the parser reads
4476 tokens and discards them until it finds a token which is acceptable. In
4477 this example, Bison reads and discards input until the next newline
4478 so that the fourth rule can apply.
4479
4480 The choice of error rules in the grammar is a choice of strategies for
4481 error recovery. A simple and useful strategy is simply to skip the rest of
4482 the current input line or current statement if an error is detected:
4483
4484 @example
4485 stmnt: error ';' /* on error, skip until ';' is read */
4486 @end example
4487
4488 It is also useful to recover to the matching close-delimiter of an
4489 opening-delimiter that has already been parsed. Otherwise the
4490 close-delimiter will probably appear to be unmatched, and generate another,
4491 spurious error message:
4492
4493 @example
4494 primary: '(' expr ')'
4495 | '(' error ')'
4496 @dots{}
4497 ;
4498 @end example
4499
4500 Error recovery strategies are necessarily guesses. When they guess wrong,
4501 one syntax error often leads to another. In the above example, the error
4502 recovery 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
4504 middle of a valid @code{stmnt}. After the error recovery rule recovers
4505 from the first error, another syntax error will be found straightaway,
4506 since the text following the spurious semicolon is also an invalid
4507 @code{stmnt}.
4508
4509 To prevent an outpouring of error messages, the parser will output no error
4510 message for another syntax error that happens shortly after the first; only
4511 after three consecutive input tokens have been successfully shifted will
4512 error messages resume.
4513
4514 Note that rules which accept the @code{error} token may have actions, just
4515 as any other rules can.
4516
4517 @findex yyerrok
4518 You 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
4520 error messages will be suppressed. This macro requires no arguments;
4521 @samp{yyerrok;} is a valid C statement.
4522
4523 @findex yyclearin
4524 The previous look-ahead token is reanalyzed immediately after an error. If
4525 this is unacceptable, then the macro @code{yyclearin} may be used to clear
4526 this token. Write the statement @samp{yyclearin;} in the error rule's
4527 action.
4528
4529 For example, suppose that on a parse error, an error handling routine is
4530 called that advances the input stream to some point where parsing should
4531 once again commence. The next symbol returned by the lexical scanner is
4532 probably correct. The previous look-ahead token ought to be discarded
4533 with @samp{yyclearin;}.
4534
4535 @vindex YYRECOVERING
4536 The macro @code{YYRECOVERING} stands for an expression that has the
4537 value 1 when the parser is recovering from a syntax error, and 0 the
4538 rest of the time. A value of 1 indicates that error messages are
4539 currently suppressed for new syntax errors.
4540
4541 @node Context Dependency, Debugging, Error Recovery, Top
4542 @chapter Handling Context Dependencies
4543
4544 The Bison paradigm is to parse tokens first, then group them into larger
4545 syntactic units. In many languages, the meaning of a token is affected by
4546 its context. Although this violates the Bison paradigm, certain techniques
4547 (known as @dfn{kludges}) may enable you to write Bison parsers for such
4548 languages.
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
4558 neither clean nor robust.)
4559
4560 @node Semantic Tokens, Lexical Tie-ins, , Context Dependency
4561 @section Semantic Info in Token Types
4562
4563 The C language has a context dependency: the way an identifier is used
4564 depends on what its current meaning is. For example, consider this:
4565
4566 @example
4567 foo (x);
4568 @end example
4569
4570 This looks like a function call statement, but if @code{foo} is a typedef
4571 name, then this is actually a declaration of @code{x}. How can a Bison
4572 parser for C decide how to parse this input?
4573
4574 The method used in GNU C is to have two different token types,
4575 @code{IDENTIFIER} and @code{TYPENAME}. When @code{yylex} finds an
4576 identifier, it looks up the current declaration of the identifier in order
4577 to decide which token type to return: @code{TYPENAME} if the identifier is
4578 declared as a typedef, @code{IDENTIFIER} otherwise.
4579
4580 The grammar rules can then express the context dependency by the choice of
4581 token type to recognize. @code{IDENTIFIER} is accepted as an expression,
4582 but @code{TYPENAME} is not. @code{TYPENAME} can start a declaration, but
4583 @code{IDENTIFIER} cannot. In contexts where the meaning of the identifier
4584 is @emph{not} significant, such as in declarations that can shadow a
4585 typedef name, either @code{TYPENAME} or @code{IDENTIFIER} is
4586 accepted---there is one rule for each of the two token types.
4587
4588 This technique is simple to use if the decision of which kinds of
4589 identifiers to allow is made at a place close to where the identifier is
4590 parsed. But in C this is not always so: C allows a declaration to
4591 redeclare a typedef name provided an explicit type has been specified
4592 earlier:
4593
4594 @example
4595 typedef int foo, bar, lose;
4596 static foo (bar); /* @r{redeclare @code{bar} as static variable} */
4597 static int foo (lose); /* @r{redeclare @code{foo} as function} */
4598 @end example
4599
4600 Unfortunately, the name being declared is separated from the declaration
4601 construct itself by a complicated syntactic structure---the ``declarator''.
4602
4603 As a result, the part of Bison parser for C needs to be duplicated, with
4604 all the nonterminal names changed: once for parsing a declaration in which
4605 a typedef name can be redefined, and once for parsing a declaration in
4606 which that can't be done. Here is a part of the duplication, with actions
4607 omitted for brevity:
4608
4609 @example
4610 initdcl:
4611 declarator maybeasm '='
4612 init
4613 | declarator maybeasm
4614 ;
4615
4616 notype_initdcl:
4617 notype_declarator maybeasm '='
4618 init
4619 | notype_declarator maybeasm
4620 ;
4621 @end example
4622
4623 @noindent
4624 Here @code{initdcl} can redeclare a typedef name, but @code{notype_initdcl}
4625 cannot. The distinction between @code{declarator} and
4626 @code{notype_declarator} is the same sort of thing.
4627
4628 There is some similarity between this technique and a lexical tie-in
4629 (described next), in that information which alters the lexical analysis is
4630 changed during parsing by other parts of the program. The difference is
4631 here the information is global, and is used for other purposes in the
4632 program. A true lexical tie-in has a special-purpose flag controlled by
4633 the 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
4639 One way to handle context-dependency is the @dfn{lexical tie-in}: a flag
4640 which is set by Bison actions, whose purpose is to alter the way tokens are
4641 parsed.
4642
4643 For example, suppose we have a language vaguely like C, but with a special
4644 construct @samp{hex (@var{hex-expr})}. After the keyword @code{hex} comes
4645 an expression in parentheses in which all integers are hexadecimal. In
4646 particular, the token @samp{a1b} must be treated as an integer rather than
4647 as an identifier if it appears in that context. Here is how you can do it:
4648
4649 @example
4650 @group
4651 %@{
4652 int hexflag;
4653 %@}
4654 %%
4655 @dots{}
4656 @end group
4657 @group
4658 expr: 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
4672 constant:
4673 INTEGER
4674 | STRING
4675 ;
4676 @end group
4677 @end example
4678
4679 @noindent
4680 Here we assume that @code{yylex} looks at the value of @code{hexflag}; when
4681 it is nonzero, all integers are parsed in hexadecimal, and tokens starting
4682 with letters are parsed as integers if possible.
4683
4684 The declaration of @code{hexflag} shown in the C declarations section of
4685 the 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}
4687 to obey the flag.
4688
4689 @node Tie-in Recovery, , Lexical Tie-ins, Context Dependency
4690 @section Lexical Tie-ins and Error Recovery
4691
4692 Lexical tie-ins make strict demands on any error recovery rules you have.
4693 @xref{Error Recovery}.
4694
4695 The reason for this is that the purpose of an error recovery rule is to
4696 abort the parsing of one construct and resume in some larger construct.
4697 For example, in C-like languages, a typical error recovery rule is to skip
4698 tokens until the next semicolon, and then start a new statement, like this:
4699
4700 @example
4701 stmt: expr ';'
4702 | IF '(' expr ')' stmt @{ @dots{} @}
4703 @dots{}
4704 error ';'
4705 @{ hexflag = 0; @}
4706 ;
4707 @end example
4708
4709 If there is a syntax error in the middle of a @samp{hex (@var{expr})}
4710 construct, this error rule will apply, and then the action for the
4711 completed @samp{hex (@var{expr})} will never run. So @code{hexflag} would
4712 remain set for the entire rest of the input, or until the next @code{hex}
4713 keyword, causing identifiers to be misinterpreted as integers.
4714
4715 To avoid this problem the error recovery rule itself clears @code{hexflag}.
4716
4717 There may also be an error recovery rule that works within expressions.
4718 For example, there could be a rule which applies within parentheses
4719 and skips to the close-parenthesis:
4720
4721 @example
4722 @group
4723 expr: @dots{}
4724 | '(' expr ')'
4725 @{ $$ = $2; @}
4726 | '(' error ')'
4727 @dots{}
4728 @end group
4729 @end example
4730
4731 If this rule acts within the @code{hex} construct, it is not going to abort
4732 that construct (since it applies to an inner level of parentheses within
4733 the construct). Therefore, it should not clear the flag: the rest of
4734 the @code{hex} construct should be parsed with the flag still in effect.
4735
4736 What 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
4738 way you can write the action to determine whether a @code{hex} construct is
4739 being aborted or not. So if you are using a lexical tie-in, you had better
4740 make sure your error recovery rules are not of this kind. Each rule must
4741 be such that you can be sure that it always will, or always won't, have to
4742 clear 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
4751 If a Bison grammar compiles properly but doesn't do what you want when it
4752 runs, the @code{yydebug} parser-trace feature can help you figure out why.
4753
4754 To 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
4757 YYDEBUG 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
4759 you run Bison (@pxref{Invocation, ,Invoking Bison}). We always define @code{YYDEBUG} so that
4760 debugging is always possible.
4761
4762 The 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
4765 Once you have compiled the program with trace facilities, the way to
4766 request a trace is to store a nonzero value in the variable @code{yydebug}.
4767 You can do this by making the C code do it (in @code{main}, perhaps), or
4768 you can alter the value with a C debugger.
4769
4770 Each step taken by the parser when @code{yydebug} is nonzero produces a
4771 line or two of trace information, written on @code{stderr}. The trace
4772 messages tell you these things:
4773
4774 @itemize @bullet
4775 @item
4776 Each time the parser calls @code{yylex}, what kind of token was read.
4777
4778 @item
4779 Each time a token is shifted, the depth and complete contents of the
4780 state stack (@pxref{Parser States}).
4781
4782 @item
4783 Each time a rule is reduced, which rule it is, and the complete contents
4784 of the state stack afterward.
4785 @end itemize
4786
4787 To make sense of this information, it helps to refer to the listing file
4788 produced by the Bison @samp{-v} option (@pxref{Invocation, ,Invoking Bison}). This file
4789 shows the meaning of each state in terms of positions in various rules, and
4790 also what each state will do with each possible input token. As you read
4791 the successive trace messages, you can see that the parser is functioning
4792 according to its specification in the listing file. Eventually you will
4793 arrive at the place where something undesirable happens, and you will see
4794 which parts of the grammar are to blame.
4795
4796 The parser file is a C program and you can use C debuggers on it, but it's
4797 not easy to interpret what it is doing. The parser function is a
4798 finite-state machine interpreter, and aside from the actions it executes
4799 the same code over and over. Only the values of variables show where in
4800 the grammar it is working.
4801
4802 @findex YYPRINT
4803 The debugging information normally gives the token type of each token
4804 read, but not its semantic value. You can optionally define a macro
4805 named @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
4807 standard I/O stream, the numeric code for the token type, and the token
4808 value (from @code{yylval}).
4809
4810 Here is an example of @code{YYPRINT} suitable for the multi-function
4811 calculator (@pxref{Mfcalc Decl, ,Declarations for @code{mfcalc}}):
4812
4813 @smallexample
4814 #define YYPRINT(file, type, value) yyprint (file, type, value)
4815
4816 static void
4817 yyprint (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
4835 The usual way to invoke Bison is as follows:
4836
4837 @example
4838 bison @var{infile}
4839 @end example
4840
4841 Here @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}
4843 with @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
4857 Bison supports both traditional single-letter options and mnemonic long
4858 option names. Long option names are indicated with @samp{--} instead of
4859 @samp{-}. Abbreviations for option names are allowed as long as they
4860 are unique. When a long option takes an argument, like
4861 @samp{--file-prefix}, connect the option name and the argument with
4862 @samp{=}.
4863
4864 Here is a list of options that can be used with Bison, alphabetized by
4865 short option. It is followed by a cross key alphabetized by long
4866 option.
4867
4868 @table @samp
4869 @item -b @var{file-prefix}
4870 @itemx --file-prefix=@var{prefix}
4871 Specify a prefix to use for all Bison output file names. The names are
4872 chosen as if the input file were named @file{@var{prefix}.c}.
4873
4874 @item -d
4875 @itemx --defines
4876 Write an extra output file containing macro definitions for the token
4877 type names defined in the grammar and the semantic value type
4878 @code{YYSTYPE}, as well as a few @code{extern} variable declarations.
4879
4880 If the parser output file is named @file{@var{name}.c} then this file
4881 is named @file{@var{name}.h}.@refill
4882
4883 This 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
4885 be 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
4890 Don't put any @code{#line} preprocessor commands in the parser file.
4891 Ordinarily Bison puts them in the parser file so that the C compiler
4892 and debuggers will associate errors with your source file, the
4893 grammar file. This option causes them to associate errors with the
4894 parser file, treating it as an independent source file in its own right.
4895
4896 @item -n
4897 @itemx --no-parser
4898 Do not include any C code in the parser file; generate tables only. The
4899 parser file contains just @code{#define} directives and static variable
4900 declarations.
4901
4902 This option also tells Bison to write the C code for the grammar actions
4903 into a file named @file{@var{filename}.act}, in the form of a
4904 brace-surrounded body fit for a @code{switch} statement.
4905
4906 @item -o @var{outfile}
4907 @itemx --output-file=@var{outfile}
4908 Specify the name @var{outfile} for the parser file.
4909
4910 The other output files' names are constructed from @var{outfile}
4911 as described under the @samp{-v} and @samp{-d} options.
4912
4913 @item -p @var{prefix}
4914 @itemx --name-prefix=@var{prefix}
4915 Rename 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
4917 is @code{yyparse}, @code{yylex}, @code{yyerror}, @code{yynerrs},
4918 @code{yylval}, @code{yychar} and @code{yydebug}.
4919
4920 For 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
4927 Pretend that @code{%raw} was specified. @xref{Decl Summary}.
4928
4929 @item -t
4930 @itemx --debug
4931 Output a definition of the macro @code{YYDEBUG} into the parser file,
4932 so that the debugging facilities are compiled. @xref{Debugging, ,Debugging Your Parser}.
4933
4934 @item -v
4935 @itemx --verbose
4936 Write an extra output file containing verbose descriptions of the
4937 parser states and what is done for each type of look-ahead token in
4938 that state.
4939
4940 This file also describes all the conflicts, both those resolved by
4941 operator precedence and the unresolved ones.
4942
4943 The file's name is made by removing @samp{.tab.c} or @samp{.c} from
4944 the parser output file name, and adding @samp{.output} instead.@refill
4945
4946 Therefore, if the input file is @file{foo.y}, then the parser file is
4947 called @file{foo.tab.c} by default. As a consequence, the verbose
4948 output file is called @file{foo.output}.@refill
4949
4950 @item -V
4951 @itemx --version
4952 Print the version number of Bison and exit.
4953
4954 @item -h
4955 @itemx --help
4956 Print 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
4962 Equivalent 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
4965 file name conventions. Thus, the following shell script can substitute
4966 for Yacc:@refill
4967
4968 @example
4969 bison -y $*
4970 @end example
4971 @end table
4972
4973 @node Option Cross Key, VMS Invocation, Bison Options, Invocation
4974 @section Option Cross Key
4975
4976 Here is a list of options, alphabetized by long option, to help you find
4977 the 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
5023 The command line syntax for Bison on VMS is a variant of the usual
5024 Bison command syntax---adapted to fit VMS conventions.
5025
5026 To find the VMS equivalent for any Bison option, start with the long
5027 option, and substitute a @samp{/} for the leading @samp{--}, and
5028 substitute a @samp{_} for each @samp{-} in the name of the long option.
5029 For example, the following invocation under VMS:
5030
5031 @example
5032 bison /debug/name_prefix=bar foo.y
5033 @end example
5034
5035 @noindent
5036 is equivalent to the following command under POSIX.
5037
5038 @example
5039 bison --debug --name-prefix=bar foo.y
5040 @end example
5041
5042 The VMS file system does not permit filenames such as
5043 @file{foo.tab.c}. In the above example, the output file
5044 would 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
5053 A token name reserved for error recovery. This token may be used in
5054 grammar rules so as to allow the Bison parser to recognize an error in
5055 the grammar without halting the process. In effect, a sentence
5056 containing an error may be recognized as valid. On a parse error, the
5057 token @code{error} becomes the current look-ahead token. Actions
5058 corresponding to @code{error} are then executed, and the look-ahead
5059 token is reset to the token that originally caused the violation.
5060 @xref{Error Recovery}.
5061
5062 @item YYABORT
5063 Macro to pretend that an unrecoverable syntax error has occurred, by
5064 making @code{yyparse} return 1 immediately. The error reporting
5065 function @code{yyerror} is not called. @xref{Parser Function, ,The Parser Function @code{yyparse}}.
5066
5067 @item YYACCEPT
5068 Macro to pretend that a complete utterance of the language has been
5069 read, by making @code{yyparse} return 0 immediately.
5070 @xref{Parser Function, ,The Parser Function @code{yyparse}}.
5071
5072 @item YYBACKUP
5073 Macro to discard a value from the parser stack and fake a look-ahead
5074 token. @xref{Action Features, ,Special Features for Use in Actions}.
5075
5076 @item YYERROR
5077 Macro 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
5083 Macro that you define with @code{#define} in the Bison declarations
5084 section to request verbose, specific error message strings when
5085 @code{yyerror} is called.
5086
5087 @item YYINITDEPTH
5088 Macro for specifying the initial size of the parser stack.
5089 @xref{Stack Overflow}.
5090
5091 @item YYLEX_PARAM
5092 Macro for specifying an extra argument (or list of extra arguments) for
5093 @code{yyparse} to pass to @code{yylex}. @xref{Pure Calling,, Calling
5094 Conventions for Pure Parsers}.
5095
5096 @item YYLTYPE
5097 Macro for the data type of @code{yylloc}; a structure with four
5098 members. @xref{Token Positions, ,Textual Positions of Tokens}.
5099
5100 @item yyltype
5101 Default value for YYLTYPE.
5102
5103 @item YYMAXDEPTH
5104 Macro for specifying the maximum size of the parser stack.
5105 @xref{Stack Overflow}.
5106
5107 @item YYPARSE_PARAM
5108 Macro for specifying the name of a parameter that @code{yyparse} should
5109 accept. @xref{Pure Calling,, Calling Conventions for Pure Parsers}.
5110
5111 @item YYRECOVERING
5112 Macro whose value indicates whether the parser is recovering from a
5113 syntax error. @xref{Action Features, ,Special Features for Use in Actions}.
5114
5115 @item YYSTYPE
5116 Macro for the data type of semantic values; @code{int} by default.
5117 @xref{Value Type, ,Data Types of Semantic Values}.
5118
5119 @item yychar
5120 External integer variable that contains the integer value of the
5121 current look-ahead token. (In a pure parser, it is a local variable
5122 within @code{yyparse}.) Error-recovery rule actions may examine this
5123 variable. @xref{Action Features, ,Special Features for Use in Actions}.
5124
5125 @item yyclearin
5126 Macro used in error-recovery rule actions. It clears the previous
5127 look-ahead token. @xref{Error Recovery}.
5128
5129 @item yydebug
5130 External integer variable set to zero by default. If @code{yydebug}
5131 is given a nonzero value, the parser will output information on input
5132 symbols and parser action. @xref{Debugging, ,Debugging Your Parser}.
5133
5134 @item yyerrok
5135 Macro to cause parser to recover immediately to its normal mode
5136 after a parse error. @xref{Error Recovery}.
5137
5138 @item yyerror
5139 User-supplied function to be called by @code{yyparse} on error. The
5140 function receives one argument, a pointer to a character string
5141 containing an error message. @xref{Error Reporting, ,The Error Reporting Function @code{yyerror}}.
5142
5143 @item yylex
5144 User-supplied lexical analyzer function, called with no arguments
5145 to get the next token. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
5146
5147 @item yylval
5148 External variable in which @code{yylex} should place the semantic
5149 value associated with a token. (In a pure parser, it is a local
5150 variable within @code{yyparse}, and its address is passed to
5151 @code{yylex}.) @xref{Token Values, ,Semantic Values of Tokens}.
5152
5153 @item yylloc
5154 External variable in which @code{yylex} should place the line and
5155 column numbers associated with a token. (In a pure parser, it is a
5156 local 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
5161 Global variable which Bison increments each time there is a parse
5162 error. (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
5166 The parser function produced by Bison; call this function to start
5167 parsing. @xref{Parser Function, ,The Parser Function @code{yyparse}}.
5168
5169 @item %left
5170 Bison declaration to assign left associativity to token(s).
5171 @xref{Precedence Decl, ,Operator Precedence}.
5172
5173 @item %no_lines
5174 Bison declaration to avoid generating @code{#line} directives in the
5175 parser file. @xref{Decl Summary}.
5176
5177 @item %nonassoc
5178 Bison declaration to assign nonassociativity to token(s).
5179 @xref{Precedence Decl, ,Operator Precedence}.
5180
5181 @item %prec
5182 Bison declaration to assign a precedence to a specific rule.
5183 @xref{Contextual Precedence, ,Context-Dependent Precedence}.
5184
5185 @item %pure_parser
5186 Bison declaration to request a pure (reentrant) parser.
5187 @xref{Pure Decl, ,A Pure (Reentrant) Parser}.
5188
5189 @item %raw
5190 Bison declaration to use Bison internal token code numbers in token
5191 tables instead of the usual Yacc-compatible token code numbers.
5192 @xref{Decl Summary}.
5193
5194 @item %right
5195 Bison declaration to assign right associativity to token(s).
5196 @xref{Precedence Decl, ,Operator Precedence}.
5197
5198 @item %start
5199 Bison declaration to specify the start symbol. @xref{Start Decl, ,The Start-Symbol}.
5200
5201 @item %token
5202 Bison declaration to declare token(s) without specifying precedence.
5203 @xref{Token Decl, ,Token Type Names}.
5204
5205 @item %token_table
5206 Bison declaration to include a token name table in the parser file.
5207 @xref{Decl Summary}.
5208
5209 @item %type
5210 Bison declaration to declare nonterminals. @xref{Type Decl, ,Nonterminal Symbols}.
5211
5212 @item %union
5213 Bison declaration to specify several possible data types for semantic
5214 values. @xref{Union Decl, ,The Collection of Value Types}.
5215 @end table
5216
5217 These are the punctuation and delimiters used in Bison input:
5218
5219 @table @samp
5220 @item %%
5221 Delimiter used to separate the grammar rule section from the
5222 Bison declarations section or the additional C code section.
5223 @xref{Grammar Layout, ,The Overall Layout of a Bison Grammar}.
5224
5225 @item %@{ %@}
5226 All code listed between @samp{%@{} and @samp{%@}} is copied directly
5227 to the output file uninterpreted. Such code forms the ``C
5228 declarations'' section of the input file. @xref{Grammar Outline, ,Outline of a Bison Grammar}.
5229
5230 @item /*@dots{}*/
5231 Comment delimiters, as in C.
5232
5233 @item :
5234 Separates a rule's result from its components. @xref{Rules, ,Syntax of Grammar Rules}.
5235
5236 @item ;
5237 Terminates a rule. @xref{Rules, ,Syntax of Grammar Rules}.
5238
5239 @item |
5240 Separates 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)
5250 Formal method of specifying context-free grammars. BNF was first used
5251 in the @cite{ALGOL-60} report, 1963. @xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5252
5253 @item Context-free grammars
5254 Grammars specified as rules that can be applied regardless of context.
5255 Thus, if there is a rule which says that an integer can be used as an
5256 expression, integers are allowed @emph{anywhere} an expression is
5257 permitted. @xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5258
5259 @item Dynamic allocation
5260 Allocation of memory that occurs during execution, rather than at
5261 compile time or on entry to a function.
5262
5263 @item Empty string
5264 Analogous to the empty set in set theory, the empty string is a
5265 character string of length zero.
5266
5267 @item Finite-state stack machine
5268 A ``machine'' that has discrete states in which it is said to exist at
5269 each instant in time. As input to the machine is processed, the
5270 machine moves from state to state as specified by the logic of the
5271 machine. In the case of the parser, the input is the language being
5272 parsed, and the states correspond to various stages in the grammar
5273 rules. @xref{Algorithm, ,The Bison Parser Algorithm }.
5274
5275 @item Grouping
5276 A language construct that is (in general) grammatically divisible;
5277 for example, `expression' or `declaration' in C.
5278 @xref{Language and Grammar, ,Languages and Context-Free Grammars}.
5279
5280 @item Infix operator
5281 An arithmetic operator that is placed between the operands on which it
5282 performs some operation.
5283
5284 @item Input stream
5285 A continuous flow of data between devices or programs.
5286
5287 @item Language construct
5288 One of the typical usage schemas of the language. For example, one of
5289 the 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
5293 Operators 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
5298 A rule whose result symbol is also its first component symbol;
5299 for example, @samp{expseq1 : expseq1 ',' exp;}. @xref{Recursion, ,Recursive Rules}.
5300
5301 @item Left-to-right parsing
5302 Parsing a sentence of a language by analyzing it token by token from
5303 left to right. @xref{Algorithm, ,The Bison Parser Algorithm }.
5304
5305 @item Lexical analyzer (scanner)
5306 A 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
5310 A flag, set by actions in the grammar rules, which alters the way
5311 tokens are parsed. @xref{Lexical Tie-ins}.
5312
5313 @item Literal string token
5314 A token which constists of two or more fixed characters.
5315 @xref{Symbols}.
5316
5317 @item Look-ahead token
5318 A token already read but not yet shifted. @xref{Look-Ahead, ,Look-Ahead Tokens}.
5319
5320 @item LALR(1)
5321 The class of context-free grammars that Bison (like most other parser
5322 generators) can handle; a subset of LR(1). @xref{Mystery Conflicts, ,
5323 Mysterious Reduce/Reduce Conflicts}.
5324
5325 @item LR(1)
5326 The class of context-free grammars in which at most one token of
5327 look-ahead is needed to disambiguate the parsing of any piece of input.
5328
5329 @item Nonterminal symbol
5330 A grammar symbol standing for a grammatical construct that can
5331 be expressed through rules in terms of smaller constructs; in other
5332 words, a construct that is not a token. @xref{Symbols}.
5333
5334 @item Parse error
5335 An error encountered during parsing of an input stream due to invalid
5336 syntax. @xref{Error Recovery}.
5337
5338 @item Parser
5339 A function that recognizes valid sentences of a language by analyzing
5340 the syntax structure of a set of tokens passed to it from a lexical
5341 analyzer.
5342
5343 @item Postfix operator
5344 An arithmetic operator that is placed after the operands upon which it
5345 performs some operation.
5346
5347 @item Reduction
5348 Replacing a string of nonterminals and/or terminals with a single
5349 nonterminal, according to a grammar rule. @xref{Algorithm, ,The Bison Parser Algorithm }.
5350
5351 @item Reentrant
5352 A reentrant subprogram is a subprogram which can be in invoked any
5353 number of times in parallel, without interference between the various
5354 invocations. @xref{Pure Decl, ,A Pure (Reentrant) Parser}.
5355
5356 @item Reverse polish notation
5357 A language in which all operators are postfix operators.
5358
5359 @item Right recursion
5360 A rule whose result symbol is also its last component symbol;
5361 for example, @samp{expseq1: exp ',' expseq1;}. @xref{Recursion, ,Recursive Rules}.
5362
5363 @item Semantics
5364 In computer languages, the semantics are specified by the actions
5365 taken for each instance of the language, i.e., the meaning of
5366 each statement. @xref{Semantics, ,Defining Language Semantics}.
5367
5368 @item Shift
5369 A parser is said to shift when it makes the choice of analyzing
5370 further input from the stream rather than reducing immediately some
5371 already-recognized rule. @xref{Algorithm, ,The Bison Parser Algorithm }.
5372
5373 @item Single-character literal
5374 A 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
5378 The nonterminal symbol that stands for a complete valid utterance in
5379 the language being parsed. The start symbol is usually listed as the
5380 first nonterminal symbol in a language specification.
5381 @xref{Start Decl, ,The Start-Symbol}.
5382
5383 @item Symbol table
5384 A data structure where symbol names and associated data are stored
5385 during parsing to allow for recognition and use of existing
5386 information in repeated uses of a symbol. @xref{Multi-function Calc}.
5387
5388 @item Token
5389 A basic, grammatically indivisible unit of a language. The symbol
5390 that describes a token in the grammar is a terminal symbol.
5391 The input of the Bison parser is a stream of tokens which comes from
5392 the lexical analyzer. @xref{Symbols}.
5393
5394 @item Terminal symbol
5395 A grammar symbol that has no rules in the grammar and therefore
5396 is grammatically indivisible. The piece of text it represents
5397 is 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
5419 Tutorial sections:
5420 * Concepts:: Basic concepts for understanding Bison.
5421 * Examples:: Three simple explained examples of using Bison.
5422
5423 Reference 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