X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/08e49d20f0e9b356ab080d84577d9640e64bfd17..c732d2c6dc97b3c9fc66295469105bd294e88d75:/doc/bison.texinfo?ds=sidebyside diff --git a/doc/bison.texinfo b/doc/bison.texinfo index 866f7968..0d3ce7d5 100644 --- a/doc/bison.texinfo +++ b/doc/bison.texinfo @@ -5,9 +5,7 @@ @settitle Bison @value{VERSION} @setchapternewpage odd -@iftex @finalout -@end iftex @c SMALL BOOK version @c This edition has been formatted so that you can format and print it in @@ -23,6 +21,7 @@ @c Check COPYRIGHT dates. should be updated in the titlepage, ifinfo @c titlepage; should NOT be changed in the GPL. --mew +@c FIXME: I don't understand this `iftex'. Obsolete? --akim. @iftex @syncodeindex fn cp @syncodeindex vr cp @@ -154,7 +153,7 @@ Reference sections: * 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. +* Debugging:: Understanding or debugging Bison parsers. * 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. @@ -299,6 +298,11 @@ Handling Context Dependencies * Tie-in Recovery:: Lexical tie-ins have implications for how error recovery rules must be written. +Understanding or Debugging Your Parser + +* Understanding:: Understanding the structure of your parser. +* Tracing:: Tracing the execution of your parser. + Invoking Bison * Bison Options:: All the options described in detail, @@ -707,9 +711,9 @@ In some cases the Bison parser file includes system headers, and in those cases your code should respect the identifiers reserved by those headers. On some non-@sc{gnu} hosts, @code{}, @code{}, and @code{} are included as needed to -declare memory allocators and related types. -Other system headers may be included if you define @code{YYDEBUG} to a -nonzero value (@pxref{Debugging, ,Debugging Your Parser}). +declare memory allocators and related types. Other system headers may +be included if you define @code{YYDEBUG} to a nonzero value +(@pxref{Tracing, ,Tracing Your Parser}). @node Stages @section Stages in Using Bison @@ -2051,6 +2055,33 @@ that they precede the definition of @code{yyparse}. You can use need any C declarations, you may omit the @samp{%@{} and @samp{%@}} delimiters that bracket this section. +You may have more than one @var{Prologue} section, intermixed with the +@var{Bison declarations}. This allows you to have C and Bison +declarations that refer to each other. For example, the @code{%union} +declaration may use types defined in a header file, and you may wish to +prototype functions that take arguments of type @code{YYSTYPE}. This +can be done with two @var{Prologue} blocks, one before and one after the +@code{%union} declaration. + +@smallexample +%@{ +#include +#include "ptypes.h" +%@} + +%union @{ + long n; + tree t; /* @r{@code{tree} is defined in @file{ptypes.h}.} */ +@} + +%@{ +static void yyprint(FILE *, int, YYSTYPE); +#define YYPRINT(F, N, L) yyprint(F, N, L) +%@} + +@dots{} +@end smallexample + @node Bison Declarations @subsection The Bison Declarations Section @cindex Bison declarations (introduction) @@ -2351,14 +2382,14 @@ expseq1: exp @end example @noindent -Any kind of sequence can be defined using either left recursion or -right recursion, but you should always use left recursion, because it -can parse a sequence of any number of elements with bounded stack -space. Right recursion uses up space on the Bison stack in proportion -to the number of elements in the sequence, because all the elements -must be shifted onto the stack before the rule can be applied even -once. @xref{Algorithm, ,The Bison Parser Algorithm }, for -further explanation of this. +Any kind of sequence can be defined using either left recursion or right +recursion, but you should always use left recursion, because it can +parse a sequence of any number of elements with bounded stack space. +Right recursion uses up space on the Bison stack in proportion to the +number of elements in the sequence, because all the elements must be +shifted onto the stack before the rule can be applied even once. +@xref{Algorithm, ,The Bison Parser Algorithm}, for further explanation +of this. @cindex mutual recursion @dfn{Indirect} or @dfn{mutual} recursion occurs when the result of the @@ -2886,9 +2917,11 @@ By default, it is defined this way: @example @group -#define YYLLOC_DEFAULT(Current, Rhs, N) \ - Current.last_line = Rhs[N].last_line; \ - Current.last_column = Rhs[N].last_column; +#define YYLLOC_DEFAULT(Current, Rhs, N) \ + Current.first_line = Rhs[1].first_line; \ + Current.first_column = Rhs[1].first_column; \ + Current.last_line = Rhs[N].last_line; \ + Current.last_column = Rhs[N].last_column; @end group @end example @@ -2900,12 +2933,8 @@ All arguments are free of side-effects. However, only the first one (the result) should be modified by @code{YYLLOC_DEFAULT}. @item -Before @code{YYLLOC_DEFAULT} is executed, the output parser sets @code{@@$} -to @code{@@1}. - -@item -For consistency with semantic actions, valid indexes for the location array -range from 1 to @var{n}. +For consistency with semantic actions, valid indexes for the location +array range from 1 to @var{n}. @end itemize @node Declarations @@ -3278,7 +3307,7 @@ directives: @item %debug In the parser file, define the macro @code{YYDEBUG} to 1 if it is not already defined, so that the debugging facilities are compiled. -@xref{Debugging, ,Debugging Your Parser}. +@xref{Tracing, ,Tracing Your Parser}. @item %defines Write an extra output file containing macro definitions for the token @@ -3388,17 +3417,10 @@ The number of parser states (@pxref{Parser States}). @item %verbose Write an extra output file containing verbose descriptions of the parser states and what is done for each type of look-ahead token in -that state. +that state. @xref{Understanding, , Understanding Your Parser}, for more +information. -This file also describes all the conflicts, both those resolved by -operator precedence and the unresolved ones. -The file's name is made by removing @samp{.tab.c} or @samp{.c} from -the parser output file name, and adding @samp{.output} instead. - -Therefore, if the input file is @file{foo.y}, then the parser file is -called @file{foo.tab.c} by default. As a consequence, the verbose -output file is called @file{foo.output}. @item %yacc Pretend the option @option{--yacc} was given, i.e., imitate Yacc, @@ -4956,8 +4978,414 @@ make sure your error recovery rules are not of this kind. Each rule must be such that you can be sure that it always will, or always won't, have to clear the flag. +@c ================================================== Debugging Your Parser + @node Debugging @chapter Debugging Your Parser + +Developing a parser can be a challenge, especially if you don't +understand the algorithm (@pxref{Algorithm, ,The Bison Parser +Algorithm}). Even so, sometimes a detailed description of the automaton +can help (@pxref{Understanding, , Understanding Your Parser}), or +tracing the execution of the parser can give some insight on why it +behaves improperly (@pxref{Tracing, , Tracing Your Parser}). + +@menu +* Understanding:: Understanding the structure of your parser. +* Tracing:: Tracing the execution of your parser. +@end menu + +@node Understanding +@section Understanding Your Parser + +As documented elsewhere (@pxref{Algorithm, ,The Bison Parser Algorithm}) +Bison parsers are @dfn{shift/reduce automata}. In some cases (much more +frequent than one would hope), looking at this automaton is required to +tune or simply fix a parser. Bison provides two different +representation of it, either textually or graphically (as a @sc{vcg} +file). + +The textual file is generated when the options @option{--report} or +@option{--verbose} are specified, see @xref{Invocation, , Invoking +Bison}. Its name is made by removing @samp{.tab.c} or @samp{.c} from +the parser output file name, and adding @samp{.output} instead. +Therefore, if the input file is @file{foo.y}, then the parser file is +called @file{foo.tab.c} by default. As a consequence, the verbose +output file is called @file{foo.output}. + +The following grammar file, @file{calc.y}, will be used in the sequel: + +@example +%token NUM STR +%left '+' '-' +%left '*' +%% +exp: exp '+' exp + | exp '-' exp + | exp '*' exp + | exp '/' exp + | NUM + ; +useless: STR; +%% +@end example + +@command{bison} reports that @samp{calc.y contains 1 useless nonterminal +and 1 useless rule} and that @samp{calc.y contains 7 shift/reduce +conflicts}. When given @option{--report=state}, in addition to +@file{calc.tab.c}, it creates a file @file{calc.output} with contents +detailed below. The order of the output and the exact presentation +might vary, but the interpretation is the same. + +The first section includes details on conflicts that were solved thanks +to precedence and/or associativity: + +@example +Conflict in state 8 between rule 2 and token '+' resolved as reduce. +Conflict in state 8 between rule 2 and token '-' resolved as reduce. +Conflict in state 8 between rule 2 and token '*' resolved as shift. +@exdent @dots{} +@end example + +@noindent +The next section lists states that still have conflicts. + +@example +State 8 contains 1 shift/reduce conflict. +State 9 contains 1 shift/reduce conflict. +State 10 contains 1 shift/reduce conflict. +State 11 contains 4 shift/reduce conflicts. +@end example + +@noindent +@cindex token, useless +@cindex useless token +@cindex nonterminal, useless +@cindex useless nonterminal +@cindex rule, useless +@cindex useless rule +The next section reports useless tokens, nonterminal and rules. Useless +nonterminals and rules are removed in order to produce a smaller parser, +but useless tokens are preserved, since they might be used by the +scanner (note the difference between ``useless'' and ``not used'' +below): + +@example +Useless nonterminals: + useless + +Terminals which are not used: + STR + +Useless rules: +#6 useless: STR; +@end example + +@noindent +The next section reproduces the exact grammar that Bison used: + +@example +Grammar + + Number, Line, Rule + 0 5 $axiom -> exp $ + 1 5 exp -> exp '+' exp + 2 6 exp -> exp '-' exp + 3 7 exp -> exp '*' exp + 4 8 exp -> exp '/' exp + 5 9 exp -> NUM +@end example + +@noindent +and reports the uses of the symbols: + +@example +Terminals, with rules where they appear + +$ (0) 0 +'*' (42) 3 +'+' (43) 1 +'-' (45) 2 +'/' (47) 4 +error (256) +NUM (258) 5 + +Nonterminals, with rules where they appear + +$axiom (8) + on left: 0 +exp (9) + on left: 1 2 3 4 5, on right: 0 1 2 3 4 +@end example + +@noindent +@cindex item +@cindex pointed rule +@cindex rule, pointed +Bison then proceeds onto the automaton itself, describing each state +with it set of @dfn{items}, also known as @dfn{pointed rules}. Each +item is a production rule together with a point (marked by @samp{.}) +that the input cursor. + +@example +state 0 + + $axiom -> . exp $ (rule 0) + + NUM shift, and go to state 1 + + exp go to state 2 +@end example + +This reads as follows: ``state 0 corresponds to being at the very +beginning of the parsing, in the initial rule, right before the start +symbol (here, @code{exp}). When the parser returns to this state right +after having reduced a rule that produced an @code{exp}, the control +flow jumps to state 2. If there is no such transition on a nonterminal +symbol, and the lookahead is a @code{NUM}, then this token is shifted on +the parse stack, and the control flow jumps to state 1. Any other +lookahead triggers a parse error.'' + +@cindex core, item set +@cindex item set core +@cindex kernel, item set +@cindex item set core +Even though the only active rule in state 0 seems to be rule 0, the +report lists @code{NUM} as a lookahead symbol because @code{NUM} can be +at the beginning of any rule deriving an @code{exp}. By default Bison +reports the so-called @dfn{core} or @dfn{kernel} of the item set, but if +you want to see more detail you can invoke @command{bison} with +@option{--report=itemset} to list all the items, include those that can +be derived: + +@example +state 0 + + $axiom -> . exp $ (rule 0) + exp -> . exp '+' exp (rule 1) + exp -> . exp '-' exp (rule 2) + exp -> . exp '*' exp (rule 3) + exp -> . exp '/' exp (rule 4) + exp -> . NUM (rule 5) + + NUM shift, and go to state 1 + + exp go to state 2 +@end example + +@noindent +In the state 1... + +@example +state 1 + + exp -> NUM . (rule 5) + + $default reduce using rule 5 (exp) +@end example + +@noindent +the rule 5, @samp{exp: NUM;}, is completed. Whatever the lookahead +(@samp{$default}), the parser will reduce it. If it was coming from +state 0, then, after this reduction it will return to state 0, and will +jump to state 2 (@samp{exp: go to state 2}). + +@example +state 2 + + $axiom -> exp . $ (rule 0) + exp -> exp . '+' exp (rule 1) + exp -> exp . '-' exp (rule 2) + exp -> exp . '*' exp (rule 3) + exp -> exp . '/' exp (rule 4) + + $ shift, and go to state 3 + '+' shift, and go to state 4 + '-' shift, and go to state 5 + '*' shift, and go to state 6 + '/' shift, and go to state 7 +@end example + +@noindent +In state 2, the automaton can only shift a symbol. For instance, +because of the item @samp{exp -> exp . '+' exp}, if the lookahead if +@samp{+}, it will be shifted on the parse stack, and the automaton +control will jump to state 4, corresponding to the item @samp{exp -> exp +'+' . exp}. Since there is no default action, any other token than +those listed above will trigger a parse error. + +The state 3 is named the @dfn{final state}, or the @dfn{accepting +state}: + +@example +state 3 + + $axiom -> exp $ . (rule 0) + + $default accept +@end example + +@noindent +the initial rule is completed (the start symbol and the end +of input were read), the parsing exits successfully. + +The interpretation of states 4 to 7 is straightforward, and is left to +the reader. + +@example +state 4 + + exp -> exp '+' . exp (rule 1) + + NUM shift, and go to state 1 + + exp go to state 8 + +state 5 + + exp -> exp '-' . exp (rule 2) + + NUM shift, and go to state 1 + + exp go to state 9 + +state 6 + + exp -> exp '*' . exp (rule 3) + + NUM shift, and go to state 1 + + exp go to state 10 + +state 7 + + exp -> exp '/' . exp (rule 4) + + NUM shift, and go to state 1 + + exp go to state 11 +@end example + +As was announced in beginning of the report, @samp{State 8 contains 1 +shift/reduce conflict}: + +@example +state 8 + + exp -> exp . '+' exp (rule 1) + exp -> exp '+' exp . (rule 1) + exp -> exp . '-' exp (rule 2) + exp -> exp . '*' exp (rule 3) + exp -> exp . '/' exp (rule 4) + + '*' shift, and go to state 6 + '/' shift, and go to state 7 + + '/' [reduce using rule 1 (exp)] + $default reduce using rule 1 (exp) +@end example + +Indeed, there are two actions associated to the lookahead @samp{/}: +either shifting (and going to state 7), or reducing rule 1. The +conflict means that either the grammar is ambiguous, or the parser lacks +information to make the right decision. Indeed the grammar is +ambiguous, as, since we did not specify the precedence of @samp{/}, the +sentence @samp{NUM + NUM / NUM} can be parsed as @samp{NUM + (NUM / +NUM)}, which corresponds to shifting @samp{/}, or as @samp{(NUM + NUM) / +NUM}, which corresponds to reducing rule 1. + +Because in LALR(1) parsing a single decision can be made, Bison +arbitrarily chose to disable the reduction, see @ref{Shift/Reduce, , +Shift/Reduce Conflicts}. Discarded actions are reported in between +square brackets. + +Note that all the previous states had a single possible action: either +shifting the next token and going to the corresponding state, or +reducing a single rule. In the other cases, i.e., when shifting +@emph{and} reducing is possible or when @emph{several} reductions are +possible, the lookahead is required to select the action. State 8 is +one such state: if the lookahead is @samp{*} or @samp{/} then the action +is shifting, otherwise the action is reducing rule 1. In other words, +the first two items, corresponding to rule 1, are not eligible when the +lookahead is @samp{*}, since we specified that @samp{*} has higher +precedence that @samp{+}. More generally, some items are eligible only +with some set of possible lookaheads. When run with +@option{--report=lookahead}, Bison specifies these lookaheads: + +@example +state 8 + + exp -> exp . '+' exp [$, '+', '-', '/'] (rule 1) + exp -> exp '+' exp . [$, '+', '-', '/'] (rule 1) + exp -> exp . '-' exp (rule 2) + exp -> exp . '*' exp (rule 3) + exp -> exp . '/' exp (rule 4) + + '*' shift, and go to state 6 + '/' shift, and go to state 7 + + '/' [reduce using rule 1 (exp)] + $default reduce using rule 1 (exp) +@end example + +The remaining states are similar: + +@example +state 9 + + exp -> exp . '+' exp (rule 1) + exp -> exp . '-' exp (rule 2) + exp -> exp '-' exp . (rule 2) + exp -> exp . '*' exp (rule 3) + exp -> exp . '/' exp (rule 4) + + '*' shift, and go to state 6 + '/' shift, and go to state 7 + + '/' [reduce using rule 2 (exp)] + $default reduce using rule 2 (exp) + +state 10 + + exp -> exp . '+' exp (rule 1) + exp -> exp . '-' exp (rule 2) + exp -> exp . '*' exp (rule 3) + exp -> exp '*' exp . (rule 3) + exp -> exp . '/' exp (rule 4) + + '/' shift, and go to state 7 + + '/' [reduce using rule 3 (exp)] + $default reduce using rule 3 (exp) + +state 11 + + exp -> exp . '+' exp (rule 1) + exp -> exp . '-' exp (rule 2) + exp -> exp . '*' exp (rule 3) + exp -> exp . '/' exp (rule 4) + exp -> exp '/' exp . (rule 4) + + '+' shift, and go to state 4 + '-' shift, and go to state 5 + '*' shift, and go to state 6 + '/' shift, and go to state 7 + + '+' [reduce using rule 4 (exp)] + '-' [reduce using rule 4 (exp)] + '*' [reduce using rule 4 (exp)] + '/' [reduce using rule 4 (exp)] + $default reduce using rule 4 (exp) +@end example + +@noindent +Observe that state 11 contains conflicts due to the lack of precedence +of @samp{/} wrt @samp{+}, @samp{-}, and @samp{*}, but also because the +associativity of @samp{/} is not specified. + + +@node Tracing +@section Tracing Your Parser @findex yydebug @cindex debugging @cindex tracing the parser @@ -5061,6 +5489,8 @@ yyprint (FILE *file, int type, YYSTYPE value) @} @end smallexample +@c ================================================= Invoking Bison + @node Invocation @chapter Invoking Bison @cindex invoking Bison @@ -5160,7 +5590,7 @@ you are developing Bison. @itemx --debug In the parser file, define the macro @code{YYDEBUG} to 1 if it is not already defined, so that the debugging facilities are compiled. -@xref{Debugging, ,Debugging Your Parser}. +@xref{Tracing, ,Tracing Your Parser}. @item --locations Pretend that @code{%locations} was specified. @xref{Decl Summary}. @@ -5206,6 +5636,27 @@ Same as above, but save in the file @var{defines-file}. Pretend that @code{%verbose} was specified, i.e, specify prefix to use for all Bison output file names. @xref{Decl Summary}. +@item -r @var{things} +@itemx --report=@var{things} +Write an extra output file containing verbose description of the comma +separated list of @var{things} among: + +@table @code +@item state +Description of the grammar, conflicts (resolved and unresolved), and +LALR automaton. + +@item lookahead +Implies @code{state} and augments the description of the automaton with +each rule's lookahead set. + +@item itemset +Implies @code{state} and augments the description of the automaton with +the full set of items for each state, instead of its core only. +@end table + +For instance, on the following grammar + @item -v @itemx --verbose Pretend that @code{%verbose} was specified, i.e, write an extra output @@ -5233,7 +5684,6 @@ the output graph filename. @node Environment Variables @section Environment Variables @cindex environment variables -@cindex BISON_HAIRY @cindex BISON_SIMPLE Here is a list of environment variables which affect the way Bison @@ -5241,18 +5691,11 @@ runs. @table @samp @item BISON_SIMPLE -@itemx BISON_HAIRY Much of the parser generated by Bison is copied verbatim from a file called @file{bison.simple}. If Bison cannot find that file, or if you would like to direct Bison to use a different copy, setting the environment variable @code{BISON_SIMPLE} to the path of the file will cause Bison to use that copy instead. - -When the @samp{%semantic-parser} declaration is used, Bison copies from -a file called @file{bison.hairy} instead. The location of this file can -also be specified or overridden in a similar fashion, with the -@code{BISON_HAIRY} environment variable. - @end table @node Option Cross Key @@ -5375,8 +5818,8 @@ Macro to discard a value from the parser stack and fake a look-ahead token. @xref{Action Features, ,Special Features for Use in Actions}. @item YYDEBUG -Macro to define to equip the parser with tracing code. @xref{Debugging, -,Debugging Your Parser}. +Macro to define to equip the parser with tracing code. @xref{Tracing, +,Tracing Your Parser}. @item YYERROR Macro to pretend that a syntax error has just been detected: call @@ -5440,7 +5883,7 @@ look-ahead token. @xref{Error Recovery}. @item yydebug External integer variable set to zero by default. If @code{yydebug} is given a nonzero value, the parser will output information on input -symbols and parser action. @xref{Debugging, ,Debugging Your Parser}. +symbols and parser action. @xref{Tracing, ,Tracing Your Parser}. @item yyerrok Macro to cause parser to recover immediately to its normal mode