Added tool bison++-1.21.11

1 files changed, 1287 insertions, 0 deletions

diff --git a/tools/bison++/bison.info-3 b/tools/bison++/bison.info-3
new file mode 100644
index 000000000..bf519e312
--- /dev/null
+++ b/tools/bison++/bison.info-3
@@ -0,0 +1,1287 @@
+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: Mid-Rule Actions,  Prev: Action Types,  Up: Semantics
+
+Actions in Mid-Rule
+-------------------
+
+   Occasionally it is useful to put an action in the middle of a rule.
+These actions are written just like usual end-of-rule actions, but they
+are executed before the parser even recognizes the following components.
+
+   A mid-rule action may refer to the components preceding it using
+`$N', but it may not refer to subsequent components because it is run
+before they are parsed.
+
+   The mid-rule action itself counts as one of the components of the
+rule.  This makes a difference when there is another action later in
+the same rule (and usually there is another at the end): you have to
+count the actions along with the symbols when working out which number
+N to use in `$N'.
+
+   The mid-rule action can also have a semantic value.  The action can
+set its value with an assignment to `$$', and actions later in the rule
+can refer to the value using `$N'.  Since there is no symbol to name
+the action, there is no way to declare a data type for the value in
+advance, so you must use the `$<...>' construct to specify a data type
+each time you refer to this value.
+
+   There is no way to set the value of the entire rule with a mid-rule
+action, because assignments to `$$' do not have that effect.  The only
+way to set the value for the entire rule is with an ordinary action at
+the end of the rule.
+
+   Here is an example from a hypothetical compiler, handling a `let'
+statement that looks like `let (VARIABLE) STATEMENT' and serves to
+create a variable named VARIABLE temporarily for the duration of
+STATEMENT.  To parse this construct, we must put VARIABLE into the
+symbol table while STATEMENT is parsed, then remove it afterward.  Here
+is how it is done:
+
+     stmt:   LET '(' var ')'
+                     { $<context>$ = push_context ();
+                       declare_variable ($3); }
+             stmt    { $$ = $6;
+                       pop_context ($<context>5); }
+
+As soon as `let (VARIABLE)' has been recognized, the first action is
+run.  It saves a copy of the current semantic context (the list of
+accessible variables) as its semantic value, using alternative
+`context' in the data-type union.  Then it calls `declare_variable' to
+add the new variable to that list.  Once the first action is finished,
+the embedded statement `stmt' can be parsed.  Note that the mid-rule
+action is component number 5, so the `stmt' is component number 6.
+
+   After the embedded statement is parsed, its semantic value becomes
+the value of the entire `let'-statement.  Then the semantic value from
+the earlier action is used to restore the prior list of variables.  This
+removes the temporary `let'-variable from the list so that it won't
+appear to exist while the rest of the program is parsed.
+
+   Taking action before a rule is completely recognized often leads to
+conflicts since the parser must commit to a parse in order to execute
+the action.  For example, the following two rules, without mid-rule
+actions, can coexist in a working parser because the parser can shift
+the open-brace token and look at what follows before deciding whether
+there is a declaration or not:
+
+     compound: '{' declarations statements '}'
+             | '{' statements '}'
+             ;
+
+But when we add a mid-rule action as follows, the rules become
+nonfunctional:
+
+     compound: { prepare_for_local_variables (); }
+               '{' declarations statements '}'
+             | '{' statements '}'
+             ;
+
+Now the parser is forced to decide whether to run the mid-rule action
+when it has read no farther than the open-brace.  In other words, it
+must commit to using one rule or the other, without sufficient
+information to do it correctly.  (The open-brace token is what is called
+the "look-ahead" token at this time, since the parser is still deciding
+what to do about it.  *Note Look-Ahead Tokens: Look-Ahead.)
+
+   You might think that you could correct the problem by putting
+identical actions into the two rules, like this:
+
+     compound: { prepare_for_local_variables (); }
+               '{' declarations statements '}'
+             | { prepare_for_local_variables (); }
+               '{' statements '}'
+             ;
+
+But this does not help, because Bison does not realize that the two
+actions are identical.  (Bison never tries to understand the C code in
+an action.)
+
+   If the grammar is such that a declaration can be distinguished from a
+statement by the first token (which is true in C), then one solution
+which does work is to put the action after the open-brace, like this:
+
+     compound: '{' { prepare_for_local_variables (); }
+               declarations statements '}'
+             | '{' statements '}'
+             ;
+
+Now the first token of the following declaration or statement, which
+would in any case tell Bison which rule to use, can still do so.
+
+   Another solution is to bury the action inside a nonterminal symbol
+which serves as a subroutine:
+
+     subroutine: /* empty */
+               { prepare_for_local_variables (); }
+             ;
+     
+     compound: subroutine
+               '{' declarations statements '}'
+             | subroutine
+               '{' statements '}'
+             ;
+
+Now Bison can execute the action in the rule for `subroutine' without
+deciding which rule for `compound' it will eventually use.  Note that
+the action is now at the end of its rule.  Any mid-rule action can be
+converted to an end-of-rule action in this way, and this is what Bison
+actually does to implement mid-rule actions.
+
+
+File: bison.info,  Node: Declarations,  Next: Multiple Parsers,  Prev: Semantics,  Up: Grammar File
+
+Bison Declarations
+==================
+
+   The "Bison declarations" section of a Bison grammar defines the
+symbols used in formulating the grammar and the data types of semantic
+values.  *Note Symbols::.
+
+   All token type names (but not single-character literal tokens such as
+`'+'' and `'*'') must be declared.  Nonterminal symbols must be
+declared if you need to specify which data type to use for the semantic
+value (*note More Than One Value Type: Multiple Types.).
+
+   The first rule in the file also specifies the start symbol, by
+default.  If you want some other symbol to be the start symbol, you
+must declare it explicitly (*note Languages and Context-Free Grammars:
+Language and Grammar.).
+
+* Menu:
+
+* 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.
+
+
+File: bison.info,  Node: Token Decl,  Next: Precedence Decl,  Up: Declarations
+
+Token Type Names
+----------------
+
+   The basic way to declare a token type name (terminal symbol) is as
+follows:
+
+     %token NAME
+
+   Bison will convert this into a `#define' directive in the parser, so
+that the function `yylex' (if it is in this file) can use the name NAME
+to stand for this token type's code.
+
+   Alternatively, you can use `%left', `%right', or `%nonassoc' instead
+of `%token', if you wish to specify precedence.  *Note Operator
+Precedence: Precedence Decl.
+
+   You can explicitly specify the numeric code for a token type by
+appending an integer value in the field immediately following the token
+name:
+
+     %token NUM 300
+
+It is generally best, however, to let Bison choose the numeric codes for
+all token types.  Bison will automatically select codes that don't
+conflict with each other or with ASCII characters.
+
+   In the event that the stack type is a union, you must augment the
+`%token' or other token declaration to include the data type
+alternative delimited by angle-brackets (*note More Than One Value
+Type: Multiple Types.).
+
+   For example:
+
+     %union {              /* define stack type */
+       double val;
+       symrec *tptr;
+     }
+     %token <val> NUM      /* define token NUM and its type */
+
+   You can associate a literal string token with a token type name by
+writing the literal string at the end of a `%token' declaration which
+declares the name.  For example:
+
+     %token arrow "=>"
+
+For example, a grammar for the C language might specify these names with
+equivalent literal string tokens:
+
+     %token  <operator>  OR      "||"
+     %token  <operator>  LE 134  "<="
+     %left  OR  "<="
+
+Once you equate the literal string and the token name, you can use them
+interchangeably in further declarations or the grammar rules.  The
+`yylex' function can use the token name or the literal string to obtain
+the token type code number (*note Calling Convention::).
+
+
+File: bison.info,  Node: Precedence Decl,  Next: Union Decl,  Prev: Token Decl,  Up: Declarations
+
+Operator Precedence
+-------------------
+
+   Use the `%left', `%right' or `%nonassoc' declaration to declare a
+token and specify its precedence and associativity, all at once.  These
+are called "precedence declarations".  *Note Operator Precedence:
+Precedence, for general information on operator precedence.
+
+   The syntax of a precedence declaration is the same as that of
+`%token': either
+
+     %left SYMBOLS...
+
+or
+
+     %left <TYPE> SYMBOLS...
+
+   And indeed any of these declarations serves the purposes of `%token'.
+But in addition, they specify the associativity and relative precedence
+for all the SYMBOLS:
+
+   * The associativity of an operator OP determines how repeated uses
+     of the operator nest: whether `X OP Y OP Z' is parsed by grouping
+     X with Y first or by grouping Y with Z first.  `%left' specifies
+     left-associativity (grouping X with Y first) and `%right'
+     specifies right-associativity (grouping Y with Z first).
+     `%nonassoc' specifies no associativity, which means that `X OP Y
+     OP Z' is considered a syntax error.
+
+   * The precedence of an operator determines how it nests with other
+     operators.  All the tokens declared in a single precedence
+     declaration have equal precedence and nest together according to
+     their associativity.  When two tokens declared in different
+     precedence declarations associate, the one declared later has the
+     higher precedence and is grouped first.
+
+
+File: bison.info,  Node: Union Decl,  Next: Type Decl,  Prev: Precedence Decl,  Up: Declarations
+
+The Collection of Value Types
+-----------------------------
+
+   The `%union' declaration specifies the entire collection of possible
+data types for semantic values.  The keyword `%union' is followed by a
+pair of braces containing the same thing that goes inside a `union' in
+C.
+
+   For example:
+
+     %union {
+       double val;
+       symrec *tptr;
+     }
+
+This says that the two alternative types are `double' and `symrec *'.
+They are given names `val' and `tptr'; these names are used in the
+`%token' and `%type' declarations to pick one of the types for a
+terminal or nonterminal symbol (*note Nonterminal Symbols: Type Decl.).
+
+   Note that, unlike making a `union' declaration in C, you do not write
+a semicolon after the closing brace.
+
+
+File: bison.info,  Node: Type Decl,  Next: Expect Decl,  Prev: Union Decl,  Up: Declarations
+
+Nonterminal Symbols
+-------------------
+
+When you use `%union' to specify multiple value types, you must declare
+the value type of each nonterminal symbol for which values are used.
+This is done with a `%type' declaration, like this:
+
+     %type <TYPE> NONTERMINAL...
+
+Here NONTERMINAL is the name of a nonterminal symbol, and TYPE is the
+name given in the `%union' to the alternative that you want (*note The
+Collection of Value Types: Union Decl.).  You can give any number of
+nonterminal symbols in the same `%type' declaration, if they have the
+same value type.  Use spaces to separate the symbol names.
+
+   You can also declare the value type of a terminal symbol.  To do
+this, use the same `<TYPE>' construction in a declaration for the
+terminal symbol.  All kinds of token declarations allow `<TYPE>'.
+
+
+File: bison.info,  Node: Expect Decl,  Next: Start Decl,  Prev: Type Decl,  Up: Declarations
+
+Suppressing Conflict Warnings
+-----------------------------
+
+   Bison normally warns if there are any conflicts in the grammar
+(*note Shift/Reduce Conflicts: Shift/Reduce.), but most real grammars
+have harmless shift/reduce conflicts which are resolved in a
+predictable way and would be difficult to eliminate.  It is desirable
+to suppress the warning about these conflicts unless the number of
+conflicts changes.  You can do this with the `%expect' declaration.
+
+   The declaration looks like this:
+
+     %expect N
+
+   Here N is a decimal integer.  The declaration says there should be no
+warning if there are N shift/reduce conflicts and no reduce/reduce
+conflicts.  The usual warning is given if there are either more or fewer
+conflicts, or if there are any reduce/reduce conflicts.
+
+   In general, using `%expect' involves these steps:
+
+   * Compile your grammar without `%expect'.  Use the `-v' option to
+     get a verbose list of where the conflicts occur.  Bison will also
+     print the number of conflicts.
+
+   * Check each of the conflicts to make sure that Bison's default
+     resolution is what you really want.  If not, rewrite the grammar
+     and go back to the beginning.
+
+   * Add an `%expect' declaration, copying the number N from the number
+     which Bison printed.
+
+   Now Bison will stop annoying you about the conflicts you have
+checked, but it will warn you again if changes in the grammar result in
+additional conflicts.
+
+
+File: bison.info,  Node: Start Decl,  Next: Pure Decl,  Prev: Expect Decl,  Up: Declarations
+
+The Start-Symbol
+----------------
+
+   Bison assumes by default that the start symbol for the grammar is
+the first nonterminal specified in the grammar specification section.
+The programmer may override this restriction with the `%start'
+declaration as follows:
+
+     %start SYMBOL
+
+
+File: bison.info,  Node: Pure Decl,  Next: Decl Summary,  Prev: Start Decl,  Up: Declarations
+
+A Pure (Reentrant) Parser
+-------------------------
+
+   A "reentrant" program is one which does not alter in the course of
+execution; in other words, it consists entirely of "pure" (read-only)
+code.  Reentrancy is important whenever asynchronous execution is
+possible; for example, a nonreentrant program may not be safe to call
+from a signal handler.  In systems with multiple threads of control, a
+nonreentrant program must be called only within interlocks.
+
+   Normally, Bison generates a parser which is not reentrant.  This is
+suitable for most uses, and it permits compatibility with YACC.  (The
+standard YACC interfaces are inherently nonreentrant, because they use
+statically allocated variables for communication with `yylex',
+including `yylval' and `yylloc'.)
+
+   Alternatively, you can generate a pure, reentrant parser.  The Bison
+declaration `%pure_parser' says that you want the parser to be
+reentrant.  It looks like this:
+
+     %pure_parser
+
+   The result is that the communication variables `yylval' and `yylloc'
+become local variables in `yyparse', and a different calling convention
+is used for the lexical analyzer function `yylex'.  *Note Calling
+Conventions for Pure Parsers: Pure Calling, for the details of this.
+The variable `yynerrs' also becomes local in `yyparse' (*note The Error
+Reporting Function `yyerror': Error Reporting.).  The convention for
+calling `yyparse' itself is unchanged.
+
+   Whether the parser is pure has nothing to do with the grammar rules.
+You can generate either a pure parser or a nonreentrant parser from any
+valid grammar.
+
+
+File: bison.info,  Node: Decl Summary,  Prev: Pure Decl,  Up: Declarations
+
+Bison Declaration Summary
+-------------------------
+
+   Here is a summary of all Bison declarations:
+
+`%union'
+     Declare the collection of data types that semantic values may have
+     (*note The Collection of Value Types: Union Decl.).
+
+`%token'
+     Declare a terminal symbol (token type name) with no precedence or
+     associativity specified (*note Token Type Names: Token Decl.).
+
+`%right'
+     Declare a terminal symbol (token type name) that is
+     right-associative (*note Operator Precedence: Precedence Decl.).
+
+`%left'
+     Declare a terminal symbol (token type name) that is
+     left-associative (*note Operator Precedence: Precedence Decl.).
+
+`%nonassoc'
+     Declare a terminal symbol (token type name) that is nonassociative
+     (using it in a way that would be associative is a syntax error)
+     (*note Operator Precedence: Precedence Decl.).
+
+`%type'
+     Declare the type of semantic values for a nonterminal symbol
+     (*note Nonterminal Symbols: Type Decl.).
+
+`%start'
+     Specify the grammar's start symbol (*note The Start-Symbol: Start
+     Decl.).
+
+`%expect'
+     Declare the expected number of shift-reduce conflicts (*note
+     Suppressing Conflict Warnings: Expect Decl.).
+
+`%pure_parser'
+     Request a pure (reentrant) parser program (*note A Pure
+     (Reentrant) Parser: Pure Decl.).
+
+`%no_lines'
+     Don't generate any `#line' preprocessor commands in the parser
+     file.  Ordinarily Bison writes these commands in the parser file
+     so that the C compiler and debuggers will associate errors and
+     object code with your source file (the grammar file).  This
+     directive causes them to associate errors with the parser file,
+     treating it an independent source file in its own right.
+
+`%raw'
+     The output file `NAME.h' normally defines the tokens with
+     Yacc-compatible token numbers.  If this option is specified, the
+     internal Bison numbers are used instead.  (Yacc-compatible numbers
+     start at 257 except for single character tokens; Bison assigns
+     token numbers sequentially for all tokens starting at 3.)
+
+`%token_table'
+     Generate an array of token names in the parser file.  The name of
+     the array is `yytname'; `yytname[I]' is the name of the token
+     whose internal Bison token code number is I.  The first three
+     elements of `yytname' are always `"$"', `"error"', and
+     `"$illegal"'; after these come the symbols defined in the grammar
+     file.
+
+     For single-character literal tokens and literal string tokens, the
+     name in the table includes the single-quote or double-quote
+     characters: for example, `"'+'"' is a single-character literal and
+     `"\"<=\""' is a literal string token.  All the characters of the
+     literal string token appear verbatim in the string found in the
+     table; even double-quote characters are not escaped.  For example,
+     if the token consists of three characters `*"*', its string in
+     `yytname' contains `"*"*"'.  (In C, that would be written as
+     `"\"*\"*\""').
+
+     When you specify `%token_table', Bison also generates macro
+     definitions for macros `YYNTOKENS', `YYNNTS', and `YYNRULES', and
+     `YYNSTATES':
+
+    `YYNTOKENS'
+          The highest token number, plus one.
+
+    `YYNNTS'
+          The number of non-terminal symbols.
+
+    `YYNRULES'
+          The number of grammar rules,
+
+    `YYNSTATES'
+          The number of parser states (*note Parser States::).
+
+
+File: bison.info,  Node: Multiple Parsers,  Prev: Declarations,  Up: Grammar File
+
+Multiple Parsers in the Same Program
+====================================
+
+   Most programs that use Bison parse only one language and therefore
+contain only one Bison parser.  But what if you want to parse more than
+one language with the same program?  Then you need to avoid a name
+conflict between different definitions of `yyparse', `yylval', and so
+on.
+
+   The easy way to do this is to use the option `-p PREFIX' (*note
+Invoking Bison: Invocation.).  This renames the interface functions and
+variables of the Bison parser to start with PREFIX instead of `yy'.
+You can use this to give each parser distinct names that do not
+conflict.
+
+   The precise list of symbols renamed is `yyparse', `yylex',
+`yyerror', `yynerrs', `yylval', `yychar' and `yydebug'.  For example,
+if you use `-p c', the names become `cparse', `clex', and so on.
+
+   *All the other variables and macros associated with Bison are not
+renamed.* These others are not global; there is no conflict if the same
+name is used in different parsers.  For example, `YYSTYPE' is not
+renamed, but defining this in different ways in different parsers causes
+no trouble (*note Data Types of Semantic Values: Value Type.).
+
+   The `-p' option works by adding macro definitions to the beginning
+of the parser source file, defining `yyparse' as `PREFIXparse', and so
+on.  This effectively substitutes one name for the other in the entire
+parser file.
+
+
+File: bison.info,  Node: Interface,  Next: Algorithm,  Prev: Grammar File,  Up: Top
+
+Parser C-Language Interface
+***************************
+
+   The Bison parser is actually a C function named `yyparse'.  Here we
+describe the interface conventions of `yyparse' and the other functions
+that it needs to use.
+
+   Keep in mind that the parser uses many C identifiers starting with
+`yy' and `YY' for internal purposes.  If you use such an identifier
+(aside from those in this manual) in an action or in additional C code
+in the grammar file, you are likely to run into trouble.
+
+* Menu:
+
+* 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.
+
+
+File: bison.info,  Node: Parser Function,  Next: Lexical,  Up: Interface
+
+The Parser Function `yyparse'
+=============================
+
+   You call the function `yyparse' to cause parsing to occur.  This
+function reads tokens, executes actions, and ultimately returns when it
+encounters end-of-input or an unrecoverable syntax error.  You can also
+write an action which directs `yyparse' to return immediately without
+reading further.
+
+   The value returned by `yyparse' is 0 if parsing was successful
+(return is due to end-of-input).
+
+   The value is 1 if parsing failed (return is due to a syntax error).
+
+   In an action, you can cause immediate return from `yyparse' by using
+these macros:
+
+`YYACCEPT'
+     Return immediately with value 0 (to report success).
+
+`YYABORT'
+     Return immediately with value 1 (to report failure).
+
+
+File: bison.info,  Node: Lexical,  Next: Error Reporting,  Prev: Parser Function,  Up: Interface
+
+The Lexical Analyzer Function `yylex'
+=====================================
+
+   The "lexical analyzer" function, `yylex', recognizes tokens from the
+input stream and returns them to the parser.  Bison does not create
+this function automatically; you must write it so that `yyparse' can
+call it.  The function is sometimes referred to as a lexical scanner.
+
+   In simple programs, `yylex' is often defined at the end of the Bison
+grammar file.  If `yylex' is defined in a separate source file, you
+need to arrange for the token-type macro definitions to be available
+there.  To do this, use the `-d' option when you run Bison, so that it
+will write these macro definitions into a separate header file
+`NAME.tab.h' which you can include in the other source files that need
+it.  *Note Invoking Bison: Invocation.
+
+* Menu:
+
+* 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.).
+
+
+File: bison.info,  Node: Calling Convention,  Next: Token Values,  Up: Lexical
+
+Calling Convention for `yylex'
+------------------------------
+
+   The value that `yylex' returns must be the numeric code for the type
+of token it has just found, or 0 for end-of-input.
+
+   When a token is referred to in the grammar rules by a name, that name
+in the parser file becomes a C macro whose definition is the proper
+numeric code for that token type.  So `yylex' can use the name to
+indicate that type.  *Note Symbols::.
+
+   When a token is referred to in the grammar rules by a character
+literal, the numeric code for that character is also the code for the
+token type.  So `yylex' can simply return that character code.  The
+null character must not be used this way, because its code is zero and
+that is what signifies end-of-input.
+
+   Here is an example showing these things:
+
+     yylex ()
+     {
+       ...
+       if (c == EOF)     /* Detect end of file. */
+         return 0;
+       ...
+       if (c == '+' || c == '-')
+         return c;      /* Assume token type for `+' is '+'. */
+       ...
+       return INT;      /* Return the type of the token. */
+       ...
+     }
+
+This interface has been designed so that the output from the `lex'
+utility can be used without change as the definition of `yylex'.
+
+   If the grammar uses literal string tokens, there are two ways that
+`yylex' can determine the token type codes for them:
+
+   * If the grammar defines symbolic token names as aliases for the
+     literal string tokens, `yylex' can use these symbolic names like
+     all others.  In this case, the use of the literal string tokens in
+     the grammar file has no effect on `yylex'.
+
+   * `yylex' can find the multi-character token in the `yytname' table.
+     The index of the token in the table is the token type's code.
+     The name of a multi-character token is recorded in `yytname' with a
+     double-quote, the token's characters, and another double-quote.
+     The token's characters are not escaped in any way; they appear
+     verbatim in the contents of the string in the table.
+
+     Here's code for looking up a token in `yytname', assuming that the
+     characters of the token are stored in `token_buffer'.
+
+          for (i = 0; i < YYNTOKENS; i++)
+            {
+              if (yytname[i] != 0
+                  && yytname[i][0] == '"'
+                  && strncmp (yytname[i] + 1, token_buffer,
+                              strlen (token_buffer))
+                  && yytname[i][strlen (token_buffer) + 1] == '"'
+                  && yytname[i][strlen (token_buffer) + 2] == 0)
+                break;
+            }
+
+     The `yytname' table is generated only if you use the
+     `%token_table' declaration.  *Note Decl Summary::.
+
+
+File: bison.info,  Node: Token Values,  Next: Token Positions,  Prev: Calling Convention,  Up: Lexical
+
+Semantic Values of Tokens
+-------------------------
+
+   In an ordinary (nonreentrant) parser, the semantic value of the
+token must be stored into the global variable `yylval'.  When you are
+using just one data type for semantic values, `yylval' has that type.
+Thus, if the type is `int' (the default), you might write this in
+`yylex':
+
+       ...
+       yylval = value;  /* Put value onto Bison stack. */
+       return INT;      /* Return the type of the token. */
+       ...
+
+   When you are using multiple data types, `yylval''s type is a union
+made from the `%union' declaration (*note The Collection of Value
+Types: Union Decl.).  So when you store a token's value, you must use
+the proper member of the union.  If the `%union' declaration looks like
+this:
+
+     %union {
+       int intval;
+       double val;
+       symrec *tptr;
+     }
+
+then the code in `yylex' might look like this:
+
+       ...
+       yylval.intval = value; /* Put value onto Bison stack. */
+       return INT;          /* Return the type of the token. */
+       ...
+
+
+File: bison.info,  Node: Token Positions,  Next: Pure Calling,  Prev: Token Values,  Up: Lexical
+
+Textual Positions of Tokens
+---------------------------
+
+   If you are using the `@N'-feature (*note Special Features for Use in
+Actions: Action Features.) in actions to keep track of the textual
+locations of tokens and groupings, then you must provide this
+information in `yylex'.  The function `yyparse' expects to find the
+textual location of a token just parsed in the global variable
+`yylloc'.  So `yylex' must store the proper data in that variable.  The
+value of `yylloc' is a structure and you need only initialize the
+members that are going to be used by the actions.  The four members are
+called `first_line', `first_column', `last_line' and `last_column'.
+Note that the use of this feature makes the parser noticeably slower.
+
+   The data type of `yylloc' has the name `YYLTYPE'.
+
+
+File: bison.info,  Node: Pure Calling,  Prev: Token Positions,  Up: Lexical
+
+Calling Conventions for Pure Parsers
+------------------------------------
+
+   When you use the Bison declaration `%pure_parser' to request a pure,
+reentrant parser, the global communication variables `yylval' and
+`yylloc' cannot be used.  (*Note A Pure (Reentrant) Parser: Pure Decl.)
+In such parsers the two global variables are replaced by pointers
+passed as arguments to `yylex'.  You must declare them as shown here,
+and pass the information back by storing it through those pointers.
+
+     yylex (lvalp, llocp)
+          YYSTYPE *lvalp;
+          YYLTYPE *llocp;
+     {
+       ...
+       *lvalp = value;  /* Put value onto Bison stack.  */
+       return INT;      /* Return the type of the token.  */
+       ...
+     }
+
+   If the grammar file does not use the `@' constructs to refer to
+textual positions, then the type `YYLTYPE' will not be defined.  In
+this case, omit the second argument; `yylex' will be called with only
+one argument.
+
+   If you use a reentrant parser, you can optionally pass additional
+parameter information to it in a reentrant way.  To do so, define the
+macro `YYPARSE_PARAM' as a variable name.  This modifies the `yyparse'
+function to accept one argument, of type `void *', with that name.
+
+   When you call `yyparse', pass the address of an object, casting the
+address to `void *'.  The grammar actions can refer to the contents of
+the object by casting the pointer value back to its proper type and
+then dereferencing it.  Here's an example.  Write this in the parser:
+
+     %{
+     struct parser_control
+     {
+       int nastiness;
+       int randomness;
+     };
+     
+     #define YYPARSE_PARAM parm
+     %}
+
+Then call the parser like this:
+
+     struct parser_control
+     {
+       int nastiness;
+       int randomness;
+     };
+     
+     ...
+     
+     {
+       struct parser_control foo;
+       ...  /* Store proper data in `foo'.  */
+       value = yyparse ((void *) &foo);
+       ...
+     }
+
+In the grammar actions, use expressions like this to refer to the data:
+
+     ((struct parser_control *) parm)->randomness
+
+   If you wish to pass the additional parameter data to `yylex', define
+the macro `YYLEX_PARAM' just like `YYPARSE_PARAM', as shown here:
+
+     %{
+     struct parser_control
+     {
+       int nastiness;
+       int randomness;
+     };
+     
+     #define YYPARSE_PARAM parm
+     #define YYLEX_PARAM parm
+     %}
+
+   You should then define `yylex' to accept one additional
+argument--the value of `parm'.  (This makes either two or three
+arguments in total, depending on whether an argument of type `YYLTYPE'
+is passed.)  You can declare the argument as a pointer to the proper
+object type, or you can declare it as `void *' and access the contents
+as shown above.
+
+   You can use `%pure_parser' to request a reentrant parser without
+also using `YYPARSE_PARAM'.  Then you should call `yyparse' with no
+arguments, as usual.
+
+
+File: bison.info,  Node: Error Reporting,  Next: Action Features,  Prev: Lexical,  Up: Interface
+
+The Error Reporting Function `yyerror'
+======================================
+
+   The Bison parser detects a "parse error" or "syntax error" whenever
+it reads a token which cannot satisfy any syntax rule.  A action in the
+grammar can also explicitly proclaim an error, using the macro
+`YYERROR' (*note Special Features for Use in Actions: Action Features.).
+
+   The Bison parser expects to report the error by calling an error
+reporting function named `yyerror', which you must supply.  It is
+called by `yyparse' whenever a syntax error is found, and it receives
+one argument.  For a parse error, the string is normally
+`"parse error"'.
+
+   If you define the macro `YYERROR_VERBOSE' in the Bison declarations
+section (*note The Bison Declarations Section: Bison Declarations.),
+then Bison provides a more verbose and specific error message string
+instead of just plain `"parse error"'.  It doesn't matter what
+definition you use for `YYERROR_VERBOSE', just whether you define it.
+
+   The parser can detect one other kind of error: stack overflow.  This
+happens when the input contains constructions that are very deeply
+nested.  It isn't likely you will encounter this, since the Bison
+parser extends its stack automatically up to a very large limit.  But
+if overflow happens, `yyparse' calls `yyerror' in the usual fashion,
+except that the argument string is `"parser stack overflow"'.
+
+   The following definition suffices in simple programs:
+
+     yyerror (s)
+          char *s;
+     {
+       fprintf (stderr, "%s\n", s);
+     }
+
+   After `yyerror' returns to `yyparse', the latter will attempt error
+recovery if you have written suitable error recovery grammar rules
+(*note Error Recovery::).  If recovery is impossible, `yyparse' will
+immediately return 1.
+
+   The variable `yynerrs' contains the number of syntax errors
+encountered so far.  Normally this variable is global; but if you
+request a pure parser (*note A Pure (Reentrant) Parser: Pure Decl.)
+then it is a local variable which only the actions can access.
+
+
+File: bison.info,  Node: Action Features,  Prev: Error Reporting,  Up: Interface
+
+Special Features for Use in Actions
+===================================
+
+   Here is a table of Bison constructs, variables and macros that are
+useful in actions.
+
+`$$'
+     Acts like a variable that contains the semantic value for the
+     grouping made by the current rule.  *Note Actions::.
+
+`$N'
+     Acts like a variable that contains the semantic value for the Nth
+     component of the current rule.  *Note Actions::.
+
+`$<TYPEALT>$'
+     Like `$$' but specifies alternative TYPEALT in the union specified
+     by the `%union' declaration.  *Note Data Types of Values in
+     Actions: Action Types.
+
+`$<TYPEALT>N'
+     Like `$N' but specifies alternative TYPEALT in the union specified
+     by the `%union' declaration.  *Note Data Types of Values in
+     Actions: Action Types.
+
+`YYABORT;'
+     Return immediately from `yyparse', indicating failure.  *Note The
+     Parser Function `yyparse': Parser Function.
+
+`YYACCEPT;'
+     Return immediately from `yyparse', indicating success.  *Note The
+     Parser Function `yyparse': Parser Function.
+
+`YYBACKUP (TOKEN, VALUE);'
+     Unshift a token.  This macro is allowed only for rules that reduce
+     a single value, and only when there is no look-ahead token.  It
+     installs a look-ahead token with token type TOKEN and semantic
+     value VALUE; then it discards the value that was going to be
+     reduced by this rule.
+
+     If the macro is used when it is not valid, such as when there is a
+     look-ahead token already, then it reports a syntax error with a
+     message `cannot back up' and performs ordinary error recovery.
+
+     In either case, the rest of the action is not executed.
+
+`YYEMPTY'
+     Value stored in `yychar' when there is no look-ahead token.
+
+`YYERROR;'
+     Cause an immediate syntax error.  This statement initiates error
+     recovery just as if the parser itself had detected an error;
+     however, it does not call `yyerror', and does not print any
+     message.  If you want to print an error message, call `yyerror'
+     explicitly before the `YYERROR;' statement.  *Note Error
+     Recovery::.
+
+`YYRECOVERING'
+     This macro stands for an expression that has the value 1 when the
+     parser is recovering from a syntax error, and 0 the rest of the
+     time.  *Note Error Recovery::.
+
+`yychar'
+     Variable containing the current look-ahead token.  (In a pure
+     parser, this is actually a local variable within `yyparse'.)  When
+     there is no look-ahead token, the value `YYEMPTY' is stored in the
+     variable.  *Note Look-Ahead Tokens: Look-Ahead.
+
+`yyclearin;'
+     Discard the current look-ahead token.  This is useful primarily in
+     error rules.  *Note Error Recovery::.
+
+`yyerrok;'
+     Resume generating error messages immediately for subsequent syntax
+     errors.  This is useful primarily in error rules.  *Note Error
+     Recovery::.
+
+`@N'
+     Acts like a structure variable containing information on the line
+     numbers and column numbers of the Nth component of the current
+     rule.  The structure has four members, like this:
+
+          struct {
+            int first_line, last_line;
+            int first_column, last_column;
+          };
+
+     Thus, to get the starting line number of the third component, you
+     would use `@3.first_line'.
+
+     In order for the members of this structure to contain valid
+     information, you must make `yylex' supply this information about
+     each token.  If you need only certain members, then `yylex' need
+     only fill in those members.
+
+     The use of this feature makes the parser noticeably slower.
+
+
+File: bison.info,  Node: Algorithm,  Next: Error Recovery,  Prev: Interface,  Up: Top
+
+The Bison Parser Algorithm
+**************************
+
+   As Bison reads tokens, it pushes them onto a stack along with their
+semantic values.  The stack is called the "parser stack".  Pushing a
+token is traditionally called "shifting".
+
+   For example, suppose the infix calculator has read `1 + 5 *', with a
+`3' to come.  The stack will have four elements, one for each token
+that was shifted.
+
+   But the stack does not always have an element for each token read.
+When the last N tokens and groupings shifted match the components of a
+grammar rule, they can be combined according to that rule.  This is
+called "reduction".  Those tokens and groupings are replaced on the
+stack by a single grouping whose symbol is the result (left hand side)
+of that rule.  Running the rule's action is part of the process of
+reduction, because this is what computes the semantic value of the
+resulting grouping.
+
+   For example, if the infix calculator's parser stack contains this:
+
+     1 + 5 * 3
+
+and the next input token is a newline character, then the last three
+elements can be reduced to 15 via the rule:
+
+     expr: expr '*' expr;
+
+Then the stack contains just these three elements:
+
+     1 + 15
+
+At this point, another reduction can be made, resulting in the single
+value 16.  Then the newline token can be shifted.
+
+   The parser tries, by shifts and reductions, to reduce the entire
+input down to a single grouping whose symbol is the grammar's
+start-symbol (*note Languages and Context-Free Grammars: Language and
+Grammar.).
+
+   This kind of parser is known in the literature as a bottom-up parser.
+
+* Menu:
+
+* 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.
+
+
+File: bison.info,  Node: Look-Ahead,  Next: Shift/Reduce,  Up: Algorithm
+
+Look-Ahead Tokens
+=================
+
+   The Bison parser does _not_ always reduce immediately as soon as the
+last N tokens and groupings match a rule.  This is because such a
+simple strategy is inadequate to handle most languages.  Instead, when a
+reduction is possible, the parser sometimes "looks ahead" at the next
+token in order to decide what to do.
+
+   When a token is read, it is not immediately shifted; first it
+becomes the "look-ahead token", which is not on the stack.  Now the
+parser can perform one or more reductions of tokens and groupings on
+the stack, while the look-ahead token remains off to the side.  When no
+more reductions should take place, the look-ahead token is shifted onto
+the stack.  This does not mean that all possible reductions have been
+done; depending on the token type of the look-ahead token, some rules
+may choose to delay their application.
+
+   Here is a simple case where look-ahead is needed.  These three rules
+define expressions which contain binary addition operators and postfix
+unary factorial operators (`!'), and allow parentheses for grouping.
+
+     expr:     term '+' expr
+             | term
+             ;
+     
+     term:     '(' expr ')'
+             | term '!'
+             | NUMBER
+             ;
+
+   Suppose that the tokens `1 + 2' have been read and shifted; what
+should be done?  If the following token is `)', then the first three
+tokens must be reduced to form an `expr'.  This is the only valid
+course, because shifting the `)' would produce a sequence of symbols
+`term ')'', and no rule allows this.
+
+   If the following token is `!', then it must be shifted immediately so
+that `2 !' can be reduced to make a `term'.  If instead the parser were
+to reduce before shifting, `1 + 2' would become an `expr'.  It would
+then be impossible to shift the `!' because doing so would produce on
+the stack the sequence of symbols `expr '!''.  No rule allows that
+sequence.
+
+   The current look-ahead token is stored in the variable `yychar'.
+*Note Special Features for Use in Actions: Action Features.
+
+
+File: bison.info,  Node: Shift/Reduce,  Next: Precedence,  Prev: Look-Ahead,  Up: Algorithm
+
+Shift/Reduce Conflicts
+======================
+
+   Suppose we are parsing a language which has if-then and if-then-else
+statements, with a pair of rules like this:
+
+     if_stmt:
+               IF expr THEN stmt
+             | IF expr THEN stmt ELSE stmt
+             ;
+
+Here we assume that `IF', `THEN' and `ELSE' are terminal symbols for
+specific keyword tokens.
+
+   When the `ELSE' token is read and becomes the look-ahead token, the
+contents of the stack (assuming the input is valid) are just right for
+reduction by the first rule.  But it is also legitimate to shift the
+`ELSE', because that would lead to eventual reduction by the second
+rule.
+
+   This situation, where either a shift or a reduction would be valid,
+is called a "shift/reduce conflict".  Bison is designed to resolve
+these conflicts by choosing to shift, unless otherwise directed by
+operator precedence declarations.  To see the reason for this, let's
+contrast it with the other alternative.
+
+   Since the parser prefers to shift the `ELSE', the result is to attach
+the else-clause to the innermost if-statement, making these two inputs
+equivalent:
+
+     if x then if y then win (); else lose;
+     
+     if x then do; if y then win (); else lose; end;
+
+   But if the parser chose to reduce when possible rather than shift,
+the result would be to attach the else-clause to the outermost
+if-statement, making these two inputs equivalent:
+
+     if x then if y then win (); else lose;
+     
+     if x then do; if y then win (); end; else lose;
+
+   The conflict exists because the grammar as written is ambiguous:
+either parsing of the simple nested if-statement is legitimate.  The
+established convention is that these ambiguities are resolved by
+attaching the else-clause to the innermost if-statement; this is what
+Bison accomplishes by choosing to shift rather than reduce.  (It would
+ideally be cleaner to write an unambiguous grammar, but that is very
+hard to do in this case.)  This particular ambiguity was first
+encountered in the specifications of Algol 60 and is called the
+"dangling `else'" ambiguity.
+
+   To avoid warnings from Bison about predictable, legitimate
+shift/reduce conflicts, use the `%expect N' declaration.  There will be
+no warning as long as the number of shift/reduce conflicts is exactly N.
+*Note Suppressing Conflict Warnings: Expect Decl.
+
+   The definition of `if_stmt' above is solely to blame for the
+conflict, but the conflict does not actually appear without additional
+rules.  Here is a complete Bison input file that actually manifests the
+conflict:
+
+     %token IF THEN ELSE variable
+     %%
+     stmt:     expr
+             | if_stmt
+             ;
+     
+     if_stmt:
+               IF expr THEN stmt
+             | IF expr THEN stmt ELSE stmt
+             ;
+     
+     expr:     variable
+             ;
+
+
+File: bison.info,  Node: Precedence,  Next: Contextual Precedence,  Prev: Shift/Reduce,  Up: Algorithm
+
+Operator Precedence
+===================
+
+   Another situation where shift/reduce conflicts appear is in
+arithmetic expressions.  Here shifting is not always the preferred
+resolution; the Bison declarations for operator precedence allow you to
+specify when to shift and when to reduce.
+
+* Menu:
+
+* 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.
+
+
+File: bison.info,  Node: Why Precedence,  Next: Using Precedence,  Up: Precedence
+
+When Precedence is Needed
+-------------------------
+
+   Consider the following ambiguous grammar fragment (ambiguous because
+the input `1 - 2 * 3' can be parsed in two different ways):
+
+     expr:     expr '-' expr
+             | expr '*' expr
+             | expr '<' expr
+             | '(' expr ')'
+             ...
+             ;
+
+Suppose the parser has seen the tokens `1', `-' and `2'; should it
+reduce them via the rule for the addition operator?  It depends on the
+next token.  Of course, if the next token is `)', we must reduce;
+shifting is invalid because no single rule can reduce the token
+sequence `- 2 )' or anything starting with that.  But if the next token
+is `*' or `<', we have a choice: either shifting or reduction would
+allow the parse to complete, but with different results.
+
+   To decide which one Bison should do, we must consider the results.
+If the next operator token OP is shifted, then it must be reduced first
+in order to permit another opportunity to reduce the sum.  The result
+is (in effect) `1 - (2 OP 3)'.  On the other hand, if the subtraction
+is reduced before shifting OP, the result is `(1 - 2) OP 3'.  Clearly,
+then, the choice of shift or reduce should depend on the relative
+precedence of the operators `-' and OP: `*' should be shifted first,
+but not `<'.
+
+   What about input such as `1 - 2 - 5'; should this be `(1 - 2) - 5'
+or should it be `1 - (2 - 5)'?  For most operators we prefer the
+former, which is called "left association".  The latter alternative,
+"right association", is desirable for assignment operators.  The choice
+of left or right association is a matter of whether the parser chooses
+to shift or reduce when the stack contains `1 - 2' and the look-ahead
+token is `-': shifting makes right-associativity.
+
+
+File: bison.info,  Node: Using Precedence,  Next: Precedence Examples,  Prev: Why Precedence,  Up: Precedence
+
+Specifying Operator Precedence
+------------------------------
+
+   Bison allows you to specify these choices with the operator
+precedence declarations `%left' and `%right'.  Each such declaration
+contains a list of tokens, which are operators whose precedence and
+associativity is being declared.  The `%left' declaration makes all
+those operators left-associative and the `%right' declaration makes
+them right-associative.  A third alternative is `%nonassoc', which
+declares that it is a syntax error to find the same operator twice "in a
+row".
+
+   The relative precedence of different operators is controlled by the
+order in which they are declared.  The first `%left' or `%right'
+declaration in the file declares the operators whose precedence is
+lowest, the next such declaration declares the operators whose
+precedence is a little higher, and so on.
+
+
+File: bison.info,  Node: Precedence Examples,  Next: How Precedence,  Prev: Using Precedence,  Up: Precedence
+
+Precedence Examples
+-------------------
+
+   In our example, we would want the following declarations:
+
+     %left '<'
+     %left '-'
+     %left '*'
+
+   In a more complete example, which supports other operators as well,
+we would declare them in groups of equal precedence.  For example,
+`'+'' is declared with `'-'':
+
+     %left '<' '>' '=' NE LE GE
+     %left '+' '-'
+     %left '*' '/'
+
+(Here `NE' and so on stand for the operators for "not equal" and so on.
+We assume that these tokens are more than one character long and
+therefore are represented by names, not character literals.)
+