home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 4 / FreshFish_May-June1994.bin / gnu / info / bison.info-3 (.txt) < prev    next >
GNU Info File  |  1994-02-21  |  51KB  |  982 lines
  1. This is Info file bison.info, produced by Makeinfo-1.54 from the input
  2. file /home/gd2/gnu/bison/bison.texinfo.
  3.    This file documents the Bison parser generator.
  4.    Copyright (C) 1988, 1989, 1990, 1991, 1992 Free Software Foundation,
  5.    Permission is granted to make and distribute verbatim copies of this
  6. manual provided the copyright notice and this permission notice are
  7. preserved on all copies.
  8.    Permission is granted to copy and distribute modified versions of
  9. this manual under the conditions for verbatim copying, provided also
  10. that the sections entitled "GNU General Public License" and "Conditions
  11. for Using Bison" are included exactly as in the original, and provided
  12. that the entire resulting derived work is distributed under the terms
  13. of a permission notice identical to this one.
  14.    Permission is granted to copy and distribute translations of this
  15. manual into another language, under the above conditions for modified
  16. versions, except that the sections entitled "GNU General Public
  17. License", "Conditions for Using Bison" and this permission notice may be
  18. included in translations approved by the Free Software Foundation
  19. instead of in the original English.
  20. File: bison.info,  Node: Mid-Rule Actions,  Prev: Action Types,  Up: Semantics
  21. Actions in Mid-Rule
  22. -------------------
  23.    Occasionally it is useful to put an action in the middle of a rule.
  24. These actions are written just like usual end-of-rule actions, but they
  25. are executed before the parser even recognizes the following components.
  26.    A mid-rule action may refer to the components preceding it using
  27. `$N', but it may not refer to subsequent components because it is run
  28. before they are parsed.
  29.    The mid-rule action itself counts as one of the components of the
  30. rule.  This makes a difference when there is another action later in
  31. the same rule (and usually there is another at the end): you have to
  32. count the actions along with the symbols when working out which number
  33. N to use in `$N'.
  34.    The mid-rule action can also have a semantic value.  The action can
  35. set its value with an assignment to `$$', and actions later in the rule
  36. can refer to the value using `$N'.  Since there is no symbol to name
  37. the action, there is no way to declare a data type for the value in
  38. advance, so you must use the `$<...>' construct to specify a data type
  39. each time you refer to this value.
  40.    There is no way to set the value of the entire rule with a mid-rule
  41. action, because assignments to `$$' do not have that effect.  The only
  42. way to set the value for the entire rule is with an ordinary action at
  43. the end of the rule.
  44.    Here is an example from a hypothetical compiler, handling a `let'
  45. statement that looks like `let (VARIABLE) STATEMENT' and serves to
  46. create a variable named VARIABLE temporarily for the duration of
  47. STATEMENT.  To parse this construct, we must put VARIABLE into the
  48. symbol table while STATEMENT is parsed, then remove it afterward.  Here
  49. is how it is done:
  50.      stmt:   LET '(' var ')'
  51.                      { $<context>$ = push_context ();
  52.                        declare_variable ($3); }
  53.              stmt    { $$ = $6;
  54.                        pop_context ($<context>5); }
  55. As soon as `let (VARIABLE)' has been recognized, the first action is
  56. run.  It saves a copy of the current semantic context (the list of
  57. accessible variables) as its semantic value, using alternative
  58. `context' in the data-type union.  Then it calls `declare_variable' to
  59. add the new variable to that list.  Once the first action is finished,
  60. the embedded statement `stmt' can be parsed.  Note that the mid-rule
  61. action is component number 5, so the `stmt' is component number 6.
  62.    After the embedded statement is parsed, its semantic value becomes
  63. the value of the entire `let'-statement.  Then the semantic value from
  64. the earlier action is used to restore the prior list of variables.  This
  65. removes the temporary `let'-variable from the list so that it won't
  66. appear to exist while the rest of the program is parsed.
  67.    Taking action before a rule is completely recognized often leads to
  68. conflicts since the parser must commit to a parse in order to execute
  69. the action.  For example, the following two rules, without mid-rule
  70. actions, can coexist in a working parser because the parser can shift
  71. the open-brace token and look at what follows before deciding whether
  72. there is a declaration or not:
  73.      compound: '{' declarations statements '}'
  74.              | '{' statements '}'
  75.              ;
  76. But when we add a mid-rule action as follows, the rules become
  77. nonfunctional:
  78.      compound: { prepare_for_local_variables (); }
  79.                '{' declarations statements '}'
  80.              | '{' statements '}'
  81.              ;
  82. Now the parser is forced to decide whether to run the mid-rule action
  83. when it has read no farther than the open-brace.  In other words, it
  84. must commit to using one rule or the other, without sufficient
  85. information to do it correctly.  (The open-brace token is what is called
  86. the "look-ahead" token at this time, since the parser is still deciding
  87. what to do about it.  *Note Look-Ahead Tokens: Look-Ahead.)
  88.    You might think that you could correct the problem by putting
  89. identical actions into the two rules, like this:
  90.      compound: { prepare_for_local_variables (); }
  91.                '{' declarations statements '}'
  92.              | { prepare_for_local_variables (); }
  93.                '{' statements '}'
  94.              ;
  95. But this does not help, because Bison does not realize that the two
  96. actions are identical.  (Bison never tries to understand the C code in
  97. an action.)
  98.    If the grammar is such that a declaration can be distinguished from a
  99. statement by the first token (which is true in C), then one solution
  100. which does work is to put the action after the open-brace, like this:
  101.      compound: '{' { prepare_for_local_variables (); }
  102.                declarations statements '}'
  103.              | '{' statements '}'
  104.              ;
  105. Now the first token of the following declaration or statement, which
  106. would in any case tell Bison which rule to use, can still do so.
  107.    Another solution is to bury the action inside a nonterminal symbol
  108. which serves as a subroutine:
  109.      subroutine: /* empty */
  110.                { prepare_for_local_variables (); }
  111.              ;
  112.      
  113.      compound: subroutine
  114.                '{' declarations statements '}'
  115.              | subroutine
  116.                '{' statements '}'
  117.              ;
  118. Now Bison can execute the action in the rule for `subroutine' without
  119. deciding which rule for `compound' it will eventually use.  Note that
  120. the action is now at the end of its rule.  Any mid-rule action can be
  121. converted to an end-of-rule action in this way, and this is what Bison
  122. actually does to implement mid-rule actions.
  123. File: bison.info,  Node: Declarations,  Next: Multiple Parsers,  Prev: Semantics,  Up: Grammar File
  124. Bison Declarations
  125. ==================
  126.    The "Bison declarations" section of a Bison grammar defines the
  127. symbols used in formulating the grammar and the data types of semantic
  128. values.  *Note Symbols::.
  129.    All token type names (but not single-character literal tokens such as
  130. `'+'' and `'*'') must be declared.  Nonterminal symbols must be
  131. declared if you need to specify which data type to use for the semantic
  132. value (*note More Than One Value Type: Multiple Types.).
  133.    The first rule in the file also specifies the start symbol, by
  134. default.  If you want some other symbol to be the start symbol, you
  135. must declare it explicitly (*note Languages and Context-Free Grammars:
  136. Language and Grammar.).
  137. * Menu:
  138. * Token Decl::        Declaring terminal symbols.
  139. * Precedence Decl::   Declaring terminals with precedence and associativity.
  140. * Union Decl::        Declaring the set of all semantic value types.
  141. * Type Decl::         Declaring the choice of type for a nonterminal symbol.
  142. * Expect Decl::       Suppressing warnings about shift/reduce conflicts.
  143. * Start Decl::        Specifying the start symbol.
  144. * Pure Decl::         Requesting a reentrant parser.
  145. * Decl Summary::      Table of all Bison declarations.
  146. File: bison.info,  Node: Token Decl,  Next: Precedence Decl,  Up: Declarations
  147. Token Type Names
  148. ----------------
  149.    The basic way to declare a token type name (termin