home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 4 / FreshFish_May-June1994.bin / gnu / info / bison.info-4 (.txt) < prev    next >
GNU Info File  |  1994-02-21  |  51KB  |  1,007 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: Mystery Conflicts,  Next: Stack Overflow,  Prev: Reduce/Reduce,  Up: Algorithm
  21. Mysterious Reduce/Reduce Conflicts
  22. ==================================
  23.    Sometimes reduce/reduce conflicts can occur that don't look
  24. warranted.  Here is an example:
  25.      %token ID
  26.      
  27.      %%
  28.      def:    param_spec return_spec ','
  29.              ;
  30.      param_spec:
  31.                   type
  32.              |    name_list ':' type
  33.              ;
  34.      return_spec:
  35.                   type
  36.              |    name ':' type
  37.              ;
  38.      type:        ID
  39.              ;
  40.      name:        ID
  41.              ;
  42.      name_list:
  43.                   name
  44.              |    name ',' name_list
  45.              ;
  46.    It would seem that this grammar can be parsed with only a single
  47. token of look-ahead: when a `param_spec' is being read, an `ID' is a
  48. `name' if a comma or colon follows, or a `type' if another `ID'
  49. follows.  In other words, this grammar is LR(1).
  50.    However, Bison, like most parser generators, cannot actually handle
  51. all LR(1) grammars.  In this grammar, two contexts, that after an `ID'
  52. at the beginning of a `param_spec' and likewise at the beginning of a
  53. `return_spec', are similar enough that Bison assumes they are the same.
  54. They appear similar because the same set of rules would be active--the
  55. rule for reducing to a `name' and that for reducing to a `type'.  Bison
  56. is unable to determine at that stage of processing that the rules would
  57. require different look-ahead tokens in the two contexts, so it makes a
  58. single parser state for them both.  Combining the two contexts causes a
  59. conflict later.  In parser terminology, this occurrence means that the
  60. grammar is not LALR(1).
  61.    In general, it is better to fix deficiencies than to document them.
  62. But this particular deficiency is intrinsically hard to fix; parser
  63. generators that can handle LR(1) grammars are hard to write and tend to
  64. produce parsers that are very large.  In practice, Bison is more useful
  65. as it is now.
  66.    When the problem arises, you can often fix it by identifying the two
  67. parser states that are being confused, and adding something to make them
  68. look distinct.  In the above example, adding one rule to `return_spec'
  69. as follows makes the problem go away:
  70.      %token BOGUS
  71.      ...
  72.      %%
  73.      ...
  74.      return_spec:
  75.                   type
  76.              |    name ':' type
  77.              /* This rule is never used.  */
  78.              |    ID BOGUS
  79.              ;
  80.    This corrects the problem because it introduces the possibility of an
  81. additional active rule in the context after the `ID' at the beginning of
  82. `return_spec'.  This rule is not active in the corresponding context in
  83. a `param_spec', so the two contexts receive distinct parser states.  As
  84. long as the token `BOGUS' is never generated by `yylex', the added rule
  85. cannot alter the way actual input is parsed.
  86.    In this particular example, there is another way to solve the
  87. problem: rewrite the rule for `return_spec' to use `ID' directly
  88. instead of via `name'.  This also causes the two confusing contexts to
  89. have different sets of active rules, because the one for `return_spec'
  90. activates the altered rule for `return_spec' rather than the one for
  91. `name'.
  92.      param_spec:
  93.                   type
  94.              |    name_list ':' type
  95.              ;
  96.      return_spec:
  97.                   type
  98.              |    ID ':' type
  99.              ;
  100. File: bison.info,  Node: Stack Overflow,  Prev: Mystery Conflicts,  Up: Algorithm
  101. Stack Overflow, and How to Avoid It
  102. ===================================
  103.    The Bison parser stack can overflow if too many tokens are shifted
  104. and not reduced.  When this happens, the parser function `yyparse'
  105. returns a nonzero value, pausing only to call `yyerror' to report the
  106. overflow.
  107.    By defining the macro `YYMAXDEPTH', you can control how deep the
  108. parser stack can become before a stack overflow occurs.  Define the
  109. macro with a value that is an integer.  This value is the maximum number
  110. of tokens that can be shifted (and not reduced) before overflow.  It
  111. must be a constant expression whose value is known at compile time.
  112.    The stack space allowed is not necessarily allocated.  If you
  113. specify a large value for `YYMAXDEPTH', the parser actually allocates a
  114. small stack at first, and then makes it bigger by stages as needed.
  115. This increasing allocation happens automatically and silently.
  116. Therefore, you do not need to make `YYMAXDEPTH' painfully small merely
  117. to save space for ordinary inputs that do not need much stack.
  118.    The default value of `YYMAXDEPTH', if you do not define it, is 10000.
  119.    You can control how much stack is allocated initially by defining the
  120. macro `YYINITDEPTH'.  This value too must be a compile-time constant
  121. integer.  The default is 200.
  122. File: bison.info,  Node: Error Recovery,  Next: Context Dependency,  Prev: Algorithm,  Up: Top
  123. Error Recovery
  124. **************
  125.    It is not usually acceptable to have a program terminate on a parse
  126. error.  For example, a compiler should recover sufficiently to parse the
  127. rest of the input file and check it for errors; a calculator should
  128. accept another expression.
  129.    In a simple interactive command parser where each input is one line,
  130. it may be sufficient to allow `yyparse' to return 1 on error and have
  131. the caller ignore the rest of the input line when that happens (and
  132. then call `yyparse' again).  But this is inadequate for a compiler,
  133. because it forgets all the syntactic context leading up to the error.
  134. A syntax error deep within a function in the compiler input should not
  135. cause the compiler to treat the following line like the beginning of a
  136. source file.
  137.    You can define how to recover from a syntax error by writing rules to
  138. recognize the special token `error'.  This is a terminal symbol that is
  139. always defined (you need not declare it) and reserved for error
  140. handling.  The Bison parser generates an `error' token whenever a
  141. syntax error happens; if you have provided a rule to recognize this
  142. token in the current context, the parse can continue.
  143.    For example:
  144.      stmnts:  /* empty string */
  145.              | stmnts '\n'
  146.              | stmnts exp '\n'
  147.              | stmnts error '\n'
  148.    The fourth rule in this example says that an error followed by a
  149. newline makes a valid addition to any `stmnts'.
  150.    What happens if a syntax error occurs in the middle of an `exp'?  The
  151. error recovery rule, interpreted strictly, applies to the precise
  152. sequence of a `stmnts', an `error' and a newline.  If an error occurs in
  153. the middle of an `exp', there will probably be some additional tokens
  154. and subexpressions on the stack after the last `stmnts', and there will
  155. be tokens to read before the next newline.  So the rule is not
  156. applicable in the ordinary way.
  157.    But Bison can force the situation to fit the rule, by discarding
  158. part of the semantic context and part of the input.  First it discards
  159. states and objects from the stack until it gets back to a state in
  160. which the `error' token is acceptable.  (This means that the
  161. subexpressions already parsed are discarded, b