@value{UPDATED}), the @acronym{GNU} parser generator.
Copyright @copyright{} 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998,
-1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
@quotation
Permission is granted to copy, distribute and/or modify this document
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
+* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars.
+* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities.
+* GLR Semantic Actions:: Deferred semantic actions have special concerns.
+* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler.
Examples
@unnumbered Introduction
@cindex introduction
-@dfn{Bison} is a general-purpose parser generator that converts a
-grammar description for an @acronym{LALR}(1) context-free grammar into a C
-program to parse that grammar. Once you are proficient with Bison,
-you may use it to develop a wide range of language parsers, from those
+@dfn{Bison} is a general-purpose parser generator that converts a grammar
+description for an @acronym{LALR}(1) or @acronym{GLR} context-free grammar
+into a C or C++ program to parse that grammar. Once you are proficient with
+Bison, you can use it to develop a wide range of language parsers, from those
used in simple desk calculators to complex programming languages.
Bison is upward compatible with Yacc: all properly-written Yacc grammars
ought to work with Bison with no change. Anyone familiar with Yacc
should be able to use Bison with little trouble. You need to be fluent in
-C programming in order to use Bison or to understand this manual.
+C or C++ programming in order to use Bison or to understand this manual.
We begin with tutorial chapters that explain the basic concepts of using
Bison and show three explained examples, each building on the last. If you
@cindex @acronym{GLR} parsing
@cindex generalized @acronym{LR} (@acronym{GLR}) parsing
@cindex ambiguous grammars
-@cindex non-deterministic parsing
+@cindex nondeterministic parsing
Parsers for @acronym{LALR}(1) grammars are @dfn{deterministic}, meaning
roughly that the next grammar rule to apply at any point in the input is
(called a @dfn{look-ahead}) of the remaining input. A context-free
grammar can be @dfn{ambiguous}, meaning that there are multiple ways to
apply the grammar rules to get the same inputs. Even unambiguous
-grammars can be @dfn{non-deterministic}, meaning that no fixed
+grammars can be @dfn{nondeterministic}, meaning that no fixed
look-ahead always suffices to determine the next grammar rule to apply.
With the proper declarations, Bison is also able to parse these more
general context-free grammars, using a technique known as @acronym{GLR}
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
+* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars.
+* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities.
+* GLR Semantic Actions:: Deferred semantic actions have special concerns.
+* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler.
@end menu
@node Simple GLR Parsers
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.
+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
and the parser will report an error during any parse that results in
the offending merge.
+@node GLR Semantic Actions
+@subsection GLR Semantic Actions
+
+@cindex deferred semantic actions
+By definition, a deferred semantic action is not performed at the same time as
+the associated reduction.
+This raises caveats for several Bison features you might use in a semantic
+action in a @acronym{GLR} parser.
+
+@vindex yychar
+@cindex @acronym{GLR} parsers and @code{yychar}
+@vindex yylval
+@cindex @acronym{GLR} parsers and @code{yylval}
+@vindex yylloc
+@cindex @acronym{GLR} parsers and @code{yylloc}
+In any semantic action, you can examine @code{yychar} to determine the type of
+the look-ahead token present at the time of the associated reduction.
+After checking that @code{yychar} is not set to @code{YYEMPTY} or @code{YYEOF},
+you can then examine @code{yylval} and @code{yylloc} to determine the
+look-ahead token's semantic value and location, if any.
+In a nondeferred semantic action, you can also modify any of these variables to
+influence syntax analysis.
+@xref{Look-Ahead, ,Look-Ahead Tokens}.
+
+@findex yyclearin
+@cindex @acronym{GLR} parsers and @code{yyclearin}
+In a deferred semantic action, it's too late to influence syntax analysis.
+In this case, @code{yychar}, @code{yylval}, and @code{yylloc} are set to
+shallow copies of the values they had at the time of the associated reduction.
+For this reason alone, modifying them is dangerous.
+Moreover, the result of modifying them is undefined and subject to change with
+future versions of Bison.
+For example, if a semantic action might be deferred, you should never write it
+to invoke @code{yyclearin} (@pxref{Action Features}) or to attempt to free
+memory referenced by @code{yylval}.
+
+@findex YYERROR
+@cindex @acronym{GLR} parsers and @code{YYERROR}
+Another Bison feature requiring special consideration is @code{YYERROR}
+(@pxref{Action Features}), which you can invoke in a semantic action to
+initiate error recovery.
+During deterministic @acronym{GLR} operation, the effect of @code{YYERROR} is
+the same as its effect in an @acronym{LALR}(1) parser.
+In a deferred semantic action, its effect is undefined.
+@c The effect is probably a syntax error at the split point.
+
+Also, see @ref{Location Default Action, ,Default Action for Locations}, which
+describes a special usage of @code{YYLLOC_DEFAULT} in @acronym{GLR} parsers.
+
@node Compiler Requirements
@subsection Considerations when Compiling @acronym{GLR} Parsers
@cindex @code{inline}
It is easy to add new operators to the infix calculator as long as they are
only single-character literals. The lexical analyzer @code{yylex} passes
-back all nonnumber characters as tokens, so new grammar rules suffice for
+back all nonnumeric characters as tokens, so new grammar rules suffice for
adding a new operator. But we want something more flexible: built-in
functions whose syntax has this form:
The function @code{yylex} must now recognize variables, numeric values, and
the single-character arithmetic operators. Strings of alphanumeric
-characters with a leading non-digit are recognized as either variables or
+characters with a leading letter are recognized as either variables or
functions depending on what the symbol table says about them.
The string is passed to @code{getsym} for look up in the symbol table. If
@cindex Prologue
@cindex declarations
-The @var{Prologue} section contains macro definitions and
-declarations of functions and variables that are used in the actions in the
-grammar rules. These are copied to the beginning of the parser file so
-that they precede the definition of @code{yyparse}. You can use
-@samp{#include} to get the declarations from a header file. If you don't
-need any C declarations, you may omit the @samp{%@{} and @samp{%@}}
-delimiters that bracket this section.
+The @var{Prologue} section contains macro definitions and declarations
+of functions and variables that are used in the actions in the grammar
+rules. These are copied to the beginning of the parser file so that
+they precede the definition of @code{yyparse}. You can use
+@samp{#include} to get the declarations from a header file. If you
+don't need any C declarations, you may omit the @samp{%@{} and
+@samp{%@}} delimiters that bracket this section.
+
+The @var{Prologue} section is terminated by the the first occurrence
+of @samp{%@}} that is outside a comment, a string literal, or a
+character constant.
You may have more than one @var{Prologue} section, intermixed with the
@var{Bison declarations}. This allows you to have C and Bison
If the last section is empty, you may omit the @samp{%%} that separates it
from the grammar rules.
-The Bison parser itself contains many macros and identifiers whose
-names start with @samp{yy} or @samp{YY}, so it is a
-good idea to avoid using any such names (except those documented in this
-manual) in the epilogue of the grammar file.
+The Bison parser itself contains many macros and identifiers whose names
+start with @samp{yy} or @samp{YY}, so it is a good idea to avoid using
+any such names (except those documented in this manual) in the epilogue
+of the grammar file.
@node Symbols
@section Symbols, Terminal and Nonterminal
class of syntactically equivalent tokens. You use the symbol in grammar
rules to mean that a token in that class is allowed. The symbol is
represented in the Bison parser by a numeric code, and the @code{yylex}
-function returns a token type code to indicate what kind of token has been
-read. You don't need to know what the code value is; you can use the
-symbol to stand for it.
+function returns a token type code to indicate what kind of token has
+been read. You don't need to know what the code value is; you can use
+the symbol to stand for it.
-A @dfn{nonterminal symbol} stands for a class of syntactically equivalent
-groupings. The symbol name is used in writing grammar rules. By convention,
-it should be all lower case.
+A @dfn{nonterminal symbol} stands for a class of syntactically
+equivalent groupings. The symbol name is used in writing grammar rules.
+By convention, it should be all lower case.
Symbol names can contain letters, digits (not at the beginning),
underscores and periods. Periods make sense only in nonterminals.
in the other source files that need it. @xref{Invocation, ,Invoking Bison}.
If you want to write a grammar that is portable to any Standard C
-host, you must use only non-null character tokens taken from the basic
+host, you must use only nonnull character tokens taken from the basic
execution character set of Standard C@. This set consists of the ten
digits, the 52 lower- and upper-case English letters, and the
characters in the following C-language string:
"\a\b\t\n\v\f\r !\"#%&'()*+,-./:;<=>?[\\]^_@{|@}~"
@end example
-The @code{yylex} function and Bison must use a consistent character
-set and encoding for character tokens. For example, if you run Bison in an
-@acronym{ASCII} environment, but then compile and run the resulting program
-in an environment that uses an incompatible character set like
-@acronym{EBCDIC}, the resulting program may not work because the
-tables generated by Bison will assume @acronym{ASCII} numeric values for
-character tokens. It is standard
-practice for software distributions to contain C source files that
-were generated by Bison in an @acronym{ASCII} environment, so installers on
-platforms that are incompatible with @acronym{ASCII} must rebuild those
-files before compiling them.
+The @code{yylex} function and Bison must use a consistent character set
+and encoding for character tokens. For example, if you run Bison in an
+@acronym{ASCII} environment, but then compile and run the resulting
+program in an environment that uses an incompatible character set like
+@acronym{EBCDIC}, the resulting program may not work because the tables
+generated by Bison will assume @acronym{ASCII} numeric values for
+character tokens. It is standard practice for software distributions to
+contain C source files that were generated by Bison in an
+@acronym{ASCII} environment, so installers on platforms that are
+incompatible with @acronym{ASCII} must rebuild those files before
+compiling them.
The symbol @code{error} is a terminal symbol reserved for error recovery
(@pxref{Error Recovery}); you shouldn't use it for any other purpose.
@end example
@noindent
+@cindex braced code
+This is an example of @dfn{braced code}, that is, C code surrounded by
+braces, much like a compound statement in C@. Braced code can contain
+any sequence of C tokens, so long as its braces are balanced. Bison
+does not check the braced code for correctness directly; it merely
+copies the code to the output file, where the C compiler can check it.
+
+Within braced code, the balanced-brace count is not affected by braces
+within comments, string literals, or character constants, but it is
+affected by the C digraphs @samp{<%} and @samp{%>} that represent
+braces. At the top level braced code must be terminated by @samp{@}}
+and not by a digraph. Bison does not look for trigraphs, so if braced
+code uses trigraphs you should ensure that they do not affect the
+nesting of braces or the boundaries of comments, string literals, or
+character constants.
+
Usually there is only one action and it follows the components.
@xref{Actions}.
@section Recursive Rules
@cindex recursive rule
-A rule is called @dfn{recursive} when its @var{result} nonterminal appears
-also on its right hand side. Nearly all Bison grammars need to use
-recursion, because that is the only way to define a sequence of any number
-of a particular thing. Consider this recursive definition of a
+A rule is called @dfn{recursive} when its @var{result} nonterminal
+appears also on its right hand side. Nearly all Bison grammars need to
+use recursion, because that is the only way to define a sequence of any
+number of a particular thing. Consider this recursive definition of a
comma-separated sequence of one or more expressions:
@example
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 int}, while a string constant needs type @code{char *},
-and an identifier might need a pointer to an entry in the symbol table.
+@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
requires you to do two things:
is to compute a semantic value for the grouping built by the rule from the
semantic values associated with tokens or smaller groupings.
-An action consists of C statements surrounded by braces, much like a
-compound statement in C@. An action can contain any sequence of C
-statements. Bison does not look for trigraphs, though, so if your C
-code uses trigraphs you should ensure that they do not affect the
-nesting of braces or the boundaries of comments, strings, or character
-literals.
-
-An action can be placed at any position in the rule;
+An action consists of braced code containing C statements, and can be
+placed at any position in the rule;
it is executed at that position. Most rules have just one action at the
end of the rule, following all the components. Actions in the middle of
a rule are tricky and used only for special purposes (@pxref{Mid-Rule
always refers to the @code{expr} which precedes @code{bar} in the
definition of @code{foo}.
+@vindex yylval
+It is also possible to access the semantic value of the look-ahead token, if
+any, from a semantic action.
+This semantic value is stored in @code{yylval}.
+@xref{Action Features, ,Special Features for Use in Actions}.
+
@node Action Types
@subsection Data Types of Values in Actions
@cindex action data types
removes the temporary @code{let}-variable from the list so that it won't
appear to exist while the rest of the program is parsed.
+@findex %destructor
+@cindex discarded symbols, mid-rule actions
+@cindex error recovery, mid-rule actions
+In the above example, if the parser initiates error recovery (@pxref{Error
+Recovery}) while parsing the tokens in the embedded statement @code{stmt},
+it might discard the previous semantic context @code{$<context>5} without
+restoring it.
+Thus, @code{$<context>5} needs a destructor (@pxref{Destructor Decl, , Freeing
+Discarded Symbols}).
+However, Bison currently provides no means to declare a destructor for a
+mid-rule action's semantic value.
+
+One solution is to bury the mid-rule action inside a nonterminal symbol and to
+declare a destructor for that symbol:
+
+@example
+@group
+%type <context> let
+%destructor @{ pop_context ($$); @} let
+
+%%
+
+stmt: let stmt
+ @{ $$ = $2;
+ pop_context ($1); @}
+ ;
+
+let: LET '(' var ')'
+ @{ $$ = push_context ();
+ declare_variable ($3); @}
+ ;
+
+@end group
+@end example
+
+@noindent
+Note that the action is now at the end of its rule.
+Any mid-rule action can be converted to an end-of-rule action in this way, and
+this is what Bison actually does to implement mid-rule actions.
+
Taking action before a rule is completely recognized often leads to
conflicts since the parser must commit to a parse in order to execute the
action. For example, the following two rules, without mid-rule actions,
@noindent
Now Bison can execute the action in the rule for @code{subroutine} without
-deciding which rule for @code{compound} it will eventually use. Note that
-the action is now at the end of its rule. Any mid-rule action can be
-converted to an end-of-rule action in this way, and this is what Bison
-actually does to implement mid-rule actions.
+deciding which rule for @code{compound} it will eventually use.
@node Locations
@section Tracking Locations
@end group
@end example
+@vindex yylloc
+It is also possible to access the location of the look-ahead token, if any,
+from a semantic action.
+This location is stored in @code{yylloc}.
+@xref{Action Features, ,Special Features for Use in Actions}.
+
@node Location Default Action
@subsection Default Action for Locations
@vindex YYLLOC_DEFAULT
+@cindex @acronym{GLR} parsers and @code{YYLLOC_DEFAULT}
Actually, actions are not the best place to compute locations. Since
locations are much more general than semantic values, there is room in
rule. The @code{YYLLOC_DEFAULT} macro is invoked each time a rule is
matched, before the associated action is run. It is also invoked
while processing a syntax error, to compute the error's location.
+Before reporting an unresolvable syntactic ambiguity, a @acronym{GLR}
+parser invokes @code{YYLLOC_DEFAULT} recursively to compute the location
+of that ambiguity.
Most of the time, this macro is general enough to suppress location
dedicated code from semantic actions.
the location of the grouping (the result of the computation). When a
rule is matched, the second parameter identifies locations of
all right hand side elements of the rule being matched, and the third
-parameter is the size of the rule's right hand side. When processing
-a syntax error, the second parameter identifies locations of
-the symbols that were discarded during error processing, and the third
+parameter is the size of the rule's right hand side.
+When a @acronym{GLR} parser reports an ambiguity, which of multiple candidate
+right hand sides it passes to @code{YYLLOC_DEFAULT} is undefined.
+When processing a syntax error, the second parameter identifies locations
+of the symbols that were discarded during error processing, and the third
parameter is the number of discarded symbols.
By default, @code{YYLLOC_DEFAULT} is defined this way:
@cindex value types, declaring
@findex %union
-The @code{%union} declaration specifies the entire collection of possible
-data types for semantic values. The keyword @code{%union} is followed by a
-pair of braces containing the same thing that goes inside a @code{union} in
-C.
+The @code{%union} declaration specifies the entire collection of
+possible data types for semantic values. The keyword @code{%union} is
+followed by braced code containing the same thing that goes inside a
+@code{union} in C@.
For example:
@end group
@end example
+@noindent
specifies the union tag @code{value}, so the corresponding C type is
@code{union value}. If you do not specify a tag, it defaults to
@code{YYSTYPE}.
+As another extension to @acronym{POSIX}, you may specify multiple
+@code{%union} declarations; their contents are concatenated. However,
+only the first @code{%union} declaration can specify a tag.
+
Note that, unlike making a @code{union} declaration in C, you need not write
a semicolon after the closing brace.
@deffn {Directive} %initial-action @{ @var{code} @}
@findex %initial-action
-Declare that the @var{code} must be invoked before parsing each time
+Declare that the braced @var{code} must be invoked before parsing each time
@code{yyparse} is called. The @var{code} may use @code{$$} and
@code{@@$} --- initial value and location of the look-ahead --- and the
@code{%parse-param}.
During error recovery (@pxref{Error Recovery}), symbols already pushed
on the stack and tokens coming from the rest of the file are discarded
until the parser falls on its feet. If the parser runs out of memory,
-or if the parsing is cut by @code{YYACCEPT} or @code{YYABORT}, all the
+or if it returns via @code{YYABORT} or @code{YYACCEPT}, all the
symbols on the stack must be discarded. Even if the parser succeeds, it
must discard the start symbol.
@deffn {Directive} %destructor @{ @var{code} @} @var{symbols}
@findex %destructor
-Invoke @var{code} whenever the parser discards one of the @var{symbols}.
+Invoke the braced @var{code} whenever the parser discards one of the
+@var{symbols}.
Within @var{code}, @code{$$} designates the semantic value associated
with the discarded symbol. The additional parser parameters are also
available (@pxref{Parser Function, , The Parser Function
incoming terminals during the second phase of error recovery,
@item
the current look-ahead and the entire stack (except the current
-right-hand side symbols) when the parser aborts (either via an explicit
-call to @code{YYABORT} or @code{YYACCEPT}, or as a consequence of a
-failed error recovery or of memory exhaustion), and
+right-hand side symbols) when the parser returns immediately, and
@item
the start symbol, when the parser succeeds.
@end itemize
-Note that right-hand size symbols of a rule that explicitly triggers a
-syntax error via @code{YYERROR} are not reclaimed. As a thumb rule,
-destructors are invoked only when you do not have other means to manage
+The parser can @dfn{return immediately} because of an explicit call to
+@code{YYABORT} or @code{YYACCEPT}, or failed error recovery, or memory
+exhaustion.
+
+Right-hand size symbols of a rule that explicitly triggers a syntax
+error via @code{YYERROR} are not discarded automatically. As a rule
+of thumb, destructors are invoked only when user actions cannot manage
the memory.
@node Expect Decl
A @dfn{reentrant} program is one which does not alter in the course of
execution; in other words, it consists entirely of @dfn{pure} (read-only)
code. Reentrancy is important whenever asynchronous execution is possible;
-for example, a non-reentrant program may not be safe to call from a signal
-handler. In systems with multiple threads of control, a non-reentrant
+for example, a nonreentrant program may not be safe to call from a signal
+handler. In systems with multiple threads of control, a nonreentrant
program must be called only within interlocks.
Normally, Bison generates a parser which is not reentrant. This is
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}.
+(@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)
@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}.
+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
@deffn {Directive} %parse-param @{@var{argument-declaration}@}
@findex %parse-param
-Declare that an argument declared by @code{argument-declaration} is an
-additional @code{yyparse} argument.
+Declare that an argument declared by the braced-code
+@var{argument-declaration} is an additional @code{yyparse} argument.
The @var{argument-declaration} is used when declaring
functions or prototypes. The last identifier in
@var{argument-declaration} must be the argument name.
@subsection Semantic Values of Tokens
@vindex yylval
-In an ordinary (non-reentrant) parser, the semantic value of the token must
+In an ordinary (nonreentrant) parser, the semantic value of the token must
be stored into the global variable @code{yylval}. When you are using
just one data type for semantic values, @code{yylval} has that type.
Thus, if the type is @code{int} (the default), you might write this in
@vindex yylloc
If you are using the @samp{@@@var{n}}-feature (@pxref{Locations, ,
-Tracking Locations}) in actions to keep track of the
-textual locations of tokens and groupings, then you must provide this
-information in @code{yylex}. The function @code{yyparse} expects to
-find the textual location of a token just parsed in the global variable
-@code{yylloc}. So @code{yylex} must store the proper data in that
-variable.
+Tracking Locations}) in actions to keep track of the textual locations
+of tokens and groupings, then you must provide this information in
+@code{yylex}. The function @code{yyparse} expects to find the textual
+location of a token just parsed in the global variable @code{yylloc}.
+So @code{yylex} must store the proper data in that variable.
By default, the value of @code{yylloc} is a structure and you need only
initialize the members that are going to be used by the actions. The
@deffn {Directive} lex-param @{@var{argument-declaration}@}
@findex %lex-param
-Declare that @code{argument-declaration} is an additional @code{yylex}
-argument declaration.
+Declare that the braced-code @var{argument-declaration} is an
+additional @code{yylex} argument declaration.
@end deffn
For instance:
Value stored in @code{yychar} when there is no look-ahead token.
@end deffn
+@deffn {Macro} YYEOF
+@vindex YYEOF
+Value stored in @code{yychar} when the look-ahead is the end of the input
+stream.
+@end deffn
+
@deffn {Macro} YYERROR;
@findex YYERROR
Cause an immediate syntax error. This statement initiates error
@end deffn
@deffn {Variable} yychar
-Variable containing the current look-ahead token. (In a pure parser,
-this is actually a local variable within @code{yyparse}.) When there is
-no look-ahead token, the value @code{YYEMPTY} is stored in the variable.
+Variable containing either the look-ahead token, or @code{YYEOF} when the
+look-ahead is the end of the input stream, or @code{YYEMPTY} when no look-ahead
+has been performed so the next token is not yet known.
+Do not modify @code{yychar} in a deferred semantic action (@pxref{GLR Semantic
+Actions}).
@xref{Look-Ahead, ,Look-Ahead Tokens}.
@end deffn
@deffn {Macro} yyclearin;
Discard the current look-ahead token. This is useful primarily in
-error rules. @xref{Error Recovery}.
+error rules.
+Do not invoke @code{yyclearin} in a deferred semantic action (@pxref{GLR
+Semantic Actions}).
+@xref{Error Recovery}.
@end deffn
@deffn {Macro} yyerrok;
@xref{Error Recovery}.
@end deffn
+@deffn {Variable} yylloc
+Variable containing the look-ahead token location when @code{yychar} is not set
+to @code{YYEMPTY} or @code{YYEOF}.
+Do not modify @code{yylloc} in a deferred semantic action (@pxref{GLR Semantic
+Actions}).
+@xref{Actions and Locations, ,Actions and Locations}.
+@end deffn
+
+@deffn {Variable} yylval
+Variable containing the look-ahead token semantic value when @code{yychar} is
+not set to @code{YYEMPTY} or @code{YYEOF}.
+Do not modify @code{yylval} in a deferred semantic action (@pxref{GLR Semantic
+Actions}).
+@xref{Actions, ,Actions}.
+@end deffn
+
@deffn {Value} @@$
@findex @@$
Acts like a structure variable containing information on the textual location
A Bison-generated parser can print diagnostics, including error and
tracing messages. By default, they appear in English. However, Bison
-also supports outputting diagnostics in the user's native language.
-To make this work, the user should set the usual environment
-variables. @xref{Users, , The User's View, gettext, GNU
-@code{gettext} utilities}. For
-example, the shell command @samp{export LC_ALL=fr_CA.UTF-8} might set
-the user's locale to French Canadian using the @acronym{UTF}-8
+also supports outputting diagnostics in the user's native language. To
+make this work, the user should set the usual environment variables.
+@xref{Users, , The User's View, gettext, GNU @code{gettext} utilities}.
+For example, the shell command @samp{export LC_ALL=fr_CA.UTF-8} might
+set the user's locale to French Canadian using the @acronym{UTF}-8
encoding. The exact set of available locales depends on the user's
installation.
'!'}. No rule allows that sequence.
@vindex yychar
-The current look-ahead token is stored in the variable @code{yychar}.
+@vindex yylval
+@vindex yylloc
+The look-ahead token is stored in the variable @code{yychar}.
+Its semantic value and location, if any, are stored in the variables
+@code{yylval} and @code{yylloc}.
@xref{Action Features, ,Special Features for Use in Actions}.
@node Shift/Reduce
@cindex @acronym{GLR} parsing
@cindex generalized @acronym{LR} (@acronym{GLR}) parsing
@cindex ambiguous grammars
-@cindex non-deterministic parsing
+@cindex nondeterministic parsing
Bison produces @emph{deterministic} parsers that choose uniquely
when to reduce and which reduction to apply
context-free grammar in cubic worst-case time. However, Bison currently
uses a simpler data structure that requires time proportional to the
length of the input times the maximum number of stacks required for any
-prefix of the input. Thus, really ambiguous or non-deterministic
+prefix of the input. Thus, really ambiguous or nondeterministic
grammars can require exponential time and space to process. Such badly
behaving examples, however, are not generally of practical interest.
-Usually, non-determinism in a grammar is local---the parser is ``in
+Usually, nondeterminism in a grammar is local---the parser is ``in
doubt'' only for a few tokens at a time. Therefore, the current data
structure should generally be adequate. On @acronym{LALR}(1) portions of a
grammar, in particular, it is only slightly slower than with the default
this is unacceptable, then the macro @code{yyclearin} may be used to clear
this token. Write the statement @samp{yyclearin;} in the error rule's
action.
+@xref{Action Features, ,Special Features for Use in Actions}.
For example, suppose that on a syntax error, an error handling routine is
called that advances the input stream to some point where parsing should
@item --print-localedir
Print the name of the directory containing locale-dependent data.
-@need 1750
@item -y
@itemx --yacc
-Equivalent to @samp{-o y.tab.c}; the parser output file is called
+Act more like the traditional Yacc command. This can cause
+different diagnostics to be generated, and may change behavior in
+other minor ways. Most importantly, imitate Yacc's output
+file name conventions, so that the parser output file is called
@file{y.tab.c}, and the other outputs are called @file{y.output} and
-@file{y.tab.h}. The purpose of this option is to imitate Yacc's output
-file name conventions. Thus, the following shell script can substitute
+@file{y.tab.h}. Thus, the following shell script can substitute
for Yacc, and the Bison distribution contains such a script for
compatibility with @acronym{POSIX}:
#! /bin/sh
bison -y "$@@"
@end example
+
+The @option{-y}/@option{--yacc} option is intended for use with
+traditional Yacc grammars. If your grammar uses a Bison extension
+like @samp{%glr-parser}, Bison might not be Yacc-compatible even if
+this option is specified.
+
@end table
@noindent
the full set of items for each state, instead of its core only.
@end table
-For instance, on the following grammar
-
@item -v
@itemx --verbose
Pretend that @code{%verbose} was specified, i.e, write an extra output
declare and define the parser class in the namespace @code{yy}. The
class name defaults to @code{parser}, but may be changed using
@samp{%define "parser_class_name" "@var{name}"}. The interface of
-this class is detailled below. It can be extended using the
+this class is detailed below. It can be extended using the
@code{%parse-param} feature: its semantics is slightly changed since
it describes an additional member of the parser class, and an
additional argument for its constructor.
@deftypemethod {parser} {debug_level_type} debug_level ()
@deftypemethodx {parser} {void} set_debug_level (debug_level @var{l})
Get or set the tracing level. Currently its value is either 0, no trace,
-or non-zero, full tracing.
+or nonzero, full tracing.
@end deftypemethod
@deftypemethod {parser} {void} error (const location_type& @var{l}, const std::string& @var{m})
@subsection Calc++ --- C++ Calculator
Of course the grammar is dedicated to arithmetics, a single
-expression, possibily preceded by variable assignments. An
+expression, possibly preceded by variable assignments. An
environment containing possibly predefined variables such as
@code{one} and @code{two}, is exchanged with the parser. An example
of valid input follows.
To enable memory deallocation during error recovery, use
@code{%destructor}.
+@c FIXME: Document %printer, and mention that it takes a braced-code operand.
@comment file: calc++-parser.yy
@example
%printer @{ debug_stream () << *$$; @} "identifier"
unit: assignments exp @{ driver.result = $2; @};
assignments: assignments assignment @{@}
- | /* Nothing. */ @{@};
+ | /* Nothing. */ @{@};
assignment: "identifier" ":=" exp @{ driver.variables[*$1] = $3; @};
# include <string>
# include "calc++-driver.hh"
# include "calc++-parser.hh"
+/* Work around a bug in flex 2.5.31. See Debian bug 333231
+ <http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=333231>. */
+# undef yywrap
+# define yywrap() 1
%@}
@end example
@end example
@noindent
-The following paragraph suffices to track locations acurately. Each
+The following paragraph suffices to track locations accurately. Each
time @code{yylex} is invoked, the begin position is moved onto the end
position. Then when a pattern is matched, the end position is
advanced of its width. In case it matched ends of lines, the end
The rules are simple, just note the use of the driver to report errors.
It is convenient to use a typedef to shorten
@code{yy::calcxx_parser::token::identifier} into
-@code{token::identifier} for isntance.
+@code{token::identifier} for instance.
@comment file: calc++-scanner.ll
@example
@end deffn
@deffn {Directive} %nonassoc
-Bison declaration to assign non-associativity to token(s).
+Bison declaration to assign nonassociativity to token(s).
@xref{Precedence Decl, ,Operator Precedence}.
@end deffn
@end deffn
@deffn {Variable} yychar
-External integer variable that contains the integer value of the current
+External integer variable that contains the integer value of the
look-ahead token. (In a pure parser, it is a local variable within
@code{yyparse}.) Error-recovery rule actions may examine this variable.
@xref{Action Features, ,Special Features for Use in Actions}.
@deffn {Macro} YYLEX_PARAM
An obsolete macro for specifying an extra argument (or list of extra
-arguments) for @code{yyparse} to pass to @code{yylex}. he use of this
+arguments) for @code{yyparse} to pass to @code{yylex}. The use of this
macro is deprecated, and is supported only for Yacc like parsers.
@xref{Pure Calling,, Calling Conventions for Pure Parsers}.
@end deffn
External variable in which @code{yylex} should place the line and column
numbers associated with a token. (In a pure parser, it is a local
variable within @code{yyparse}, and its address is passed to
-@code{yylex}.) You can ignore this variable if you don't use the
-@samp{@@} feature in the grammar actions. @xref{Token Locations,
-,Textual Locations of Tokens}.
+@code{yylex}.)
+You can ignore this variable if you don't use the @samp{@@} feature in the
+grammar actions.
+@xref{Token Locations, ,Textual Locations of Tokens}.
+In semantic actions, it stores the location of the look-ahead token.
+@xref{Actions and Locations, ,Actions and Locations}.
@end deffn
@deffn {Type} YYLTYPE
External variable in which @code{yylex} should place the semantic
value associated with a token. (In a pure parser, it is a local
variable within @code{yyparse}, and its address is passed to
-@code{yylex}.) @xref{Token Values, ,Semantic Values of Tokens}.
+@code{yylex}.)
+@xref{Token Values, ,Semantic Values of Tokens}.
+In semantic actions, it stores the semantic value of the look-ahead token.
+@xref{Actions, ,Actions}.
@end deffn
@deffn {Macro} YYMAXDEPTH
@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: YYEMPTY YYEOF 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
projects / bison.git / blobdiff