X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/fef4cb511e07b026e31b2791c3998515bd36bb0e..5c9be03d6d7ccc5c8ad2ca47e8e767b37a3708b1:/doc/bison.texinfo diff --git a/doc/bison.texinfo b/doc/bison.texinfo index 9332050e..c1dcbd26 100644 --- a/doc/bison.texinfo +++ b/doc/bison.texinfo @@ -16,6 +16,10 @@ @c @clear shorttitlepage-enabled @c @set shorttitlepage-enabled +@c Set following if you want to document %default-prec and %no-default-prec. +@c This feature is experimental and may change in future Bison versions. +@c @set defaultprec + @c ISPELL CHECK: done, 14 Jan 1993 --bob @c Check COPYRIGHT dates. should be updated in the titlepage, ifinfo @@ -39,8 +43,8 @@ This manual is for @acronym{GNU} Bison (version @value{VERSION}, @value{UPDATED}), the @acronym{GNU} parser generator. -Copyright @copyright{} 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998, 2003, -1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc. +Copyright @copyright{} 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998, +1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc. @quotation Permission is granted to copy, distribute and/or modify this document @@ -219,7 +223,7 @@ Bison Declarations * Union Decl:: Declaring the set of all semantic value types. * Type Decl:: Declaring the choice of type for a nonterminal symbol. * Destructor Decl:: Declaring how symbols are freed. -* Expect Decl:: Suppressing warnings about shift/reduce conflicts. +* Expect Decl:: Suppressing warnings about parsing conflicts. * Start Decl:: Specifying the start symbol. * Pure Decl:: Requesting a reentrant parser. * Decl Summary:: Table of all Bison declarations. @@ -284,7 +288,10 @@ Invoking Bison Frequently Asked Questions * Parser Stack Overflow:: Breaking the Stack Limits +* How Can I Reset the Parser:: @code{yyparse} Keeps some State * Strings are Destroyed:: @code{yylval} Loses Track of Strings +* C++ Parsers:: Compiling Parsers with C++ Compilers +* Implementing Loops:: Control Flow in the Calculator Copying This Manual @@ -349,7 +356,7 @@ encourage people to make other software free. So we decided to make the practical conditions for using Bison match the practical conditions for using the other @acronym{GNU} tools. -This exception applies only when Bison is generating C code for a +This exception applies only when Bison is generating C code for an @acronym{LALR}(1) parser; otherwise, the @acronym{GPL} terms operate as usual. You can tell whether the exception applies to your @samp{.c} output file by @@ -1412,7 +1419,7 @@ here is the definition we will use: void yyerror (char const *s) @{ - printf ("%s\n", s); + fprintf (stderr, "%s\n", s); @} @end group @end example @@ -2331,7 +2338,7 @@ can be done with two @var{Prologue} blocks, one before and one after the %@} %union @{ - long n; + long int n; tree t; /* @r{@code{tree} is defined in @file{ptypes.h}.} */ @} @@ -2474,7 +2481,8 @@ does not enforce this convention, but if you depart from it, people who read your program will be confused. All the escape sequences used in string literals in C can be used in -Bison as well. However, unlike Standard C, trigraphs have no special +Bison as well, except that you must not use a null character within a +string literal. Also, unlike Standard C, trigraphs have no special meaning in Bison string literals, nor is backslash-newline allowed. A literal string token must contain two or more characters; for a token containing just one character, use a character token (see above). @@ -2747,7 +2755,7 @@ This macro definition must go in the prologue of the grammar file In most programs, you will need different data types for different kinds of tokens and groupings. For example, a numeric constant may need type -@code{int} or @code{long}, while a string constant needs type @code{char *}, +@code{int} or @code{long int}, while a string constant needs type @code{char *}, and an identifier might need a pointer to an entry in the symbol table. To use more than one data type for semantic values in one parser, Bison @@ -2794,9 +2802,10 @@ Actions, ,Actions in Mid-Rule}). The C code in an action can refer to the semantic values of the components matched by the rule with the construct @code{$@var{n}}, which stands for the value of the @var{n}th component. The semantic value for the grouping -being constructed is @code{$$}. (Bison translates both of these constructs -into array element references when it copies the actions into the parser -file.) +being constructed is @code{$$}. Bison translates both of these +constructs into expressions of the appropriate type when it copies the +actions into the parser file. @code{$$} is translated to a modifiable +lvalue, so it can be assigned to. Here is a typical example: @@ -3079,8 +3088,6 @@ Though grammar rules and semantic actions are enough to write a fully functional parser, it can be useful to process some additional information, especially symbol locations. -@c (terminal or not) ? - The way locations are handled is defined by providing a data type, and actions to take when rules are matched. @@ -3145,9 +3152,10 @@ exp: @dots{} else @{ $$ = 1; - printf("Division by zero, l%d,c%d-l%d,c%d", - @@3.first_line, @@3.first_column, - @@3.last_line, @@3.last_column); + fprintf (stderr, + "Division by zero, l%d,c%d-l%d,c%d", + @@3.first_line, @@3.first_column, + @@3.last_line, @@3.last_column); @} @} @end group @@ -3171,9 +3179,10 @@ exp: @dots{} else @{ $$ = 1; - printf("Division by zero, l%d,c%d-l%d,c%d", - @@3.first_line, @@3.first_column, - @@3.last_line, @@3.last_column); + fprintf (stderr, + "Division by zero, l%d,c%d-l%d,c%d", + @@3.first_line, @@3.first_column, + @@3.last_line, @@3.last_column); @} @} @end group @@ -3207,11 +3216,11 @@ By default, @code{YYLLOC_DEFAULT} is defined this way for simple @example @group -#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; +# 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 @@ -3220,11 +3229,11 @@ and like this for @acronym{GLR} parsers: @example @group -#define YYLLOC_DEFAULT(Current, Rhs, N) \ - Current.first_line = YYRHSLOC(Rhs,1).first_line; \ - Current.first_column = YYRHSLOC(Rhs,1).first_column; \ - Current.last_line = YYRHSLOC(Rhs,N).last_line; \ - Current.last_column = YYRHSLOC(Rhs,N).last_column; +# define YYLLOC_DEFAULT(yyCurrent, yyRhs, YYN) \ + ((yyCurrent).first_line = YYRHSLOC(yyRhs, 1).first_line, \ + (yyCurrent).first_column = YYRHSLOC(yyRhs, 1).first_column, \ + (yyCurrent).last_line = YYRHSLOC(yyRhs, YYN).last_line, \ + (yyCurrent).last_column = YYRHSLOC(yyRhs, YYN).last_column) @end group @end example @@ -3238,6 +3247,12 @@ result) should be modified by @code{YYLLOC_DEFAULT}. @item For consistency with semantic actions, valid indexes for the location array range from 1 to @var{n}. + +@item +Your macro should parenthesize its arguments, if need be, since the +actual arguments may not be surrounded by parentheses. Also, your +macro should expand to something that can be used as a single +statement when it is followed by a semicolon. @end itemize @node Declarations @@ -3265,7 +3280,7 @@ Grammars}). * Union Decl:: Declaring the set of all semantic value types. * Type Decl:: Declaring the choice of type for a nonterminal symbol. * Destructor Decl:: Declaring how symbols are freed. -* Expect Decl:: Suppressing warnings about shift/reduce conflicts. +* Expect Decl:: Suppressing warnings about parsing conflicts. * Start Decl:: Specifying the start symbol. * Pure Decl:: Requesting a reentrant parser. * Decl Summary:: Table of all Bison declarations. @@ -3294,10 +3309,12 @@ associativity and precedence. @xref{Precedence Decl, ,Operator Precedence}. You can explicitly specify the numeric code for a token type by appending -an integer value in the field immediately following the token name: +a decimal or hexadecimal integer value in the field immediately +following the token name: @example %token NUM 300 +%token XNUM 0x12d // a GNU extension @end example @noindent @@ -3494,7 +3511,7 @@ is called when a symbol is thrown away. Declare that the @var{code} must be invoked for each of the @var{symbols} that will be discarded by the parser. The @var{code} should use @code{$$} to designate the semantic value associated to the -@var{symbols}. The additional parser parameters are also avaible +@var{symbols}. The additional parser parameters are also available (@pxref{Parser Function, , The Parser Function @code{yyparse}}). @strong{Warning:} as of Bison 1.875, this feature is still considered as @@ -3543,6 +3560,7 @@ typefull: string; // $$ = $1 applies, $1 is not destroyed. @cindex warnings, preventing @cindex conflicts, suppressing warnings of @findex %expect +@findex %expect-rr Bison normally warns if there are any conflicts in the grammar (@pxref{Shift/Reduce, ,Shift/Reduce Conflicts}), but most real grammars @@ -3563,6 +3581,18 @@ reduce/reduce conflicts. The usual warning is given if there are either more or fewer conflicts, or if there are any reduce/reduce conflicts. +For normal LALR(1) parsers, reduce/reduce conflicts are more serious, +and should be eliminated entirely. Bison will always report +reduce/reduce conflicts for these parsers. With GLR parsers, however, +both shift/reduce and reduce/reduce are routine (otherwise, there +would be no need to use GLR parsing). Therefore, it is also possible +to specify an expected number of reduce/reduce conflicts in GLR +parsers, using the declaration: + +@example +%expect-rr @var{n} +@end example + In general, using @code{%expect} involves these steps: @itemize @bullet @@ -3670,9 +3700,16 @@ Declare a terminal symbol (token type name) that is left-associative @deffn {Directive} %nonassoc Declare a terminal symbol (token type name) that is nonassociative -(using it in a way that would be associative is a syntax error) -@end deffn (@pxref{Precedence Decl, ,Operator Precedence}). +Using it in a way that would be associative is a syntax error. +@end deffn + +@ifset defaultprec +@deffn {Directive} %default-prec +Assign a precedence to rules lacking an explicit @code{%prec} modifier +(@pxref{Contextual Precedence, ,Context-Dependent Precedence}). +@end deffn +@end ifset @deffn {Directive} %type Declare the type of semantic values for a nonterminal symbol @@ -3702,17 +3739,35 @@ already defined, so that the debugging facilities are compiled. @xref{Tracing, ,Tracing Your Parser}. @deffn {Directive} %defines -Write an extra output file containing macro definitions for the token -type names defined in the grammar and the semantic value type -@code{YYSTYPE}, as well as a few @code{extern} variable declarations. - +Write a header file containing macro definitions for the token type +names defined in the grammar as well as a few other declarations. If the parser output file is named @file{@var{name}.c} then this file is named @file{@var{name}.h}. -This output file is essential if you wish to put the definition of -@code{yylex} in a separate source file, because @code{yylex} needs to -be able to refer to token type codes and the variable -@code{yylval}. @xref{Token Values, ,Semantic Values of Tokens}. +Unless @code{YYSTYPE} is already defined as a macro, the output header +declares @code{YYSTYPE}. Therefore, if you are using a @code{%union} +(@pxref{Multiple Types, ,More Than One Value Type}) with components +that require other definitions, or if you have defined a +@code{YYSTYPE} macro (@pxref{Value Type, ,Data Types of Semantic +Values}), you need to arrange for these definitions to be propagated to +all modules, e.g., by putting them in a +prerequisite header that is included both by your parser and by any +other module that needs @code{YYSTYPE}. + +Unless your parser is pure, the output header declares @code{yylval} +as an external variable. @xref{Pure Decl, ,A Pure (Reentrant) +Parser}. + +If you have also used locations, the output header declares +@code{YYLTYPE} and @code{yylloc} using a protocol similar to that of +@code{YYSTYPE} and @code{yylval}. @xref{Locations, ,Tracking +Locations}. + +This output file is normally essential if you wish to put the +definition of @code{yylex} in a separate source file, because +@code{yylex} typically needs to be able to refer to the +above-mentioned declarations and to the token type codes. +@xref{Token Values, ,Semantic Values of Tokens}. @end deffn @deffn {Directive} %destructor @@ -3744,6 +3799,14 @@ and so on. @xref{Multiple Parsers, ,Multiple Parsers in the Same Program}. @end deffn +@ifset defaultprec +@deffn {Directive} %no-default-prec +Do not assign a precedence to rules lacking an explicit @code{%prec} +modifier (@pxref{Contextual Precedence, ,Context-Dependent +Precedence}). +@end deffn +@end ifset + @deffn {Directive} %no-parser Do not include any C code in the parser file; generate tables only. The parser file contains just @code{#define} directives and static variable @@ -4842,6 +4905,28 @@ exp: @dots{} @end group @end example +@ifset defaultprec +If you forget to append @code{%prec UMINUS} to the rule for unary +minus, Bison silently assumes that minus has its usual precedence. +This kind of problem can be tricky to debug, since one typically +discovers the mistake only by testing the code. + +The @code{%no-default-prec;} declaration makes it easier to discover +this kind of problem systematically. It causes rules that lack a +@code{%prec} modifier to have no precedence, even if the last terminal +symbol mentioned in their components has a declared precedence. + +If @code{%no-default-prec;} is in effect, you must specify @code{%prec} +for all rules that participate in precedence conflict resolution. +Then you will see any shift/reduce conflict until you tell Bison how +to resolve it, either by changing your grammar or by adding an +explicit precedence. This will probably add declarations to the +grammar, but it helps to protect against incorrect rule precedences. + +The effect of @code{%no-default-prec;} can be reversed by giving +@code{%default-prec;}, which is the default. +@end ifset + @node Parser States @section Parser States @cindex finite-state machine @@ -6162,7 +6247,7 @@ compatibility with @acronym{POSIX}: @example #! /bin/sh -bison -y "$@" +bison -y "$@@" @end example @end table @@ -6214,8 +6299,7 @@ Adjust the output: @itemx --defines Pretend that @code{%defines} was specified, i.e., write an extra output file containing macro definitions for the token type names defined in -the grammar and the semantic value type @code{YYSTYPE}, as well as a few -@code{extern} variable declarations. @xref{Decl Summary}. +the grammar, as well as a few other declarations. @xref{Decl Summary}. @item --defines=@var{defines-file} Same as above, but save in the file @var{defines-file}. @@ -6353,7 +6437,10 @@ are addressed. @menu * Parser Stack Overflow:: Breaking the Stack Limits +* How Can I Reset the Parser:: @code{yyparse} Keeps some State * Strings are Destroyed:: @code{yylval} Loses Track of Strings +* C++ Parsers:: Compiling Parsers with C++ Compilers +* Implementing Loops:: Control Flow in the Calculator @end menu @node Parser Stack Overflow @@ -6367,11 +6454,102 @@ message. What can I do? This question is already addressed elsewhere, @xref{Recursion, ,Recursive Rules}. +@node How Can I Reset the Parser +@section How Can I Reset the Parser + +The following phenomenon has several symptoms, resulting in the +following typical questions: + +@display +I invoke @code{yyparse} several times, and on correct input it works +properly; but when a parse error is found, all the other calls fail +too. How can I reset the error flag of @code{yyparse}? +@end display + +@noindent +or + +@display +My parser includes support for an @samp{#include}-like feature, in +which case I run @code{yyparse} from @code{yyparse}. This fails +although I did specify I needed a @code{%pure-parser}. +@end display + +These problems typically come not from Bison itself, but from +Lex-generated scanners. Because these scanners use large buffers for +speed, they might not notice a change of input file. As a +demonstration, consider the following source file, +@file{first-line.l}: + +@verbatim +%{ +#include +#include +%} +%% +.*\n ECHO; return 1; +%% +int +yyparse (char const *file) +{ + yyin = fopen (file, "r"); + if (!yyin) + exit (2); + /* One token only. */ + yylex (); + if (fclose (yyin) != 0) + exit (3); + return 0; +} + +int +main (void) +{ + yyparse ("input"); + yyparse ("input"); + return 0; +} +@end verbatim + +@noindent +If the file @file{input} contains + +@verbatim +input:1: Hello, +input:2: World! +@end verbatim + +@noindent +then instead of getting the first line twice, you get: + +@example +$ @kbd{flex -ofirst-line.c first-line.l} +$ @kbd{gcc -ofirst-line first-line.c -ll} +$ @kbd{./first-line} +input:1: Hello, +input:2: World! +@end example + +Therefore, whenever you change @code{yyin}, you must tell the +Lex-generated scanner to discard its current buffer and switch to the +new one. This depends upon your implementation of Lex; see its +documentation for more. For Flex, it suffices to call +@samp{YY_FLUSH_BUFFER} after each change to @code{yyin}. If your +Flex-generated scanner needs to read from several input streams to +handle features like include files, you might consider using Flex +functions like @samp{yy_switch_to_buffer} that manipulate multiple +input buffers. + +If your Flex-generated scanner uses start conditions (@pxref{Start +conditions, , Start conditions, flex, The Flex Manual}), you might +also want to reset the scanner's state, i.e., go back to the initial +start condition, through a call to @samp{BEGIN (0)}. + @node Strings are Destroyed @section Strings are Destroyed @display -My parser seems to destroy old strings, or maybe it losses track of +My parser seems to destroy old strings, or maybe it loses track of them. Instead of reporting @samp{"foo", "bar"}, it reports @samp{"bar", "bar"}, or even @samp{"foo\nbar", "bar"}. @end display @@ -6426,6 +6604,59 @@ $ @kbd{printf 'one\ntwo\n' | ./split-lines} @end example +@node C++ Parsers +@section C++ Parsers + +@display +How can I generate parsers in C++? +@end display + +We are working on a C++ output for Bison, but unfortunately, for lack +of time, the skeleton is not finished. It is functional, but in +numerous respects, it will require additional work which @emph{might} +break backward compatibility. Since the skeleton for C++ is not +documented, we do not consider ourselves bound to this interface, +nevertheless, as much as possible we will try to keep compatibility. + +Another possibility is to use the regular C parsers, and to compile +them with a C++ compiler. This works properly, provided that you bear +some simple C++ rules in mind, such as not including ``real classes'' +(i.e., structure with constructors) in unions. Therefore, in the +@code{%union}, use pointers to classes, or better yet, a single +pointer type to the root of your lexical/syntactic hierarchy. + + +@node Implementing Loops +@section Implementing Loops + +@display +My simple calculator supports variables, assignments, and functions, +but how can I implement loops? +@end display + +Although very pedagogical, the examples included in the document blur +the distinction to make between the parser---whose job is to recover +the structure of a text and to transmit it to subsequent modules of +the program---and the processing (such as the execution) of this +structure. This works well with so called straight line programs, +i.e., precisely those that have a straightforward execution model: +execute simple instructions one after the others. + +@cindex abstract syntax tree +@cindex @acronym{AST} +If you want a richer model, you will probably need to use the parser +to construct a tree that does represent the structure it has +recovered; this tree is usually called the @dfn{abstract syntax tree}, +or @dfn{@acronym{AST}} for short. Then, walking through this tree, +traversing it in various ways, will enable treatments such as its +execution or its translation, which will result in an interpreter or a +compiler. + +This topic is way beyond the scope of this manual, and the reader is +invited to consult the dedicated literature. + + + @c ================================================= Table of Symbols @node Table of Symbols @@ -6631,6 +6862,14 @@ parsing. @xref{Parser Function, ,The Parser Function @code{yyparse}}. Equip the parser for debugging. @xref{Decl Summary}. @end deffn +@ifset defaultprec +@deffn {Directive} %default-prec +Assign a precedence to rules that lack an explicit @samp{%prec} +modifier. @xref{Contextual Precedence, ,Context-Dependent +Precedence}. +@end deffn +@end ifset + @deffn {Directive} %defines Bison declaration to create a header file meant for the scanner. @xref{Decl Summary}. @@ -6684,6 +6923,14 @@ function is applied to the two semantic values to get a single result. Bison declaration to rename the external symbols. @xref{Decl Summary}. @end deffn +@ifset defaultprec +@deffn {Directive} %no-default-prec +Do not assign a precedence to rules that lack an explicit @samp{%prec} +modifier. @xref{Contextual Precedence, ,Context-Dependent +Precedence}. +@end deffn +@end ifset + @deffn {Directive} %no-lines Bison declaration to avoid generating @code{#line} directives in the parser file. @xref{Decl Summary}. @@ -6967,3 +7214,33 @@ grammatically indivisible. The piece of text it represents is a token. @printindex cp @bye + +@c LocalWords: texinfo setfilename settitle setchapternewpage finalout +@c LocalWords: ifinfo smallbook shorttitlepage titlepage GPL FIXME iftex +@c LocalWords: akim fn cp syncodeindex vr tp synindex dircategory direntry +@c LocalWords: ifset vskip pt filll insertcopying sp ISBN Etienne Suvasa +@c LocalWords: ifnottex yyparse detailmenu GLR RPN Calc var Decls Rpcalc +@c LocalWords: rpcalc Lexer Gen Comp Expr ltcalc mfcalc Decl Symtab yylex +@c LocalWords: yyerror pxref LR yylval cindex dfn LALR samp gpl BNF xref +@c LocalWords: const int paren ifnotinfo AC noindent emph expr stmt findex +@c LocalWords: glr YYSTYPE TYPENAME prog dprec printf decl init stmtMerge +@c LocalWords: pre STDC GNUC endif yy YY alloca lf stddef stdlib YYDEBUG +@c LocalWords: NUM exp subsubsection kbd Ctrl ctype EOF getchar isdigit +@c LocalWords: ungetc stdin scanf sc calc ulator ls lm cc NEG prec yyerrok +@c LocalWords: longjmp fprintf stderr preg yylloc YYLTYPE cos ln +@c LocalWords: smallexample symrec val tptr FNCT fnctptr func struct sym +@c LocalWords: fnct putsym getsym fname arith fncts atan ptr malloc sizeof +@c LocalWords: strlen strcpy fctn strcmp isalpha symbuf realloc isalnum +@c LocalWords: ptypes itype YYPRINT trigraphs yytname expseq vindex dtype +@c LocalWords: Rhs YYRHSLOC LE nonassoc op deffn typeless typefull yynerrs +@c LocalWords: yychar yydebug msg YYNTOKENS YYNNTS YYNRULES YYNSTATES +@c LocalWords: cparse clex deftypefun NE defmac YYACCEPT YYABORT param +@c LocalWords: strncmp intval tindex lvalp locp llocp typealt YYBACKUP +@c LocalWords: YYEMPTY YYRECOVERING yyclearin GE def UMINUS maybeword +@c LocalWords: Johnstone Shamsa Sadaf Hussain Tomita TR uref YYMAXDEPTH +@c LocalWords: YYINITDEPTH stmnts ref stmnt initdcl maybeasm VCG notype +@c LocalWords: hexflag STR exdent itemset asis DYYDEBUG YYFPRINTF args +@c LocalWords: YYPRINTF infile ypp yxx outfile itemx vcg tex leaderfill +@c LocalWords: hbox hss hfill tt ly yyin fopen fclose ofirst gcc ll +@c LocalWords: yyrestart nbar yytext fst snd osplit ntwo strdup AST +@c LocalWords: YYSTACK DVI fdl printindex