@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
@value{UPDATED}), the @acronym{GNU} parser generator.
Copyright @copyright{} 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998,
-1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
+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.
* Locations Overview:: Tracking Locations.
* Bison Parser:: What are Bison's input and output,
how is the output used?
* Stages:: Stages in writing and running Bison grammars.
* Grammar Layout:: Overall structure of a Bison grammar file.
+Writing @acronym{GLR} Parsers
+
+* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars
+* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities
+* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler
+
Examples
* RPN Calc:: Reverse polish notation calculator;
* 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 @code{yyparse}:: @code{yyparse} Keeps some State
+* 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
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.
* Locations Overview:: Tracking Locations.
* Bison Parser:: What are Bison's input and output,
how is the output used?
@findex %glr-parser
@cindex conflicts
@cindex shift/reduce conflicts
+@cindex reduce/reduce conflicts
-In some grammars, there will be cases where Bison's standard
+In some grammars, Bison's standard
@acronym{LALR}(1) parsing algorithm cannot decide whether to apply a
certain grammar rule at a given point. That is, it may not be able to
decide (on the basis of the input read so far) which of two possible
To use a grammar that is not easily modified to be @acronym{LALR}(1), a
more general parsing algorithm is sometimes necessary. If you include
@code{%glr-parser} among the Bison declarations in your file
-(@pxref{Grammar Outline}), the result will be a Generalized @acronym{LR}
+(@pxref{Grammar Outline}), the result is a Generalized @acronym{LR}
(@acronym{GLR}) parser. These parsers handle Bison grammars that
contain no unresolved conflicts (i.e., after applying precedence
declarations) identically to @acronym{LALR}(1) parsers. However, when
user-defined function on the resulting values to produce an arbitrary
merged result.
+@menu
+* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars
+* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities
+* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler
+@end menu
+
+@node Simple GLR Parsers
+@subsection Using @acronym{GLR} on Unambiguous Grammars
+@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
+@cindex shift/reduce conflicts
+
+In the simplest cases, you can use the @acronym{GLR} algorithm
+to parse grammars that are unambiguous, but fail to be @acronym{LALR}(1).
+Such grammars typically require more than one symbol of look-ahead,
+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}).
+
+Consider a problem that
+arises in the declaration of enumerated and subrange types in the
+programming language Pascal. Here are some examples:
+
+@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 (@acronym{ISO}/@acronym{IEC}
+10206) 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 simple solution to this problem is to declare the parser to
+use the @acronym{GLR} algorithm.
+When the @acronym{GLR} parser reaches the critical state, it
+merely 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.
+
+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.
+The present example contains only one conflict between two
+rules, and the type-declaration context containing the conflict
+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.
+
+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, by
+adding these two declarations to the Bison input file (before the first
+@samp{%%}):
+
+@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.
+
+So here we have a case where we can use the benefits of @acronym{GLR}, almost
+without disadvantages. Even in simple cases like this, however, there
+are at least two potential problems to beware.
+First, always analyze the conflicts reported by
+Bison to make sure that @acronym{GLR} splitting is only done where it is
+intended. 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, consider interactions with the lexer (@pxref{Semantic Tokens})
+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 be eliminated by using @acronym{GLR} to
+shift the complications from the lexer to the parser. You must check
+the remaining cases for correctness.
+
+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.
+
+@node Merging GLR Parses
+@subsection Using @acronym{GLR} to Resolve Ambiguities
+@cindex @acronym{GLR} parsing, ambiguous grammars
+@cindex generalized @acronym{LR} (@acronym{GLR}) parsing, ambiguous grammars
+@findex %dprec
+@findex %merge
+@cindex conflicts
+@cindex reduce/reduce conflicts
+
Let's consider an example, vastly simplified from a C++ grammar.
@example
@samp{x} as an @code{ID}).
Bison detects this as a reduce/reduce conflict between the rules
@code{expr : ID} and @code{declarator : ID}, which it cannot resolve at the
-time it encounters @code{x} in the example above. The two @code{%dprec}
-declarations, however, give precedence to interpreting the example as a
+time it encounters @code{x} in the example above. Since this is a
+@acronym{GLR} parser, it therefore splits the problem into two parses, one for
+each choice of resolving the reduce/reduce conflict.
+Unlike the example from the previous section (@pxref{Simple GLR Parsers}),
+however, neither of these parses ``dies,'' because the grammar as it stands is
+ambiguous. One of the parsers eventually reduces @code{stmt : expr ';'} and
+the other reduces @code{stmt : decl}, after which both parsers are in an
+identical state: they've seen @samp{prog stmt} and have the same unprocessed
+input remaining. We say that these parses have @dfn{merged.}
+
+At this point, the @acronym{GLR} parser requires a specification in the
+grammar of how to choose between the competing parses.
+In the example above, the two @code{%dprec}
+declarations specify that Bison is to give precedence
+to the parse that interprets the example as a
@code{decl}, which implies that @code{x} is a declarator.
The parser therefore prints
"x" y z + T <init-declare>
@end example
-Consider a different input string for this parser:
+The @code{%dprec} declarations only come into play when more than one
+parse survives. Consider a different input string for this parser:
@example
T (x) + y;
@end example
@noindent
+This is another example of using @acronym{GLR} to parse an unambiguous
+construct, as shown in the previous section (@pxref{Simple GLR Parsers}).
Here, there is no ambiguity (this cannot be parsed as a declaration).
However, at the time the Bison parser encounters @code{x}, it does not
have enough information to resolve the reduce/reduce conflict (again,
between @code{x} as an @code{expr} or a @code{declarator}). In this
-case, no precedence declaration is used. Instead, the parser splits
+case, no precedence declaration is used. Again, the parser splits
into two, one assuming that @code{x} is an @code{expr}, and the other
assuming @code{x} is a @code{declarator}. The second of these parsers
then vanishes when it sees @code{+}, and the parser prints
@end example
Suppose that instead of resolving the ambiguity, you wanted to see all
-the possibilities. For this purpose, we must @dfn{merge} the semantic
+the possibilities. For this purpose, you must merge the semantic
actions of the two possible parsers, rather than choosing one over the
other. To do so, you could change the declaration of @code{stmt} as
follows:
@end example
@noindent
-
and define the @code{stmtMerge} function as:
@example
@end example
@noindent
-With these declarations, the resulting parser will parse the first example
-as both an @code{expr} and a @code{decl}, and print
+With these declarations, the resulting parser parses the first example
+as both an @code{expr} and a @code{decl}, and prints
@example
"x" y z + T <init-declare> x T <cast> y z + = <OR>
@end example
-@sp 1
+Bison requires that all of the
+productions that participate in any particular merge have identical
+@samp{%merge} clauses. Otherwise, the ambiguity would be unresolvable,
+and the parser will report an error during any parse that results in
+the offending merge.
-@cindex @code{incline}
+@node Compiler Requirements
+@subsection Considerations when Compiling @acronym{GLR} Parsers
+@cindex @code{inline}
@cindex @acronym{GLR} parsers and @code{inline}
+
The @acronym{GLR} parsers require a compiler for @acronym{ISO} C89 or
later. In addition, they use the @code{inline} keyword, which is not
C89, but is C99 and is a common extension in pre-C99 compilers. It is
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
@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 @acronym{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 @acronym{GLR} parsers, however,
+both shift/reduce and reduce/reduce are routine (otherwise, there
+would be no need to use @acronym{GLR} parsing). Therefore, it is also possible
+to specify an expected number of reduce/reduce conflicts in @acronym{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
Specifying how the parser should reclaim the memory associated to
-discarded symbols. @xref{Destructor Decl, , Freeing Discarded Symbols}.
+discarded symbols. @xref{Destructor Decl, , Freeing Discarded Symbols}.
@end deffn
@deffn {Directive} %file-prefix="@var{prefix}"
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
immediately return 1.
Obviously, in location tracking pure parsers, @code{yyerror} should have
-an access to the current location. This is indeed the case for the GLR
+an access to the current location.
+This is indeed the case for the @acronym{GLR}
parsers, but not for the Yacc parser, for historical reasons. I.e., if
@samp{%locations %pure-parser} is passed then the prototypes for
@code{yyerror} are:
void yyerror (int *nastiness, char const *msg); /* GLR parsers. */
@end example
-Finally, GLR and Yacc parsers share the same @code{yyerror} calling
+Finally, @acronym{GLR} and Yacc parsers share the same @code{yyerror} calling
convention for absolutely pure parsers, i.e., when the calling
convention of @code{yylex} @emph{and} the calling convention of
@code{%pure-parser} are pure. I.e.:
@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
grammar, in particular, it is only slightly slower than with the default
Bison parser.
-For a more detailed exposition of GLR parsers, please see: Elizabeth
+For a more detailed exposition of @acronym{GLR} parsers, please see: Elizabeth
Scott, Adrian Johnstone and Shamsa Sadaf Hussain, Tomita-Style
Generalised @acronym{LR} Parsers, Royal Holloway, University of
London, Department of Computer Science, TR-00-12,
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
@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
+Observe that state 11 contains conflicts not only due to the lack of
+precedence of @samp{/} with respect to @samp{+}, @samp{-}, and
+@samp{*}, but also because the
associativity of @samp{/} is not specified.
@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 @code{yyparse}:: @code{yyparse} Keeps some State
+* 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
This question is already addressed elsewhere, @xref{Recursion,
,Recursive Rules}.
-@node How Can I Reset @code{yyparse}
-@section How Can I Reset @code{yyparse}
+@node How Can I Reset the Parser
+@section How Can I Reset the Parser
-The following phenomenon gives raise to several incarnations,
-resulting in the following typical questions:
+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 @code{yyparse}'s error flag?
+too. How can I reset the error flag of @code{yyparse}?
@end display
@noindent
or
@display
-My parser includes support for a @samp{#include} like feature, in
+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 are not related to Bison itself, but with the Lex
-generated scanners. Because these scanners use large buffers for
+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}:
.*\n ECHO; return 1;
%%
int
-yyparse (const char *file)
+yyparse (char const *file)
{
yyin = fopen (file, "r");
if (!yyin)
exit (2);
- /* One token only. */
+ /* One token only. */
yylex ();
- if (!fclose (yyin))
+ if (fclose (yyin) != 0)
exit (3);
return 0;
}
int
-main ()
+main (void)
{
yyparse ("input");
yyparse ("input");
@end verbatim
@noindent
-then instead of getting twice the first line, you get:
+then instead of getting the first line twice, you get:
@example
$ @kbd{flex -ofirst-line.c first-line.l}
input:2: World!
@end example
-Therefore, whenever you change @code{yyin}, you must tell the Lex
-generated scanner to discard its current buffer, and to switch to the
-new one. This depends upon your implementation of Lex, see its
-documentation for more. For instance, in the case of Flex, a simple
-call @samp{yyrestart (yyin)} suffices after each change to
-@code{yyin}.
+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
int
main ()
{
- /* Similar to using $1, $2 in a Bison action. */
+ /* Similar to using $1, $2 in a Bison action. */
char *fst = (yylex (), yylval);
char *snd = (yylex (), yylval);
printf ("\"%s\", \"%s\"\n", fst, snd);
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}.
@deffn {Directive} %destructor
Specifying how the parser should reclaim the memory associated to
-discarded symbols. @xref{Destructor Decl, , Freeing Discarded Symbols}.
+discarded symbols. @xref{Destructor Decl, , Freeing Discarded Symbols}.
@end deffn
@deffn {Directive} %dprec
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}.
projects / bison.git / blobdiff