home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 4 / FreshFish_May-June1994.bin / gnu / info / bison.info-2 (.txt) < prev    next >
GNU Info File  |  1994-02-21  |  48KB  |  1,024 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: Rpcalc Rules,  Next: Rpcalc Lexer,  Prev: Rpcalc Decls,  Up: RPN Calc
  21. Grammar Rules for `rpcalc'
  22. --------------------------
  23.    Here are the grammar rules for the reverse polish notation
  24. calculator.
  25.      input:    /* empty */
  26.              | input line
  27.      ;
  28.      
  29.      line:     '\n'
  30.              | exp '\n'  { printf ("\t%.10g\n", $1); }
  31.      ;
  32.      
  33.      exp:      NUM             { $$ = $1;         }
  34.              | exp exp '+'     { $$ = $1 + $2;    }
  35.              | exp exp '-'     { $$ = $1 - $2;    }
  36.              | exp exp '*'     { $$ = $1 * $2;    }
  37.              | exp exp '/'     { $$ = $1 / $2;    }
  38.            /* Exponentiation */
  39.              | exp exp '^'     { $$ = pow ($1, $2); }
  40.            /* Unary minus    */
  41.              | exp 'n'         { $$ = -$1;        }
  42.      ;
  43.      %%
  44.    The groupings of the rpcalc "language" defined here are the
  45. expression (given the name `exp'), the line of input (`line'), and the
  46. complete input transcript (`input').  Each of these nonterminal symbols
  47. has several alternate rules, joined by the `|' punctuator which is read
  48. as "or".  The following sections explain what these rules mean.
  49.    The semantics of the language is determined by the actions taken
  50. when a grouping is recognized.  The actions are the C code that appears
  51. inside braces.  *Note Actions::.
  52.    You must specify these actions in C, but Bison provides the means for
  53. passing semantic values between the rules.  In each action, the
  54. pseudo-variable `$$' stands for the semantic value for the grouping
  55. that the rule is going to construct.  Assigning a value to `$$' is the
  56. main job of most actions.  The semantic values of the components of the
  57. rule are referred to as `$1', `$2', and so on.
  58. * Menu:
  59. * Rpcalc Input::
  60. * Rpcalc Line::
  61. * Rpcalc Expr::
  62. File: bison.info,  Node: Rpcalc Input,  Next: Rpcalc Line,  Up: Rpcalc Rules
  63. Explanation of `input'
  64. ......................
  65.    Consider the definition of `input':
  66.      input:    /* empty */
  67.              | input line
  68.      ;
  69.    This definition reads as follows: "A complete input is either an
  70. empty string, or a complete input followed by an input line".  Notice
  71. that "complete input" is defined in terms of itself.  This definition
  72. is said to be "left recursive" since `input' appears always as the
  73. leftmost symbol in the sequence.  *Note Recursive Rules: Recursion.
  74.    The first alternative is empty because there are no symbols between
  75. the colon and the first `|'; this means that `input' can match an empty
  76. string of input (no tokens).  We write the rules this way because it is
  77. legitimate to type `Ctrl-d' right after you start the calculator.  It's
  78. conventional to put an empty alternative first and write the comment
  79. `/* empty */' in it.
  80.    The second alternate rule (`input line') handles all nontrivial
  81. input.  It means, "After reading any number of lines, read one more
  82. line if possible."  The left recursion makes this rule into a loop.
  83. Since the first alternative matches empty input, the loop can be
  84. executed zero or more times.
  85.    The parser function `yyparse' continues to process input until a
  86. grammatical error is seen or the lexical analyzer says there are no more
  87. input tokens; we will arrange for the latter to happen at end of file.
  88. File: bison.info,  Node: Rpcalc Line,  Next: Rpcalc Expr,  Prev: Rpcalc Input,  Up: Rpcalc Rules
  89. Explanation of `line'
  90. .....................
  91.    Now consider the definition of `line':
  92.      line:     '\n'
  93.              | exp '\n'  { printf ("\t%.10g\n", $1); }
  94.      ;
  95.    The first alternative is a token which is a newline character; this
  96. means that rpcalc accepts a blank line (and ignores it, since there is
  97. no action).  The second alternative is an expression followed by a
  98. newline.  This is the alternative that makes rpcalc useful.  The
  99. semantic value of the `exp' grouping is the value of `$1' because the
  100. `exp' in question is the first symbol in the alternative.  The action
  101. prints this value, which is the result of the computation the user
  102. asked for.
  103.    This action is unusual because it does not assign a value to `$$'.
  104. As a consequence, the semantic value associated with the `line' is
  105. uninitialized (its value will be unpredictable).  This would be a bug if
  106. that value were ever used, but we don't use it: once rpcalc has printed
  107. the value of the user's input line, that value is no longer needed.
  108. File: bison.info,  Node: Rpcalc Expr,  Prev: Rpcalc Line,  Up: Rpcalc Rules
  109. Explanation of `expr'
  110. .....................
  111.    The `exp' grouping has several rules, one for each kind of
  112. expression.  The first rule handles the simplest expressions: those
  113. that are just numbers.  The second handles an addition-expression,
  114. which looks like two expressions followed by a plus-sign.  The third
  115. handles subtraction, and so on.
  116.      exp:      NUM
  117.              | exp exp '+'     { $$ = $1 + $2;    }
  118.              | exp exp '-'     { $$ = $1 - $2;    }
  119.              ...
  120.              ;
  121.    We have used `|' to join all the rules for `exp', but we could
  122. equally well have written them separately:
  123.      exp:      NUM ;
  124.      exp:      exp exp '+'     { $$ = $1 + $2;    } ;
  125.      exp:      exp exp '-'     { $$ = $1 - $2;    } ;
  126.              ...
  127.    Most of the rules have actions that compute the value of the
  128. expression in terms of the value of its parts.  For example, in the
  129. rule for addition, `$1' refers to the first component `exp' and `$2'
  130. refers to the second one.  The third component, `'+'', has no meaningful
  131. associated semantic value, but if it had one you could refer to it as
  132. `$3'.  When `yyparse' recognizes a sum expression using this rule, the
  133. sum of the two subexpressions' values is produced as the value of the
  134. entire expression.  *Note Actions::.
  135.    You don't have to give an action for every rule.  When a rule has no
  136. action, Bison by default copies the value of `$1' into `$$'.  This is
  137. what happens in the first rule (the one that uses `NUM').
  138.    The formatting shown here is the recommended convention, but Bison
  139. does not require it.  You can add or change whitespace as much as you
  140. wish.  For example, this:
  141.      exp   : NUM | exp exp '+' {$$ = $1 + $2; } | ...
  142. means the same thing as this:
  143.      exp:      NUM
  144.              | exp exp '+'    { $$ = $1 + $2; }
  145.              | ...
  146. The latter, however, is much more readable.
  147. File: bison.info,  Node: Rpcalc Lexer,  Next: Rpcalc Main,  Prev: Rpcalc Rules,  Up: RPN Calc
  148. The `rpcalc' Lexical Analyzer
  149. -----------------------------
  150.    The lexical analyzer's job is low-level parsing: converting
  151. characters or sequences of characters into tokens.  The Bison parser
  152. gets its tokens by calling the lexical analyzer.  *Note The Lexical
  153. Analyzer Function `yylex': Lexical.
  154.    Only a simple lexical analyzer is needed for the RPN calculator.
  155. This lexical analyzer skips blanks and tabs, then reads in numbers as
  156. `double' and returns them as `NUM' tokens.  Any other character that
  157. isn't part of a number is a separate token.  Note that the token-code
  158. for such a single-character token is the character itself.
  159.    The return v