@c the smallbook format.
@c @smallbook
-@c Set following if you have the new `shorttitlepage' command
-@c @clear shorttitlepage-enabled
-@c @set shorttitlepage-enabled
-
@c Set following if you want to document %default-prec and %no-default-prec.
@c This feature is experimental and may change in future Bison versions.
@c @set defaultprec
-@c ISPELL CHECK: done, 14 Jan 1993 --bob
-
-@c Check COPYRIGHT dates. should be updated in the titlepage, ifinfo
-@c titlepage; should NOT be changed in the GPL. --mew
-
-@c FIXME: I don't understand this `iftex'. Obsolete? --akim.
-@iftex
+@ifnotinfo
@syncodeindex fn cp
@syncodeindex vr cp
@syncodeindex tp cp
-@end iftex
+@end ifnotinfo
@ifinfo
@synindex fn cp
@synindex vr cp
* bison: (bison). @acronym{GNU} parser generator (Yacc replacement).
@end direntry
-@ifset shorttitlepage-enabled
-@shorttitlepage Bison
-@end ifset
@titlepage
@title Bison
@subtitle The Yacc-compatible Parser Generator
* How Can I Reset the Parser:: @code{yyparse} Keeps some State
* Strings are Destroyed:: @code{yylval} Loses Track of Strings
* Implementing Gotos/Loops:: Control Flow in the Calculator
+* Multiple start-symbols:: Factoring closely related grammars
+* Secure? Conform?:: Is Bison @acronym{POSIX} safe?
+* I can't build Bison:: Troubleshooting
+* Where can I find help?:: Troubleshouting
+* Bug Reports:: Troublereporting
+* Other Languages:: Parsers in Java and others
+* Beta Testing:: Experimenting development versions
+* Mailing Lists:: Meeting other Bison users
Copying This Manual
@unnumbered Introduction
@cindex introduction
-@dfn{Bison} is a general-purpose parser generator that converts a
-grammar description for an @acronym{LALR}(1) context-free grammar into a C
-program to parse that grammar. Once you are proficient with Bison,
-you may use it to develop a wide range of language parsers, from those
+@dfn{Bison} is a general-purpose parser generator that converts a grammar
+description for an @acronym{LALR}(1) or @acronym{GLR} context-free grammar
+into a C or C++ program to parse that grammar. Once you are proficient with
+Bison, you can use it to develop a wide range of language parsers, from those
used in simple desk calculators to complex programming languages.
Bison is upward compatible with Yacc: all properly-written Yacc grammars
ought to work with Bison with no change. Anyone familiar with Yacc
should be able to use Bison with little trouble. You need to be fluent in
-C programming in order to use Bison or to understand this manual.
+C or C++ programming in order to use Bison or to understand this manual.
We begin with tutorial chapters that explain the basic concepts of using
Bison and show three explained examples, each building on the last. If you
@node Conditions
@unnumbered Conditions for Using Bison
-As of Bison version 1.24, we have changed the distribution terms for
-@code{yyparse} to permit using Bison's output in nonfree programs when
-Bison is generating C code for @acronym{LALR}(1) parsers. Formerly, these
+The distribution terms for Bison-generated parsers permit using the
+parsers in nonfree programs. Before Bison version 2.2, these extra
+permissions applied only when Bison was generating @acronym{LALR}(1)
+parsers in C@. And before Bison version 1.24, Bison-generated
parsers could be used only in programs that were free software.
The other @acronym{GNU} programming tools, such as the @acronym{GNU} C
The output of the Bison utility---the Bison parser file---contains a
verbatim copy of a sizable piece of Bison, which is the code for the
-@code{yyparse} function. (The actions from your grammar are inserted
-into this function at one point, but the rest of the function is not
-changed.) When we applied the @acronym{GPL} terms to the code for
-@code{yyparse},
+parser's implementation. (The actions from your grammar are inserted
+into this implementation at one point, but most of the rest of the
+implementation is not changed.) When we applied the @acronym{GPL}
+terms to the skeleton code for the parser's implementation,
the effect was to restrict the use of Bison output to free software.
We didn't change the terms because of sympathy for people who want to
practical conditions for using Bison match the practical conditions for
using the other @acronym{GNU} tools.
-This exception applies only when Bison is generating C code for an
-@acronym{LALR}(1) parser; otherwise, the @acronym{GPL} terms operate
-as usual. You can
-tell whether the exception applies to your @samp{.c} output file by
-inspecting it to see whether it says ``As a special exception, when
-this file is copied by Bison into a Bison output file, you may use
-that output file without restriction.''
+This exception applies when Bison is generating code for a parser.
+You can tell whether the exception applies to a Bison output file by
+inspecting the file for text beginning with ``As a special
+exception@dots{}''. The text spells out the exact terms of the
+exception.
@include gpl.texi
square (int x) /* @r{identifier, open-paren, keyword `int',}
@r{identifier, close-paren} */
@{ /* @r{open-brace} */
- return x * x; /* @r{keyword `return', identifier, asterisk,
- identifier, semicolon} */
+ return x * x; /* @r{keyword `return', identifier, asterisk,}
+ @r{identifier, semicolon} */
@} /* @r{close-brace} */
@end example
@end ifinfo
@findex YYERROR
@cindex @acronym{GLR} parsers and @code{YYERROR}
Another Bison feature requiring special consideration is @code{YYERROR}
-(@pxref{Action Features}), which you can invoke in any semantic action to
+(@pxref{Action Features}), which you can invoke in a semantic action to
initiate error recovery.
During deterministic @acronym{GLR} operation, the effect of @code{YYERROR} is
the same as its effect in an @acronym{LALR}(1) parser.
In a deferred semantic action, its effect is undefined.
@c The effect is probably a syntax error at the split point.
+Also, see @ref{Location Default Action, ,Default Action for Locations}, which
+describes a special usage of @code{YYLLOC_DEFAULT} in @acronym{GLR} parsers.
+
@node Compiler Requirements
@subsection Considerations when Compiling @acronym{GLR} Parsers
@cindex @code{inline}
desk-top calculator.
These examples are simple, but Bison grammars for real programming
-languages are written the same way.
-@ifinfo
-You can copy these examples out of the Info file and into a source file
-to try them.
-@end ifinfo
+languages are written the same way. You can copy these examples into a
+source file to try them.
@menu
* RPN Calc:: Reverse polish notation calculator;
The groupings of the rpcalc ``language'' defined here are the expression
(given the name @code{exp}), the line of input (@code{line}), and the
complete input transcript (@code{input}). Each of these nonterminal
-symbols has several alternate rules, joined by the @samp{|} punctuator
+symbols has several alternate rules, joined by the vertical bar @samp{|}
which is read as ``or''. The following sections explain what these rules
mean.
Multiple rules for the same @var{result} can be written separately or can
be joined with the vertical-bar character @samp{|} as follows:
-@ifinfo
-@example
-@var{result}: @var{rule1-components}@dots{}
- | @var{rule2-components}@dots{}
- @dots{}
- ;
-@end example
-@end ifinfo
-@iftex
@example
@group
@var{result}: @var{rule1-components}@dots{}
;
@end group
@end example
-@end iftex
@noindent
They are still considered distinct rules even when joined in this way.
@end example
@noindent
+@code{YYSTYPE}'s replacement list should be a type name
+that does not contain parentheses or square brackets.
This macro definition must go in the prologue of the grammar file
(@pxref{Grammar Outline, ,Outline of a Bison Grammar}).
removes the temporary @code{let}-variable from the list so that it won't
appear to exist while the rest of the program is parsed.
+@findex %destructor
+@cindex discarded symbols, mid-rule actions
+@cindex error recovery, mid-rule actions
+In the above example, if the parser initiates error recovery (@pxref{Error
+Recovery}) while parsing the tokens in the embedded statement @code{stmt},
+it might discard the previous semantic context @code{$<context>5} without
+restoring it.
+Thus, @code{$<context>5} needs a destructor (@pxref{Destructor Decl, , Freeing
+Discarded Symbols}).
+However, Bison currently provides no means to declare a destructor for a
+mid-rule action's semantic value.
+
+One solution is to bury the mid-rule action inside a nonterminal symbol and to
+declare a destructor for that symbol:
+
+@example
+@group
+%type <context> let
+%destructor @{ pop_context ($$); @} let
+
+%%
+
+stmt: let stmt
+ @{ $$ = $2;
+ pop_context ($1); @}
+ ;
+
+let: LET '(' var ')'
+ @{ $$ = push_context ();
+ declare_variable ($3); @}
+ ;
+
+@end group
+@end example
+
+@noindent
+Note that the action is now at the end of its rule.
+Any mid-rule action can be converted to an end-of-rule action in this way, and
+this is what Bison actually does to implement mid-rule actions.
+
Taking action before a rule is completely recognized often leads to
conflicts since the parser must commit to a parse in order to execute the
action. For example, the following two rules, without mid-rule actions,
@noindent
Now Bison can execute the action in the rule for @code{subroutine} without
-deciding which rule for @code{compound} it will eventually use. Note that
-the action is now at the end of its rule. Any mid-rule action can be
-converted to an end-of-rule action in this way, and this is what Bison
-actually does to implement mid-rule actions.
+deciding which rule for @code{compound} it will eventually use.
@node Locations
@section Tracking Locations
Defining a data type for locations is much simpler than for semantic values,
since all tokens and groupings always use the same type.
-The type of locations is specified by defining a macro called @code{YYLTYPE}.
+You can specify the type of locations by defining a macro called
+@code{YYLTYPE}, just as you can specify the semantic value type by
+defining @code{YYSTYPE} (@pxref{Value Type}).
When @code{YYLTYPE} is not defined, Bison uses a default structure type with
four members:
@node Location Default Action
@subsection Default Action for Locations
@vindex YYLLOC_DEFAULT
+@cindex @acronym{GLR} parsers and @code{YYLLOC_DEFAULT}
Actually, actions are not the best place to compute locations. Since
locations are much more general than semantic values, there is room in
rule. The @code{YYLLOC_DEFAULT} macro is invoked each time a rule is
matched, before the associated action is run. It is also invoked
while processing a syntax error, to compute the error's location.
+Before reporting an unresolvable syntactic ambiguity, a @acronym{GLR}
+parser invokes @code{YYLLOC_DEFAULT} recursively to compute the location
+of that ambiguity.
Most of the time, this macro is general enough to suppress location
dedicated code from semantic actions.
the location of the grouping (the result of the computation). When a
rule is matched, the second parameter identifies locations of
all right hand side elements of the rule being matched, and the third
-parameter is the size of the rule's right hand side. When processing
-a syntax error, the second parameter identifies locations of
-the symbols that were discarded during error processing, and the third
+parameter is the size of the rule's right hand side.
+When a @acronym{GLR} parser reports an ambiguity, which of multiple candidate
+right hand sides it passes to @code{YYLLOC_DEFAULT} is undefined.
+When processing a syntax error, the second parameter identifies locations
+of the symbols that were discarded during error processing, and the third
parameter is the number of discarded symbols.
By default, @code{YYLLOC_DEFAULT} is defined this way:
@deffn {Directive} %name-prefix="@var{prefix}"
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
+in C parsers
is @code{yyparse}, @code{yylex}, @code{yyerror}, @code{yynerrs},
-@code{yylval}, @code{yylloc}, @code{yychar}, @code{yydebug}, and
-possible @code{yylloc}. For example, if you use
+@code{yylval}, @code{yychar}, @code{yydebug}, and
+(if locations are used) @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}.
+and so on. In C++ parsers, it is only the surrounding namespace which is
+named @var{prefix} instead of @samp{yy}.
+@xref{Multiple Parsers, ,Multiple Parsers in the Same Program}.
@end deffn
@ifset defaultprec
@item -b @var{file-prefix}
@itemx --file-prefix=@var{prefix}
-Pretend that @code{%verbose} was specified, i.e, specify prefix to use
+Pretend that @code{%file-prefix} was specified, i.e, specify prefix to use
for all Bison output file names. @xref{Decl Summary}.
@item -r @var{things}
@node Option Cross Key
@section Option Cross Key
+@c FIXME: How about putting the directives too?
Here is a list of options, alphabetized by long option, to help you find
the corresponding short option.
-@tex
-\def\leaderfill{\leaders\hbox to 1em{\hss.\hss}\hfill}
-
-{\tt
-\line{ --debug \leaderfill -t}
-\line{ --defines \leaderfill -d}
-\line{ --file-prefix \leaderfill -b}
-\line{ --graph \leaderfill -g}
-\line{ --help \leaderfill -h}
-\line{ --name-prefix \leaderfill -p}
-\line{ --no-lines \leaderfill -l}
-\line{ --no-parser \leaderfill -n}
-\line{ --output \leaderfill -o}
-\line{ --print-localedir}
-\line{ --token-table \leaderfill -k}
-\line{ --verbose \leaderfill -v}
-\line{ --version \leaderfill -V}
-\line{ --yacc \leaderfill -y}
-}
-@end tex
-
-@ifinfo
-@example
---debug -t
---defines=@var{defines-file} -d
---file-prefix=@var{prefix} -b @var{file-prefix}
---graph=@var{graph-file} -d
---help -h
---name-prefix=@var{prefix} -p @var{name-prefix}
---no-lines -l
---no-parser -n
---output=@var{outfile} -o @var{outfile}
---print-localedir
---token-table -k
---verbose -v
---version -V
---yacc -y
-@end example
-@end ifinfo
+@multitable {@option{--defines=@var{defines-file}}} {@option{-b @var{file-prefix}XXX}}
+@headitem Long Option @tab Short Option
+@item @option{--debug} @tab @option{-t}
+@item @option{--defines=@var{defines-file}} @tab @option{-d}
+@item @option{--file-prefix=@var{prefix}} @tab @option{-b @var{file-prefix}}
+@item @option{--graph=@var{graph-file}} @tab @option{-d}
+@item @option{--help} @tab @option{-h}
+@item @option{--name-prefix=@var{prefix}} @tab @option{-p @var{name-prefix}}
+@item @option{--no-lines} @tab @option{-l}
+@item @option{--no-parser} @tab @option{-n}
+@item @option{--output=@var{outfile}} @tab @option{-o @var{outfile}}
+@item @option{--print-localedir} @tab
+@item @option{--token-table} @tab @option{-k}
+@item @option{--verbose} @tab @option{-v}
+@item @option{--version} @tab @option{-V}
+@item @option{--yacc} @tab @option{-y}
+@end multitable
@node Yacc Library
@section Yacc Library
@c - Always pure
@c - initial action
-The C++ parser @acronym{LALR}(1) skeleton is named @file{lalr1.cc}. To select
-it, you may either pass the option @option{--skeleton=lalr1.cc} to
-Bison, or include the directive @samp{%skeleton "lalr1.cc"} in the
+The C++ parser @acronym{LALR}(1) skeleton is named @file{lalr1.cc}. To
+select it, you may either pass the option @option{--skeleton=lalr1.cc}
+to Bison, or include the directive @samp{%skeleton "lalr1.cc"} in the
grammar preamble. When run, @command{bison} will create several
-files:
+entities in the @samp{yy} namespace. Use the @samp{%name-prefix}
+directive to change the namespace name, see @ref{Decl Summary}. The
+various classes are generated in the following files:
+
@table @file
@item position.hh
@itemx location.hh
@item @var{file}.hh
@itemx @var{file}.cc
-The declaration and implementation of the C++ parser class.
-@var{file} is the name of the output file. It follows the same
-rules as with regular C parsers.
+(Assuming the extension of the input file was @samp{.yy}.) The
+declaration and implementation of the C++ parser class. The basename
+and extension of these two files follow the same rules as with regular C
+parsers (@pxref{Invocation}).
-Note that @file{@var{file}.hh} is @emph{mandatory}, the C++ cannot
-work without the parser class declaration. Therefore, you must either
-pass @option{-d}/@option{--defines} to @command{bison}, or use the
+The header is @emph{mandatory}; you must either pass
+@option{-d}/@option{--defines} to @command{bison}, or use the
@samp{%defines} directive.
@end table
@comment file: calc++-driver.hh
@example
// Announce to Flex the prototype we want for lexing function, ...
-# define YY_DECL \
- int yylex (yy::calcxx_parser::semantic_type* yylval, \
- yy::calcxx_parser::location_type* yylloc, \
- calcxx_driver& driver)
+# 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;
@end example
# include <string>
# include "calc++-driver.hh"
# include "calc++-parser.hh"
-/* Work around a bug in flex 2.5.31. See Debian bug 333231
- <http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=333231>. */
+
+/* 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
%@}
@end example
%@{
typedef yy::calcxx_parser::token token;
%@}
-
-[-+*/] return yytext[0];
+ /* Convert ints to the actual type of tokens. */
+[-+*/] return yy::calcxx_parser::token_type (yytext[0]);
":=" return token::ASSIGN;
@{int@} @{
errno = 0;
are addressed.
@menu
-* Memory Exhausted:: Breaking the Stack Limits
-* How Can I Reset the Parser:: @code{yyparse} Keeps some State
-* Strings are Destroyed:: @code{yylval} Loses Track of Strings
-* Implementing Gotos/Loops:: Control Flow in the Calculator
+* Memory Exhausted:: Breaking the Stack Limits
+* How Can I Reset the Parser:: @code{yyparse} Keeps some State
+* Strings are Destroyed:: @code{yylval} Loses Track of Strings
+* Implementing Gotos/Loops:: Control Flow in the Calculator
+* Multiple start-symbols:: Factoring closely related grammars
+* Secure? Conform?:: Is Bison @acronym{POSIX} safe?
+* I can't build Bison:: Troubleshooting
+* Where can I find help?:: Troubleshouting
+* Bug Reports:: Troublereporting
+* Other Languages:: Parsers in Java and others
+* Beta Testing:: Experimenting development versions
+* Mailing Lists:: Meeting other Bison users
@end menu
@node Memory Exhausted
This error is probably the single most frequent ``bug report'' sent to
Bison lists, but is only concerned with a misunderstanding of the role
-of scanner. Consider the following Lex code:
+of the scanner. Consider the following Lex code:
@verbatim
%{
invited to consult the dedicated literature.
+@node Multiple start-symbols
+@section Multiple start-symbols
+
+@display
+I have several closely related grammars, and I would like to share their
+implementations. In fact, I could use a single grammar but with
+multiple entry points.
+@end display
+
+Bison does not support multiple start-symbols, but there is a very
+simple means to simulate them. If @code{foo} and @code{bar} are the two
+pseudo start-symbols, then introduce two new tokens, say
+@code{START_FOO} and @code{START_BAR}, and use them as switches from the
+real start-symbol:
+
+@example
+%token START_FOO START_BAR;
+%start start;
+start: START_FOO foo
+ | START_BAR bar;
+@end example
+
+These tokens prevents the introduction of new conflicts. As far as the
+parser goes, that is all that is needed.
+
+Now the difficult part is ensuring that the scanner will send these
+tokens first. If your scanner is hand-written, that should be
+straightforward. If your scanner is generated by Lex, them there is
+simple means to do it: recall that anything between @samp{%@{ ... %@}}
+after the first @code{%%} is copied verbatim in the top of the generated
+@code{yylex} function. Make sure a variable @code{start_token} is
+available in the scanner (e.g., a global variable or using
+@code{%lex-param} etc.), and use the following:
+
+@example
+ /* @r{Prologue.} */
+%%
+%@{
+ if (start_token)
+ @{
+ int t = start_token;
+ start_token = 0;
+ return t;
+ @}
+%@}
+ /* @r{The rules.} */
+@end example
+
+
+@node Secure? Conform?
+@section Secure? Conform?
+
+@display
+Is Bison secure? Does it conform to POSIX?
+@end display
+
+If you're looking for a guarantee or certification, we don't provide it.
+However, Bison is intended to be a reliable program that conforms to the
+@acronym{POSIX} specification for Yacc. If you run into problems,
+please send us a bug report.
+
+@node I can't build Bison
+@section I can't build Bison
+
+@display
+I can't build Bison because @command{make} complains that
+@code{msgfmt} is not found.
+What should I do?
+@end display
+
+Like most GNU packages with internationalization support, that feature
+is turned on by default. If you have problems building in the @file{po}
+subdirectory, it indicates that your system's internationalization
+support is lacking. You can re-configure Bison with
+@option{--disable-nls} to turn off this support, or you can install GNU
+gettext from @url{ftp://ftp.gnu.org/gnu/gettext/} and re-configure
+Bison. See the file @file{ABOUT-NLS} for more information.
+
+
+@node Where can I find help?
+@section Where can I find help?
+
+@display
+I'm having trouble using Bison. Where can I find help?
+@end display
+
+First, read this fine manual. Beyond that, you can send mail to
+@email{help-bison@@gnu.org}. This mailing list is intended to be
+populated with people who are willing to answer questions about using
+and installing Bison. Please keep in mind that (most of) the people on
+the list have aspects of their lives which are not related to Bison (!),
+so you may not receive an answer to your question right away. This can
+be frustrating, but please try not to honk them off; remember that any
+help they provide is purely voluntary and out of the kindness of their
+hearts.
+
+@node Bug Reports
+@section Bug Reports
+
+@display
+I found a bug. What should I include in the bug report?
+@end display
+
+Before you send a bug report, make sure you are using the latest
+version. Check @url{ftp://ftp.gnu.org/pub/gnu/bison/} or one of its
+mirrors. Be sure to include the version number in your bug report. If
+the bug is present in the latest version but not in a previous version,
+try to determine the most recent version which did not contain the bug.
+
+If the bug is parser-related, you should include the smallest grammar
+you can which demonstrates the bug. The grammar file should also be
+complete (i.e., I should be able to run it through Bison without having
+to edit or add anything). The smaller and simpler the grammar, the
+easier it will be to fix the bug.
+
+Include information about your compilation environment, including your
+operating system's name and version and your compiler's name and
+version. If you have trouble compiling, you should also include a
+transcript of the build session, starting with the invocation of
+`configure'. Depending on the nature of the bug, you may be asked to
+send additional files as well (such as `config.h' or `config.cache').
+
+Patches are most welcome, but not required. That is, do not hesitate to
+send a bug report just because you can not provide a fix.
+
+Send bug reports to @email{bug-bison@@gnu.org}.
+
+@node Other Languages
+@section Other Languages
+
+@display
+Will Bison ever have C++ support? How about Java or @var{insert your
+favorite language here}?
+@end display
+
+C++ support is there now, and is documented. We'd love to add other
+languages; contributions are welcome.
+
+@node Beta Testing
+@section Beta Testing
+
+@display
+What is involved in being a beta tester?
+@end display
+
+It's not terribly involved. Basically, you would download a test
+release, compile it, and use it to build and run a parser or two. After
+that, you would submit either a bug report or a message saying that
+everything is okay. It is important to report successes as well as
+failures because test releases eventually become mainstream releases,
+but only if they are adequately tested. If no one tests, development is
+essentially halted.
+
+Beta testers are particularly needed for operating systems to which the
+developers do not have easy access. They currently have easy access to
+recent GNU/Linux and Solaris versions. Reports about other operating
+systems are especially welcome.
+
+@node Mailing Lists
+@section Mailing Lists
+
+@display
+How do I join the help-bison and bug-bison mailing lists?
+@end display
+
+See @url{http://lists.gnu.org/}.
@c ================================================= Table of Symbols
projects / bison.git / blobdiff