X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/552893661babb72c427f5fe21e5a47c6d916af74..4d7bc38cdcb1fb457dfd34fdf7c81e507a002867:/doc/bison.texinfo?ds=sidebyside diff --git a/doc/bison.texinfo b/doc/bison.texinfo index eae08d97..35b978af 100644 --- a/doc/bison.texinfo +++ b/doc/bison.texinfo @@ -44,7 +44,7 @@ This manual is for @acronym{GNU} Bison (version @value{VERSION}, @value{UPDATED}), the @acronym{GNU} parser generator. Copyright @copyright{} 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998, -1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. +1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc. @quotation Permission is granted to copy, distribute and/or modify this document @@ -145,9 +145,10 @@ The Concepts of Bison Writing @acronym{GLR} Parsers -* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars -* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities -* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler +* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars. +* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities. +* GLR Semantic Actions:: Deferred semantic actions have special concerns. +* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler. Examples @@ -225,6 +226,7 @@ Tracking Locations Bison Declarations +* Require Decl:: Requiring a Bison version. * Token Decl:: Declaring terminal symbols. * Precedence Decl:: Declaring terminals with precedence and associativity. * Union Decl:: Declaring the set of all semantic value types. @@ -460,7 +462,7 @@ more information on this. @cindex @acronym{GLR} parsing @cindex generalized @acronym{LR} (@acronym{GLR}) parsing @cindex ambiguous grammars -@cindex non-deterministic parsing +@cindex nondeterministic parsing Parsers for @acronym{LALR}(1) grammars are @dfn{deterministic}, meaning roughly that the next grammar rule to apply at any point in the input is @@ -468,7 +470,7 @@ uniquely determined by the preceding input and a fixed, finite portion (called a @dfn{look-ahead}) of the remaining input. A context-free grammar can be @dfn{ambiguous}, meaning that there are multiple ways to apply the grammar rules to get the same inputs. Even unambiguous -grammars can be @dfn{non-deterministic}, meaning that no fixed +grammars can be @dfn{nondeterministic}, meaning that no fixed look-ahead always suffices to determine the next grammar rule to apply. With the proper declarations, Bison is also able to parse these more general context-free grammars, using a technique known as @acronym{GLR} @@ -732,9 +734,10 @@ user-defined function on the resulting values to produce an arbitrary merged result. @menu -* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars -* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities -* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler +* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars. +* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities. +* GLR Semantic Actions:: Deferred semantic actions have special concerns. +* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler. @end menu @node Simple GLR Parsers @@ -909,29 +912,27 @@ parser recognizes all valid declarations, according to the limited syntax above, transparently. In fact, the user does not even notice when the parser splits. -So here we have a case where we can use the benefits of @acronym{GLR}, almost -without disadvantages. Even in simple cases like this, however, there -are at least two potential problems to beware. -First, always analyze the conflicts reported by -Bison to make sure that @acronym{GLR} splitting is only done where it is -intended. A @acronym{GLR} parser splitting inadvertently may cause -problems less obvious than an @acronym{LALR} parser statically choosing the -wrong alternative in a conflict. -Second, consider interactions with the lexer (@pxref{Semantic Tokens}) -with great care. Since a split parser consumes tokens -without performing any actions during the split, the lexer cannot -obtain information via parser actions. Some cases of -lexer interactions can be eliminated by using @acronym{GLR} to -shift the complications from the lexer to the parser. You must check -the remaining cases for correctness. - -In our example, it would be safe for the lexer to return tokens -based on their current meanings in some symbol table, because no new -symbols are defined in the middle of a type declaration. Though it -is possible for a parser to define the enumeration -constants as they are parsed, before the type declaration is -completed, it actually makes no difference since they cannot be used -within the same enumerated type declaration. +So here we have a case where we can use the benefits of @acronym{GLR}, +almost without disadvantages. Even in simple cases like this, however, +there are at least two potential problems to beware. First, always +analyze the conflicts reported by Bison to make sure that @acronym{GLR} +splitting is only done where it is intended. A @acronym{GLR} parser +splitting inadvertently may cause problems less obvious than an +@acronym{LALR} parser statically choosing the wrong alternative in a +conflict. Second, consider interactions with the lexer (@pxref{Semantic +Tokens}) with great care. Since a split parser consumes tokens without +performing any actions during the split, the lexer cannot obtain +information via parser actions. Some cases of lexer interactions can be +eliminated by using @acronym{GLR} to shift the complications from the +lexer to the parser. You must check the remaining cases for +correctness. + +In our example, it would be safe for the lexer to return tokens based on +their current meanings in some symbol table, because no new symbols are +defined in the middle of a type declaration. Though it is possible for +a parser to define the enumeration constants as they are parsed, before +the type declaration is completed, it actually makes no difference since +they cannot be used within the same enumerated type declaration. @node Merging GLR Parses @subsection Using @acronym{GLR} to Resolve Ambiguities @@ -1095,6 +1096,52 @@ productions that participate in any particular merge have identical and the parser will report an error during any parse that results in the offending merge. +@node GLR Semantic Actions +@subsection GLR Semantic Actions + +@cindex deferred semantic actions +By definition, a deferred semantic action is not performed at the same time as +the associated reduction. +This raises caveats for several Bison features you might use in a semantic +action in a @acronym{GLR} parser. + +@vindex yychar +@cindex @acronym{GLR} parsers and @code{yychar} +@vindex yylval +@cindex @acronym{GLR} parsers and @code{yylval} +@vindex yylloc +@cindex @acronym{GLR} parsers and @code{yylloc} +In any semantic action, you can examine @code{yychar} to determine the type of +the look-ahead token present at the time of the associated reduction. +After checking that @code{yychar} is not set to @code{YYEMPTY} or @code{YYEOF}, +you can then examine @code{yylval} and @code{yylloc} to determine the +look-ahead token's semantic value and location, if any. +In a nondeferred semantic action, you can also modify any of these variables to +influence syntax analysis. +@xref{Look-Ahead, ,Look-Ahead Tokens}. + +@findex yyclearin +@cindex @acronym{GLR} parsers and @code{yyclearin} +In a deferred semantic action, it's too late to influence syntax analysis. +In this case, @code{yychar}, @code{yylval}, and @code{yylloc} are set to +shallow copies of the values they had at the time of the associated reduction. +For this reason alone, modifying them is dangerous. +Moreover, the result of modifying them is undefined and subject to change with +future versions of Bison. +For example, if a semantic action might be deferred, you should never write it +to invoke @code{yyclearin} (@pxref{Action Features}) or to attempt to free +memory referenced by @code{yylval}. + +@findex YYERROR +@cindex @acronym{GLR} parsers and @code{YYERROR} +Another Bison feature requiring special consideration is @code{YYERROR} +(@pxref{Action Features}), which you can invoke in any 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. + @node Compiler Requirements @subsection Considerations when Compiling @acronym{GLR} Parsers @cindex @code{inline} @@ -2125,7 +2172,7 @@ as @code{sin}, @code{cos}, etc. It is easy to add new operators to the infix calculator as long as they are only single-character literals. The lexical analyzer @code{yylex} passes -back all nonnumber characters as tokens, so new grammar rules suffice for +back all nonnumeric characters as tokens, so new grammar rules suffice for adding a new operator. But we want something more flexible: built-in functions whose syntax has this form: @@ -2410,7 +2457,7 @@ getsym (char const *sym_name) The function @code{yylex} must now recognize variables, numeric values, and the single-character arithmetic operators. Strings of alphanumeric -characters with a leading non-digit are recognized as either variables or +characters with a leading letter are recognized as either variables or functions depending on what the symbol table says about them. The string is passed to @code{getsym} for look up in the symbol table. If @@ -2584,13 +2631,17 @@ continues until end of line. @cindex Prologue @cindex declarations -The @var{Prologue} section contains macro definitions and -declarations of functions and variables that are used in the actions in the -grammar rules. These are copied to the beginning of the parser file so -that they precede the definition of @code{yyparse}. You can use -@samp{#include} to get the declarations from a header file. If you don't -need any C declarations, you may omit the @samp{%@{} and @samp{%@}} -delimiters that bracket this section. +The @var{Prologue} section contains macro definitions and declarations +of functions and variables that are used in the actions in the grammar +rules. These are copied to the beginning of the parser file so that +they precede the definition of @code{yyparse}. You can use +@samp{#include} to get the declarations from a header file. If you +don't need any C declarations, you may omit the @samp{%@{} and +@samp{%@}} delimiters that bracket this section. + +The @var{Prologue} section is terminated by the the first occurrence +of @samp{%@}} that is outside a comment, a string literal, or a +character constant. You may have more than one @var{Prologue} section, intermixed with the @var{Bison declarations}. This allows you to have C and Bison @@ -2660,10 +2711,10 @@ even if you define them in the Epilogue. If the last section is empty, you may omit the @samp{%%} that separates it from the grammar rules. -The Bison parser itself contains many macros and identifiers whose -names start with @samp{yy} or @samp{YY}, so it is a -good idea to avoid using any such names (except those documented in this -manual) in the epilogue of the grammar file. +The Bison parser itself contains many macros and identifiers whose names +start with @samp{yy} or @samp{YY}, so it is a good idea to avoid using +any such names (except those documented in this manual) in the epilogue +of the grammar file. @node Symbols @section Symbols, Terminal and Nonterminal @@ -2679,13 +2730,13 @@ A @dfn{terminal symbol} (also known as a @dfn{token type}) represents a class of syntactically equivalent tokens. You use the symbol in grammar rules to mean that a token in that class is allowed. The symbol is represented in the Bison parser by a numeric code, and the @code{yylex} -function returns a token type code to indicate what kind of token has been -read. You don't need to know what the code value is; you can use the -symbol to stand for it. +function returns a token type code to indicate what kind of token has +been read. You don't need to know what the code value is; you can use +the symbol to stand for it. -A @dfn{nonterminal symbol} stands for a class of syntactically equivalent -groupings. The symbol name is used in writing grammar rules. By convention, -it should be all lower case. +A @dfn{nonterminal symbol} stands for a class of syntactically +equivalent groupings. The symbol name is used in writing grammar rules. +By convention, it should be all lower case. Symbol names can contain letters, digits (not at the beginning), underscores and periods. Periods make sense only in nonterminals. @@ -2781,7 +2832,7 @@ 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}. If you want to write a grammar that is portable to any Standard C -host, you must use only non-null character tokens taken from the basic +host, you must use only nonnull character tokens taken from the basic execution character set of Standard C@. This set consists of the ten digits, the 52 lower- and upper-case English letters, and the characters in the following C-language string: @@ -2790,17 +2841,17 @@ characters in the following C-language string: "\a\b\t\n\v\f\r !\"#%&'()*+,-./:;<=>?[\\]^_@{|@}~" @end example -The @code{yylex} function and Bison must use a consistent character -set and encoding for character tokens. For example, if you run Bison in an -@acronym{ASCII} environment, but then compile and run the resulting program -in an environment that uses an incompatible character set like -@acronym{EBCDIC}, the resulting program may not work because the -tables generated by Bison will assume @acronym{ASCII} numeric values for -character tokens. It is standard -practice for software distributions to contain C source files that -were generated by Bison in an @acronym{ASCII} environment, so installers on -platforms that are incompatible with @acronym{ASCII} must rebuild those -files before compiling them. +The @code{yylex} function and Bison must use a consistent character set +and encoding for character tokens. For example, if you run Bison in an +@acronym{ASCII} environment, but then compile and run the resulting +program in an environment that uses an incompatible character set like +@acronym{EBCDIC}, the resulting program may not work because the tables +generated by Bison will assume @acronym{ASCII} numeric values for +character tokens. It is standard practice for software distributions to +contain C source files that were generated by Bison in an +@acronym{ASCII} environment, so installers on platforms that are +incompatible with @acronym{ASCII} must rebuild those files before +compiling them. The symbol @code{error} is a terminal symbol reserved for error recovery (@pxref{Error Recovery}); you shouldn't use it for any other purpose. @@ -2852,6 +2903,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}. @@ -2907,10 +2974,10 @@ with no components. @section Recursive Rules @cindex recursive rule -A rule is called @dfn{recursive} when its @var{result} nonterminal appears -also on its right hand side. Nearly all Bison grammars need to use -recursion, because that is the only way to define a sequence of any number -of a particular thing. Consider this recursive definition of a +A rule is called @dfn{recursive} when its @var{result} nonterminal +appears also on its right hand side. Nearly all Bison grammars need to +use recursion, because that is the only way to define a sequence of any +number of a particular thing. Consider this recursive definition of a comma-separated sequence of one or more expressions: @example @@ -3024,8 +3091,9 @@ This macro definition must go in the prologue of the grammar file In most programs, you will need different data types for different kinds of tokens and groupings. For example, a numeric constant may need type -@code{int} or @code{long int}, while a string constant needs type @code{char *}, -and an identifier might need a pointer to an entry in the symbol table. +@code{int} or @code{long int}, while a string constant needs type +@code{char *}, and an identifier might need a pointer to an entry in the +symbol table. To use more than one data type for semantic values in one parser, Bison requires you to do two things: @@ -3055,14 +3123,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 @@ -3140,6 +3202,12 @@ As long as @code{bar} is used only in the fashion shown here, @code{$0} always refers to the @code{expr} which precedes @code{bar} in the definition of @code{foo}. +@vindex yylval +It is also possible to access the semantic value of the look-ahead token, if +any, from a semantic action. +This semantic value is stored in @code{yylval}. +@xref{Action Features, ,Special Features for Use in Actions}. + @node Action Types @subsection Data Types of Values in Actions @cindex action data types @@ -3457,6 +3525,12 @@ exp: @dots{} @end group @end example +@vindex yylloc +It is also possible to access the location of the look-ahead token, if any, +from a semantic action. +This location is stored in @code{yylloc}. +@xref{Action Features, ,Special Features for Use in Actions}. + @node Location Default Action @subsection Default Action for Locations @vindex YYLLOC_DEFAULT @@ -3548,6 +3622,7 @@ it explicitly (@pxref{Language and Grammar, ,Languages and Context-Free Grammars}). @menu +* Require Decl:: Requiring a Bison version. * Token Decl:: Declaring terminal symbols. * Precedence Decl:: Declaring terminals with precedence and associativity. * Union Decl:: Declaring the set of all semantic value types. @@ -3560,6 +3635,20 @@ Grammars}). * Decl Summary:: Table of all Bison declarations. @end menu +@node Require Decl +@subsection Require a Version of Bison +@cindex version requirement +@cindex requiring a version of Bison +@findex %require + +You may require the minimum version of Bison to process the grammar. If +the requirement is not met, @command{bison} exits with an error (exit +status 63). + +@example +%require "@var{version}" +@end example + @node Token Decl @subsection Token Type Names @cindex declaring token type names @@ -3693,10 +3782,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: @@ -3727,10 +3816,15 @@ As an extension to @acronym{POSIX}, a tag is allowed after the @end group @end example +@noindent specifies the union tag @code{value}, so the corresponding C type is @code{union value}. If you do not specify a tag, it defaults to @code{YYSTYPE}. +As another extension to @acronym{POSIX}, you may specify multiple +@code{%union} declarations; their contents are concatenated. However, +only the first @code{%union} declaration can specify a tag. + Note that, unlike making a @code{union} declaration in C, you need not write a semicolon after the closing brace. @@ -3772,7 +3866,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}. @@ -3784,7 +3878,7 @@ For instance, if your locations use a file name, you may use %parse-param @{ char const *file_name @}; %initial-action @{ - @@$.begin.filename = @@$.end.filename = file_name; + @@$.initialize (file_name); @}; @end example @@ -3794,32 +3888,29 @@ For instance, if your locations use a file name, you may use @cindex freeing discarded symbols @findex %destructor -Some symbols can be discarded by the parser. During error -recovery (@pxref{Error Recovery}), symbols already pushed -on the stack and tokens coming from the rest of the file -are discarded until the parser falls on its feet. If the parser -runs out of memory, all the symbols on the stack must be discarded. -Even if the parser succeeds, it must discard the start symbol. +During error recovery (@pxref{Error Recovery}), symbols already pushed +on the stack and tokens coming from the rest of the file are discarded +until the parser falls on its feet. If the parser runs out of memory, +or if it returns via @code{YYABORT} or @code{YYACCEPT}, all the +symbols on the stack must be discarded. Even if the parser succeeds, it +must discard the start symbol. 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. +in traditional compilers, it is unacceptable for programs like shells or +protocol implementations that may parse and execute indefinitely. -The @code{%destructor} directive defines code that -is called when a symbol is discarded. +The @code{%destructor} directive defines code that is called when a +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}. 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 @code{yyparse}}). - -@strong{Warning:} as of Bison 2.1, this feature is still -experimental, as there has not been enough user feedback. In particular, -the syntax might still change. +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 +@code{yyparse}}). @end deffn For instance: @@ -3838,24 +3929,6 @@ For instance: guarantees that when a @code{STRING} or a @code{string} is discarded, its associated memory will be freed. -Note that in the future, Bison might also consider that right hand side -members that are not mentioned in the action can be destroyed. For -instance, in: - -@smallexample -comment: "/*" STRING "*/"; -@end smallexample - -@noindent -the parser is entitled to destroy the semantic value of the -@code{string}. Of course, this will not apply to the default action; -compare: - -@smallexample -typeless: string; // $$ = $1 does not apply; $1 is destroyed. -typefull: string; // $$ = $1 applies, $1 is not destroyed. -@end smallexample - @sp 1 @cindex discarded symbols @@ -3867,13 +3940,20 @@ stacked symbols popped during the first phase of error recovery, @item incoming terminals during the second phase of error recovery, @item -the current look-ahead and the entire stack when the parser aborts -(either via an explicit call to @code{YYABORT}, or as a consequence of -a failed error recovery or of memory exhaustion), and +the current look-ahead and the entire stack (except the current +right-hand side symbols) when the parser returns immediately, and @item the start symbol, when the parser succeeds. @end itemize +The parser can @dfn{return immediately} because of an explicit call to +@code{YYABORT} or @code{YYACCEPT}, or failed error recovery, or memory +exhaustion. + +Right-hand size symbols of a rule that explicitly triggers a syntax +error via @code{YYERROR} are not discarded automatically. As a rule +of thumb, destructors are invoked only when user actions cannot manage +the memory. @node Expect Decl @subsection Suppressing Conflict Warnings @@ -3897,19 +3977,18 @@ The declaration looks like this: %expect @var{n} @end example -Here @var{n} is a decimal integer. The declaration says there should be -no warning if there are @var{n} shift/reduce conflicts and no -reduce/reduce conflicts. The usual warning is -given if there are either more or fewer conflicts, or if there are any -reduce/reduce conflicts. +Here @var{n} is a decimal integer. The declaration says there should +be @var{n} shift/reduce conflicts and no reduce/reduce conflicts. +Bison reports an error if the number of shift/reduce conflicts differs +from @var{n}, or if there are any reduce/reduce conflicts. -For normal @acronym{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 @acronym{GLR} parsers, however, -both shift/reduce and reduce/reduce are routine (otherwise, there -would be no need to use @acronym{GLR} parsing). Therefore, it is also possible -to specify an expected number of reduce/reduce conflicts in @acronym{GLR} -parsers, using the declaration: +For normal @acronym{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 @acronym{GLR} +parsers, however, both kinds of conflicts are routine; otherwise, +there would be no need to use @acronym{GLR} parsing. Therefore, it is +also possible to specify an expected number of reduce/reduce conflicts +in @acronym{GLR} parsers, using the declaration: @example %expect-rr @var{n} @@ -3930,12 +4009,12 @@ go back to the beginning. @item Add an @code{%expect} declaration, copying the number @var{n} from the -number which Bison printed. +number which Bison printed. With @acronym{GLR} parsers, add an +@code{%expect-rr} declaration as well. @end itemize -Now Bison will stop annoying you if you do not change the number of -conflicts, but it will warn you again if changes in the grammar result -in more or fewer conflicts. +Now Bison will warn you if you introduce an unexpected conflict, but +will keep silent otherwise. @node Start Decl @subsection The Start-Symbol @@ -3961,8 +4040,8 @@ may override this restriction with the @code{%start} declaration as follows: A @dfn{reentrant} program is one which does not alter in the course of execution; in other words, it consists entirely of @dfn{pure} (read-only) code. Reentrancy is important whenever asynchronous execution is possible; -for example, a non-reentrant program may not be safe to call from a signal -handler. In systems with multiple threads of control, a non-reentrant +for example, a nonreentrant program may not be safe to call from a signal +handler. In systems with multiple threads of control, a nonreentrant program must be called only within interlocks. Normally, Bison generates a parser which is not reentrant. This is @@ -4068,13 +4147,12 @@ is named @file{@var{name}.h}. Unless @code{YYSTYPE} is already defined as a macro, the output header declares @code{YYSTYPE}. Therefore, if you are using a @code{%union} -(@pxref{Multiple Types, ,More Than One Value Type}) with components -that require other definitions, or if you have defined a -@code{YYSTYPE} macro (@pxref{Value Type, ,Data Types of Semantic -Values}), you need to arrange for these definitions to be propagated to -all modules, e.g., by putting them in a -prerequisite header that is included both by your parser and by any -other module that needs @code{YYSTYPE}. +(@pxref{Multiple Types, ,More Than One Value Type}) with components that +require other definitions, or if you have defined a @code{YYSTYPE} macro +(@pxref{Value Type, ,Data Types of Semantic Values}), you need to +arrange for these definitions to be propagated to all modules, e.g., by +putting them in a prerequisite header that is included both by your +parser and by any other module that needs @code{YYSTYPE}. Unless your parser is pure, the output header declares @code{yylval} as an external variable. @xref{Pure Decl, ,A Pure (Reentrant) @@ -4085,11 +4163,11 @@ If you have also used locations, the output header declares @code{YYSTYPE} and @code{yylval}. @xref{Locations, ,Tracking Locations}. -This output file is normally essential if you wish to put the -definition of @code{yylex} in a separate source file, because -@code{yylex} typically needs to be able to refer to the -above-mentioned declarations and to the token type codes. -@xref{Token Values, ,Semantic Values of Tokens}. +This output file is normally essential if you wish to put the definition +of @code{yylex} in a separate source file, because @code{yylex} +typically needs to be able to refer to the above-mentioned declarations +and to the token type codes. @xref{Token Values, ,Semantic Values of +Tokens}. @end deffn @deffn {Directive} %destructor @@ -4157,6 +4235,11 @@ Request a pure (reentrant) parser program (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}). @end deffn +@deffn {Directive} %require "@var{version}" +Require version @var{version} or higher of Bison. @xref{Require Decl, , +Require a Version of Bison}. +@end deffn + @deffn {Directive} %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 @@ -4299,8 +4382,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. @@ -4447,7 +4530,7 @@ The @code{yytname} table is generated only if you use the @subsection Semantic Values of Tokens @vindex yylval -In an ordinary (non-reentrant) parser, the semantic value of the token must +In an ordinary (nonreentrant) parser, the semantic value of the token must be stored into the global variable @code{yylval}. When you are using just one data type for semantic values, @code{yylval} has that type. Thus, if the type is @code{int} (the default), you might write this in @@ -4495,12 +4578,11 @@ then the code in @code{yylex} might look like this: @vindex yylloc If you are using the @samp{@@@var{n}}-feature (@pxref{Locations, , -Tracking Locations}) in actions to keep track of the -textual locations of tokens and groupings, then you must provide this -information in @code{yylex}. The function @code{yyparse} expects to -find the textual location of a token just parsed in the global variable -@code{yylloc}. So @code{yylex} must store the proper data in that -variable. +Tracking Locations}) in actions to keep track of the textual locations +of tokens and groupings, then you must provide this information in +@code{yylex}. The function @code{yyparse} expects to find the textual +location of a token just parsed in the global variable @code{yylloc}. +So @code{yylex} must store the proper data in that variable. By default, the value of @code{yylloc} is a structure and you need only initialize the members that are going to be used by the actions. The @@ -4545,8 +4627,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: @@ -4761,6 +4843,12 @@ In either case, the rest of the action is not executed. Value stored in @code{yychar} when there is no look-ahead token. @end deffn +@deffn {Macro} YYEOF +@vindex YYEOF +Value stored in @code{yychar} when the look-ahead is the end of the input +stream. +@end deffn + @deffn {Macro} YYERROR; @findex YYERROR Cause an immediate syntax error. This statement initiates error @@ -4777,15 +4865,20 @@ is recovering from a syntax error, and 0 the rest of the time. @end deffn @deffn {Variable} yychar -Variable containing the current look-ahead token. (In a pure parser, -this is actually a local variable within @code{yyparse}.) When there is -no look-ahead token, the value @code{YYEMPTY} is stored in the variable. +Variable containing either the look-ahead token, or @code{YYEOF} when the +look-ahead is the end of the input stream, or @code{YYEMPTY} when no look-ahead +has been performed so the next token is not yet known. +Do not modify @code{yychar} in a deferred semantic action (@pxref{GLR Semantic +Actions}). @xref{Look-Ahead, ,Look-Ahead Tokens}. @end deffn @deffn {Macro} yyclearin; Discard the current look-ahead token. This is useful primarily in -error rules. @xref{Error Recovery}. +error rules. +Do not invoke @code{yyclearin} in a deferred semantic action (@pxref{GLR +Semantic Actions}). +@xref{Error Recovery}. @end deffn @deffn {Macro} yyerrok; @@ -4794,6 +4887,22 @@ errors. This is useful primarily in error rules. @xref{Error Recovery}. @end deffn +@deffn {Variable} yylloc +Variable containing the look-ahead token location when @code{yychar} is not set +to @code{YYEMPTY} or @code{YYEOF}. +Do not modify @code{yylloc} in a deferred semantic action (@pxref{GLR Semantic +Actions}). +@xref{Actions and Locations, ,Actions and Locations}. +@end deffn + +@deffn {Variable} yylval +Variable containing the look-ahead token semantic value when @code{yychar} is +not set to @code{YYEMPTY} or @code{YYEOF}. +Do not modify @code{yylval} in a deferred semantic action (@pxref{GLR Semantic +Actions}). +@xref{Actions, ,Actions}. +@end deffn + @deffn {Value} @@$ @findex @@$ Acts like a structure variable containing information on the textual location @@ -4837,12 +4946,11 @@ 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. @xref{Users, , The User's View, gettext, GNU -@code{gettext} utilities}. For -example, the shell command @samp{export LC_ALL=fr_CA.UTF-8} might set -the user's locale to French Canadian using the @acronym{UTF}-8 +also supports outputting diagnostics in the user's native language. To +make this work, the user should set the usual environment variables. +@xref{Users, , The User's View, gettext, GNU @code{gettext} utilities}. +For example, the shell command @samp{export LC_ALL=fr_CA.UTF-8} might +set the user's locale to French Canadian using the @acronym{UTF}-8 encoding. The exact set of available locales depends on the user's installation. @@ -5032,7 +5140,11 @@ doing so would produce on the stack the sequence of symbols @code{expr '!'}. No rule allows that sequence. @vindex yychar -The current look-ahead token is stored in the variable @code{yychar}. +@vindex yylval +@vindex yylloc +The look-ahead token is stored in the variable @code{yychar}. +Its semantic value and location, if any, are stored in the variables +@code{yylval} and @code{yylloc}. @xref{Action Features, ,Special Features for Use in Actions}. @node Shift/Reduce @@ -5607,7 +5719,7 @@ pp.@: 615--649 @uref{http://doi.acm.org/10.1145/69622.357187}. @cindex @acronym{GLR} parsing @cindex generalized @acronym{LR} (@acronym{GLR}) parsing @cindex ambiguous grammars -@cindex non-deterministic parsing +@cindex nondeterministic parsing Bison produces @emph{deterministic} parsers that choose uniquely when to reduce and which reduction to apply @@ -5672,10 +5784,10 @@ 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 non-deterministic +prefix of the input. Thus, really ambiguous or nondeterministic grammars can require exponential time and space to process. Such badly behaving examples, however, are not generally of practical interest. -Usually, non-determinism in a grammar is local---the parser is ``in +Usually, nondeterminism in a grammar is local---the parser is ``in doubt'' only for a few tokens at a time. Therefore, the current data structure should generally be adequate. On @acronym{LALR}(1) portions of a grammar, in particular, it is only slightly slower than with the default @@ -5849,6 +5961,7 @@ The previous look-ahead token is reanalyzed immediately after an error. If this is unacceptable, then the macro @code{yyclearin} may be used to clear this token. Write the statement @samp{yyclearin;} in the error rule's action. +@xref{Action Features, ,Special Features for Use in Actions}. For example, suppose that on a syntax error, an error handling routine is called that advances the input stream to some point where parsing should @@ -6676,13 +6789,14 @@ Print the version number of Bison and exit. @item --print-localedir Print the name of the directory containing locale-dependent data. -@need 1750 @item -y @itemx --yacc -Equivalent to @samp{-o y.tab.c}; the parser output file is called +Act more like the traditional Yacc command. This can cause +different diagnostics to be generated, and may change behavior in +other minor ways. Most importantly, imitate Yacc's output +file name conventions, so that the parser output file is called @file{y.tab.c}, and the other outputs are called @file{y.output} and -@file{y.tab.h}. The purpose of this option is to imitate Yacc's output -file name conventions. Thus, the following shell script can substitute +@file{y.tab.h}. Thus, the following shell script can substitute for Yacc, and the Bison distribution contains such a script for compatibility with @acronym{POSIX}: @@ -6690,6 +6804,12 @@ compatibility with @acronym{POSIX}: #! /bin/sh bison -y "$@@" @end example + +The @option{-y}/@option{--yacc} option is intended for use with +traditional Yacc grammars. If your grammar uses a Bison extension +like @samp{%glr-parser}, Bison might not be Yacc-compatible even if +this option is specified. + @end table @noindent @@ -6769,8 +6889,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 @@ -6933,12 +7051,13 @@ for a complete and accurate documentation. The @code{%union} directive works as for C, see @ref{Union Decl, ,The Collection of Value Types}. In particular it produces a genuine @code{union}@footnote{In the future techniques to allow complex types -within pseudo-unions (variants) might be implemented to alleviate -these issues.}, which have a few specific features in C++. +within pseudo-unions (similar to Boost variants) might be implemented to +alleviate these issues.}, which have a few specific features in C++. @itemize @minus @item -The name @code{YYSTYPE} also denotes @samp{union YYSTYPE}. You may -forward declare it just with @samp{union YYSTYPE;}. +The type @code{YYSTYPE} is defined but its use is discouraged: rather +you should refer to the parser's encapsulated type +@code{yy::parser::semantic_type}. @item Non POD (Plain Old Data) types cannot be used. C++ forbids any instance of classes with constructors in unions: only @emph{pointers} @@ -7033,7 +7152,7 @@ The output files @file{@var{output}.hh} and @file{@var{output}.cc} declare and define the parser class in the namespace @code{yy}. The class name defaults to @code{parser}, but may be changed using @samp{%define "parser_class_name" "@var{name}"}. The interface of -this class is detailled below. It can be extended using the +this class is detailed below. It can be extended using the @code{%parse-param} feature: its semantics is slightly changed since it describes an additional member of the parser class, and an additional argument for its constructor. @@ -7061,7 +7180,7 @@ Get or set the stream used for tracing the parsing. It defaults to @deftypemethod {parser} {debug_level_type} debug_level () @deftypemethodx {parser} {void} set_debug_level (debug_level @var{l}) Get or set the tracing level. Currently its value is either 0, no trace, -or non-zero, full tracing. +or nonzero, full tracing. @end deftypemethod @deftypemethod {parser} {void} error (const location_type& @var{l}, const std::string& @var{m}) @@ -7112,7 +7231,7 @@ actually easier to interface with. @subsection Calc++ --- C++ Calculator Of course the grammar is dedicated to arithmetics, a single -expression, possibily preceded by variable assignments. An +expression, possibly preceded by variable assignments. An environment containing possibly predefined variables such as @code{one} and @code{two}, is exchanged with the parser. An example of valid input follows. @@ -7139,7 +7258,8 @@ transforming the simple parsing context structure into a fully blown The declaration of this driver class, @file{calc++-driver.hh}, is as follows. The first part includes the CPP guard and imports the -required standard library components. +required standard library components, and the declaration of the parser +class. @comment file: calc++-driver.hh @example @@ -7147,26 +7267,9 @@ required standard library components. # define CALCXX_DRIVER_HH # include # include +# include "calc++-parser.hh" @end example -@noindent -Then come forward declarations. Because the parser uses the parsing -driver and reciprocally, simple inclusions of header files will not -do. Because the driver's declaration is the one that will be imported -by the rest of the project, it is saner to forward declare the -parser's information here. - -@comment file: calc++-driver.hh -@example -// Forward declarations. -union YYSTYPE; -namespace yy -@{ - class location; - class calcxx_parser; -@} -class calcxx_driver; -@end example @noindent Then comes the declaration of the scanning function. Flex expects @@ -7178,7 +7281,9 @@ factor both as follows. @example // Announce to Flex the prototype we want for lexing function, ... # define YY_DECL \ - int yylex (YYSTYPE* yylval, yy::location* yylloc, calcxx_driver& driver) + int 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 @@ -7288,19 +7393,33 @@ calcxx_driver::error (const std::string& m) @node Calc++ Parser @subsection Calc++ Parser -The parser definition file @file{calc++-parser.yy} starts by asking -for the C++ skeleton, the creation of the parser header file, and -specifies the name of the parser class. It then includes the required -headers. +The parser definition file @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. @comment file: calc++-parser.yy @example %skeleton "lalr1.cc" /* -*- C++ -*- */ -%define "parser_class_name" "calcxx_parser" +%require "2.1a" %defines +%define "parser_class_name" "calcxx_parser" +@end example + +@noindent +Then come the declarations/inclusions needed to define the +@code{%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. + +@comment file: calc++-parser.yy +@example %@{ # include -# include "calc++-driver.hh" +class calcxx_driver; %@} @end example @@ -7356,6 +7475,19 @@ them. @}; @end example +@noindent +The code between @samp{%@{} and @samp{%@}} after the introduction of the +@samp{%union} is output in the @file{*.cc} file; it needs detailed +knowledge about the driver. + +@comment file: calc++-parser.yy +@example +%@{ +# include "calc++-driver.hh" +%@} +@end example + + @noindent The token numbered as 0 corresponds to end of file; the following line allows for nicer error messages referring to ``end of file'' instead @@ -7365,17 +7497,18 @@ avoid name clashes. @comment file: calc++-parser.yy @example -%token TOKEN_EOF 0 "end of file" -%token TOKEN_ASSIGN ":=" -%token TOKEN_IDENTIFIER "identifier" -%token TOKEN_NUMBER "number" -%type exp "expression" +%token END 0 "end of file" +%token ASSIGN ":=" +%token IDENTIFIER "identifier" +%token NUMBER "number" +%type exp "expression" @end example @noindent 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" @@ -7394,9 +7527,9 @@ The grammar itself is straightforward. unit: assignments exp @{ driver.result = $2; @}; assignments: assignments assignment @{@} - | /* Nothing. */ @{@}; + | /* Nothing. */ @{@}; -assignment: TOKEN_IDENTIFIER ":=" exp @{ driver.variables[*$1] = $3; @}; +assignment: "identifier" ":=" exp @{ driver.variables[*$1] = $3; @}; %left '+' '-'; %left '*' '/'; @@ -7404,8 +7537,8 @@ exp: exp '+' exp @{ $$ = $1 + $3; @} | exp '-' exp @{ $$ = $1 - $3; @} | exp '*' exp @{ $$ = $1 * $3; @} | exp '/' exp @{ $$ = $1 / $3; @} - | TOKEN_IDENTIFIER @{ $$ = driver.variables[*$1]; @} - | TOKEN_NUMBER @{ $$ = $1; @}; + | "identifier" @{ $$ = driver.variables[*$1]; @} + | "number" @{ $$ = $1; @}; %% @end example @@ -7438,6 +7571,10 @@ 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 %@} @end example @@ -7463,7 +7600,7 @@ blank [ \t] @end example @noindent -The following paragraph suffices to track locations acurately. Each +The following paragraph suffices to track locations accurately. Each time @code{yylex} is invoked, the begin position is moved onto the end position. Then when a pattern is matched, the end position is advanced of its width. In case it matched ends of lines, the end @@ -7485,22 +7622,28 @@ preceding tokens. Comments would be treated equally. @end example @noindent -The rules are simple, just note the use of the driver to report -errors. +The rules are simple, just note the use of the driver to report errors. +It is convenient to use a typedef to shorten +@code{yy::calcxx_parser::token::identifier} into +@code{token::identifier} for instance. @comment file: calc++-scanner.ll @example +%@{ + typedef yy::calcxx_parser::token token; +%@} + [-+*/] return yytext[0]; -":=" return TOKEN_ASSIGN; +":=" 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; + return token::NUMBER; @} -@{id@} yylval->sval = new std::string (yytext); return TOKEN_IDENTIFIER; +@{id@} yylval->sval = new std::string (yytext); return token::IDENTIFIER; . driver.error (*yylloc, "invalid character"); %% @end example @@ -7926,7 +8069,7 @@ parser file. @xref{Decl Summary}. @end deffn @deffn {Directive} %nonassoc -Bison declaration to assign non-associativity to token(s). +Bison declaration to assign nonassociativity to token(s). @xref{Precedence Decl, ,Operator Precedence}. @end deffn @@ -7951,6 +8094,11 @@ Bison declaration to request a pure (reentrant) parser. @xref{Pure Decl, ,A Pure (Reentrant) Parser}. @end deffn +@deffn {Directive} %require "@var{version}" +Require version @var{version} or higher of Bison. @xref{Require Decl, , +Require a Version of Bison}. +@end deffn + @deffn {Directive} %right Bison declaration to assign right associativity to token(s). @xref{Precedence Decl, ,Operator Precedence}. @@ -8006,7 +8154,7 @@ token. @xref{Action Features, ,Special Features for Use in Actions}. @end deffn @deffn {Variable} yychar -External integer variable that contains the integer value of the current +External integer variable that contains the integer value of the look-ahead token. (In a pure parser, it is a local variable within @code{yyparse}.) Error-recovery rule actions may examine this variable. @xref{Action Features, ,Special Features for Use in Actions}. @@ -8067,7 +8215,7 @@ the next token. @xref{Lexical, ,The Lexical Analyzer Function @deffn {Macro} YYLEX_PARAM An obsolete macro for specifying an extra argument (or list of extra -arguments) for @code{yyparse} to pass to @code{yylex}. he use of this +arguments) for @code{yyparse} to pass to @code{yylex}. The use of this macro is deprecated, and is supported only for Yacc like parsers. @xref{Pure Calling,, Calling Conventions for Pure Parsers}. @end deffn @@ -8076,9 +8224,12 @@ macro is deprecated, and is supported only for Yacc like parsers. External variable in which @code{yylex} should place the line and column numbers associated with a token. (In a pure parser, it is a local variable within @code{yyparse}, and its address is passed to -@code{yylex}.) You can ignore this variable if you don't use the -@samp{@@} feature in the grammar actions. @xref{Token Locations, -,Textual Locations of Tokens}. +@code{yylex}.) +You can ignore this variable if you don't use the @samp{@@} feature in the +grammar actions. +@xref{Token Locations, ,Textual Locations of Tokens}. +In semantic actions, it stores the location of the look-ahead token. +@xref{Actions and Locations, ,Actions and Locations}. @end deffn @deffn {Type} YYLTYPE @@ -8090,7 +8241,10 @@ members. @xref{Location Type, , Data Types of Locations}. External variable in which @code{yylex} should place the semantic value associated with a token. (In a pure parser, it is a local variable within @code{yyparse}, and its address is passed to -@code{yylex}.) @xref{Token Values, ,Semantic Values of Tokens}. +@code{yylex}.) +@xref{Token Values, ,Semantic Values of Tokens}. +In semantic actions, it stores the semantic value of the look-ahead token. +@xref{Actions, ,Actions}. @end deffn @deffn {Macro} YYMAXDEPTH @@ -8351,7 +8505,7 @@ grammatically indivisible. The piece of text it represents is a token. @c LocalWords: yychar yydebug msg YYNTOKENS YYNNTS YYNRULES YYNSTATES @c LocalWords: cparse clex deftypefun NE defmac YYACCEPT YYABORT param @c LocalWords: strncmp intval tindex lvalp locp llocp typealt YYBACKUP -@c LocalWords: YYEMPTY YYRECOVERING yyclearin GE def UMINUS maybeword +@c LocalWords: YYEMPTY YYEOF YYRECOVERING yyclearin GE def UMINUS maybeword @c LocalWords: Johnstone Shamsa Sadaf Hussain Tomita TR uref YYMAXDEPTH @c LocalWords: YYINITDEPTH stmnts ref stmnt initdcl maybeasm VCG notype @c LocalWords: hexflag STR exdent itemset asis DYYDEBUG YYFPRINTF args