@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
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
a semantic value (the value of an integer,
the name of an identifier, etc.).
* Semantic Actions:: Each rule can have an action containing C code.
-* GLR Parsers:: Writing parsers for general context-free languages
+* GLR Parsers:: Writing parsers for general context-free languages.
+* Simple GLR Parsers:: Using GLR in its simplest form.
* Locations Overview:: Tracking Locations.
* Bison Parser:: What are Bison's input and output,
how is the output used?
* 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.
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
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
a semantic value (the value of an integer,
the name of an identifier, etc.).
* Semantic Actions:: Each rule can have an action containing C code.
-* GLR Parsers:: Writing parsers for general context-free languages
+* GLR Parsers:: Writing parsers for general context-free languages.
+* Simple GLR Parsers:: Using GLR in its simplest form.
* Locations Overview:: Tracking Locations.
* Bison Parser:: What are Bison's input and output,
how is the output used?
%@}
@end example
+@node Simple GLR Parsers
+@section Using @acronym{GLR} in its Simplest Form
+@cindex @acronym{GLR} parsing, unambiguous grammars
+@cindex generalized @acronym{LR} (@acronym{GLR}) parsing, unambiguous grammars
+@findex %glr-parser
+@findex %expect-rr
+@cindex conflicts
+@cindex reduce/reduce conflicts
+
+The C++ example for @acronym{GLR} (@pxref{GLR Parsers}) explains how to use
+the @acronym{GLR} parsing algorithm with some advanced features such as
+@samp{%dprec} and @samp{%merge} to handle syntactically ambiguous
+grammars. However, the @acronym{GLR} algorithm can also be used in a simpler
+way to parse grammars that are unambiguous, but fail to be @acronym{LALR}(1).
+Such grammars typically require more than one symbol of lookahead,
+or (in rare cases) fall into the category of grammars in which the
+@acronym{LALR}(1) algorithm throws away too much information (they are in
+@acronym{LR}(1), but not @acronym{LALR}(1), @ref{Mystery Conflicts}).
+
+Here is an example of this situation, using a problem that
+arises in the declaration of enumerated and subrange types in the
+programming language Pascal. These declarations look like this:
+
+@example
+type subrange = lo .. hi;
+type enum = (a, b, c);
+@end example
+
+@noindent
+The original language standard allows only numeric
+literals and constant identifiers for the subrange bounds (@samp{lo}
+and @samp{hi}), but Extended Pascal (ISO/IEC 10206:1990) and many other
+Pascal implementations allow arbitrary expressions there. This gives
+rise to the following situation, containing a superfluous pair of
+parentheses:
+
+@example
+type subrange = (a) .. b;
+@end example
+
+@noindent
+Compare this to the following declaration of an enumerated
+type with only one value:
+
+@example
+type enum = (a);
+@end example
+
+@noindent
+(These declarations are contrived, but they are syntactically
+valid, and more-complicated cases can come up in practical programs.)
+
+These two declarations look identical until the @samp{..} token.
+With normal @acronym{LALR}(1) one-token look-ahead it is not
+possible to decide between the two forms when the identifier
+@samp{a} is parsed. It is, however, desirable
+for a parser to decide this, since in the latter case
+@samp{a} must become a new identifier to represent the enumeration
+value, while in the former case @samp{a} must be evaluated with its
+current meaning, which may be a constant or even a function call.
+
+You could parse @samp{(a)} as an ``unspecified identifier in parentheses'',
+to be resolved later, but this typically requires substantial
+contortions in both semantic actions and large parts of the
+grammar, where the parentheses are nested in the recursive rules for
+expressions.
+
+You might think of using the lexer to distinguish between the two
+forms by returning different tokens for currently defined and
+undefined identifiers. But if these declarations occur in a local
+scope, and @samp{a} is defined in an outer scope, then both forms
+are possible---either locally redefining @samp{a}, or using the
+value of @samp{a} from the outer scope. So this approach cannot
+work.
+
+A solution to this problem is to use a @acronym{GLR} parser in its simplest
+form, i.e., without using special features such as @samp{%dprec} and
+@samp{%merge}. When the @acronym{GLR} parser reaches the critical state, it
+simply splits into two branches and pursues both syntax rules
+simultaneously. Sooner or later, one of them runs into a parsing
+error. If there is a @samp{..} token before the next
+@samp{;}, the rule for enumerated types fails since it cannot
+accept @samp{..} anywhere; otherwise, the subrange type rule
+fails since it requires a @samp{..} token. So one of the branches
+fails silently, and the other one continues normally, performing
+all the intermediate actions that were postponed during the split.
+
+If the input is syntactically incorrect, both branches fail and the parser
+reports a syntax error as usual.
+
+The effect of all this is that the parser seems to ``guess'' the
+correct branch to take, or in other words, it seems to use more
+look-ahead than the underlying @acronym{LALR}(1) algorithm actually allows
+for. In this example, @acronym{LALR}(2) would suffice, but also some cases
+that are not @acronym{LALR}(@math{k}) for any @math{k} can be handled this way.
+
+Since there can be only two branches and at least one of them
+must fail, you need not worry about merging the branches by
+using dynamic precedence or @samp{%merge}.
+
+Another potential problem of @acronym{GLR} does not arise here, either. In
+general, a @acronym{GLR} parser can take quadratic or cubic worst-case time,
+and the current Bison parser even takes exponential time and space
+for some grammars. In practice, this rarely happens, and for many
+grammars it is possible to prove that it cannot happen. In
+in the present example, there is only one conflict between two
+rules, and the type-declaration context where the conflict
+arises cannot be nested. So the number of
+branches that can exist at any time is limited by the constant 2,
+and the parsing time is still linear.
+
+So here we have a case where we can use the benefits of @acronym{GLR}, almost
+without disadvantages. There are two things to note, though.
+First, one should carefully analyze the conflicts reported by
+Bison to make sure that @acronym{GLR} splitting is done only where it is
+intended to be. A @acronym{GLR} parser splitting inadvertently may cause
+problems less obvious than an @acronym{LALR} parser statically choosing the
+wrong alternative in a conflict.
+
+Second, interactions with the lexer (@pxref{Semantic Tokens}) must
+be considered with great care. Since a split parser consumes tokens
+without performing any actions during the split, the lexer cannot
+obtain information via parser actions. Some cases of
+lexer interactions can simply be eliminated by using @acronym{GLR}, i.e.,
+shifting the complications from the lexer to the parser. Remaining
+cases have to be checked for safety.
+
+In our example, it would be safe for the lexer to return tokens
+based on their current meanings in some symbol table, because no new
+symbols are defined in the middle of a type declaration. Though it
+is possible for a parser to define the enumeration
+constants as they are parsed, before the type declaration is
+completed, it actually makes no difference since they cannot be used
+within the same enumerated type declaration.
+
+Here is a Bison grammar corresponding to the example above. It
+parses a vastly simplified form of Pascal type declarations.
+
+@example
+%token TYPE DOTDOT ID
+
+@group
+%left '+' '-'
+%left '*' '/'
+@end group
+
+%%
+
+@group
+type_decl:
+ TYPE ID '=' type ';'
+;
+@end group
+
+@group
+type: '(' id_list ')'
+ | expr DOTDOT expr
+;
+@end group
+
+@group
+id_list: ID
+ | id_list ',' ID
+;
+@end group
+
+@group
+expr: '(' expr ')'
+ | expr '+' expr
+ | expr '-' expr
+ | expr '*' expr
+ | expr '/' expr
+ | ID
+;
+@end group
+@end example
+
+When used as a normal @acronym{LALR}(1) grammar, Bison correctly complains
+about one reduce/reduce conflict. In the conflicting situation the
+parser chooses one of the alternatives, arbitrarily the one
+declared first. Therefore the following correct input is not
+recognized:
+
+@example
+type t = (a) .. b;
+@end example
+
+The parser can be turned into a @acronym{GLR} parser, while also telling Bison
+to be silent about the one known reduce/reduce conflict, simply by
+adding these two declarations to the Bison input file:
+
+@example
+%glr-parser
+%expect-rr 1
+@end example
+
+@noindent
+No change in the grammar itself is required. Now the
+parser recognizes all valid declarations, according to the
+limited syntax above, transparently. In fact, the user does not even
+notice when the parser splits.
+
@node Locations Overview
@section Locations
@cindex location
For example, this:
@example
-exp : NUM | exp exp '+' @{$$ = $1 + $2; @} | @dots{}
+exp : NUM | exp exp '+' @{$$ = $1 + $2; @} | @dots{} ;
@end example
@noindent
exp: NUM
| exp exp '+' @{ $$ = $1 + $2; @}
| @dots{}
+;
@end example
@noindent
void
yyerror (char const *s)
@{
- printf ("%s\n", s);
+ fprintf (stderr, "%s\n", s);
@}
@end group
@end example
%@}
%union @{
- long n;
+ long int n;
tree t; /* @r{@code{tree} is defined in @file{ptypes.h}.} */
@}
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).
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
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:
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.
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
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
@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
@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
@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
* 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.
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
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
@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
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
@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
@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
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
@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
Bison produces @emph{deterministic} parsers that choose uniquely
when to reduce and which reduction to apply
-based on a summary of the preceding input and on one extra token of lookahead.
+based on a summary of the preceding input and on one extra token of look-ahead.
As a result, normal Bison handles a proper subset of the family of
context-free languages.
Ambiguous grammars, since they have strings with more than one possible
sequence of reductions cannot have deterministic parsers in this sense.
The same is true of languages that require more than one symbol of
-lookahead, since the parser lacks the information necessary to make a
+look-ahead, since the parser lacks the information necessary to make a
decision at the point it must be made in a shift-reduce parser.
Finally, as previously mentioned (@pxref{Mystery Conflicts}),
there are languages where Bison's particular choice of how to
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
+symbol, and the look-ahead 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 syntax error.''
+look-ahead triggers a syntax 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
+report lists @code{NUM} as a look-ahead token 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
@end example
@noindent
-the rule 5, @samp{exp: NUM;}, is completed. Whatever the lookahead
+the rule 5, @samp{exp: NUM;}, is completed. Whatever the look-ahead token
(@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}).
@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
+because of the item @samp{exp -> exp . '+' exp}, if the look-ahead 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
$default reduce using rule 1 (exp)
@end example
-Indeed, there are two actions associated to the lookahead @samp{/}:
+Indeed, there are two actions associated to the look-ahead @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
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
+possible, the look-ahead is required to select the action. State 8 is
+one such state: if the look-ahead 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:
+look-ahead token is @samp{*}, since we specified that @samp{*} has higher
+precedence than @samp{+}. More generally, some items are eligible only
+with some set of possible look-ahead tokens. When run with
+@option{--report=look-ahead}, Bison specifies these look-ahead tokens:
@example
state 8
@example
#! /bin/sh
-bison -y "$@"
+bison -y "$@@"
@end example
@end table
@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}.
Description of the grammar, conflicts (resolved and unresolved), and
@acronym{LALR} automaton.
-@item lookahead
+@item look-ahead
Implies @code{state} and augments the description of the automaton with
-each rule's lookahead set.
+each rule's look-ahead set.
@item itemset
Implies @code{state} and augments the description of the automaton with
@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
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 <stdio.h>
+#include <stdlib.h>
+%}
+%%
+.*\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 loses track of
+them. Instead of reporting @samp{"foo", "bar"}, it reports
+@samp{"bar", "bar"}, or even @samp{"foo\nbar", "bar"}.
+@end display
+
+This error is probably the single most frequent ``bug report'' sent to
+Bison lists, but is only concerned with a misunderstanding of the role
+of scanner. Consider the following Lex code:
+
+@verbatim
+%{
+#include <stdio.h>
+char *yylval = NULL;
+%}
+%%
+.* yylval = yytext; return 1;
+\n /* IGNORE */
+%%
+int
+main ()
+{
+ /* Similar to using $1, $2 in a Bison action. */
+ char *fst = (yylex (), yylval);
+ char *snd = (yylex (), yylval);
+ printf ("\"%s\", \"%s\"\n", fst, snd);
+ return 0;
+}
+@end verbatim
+
+If you compile and run this code, you get:
+
+@example
+$ @kbd{flex -osplit-lines.c split-lines.l}
+$ @kbd{gcc -osplit-lines split-lines.c -ll}
+$ @kbd{printf 'one\ntwo\n' | ./split-lines}
+"one
+two", "two"
+@end example
+
+@noindent
+this is because @code{yytext} is a buffer provided for @emph{reading}
+in the action, but if you want to keep it, you have to duplicate it
+(e.g., using @code{strdup}). Note that the output may depend on how
+your implementation of Lex handles @code{yytext}. For instance, when
+given the Lex compatibility option @option{-l} (which triggers the
+option @samp{%array}) Flex generates a different behavior:
+
+@example
+$ @kbd{flex -l -osplit-lines.c split-lines.l}
+$ @kbd{gcc -osplit-lines split-lines.c -ll}
+$ @kbd{printf 'one\ntwo\n' | ./split-lines}
+"two", "two"
+@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
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}.
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}.
@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
projects / bison.git / blobdiff