aboutsummaryrefslogtreecommitdiff
path: root/tools/bison++/bison.info-1
diff options
context:
space:
mode:
authormarha <marha@users.sourceforge.net>2010-11-19 13:18:48 +0000
committermarha <marha@users.sourceforge.net>2010-11-19 13:18:48 +0000
commit12f606ce06ef926f366a03079c5e3107c23f18af (patch)
tree28d7be4328bca9c31c1ab0f7cb5924c196be23a0 /tools/bison++/bison.info-1
parent773752eab55047c33bad0d88006bb69f5c601502 (diff)
downloadvcxsrv-12f606ce06ef926f366a03079c5e3107c23f18af.tar.gz
vcxsrv-12f606ce06ef926f366a03079c5e3107c23f18af.tar.bz2
vcxsrv-12f606ce06ef926f366a03079c5e3107c23f18af.zip
Added tool bison++-1.21.11
Diffstat (limited to 'tools/bison++/bison.info-1')
-rw-r--r--tools/bison++/bison.info-11070
1 files changed, 1070 insertions, 0 deletions
diff --git a/tools/bison++/bison.info-1 b/tools/bison++/bison.info-1
new file mode 100644
index 000000000..3b458c6ed
--- /dev/null
+++ b/tools/bison++/bison.info-1
@@ -0,0 +1,1070 @@
+This is bison.info, produced by makeinfo version 4.1 from bison.texinfo.
+
+START-INFO-DIR-ENTRY
+* bison: (bison). GNU Project parser generator (yacc replacement).
+END-INFO-DIR-ENTRY
+
+ This file documents the Bison parser generator.
+
+ Copyright (C) 1988, 89, 90, 91, 92, 93, 95, 98, 1999 Free Software
+Foundation, Inc.
+
+ Permission is granted to make and distribute verbatim copies of this
+manual provided the copyright notice and this permission notice are
+preserved on all copies.
+
+ Permission is granted to copy and distribute modified versions of
+this manual under the conditions for verbatim copying, provided also
+that the sections entitled "GNU General Public License" and "Conditions
+for Using Bison" are included exactly as in the original, and provided
+that the entire resulting derived work is distributed under the terms
+of a permission notice identical to this one.
+
+ Permission is granted to copy and distribute translations of this
+manual into another language, under the above conditions for modified
+versions, except that the sections entitled "GNU General Public
+License", "Conditions for Using Bison" and this permission notice may be
+included in translations approved by the Free Software Foundation
+instead of in the original English.
+
+
+File: bison.info, Node: Top, Next: Introduction, Prev: (dir), Up: (dir)
+
+ This manual documents version 2.21.5 of Bison.
+
+* Menu:
+
+* Introduction::
+* Conditions::
+* Copying:: The GNU General Public License says
+ how you can copy and share Bison
+
+Tutorial sections:
+* Concepts:: Basic concepts for understanding Bison.
+* Examples:: Three simple explained examples of using Bison.
+
+Reference sections:
+* Grammar File:: Writing Bison declarations and rules.
+* Interface:: C-language interface to the parser function `yyparse'.
+* Algorithm:: How the Bison parser works at run-time.
+* Error Recovery:: Writing rules for error recovery.
+* Context Dependency:: What to do if your language syntax is too
+ messy for Bison to handle straightforwardly.
+* Debugging:: Debugging Bison parsers that parse wrong.
+* Invocation:: How to run Bison (to produce the parser source file).
+* Table of Symbols:: All the keywords of the Bison language are explained.
+* Glossary:: Basic concepts are explained.
+* Index:: Cross-references to the text.
+
+ --- The Detailed Node Listing ---
+
+The Concepts of Bison
+
+* Language and Grammar:: Languages and context-free grammars,
+ as mathematical ideas.
+* Grammar in Bison:: How we represent grammars for Bison's sake.
+* Semantic Values:: Each token or syntactic grouping can have
+ a semantic value (the value of an integer,
+ the name of an identifier, etc.).
+* Semantic Actions:: Each rule can have an action containing C code.
+* Bison Parser:: What are Bison's input and output,
+ how is the output used?
+* Stages:: Stages in writing and running Bison grammars.
+* Grammar Layout:: Overall structure of a Bison grammar file.
+
+Examples
+
+* RPN Calc:: Reverse polish notation calculator;
+ a first example with no operator precedence.
+* Infix Calc:: Infix (algebraic) notation calculator.
+ Operator precedence is introduced.
+* Simple Error Recovery:: Continuing after syntax errors.
+* Multi-function Calc:: Calculator with memory and trig functions.
+ It uses multiple data-types for semantic values.
+* Exercises:: Ideas for improving the multi-function calculator.
+
+Reverse Polish Notation Calculator
+
+* Decls: Rpcalc Decls. Bison and C declarations for rpcalc.
+* Rules: Rpcalc Rules. Grammar Rules for rpcalc, with explanation.
+* Lexer: Rpcalc Lexer. The lexical analyzer.
+* Main: Rpcalc Main. The controlling function.
+* Error: Rpcalc Error. The error reporting function.
+* Gen: Rpcalc Gen. Running Bison on the grammar file.
+* Comp: Rpcalc Compile. Run the C compiler on the output code.
+
+Grammar Rules for `rpcalc'
+
+* Rpcalc Input::
+* Rpcalc Line::
+* Rpcalc Expr::
+
+Multi-Function Calculator: `mfcalc'
+
+* Decl: Mfcalc Decl. Bison declarations for multi-function calculator.
+* Rules: Mfcalc Rules. Grammar rules for the calculator.
+* Symtab: Mfcalc Symtab. Symbol table management subroutines.
+
+Bison Grammar Files
+
+* Grammar Outline:: Overall layout of the grammar file.
+* Symbols:: Terminal and nonterminal symbols.
+* Rules:: How to write grammar rules.
+* Recursion:: Writing recursive rules.
+* Semantics:: Semantic values and actions.
+* Declarations:: All kinds of Bison declarations are described here.
+* Multiple Parsers:: Putting more than one Bison parser in one program.
+
+Outline of a Bison Grammar
+
+* C Declarations:: Syntax and usage of the C declarations section.
+* Bison Declarations:: Syntax and usage of the Bison declarations section.
+* Grammar Rules:: Syntax and usage of the grammar rules section.
+* C Code:: Syntax and usage of the additional C code section.
+
+Defining Language Semantics
+
+* Value Type:: Specifying one data type for all semantic values.
+* Multiple Types:: Specifying several alternative data types.
+* Actions:: An action is the semantic definition of a grammar rule.
+* Action Types:: Specifying data types for actions to operate on.
+* Mid-Rule Actions:: Most actions go at the end of a rule.
+ This says when, why and how to use the exceptional
+ action in the middle of a rule.
+
+Bison Declarations
+
+* Token Decl:: Declaring terminal symbols.
+* Precedence Decl:: Declaring terminals with precedence and associativity.
+* Union Decl:: Declaring the set of all semantic value types.
+* Type Decl:: Declaring the choice of type for a nonterminal symbol.
+* Expect Decl:: Suppressing warnings about shift/reduce conflicts.
+* Start Decl:: Specifying the start symbol.
+* Pure Decl:: Requesting a reentrant parser.
+* Decl Summary:: Table of all Bison declarations.
+
+Parser C-Language Interface
+
+* Parser Function:: How to call `yyparse' and what it returns.
+* Lexical:: You must supply a function `yylex'
+ which reads tokens.
+* Error Reporting:: You must supply a function `yyerror'.
+* Action Features:: Special features for use in actions.
+
+The Lexical Analyzer Function `yylex'
+
+* Calling Convention:: How `yyparse' calls `yylex'.
+* Token Values:: How `yylex' must return the semantic value
+ of the token it has read.
+* Token Positions:: How `yylex' must return the text position
+ (line number, etc.) of the token, if the
+ actions want that.
+* Pure Calling:: How the calling convention differs
+ in a pure parser (*note A Pure (Reentrant) Parser: Pure Decl.).
+
+The Bison Parser Algorithm
+
+* Look-Ahead:: Parser looks one token ahead when deciding what to do.
+* Shift/Reduce:: Conflicts: when either shifting or reduction is valid.
+* Precedence:: Operator precedence works by resolving conflicts.
+* Contextual Precedence:: When an operator's precedence depends on context.
+* Parser States:: The parser is a finite-state-machine with stack.
+* Reduce/Reduce:: When two rules are applicable in the same situation.
+* Mystery Conflicts:: Reduce/reduce conflicts that look unjustified.
+* Stack Overflow:: What happens when stack gets full. How to avoid it.
+
+Operator Precedence
+
+* Why Precedence:: An example showing why precedence is needed.
+* Using Precedence:: How to specify precedence in Bison grammars.
+* Precedence Examples:: How these features are used in the previous example.
+* How Precedence:: How they work.
+
+Handling Context Dependencies
+
+* Semantic Tokens:: Token parsing can depend on the semantic context.
+* Lexical Tie-ins:: Token parsing can depend on the syntactic context.
+* Tie-in Recovery:: Lexical tie-ins have implications for how
+ error recovery rules must be written.
+
+Invoking Bison
+
+* Bison Options:: All the options described in detail,
+ in alphabetical order by short options.
+* Option Cross Key:: Alphabetical list of long options.
+* VMS Invocation:: Bison command syntax on VMS.
+
+
+File: bison.info, Node: Introduction, Next: Conditions, Prev: Top, Up: Top
+
+Introduction
+************
+
+ "Bison" is a general-purpose parser generator that converts a
+grammar description for an LALR(1) context-free grammar into a C
+program to parse that grammar. Once you are proficient with Bison, you
+may use it to develop a wide range of language parsers, from those used
+in simple desk calculators to complex programming languages.
+
+ Bison is upward compatible with Yacc: all properly-written Yacc
+grammars ought to work with Bison with no change. Anyone familiar with
+Yacc should be able to use Bison with little trouble. You need to be
+fluent in C programming in order to use Bison or to understand this
+manual.
+
+ We begin with tutorial chapters that explain the basic concepts of
+using Bison and show three explained examples, each building on the
+last. If you don't know Bison or Yacc, start by reading these
+chapters. Reference chapters follow which describe specific aspects of
+Bison in detail.
+
+ Bison was written primarily by Robert Corbett; Richard Stallman made
+it Yacc-compatible. Wilfred Hansen of Carnegie Mellon University added
+multicharacter string literals and other features.
+
+ This edition corresponds to version 2.21.5 of Bison.
+
+
+File: bison.info, Node: Conditions, Next: Copying, Prev: Introduction, Up: Top
+
+Conditions for Using Bison
+**************************
+
+ As of Bison version 1.24, we have changed the distribution terms for
+`yyparse' to permit using Bison's output in non-free programs.
+Formerly, Bison parsers could be used only in programs that were free
+software.
+
+ The other GNU programming tools, such as the GNU C compiler, have
+never had such a requirement. They could always be used for non-free
+software. The reason Bison was different was not due to a special
+policy decision; it resulted from applying the usual General Public
+License to all of the Bison source code.
+
+ The output of the Bison utility--the Bison parser file--contains a
+verbatim copy of a sizable piece of Bison, which is the code for the
+`yyparse' function. (The actions from your grammar are inserted into
+this function at one point, but the rest of the function is not
+changed.) When we applied the GPL terms to the code for `yyparse', the
+effect was to restrict the use of Bison output to free software.
+
+ We didn't change the terms because of sympathy for people who want to
+make software proprietary. *Software should be free.* But we
+concluded that limiting Bison's use to free software was doing little to
+encourage people to make other software free. So we decided to make the
+practical conditions for using Bison match the practical conditions for
+using the other GNU tools.
+
+
+File: bison.info, Node: Copying, Next: Concepts, Prev: Conditions, Up: Top
+
+GNU GENERAL PUBLIC LICENSE
+**************************
+
+ Version 2, June 1991
+ Copyright (C) 1989, 1991 Free Software Foundation, Inc.
+ 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+
+ Everyone is permitted to copy and distribute verbatim copies
+ of this license document, but changing it is not allowed.
+
+Preamble
+========
+
+ The licenses for most software are designed to take away your
+freedom to share and change it. By contrast, the GNU General Public
+License is intended to guarantee your freedom to share and change free
+software--to make sure the software is free for all its users. This
+General Public License applies to most of the Free Software
+Foundation's software and to any other program whose authors commit to
+using it. (Some other Free Software Foundation software is covered by
+the GNU Library General Public License instead.) You can apply it to
+your programs, too.
+
+ When we speak of free software, we are referring to freedom, not
+price. Our General Public Licenses are designed to make sure that you
+have the freedom to distribute copies of free software (and charge for
+this service if you wish), that you receive source code or can get it
+if you want it, that you can change the software or use pieces of it in
+new free programs; and that you know you can do these things.
+
+ To protect your rights, we need to make restrictions that forbid
+anyone to deny you these rights or to ask you to surrender the rights.
+These restrictions translate to certain responsibilities for you if you
+distribute copies of the software, or if you modify it.
+
+ For example, if you distribute copies of such a program, whether
+gratis or for a fee, you must give the recipients all the rights that
+you have. You must make sure that they, too, receive or can get the
+source code. And you must show them these terms so they know their
+rights.
+
+ We protect your rights with two steps: (1) copyright the software,
+and (2) offer you this license which gives you legal permission to copy,
+distribute and/or modify the software.
+
+ Also, for each author's protection and ours, we want to make certain
+that everyone understands that there is no warranty for this free
+software. If the software is modified by someone else and passed on, we
+want its recipients to know that what they have is not the original, so
+that any problems introduced by others will not reflect on the original
+authors' reputations.
+
+ Finally, any free program is threatened constantly by software
+patents. We wish to avoid the danger that redistributors of a free
+program will individually obtain patent licenses, in effect making the
+program proprietary. To prevent this, we have made it clear that any
+patent must be licensed for everyone's free use or not licensed at all.
+
+ The precise terms and conditions for copying, distribution and
+modification follow.
+
+ TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
+ 0. This License applies to any program or other work which contains a
+ notice placed by the copyright holder saying it may be distributed
+ under the terms of this General Public License. The "Program",
+ below, refers to any such program or work, and a "work based on
+ the Program" means either the Program or any derivative work under
+ copyright law: that is to say, a work containing the Program or a
+ portion of it, either verbatim or with modifications and/or
+ translated into another language. (Hereinafter, translation is
+ included without limitation in the term "modification".) Each
+ licensee is addressed as "you".
+
+ Activities other than copying, distribution and modification are
+ not covered by this License; they are outside its scope. The act
+ of running the Program is not restricted, and the output from the
+ Program is covered only if its contents constitute a work based on
+ the Program (independent of having been made by running the
+ Program). Whether that is true depends on what the Program does.
+
+ 1. You may copy and distribute verbatim copies of the Program's
+ source code as you receive it, in any medium, provided that you
+ conspicuously and appropriately publish on each copy an appropriate
+ copyright notice and disclaimer of warranty; keep intact all the
+ notices that refer to this License and to the absence of any
+ warranty; and give any other recipients of the Program a copy of
+ this License along with the Program.
+
+ You may charge a fee for the physical act of transferring a copy,
+ and you may at your option offer warranty protection in exchange
+ for a fee.
+
+ 2. You may modify your copy or copies of the Program or any portion
+ of it, thus forming a work based on the Program, and copy and
+ distribute such modifications or work under the terms of Section 1
+ above, provided that you also meet all of these conditions:
+
+ a. You must cause the modified files to carry prominent notices
+ stating that you changed the files and the date of any change.
+
+ b. You must cause any work that you distribute or publish, that
+ in whole or in part contains or is derived from the Program
+ or any part thereof, to be licensed as a whole at no charge
+ to all third parties under the terms of this License.
+
+ c. If the modified program normally reads commands interactively
+ when run, you must cause it, when started running for such
+ interactive use in the most ordinary way, to print or display
+ an announcement including an appropriate copyright notice and
+ a notice that there is no warranty (or else, saying that you
+ provide a warranty) and that users may redistribute the
+ program under these conditions, and telling the user how to
+ view a copy of this License. (Exception: if the Program
+ itself is interactive but does not normally print such an
+ announcement, your work based on the Program is not required
+ to print an announcement.)
+
+ These requirements apply to the modified work as a whole. If
+ identifiable sections of that work are not derived from the
+ Program, and can be reasonably considered independent and separate
+ works in themselves, then this License, and its terms, do not
+ apply to those sections when you distribute them as separate
+ works. But when you distribute the same sections as part of a
+ whole which is a work based on the Program, the distribution of
+ the whole must be on the terms of this License, whose permissions
+ for other licensees extend to the entire whole, and thus to each
+ and every part regardless of who wrote it.
+
+ Thus, it is not the intent of this section to claim rights or
+ contest your rights to work written entirely by you; rather, the
+ intent is to exercise the right to control the distribution of
+ derivative or collective works based on the Program.
+
+ In addition, mere aggregation of another work not based on the
+ Program with the Program (or with a work based on the Program) on
+ a volume of a storage or distribution medium does not bring the
+ other work under the scope of this License.
+
+ 3. You may copy and distribute the Program (or a work based on it,
+ under Section 2) in object code or executable form under the terms
+ of Sections 1 and 2 above provided that you also do one of the
+ following:
+
+ a. Accompany it with the complete corresponding machine-readable
+ source code, which must be distributed under the terms of
+ Sections 1 and 2 above on a medium customarily used for
+ software interchange; or,
+
+ b. Accompany it with a written offer, valid for at least three
+ years, to give any third party, for a charge no more than your
+ cost of physically performing source distribution, a complete
+ machine-readable copy of the corresponding source code, to be
+ distributed under the terms of Sections 1 and 2 above on a
+ medium customarily used for software interchange; or,
+
+ c. Accompany it with the information you received as to the offer
+ to distribute corresponding source code. (This alternative is
+ allowed only for noncommercial distribution and only if you
+ received the program in object code or executable form with
+ such an offer, in accord with Subsection b above.)
+
+ The source code for a work means the preferred form of the work for
+ making modifications to it. For an executable work, complete
+ source code means all the source code for all modules it contains,
+ plus any associated interface definition files, plus the scripts
+ used to control compilation and installation of the executable.
+ However, as a special exception, the source code distributed need
+ not include anything that is normally distributed (in either
+ source or binary form) with the major components (compiler,
+ kernel, and so on) of the operating system on which the executable
+ runs, unless that component itself accompanies the executable.
+
+ If distribution of executable or object code is made by offering
+ access to copy from a designated place, then offering equivalent
+ access to copy the source code from the same place counts as
+ distribution of the source code, even though third parties are not
+ compelled to copy the source along with the object code.
+
+ 4. You may not copy, modify, sublicense, or distribute the Program
+ except as expressly provided under this License. Any attempt
+ otherwise to copy, modify, sublicense or distribute the Program is
+ void, and will automatically terminate your rights under this
+ License. However, parties who have received copies, or rights,
+ from you under this License will not have their licenses
+ terminated so long as such parties remain in full compliance.
+
+ 5. You are not required to accept this License, since you have not
+ signed it. However, nothing else grants you permission to modify
+ or distribute the Program or its derivative works. These actions
+ are prohibited by law if you do not accept this License.
+ Therefore, by modifying or distributing the Program (or any work
+ based on the Program), you indicate your acceptance of this
+ License to do so, and all its terms and conditions for copying,
+ distributing or modifying the Program or works based on it.
+
+ 6. Each time you redistribute the Program (or any work based on the
+ Program), the recipient automatically receives a license from the
+ original licensor to copy, distribute or modify the Program
+ subject to these terms and conditions. You may not impose any
+ further restrictions on the recipients' exercise of the rights
+ granted herein. You are not responsible for enforcing compliance
+ by third parties to this License.
+
+ 7. If, as a consequence of a court judgment or allegation of patent
+ infringement or for any other reason (not limited to patent
+ issues), conditions are imposed on you (whether by court order,
+ agreement or otherwise) that contradict the conditions of this
+ License, they do not excuse you from the conditions of this
+ License. If you cannot distribute so as to satisfy simultaneously
+ your obligations under this License and any other pertinent
+ obligations, then as a consequence you may not distribute the
+ Program at all. For example, if a patent license would not permit
+ royalty-free redistribution of the Program by all those who
+ receive copies directly or indirectly through you, then the only
+ way you could satisfy both it and this License would be to refrain
+ entirely from distribution of the Program.
+
+ If any portion of this section is held invalid or unenforceable
+ under any particular circumstance, the balance of the section is
+ intended to apply and the section as a whole is intended to apply
+ in other circumstances.
+
+ It is not the purpose of this section to induce you to infringe any
+ patents or other property right claims or to contest validity of
+ any such claims; this section has the sole purpose of protecting
+ the integrity of the free software distribution system, which is
+ implemented by public license practices. Many people have made
+ generous contributions to the wide range of software distributed
+ through that system in reliance on consistent application of that
+ system; it is up to the author/donor to decide if he or she is
+ willing to distribute software through any other system and a
+ licensee cannot impose that choice.
+
+ This section is intended to make thoroughly clear what is believed
+ to be a consequence of the rest of this License.
+
+ 8. If the distribution and/or use of the Program is restricted in
+ certain countries either by patents or by copyrighted interfaces,
+ the original copyright holder who places the Program under this
+ License may add an explicit geographical distribution limitation
+ excluding those countries, so that distribution is permitted only
+ in or among countries not thus excluded. In such case, this
+ License incorporates the limitation as if written in the body of
+ this License.
+
+ 9. The Free Software Foundation may publish revised and/or new
+ versions of the General Public License from time to time. Such
+ new versions will be similar in spirit to the present version, but
+ may differ in detail to address new problems or concerns.
+
+ Each version is given a distinguishing version number. If the
+ Program specifies a version number of this License which applies
+ to it and "any later version", you have the option of following
+ the terms and conditions either of that version or of any later
+ version published by the Free Software Foundation. If the Program
+ does not specify a version number of this License, you may choose
+ any version ever published by the Free Software Foundation.
+
+ 10. If you wish to incorporate parts of the Program into other free
+ programs whose distribution conditions are different, write to the
+ author to ask for permission. For software which is copyrighted
+ by the Free Software Foundation, write to the Free Software
+ Foundation; we sometimes make exceptions for this. Our decision
+ will be guided by the two goals of preserving the free status of
+ all derivatives of our free software and of promoting the sharing
+ and reuse of software generally.
+
+ NO WARRANTY
+
+ 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO
+ WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE
+ LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT
+ HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT
+ WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT
+ NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
+ FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE
+ QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE
+ PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY
+ SERVICING, REPAIR OR CORRECTION.
+
+ 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN
+ WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY
+ MODIFY AND/OR REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE
+ LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL,
+ INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR
+ INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF
+ DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU
+ OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY
+ OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN
+ ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
+
+ END OF TERMS AND CONDITIONS
+
+How to Apply These Terms to Your New Programs
+=============================================
+
+ If you develop a new program, and you want it to be of the greatest
+possible use to the public, the best way to achieve this is to make it
+free software which everyone can redistribute and change under these
+terms.
+
+ To do so, attach the following notices to the program. It is safest
+to attach them to the start of each source file to most effectively
+convey the exclusion of warranty; and each file should have at least
+the "copyright" line and a pointer to where the full notice is found.
+
+ ONE LINE TO GIVE THE PROGRAM'S NAME AND A BRIEF IDEA OF WHAT IT DOES.
+ Copyright (C) 19YY NAME OF AUTHOR
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA.
+
+ Also add information on how to contact you by electronic and paper
+mail.
+
+ If the program is interactive, make it output a short notice like
+this when it starts in an interactive mode:
+
+ Gnomovision version 69, Copyright (C) 19YY NAME OF AUTHOR
+ Gnomovision comes with ABSOLUTELY NO WARRANTY; for details
+ type `show w'.
+ This is free software, and you are welcome to redistribute it
+ under certain conditions; type `show c' for details.
+
+ The hypothetical commands `show w' and `show c' should show the
+appropriate parts of the General Public License. Of course, the
+commands you use may be called something other than `show w' and `show
+c'; they could even be mouse-clicks or menu items--whatever suits your
+program.
+
+ You should also get your employer (if you work as a programmer) or
+your school, if any, to sign a "copyright disclaimer" for the program,
+if necessary. Here is a sample; alter the names:
+
+ Yoyodyne, Inc., hereby disclaims all copyright interest in the program
+ `Gnomovision' (which makes passes at compilers) written by James Hacker.
+
+ SIGNATURE OF TY COON, 1 April 1989
+ Ty Coon, President of Vice
+
+ This General Public License does not permit incorporating your
+program into proprietary programs. If your program is a subroutine
+library, you may consider it more useful to permit linking proprietary
+applications with the library. If this is what you want to do, use the
+GNU Library General Public License instead of this License.
+
+
+File: bison.info, Node: Concepts, Next: Examples, Prev: Copying, Up: Top
+
+The Concepts of Bison
+*********************
+
+ This chapter introduces many of the basic concepts without which the
+details of Bison will not make sense. If you do not already know how to
+use Bison or Yacc, we suggest you start by reading this chapter
+carefully.
+
+* Menu:
+
+* Language and Grammar:: Languages and context-free grammars,
+ as mathematical ideas.
+* Grammar in Bison:: How we represent grammars for Bison's sake.
+* Semantic Values:: Each token or syntactic grouping can have
+ a semantic value (the value of an integer,
+ the name of an identifier, etc.).
+* Semantic Actions:: Each rule can have an action containing C code.
+* Bison Parser:: What are Bison's input and output,
+ how is the output used?
+* Stages:: Stages in writing and running Bison grammars.
+* Grammar Layout:: Overall structure of a Bison grammar file.
+
+
+File: bison.info, Node: Language and Grammar, Next: Grammar in Bison, Up: Concepts
+
+Languages and Context-Free Grammars
+===================================
+
+ In order for Bison to parse a language, it must be described by a
+"context-free grammar". This means that you specify one or more
+"syntactic groupings" and give rules for constructing them from their
+parts. For example, in the C language, one kind of grouping is called
+an `expression'. One rule for making an expression might be, "An
+expression can be made of a minus sign and another expression".
+Another would be, "An expression can be an integer". As you can see,
+rules are often recursive, but there must be at least one rule which
+leads out of the recursion.
+
+ The most common formal system for presenting such rules for humans
+to read is "Backus-Naur Form" or "BNF", which was developed in order to
+specify the language Algol 60. Any grammar expressed in BNF is a
+context-free grammar. The input to Bison is essentially
+machine-readable BNF.
+
+ Not all context-free languages can be handled by Bison, only those
+that are LALR(1). In brief, this means that it must be possible to
+tell how to parse any portion of an input string with just a single
+token of look-ahead. Strictly speaking, that is a description of an
+LR(1) grammar, and LALR(1) involves additional restrictions that are
+hard to explain simply; but it is rare in actual practice to find an
+LR(1) grammar that fails to be LALR(1). *Note Mysterious Reduce/Reduce
+Conflicts: Mystery Conflicts, for more information on this.
+
+ In the formal grammatical rules for a language, each kind of
+syntactic unit or grouping is named by a "symbol". Those which are
+built by grouping smaller constructs according to grammatical rules are
+called "nonterminal symbols"; those which can't be subdivided are called
+"terminal symbols" or "token types". We call a piece of input
+corresponding to a single terminal symbol a "token", and a piece
+corresponding to a single nonterminal symbol a "grouping".
+
+ We can use the C language as an example of what symbols, terminal and
+nonterminal, mean. The tokens of C are identifiers, constants (numeric
+and string), and the various keywords, arithmetic operators and
+punctuation marks. So the terminal symbols of a grammar for C include
+`identifier', `number', `string', plus one symbol for each keyword,
+operator or punctuation mark: `if', `return', `const', `static', `int',
+`char', `plus-sign', `open-brace', `close-brace', `comma' and many
+more. (These tokens can be subdivided into characters, but that is a
+matter of lexicography, not grammar.)
+
+ Here is a simple C function subdivided into tokens:
+
+ int /* keyword `int' */
+ square (x) /* identifier, open-paren, */
+ /* identifier, close-paren */
+ int x; /* keyword `int', identifier, semicolon */
+ { /* open-brace */
+ return x * x; /* keyword `return', identifier, */
+ /* asterisk, identifier, semicolon */
+ } /* close-brace */
+
+ The syntactic groupings of C include the expression, the statement,
+the declaration, and the function definition. These are represented in
+the grammar of C by nonterminal symbols `expression', `statement',
+`declaration' and `function definition'. The full grammar uses dozens
+of additional language constructs, each with its own nonterminal
+symbol, in order to express the meanings of these four. The example
+above is a function definition; it contains one declaration, and one
+statement. In the statement, each `x' is an expression and so is `x *
+x'.
+
+ Each nonterminal symbol must have grammatical rules showing how it
+is made out of simpler constructs. For example, one kind of C
+statement is the `return' statement; this would be described with a
+grammar rule which reads informally as follows:
+
+ A `statement' can be made of a `return' keyword, an `expression'
+ and a `semicolon'.
+
+There would be many other rules for `statement', one for each kind of
+statement in C.
+
+ One nonterminal symbol must be distinguished as the special one which
+defines a complete utterance in the language. It is called the "start
+symbol". In a compiler, this means a complete input program. In the C
+language, the nonterminal symbol `sequence of definitions and
+declarations' plays this role.
+
+ For example, `1 + 2' is a valid C expression--a valid part of a C
+program--but it is not valid as an _entire_ C program. In the
+context-free grammar of C, this follows from the fact that `expression'
+is not the start symbol.
+
+ The Bison parser reads a sequence of tokens as its input, and groups
+the tokens using the grammar rules. If the input is valid, the end
+result is that the entire token sequence reduces to a single grouping
+whose symbol is the grammar's start symbol. If we use a grammar for C,
+the entire input must be a `sequence of definitions and declarations'.
+If not, the parser reports a syntax error.
+
+
+File: bison.info, Node: Grammar in Bison, Next: Semantic Values, Prev: Language and Grammar, Up: Concepts
+
+From Formal Rules to Bison Input
+================================
+
+ A formal grammar is a mathematical construct. To define the language
+for Bison, you must write a file expressing the grammar in Bison syntax:
+a "Bison grammar" file. *Note Bison Grammar Files: Grammar File.
+
+ A nonterminal symbol in the formal grammar is represented in Bison
+input as an identifier, like an identifier in C. By convention, it
+should be in lower case, such as `expr', `stmt' or `declaration'.
+
+ The Bison representation for a terminal symbol is also called a
+"token type". Token types as well can be represented as C-like
+identifiers. By convention, these identifiers should be upper case to
+distinguish them from nonterminals: for example, `INTEGER',
+`IDENTIFIER', `IF' or `RETURN'. A terminal symbol that stands for a
+particular keyword in the language should be named after that keyword
+converted to upper case. The terminal symbol `error' is reserved for
+error recovery. *Note Symbols::.
+
+ A terminal symbol can also be represented as a character literal,
+just like a C character constant. You should do this whenever a token
+is just a single character (parenthesis, plus-sign, etc.): use that
+same character in a literal as the terminal symbol for that token.
+
+ A third way to represent a terminal symbol is with a C string
+constant containing several characters. *Note Symbols::, for more
+information.
+
+ The grammar rules also have an expression in Bison syntax. For
+example, here is the Bison rule for a C `return' statement. The
+semicolon in quotes is a literal character token, representing part of
+the C syntax for the statement; the naked semicolon, and the colon, are
+Bison punctuation used in every rule.
+
+ stmt: RETURN expr ';'
+ ;
+
+*Note Syntax of Grammar Rules: Rules.
+
+
+File: bison.info, Node: Semantic Values, Next: Semantic Actions, Prev: Grammar in Bison, Up: Concepts
+
+Semantic Values
+===============
+
+ A formal grammar selects tokens only by their classifications: for
+example, if a rule mentions the terminal symbol `integer constant', it
+means that _any_ integer constant is grammatically valid in that
+position. The precise value of the constant is irrelevant to how to
+parse the input: if `x+4' is grammatical then `x+1' or `x+3989' is
+equally grammatical.
+
+ But the precise value is very important for what the input means
+once it is parsed. A compiler is useless if it fails to distinguish
+between 4, 1 and 3989 as constants in the program! Therefore, each
+token in a Bison grammar has both a token type and a "semantic value".
+*Note Defining Language Semantics: Semantics, for details.
+
+ The token type is a terminal symbol defined in the grammar, such as
+`INTEGER', `IDENTIFIER' or `',''. It tells everything you need to know
+to decide where the token may validly appear and how to group it with
+other tokens. The grammar rules know nothing about tokens except their
+types.
+
+ The semantic value has all the rest of the information about the
+meaning of the token, such as the value of an integer, or the name of an
+identifier. (A token such as `','' which is just punctuation doesn't
+need to have any semantic value.)
+
+ For example, an input token might be classified as token type
+`INTEGER' and have the semantic value 4. Another input token might
+have the same token type `INTEGER' but value 3989. When a grammar rule
+says that `INTEGER' is allowed, either of these tokens is acceptable
+because each is an `INTEGER'. When the parser accepts the token, it
+keeps track of the token's semantic value.
+
+ Each grouping can also have a semantic value as well as its
+nonterminal symbol. For example, in a calculator, an expression
+typically has a semantic value that is a number. In a compiler for a
+programming language, an expression typically has a semantic value that
+is a tree structure describing the meaning of the expression.
+
+
+File: bison.info, Node: Semantic Actions, Next: Bison Parser, Prev: Semantic Values, Up: Concepts
+
+Semantic Actions
+================
+
+ In order to be useful, a program must do more than parse input; it
+must also produce some output based on the input. In a Bison grammar,
+a grammar rule can have an "action" made up of C statements. Each time
+the parser recognizes a match for that rule, the action is executed.
+*Note Actions::.
+
+ Most of the time, the purpose of an action is to compute the
+semantic value of the whole construct from the semantic values of its
+parts. For example, suppose we have a rule which says an expression
+can be the sum of two expressions. When the parser recognizes such a
+sum, each of the subexpressions has a semantic value which describes
+how it was built up. The action for this rule should create a similar
+sort of value for the newly recognized larger expression.
+
+ For example, here is a rule that says an expression can be the sum of
+two subexpressions:
+
+ expr: expr '+' expr { $$ = $1 + $3; }
+ ;
+
+The action says how to produce the semantic value of the sum expression
+from the values of the two subexpressions.
+
+
+File: bison.info, Node: Bison Parser, Next: Stages, Prev: Semantic Actions, Up: Concepts
+
+Bison Output: the Parser File
+=============================
+
+ When you run Bison, you give it a Bison grammar file as input. The
+output is a C source file that parses the language described by the
+grammar. This file is called a "Bison parser". Keep in mind that the
+Bison utility and the Bison parser are two distinct programs: the Bison
+utility is a program whose output is the Bison parser that becomes part
+of your program.
+
+ The job of the Bison parser is to group tokens into groupings
+according to the grammar rules--for example, to build identifiers and
+operators into expressions. As it does this, it runs the actions for
+the grammar rules it uses.
+
+ The tokens come from a function called the "lexical analyzer" that
+you must supply in some fashion (such as by writing it in C). The
+Bison parser calls the lexical analyzer each time it wants a new token.
+It doesn't know what is "inside" the tokens (though their semantic
+values may reflect this). Typically the lexical analyzer makes the
+tokens by parsing characters of text, but Bison does not depend on
+this. *Note The Lexical Analyzer Function `yylex': Lexical.
+
+ The Bison parser file is C code which defines a function named
+`yyparse' which implements that grammar. This function does not make a
+complete C program: you must supply some additional functions. One is
+the lexical analyzer. Another is an error-reporting function which the
+parser calls to report an error. In addition, a complete C program must
+start with a function called `main'; you have to provide this, and
+arrange for it to call `yyparse' or the parser will never run. *Note
+Parser C-Language Interface: Interface.
+
+ Aside from the token type names and the symbols in the actions you
+write, all variable and function names used in the Bison parser file
+begin with `yy' or `YY'. This includes interface functions such as the
+lexical analyzer function `yylex', the error reporting function
+`yyerror' and the parser function `yyparse' itself. This also includes
+numerous identifiers used for internal purposes. Therefore, you should
+avoid using C identifiers starting with `yy' or `YY' in the Bison
+grammar file except for the ones defined in this manual.
+
+
+File: bison.info, Node: Stages, Next: Grammar Layout, Prev: Bison Parser, Up: Concepts
+
+Stages in Using Bison
+=====================
+
+ The actual language-design process using Bison, from grammar
+specification to a working compiler or interpreter, has these parts:
+
+ 1. Formally specify the grammar in a form recognized by Bison (*note
+ Bison Grammar Files: Grammar File.). For each grammatical rule in
+ the language, describe the action that is to be taken when an
+ instance of that rule is recognized. The action is described by a
+ sequence of C statements.
+
+ 2. Write a lexical analyzer to process input and pass tokens to the
+ parser. The lexical analyzer may be written by hand in C (*note
+ The Lexical Analyzer Function `yylex': Lexical.). It could also
+ be produced using Lex, but the use of Lex is not discussed in this
+ manual.
+
+ 3. Write a controlling function that calls the Bison-produced parser.
+
+ 4. Write error-reporting routines.
+
+ To turn this source code as written into a runnable program, you
+must follow these steps:
+
+ 1. Run Bison on the grammar to produce the parser.
+
+ 2. Compile the code output by Bison, as well as any other source
+ files.
+
+ 3. Link the object files to produce the finished product.
+
+
+File: bison.info, Node: Grammar Layout, Prev: Stages, Up: Concepts
+
+The Overall Layout of a Bison Grammar
+=====================================
+
+ The input file for the Bison utility is a "Bison grammar file". The
+general form of a Bison grammar file is as follows:
+
+ %{
+ C DECLARATIONS
+ %}
+
+ BISON DECLARATIONS
+
+ %%
+ GRAMMAR RULES
+ %%
+ ADDITIONAL C CODE
+
+The `%%', `%{' and `%}' are punctuation that appears in every Bison
+grammar file to separate the sections.
+
+ The C declarations may define types and variables used in the
+actions. You can also use preprocessor commands to define macros used
+there, and use `#include' to include header files that do any of these
+things.
+
+ The Bison declarations declare the names of the terminal and
+nonterminal symbols, and may also describe operator precedence and the
+data types of semantic values of various symbols.
+
+ The grammar rules define how to construct each nonterminal symbol
+from its parts.
+
+ The additional C code can contain any C code you want to use. Often
+the definition of the lexical analyzer `yylex' goes here, plus
+subroutines called by the actions in the grammar rules. In a simple
+program, all the rest of the program can go here.
+
+
+File: bison.info, Node: Examples, Next: Grammar File, Prev: Concepts, Up: Top
+
+Examples
+********
+
+ Now we show and explain three sample programs written using Bison: a
+reverse polish notation calculator, an algebraic (infix) notation
+calculator, and a multi-function calculator. All three have been tested
+under BSD Unix 4.3; each produces a usable, though limited, interactive
+desk-top calculator.
+
+ These examples are simple, but Bison grammars for real programming
+languages are written the same way. You can copy these examples out of
+the Info file and into a source file to try them.
+
+* Menu:
+
+* RPN Calc:: Reverse polish notation calculator;
+ a first example with no operator precedence.
+* Infix Calc:: Infix (algebraic) notation calculator.
+ Operator precedence is introduced.
+* Simple Error Recovery:: Continuing after syntax errors.
+* Multi-function Calc:: Calculator with memory and trig functions.
+ It uses multiple data-types for semantic values.
+* Exercises:: Ideas for improving the multi-function calculator.
+
+
+File: bison.info, Node: RPN Calc, Next: Infix Calc, Up: Examples
+
+Reverse Polish Notation Calculator
+==================================
+
+ The first example is that of a simple double-precision "reverse
+polish notation" calculator (a calculator using postfix operators).
+This example provides a good starting point, since operator precedence
+is not an issue. The second example will illustrate how operator
+precedence is handled.
+
+ The source code for this calculator is named `rpcalc.y'. The `.y'
+extension is a convention used for Bison input files.
+
+* Menu:
+
+* Decls: Rpcalc Decls. Bison and C declarations for rpcalc.
+* Rules: Rpcalc Rules. Grammar Rules for rpcalc, with explanation.
+* Lexer: Rpcalc Lexer. The lexical analyzer.
+* Main: Rpcalc Main. The controlling function.
+* Error: Rpcalc Error. The error reporting function.
+* Gen: Rpcalc Gen. Running Bison on the grammar file.
+* Comp: Rpcalc Compile. Run the C compiler on the output code.
+
+
+File: bison.info, Node: Rpcalc Decls, Next: Rpcalc Rules, Up: RPN Calc
+
+Declarations for `rpcalc'
+-------------------------
+
+ Here are the C and Bison declarations for the reverse polish notation
+calculator. As in C, comments are placed between `/*...*/'.
+
+ /* Reverse polish notation calculator. */
+
+ %{
+ #define YYSTYPE double
+ #include <math.h>
+ %}
+
+ %token NUM
+
+ %% /* Grammar rules and actions follow */
+
+ The C declarations section (*note The C Declarations Section: C
+Declarations.) contains two preprocessor directives.
+
+ The `#define' directive defines the macro `YYSTYPE', thus specifying
+the C data type for semantic values of both tokens and groupings (*note
+Data Types of Semantic Values: Value Type.). The Bison parser will use
+whatever type `YYSTYPE' is defined as; if you don't define it, `int' is
+the default. Because we specify `double', each token and each
+expression has an associated value, which is a floating point number.
+
+ The `#include' directive is used to declare the exponentiation
+function `pow'.
+
+ The second section, Bison declarations, provides information to
+Bison about the token types (*note The Bison Declarations Section:
+Bison Declarations.). Each terminal symbol that is not a
+single-character literal must be declared here. (Single-character
+literals normally don't need to be declared.) In this example, all the
+arithmetic operators are designated by single-character literals, so the
+only terminal symbol that needs to be declared is `NUM', the token type
+for numeric constants.
+