This file documents the Bison parser generator.
Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998, 1999,
-2000, 2001
+2000, 2001, 2002
Free Software Foundation, Inc.
Permission is granted to make and distribute verbatim copies of
@page
@vskip 0pt plus 1filll
Copyright @copyright{} 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998,
-1999, 2000, 2001
+1999, 2000, 2001, 2002
Free Software Foundation, Inc.
@sp 2
@dfn{nonterminal symbols}; those which can't be subdivided are called
@dfn{terminal symbols} or @dfn{token types}. We call a piece of input
corresponding to a single terminal symbol a @dfn{token}, and a piece
-corresponding to a single nonterminal symbol a @dfn{grouping}.@refill
+corresponding to a single nonterminal symbol a @dfn{grouping}.
We can use the C language as an example of what symbols, terminal and
nonterminal, mean. The tokens of C are identifiers, constants (numeric and
@emph{any} integer constant is grammatically valid in that position. The
precise value of the constant is irrelevant to how to parse the input: if
@samp{x+4} is grammatical then @samp{x+1} or @samp{x+3989} is equally
-grammatical.@refill
+grammatical.
But the precise value is very important for what the input means once it is
parsed. A compiler is useless if it fails to distinguish between 4, 1 and
@code{INTEGER}, @code{IDENTIFIER} or @code{','}. It tells everything
you need to know to decide where the token may validly appear and how to
group it with other tokens. The grammar rules know nothing about tokens
-except their types.@refill
+except their types.
The semantic value has all the rest of the information about the
meaning of the token, such as the value of an integer, or the name of an
those cases your code should respect the identifiers reserved by those
headers. On some non-@sc{gnu} hosts, @code{<alloca.h>},
@code{<stddef.h>}, and @code{<stdlib.h>} are included as needed to
-declare memory allocators and related types. In the same situation,
-C++ parsers may include @code{<cstddef>} and @code{<cstdlib>} instead.
+declare memory allocators and related types.
Other system headers may be included if you define @code{YYDEBUG} to a
nonzero value (@pxref{Debugging, ,Debugging Your Parser}).
represents a token type. The same text used in Bison rules to stand for
this token type is also a C expression for the numeric code for the type.
This works in two ways. If the token type is a character literal, then its
-numeric code is the ASCII code for that character; you can use the same
+numeric code is that of the character; you can use the same
character literal in the lexical analyzer to express the number. If the
token type is an identifier, that identifier is defined by Bison as a C
macro whose definition is the appropriate number. In this example,
@example
@group
/* Lexical analyzer returns a double floating point
- number on the stack and the token NUM, or the ASCII
- character read if not a number. Skips all blanks
+ number on the stack and the token NUM, or the numeric code
+ of the character read if not a number. Skips all blanks
and tabs, returns 0 for EOF. */
#include <ctype.h>
@code{yyerrok}, a macro defined automatically by Bison; its meaning is
that error recovery is complete (@pxref{Error Recovery}). Note the
difference between @code{yyerrok} and @code{yyerror}; neither one is a
-misprint.@refill
+misprint.
This form of error recovery deals with syntax errors. There are other
kinds of errors; for example, division by zero, which raises an exception
(@code{VAR} or @code{FNCT}) is returned to @code{yyparse}. If it is not
already in the table, then it is installed as a @code{VAR} using
@code{putsym}. Again, a pointer and its type (which must be @code{VAR}) is
-returned to @code{yyparse}.@refill
+returned to @code{yyparse}.
No change is needed in the handling of numeric values and arithmetic
operators in @code{yylex}.
All the usual escape sequences used in character literals in C can be
used in Bison as well, but you must not use the null character as a
-character literal because its ASCII code, zero, is the code @code{yylex}
+character literal because its numeric code, zero, is the code @code{yylex}
returns for end-of-input (@pxref{Calling Convention, ,Calling Convention
for @code{yylex}}).
The value returned by @code{yylex} is always one of the terminal symbols
(or 0 for end-of-input). Whichever way you write the token type in the
grammar rules, you write it the same way in the definition of @code{yylex}.
-The numeric code for a character token type is simply the ASCII code for
+The numeric code for a character token type is simply the numeric code of
the character, so @code{yylex} can use the identical character constant to
generate the requisite code. Each named token type becomes a C macro in
the parser file, so @code{yylex} can use the name to stand for the code.
into a separate header file @file{@var{name}.tab.h} which you can include
in the other source files that need it. @xref{Invocation, ,Invoking Bison}.
+The @code{yylex} function must use the same character set and encoding
+that was used by Bison. For example, if you run Bison in an
+@sc{ascii} environment, but then compile and run the resulting program
+in an environment that uses an incompatible character set like
+@sc{ebcdic}, the resulting program will probably not work because the
+tables generated by Bison will assume @sc{ascii} numeric values for
+character tokens. Portable grammars should avoid non-@sc{ascii}
+character tokens, as implementations in practice often use different
+and incompatible extensions in this area. However, it is standard
+practice for software distributions to contain C source files that
+were generated by Bison in an @sc{ascii} environment, so installers on
+platforms that are incompatible with @sc{ascii} must rebuild those
+files before compiling them.
+
The symbol @code{error} is a terminal symbol reserved for error recovery
(@pxref{Error Recovery}); you shouldn't use it for any other purpose.
-In particular, @code{yylex} should never return this value.
+In particular, @code{yylex} should never return this value. The default
+value of the error token is 256, unless you explicitly assigned 256 to
+one of your tokens with a @code{%token} declaration.
@node Rules
@section Syntax of Grammar Rules
The sum is stored into @code{$$} so that it becomes the semantic value of
the addition-expression just recognized by the rule. If there were a
useful semantic value associated with the @samp{+} token, it could be
-referred to as @code{$2}.@refill
+referred to as @code{$2}.
+
+Note that the vertical-bar character @samp{|} is really a rule
+separator, and actions are attached to a single rule. This is a
+difference with tools like Flex, for which @samp{|} stands for either
+``or'', or ``the same action as that of the next rule''. In the
+following example, the action is triggered only when @samp{b} is found:
+
+@example
+@group
+a-or-b: 'a'|'b' @{ a_or_b_found = 1; @};
+@end group
+@end example
@cindex default action
If you don't specify an action for a rule, Bison supplies a default:
must declare a choice among these types for each terminal or nonterminal
symbol that can have a semantic value. Then each time you use @code{$$} or
@code{$@var{n}}, its data type is determined by which symbol it refers to
-in the rule. In this example,@refill
+in the rule. In this example,
@example
@group
@code{$1} and @code{$3} refer to instances of @code{exp}, so they all
have the data type declared for the nonterminal symbol @code{exp}. If
@code{$2} were used, it would have the data type declared for the
-terminal symbol @code{'+'}, whatever that might be.@refill
+terminal symbol @code{'+'}, whatever that might be.
Alternatively, you can specify the data type when you refer to the value,
by inserting @samp{<@var{type}>} after the @samp{$} at the beginning of the
@noindent
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 ASCII characters.
+with each other or with normal characters.
In the event that the stack type is a union, you must augment the
@code{%token} or other token declaration to include the data type
@subsection A Pure (Reentrant) Parser
@cindex reentrant parser
@cindex pure parser
-@findex %pure_parser
+@findex %pure-parser
A @dfn{reentrant} program is one which does not alter in the course of
execution; in other words, it consists entirely of @dfn{pure} (read-only)
including @code{yylval} and @code{yylloc}.)
Alternatively, you can generate a pure, reentrant parser. The Bison
-declaration @code{%pure_parser} says that you want the parser to be
+declaration @code{%pure-parser} says that you want the parser to be
reentrant. It looks like this:
@example
-%pure_parser
+%pure-parser
@end example
The result is that the communication variables @code{yylval} and
@code{YYSTYPE}, as well as a few @code{extern} variable declarations.
If the parser output file is named @file{@var{name}.c} then this file
-is named @file{@var{name}.h}.@refill
+is named @file{@var{name}.h}.
This output file is essential if you wish to put the definition of
@code{yylex} in a separate source file, because @code{yylex} needs to
be able to refer to token type codes and the variable
-@code{yylval}. @xref{Token Values, ,Semantic Values of Tokens}.@refill
+@code{yylval}. @xref{Token Values, ,Semantic Values of Tokens}.
@item %file-prefix="@var{prefix}"
Specify a prefix to use for all Bison output file names. The names are
chosen as if the input file were named @file{@var{prefix}.y}.
-@c @item %header_extension
+@c @item %header-extension
@c Specify the extension of the parser header file generated when
@c @code{%define} or @samp{-d} are used.
@c
@c For example, a grammar file named @file{foo.ypp} and containing a
-@c @code{%header_extension .hh} directive will produce a header file
+@c @code{%header-extension .hh} directive will produce a header file
@c named @file{foo.tab.hh}
@item %locations
Rename the external symbols used in the parser so that they start with
@var{prefix} instead of @samp{yy}. The precise list of symbols renamed
is @code{yyparse}, @code{yylex}, @code{yyerror}, @code{yynerrs},
-@code{yylval}, @code{yychar} and @code{yydebug}. For example, if you
-use @samp{%name-prefix="c_"}, the names become @code{c_parse},
-@code{c_lex}, and so on. @xref{Multiple Parsers, ,Multiple Parsers in
-the Same Program}.
+@code{yylval}, @code{yychar}, @code{yydebug}, and possible
+@code{yylloc}. For example, if you use @samp{%name-prefix="c_"}, the
+names become @code{c_parse}, @code{c_lex}, and so on. @xref{Multiple
+Parsers, ,Multiple Parsers in the Same Program}.
@item %no-parser
Do not include any C code in the parser file; generate tables only. The
Request a pure (reentrant) parser program (@pxref{Pure Decl, ,A Pure
(Reentrant) Parser}).
-@c @item %source_extension
+@c @item %source-extension
@c Specify the extension of the parser output file.
@c
@c For example, a grammar file named @file{foo.yy} and containing a
-@c @code{%source_extension .cpp} directive will produce a parser file
+@c @code{%source-extension .cpp} directive will produce a parser file
@c named @file{foo.tab.cpp}
-@item %token_table
+@item %token-table
Generate an array of token names in the parser file. The name of the
array is @code{yytname}; @code{yytname[@var{i}]} is the name of the
token whose internal Bison token code number is @var{i}. The first three
contains @samp{"*"*"}. (In C, that would be written as
@code{"\"*\"*\""}).
-When you specify @code{%token_table}, Bison also generates macro
+When you specify @code{%token-table}, Bison also generates macro
definitions for macros @code{YYNTOKENS}, @code{YYNNTS}, and
@code{YYNRULES}, and @code{YYNSTATES}:
operator precedence and the unresolved ones.
The file's name is made by removing @samp{.tab.c} or @samp{.c} from
-the parser output file name, and adding @samp{.output} instead.@refill
+the parser output file name, and adding @samp{.output} instead.
Therefore, if the input file is @file{foo.y}, then the parser file is
called @file{foo.tab.c} by default. As a consequence, the verbose
-output file is called @file{foo.output}.@refill
+output file is called @file{foo.output}.
@item %yacc
-@itemx %fixed-output-files
Pretend the option @option{--yacc} was given, i.e., imitate Yacc,
including its naming conventions. @xref{Bison Options}, for more.
@end table
To do this, use the @samp{-d} option when you run Bison, so that it will
write these macro definitions into a separate header file
@file{@var{name}.tab.h} which you can include in the other source files
-that need it. @xref{Invocation, ,Invoking Bison}.@refill
+that need it. @xref{Invocation, ,Invoking Bison}.
@menu
* Calling Convention:: How @code{yyparse} calls @code{yylex}.
@end smallexample
The @code{yytname} table is generated only if you use the
-@code{%token_table} declaration. @xref{Decl Summary}.
+@code{%token-table} declaration. @xref{Decl Summary}.
@end itemize
@node Token Values
@node Pure Calling
@subsection Calling Conventions for Pure Parsers
-When you use the Bison declaration @code{%pure_parser} to request a
+When you use the Bison declaration @code{%pure-parser} to request a
pure, reentrant parser, the global communication variables @code{yylval}
and @code{yylloc} cannot be used. (@xref{Pure Decl, ,A Pure (Reentrant)
Parser}.) In such parsers the two global variables are replaced by
the proper object type, or you can declare it as @code{void *} and
access the contents as shown above.
-You can use @samp{%pure_parser} to request a reentrant parser without
+You can use @samp{%pure-parser} to request a reentrant parser without
also using @code{YYPARSE_PARAM}. Then you should call @code{yyparse}
with no arguments, as usual.
@item $<@var{typealt}>@var{n}
Like @code{$@var{n}} but specifies alternative @var{typealt} in the
union specified by the @code{%union} declaration.
-@xref{Action Types, ,Data Types of Values in Actions}.@refill
+@xref{Action Types, ,Data Types of Values in Actions}.
@item YYABORT;
Return immediately from @code{yyparse}, indicating failure.
@code{%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 @code{%prec}
-modifier for rules.@refill
+modifier for rules.
The @code{%prec} modifier declares the precedence of a particular rule by
specifying a terminal symbol whose precedence should be used for that rule.
@node Debugging
@chapter Debugging Your Parser
-@findex YYDEBUG
@findex yydebug
@cindex debugging
@cindex tracing the parser
If a Bison grammar compiles properly but doesn't do what you want when it
runs, the @code{yydebug} parser-trace feature can help you figure out why.
-To enable compilation of trace facilities, you must define the macro
-@code{YYDEBUG} to a nonzero value when you compile the parser. You
-could use @samp{-DYYDEBUG=1} as a compiler option or you could put
-@samp{#define YYDEBUG 1} in the prologue of the grammar file
-(@pxref{Prologue, , The Prologue}). Alternatively, use the @samp{-t}
-option when you run Bison (@pxref{Invocation, ,Invoking Bison}) or the
-@code{%debug} declaration (@pxref{Decl Summary, ,Bison Declaration
-Summary}). We suggest that you always define @code{YYDEBUG} so that
-debugging is always possible.
+There are several means to enable compilation of trace facilities:
+
+@table @asis
+@item the macro @code{YYDEBUG}
+@findex YYDEBUG
+Define the macro @code{YYDEBUG} to a nonzero value when you compile the
+parser. This is compliant with POSIX Yacc. You could use
+@samp{-DYYDEBUG=1} as a compiler option or you could put @samp{#define
+YYDEBUG 1} in the prologue of the grammar file (@pxref{Prologue, , The
+Prologue}).
+
+@item the option @option{-t}, @option{--debug}
+Use the @samp{-t} option when you run Bison (@pxref{Invocation,
+,Invoking Bison}). This is POSIX compliant too.
+
+@item the directive @samp{%debug}
+@findex %debug
+Add the @code{%debug} directive (@pxref{Decl Summary, ,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. Useless POSIX and Yacc portability matter to you, this is
+the preferred solution.
+@end table
+
+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
-@code{YYFPRINTF (YYSTDERR, @var{format}, @var{args})} where
+@code{YYFPRINTF (stderr, @var{format}, @var{args})} where
@var{format} and @var{args} are the usual @code{printf} format and
arguments. If you define @code{YYDEBUG} to a nonzero value but do not
define @code{YYFPRINTF}, @code{<stdio.h>} is automatically included
-and the macros are defined to @code{fprintf} and @code{stderr}. In
-the same situation, C++ parsers include @code{<cstdio.h>} instead, and
-use @code{std::fprintf} and @code{std::stderr}.
+and @code{YYPRINTF} is defined to @code{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 @code{yydebug}.
@need 1750
@item -y
@itemx --yacc
-@itemx --fixed-output-files
Equivalent to @samp{-o y.tab.c}; the parser output file is called
@file{y.tab.c}, and the other outputs are called @file{y.output} and
@file{y.tab.h}. The purpose of this option is to imitate Yacc's output
file name conventions. Thus, the following shell script can substitute
-for Yacc:@refill
+for Yacc:
@example
bison -y $*
environment variable @code{BISON_SIMPLE} to the path of the file will
cause Bison to use that copy instead.
-When the @samp{%semantic_parser} declaration is used, Bison copies from
+When the @samp{%semantic-parser} declaration is used, Bison copies from
a file called @file{bison.hairy} instead. The location of this file can
also be specified or overridden in a similar fashion, with the
@code{BISON_HAIRY} environment variable.
\line{ --debug \leaderfill -t}
\line{ --defines \leaderfill -d}
\line{ --file-prefix \leaderfill -b}
-\line{ --fixed-output-files \leaderfill -y}
\line{ --graph \leaderfill -g}
\line{ --help \leaderfill -h}
\line{ --name-prefix \leaderfill -p}
--debug -t
--defines=@var{defines-file} -d
--file-prefix=@var{prefix} -b @var{file-prefix}
---fixed-output-files --yacc -y
--graph=@var{graph-file} -d
--help -h
--name-prefix=@var{prefix} -p @var{name-prefix}
--token-table -k
--verbose -v
--version -V
+--yacc -y
@end example
@end ifinfo
@cindex symbols in Bison, table of
@table @code
+@item @@$
+In an action, the location of the left-hand side of the rule.
+ @xref{Locations, , Locations Overview}.
+
+@item @@@var{n}
+In an action, the location of the @var{n}-th symbol of the right-hand
+side of the rule. @xref{Locations, , Locations Overview}.
+
+@item $$
+In an action, the semantic value of the left-hand side of the rule.
+@xref{Actions}.
+
+@item $@var{n}
+In an action, the semantic value of the @var{n}-th symbol of the
+right-hand side of the rule. @xref{Actions}.
+
@item error
A token name reserved for error recovery. This token may be used in
grammar rules so as to allow the Bison parser to recognize an error in
Macro to discard a value from the parser stack and fake a look-ahead
token. @xref{Action Features, ,Special Features for Use in Actions}.
+@item YYDEBUG
+Macro to define to equip the parser with tracing code. @xref{Debugging,
+,Debugging Your Parser}.
+
@item YYERROR
Macro to pretend that a syntax error has just been detected: call
@code{yyerror} and then perform normal error recovery if possible
Bison declaration to set tge prefix of the output files. @xref{Decl
Summary}.
-@c @item %source_extension
+@c @item %source-extension
@c Bison declaration to specify the generated parser output file extension.
@c @xref{Decl Summary}.
@c
-@c @item %header_extension
+@c @item %header-extension
@c Bison declaration to specify the generated parser header file extension
@c if required. @xref{Decl Summary}.
values. @xref{Union Decl, ,The Collection of Value Types}.
@end table
+@sp 1
+
These are the punctuation and delimiters used in Bison input:
@table @samp
projects / bison.git / blobdiff