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