X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/d6ca7905ab458076e6d89ea409a413c0ae7402b1..55ba27be34b24644e7b7d581d0313b299ce0aa39:/doc/bison.texinfo diff --git a/doc/bison.texinfo b/doc/bison.texinfo index 5ff8f863..cd5ec423 100644 --- a/doc/bison.texinfo +++ b/doc/bison.texinfo @@ -324,6 +324,13 @@ Frequently Asked Questions * 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 +* 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 @@ -336,16 +343,16 @@ 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 @@ -1135,13 +1142,16 @@ memory referenced by @code{yylval}. @findex YYERROR @cindex @acronym{GLR} parsers and @code{YYERROR} Another Bison feature requiring special consideration is @code{YYERROR} -(@pxref{Action Features}), which you can invoke in 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} @@ -2639,6 +2649,10 @@ they precede the definition of @code{yyparse}. You can use don't need any C declarations, you may omit the @samp{%@{} and @samp{%@}} delimiters that bracket this section. +The @var{Prologue} section is terminated by the the first occurrence +of @samp{%@}} that is outside a comment, a string literal, or a +character constant. + You may have more than one @var{Prologue} section, intermixed with the @var{Bison declarations}. This allows you to have C and Bison declarations that refer to each other. For example, the @code{%union} @@ -2899,6 +2913,22 @@ the semantics of the rule. An action looks like this: @end example @noindent +@cindex braced code +This is an example of @dfn{braced code}, that is, C code surrounded by +braces, much like a compound statement in C@. Braced code can contain +any sequence of C tokens, so long as its braces are balanced. Bison +does not check the braced code for correctness directly; it merely +copies the code to the output file, where the C compiler can check it. + +Within braced code, the balanced-brace count is not affected by braces +within comments, string literals, or character constants, but it is +affected by the C digraphs @samp{<%} and @samp{%>} that represent +braces. At the top level braced code must be terminated by @samp{@}} +and not by a digraph. Bison does not look for trigraphs, so if braced +code uses trigraphs you should ensure that they do not affect the +nesting of braces or the boundaries of comments, string literals, or +character constants. + Usually there is only one action and it follows the components. @xref{Actions}. @@ -3103,14 +3133,8 @@ each time an instance of that rule is recognized. The task of most actions is to compute a semantic value for the grouping built by the rule from the semantic values associated with tokens or smaller groupings. -An action consists of C statements surrounded by braces, much like a -compound statement in C@. An action can contain any sequence of C -statements. Bison does not look for trigraphs, though, so if your C -code uses trigraphs you should ensure that they do not affect the -nesting of braces or the boundaries of comments, strings, or character -literals. - -An action can be placed at any position in the rule; +An action consists of braced code containing C statements, and can be +placed at any position in the rule; it is executed at that position. Most rules have just one action at the end of the rule, following all the components. Actions in the middle of a rule are tricky and used only for special purposes (@pxref{Mid-Rule @@ -3303,6 +3327,46 @@ earlier action is used to restore the prior list of variables. This 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{$5} without +restoring it. +Thus, @code{$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 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, @@ -3396,10 +3460,7 @@ compound: subroutine @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 @@ -3520,6 +3581,7 @@ This location is stored in @code{yylloc}. @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 @@ -3527,6 +3589,9 @@ the output parser to redefine the default action to take for each 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. @@ -3535,9 +3600,11 @@ The @code{YYLLOC_DEFAULT} macro takes three parameters. The first one is 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: @@ -3768,10 +3835,10 @@ the one declared later has the higher precedence and is grouped first. @cindex value types, declaring @findex %union -The @code{%union} declaration specifies the entire collection of possible -data types for semantic values. The keyword @code{%union} is followed by a -pair of braces containing the same thing that goes inside a @code{union} in -C. +The @code{%union} declaration specifies the entire collection of +possible data types for semantic values. The keyword @code{%union} is +followed by braced code containing the same thing that goes inside a +@code{union} in C@. For example: @@ -3852,7 +3919,7 @@ code. @deffn {Directive} %initial-action @{ @var{code} @} @findex %initial-action -Declare that the @var{code} must be invoked before parsing each time +Declare that the braced @var{code} must be invoked before parsing each time @code{yyparse} is called. The @var{code} may use @code{$$} and @code{@@$} --- initial value and location of the look-ahead --- and the @code{%parse-param}. @@ -3891,7 +3958,8 @@ symbol is automatically discarded. @deffn {Directive} %destructor @{ @var{code} @} @var{symbols} @findex %destructor -Invoke @var{code} whenever the parser discards one of the @var{symbols}. +Invoke the braced @var{code} whenever the parser discards one of the +@var{symbols}. Within @var{code}, @code{$$} designates the semantic value associated with the discarded symbol. The additional parser parameters are also available (@pxref{Parser Function, , The Parser Function @@ -4367,8 +4435,8 @@ declaration @code{%parse-param}: @deffn {Directive} %parse-param @{@var{argument-declaration}@} @findex %parse-param -Declare that an argument declared by @code{argument-declaration} is an -additional @code{yyparse} argument. +Declare that an argument declared by the braced-code +@var{argument-declaration} is an additional @code{yyparse} argument. The @var{argument-declaration} is used when declaring functions or prototypes. The last identifier in @var{argument-declaration} must be the argument name. @@ -4612,8 +4680,8 @@ Function}). @deffn {Directive} lex-param @{@var{argument-declaration}@} @findex %lex-param -Declare that @code{argument-declaration} is an additional @code{yylex} -argument declaration. +Declare that the braced-code @var{argument-declaration} is an +additional @code{yylex} argument declaration. @end deffn For instance: @@ -6874,8 +6942,6 @@ Implies @code{state} and augments the description of the automaton with the full set of items for each state, instead of its core only. @end table -For instance, on the following grammar - @item -v @itemx --verbose Pretend that @code{%verbose} was specified, i.e, write an extra output @@ -7267,10 +7333,11 @@ factor both as follows. @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 @@ -7495,6 +7562,7 @@ avoid name clashes. To enable memory deallocation during error recovery, use @code{%destructor}. +@c FIXME: Document %printer, and mention that it takes a braced-code operand. @comment file: calc++-parser.yy @example %printer @{ debug_stream () << *$$; @} "identifier" @@ -7557,6 +7625,14 @@ parser's to get the set of defined tokens. # include # include "calc++-driver.hh" # include "calc++-parser.hh" +/* Work around a bug in flex 2.5.31. See Debian 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 @@ -7614,8 +7690,8 @@ It is convenient to use a typedef to shorten %@{ 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; @@ -7689,10 +7765,17 @@ Several questions about Bison come up occasionally. Here some of them 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 +* 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 @@ -7886,6 +7969,122 @@ This topic is way beyond the scope of this manual, and the reader is invited to consult the dedicated literature. +@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 "make" complains that "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