# define YYLLOC_DEFAULT(Current, Rhs, N) \ do \ if (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; \ } \ else \ { \ (Current).first_line = (Current).last_line = \ YYRHSLOC(Rhs, 0).last_line; \ (Current).first_column = (Current).last_column = \ YYRHSLOC(Rhs, 0).last_column; \ } \ while (0)
where YYRHSLOC (rhs, k)
is the location of the kth symbol
in rhs when k is positive, and the location of the symbol
just before the reduction when k and n are both zero.
When defining YYLLOC_DEFAULT
, you should consider that:
YYLLOC_DEFAULT
.
The Bison declarations section of a Bison grammar defines the symbols used in formulating the grammar and the data types of semantic values. See Symbols.
All token type names (but not single-character literal tokens such as
'+'
and '*'
) must be declared. Nonterminal symbols must be
declared if you need to specify which data type to use for the semantic
value (see More Than One Value Type).
The first rule in the file also specifies the start symbol, by default. If you want some other symbol to be the start symbol, you must declare it explicitly (see Languages and Context-Free Grammars).
You may require the minimum version of Bison to process the grammar. If the requirement is not met, bison exits with an error (exit status 63).
%require "version"
The basic way to declare a token type name (terminal symbol) is as follows:
%token name
Bison will convert this into a #define
directive in
the parser, so that the function yylex
(if it is in this file)
can use the name name to stand for this token type's code.
Alternatively, you can use %left
, %right
, or
%nonassoc
instead of %token
, if you wish to specify
associativity and precedence. See Operator Precedence.
You can explicitly specify the numeric code for a token type by appending a nonnegative decimal or hexadecimal integer value in the field immediately following the token name:
%token NUM 300 %token XNUM 0x12d // a GNU extension
It is generally best, however, to let Bison choose the numeric codes for all token types. Bison will automatically select codes that don't conflict with each other or with normal characters.
In the event that the stack type is a union, you must augment the
%token
or other token declaration to include the data type
alternative delimited by angle-brackets (see More Than One Value Type).
For example:
%union { /* define stack type */ double val; symrec *tptr; } %token <val> NUM /* define token NUM and its type */
You can associate a literal string token with a token type name by
writing the literal string at the end of a %token
declaration which declares the name. For example:
%token arrow "=>"
For example, a grammar for the C language might specify these names with equivalent literal string tokens:
%token <operator> OR "||" %token <operator> LE 134 "<=" %left OR "<="
Once you equate the literal string and the token name, you can use them
interchangeably in further declarations or the grammar rules. The
yylex
function can use the token name or the literal string to
obtain the token type code number (see Calling Convention).
Syntax error messages passed to yyerror
from the parser will reference
the literal string instead of the token name.
The token numbered as 0 corresponds to end of file; the following line allows for nicer error messages referring to “end of file” instead of “$end”:
%token END 0 "end of file"
Use the %left
, %right
or %nonassoc
declaration to
declare a token and specify its precedence and associativity, all at
once. These are called precedence declarations.
See Operator Precedence, for general information on
operator precedence.
The syntax of a precedence declaration is nearly the same as that of
%token
: either
%left symbols...
or
%left <type> symbols...
And indeed any of these declarations serves the purposes of %token
.
But in addition, they specify the associativity and relative precedence for
all the symbols:
%left
specifies
left-associativity (grouping x with y first) and
%right
specifies right-associativity (grouping y with
z first). %nonassoc
specifies no associativity, which
means that x op y op z is
considered a syntax error.
For backward compatibility, there is a confusing difference between the
argument lists of %token
and precedence declarations.
Only a %token
can associate a literal string with a token type name.
A precedence declaration always interprets a literal string as a reference to a
separate token.
For example:
%left OR "<=" // Does not declare an alias. %left OR 134 "<=" 135 // Declares 134 for OR and 135 for "<=".
The %union
declaration specifies the entire collection of
possible data types for semantic values. The keyword %union
is
followed by braced code containing the same thing that goes inside a
union
in C.
For example:
%union { double val; symrec *tptr; }
This says that the two alternative types are double
and symrec
*
. They are given names val
and tptr
; these names are used
in the %token
and %type
declarations to pick one of the types
for a terminal or nonterminal symbol (see Nonterminal Symbols).
As an extension to POSIX, a tag is allowed after the
union
. For example:
%union value { double val; symrec *tptr; }
specifies the union tag value
, so the corresponding C type is
union value
. If you do not specify a tag, it defaults to
YYSTYPE
.
As another extension to POSIX, you may specify multiple
%union
declarations; their contents are concatenated. However,
only the first %union
declaration can specify a tag.
Note that, unlike making a union
declaration in C, you need not write
a semicolon after the closing brace.
Instead of %union
, you can define and use your own union type
YYSTYPE
if your grammar contains at least one
<type> tag. For example, you can put the following into
a header file parser.h:
union YYSTYPE { double val; symrec *tptr; }; typedef union YYSTYPE YYSTYPE;
and then your grammar can use the following
instead of %union
:
%{ #include "parser.h" %} %type <val> expr %token <tptr> ID
When you use %union
to specify multiple value types, you must
declare the value type of each nonterminal symbol for which values are
used. This is done with a %type
declaration, like this:
%type <type> nonterminal...
Here nonterminal is the name of a nonterminal symbol, and
type is the name given in the %union
to the alternative
that you want (see The Collection of Value Types). You
can give any number of nonterminal symbols in the same %type
declaration, if they have the same value type. Use spaces to separate
the symbol names.
You can also declare the value type of a terminal symbol. To do this,
use the same <
type>
construction in a declaration for the
terminal symbol. All kinds of token declarations allow
<
type>
.
Sometimes your parser needs to perform some initializations before
parsing. The %initial-action
directive allows for such arbitrary
code.
Declare that the braced code must be invoked before parsing each time
yyparse
is called. The code may use$$
and@$
— initial value and location of the lookahead — and the%parse-param
.
For instance, if your locations use a file name, you may use
%parse-param { char const *file_name }; %initial-action { @$.initialize (file_name); };
During error recovery (see 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 it returns via YYABORT
or YYACCEPT
, all the
symbols on the stack must be discarded. Even if the parser succeeds, it
must discard the start symbol.
When discarded symbols convey heap based information, this memory is lost. While this behavior can be tolerable for batch parsers, such as in traditional compilers, it is unacceptable for programs like shells or protocol implementations that may parse and execute indefinitely.
The %destructor
directive defines code that is called when a
symbol is automatically discarded.
Invoke the braced code whenever the parser discards one of the symbols. Within code,
$$
designates the semantic value associated with the discarded symbol, and@$
designates its location. The additional parser parameters are also available (see The Parser Functionyyparse
).When a symbol is listed among symbols, its
%destructor
is called a per-symbol%destructor
. You may also define a per-type%destructor
by listing a semantic type tag among symbols. In that case, the parser will invoke this code whenever it discards any grammar symbol that has that semantic type tag unless that symbol has its own per-symbol%destructor
.Finally, you can define two different kinds of default
%destructor
s. (These default forms are experimental. More user feedback will help to determine whether they should become permanent features.) You can place each of<*>
and<>
in the symbols list of exactly one%destructor
declaration in your grammar file. The parser will invoke the code associated with one of these whenever it discards any user-defined grammar symbol that has no per-symbol and no per-type%destructor
. The parser uses the code for<*>
in the case of such a grammar symbol for which you have formally declared a semantic type tag (%type
counts as such a declaration, but$<tag>$
does not). The parser uses the code for<>
in the case of such a grammar symbol that has no declared semantic type tag.
For example:
%union { char *string; } %token <string> STRING1 %token <string> STRING2 %type <string> string1 %type <string> string2 %union { char character; } %token <character> CHR %type <character> chr %token TAGLESS %destructor { } <character> %destructor { free ($$); } <*> %destructor { free ($$); printf ("%d", @$.first_line); } STRING1 string1 %destructor { printf ("Discarding tagless symbol.\n"); } <>
guarantees that, when the parser discards any user-defined symbol that has a
semantic type tag other than <character>
, it passes its semantic value
to free
by default.
However, when the parser discards a STRING1
or a string1
, it also
prints its line number to stdout
.
It performs only the second %destructor
in this case, so it invokes
free
only once.
Finally, the parser merely prints a message whenever it discards any symbol,
such as TAGLESS
, that has no semantic type tag.
A Bison-generated parser invokes the default %destructor
s only for
user-defined as opposed to Bison-defined symbols.
For example, the parser will not invoke either kind of default
%destructor
for the special Bison-defined symbols $accept
,
$undefined
, or $end
(see Bison Symbols),
none of which you can reference in your grammar.
It also will not invoke either for the error
token (see error), which is always defined by Bison regardless of whether you
reference it in your grammar.
However, it may invoke one of them for the end token (token 0) if you
redefine it from $end
to, for example, END
:
%token END 0
Finally, Bison will never invoke a %destructor
for an unreferenced
mid-rule semantic value (see Actions in Mid-Rule).
That is, Bison does not consider a mid-rule to have a semantic value if you do
not reference $$
in the mid-rule's action or $
n (where
n is the RHS symbol position of the mid-rule) in any later action in that
rule.
However, if you do reference either, the Bison-generated parser will invoke the
<>
%destructor
whenever it discards the mid-rule symbol.
Discarded symbols are the following:
The parser can return immediately because of an explicit call to
YYABORT
or YYACCEPT
, or failed error recovery, or memory
exhaustion.
Right-hand side symbols of a rule that explicitly triggers a syntax
error via YYERROR
are not discarded automatically. As a rule
of thumb, destructors are invoked only when user actions cannot manage
the memory.
Bison normally warns if there are any conflicts in the grammar
(see Shift/Reduce Conflicts), but most real grammars
have harmless shift/reduce conflicts which are resolved in a predictable
way and would be difficult to eliminate. It is desirable to suppress
the warning about these conflicts unless the number of conflicts
changes. You can do this with the %expect
declaration.
The declaration looks like this:
%expect n
Here n is a decimal integer. The declaration says there should be n shift/reduce conflicts and no reduce/reduce conflicts. Bison reports an error if the number of shift/reduce conflicts differs from n, 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 kinds of conflicts 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:
%expect-rr n
In general, using %expect
involves these steps:
%expect
. Use the -v option
to get a verbose list of where the conflicts occur. Bison will also
print the number of conflicts.
%expect
declaration, copying the number n from the
number which Bison printed. With GLR parsers, add an
%expect-rr
declaration as well.
Now Bison will warn you if you introduce an unexpected conflict, but will keep silent otherwise.
Bison assumes by default that the start symbol for the grammar is the first
nonterminal specified in the grammar specification section. The programmer
may override this restriction with the %start
declaration as follows:
%start symbol
A reentrant program is one which does not alter in the course of execution; in other words, it consists entirely of pure (read-only) code. Reentrancy is important whenever asynchronous execution is possible; 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
suitable for most uses, and it permits compatibility with Yacc. (The
standard Yacc interfaces are inherently nonreentrant, because they use
statically allocated variables for communication with yylex
,
including yylval
and yylloc
.)
Alternatively, you can generate a pure, reentrant parser. The Bison
declaration %define api.pure
says that you want the parser to be
reentrant. It looks like this:
%define api.pure
The result is that the communication variables yylval
and
yylloc
become local variables in yyparse
, and a different
calling convention is used for the lexical analyzer function
yylex
. See Calling Conventions for Pure Parsers, for the details of this. The variable yynerrs
becomes local in yyparse
in pull mode but it becomes a member
of yypstate in push mode. (see The Error Reporting Function yyerror
). The convention for calling
yyparse
itself is unchanged.
Whether the parser is pure has nothing to do with the grammar rules. You can generate either a pure parser or a nonreentrant parser from any valid grammar.
(The current push parsing interface is experimental and may evolve. More user feedback will help to stabilize it.)
A pull parser is called once and it takes control until all its input is completely parsed. A push parser, on the other hand, is called each time a new token is made available.
A push parser is typically useful when the parser is part of a main event loop in the client's application. This is typically a requirement of a GUI, when the main event loop needs to be triggered within a certain time period.
Normally, Bison generates a pull parser. The following Bison declaration says that you want the parser to be a push parser (see %define api.push_pull):
%define api.push_pull "push"
In almost all cases, you want to ensure that your push parser is also a pure parser (see A Pure (Reentrant) Parser). The only time you should create an impure push parser is to have backwards compatibility with the impure Yacc pull mode interface. Unless you know what you are doing, your declarations should look like this:
%define api.pure %define api.push_pull "push"
There is a major notable functional difference between the pure push parser and the impure push parser. It is acceptable for a pure push parser to have many parser instances, of the same type of parser, in memory at the same time. An impure push parser should only use one parser at a time.
When a push parser is selected, Bison will generate some new symbols in
the generated parser. yypstate
is a structure that the generated
parser uses to store the parser's state. yypstate_new
is the
function that will create a new parser instance. yypstate_delete
will free the resources associated with the corresponding parser instance.
Finally, yypush_parse
is the function that should be called whenever a
token is available to provide the parser. A trivial example
of using a pure push parser would look like this:
int status; yypstate *ps = yypstate_new (); do { status = yypush_parse (ps, yylex (), NULL); } while (status == YYPUSH_MORE); yypstate_delete (ps);
If the user decided to use an impure push parser, a few things about
the generated parser will change. The yychar
variable becomes
a global variable instead of a variable in the yypush_parse
function.
For this reason, the signature of the yypush_parse
function is
changed to remove the token as a parameter. A nonreentrant push parser
example would thus look like this:
extern int yychar; int status; yypstate *ps = yypstate_new (); do { yychar = yylex (); status = yypush_parse (ps); } while (status == YYPUSH_MORE); yypstate_delete (ps);
That's it. Notice the next token is put into the global variable yychar
for use by the next invocation of the yypush_parse
function.
Bison also supports both the push parser interface along with the pull parser
interface in the same generated parser. In order to get this functionality,
you should replace the %define api.push_pull "push"
declaration with the
%define api.push_pull "both"
declaration. Doing this will create all of
the symbols mentioned earlier along with the two extra symbols, yyparse
and yypull_parse
. yyparse
can be used exactly as it normally
would be used. However, the user should note that it is implemented in the
generated parser by calling yypull_parse
.
This makes the yyparse
function that is generated with the
%define api.push_pull "both"
declaration slower than the normal
yyparse
function. If the user
calls the yypull_parse
function it will parse the rest of the input
stream. It is possible to yypush_parse
tokens to select a subgrammar
and then yypull_parse
the rest of the input stream. If you would like
to switch back and forth between between parsing styles, you would have to
write your own yypull_parse
function that knows when to quit looking
for input. An example of using the yypull_parse
function would look
like this:
yypstate *ps = yypstate_new (); yypull_parse (ps); /* Will call the lexer */ yypstate_delete (ps);
Adding the %define api.pure
declaration does exactly the same thing to
the generated parser with %define api.push_pull "both"
as it did for
%define api.push_pull "push"
.
Here is a summary of the declarations used to define a grammar:
Declare the collection of data types that semantic values may have (see The Collection of Value Types).
Declare a terminal symbol (token type name) with no precedence or associativity specified (see Token Type Names).
Declare a terminal symbol (token type name) that is right-associative (see Operator Precedence).
Declare a terminal symbol (token type name) that is left-associative (see Operator Precedence).
Declare a terminal symbol (token type name) that is nonassociative (see Operator Precedence). Using it in a way that would be associative is a syntax error.
Declare the type of semantic values for a nonterminal symbol (see Nonterminal Symbols).
Declare the expected number of shift-reduce conflicts (see Suppressing Conflict Warnings).
In order to change the behavior of bison, use the following directives:
This is the unqualified form of the
%code
directive. It inserts code verbatim at a language-dependent default location in the output1.For C/C++, the default location is the parser source code file after the usual contents of the parser header file. Thus,
%code
replaces the traditional Yacc prologue,%{
code%}
, for most purposes. For a detailed discussion, see Prologue Alternatives.For Java, the default location is inside the parser class.
(Like all the Yacc prologue alternatives, this directive is experimental. More user feedback will help to determine whether it should become a permanent feature.)
This is the qualified form of the
%code
directive. If you need to specify location-sensitive verbatim code that does not belong at the default location selected by the unqualified%code
form, use this form instead.qualifier identifies the purpose of code and thus the location(s) where Bison should generate it. Not all values of qualifier are available for all target languages:
- requires
- Language(s): C, C++
- Purpose: This is the best place to write dependency code required for
YYSTYPE
andYYLTYPE
. In other words, it's the best place to define types referenced in%union
directives, and it's the best place to override Bison's defaultYYSTYPE
andYYLTYPE
definitions.- Location(s): The parser header file and the parser source code file before the Bison-generated
YYSTYPE
andYYLTYPE
definitions.- provides
- Language(s): C, C++
- Purpose: This is the best place to write additional definitions and declarations that should be provided to other modules.
- Location(s): The parser header file and the parser source code file after the Bison-generated
YYSTYPE
,YYLTYPE
, and token definitions.- top
- Language(s): C, C++
- Purpose: The unqualified
%code
or%code requires
should usually be more appropriate than%code top
. However, occasionally it is necessary to insert code much nearer the top of the parser source code file. For example:%code top { #define _GNU_SOURCE #include <stdio.h> }- Location(s): Near the top of the parser source code file.
- imports
- Language(s): Java
- Purpose: This is the best place to write Java import directives.
- Location(s): The parser Java file after any Java package directive and before any class definitions.
(Like all the Yacc prologue alternatives, this directive is experimental. More user feedback will help to determine whether it should become a permanent feature.)
For a detailed discussion of how to use
%code
in place of the traditional Yacc prologue for C/C++, see Prologue Alternatives.
In the parser file, define the macro
YYDEBUG
to 1 if it is not already defined, so that the debugging facilities are compiled.
Define a variable to adjust Bison's behavior. The possible choices for variable, as well as their meanings, depend on the selected target language and/or the parser skeleton (see %language, see %skeleton).
Bison will warn if a variable is defined multiple times.
Omitting
"
value"
is always equivalent to specifying it as""
.Some variables may be used as Booleans. In this case, Bison will complain if the variable definition does not meet one of the following four conditions:
"
value"
is"true"
"
value"
is omitted (or is""
). This is equivalent to"true"
."
value"
is"false"
.- variable is never defined. In this case, Bison selects a default value, which may depend on the selected target language and/or parser skeleton.
Some of the accepted variables are:
- api.pure
- Language(s): C
- Purpose: Request a pure (reentrant) parser program. See A Pure (Reentrant) Parser.
- Accepted Values: Boolean
- Default Value:
"false"
- api.push_pull
- Language(s): C (LALR(1) only)
- Purpose: Requests a pull parser, a push parser, or both. See A Push Parser. (The current push parsing interface is experimental and may evolve. More user feedback will help to stabilize it.)
- Accepted Values:
"pull"
,"push"
,"both"
- Default Value:
"pull"
- lr.keep_unreachable_states
- Language(s): all
- Purpose: Requests that Bison allow unreachable parser states to remain in the parser tables. Bison considers a state to be unreachable if there exists no sequence of transitions from the start state to that state. A state can become unreachable during conflict resolution if Bison disables a shift action leading to it from a predecessor state. Keeping unreachable states is sometimes useful for analysis purposes, but they are useless in the generated parser.
- Accepted Values: Boolean
- Default Value:
"false"
- Caveats:
- Unreachable states may contain conflicts and may use rules not used in any other state. Thus, keeping unreachable states may induce warnings that are irrelevant to your parser's behavior, and it may eliminate warnings that are relevant. Of course, the change in warnings may actually be relevant to a parser table analysis that wants to keep unreachable states, so this behavior will likely remain in future Bison releases.
- While Bison is able to remove unreachable states, it is not guaranteed to remove other kinds of useless states. Specifically, when Bison disables reduce actions during conflict resolution, some goto actions may become useless, and thus some additional states may become useless. If Bison were to compute which goto actions were useless and then disable those actions, it could identify such states as unreachable and then remove those states. However, Bison does not compute which goto actions are useless.
- namespace
- Languages(s): C++
- Purpose: Specifies the namespace for the parser class. For example, if you specify:
%define namespace "foo::bar"Bison uses
foo::bar
verbatim in references such as:foo::bar::parser::semantic_typeHowever, to open a namespace, Bison removes any leading
::
and then splits on any remaining occurrences:namespace foo { namespace bar { class position; class location; } }- Accepted Values: Any absolute or relative C++ namespace reference without a trailing
"::"
. For example,"foo"
or"::foo::bar"
.- Default Value: The value specified by
%name-prefix
, which defaults toyy
. This usage of%name-prefix
is for backward compatibility and can be confusing since%name-prefix
also specifies the textual prefix for the lexical analyzer function. Thus, if you specify%name-prefix
, it is best to also specify%define namespace
so that%name-prefix
only affects the lexical analyzer function. For example, if you specify:%define namespace "foo" %name-prefix "bar::"The parser namespace is
foo
andyylex
is referenced asbar::lex
.
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 name.c then this file is named name.h.
For C parsers, the output header declares
YYSTYPE
unlessYYSTYPE
is already defined as a macro or you have used a<
type>
tag without using%union
. Therefore, if you are using a%union
(see More Than One Value Type) with components that require other definitions, or if you have defined aYYSTYPE
macro or type definition (see 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 needsYYSTYPE
.Unless your parser is pure, the output header declares
yylval
as an external variable. See A Pure (Reentrant) Parser.If you have also used locations, the output header declares
YYLTYPE
andyylloc
using a protocol similar to that of theYYSTYPE
macro andyylval
. See Tracking Locations.This output file is normally essential if you wish to put the definition of
yylex
in a separate source file, becauseyylex
typically needs to be able to refer to the above-mentioned declarations and to the token type codes. See Semantic Values of Tokens.If you have declared
%code requires
or%code provides
, the output header also contains their code. See %code.
Specify how the parser should reclaim the memory associated to discarded symbols. See Freeing Discarded Symbols.
Specify a prefix to use for all Bison output file names. The names are chosen as if the input file were named prefix.y.
Specify the programming language for the generated parser. Currently supported languages include C, C++, and Java. language is case-insensitive.
This directive is experimental and its effect may be modified in future releases.
Generate the code processing the locations (see Special Features for Use in Actions). This mode is enabled as soon as the grammar uses the special @n tokens, but if your grammar does not use it, using %locations allows for more accurate syntax error messages.
Rename the external symbols used in the parser so that they start with prefix instead of yy. The precise list of symbols renamed in C parsers is
yyparse
,yylex
,yyerror
,yynerrs
,yylval
,yychar
,yydebug
, and (if locations are used)yylloc
. If you use a push parser,yypush_parse
,yypull_parse
,yypstate
,yypstate_new
andyypstate_delete
will also be renamed. For example, if you use %name-prefix "c_", the names becomec_parse
,c_lex
, and so on. For C++ parsers, see the%define namespace
documentation in this section. See Multiple Parsers in the Same Program.
Don't generate any
#line
preprocessor commands in the parser file. Ordinarily Bison writes these commands in the parser file so that the C compiler and debuggers will associate errors and object code with your source file (the grammar file). This directive causes them to associate errors with the parser file, treating it an independent source file in its own right.
Deprecated version of
%define api.pure
(see %define), for which Bison is more careful to warn about unreasonable usage.
Require version version or higher of Bison. See Require a Version of Bison.
Specify the skeleton to use.
If file does not contain a
/
, file is the name of a skeleton file in the Bison installation directory. If it does, file is an absolute file name or a file name relative to the directory of the grammar file. This is similar to how most shells resolve commands.
Generate an array of token names in the parser file. The name of the array is
yytname
;yytname[
i]
is the name of the token whose internal Bison token code number is i. The first three elements ofyytname
correspond to the predefined tokens"$end"
,"error"
, and"$undefined"
; after these come the symbols defined in the grammar file.The name in the table includes all the characters needed to represent the token in Bison. For single-character literals and literal strings, this includes the surrounding quoting characters and any escape sequences. For example, the Bison single-character literal
'+'
corresponds to a three-character name, represented in C as"'+'"
; and the Bison two-character literal string"\\/"
corresponds to a five-character name, represented in C as"\"\\\\/\""
.When you specify
%token-table
, Bison also generates macro definitions for macrosYYNTOKENS
,YYNNTS
, andYYNRULES
, andYYNSTATES
:
YYNTOKENS
- The highest token number, plus one.
YYNNTS
- The number of nonterminal symbols.
YYNRULES
- The number of grammar rules,
YYNSTATES
- The number of parser states (see Parser States).
Write an extra output file containing verbose descriptions of the parser states and what is done for each type of lookahead token in that state. See Understanding Your Parser, for more information.
Pretend the option --yacc was given, i.e., imitate Yacc, including its naming conventions. See Bison Options, for more.
Most programs that use Bison parse only one language and therefore contain
only one Bison parser. But what if you want to parse more than one
language with the same program? Then you need to avoid a name conflict
between different definitions of yyparse
, yylval
, and so on.
The easy way to do this is to use the option -p prefix (see Invoking Bison). This renames the interface functions and variables of the Bison parser to start with prefix instead of yy. You can use this to give each parser distinct names that do not conflict.
The precise list of symbols renamed is yyparse
, yylex
,
yyerror
, yynerrs
, yylval
, yylloc
,
yychar
and yydebug
. If you use a push parser,
yypush_parse
, yypull_parse
, yypstate
,
yypstate_new
and yypstate_delete
will also be renamed.
For example, if you use -p c, the names become cparse
,
clex
, and so on.
All the other variables and macros associated with Bison are not
renamed. These others are not global; there is no conflict if the same
name is used in different parsers. For example, YYSTYPE
is not
renamed, but defining this in different ways in different parsers causes
no trouble (see Data Types of Semantic Values).
The -p option works by adding macro definitions to the beginning
of the parser source file, defining yyparse
as
prefixparse
, and so on. This effectively substitutes one
name for the other in the entire parser file.
The Bison parser is actually a C function named yyparse
. Here we
describe the interface conventions of yyparse
and the other
functions that it needs to use.
Keep in mind that the parser uses many C identifiers starting with yy and YY for internal purposes. If you use such an identifier (aside from those in this manual) in an action or in epilogue in the grammar file, you are likely to run into trouble.
yyparse
You call the function yyparse
to cause parsing to occur. This
function reads tokens, executes actions, and ultimately returns when it
encounters end-of-input or an unrecoverable syntax error. You can also
write an action which directs yyparse
to return immediately
without reading further.
The value returned by
yyparse
is 0 if parsing was successful (return is due to end-of-input).The value is 1 if parsing failed because of invalid input, i.e., input that contains a syntax error or that causes
YYABORT
to be invoked.The value is 2 if parsing failed due to memory exhaustion.
In an action, you can cause immediate return from yyparse
by using
these macros:
If you use a reentrant parser, you can optionally pass additional
parameter information to it in a reentrant way. To do so, use the
declaration %parse-param
:
Declare that an argument declared by the braced-code argument-declaration is an additional
yyparse
argument. The argument-declaration is used when declaring functions or prototypes. The last identifier in argument-declaration must be the argument name.
Here's an example. Write this in the parser:
%parse-param {int *nastiness} %parse-param {int *randomness}
Then call the parser like this:
{ int nastiness, randomness; ... /* Store proper data innastiness
andrandomness
. */ value = yyparse (&nastiness, &randomness); ... }
In the grammar actions, use expressions like this to refer to the data:
exp: ... { ...; *randomness += 1; ... }
yypush_parse
(The current push parsing interface is experimental and may evolve. More user feedback will help to stabilize it.)
You call the function yypush_parse
to parse a single token. This
function is available if either the %define api.push_pull "push"
or
%define api.push_pull "both"
declaration is used.
See A Push Parser.
The value returned by
yypush_parse
is the same as for yyparse with the following exception.yypush_parse
will return YYPUSH_MORE if more input is required to finish parsing the grammar.
yypull_parse
(The current push parsing interface is experimental and may evolve. More user feedback will help to stabilize it.)
You call the function yypull_parse
to parse the rest of the input
stream. This function is available if the %define api.push_pull "both"
declaration is used.
See A Push Parser.
The value returned by
yypull_parse
is the same as foryyparse
.
yystate_new
(The current push parsing interface is experimental and may evolve. More user feedback will help to stabilize it.)
You call the function yypstate_new
to create a new parser instance.
This function is available if either the %define api.push_pull "push"
or
%define api.push_pull "both"
declaration is used.
See A Push Parser.
The fuction will return a valid parser instance if there was memory available or 0 if no memory was available. In impure mode, it will also return 0 if a parser instance is currently allocated.
yystate_delete
(The current push parsing interface is experimental and may evolve. More user feedback will help to stabilize it.)
You call the function yypstate_delete
to delete a parser instance.
function is available if either the %define api.push_pull "push"
or
%define api.push_pull "both"
declaration is used.
See A Push Parser.
This function will reclaim the memory associated with a parser instance. After this call, you should no longer attempt to use the parser instance.
yylex
The lexical analyzer function, yylex
, recognizes tokens from
the input stream and returns them to the parser. Bison does not create
this function automatically; you must write it so that yyparse
can
call it. The function is sometimes referred to as a lexical scanner.
In simple programs, yylex
is often defined at the end of the Bison
grammar file. If yylex
is defined in a separate source file, you
need to arrange for the token-type macro definitions to be available there.
To do this, use the -d option when you run Bison, so that it will
write these macro definitions into a separate header file
name.tab.h which you can include in the other source files
that need it. See Invoking Bison.
yylex
The value that yylex
returns must be the positive numeric code
for the type of token it has just found; a zero or negative value
signifies end-of-input.
When a token is referred to in the grammar rules by a name, that name
in the parser file becomes a C macro whose definition is the proper
numeric code for that token type. So yylex
can use the name
to indicate that type. See Symbols.
When a token is referred to in the grammar rules by a character literal,
the numeric code for that character is also the code for the token type.
So yylex
can simply return that character code, possibly converted
to unsigned char
to avoid sign-extension. The null character
must not be used this way, because its code is zero and that
signifies end-of-input.
Here is an example showing these things:
int yylex (void) { ... if (c == EOF) /* Detect end-of-input. */ return 0; ... if (c == '+' || c == '-') return c; /* Assume token type for `+' is '+'. */ ... return INT; /* Return the type of the token. */ ... }
This interface has been designed so that the output from the lex
utility can be used without change as the definition of yylex
.
If the grammar uses literal string tokens, there are two ways that
yylex
can determine the token type codes for them:
yylex
can use these symbolic names like
all others. In this case, the use of the literal string tokens in
the grammar file has no effect on yylex
.
yylex
can find the multicharacter token in the yytname
table. The index of the token in the table is the token type's code.
The name of a multicharacter token is recorded in yytname
with a
double-quote, the token's characters, and another double-quote. The
token's characters are escaped as necessary to be suitable as input
to Bison.
Here's code for looking up a multicharacter token in yytname
,
assuming that the characters of the token are stored in
token_buffer
, and assuming that the token does not contain any
characters like " that require escaping.
for (i = 0; i < YYNTOKENS; i++) { if (yytname[i] != 0 && yytname[i][0] == '"' && ! strncmp (yytname[i] + 1, token_buffer, strlen (token_buffer)) && yytname[i][strlen (token_buffer) + 1] == '"' && yytname[i][strlen (token_buffer) + 2] == 0) break; }
The yytname
table is generated only if you use the
%token-table
declaration. See Decl Summary.
In an ordinary (nonreentrant) parser, the semantic value of the token must
be stored into the global variable yylval
. When you are using
just one data type for semantic values, yylval
has that type.
Thus, if the type is int
(the default), you might write this in
yylex
:
... yylval = value; /* Put value onto Bison stack. */ return INT; /* Return the type of the token. */ ...
When you are using multiple data types, yylval
's type is a union
made from the %union
declaration (see The Collection of Value Types). So when you store a token's value, you
must use the proper member of the union. If the %union
declaration looks like this:
%union { int intval; double val; symrec *tptr; }
then the code in yylex
might look like this:
... yylval.intval = value; /* Put value onto Bison stack. */ return INT; /* Return the type of the token. */ ...
If you are using the @n-feature (see Tracking Locations) in actions to keep track of the textual locations
of tokens and groupings, then you must provide this information in
yylex
. The function yyparse
expects to find the textual
location of a token just parsed in the global variable yylloc
.
So yylex
must store the proper data in that variable.
By default, the value of yylloc
is a structure and you need only
initialize the members that are going to be used by the actions. The
four members are called first_line
, first_column
,
last_line
and last_column
. Note that the use of this
feature makes the parser noticeably slower.
The data type of yylloc
has the name YYLTYPE
.
When you use the Bison declaration %define api.pure
to request a
pure, reentrant parser, the global communication variables yylval
and yylloc
cannot be used. (See A Pure (Reentrant) Parser.) In such parsers the two global variables are replaced by
pointers passed as arguments to yylex
. You must declare them as
shown here, and pass the information back by storing it through those
pointers.
int yylex (YYSTYPE *lvalp, YYLTYPE *llocp) { ... *lvalp = value; /* Put value onto Bison stack. */ return INT; /* Return the type of the token. */ ... }
If the grammar file does not use the @ constructs to refer to
textual locations, then the type YYLTYPE
will not be defined. In
this case, omit the second argument; yylex
will be called with
only one argument.
If you wish to pass the additional parameter data to yylex
, use
%lex-param
just like %parse-param
(see Parser Function).
Declare that the braced-code argument-declaration is an additional
yylex
argument declaration.
For instance:
%parse-param {int *nastiness} %lex-param {int *nastiness} %parse-param {int *randomness}
results in the following signature:
int yylex (int *nastiness); int yyparse (int *nastiness, int *randomness);
If %define api.pure
is added:
int yylex (YYSTYPE *lvalp, int *nastiness); int yyparse (int *nastiness, int *randomness);
and finally, if both %define api.pure
and %locations
are used:
int yylex (YYSTYPE *lvalp, YYLTYPE *llocp, int *nastiness); int yyparse (int *nastiness, int *randomness);
yyerror
The Bison parser detects a syntax error or parse error
whenever it reads a token which cannot satisfy any syntax rule. An
action in the grammar can also explicitly proclaim an error, using the
macro YYERROR
(see Special Features for Use in Actions).
The Bison parser expects to report the error by calling an error
reporting function named yyerror
, which you must supply. It is
called by yyparse
whenever a syntax error is found, and it
receives one argument. For a syntax error, the string is normally
"syntax error"
.
If you invoke the directive %error-verbose
in the Bison
declarations section (see The Bison Declarations Section), then Bison provides a more verbose and specific error message
string instead of just plain "syntax error"
.
The parser can detect one other kind of error: memory exhaustion. This
can happen when the input contains constructions that are very deeply
nested. It isn't likely you will encounter this, since the Bison
parser normally extends its stack automatically up to a very large limit. But
if memory is exhausted, yyparse
calls yyerror
in the usual
fashion, except that the argument string is "memory exhausted"
.
In some cases diagnostics like "syntax error"
are
translated automatically from English to some other language before
they are passed to yyerror
. See Internationalization.
The following definition suffices in simple programs:
void yyerror (char const *s) { fprintf (stderr, "%s\n", s); }
After yyerror
returns to yyparse
, the latter will attempt
error recovery if you have written suitable error recovery grammar rules
(see Error Recovery). If recovery is impossible, yyparse
will
immediately return 1.
Obviously, in location tracking pure parsers, yyerror
should have
an access to the current location.
This is indeed the case for the GLR
parsers, but not for the Yacc parser, for historical reasons. I.e., if
%locations %define api.pure is passed then the prototypes for
yyerror
are:
void yyerror (char const *msg); /* Yacc parsers. */ void yyerror (YYLTYPE *locp, char const *msg); /* GLR parsers. */
If %parse-param {int *nastiness} is used, then:
void yyerror (int *nastiness, char const *msg); /* Yacc parsers. */ void yyerror (int *nastiness, char const *msg); /* GLR parsers. */
Finally, GLR and Yacc parsers share the same yyerror
calling
convention for absolutely pure parsers, i.e., when the calling
convention of yylex
and the calling convention of
%define api.pure
are pure.
I.e.:
/* Location tracking. */ %locations /* Pure yylex. */ %define api.pure %lex-param {int *nastiness} /* Pure yyparse. */ %parse-param {int *nastiness} %parse-param {int *randomness}
results in the following signatures for all the parser kinds:
int yylex (YYSTYPE *lvalp, YYLTYPE *llocp, int *nastiness); int yyparse (int *nastiness, int *randomness); void yyerror (YYLTYPE *locp, int *nastiness, int *randomness, char const *msg);
The prototypes are only indications of how the code produced by Bison
uses yyerror
. Bison-generated code always ignores the returned
value, so yyerror
can return any type, including void
.
Also, yyerror
can be a variadic function; that is why the
message is always passed last.
Traditionally yyerror
returns an int
that is always
ignored, but this is purely for historical reasons, and void
is
preferable since it more accurately describes the return type for
yyerror
.
The variable yynerrs
contains the number of syntax errors
reported so far. Normally this variable is global; but if you
request a pure parser (see A Pure (Reentrant) Parser)
then it is a local variable which only the actions can access.
Here is a table of Bison constructs, variables and macros that are useful in actions.
Acts like a variable that contains the semantic value for the grouping made by the current rule. See Actions.
Acts like a variable that contains the semantic value for the nth component of the current rule. See Actions.
Like
$$
but specifies alternative typealt in the union specified by the%union
declaration. See Data Types of Values in Actions.
Like
$
n but specifies alternative typealt in the union specified by the%union
declaration. See Data Types of Values in Actions.
Return immediately from
yyparse
, indicating failure. See The Parser Functionyyparse
.
Return immediately from
yyparse
, indicating success. See The Parser Functionyyparse
.
Unshift a token. This macro is allowed only for rules that reduce a single value, and only when there is no lookahead token. It is also disallowed in GLR parsers. It installs a lookahead token with token type token and semantic value value; then it discards the value that was going to be reduced by this rule.
If the macro is used when it is not valid, such as when there is a lookahead token already, then it reports a syntax error with a message cannot back up and performs ordinary error recovery.
In either case, the rest of the action is not executed.
Cause an immediate syntax error. This statement initiates error recovery just as if the parser itself had detected an error; however, it does not call
yyerror
, and does not print any message. If you want to print an error message, callyyerror
explicitly before the YYERROR; statement. See Error Recovery.
The expression
YYRECOVERING ()
yields 1 when the parser is recovering from a syntax error, and 0 otherwise. See Error Recovery.
Variable containing either the lookahead token, or
YYEOF
when the lookahead is the end of the input stream, orYYEMPTY
when no lookahead has been performed so the next token is not yet known. Do not modifyyychar
in a deferred semantic action (see GLR Semantic Actions). See Lookahead Tokens.
Discard the current lookahead token. This is useful primarily in error rules. Do not invoke
yyclearin
in a deferred semantic action (see GLR Semantic Actions). See Error Recovery.
Resume generating error messages immediately for subsequent syntax errors. This is useful primarily in error rules. See Error Recovery.
Variable containing the lookahead token location when
yychar
is not set toYYEMPTY
orYYEOF
. Do not modifyyylloc
in a deferred semantic action (see GLR Semantic Actions). See Actions and Locations.
Variable containing the lookahead token semantic value when
yychar
is not set toYYEMPTY
orYYEOF
. Do not modifyyylval
in a deferred semantic action (see GLR Semantic Actions). See Actions.
Acts like a structure variable containing information on the textual location of the grouping made by the current rule. See Tracking Locations.
Acts like a structure variable containing information on the textual location of the nth component of the current rule. See Tracking Locations.
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.
See The User's View (GNU gettext
utilities).
For example, the shell command export LC_ALL=fr_CA.UTF-8 might
set the user's locale to French Canadian using the UTF-8
encoding. The exact set of available locales depends on the user's
installation.
The maintainer of a package that uses a Bison-generated parser enables the internationalization of the parser's output through the following steps. Here we assume a package that uses GNU Autoconf and GNU Automake.
cp /usr/local/share/aclocal/bison-i18n.m4 m4/bison-i18n.m4
AM_GNU_GETTEXT
invocation, add an invocation of BISON_I18N
. This macro is
defined in the file bison-i18n.m4 that you copied earlier. It
causes configure to find the value of the
BISON_LOCALEDIR
variable, and it defines the source-language
symbol YYENABLE_NLS
to enable translations in the
Bison-generated parser.
main
function of your program, designate the directory
containing Bison's runtime message catalog, through a call to
bindtextdomain with domain name bison-runtime.
For example:
bindtextdomain ("bison-runtime", BISON_LOCALEDIR);
Typically this appears after any other call bindtextdomain
(PACKAGE, LOCALEDIR)
that your package already has. Here we rely on
BISON_LOCALEDIR to be defined as a string through the
Makefile.
main
function, make BISON_LOCALEDIR available as a C preprocessor macro,
either in DEFS or in AM_CPPFLAGS. For example:
DEFS = @DEFS@ -DBISON_LOCALEDIR='"$(BISON_LOCALEDIR)"'
or:
AM_CPPFLAGS = -DBISON_LOCALEDIR='"$(BISON_LOCALEDIR)"'
As Bison reads tokens, it pushes them onto a stack along with their semantic values. The stack is called the parser stack. Pushing a token is traditionally called shifting.
For example, suppose the infix calculator has read 1 + 5 *, with a 3 to come. The stack will have four elements, one for each token that was shifted.
But the stack does not always have an element for each token read. When the last n tokens and groupings shifted match the components of a grammar rule, they can be combined according to that rule. This is called reduction. Those tokens and groupings are replaced on the stack by a single grouping whose symbol is the result (left hand side) of that rule. Running the rule's action is part of the process of reduction, because this is what computes the semantic value of the resulting grouping.
For example, if the infix calculator's parser stack contains this:
1 + 5 * 3
and the next input token is a newline character, then the last three elements can be reduced to 15 via the rule:
expr: expr '*' expr;
Then the stack contains just these three elements:
1 + 15
At this point, another reduction can be made, resulting in the single value 16. Then the newline token can be shifted.
The parser tries, by shifts and reductions, to reduce the entire input down to a single grouping whose symbol is the grammar's start-symbol (see Languages and Context-Free Grammars).
This kind of parser is known in the literature as a bottom-up parser.
The Bison parser does not always reduce immediately as soon as the last n tokens and groupings match a rule. This is because such a simple strategy is inadequate to handle most languages. Instead, when a reduction is possible, the parser sometimes “looks ahead” at the next token in order to decide what to do.
When a token is read, it is not immediately shifted; first it becomes the lookahead token, which is not on the stack. Now the parser can perform one or more reductions of tokens and groupings on the stack, while the lookahead token remains off to the side. When no more reductions should take place, the lookahead token is shifted onto the stack. This does not mean that all possible reductions have been done; depending on the token type of the lookahead token, some rules may choose to delay their application.
Here is a simple case where lookahead is needed. These three rules define expressions which contain binary addition operators and postfix unary factorial operators (!), and allow parentheses for grouping.
expr: term '+' expr | term ; term: '(' expr ')' | term '!' | NUMBER ;
Suppose that the tokens 1 + 2 have been read and shifted; what
should be done? If the following token is ), then the first three
tokens must be reduced to form an expr
. This is the only valid
course, because shifting the ) would produce a sequence of symbols
term ')'
, and no rule allows this.
If the following token is !, then it must be shifted immediately so
that 2 ! can be reduced to make a term
. If instead the
parser were to reduce before shifting, 1 + 2 would become an
expr
. It would then be impossible to shift the ! because
doing so would produce on the stack the sequence of symbols expr
'!'
. No rule allows that sequence.
The lookahead token is stored in the variable yychar
.
Its semantic value and location, if any, are stored in the variables
yylval
and yylloc
.
See Special Features for Use in Actions.
Suppose we are parsing a language which has if-then and if-then-else statements, with a pair of rules like this:
if_stmt: IF expr THEN stmt | IF expr THEN stmt ELSE stmt ;
Here we assume that IF
, THEN
and ELSE
are
terminal symbols for specific keyword tokens.
When the ELSE
token is read and becomes the lookahead token, the
contents of the stack (assuming the input is valid) are just right for
reduction by the first rule. But it is also legitimate to shift the
ELSE
, because that would lead to eventual reduction by the second
rule.
This situation, where either a shift or a reduction would be valid, is called a shift/reduce conflict. Bison is designed to resolve these conflicts by choosing to shift, unless otherwise directed by operator precedence declarations. To see the reason for this, let's contrast it with the other alternative.
Since the parser prefers to shift the ELSE
, the result is to attach
the else-clause to the innermost if-statement, making these two inputs
equivalent:
if x then if y then win (); else lose; if x then do; if y then win (); else lose; end;
But if the parser chose to reduce when possible rather than shift, the result would be to attach the else-clause to the outermost if-statement, making these two inputs equivalent:
if x then if y then win (); else lose; if x then do; if y then win (); end; else lose;
The conflict exists because the grammar as written is ambiguous: either
parsing of the simple nested if-statement is legitimate. The established
convention is that these ambiguities are resolved by attaching the
else-clause to the innermost if-statement; this is what Bison accomplishes
by choosing to shift rather than reduce. (It would ideally be cleaner to
write an unambiguous grammar, but that is very hard to do in this case.)
This particular ambiguity was first encountered in the specifications of
Algol 60 and is called the “dangling else
” ambiguity.
To avoid warnings from Bison about predictable, legitimate shift/reduce
conflicts, use the %expect
n declaration. There will be no
warning as long as the number of shift/reduce conflicts is exactly n.
See Suppressing Conflict Warnings.
The definition of if_stmt
above is solely to blame for the
conflict, but the conflict does not actually appear without additional
rules. Here is a complete Bison input file that actually manifests the
conflict:
%token IF THEN ELSE variable %% stmt: expr | if_stmt ; if_stmt: IF expr THEN stmt | IF expr THEN stmt ELSE stmt ; expr: variable ;
Another situation where shift/reduce conflicts appear is in arithmetic expressions. Here shifting is not always the preferred resolution; the Bison declarations for operator precedence allow you to specify when to shift and when to reduce.
Consider the following ambiguous grammar fragment (ambiguous because the input 1 - 2 * 3 can be parsed in two different ways):
expr: expr '-' expr | expr '*' expr | expr '<' expr | '(' expr ')' ... ;
Suppose the parser has seen the tokens 1, - and 2; should it reduce them via the rule for the subtraction operator? It depends on the next token. Of course, if the next token is ), we must reduce; shifting is invalid because no single rule can reduce the token sequence - 2 ) or anything starting with that. But if the next token is * or <, we have a choice: either shifting or reduction would allow the parse to complete, but with different results.
To decide which one Bison should do, we must consider the results. If the next operator token op is shifted, then it must be reduced first in order to permit another opportunity to reduce the difference. The result is (in effect) 1 - (2 op 3). On the other hand, if the subtraction is reduced before shifting op, the result is (1 - 2) op 3. Clearly, then, the choice of shift or reduce should depend on the relative precedence of the operators - and op: * should be shifted first, but not <.
What about input such as 1 - 2 - 5; should this be (1 - 2) - 5 or should it be 1 - (2 - 5)? For most operators we prefer the former, which is called left association. The latter alternative, right association, is desirable for assignment operators. The choice of left or right association is a matter of whether the parser chooses to shift or reduce when the stack contains 1 - 2 and the lookahead token is -: shifting makes right-associativity.
Bison allows you to specify these choices with the operator precedence
declarations %left
and %right
. Each such declaration
contains a list of tokens, which are operators whose precedence and
associativity is being declared. The %left
declaration makes all
those operators left-associative and the %right
declaration makes
them right-associative. A third alternative is %nonassoc
, which
declares that it is a syntax error to find the same operator twice “in a
row”.
The relative precedence of different operators is controlled by the
order in which they are declared. The first %left
or
%right
declaration in the file declares the operators whose
precedence is lowest, the next such declaration declares the operators
whose precedence is a little higher, and so on.
In our example, we would want the following declarations:
%left '<' %left '-' %left '*'
In a more complete example, which supports other operators as well, we
would declare them in groups of equal precedence. For example, '+'
is
declared with '-'
:
%left '<' '>' '=' NE LE GE %left '+' '-' %left '*' '/'
(Here NE
and so on stand for the operators for “not equal”
and so on. We assume that these tokens are more than one character long
and therefore are represented by names, not character literals.)
The first effect of the precedence declarations is to assign precedence levels to the terminal symbols declared. The second effect is to assign precedence levels to certain rules: each rule gets its precedence from the last terminal symbol mentioned in the components. (You can also specify explicitly the precedence of a rule. See Context-Dependent Precedence.)
Finally, the resolution of conflicts works by comparing the precedence of the rule being considered with that of the lookahead token. If the token's precedence is higher, the choice is to shift. If the rule's precedence is higher, the choice is to reduce. If they have equal precedence, the choice is made based on the associativity of that precedence level. The verbose output file made by -v (see Invoking Bison) says how each conflict was resolved.
Not all rules and not all tokens have precedence. If either the rule or the lookahead token has no precedence, then the default is to shift.
Often the precedence of an operator depends on the context. This sounds outlandish at first, but it is really very common. For example, a minus sign typically has a very high precedence as a unary operator, and a somewhat lower precedence (lower than multiplication) as a binary operator.
The Bison precedence declarations, %left
, %right
and
%nonassoc
, can only be used once for a given token; so a token has
only one precedence declared in this way. For context-dependent
precedence, you need to use an additional mechanism: the %prec
modifier for rules.
The %prec
modifier declares the precedence of a particular rule by
specifying a terminal symbol whose precedence should be used for that rule.
It's not necessary for that symbol to appear otherwise in the rule. The
modifier's syntax is:
%prec terminal-symbol
and it is written after the components of the rule. Its effect is to assign the rule the precedence of terminal-symbol, overriding the precedence that would be deduced for it in the ordinary way. The altered rule precedence then affects how conflicts involving that rule are resolved (see Operator Precedence).
Here is how %prec
solves the problem of unary minus. First, declare
a precedence for a fictitious terminal symbol named UMINUS
. There
are no tokens of this type, but the symbol serves to stand for its
precedence:
... %left '+' '-' %left '*' %left UMINUS
Now the precedence of UMINUS
can be used in specific rules:
exp: ... | exp '-' exp ... | '-' exp %prec UMINUS
The function yyparse
is implemented using a finite-state machine.
The values pushed on the parser stack are not simply token type codes; they
represent the entire sequence of terminal and nonterminal symbols at or
near the top of the stack. The current state collects all the information
about previous input which is relevant to deciding what to do next.
Each time a lookahead token is read, the current parser state together with the type of lookahead token are looked up in a table. This table entry can say, “Shift the lookahead token.” In this case, it also specifies the new parser state, which is pushed onto the top of the parser stack. Or it can say, “Reduce using rule number n.” This means that a certain number of tokens or groupings are taken off the top of the stack, and replaced by one grouping. In other words, that number of states are popped from the stack, and one new state is pushed.
There is one other alternative: the table can say that the lookahead token is erroneous in the current state. This causes error processing to begin (see Error Recovery).
A reduce/reduce conflict occurs if there are two or more rules that apply to the same sequence of input. This usually indicates a serious error in the grammar.
For example, here is an erroneous attempt to define a sequence
of zero or more word
groupings.
sequence: /* empty */ { printf ("empty sequence\n"); } | maybeword | sequence word { printf ("added word %s\n", $2); } ; maybeword: /* empty */ { printf ("empty maybeword\n"); } | word { printf ("single word %s\n", $1); } ;
The error is an ambiguity: there is more than one way to parse a single
word
into a sequence
. It could be reduced to a
maybeword
and then into a sequence
via the second rule.
Alternatively, nothing-at-all could be reduced into a sequence
via the first rule, and this could be combined with the word
using the third rule for sequence
.
There is also more than one way to reduce nothing-at-all into a
sequence
. This can be done directly via the first rule,
or indirectly via maybeword
and then the second rule.
You might think that this is a distinction without a difference, because it does not change whether any particular input is valid or not. But it does affect which actions are run. One parsing order runs the second rule's action; the other runs the first rule's action and the third rule's action. In this example, the output of the program changes.
Bison resolves a reduce/reduce conflict by choosing to use the rule that
appears first in the grammar, but it is very risky to rely on this. Every
reduce/reduce conflict must be studied and usually eliminated. Here is the
proper way to define sequence
:
sequence: /* empty */ { printf ("empty sequence\n"); } | sequence word { printf ("added word %s\n", $2); } ;
Here is another common error that yields a reduce/reduce conflict:
sequence: /* empty */ | sequence words | sequence redirects ; words: /* empty */ | words word ; redirects:/* empty */ | redirects redirect ;
The intention here is to define a sequence which can contain either
word
or redirect
groupings. The individual definitions of
sequence
, words
and redirects
are error-free, but the
three together make a subtle ambiguity: even an empty input can be parsed
in infinitely many ways!
Consider: nothing-at-all could be a words
. Or it could be two
words
in a row, or three, or any number. It could equally well be a
redirects
, or two, or any number. Or it could be a words
followed by three redirects
and another words
. And so on.
Here are two ways to correct these rules. First, to make it a single level of sequence:
sequence: /* empty */ | sequence word | sequence redirect ;
Second, to prevent either a words
or a redirects
from being empty:
sequence: /* empty */ | sequence words | sequence redirects ; words: word | words word ; redirects:redirect | redirects redirect ;
Sometimes reduce/reduce conflicts can occur that don't look warranted. Here is an example:
%token ID %% def: param_spec return_spec ',' ; param_spec: type | name_list ':' type ; return_spec: type | name ':' type ; type: ID ; name: ID ; name_list: name | name ',' name_list ;
It would seem that this grammar can be parsed with only a single token
of lookahead: when a param_spec
is being read, an ID
is
a name
if a comma or colon follows, or a type
if another
ID
follows. In other words, this grammar is LR(1).
However, Bison, like most parser generators, cannot actually handle all
LR(1) grammars. In this grammar, two contexts, that after
an ID
at the beginning of a param_spec
and likewise at the beginning of
a return_spec
, are similar enough that Bison assumes they are the
same. They appear similar because the same set of rules would be
active—the rule for reducing to a name
and that for reducing to
a type
. Bison is unable to determine at that stage of processing
that the rules would require different lookahead tokens in the two
contexts, so it makes a single parser state for them both. Combining
the two contexts causes a conflict later. In parser terminology, this
occurrence means that the grammar is not LALR(1).
In general, it is better to fix deficiencies than to document them. But this particular deficiency is intrinsically hard to fix; parser generators that can handle LR(1) grammars are hard to write and tend to produce parsers that are very large. In practice, Bison is more useful as it is now.
When the problem arises, you can often fix it by identifying the two
parser states that are being confused, and adding something to make them
look distinct. In the above example, adding one rule to
return_spec
as follows makes the problem go away:
%token BOGUS ... %% ... return_spec: type | name ':' type /* This rule is never used. */ | ID BOGUS ;
This corrects the problem because it introduces the possibility of an
additional active rule in the context after the ID
at the beginning of
return_spec
. This rule is not active in the corresponding context
in a param_spec
, so the two contexts receive distinct parser states.
As long as the token BOGUS
is never generated by yylex
,
the added rule cannot alter the way actual input is parsed.
In this particular example, there is another way to solve the problem:
rewrite the rule for return_spec
to use ID
directly
instead of via name
. This also causes the two confusing
contexts to have different sets of active rules, because the one for
return_spec
activates the altered rule for return_spec
rather than the one for name
.
param_spec: type | name_list ':' type ; return_spec: type | ID ':' type ;
For a more detailed exposition of LALR(1) parsers and parser generators, please see: Frank DeRemer and Thomas Pennello, Efficient Computation of LALR(1) Look-Ahead Sets, ACM Transactions on Programming Languages and Systems, Vol. 4, No. 4 (October 1982), pp. 615–649 http://doi.acm.org/10.1145/69622.357187.
Bison produces 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. 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 decision at the point it must be made in a shift-reduce parser. Finally, as previously mentioned (see Mystery Conflicts), there are languages where Bison's particular choice of how to summarize the input seen so far loses necessary information.
When you use the %glr-parser declaration in your grammar file, Bison generates a parser that uses a different algorithm, called Generalized LR (or GLR). A Bison GLR parser uses the same basic algorithm for parsing as an ordinary Bison parser, but behaves differently in cases where there is a shift-reduce conflict that has not been resolved by precedence rules (see Precedence) or a reduce-reduce conflict. When a GLR parser encounters such a situation, it effectively splits into a several parsers, one for each possible shift or reduction. These parsers then proceed as usual, consuming tokens in lock-step. Some of the stacks may encounter other conflicts and split further, with the result that instead of a sequence of states, a Bison GLR parsing stack is what is in effect a tree of states.
In effect, each stack represents a guess as to what the proper parse is. Additional input may indicate that a guess was wrong, in which case the appropriate stack silently disappears. Otherwise, the semantics actions generated in each stack are saved, rather than being executed immediately. When a stack disappears, its saved semantic actions never get executed. When a reduction causes two stacks to become equivalent, their sets of semantic actions are both saved with the state that results from the reduction. We say that two stacks are equivalent when they both represent the same sequence of states, and each pair of corresponding states represents a grammar symbol that produces the same segment of the input token stream.
Whenever the parser makes a transition from having multiple states to having one, it reverts to the normal LALR(1) parsing algorithm, after resolving and executing the saved-up actions. At this transition, some of the states on the stack will have semantic values that are sets (actually multisets) of possible actions. The parser tries to pick one of the actions by first finding one whose rule has the highest dynamic precedence, as set by the %dprec declaration. Otherwise, if the alternative actions are not ordered by precedence, but there the same merging function is declared for both rules by the %merge declaration, Bison resolves and evaluates both and then calls the merge function on the result. Otherwise, it reports an ambiguity.
It is possible to use a data structure for the GLR parsing tree that permits the processing of any LALR(1) grammar in linear time (in the size of the input), any unambiguous (not necessarily LALR(1)) grammar in quadratic worst-case time, and any general (possibly ambiguous) 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 nondeterministic grammars can require exponential time and space to process. Such badly behaving examples, however, are not generally of practical interest. 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 LALR(1) portions of a 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 Scott, Adrian Johnstone and Shamsa Sadaf Hussain, Tomita-Style Generalised LR Parsers, Royal Holloway, University of London, Department of Computer Science, TR-00-12, http://www.cs.rhul.ac.uk/research/languages/publications/tomita_style_1.ps, (2000-12-24).
The Bison parser stack can run out of memory if too many tokens are shifted and
not reduced. When this happens, the parser function yyparse
calls yyerror
and then returns 2.
Because Bison parsers have growing stacks, hitting the upper limit usually results from using a right recursion instead of a left recursion, See Recursive Rules.
By defining the macro YYMAXDEPTH
, you can control how deep the
parser stack can become before memory is exhausted. Define the
macro with a value that is an integer. This value is the maximum number
of tokens that can be shifted (and not reduced) before overflow.
The stack space allowed is not necessarily allocated. If you specify a
large value for YYMAXDEPTH
, the parser normally allocates a small
stack at first, and then makes it bigger by stages as needed. This
increasing allocation happens automatically and silently. Therefore,
you do not need to make YYMAXDEPTH
painfully small merely to save
space for ordinary inputs that do not need much stack.
However, do not allow YYMAXDEPTH
to be a value so large that
arithmetic overflow could occur when calculating the size of the stack
space. Also, do not allow YYMAXDEPTH
to be less than
YYINITDEPTH
.
The default value of YYMAXDEPTH
, if you do not define it, is
10000.
You can control how much stack is allocated initially by defining the
macro YYINITDEPTH
to a positive integer. For the C
LALR(1) parser, this value must be a compile-time constant
unless you are assuming C99 or some other target language or compiler
that allows variable-length arrays. The default is 200.
Do not allow YYINITDEPTH
to be greater than YYMAXDEPTH
.
Because of semantical differences between C and C++, the
LALR(1) parsers in C produced by Bison cannot grow when compiled
by C++ compilers. In this precise case (compiling a C parser as C++) you are
suggested to grow YYINITDEPTH
. The Bison maintainers hope to fix
this deficiency in a future release.
It is not usually acceptable to have a program terminate on a syntax error. For example, a compiler should recover sufficiently to parse the rest of the input file and check it for errors; a calculator should accept another expression.
In a simple interactive command parser where each input is one line, it may
be sufficient to allow yyparse
to return 1 on error and have the
caller ignore the rest of the input line when that happens (and then call
yyparse
again). But this is inadequate for a compiler, because it
forgets all the syntactic context leading up to the error. A syntax error
deep within a function in the compiler input should not cause the compiler
to treat the following line like the beginning of a source file.
You can define how to recover from a syntax error by writing rules to
recognize the special token error
. This is a terminal symbol that
is always defined (you need not declare it) and reserved for error
handling. The Bison parser generates an error
token whenever a
syntax error happens; if you have provided a rule to recognize this token
in the current context, the parse can continue.
For example:
stmnts: /* empty string */ | stmnts '\n' | stmnts exp '\n' | stmnts error '\n'
The fourth rule in this example says that an error followed by a newline
makes a valid addition to any stmnts
.
What happens if a syntax error occurs in the middle of an exp
? The
error recovery rule, interpreted strictly, applies to the precise sequence
of a stmnts
, an error
and a newline. If an error occurs in
the middle of an exp
, there will probably be some additional tokens
and subexpressions on the stack after the last stmnts
, and there
will be tokens to read before the next newline. So the rule is not
applicable in the ordinary way.
But Bison can force the situation to fit the rule, by discarding part of
the semantic context and part of the input. First it discards states
and objects from the stack until it gets back to a state in which the
error
token is acceptable. (This means that the subexpressions
already parsed are discarded, back to the last complete stmnts
.)
At this point the error
token can be shifted. Then, if the old
lookahead token is not acceptable to be shifted next, the parser reads
tokens and discards them until it finds a token which is acceptable. In
this example, Bison reads and discards input until the next newline so
that the fourth rule can apply. Note that discarded symbols are
possible sources of memory leaks, see Freeing Discarded Symbols, for a means to reclaim this memory.
The choice of error rules in the grammar is a choice of strategies for error recovery. A simple and useful strategy is simply to skip the rest of the current input line or current statement if an error is detected:
stmnt: error ';' /* On error, skip until ';' is read. */
It is also useful to recover to the matching close-delimiter of an opening-delimiter that has already been parsed. Otherwise the close-delimiter will probably appear to be unmatched, and generate another, spurious error message:
primary: '(' expr ')' | '(' error ')' ... ;
Error recovery strategies are necessarily guesses. When they guess wrong,
one syntax error often leads to another. In the above example, the error
recovery rule guesses that an error is due to bad input within one
stmnt
. Suppose that instead a spurious semicolon is inserted in the
middle of a valid stmnt
. After the error recovery rule recovers
from the first error, another syntax error will be found straightaway,
since the text following the spurious semicolon is also an invalid
stmnt
.
To prevent an outpouring of error messages, the parser will output no error message for another syntax error that happens shortly after the first; only after three consecutive input tokens have been successfully shifted will error messages resume.
Note that rules which accept the error
token may have actions, just
as any other rules can.
You can make error messages resume immediately by using the macro
yyerrok
in an action. If you do this in the error rule's action, no
error messages will be suppressed. This macro requires no arguments;
yyerrok; is a valid C statement.
The previous lookahead token is reanalyzed immediately after an error. If
this is unacceptable, then the macro yyclearin
may be used to clear
this token. Write the statement yyclearin; in the error rule's
action.
See 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 once again commence. The next symbol returned by the lexical scanner is probably correct. The previous lookahead token ought to be discarded with yyclearin;.
The expression YYRECOVERING ()
yields 1 when the parser
is recovering from a syntax error, and 0 otherwise.
Syntax error diagnostics are suppressed while recovering from a syntax
error.
The Bison paradigm is to parse tokens first, then group them into larger syntactic units. In many languages, the meaning of a token is affected by its context. Although this violates the Bison paradigm, certain techniques (known as kludges) may enable you to write Bison parsers for such languages.
(Actually, “kludge” means any technique that gets its job done but is neither clean nor robust.)
The C language has a context dependency: the way an identifier is used depends on what its current meaning is. For example, consider this:
foo (x);
This looks like a function call statement, but if foo
is a typedef
name, then this is actually a declaration of x
. How can a Bison
parser for C decide how to parse this input?
The method used in GNU C is to have two different token types,
IDENTIFIER
and TYPENAME
. When yylex
finds an
identifier, it looks up the current declaration of the identifier in order
to decide which token type to return: TYPENAME
if the identifier is
declared as a typedef, IDENTIFIER
otherwise.
The grammar rules can then express the context dependency by the choice of
token type to recognize. IDENTIFIER
is accepted as an expression,
but TYPENAME
is not. TYPENAME
can start a declaration, but
IDENTIFIER
cannot. In contexts where the meaning of the identifier
is not significant, such as in declarations that can shadow a
typedef name, either TYPENAME
or IDENTIFIER
is
accepted—there is one rule for each of the two token types.
This technique is simple to use if the decision of which kinds of identifiers to allow is made at a place close to where the identifier is parsed. But in C this is not always so: C allows a declaration to redeclare a typedef name provided an explicit type has been specified earlier:
typedef int foo, bar; int baz (void) { static bar (bar); /* redeclarebar
as static variable */ extern foo foo (foo); /* redeclarefoo
as function */ return foo (bar); }
Unfortunately, the name being declared is separated from the declaration construct itself by a complicated syntactic structure—the “declarator”.
As a result, part of the Bison parser for C needs to be duplicated, with all the nonterminal names changed: once for parsing a declaration in which a typedef name can be redefined, and once for parsing a declaration in which that can't be done. Here is a part of the duplication, with actions omitted for brevity:
initdcl: declarator maybeasm '=' init | declarator maybeasm ; notype_initdcl: notype_declarator maybeasm '=' init | notype_declarator maybeasm ;
Here initdcl
can redeclare a typedef name, but notype_initdcl
cannot. The distinction between declarator
and
notype_declarator
is the same sort of thing.
There is some similarity between this technique and a lexical tie-in (described next), in that information which alters the lexical analysis is changed during parsing by other parts of the program. The difference is here the information is global, and is used for other purposes in the program. A true lexical tie-in has a special-purpose flag controlled by the syntactic context.
One way to handle context-dependency is the lexical tie-in: a flag which is set by Bison actions, whose purpose is to alter the way tokens are parsed.
For example, suppose we have a language vaguely like C, but with a special
construct hex (hex-expr). After the keyword hex
comes
an expression in parentheses in which all integers are hexadecimal. In
particular, the token a1b must be treated as an integer rather than
as an identifier if it appears in that context. Here is how you can do it:
%{ int hexflag; int yylex (void); void yyerror (char const *); %} %% ... expr: IDENTIFIER | constant | HEX '(' { hexflag = 1; } expr ')' { hexflag = 0; $$ = $4; } | expr '+' expr { $$ = make_sum ($1, $3); } ... ; constant: INTEGER | STRING ;
Here we assume that yylex
looks at the value of hexflag
; when
it is nonzero, all integers are parsed in hexadecimal, and tokens starting
with letters are parsed as integers if possible.
The declaration of hexflag
shown in the prologue of the parser file
is needed to make it accessible to the actions (see The Prologue).
You must also write the code in yylex
to obey the flag.
Lexical tie-ins make strict demands on any error recovery rules you have. See Error Recovery.
The reason for this is that the purpose of an error recovery rule is to abort the parsing of one construct and resume in some larger construct. For example, in C-like languages, a typical error recovery rule is to skip tokens until the next semicolon, and then start a new statement, like this:
stmt: expr ';' | IF '(' expr ')' stmt { ... } ... error ';' { hexflag = 0; } ;
If there is a syntax error in the middle of a hex (expr)
construct, this error rule will apply, and then the action for the
completed hex (expr) will never run. So hexflag
would
remain set for the entire rest of the input, or until the next hex
keyword, causing identifiers to be misinterpreted as integers.
To avoid this problem the error recovery rule itself clears hexflag
.
There may also be an error recovery rule that works within expressions. For example, there could be a rule which applies within parentheses and skips to the close-parenthesis:
expr: ... | '(' expr ')' { $$ = $2; } | '(' error ')' ...
If this rule acts within the hex
construct, it is not going to abort
that construct (since it applies to an inner level of parentheses within
the construct). Therefore, it should not clear the flag: the rest of
the hex
construct should be parsed with the flag still in effect.
What if there is an error recovery rule which might abort out of the
hex
construct or might not, depending on circumstances? There is no
way you can write the action to determine whether a hex
construct is
being aborted or not. So if you are using a lexical tie-in, you had better
make sure your error recovery rules are not of this kind. Each rule must
be such that you can be sure that it always will, or always won't, have to
clear the flag.
Developing a parser can be a challenge, especially if you don't understand the algorithm (see The Bison Parser Algorithm). Even so, sometimes a detailed description of the automaton can help (see Understanding Your Parser), or tracing the execution of the parser can give some insight on why it behaves improperly (see Tracing Your Parser).
As documented elsewhere (see The Bison Parser Algorithm) Bison parsers are shift/reduce automata. In some cases (much more frequent than one would hope), looking at this automaton is required to tune or simply fix a parser. Bison provides two different representation of it, either textually or graphically (as a DOT file).
The textual file is generated when the options --report or --verbose are specified, see See Invoking Bison. Its name is made by removing .tab.c or .c from the parser output file name, and adding .output instead. Therefore, if the input file is foo.y, then the parser file is called foo.tab.c by default. As a consequence, the verbose output file is called foo.output.
The following grammar file, calc.y, will be used in the sequel:
%token NUM STR %left '+' '-' %left '*' %% exp: exp '+' exp | exp '-' exp | exp '*' exp | exp '/' exp | NUM ; useless: STR; %%
bison reports:
calc.y: warning: 1 nonterminal and 1 rule useless in grammar calc.y:11.1-7: warning: nonterminal useless in grammar: useless calc.y:11.10-12: warning: rule useless in grammar: useless: STR calc.y: conflicts: 7 shift/reduce
When given --report=state, in addition to calc.tab.c, it creates a file calc.output with contents detailed below. The order of the output and the exact presentation might vary, but the interpretation is the same.
The first section includes details on conflicts that were solved thanks to precedence and/or associativity:
Conflict in state 8 between rule 2 and token '+' resolved as reduce. Conflict in state 8 between rule 2 and token '-' resolved as reduce. Conflict in state 8 between rule 2 and token '*' resolved as shift.
...
The next section lists states that still have conflicts.
State 8 conflicts: 1 shift/reduce State 9 conflicts: 1 shift/reduce State 10 conflicts: 1 shift/reduce State 11 conflicts: 4 shift/reduce
The next section reports useless tokens, nonterminal and rules. Useless nonterminals and rules are removed in order to produce a smaller parser, but useless tokens are preserved, since they might be used by the scanner (note the difference between “useless” and “unused” below):
Nonterminals useless in grammar: useless Terminals unused in grammar: STR Rules useless in grammar: #6 useless: STR;
The next section reproduces the exact grammar that Bison used:
Grammar Number, Line, Rule 0 5 $accept -> exp $end 1 5 exp -> exp '+' exp 2 6 exp -> exp '-' exp 3 7 exp -> exp '*' exp 4 8 exp -> exp '/' exp 5 9 exp -> NUM
and reports the uses of the symbols:
Terminals, with rules where they appear $end (0) 0 '*' (42) 3 '+' (43) 1 '-' (45) 2 '/' (47) 4 error (256) NUM (258) 5 Nonterminals, with rules where they appear $accept (8) on left: 0 exp (9) on left: 1 2 3 4 5, on right: 0 1 2 3 4
Bison then proceeds onto the automaton itself, describing each state with it set of items, also known as pointed rules. Each item is a production rule together with a point (marked by .) that the input cursor.
state 0 $accept -> . exp $ (rule 0) NUM shift, and go to state 1 exp go to state 2
This reads as follows: “state 0 corresponds to being at the very
beginning of the parsing, in the initial rule, right before the start
symbol (here, exp
). When the parser returns to this state right
after having reduced a rule that produced an exp
, the control
flow jumps to state 2. If there is no such transition on a nonterminal
symbol, and the lookahead is a 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.”
Even though the only active rule in state 0 seems to be rule 0, the
report lists NUM
as a lookahead token because NUM
can be
at the beginning of any rule deriving an exp
. By default Bison
reports the so-called core or kernel of the item set, but if
you want to see more detail you can invoke bison with
--report=itemset to list all the items, include those that can
be derived:
state 0 $accept -> . exp $ (rule 0) exp -> . exp '+' exp (rule 1) exp -> . exp '-' exp (rule 2) exp -> . exp '*' exp (rule 3) exp -> . exp '/' exp (rule 4) exp -> . NUM (rule 5) NUM shift, and go to state 1 exp go to state 2
In the state 1...
state 1 exp -> NUM . (rule 5) $default reduce using rule 5 (exp)
the rule 5, exp: NUM;, is completed. Whatever the lookahead token ($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 (exp: go to state 2).
state 2 $accept -> exp . $ (rule 0) exp -> exp . '+' exp (rule 1) exp -> exp . '-' exp (rule 2) exp -> exp . '*' exp (rule 3) exp -> exp . '/' exp (rule 4) $ shift, and go to state 3 '+' shift, and go to state 4 '-' shift, and go to state 5 '*' shift, and go to state 6 '/' shift, and go to state 7
In state 2, the automaton can only shift a symbol. For instance, because of the item exp -> exp . '+' exp, if the lookahead if +, it will be shifted on the parse stack, and the automaton control will jump to state 4, corresponding to the item exp -> exp '+' . exp. Since there is no default action, any other token than those listed above will trigger a syntax error.
The state 3 is named the final state, or the accepting state:
state 3 $accept -> exp $ . (rule 0) $default accept
the initial rule is completed (the start symbol and the end of input were read), the parsing exits successfully.
The interpretation of states 4 to 7 is straightforward, and is left to the reader.
state 4 exp -> exp '+' . exp (rule 1) NUM shift, and go to state 1 exp go to state 8 state 5 exp -> exp '-' . exp (rule 2) NUM shift, and go to state 1 exp go to state 9 state 6 exp -> exp '*' . exp (rule 3) NUM shift, and go to state 1 exp go to state 10 state 7 exp -> exp '/' . exp (rule 4) NUM shift, and go to state 1 exp go to state 11
As was announced in beginning of the report, State 8 conflicts: 1 shift/reduce:
state 8 exp -> exp . '+' exp (rule 1) exp -> exp '+' exp . (rule 1) exp -> exp . '-' exp (rule 2) exp -> exp . '*' exp (rule 3) exp -> exp . '/' exp (rule 4) '*' shift, and go to state 6 '/' shift, and go to state 7 '/' [reduce using rule 1 (exp)] $default reduce using rule 1 (exp)
Indeed, there are two actions associated to the lookahead /: either shifting (and going to state 7), or reducing rule 1. The conflict means that either the grammar is ambiguous, or the parser lacks information to make the right decision. Indeed the grammar is ambiguous, as, since we did not specify the precedence of /, the sentence NUM + NUM / NUM can be parsed as NUM + (NUM / NUM), which corresponds to shifting /, or as (NUM + NUM) / NUM, which corresponds to reducing rule 1.
Because in LALR(1) parsing a single decision can be made, Bison arbitrarily chose to disable the reduction, see Shift/Reduce Conflicts. Discarded actions are reported in between square brackets.
Note that all the previous states had a single possible action: either shifting the next token and going to the corresponding state, or reducing a single rule. In the other cases, i.e., when shifting and reducing is possible or when several reductions are possible, the lookahead is required to select the action. State 8 is one such state: if the lookahead is * or / 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 token is *, since we specified that * has higher precedence than +. More generally, some items are eligible only with some set of possible lookahead tokens. When run with --report=lookahead, Bison specifies these lookahead tokens:
state 8 exp -> exp . '+' exp (rule 1) exp -> exp '+' exp . [$, '+', '-', '/'] (rule 1) exp -> exp . '-' exp (rule 2) exp -> exp . '*' exp (rule 3) exp -> exp . '/' exp (rule 4) '*' shift, and go to state 6 '/' shift, and go to state 7 '/' [reduce using rule 1 (exp)] $default reduce using rule 1 (exp)
The remaining states are similar:
state 9 exp -> exp . '+' exp (rule 1) exp -> exp . '-' exp (rule 2) exp -> exp '-' exp . (rule 2) exp -> exp . '*' exp (rule 3) exp -> exp . '/' exp (rule 4) '*' shift, and go to state 6 '/' shift, and go to state 7 '/' [reduce using rule 2 (exp)] $default reduce using rule 2 (exp) state 10 exp -> exp . '+' exp (rule 1) exp -> exp . '-' exp (rule 2) exp -> exp . '*' exp (rule 3) exp -> exp '*' exp . (rule 3) exp -> exp . '/' exp (rule 4) '/' shift, and go to state 7 '/' [reduce using rule 3 (exp)] $default reduce using rule 3 (exp) state 11 exp -> exp . '+' exp (rule 1) exp -> exp . '-' exp (rule 2) exp -> exp . '*' exp (rule 3) exp -> exp . '/' exp (rule 4) exp -> exp '/' exp . (rule 4) '+' shift, and go to state 4 '-' shift, and go to state 5 '*' shift, and go to state 6 '/' shift, and go to state 7 '+' [reduce using rule 4 (exp)] '-' [reduce using rule 4 (exp)] '*' [reduce using rule 4 (exp)] '/' [reduce using rule 4 (exp)] $default reduce using rule 4 (exp)
Observe that state 11 contains conflicts not only due to the lack of precedence of / with respect to +, -, and *, but also because the associativity of / is not specified.
If a Bison grammar compiles properly but doesn't do what you want when it
runs, the yydebug
parser-trace feature can help you figure out why.
There are several means to enable compilation of trace facilities:
YYDEBUG
YYDEBUG
to a nonzero value when you compile the
parser. This is compliant with POSIX Yacc. You could use
-DYYDEBUG=1 as a compiler option or you could put #define
YYDEBUG 1 in the prologue of the grammar file (see The Prologue).
%debug
directive (see Bison Declaration Summary). This is a Bison extension, which will prove
useful when Bison will output parsers for languages that don't use a
preprocessor. Unless POSIX and Yacc portability matter to
you, this is
the preferred solution.
We suggest that you always enable the debug option so that debugging is always possible.
The trace facility outputs messages with macro calls of the form
YYFPRINTF (stderr,
format,
args)
where
format and args are the usual printf
format and variadic
arguments. If you define YYDEBUG
to a nonzero value but do not
define YYFPRINTF
, <stdio.h>
is automatically included
and YYFPRINTF
is defined to fprintf
.
Once you have compiled the program with trace facilities, the way to
request a trace is to store a nonzero value in the variable yydebug
.
You can do this by making the C code do it (in main
, perhaps), or
you can alter the value with a C debugger.
Each step taken by the parser when yydebug
is nonzero produces a
line or two of trace information, written on stderr
. The trace
messages tell you these things:
yylex
, what kind of token was read.
To make sense of this information, it helps to refer to the listing file produced by the Bison -v option (see Invoking Bison). This file shows the meaning of each state in terms of positions in various rules, and also what each state will do with each possible input token. As you read the successive trace messages, you can see that the parser is functioning according to its specification in the listing file. Eventually you will arrive at the place where something undesirable happens, and you will see which parts of the grammar are to blame.
The parser file is a C program and you can use C debuggers on it, but it's not easy to interpret what it is doing. The parser function is a finite-state machine interpreter, and aside from the actions it executes the same code over and over. Only the values of variables show where in the grammar it is working.
The debugging information normally gives the token type of each token
read, but not its semantic value. You can optionally define a macro
named YYPRINT
to provide a way to print the value. If you define
YYPRINT
, it should take three arguments. The parser will pass a
standard I/O stream, the numeric code for the token type, and the token
value (from yylval
).
Here is an example of YYPRINT
suitable for the multi-function
calculator (see Declarations for mfcalc
):
%{ static void print_token_value (FILE *, int, YYSTYPE); #define YYPRINT(file, type, value) print_token_value (file, type, value) %} ... %% ... %% ... static void print_token_value (FILE *file, int type, YYSTYPE value) { if (type == VAR) fprintf (file, "%s", value.tptr->name); else if (type == NUM) fprintf (file, "%d", value.val); }
The usual way to invoke Bison is as follows:
bison infile
Here infile is the grammar file name, which usually ends in .y. The parser file's name is made by replacing the .y with .tab.c and removing any leading directory. Thus, the bison foo.y file name yields foo.tab.c, and the bison hack/foo.y file name yields foo.tab.c. It's also possible, in case you are writing C++ code instead of C in your grammar file, to name it foo.ypp or foo.y++. Then, the output files will take an extension like the given one as input (respectively foo.tab.cpp and foo.tab.c++). This feature takes effect with all options that manipulate file names like -o or -d.
For example :
bison -d infile.yxx
will produce infile.tab.cxx and infile.tab.hxx, and
bison -d -o output.c++ infile.y
will produce output.c++ and outfile.h++.
For compatibility with POSIX, the standard Bison distribution also contains a shell script called yacc that invokes Bison with the -y option.
Bison supports both traditional single-letter options and mnemonic long option names. Long option names are indicated with -- instead of -. Abbreviations for option names are allowed as long as they are unique. When a long option takes an argument, like --file-prefix, connect the option name and the argument with =.
Here is a list of options that can be used with Bison, alphabetized by short option. It is followed by a cross key alphabetized by long option.
Operations modes:
#define
statements in addition to an enum
to associate token numbers with token
names.
Thus, the following shell script can substitute for Yacc, and the Bison
distribution contains such a script for compatibility with POSIX:
#! /bin/sh bison -y "$@"
The -y/--yacc option is intended for use with
traditional Yacc grammars. If your grammar uses a Bison extension
like %glr-parser, Bison might not be Yacc-compatible even if
this option is specified.
midrule-values
$2
in:
exp: '1' { $$ = 1; } '+' exp { $$ = $1 + $4; };
Also warn about mid-rule values that are used but not set.
For example, warn about unset $$
in the mid-rule action in:
exp: '1' { $1 = 1; } '+' exp { $$ = $2 + $4; };
These warnings are not enabled by default since they sometimes prove to
be false alarms in existing grammars employing the Yacc constructs
$0
or $-
n (where n is some positive integer).
yacc
all
none
error
A category can be turned off by prefixing its name with no-. For instance, -Wno-syntax will hide the warnings about unused variables.
Tuning the parser:
YYDEBUG
to 1 if it is not
already defined, so that the debugging facilities are compiled.
See Tracing Your Parser.
%language
was specified (see Bison Declaration Summary). Currently supported languages include C, C++, and Java.
language is case-insensitive.
This option is experimental and its effect may be modified in future
releases.
%locations
was specified. See Decl Summary.
%name-prefix "
prefix"
was specified.
See Decl Summary.
#line
preprocessor commands in the parser file.
Ordinarily Bison puts them in the parser file so that the C compiler
and debuggers will associate errors with your source file, the
grammar file. This option causes them to associate errors with the
parser file, treating it as an independent source file in its own right.
%skeleton
(see Bison Declaration Summary).
If file does not contain a /
, file is the name of a skeleton
file in the Bison installation directory.
If it does, file is an absolute file name or a file name relative to the
current working directory.
This is similar to how most shells resolve commands.
%token-table
was specified. See Decl Summary.
Adjust the output:
%defines
was specified, i.e., write an extra output
file containing macro definitions for the token type names defined in
the grammar, as well as a few other declarations. See Decl Summary.
--defines
except -d
does not accept a
file argument since POSIX Yacc requires that -d
can be bundled
with other short options.
%file-prefix
was specified, i.e., specify prefix to use
for all Bison output file names. See Decl Summary.
state
lookahead
state
and augments the description of the automaton with
each rule's lookahead set.
itemset
state
and augments the description of the automaton with
the full set of items for each state, instead of its core only.
%verbose
was specified, i.e., write an extra output
file containing verbose descriptions of the grammar and
parser. See Decl Summary.
The other output files' names are constructed from file as
described under the -v and -d options.
Here is a list of options, alphabetized by long option, to help you find the corresponding short option.
| Long Option | Short Option
|
|---|---|
| --debug | -t
|
| --defines=[file] |
|
| --file-prefix=prefix | -b prefix
|
| --graph=[file] | -g [file]
|
| --help | -h
|
| --language=language | -L language
|
| --locations |
|
| --name-prefix=prefix | -p prefix
|
| --no-lines | -l
|
| --output=file | -o file
|
| --print-datadir |
|
| --print-localedir |
|
| --report-file=file |
|
| --report=things | -r things
|
| --skeleton=file | -S file
|
| --token-table | -k
|
| --verbose | -v
|
| --version | -V
|
| --warnings | -W
|
| --xml=[file] | -x [file]
|
| --yacc | -y
|
The Yacc library contains default implementations of the
yyerror
and main
functions. These default
implementations are normally not useful, but POSIX requires
them. To use the Yacc library, link your program with the
-ly option. Note that Bison's implementation of the Yacc
library is distributed under the terms of the GNU General
Public License (see Copying).
If you use the Yacc library's yyerror
function, you should
declare yyerror
as follows:
int yyerror (char const *);
Bison ignores the int
value returned by this yyerror
.
If you use the Yacc library's main
function, your
yyparse
function should have the following type signature:
int yyparse (void);
The C++ LALR(1) parser is selected using the skeleton directive, %skeleton "lalr1.c", or the synonymous command-line option --skeleton=lalr1.c. See Decl Summary.
When run, bison will create several entities in the yy namespace. Use the %define namespace directive to change the namespace name, see Decl Summary. The various classes are generated in the following files:
position
and location
,
used for location tracking. See C++ Location Values.
stack
used by the parser.
The header is mandatory; you must either pass -d/--defines to bison, or use the %defines directive.
All these files are documented using Doxygen; run doxygen for a complete and accurate documentation.
The %union
directive works as for C, see The Collection of Value Types. In particular it produces a genuine
union
2, which have a few specific features in C++.
YYSTYPE
is defined but its use is discouraged: rather
you should refer to the parser's encapsulated type
yy::parser::semantic_type
.
Because objects have to be stored via pointers, memory is not
reclaimed automatically: using the %destructor
directive is the
only means to avoid leaks. See Freeing Discarded Symbols.
When the directive %locations
is used, the C++ parser supports
location tracking, see Locations Overview. Two
auxiliary classes define a position
, a single point in a file,
and a location
, a range composed of a pair of
position
s (possibly spanning several files).
The name of the file. It will always be handled as a pointer, the parser will never duplicate nor deallocate it. As an experimental feature you may change it to type* using %define filename_type "type".
Advance by height lines, resetting the column number.
Advance by width columns, without changing the line number.
Various forms of syntactic sugar for
columns
.
Report p on o like this: file:line.column, or line.column if file is null.
The first, inclusive, position of the range, and the first beyond.
Advance the
end
position.
Various forms of syntactic sugar.
The output files output.hh and output.cc
declare and define the parser class in the namespace yy
. The
class name defaults to parser
, but may be changed using
%define parser_class_name "name". The interface of
this class is detailed below. It can be extended using the
%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.
The types for semantics value and locations.
Build a new parser object. There are no arguments by default, unless %parse-param {type1 arg1} was used.
Get or set the stream used for tracing the parsing. It defaults to
std::cerr
.
Get or set the tracing level. Currently its value is either 0, no trace, or nonzero, full tracing.
The definition for this member function must be supplied by the user: the parser uses it to report a parser error occurring at l, described by m.
The parser invokes the scanner by calling yylex
. Contrary to C
parsers, C++ parsers are always pure: there is no point in using the
%define api.pure
directive. Therefore the interface is as follows.
Return the next token. Its type is the return value, its semantic value and location being yylval and yylloc. Invocations of %lex-param {type1 arg1} yield additional arguments.
This section demonstrates the use of a C++ parser with a simple but complete example. This example should be available on your system, ready to compile, in the directory ../bison/examples/calc++. It focuses on the use of Bison, therefore the design of the various C++ classes is very naive: no accessors, no encapsulation of members etc. We will use a Lex scanner, and more precisely, a Flex scanner, to demonstrate the various interaction. A hand written scanner is actually easier to interface with.
Of course the grammar is dedicated to arithmetics, a single
expression, possibly preceded by variable assignments. An
environment containing possibly predefined variables such as
one
and two
, is exchanged with the parser. An example
of valid input follows.
three := 3 seven := one + two * three seven * seven
To support a pure interface with the parser (and the scanner) the technique of the “parsing context” is convenient: a structure containing all the data to exchange. Since, in addition to simply launch the parsing, there are several auxiliary tasks to execute (open the file for parsing, instantiate the parser etc.), we recommend transforming the simple parsing context structure into a fully blown parsing driver class.
The declaration of this driver class, calc++-driver.hh, is as follows. The first part includes the CPP guard and imports the required standard library components, and the declaration of the parser class.
#ifndef CALCXX_DRIVER_HH # define CALCXX_DRIVER_HH # include <string> # include <map> # include "calc++-parser.hh"
Then comes the declaration of the scanning function. Flex expects
the signature of yylex
to be defined in the macro
YY_DECL
, and the C++ parser expects it to be declared. We can
factor both as follows.
// Tell Flex the lexer's prototype ... # define YY_DECL \ yy::calcxx_parser::token_type \ yylex (yy::calcxx_parser::semantic_type* yylval, \ yy::calcxx_parser::location_type* yylloc, \ calcxx_driver& driver) // ... and declare it for the parser's sake. YY_DECL;
The calcxx_driver
class is then declared with its most obvious
members.
// Conducting the whole scanning and parsing of Calc++. class calcxx_driver { public: calcxx_driver (); virtual ~calcxx_driver (); std::map<std::string, int> variables; int result;
To encapsulate the coordination with the Flex scanner, it is useful to have two members function to open and close the scanning phase.
// Handling the scanner. void scan_begin (); void scan_end (); bool trace_scanning;
Similarly for the parser itself.
// Run the parser. Return 0 on success. int parse (const std::string& f); std::string file; bool trace_parsing;
To demonstrate pure handling of parse errors, instead of simply dumping them on the standard error output, we will pass them to the compiler driver using the following two member functions. Finally, we close the class declaration and CPP guard.
// Error handling. void error (const yy::location& l, const std::string& m); void error (const std::string& m); }; #endif // ! CALCXX_DRIVER_HH
The implementation of the driver is straightforward. The parse
member function deserves some attention. The error
functions
are simple stubs, they should actually register the located error
messages and set error state.
#include "calc++-driver.hh" #include "calc++-parser.hh" calcxx_driver::calcxx_driver () : trace_scanning (false), trace_parsing (false) { variables["one"] = 1; variables["two"] = 2; } calcxx_driver::~calcxx_driver () { } int calcxx_driver::parse (const std::string &f) { file = f; scan_begin (); yy::calcxx_parser parser (*this); parser.set_debug_level (trace_parsing); int res = parser.parse (); scan_end (); return res; } void calcxx_driver::error (const yy::location& l, const std::string& m) { std::cerr << l << ": " << m << std::endl; } void calcxx_driver::error (const std::string& m) { std::cerr << m << std::endl; }
The parser definition file calc++-parser.yy starts by asking for the C++ LALR(1) skeleton, the creation of the parser header file, and specifies the name of the parser class. Because the C++ skeleton changed several times, it is safer to require the version you designed the grammar for.
%skeleton "lalr1.cc" /* -*- C++ -*- */ %require "2.4.1" %defines %define parser_class_name "calcxx_parser"
Then come the declarations/inclusions needed to define the
%union
. Because the parser uses the parsing driver and
reciprocally, both cannot include the header of the other. Because the
driver's header needs detailed knowledge about the parser class (in
particular its inner types), it is the parser's header which will simply
use a forward declaration of the driver.
See %code.
%code requires { # include <string> class calcxx_driver; }
The driver is passed by reference to the parser and to the scanner. This provides a simple but effective pure interface, not relying on global variables.
// The parsing context. %parse-param { calcxx_driver& driver } %lex-param { calcxx_driver& driver }
Then we request the location tracking feature, and initialize the first location's file name. Afterwards new locations are computed relatively to the previous locations: the file name will be automatically propagated.
%locations %initial-action { // Initialize the initial location. @$.begin.filename = @$.end.filename = &driver.file; };
Use the two following directives to enable parser tracing and verbose error messages.
%debug %error-verbose
Semantic values cannot use “real” objects, but only pointers to them.
// Symbols. %union { int ival; std::string *sval; };
The code between %code { and } is output in the *.cc file; it needs detailed knowledge about the driver.
%code { # include "calc++-driver.hh" }
The token numbered as 0 corresponds to end of file; the following line
allows for nicer error messages referring to “end of file” instead
of “$end”. Similarly user friendly named are provided for each
symbol. Note that the tokens names are prefixed by TOKEN_
to
avoid name clashes.
%token END 0 "end of file" %token ASSIGN ":=" %token <sval> IDENTIFIER "identifier" %token <ival> NUMBER "number" %type <ival> exp
To enable memory deallocation during error recovery, use
%destructor
.
%printer { debug_stream () << *$$; } "identifier" %destructor { delete $$; } "identifier" %printer { debug_stream () << $$; } <ival>
The grammar itself is straightforward.
%% %start unit; unit: assignments exp { driver.result = $2; }; assignments: assignments assignment {} | /* Nothing. */ {}; assignment: "identifier" ":=" exp { driver.variables[*$1] = $3; delete $1; }; %left '+' '-'; %left '*' '/'; exp: exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | exp '*' exp { $$ = $1 * $3; } | exp '/' exp { $$ = $1 / $3; } | "identifier" { $$ = driver.variables[*$1]; delete $1; } | "number" { $$ = $1; }; %%
Finally the error
member function registers the errors to the
driver.
void yy::calcxx_parser::error (const yy::calcxx_parser::location_type& l, const std::string& m) { driver.error (l, m); }
The Flex scanner first includes the driver declaration, then the parser's to get the set of defined tokens.
%{ /* -*- C++ -*- */ # include <cstdlib> # include <errno.h> # include <limits.h> # include <string> # include "calc++-driver.hh" # include "calc++-parser.hh" /* Work around an incompatibility in flex (at least versions 2.5.31 through 2.5.33): it generates code that does not conform to C89. See Debian bug 333231 <http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=333231>. */ # undef yywrap # define yywrap() 1 /* By default yylex returns int, we use token_type. Unfortunately yyterminate by default returns 0, which is not of token_type. */ #define yyterminate() return token::END %}
Because there is no #include
-like feature we don't need
yywrap
, we don't need unput
either, and we parse an
actual file, this is not an interactive session with the user.
Finally we enable the scanner tracing features.
%option noyywrap nounput batch debug
Abbreviations allow for more readable rules.
id [a-zA-Z][a-zA-Z_0-9]* int [0-9]+ blank [ \t]
The following paragraph suffices to track locations accurately. Each
time 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
cursor is adjusted, and each time blanks are matched, the begin cursor
is moved onto the end cursor to effectively ignore the blanks
preceding tokens. Comments would be treated equally.
%{ # define YY_USER_ACTION yylloc->columns (yyleng); %} %% %{ yylloc->step (); %} {blank}+ yylloc->step (); [\n]+ yylloc->lines (yyleng); yylloc->step ();
The rules are simple, just note the use of the driver to report errors.
It is convenient to use a typedef to shorten
yy::calcxx_parser::token::identifier
into
token::identifier
for instance.
%{ typedef yy::calcxx_parser::token token; %} /* Convert ints to the actual type of tokens. */ [-+*/] return yy::calcxx_parser::token_type (yytext[0]); ":=" return token::ASSIGN; {int} { errno = 0; long n = strtol (yytext, NULL, 10); if (! (INT_MIN <= n && n <= INT_MAX && errno != ERANGE)) driver.error (*yylloc, "integer is out of range"); yylval->ival = n; return token::NUMBER; } {id} yylval->sval = new std::string (yytext); return token::IDENTIFIER; . driver.error (*yylloc, "invalid character"); %%
Finally, because the scanner related driver's member function depend on the scanner's data, it is simpler to implement them in this file.
void calcxx_driver::scan_begin () { yy_flex_debug = trace_scanning; if (file == "-") yyin = stdin; else if (!(yyin = fopen (file.c_str (), "r"))) { error (std::string ("cannot open ") + file); exit (1); } } void calcxx_driver::scan_end () { fclose (yyin); }
The top level file, calc++.cc, poses no problem.
#include <iostream> #include "calc++-driver.hh" int main (int argc, char *argv[]) { calcxx_driver driver; for (++argv; argv[0]; ++argv) if (*argv == std::string ("-p")) driver.trace_parsing = true; else if (*argv == std::string ("-s")) driver.trace_scanning = true; else if (!driver.parse (*argv)) std::cout << driver.result << std::endl; }
(The current Java interface is experimental and may evolve. More user feedback will help to stabilize it.)
The Java parser skeletons are selected using the %language "Java"
directive or the -L java/--language=java option.
When generating a Java parser, bison
basename.y
will create
a single Java source file named basename.java. Using an
input file without a .y suffix is currently broken. The basename
of the output file can be changed by the %file-prefix
directive
or the -p/--name-prefix option. The entire output file
name can be changed by the %output
directive or the
-o/--output option. The output file contains a single
class for the parser.
You can create documentation for generated parsers using Javadoc.
Contrary to C parsers, Java parsers do not use global variables; the
state of the parser is always local to an instance of the parser class.
Therefore, all Java parsers are “pure”, and the %pure-parser
and %define api.pure
directives does not do anything when used in
Java.
Push parsers are currently unsupported in Java and %define
api.push_pull
have no effect.
GLR parsers are currently unsupported in Java. Do not use the
glr-parser
directive.
No header file can be generated for Java parsers. Do not use the
%defines
directive or the -d/--defines options.
Currently, support for debugging and verbose errors are always compiled
in. Thus the %debug
and %token-table
directives and the
-t/--debug and -k/--token-table
options have no effect. This may change in the future to eliminate
unused code in the generated parser, so use %debug
and
%verbose-error
explicitly if needed. Also, in the future the
%token-table
directive might enable a public interface to
access the token names and codes.
There is no %union
directive in Java parsers. Instead, the
semantic values' types (class names) should be specified in the
%type
or %token
directive:
%type <Expression> expr assignment_expr term factor %type <Integer> number
By default, the semantic stack is declared to have Object
members,
which means that the class types you specify can be of any class.
To improve the type safety of the parser, you can declare the common
superclass of all the semantic values using the %define stype
directive. For example, after the following declaration:
%define stype "ASTNode"
any %type
or %token
specifying a semantic type which
is not a subclass of ASTNode, will cause a compile-time error.
Types used in the directives may be qualified with a package name. Primitive data types are accepted for Java version 1.5 or later. Note that in this case the autoboxing feature of Java 1.5 will be used. Generic types may not be used; this is due to a limitation in the implementation of Bison, and may change in future releases.
Java parsers do not support %destructor
, since the language
adopts garbage collection. The parser will try to hold references
to semantic values for as little time as needed.
Java parsers do not support %printer
, as toString()
can be used to print the semantic values. This however may change
(in a backwards-compatible way) in future versions of Bison.
When the directive %locations
is used, the Java parser
supports location tracking, see Locations Overview.
An auxiliary user-defined class defines a position, a single point
in a file; Bison itself defines a class representing a location,
a range composed of a pair of positions (possibly spanning several
files). The location class is an inner class of the parser; the name
is Location
by default, and may also be renamed using
%define location_type "
class-name.
The location class treats the position as a completely opaque value.
By default, the class name is Position
, but this can be changed
with %define position_type "
class-name"
. This class must
be supplied by the user.
The first, inclusive, position of the range, and the first beyond.
Create a
Location
denoting an empty range located at a given point.
Create a
Location
from the endpoints of the range.
Prints the range represented by the location. For this to work properly, the position class should override the
equals
andtoString
methods appropriately.
The name of the generated parser class defaults to YYParser
. The
YY
prefix may be changed using the %name-prefix
directive
or the -p/--name-prefix option. Alternatively, use
%define parser_class_name "
name"
to give a custom name to
the class. The interface of this class is detailed below.
By default, the parser class has package visibility. A declaration
%define public
will change to public visibility. Remember that,
according to the Java language specification, the name of the .java
file should match the name of the class in this case. Similarly, you can
use abstract
, final
and strictfp
with the
%define
declaration to add other modifiers to the parser class.
The Java package name of the parser class can be specified using the
%define package
directive. The superclass and the implemented
interfaces of the parser class can be specified with the %define
extends
and %define implements
directives.
The parser class defines an inner class, Location
, that is used
for location tracking (see Java Location Values), and a inner
interface, Lexer
(see Java Scanner Interface). Other than
these inner class/interface, and the members described in the interface
below, all the other members and fields are preceded with a yy
or
YY
prefix to avoid clashes with user code.
The parser class can be extended using the %parse-param
directive. Each occurrence of the directive will add a protected
final
field to the parser class, and an argument to its constructor,
which initialize them automatically.
Token names defined by %token
and the predefined EOF
token
name are added as constant fields to the parser class.
Build a new parser object with embedded
%code lexer
. There are no parameters, unless%parse-param
s and/or%lex-param
s are used.
Build a new parser object using the specified scanner. There are no additional parameters unless
%parse-param
s are used.If the scanner is defined by
%code lexer
, this constructor is declaredprotected
and is called automatically with a scanner created with the correct%lex-param
s.
Run the syntactic analysis, and return
true
on success,false
otherwise.
During the syntactic analysis, return
true
if recovering from a syntax error. See Error Recovery.
Get or set the stream used for tracing the parsing. It defaults to
System.err
.
Get or set the tracing level. Currently its value is either 0, no trace, or nonzero, full tracing.
There are two possible ways to interface a Bison-generated Java parser
with a scanner: the scanner may be defined by %code lexer
, or
defined elsewhere. In either case, the scanner has to implement the
Lexer
inner interface of the parser class.
In the first case, the body of the scanner class is placed in
%code lexer
blocks. If you want to pass parameters from the
parser constructor to the scanner constructor, specify them with
%lex-param
; they are passed before %parse-param
s to the
constructor.
In the second case, the scanner has to implement the Lexer
interface,
which is defined within the parser class (e.g., YYParser.Lexer
).
The constructor of the parser object will then accept an object
implementing the interface; %lex-param
is not used in this
case.
In both cases, the scanner has to implement the following methods.
This method is defined by the user to emit an error message. The first parameter is omitted if location tracking is not active. Its type can be changed using
%define location_type "
class-name".
Return the next token. Its type is the return value, its semantic value and location are saved and returned by the ther methods in the interface.
Use
%define lex_throws
to specify any uncaught exceptions. Default isjava.io.IOException
.
Return respectively the first position of the last token that
yylex
returned, and the first position beyond it. These methods are not needed unless location tracking is active.The return type can be changed using
%define position_type "
class-name".
Return the semantical value of the last token that yylex returned.
The return type can be changed using
%define stype "
class-name".
The following special constructs can be uses in Java actions. Other analogous C action features are currently unavailable for Java.
Use %define throws
to specify any uncaught exceptions from parser
actions, and initial actions specified by %initial-action
.
The semantic value for the nth component of the current rule. This may not be assigned to. See Java Semantic Values.
The semantic value for the grouping made by the current rule. As a value, this is in the base type (
Object
or as specified by%define stype
) as in not cast to the declared subtype because casts are not allowed on the left-hand side of Java assignments. Use an explicit Java cast if the correct subtype is needed. See Java Semantic Values.
Same as
$$
since Java always allow assigning to the base type. Perhaps we should use this and$<>$
for the value and$$
for setting the value but there is currently no easy way to distinguish these constructs. See Java Semantic Values.
The location information of the nth component of the current rule. This may not be assigned to. See Java Location Values.
The location information of the grouping made by the current rule. See Java Location Values.
Return immediately from the parser, indicating failure. See Java Parser Interface.
Return immediately from the parser, indicating success. See Java Parser Interface.
Start error recovery without printing an error message. See Error Recovery.
Return whether error recovery is being done. In this state, the parser reads token until it reaches a known state, and then restarts normal operation. See Error Recovery.
Print an error message using the
yyerror