X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/4626a15dd155e1895262c48945a1c2b1d79b481f..927b425baae16fc1d50e092b78b944e281b521f6:/doc/bison.texinfo?ds=inline diff --git a/doc/bison.texinfo b/doc/bison.texinfo index 47b6720e..c004a842 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 @@ -461,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 @@ -469,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} @@ -733,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 @@ -910,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 @@ -1096,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} @@ -2126,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: @@ -2411,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 @@ -2585,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 @@ -2661,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 @@ -2680,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. @@ -2782,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: @@ -2791,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. @@ -2853,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}. @@ -2908,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 @@ -3025,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: @@ -3056,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 @@ -3141,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 @@ -3458,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 @@ -3709,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: @@ -3743,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. @@ -3788,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}. @@ -3810,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. -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}. +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}}). - -@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. @end deffn For instance: @@ -3854,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 @@ -3883,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 @@ -3913,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} @@ -3946,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 @@ -3977,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 @@ -4084,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) @@ -4101,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 @@ -4320,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. @@ -4468,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 @@ -4516,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 @@ -4566,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: @@ -4782,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 @@ -4798,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; @@ -4815,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 @@ -4858,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. @@ -5053,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 @@ -5628,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 @@ -5693,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 @@ -5870,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 @@ -6697,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}: @@ -6711,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 @@ -6790,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 @@ -7055,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. @@ -7083,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}) @@ -7134,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. @@ -7411,6 +7508,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" @@ -7429,7 +7527,7 @@ The grammar itself is straightforward. unit: assignments exp @{ driver.result = $2; @}; assignments: assignments assignment @{@} - | /* Nothing. */ @{@}; + | /* Nothing. */ @{@}; assignment: "identifier" ":=" exp @{ driver.variables[*$1] = $3; @}; @@ -7498,7 +7596,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 @@ -7523,7 +7621,7 @@ preceding tokens. Comments would be treated equally. 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 isntance. +@code{token::identifier} for instance. @comment file: calc++-scanner.ll @example @@ -7967,7 +8065,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 @@ -8052,7 +8150,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}. @@ -8113,7 +8211,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 @@ -8122,9 +8220,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 @@ -8136,7 +8237,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 @@ -8397,7 +8501,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