X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/b10dd689b645f4f62d616cb9fbc14f416e8e06bd..f52e1e5e44fd155cfe0fbbf0fd370e99a256c20e:/doc/bison.texinfo?ds=inline diff --git a/doc/bison.texinfo b/doc/bison.texinfo index 1a66edc4..0c09e35e 100644 --- a/doc/bison.texinfo +++ b/doc/bison.texinfo @@ -33,14 +33,14 @@ This manual (@value{UPDATED}) is for @acronym{GNU} Bison (version @value{VERSION}), the @acronym{GNU} parser generator. -Copyright @copyright{} 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998, -1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 Free +Copyright @copyright{} 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998, 1999, +2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. @quotation Permission is granted to copy, distribute and/or modify this document under the terms of the @acronym{GNU} Free Documentation License, -Version 1.2 or any later version published by the Free Software +Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections, with the Front-Cover texts being ``A @acronym{GNU} Manual,'' and with the Back-Cover Texts as in (a) below. A copy of the license is included in the section entitled @@ -206,6 +206,7 @@ Defining Language Semantics * Mid-Rule Actions:: Most actions go at the end of a rule. This says when, why and how to use the exceptional action in the middle of a rule. +* Named References:: Using named references in actions. Tracking Locations @@ -351,9 +352,10 @@ Copying This Manual @cindex introduction @dfn{Bison} is a general-purpose parser generator that converts an -annotated context-free grammar into a deterministic or @acronym{GLR} -parser employing @acronym{LALR}(1), @acronym{IELR}(1), or canonical -@acronym{LR}(1) parser tables. +annotated context-free grammar into a deterministic @acronym{LR} or +generalized @acronym{LR} (@acronym{GLR}) parser employing +@acronym{LALR}(1), @acronym{IELR}(1), or canonical @acronym{LR}(1) +parser tables. Once you are proficient with Bison, you can use it to develop a wide range of language parsers, from those used in simple desk calculators to complex programming languages. @@ -473,8 +475,8 @@ For historical reasons, Bison by default is limited by the additional restrictions of @acronym{LALR}(1), which is hard to explain simply. @xref{Mystery Conflicts, ,Mysterious Reduce/Reduce Conflicts}, for more information on this. -To escape these additional restrictions, you can request -@acronym{IELR}(1) or canonical @acronym{LR}(1) parser tables. +As an experimental feature, you can escape these additional restrictions by +requesting @acronym{IELR}(1) or canonical @acronym{LR}(1) parser tables. @xref{Decl Summary,,lr.type}, to learn how. @cindex @acronym{GLR} parsing @@ -3365,6 +3367,7 @@ the numbers associated with @var{x} and @var{y}. * Mid-Rule Actions:: Most actions go at the end of a rule. This says when, why and how to use the exceptional action in the middle of a rule. +* Named References:: Using named references in actions. @end menu @node Value Type @@ -3426,6 +3429,8 @@ Decl, ,Nonterminal Symbols}). @cindex action @vindex $$ @vindex $@var{n} +@vindex $@var{name} +@vindex $[@var{name}] An action accompanies a syntactic rule and contains C code to be executed each time an instance of that rule is recognized. The task of most actions @@ -3442,9 +3447,12 @@ Actions, ,Actions in Mid-Rule}). The C code in an action can refer to the semantic values of the components matched by the rule with the construct @code{$@var{n}}, which stands for the value of the @var{n}th component. The semantic value for the grouping -being constructed is @code{$$}. Bison translates both of these +being constructed is @code{$$}. In addition, the semantic values of +symbols can be accessed with the named references construct +@code{$@var{name}} or @code{$[@var{name}]}. Bison translates both of these constructs into expressions of the appropriate type when it copies the -actions into the parser file. @code{$$} is translated to a modifiable +actions into the parser file. @code{$$} (or @code{$@var{name}}, when it +stands for the current grouping) is translated to a modifiable lvalue, so it can be assigned to. Here is a typical example: @@ -3457,16 +3465,31 @@ exp: @dots{} @end group @end example +Or, in terms of named references: + +@example +@group +exp[result]: @dots{} + | exp[left] '+' exp[right] + @{ $result = $left + $right; @} +@end group +@end example + @noindent This rule constructs an @code{exp} from two smaller @code{exp} groupings connected by a plus-sign token. In the action, @code{$1} and @code{$3} +(@code{$left} and @code{$right}) refer to the semantic values of the two component @code{exp} groupings, which are the first and third symbols on the right hand side of the rule. -The sum is stored into @code{$$} so that it becomes the semantic value of +The sum is stored into @code{$$} (@code{$result}) so that it becomes the +semantic value of the addition-expression just recognized by the rule. If there were a useful semantic value associated with the @samp{+} token, it could be referred to as @code{$2}. +@xref{Named References,,Using Named References}, for more information +about using the named references construct. + Note that the vertical-bar character @samp{|} is really a rule separator, and actions are attached to a single rule. This is a difference with tools like Flex, for which @samp{|} stands for either @@ -3761,6 +3784,93 @@ compound: subroutine Now Bison can execute the action in the rule for @code{subroutine} without deciding which rule for @code{compound} it will eventually use. +@node Named References +@subsection Using Named References +@cindex named references + +While every semantic value can be accessed with positional references +@code{$@var{n}} and @code{$$}, it's often much more convenient to refer to +them by name. First of all, original symbol names may be used as named +references. For example: + +@example +@group +invocation: op '(' args ')' + @{ $invocation = new_invocation ($op, $args, @@invocation); @} +@end group +@end example + +@noindent +The positional @code{$$}, @code{@@$}, @code{$n}, and @code{@@n} can be +mixed with @code{$name} and @code{@@name} arbitrarily. For example: + +@example +@group +invocation: op '(' args ')' + @{ $$ = new_invocation ($op, $args, @@$); @} +@end group +@end example + +@noindent +However, sometimes regular symbol names are not sufficient due to +ambiguities: + +@example +@group +exp: exp '/' exp + @{ $exp = $exp / $exp; @} // $exp is ambiguous. + +exp: exp '/' exp + @{ $$ = $1 / $exp; @} // One usage is ambiguous. + +exp: exp '/' exp + @{ $$ = $1 / $3; @} // No error. +@end group +@end example + +@noindent +When ambiguity occurs, explicitly declared names may be used for values and +locations. Explicit names are declared as a bracketed name after a symbol +appearance in rule definitions. For example: +@example +@group +exp[result]: exp[left] '/' exp[right] + @{ $result = $left / $right; @} +@end group +@end example + +@noindent +Explicit names may be declared for RHS and for LHS symbols as well. In order +to access a semantic value generated by a mid-rule action, an explicit name +may also be declared by putting a bracketed name after the closing brace of +the mid-rule action code: +@example +@group +exp[res]: exp[x] '+' @{$left = $x;@}[left] exp[right] + @{ $res = $left + $right; @} +@end group +@end example + +@noindent + +In references, in order to specify names containing dots and dashes, an explicit +bracketed syntax @code{$[name]} and @code{@@[name]} must be used: +@example +@group +if-stmt: IF '(' expr ')' THEN then.stmt ';' + @{ $[if-stmt] = new_if_stmt ($expr, $[then.stmt]); @} +@end group +@end example + +It often happens that named references are followed by a dot, dash or other +C punctuation marks and operators. By default, Bison will read +@code{$name.suffix} as a reference to symbol value @code{$name} followed by +@samp{.suffix}, i.e., an access to the @samp{suffix} field of the semantic +value. In order to force Bison to recognize @code{name.suffix} in its entirety +as the name of a semantic value, bracketed syntax @code{$[name.suffix]} +must be used. + + @node Locations @section Tracking Locations @cindex location @@ -3804,8 +3914,11 @@ typedef struct YYLTYPE @} YYLTYPE; @end example -At the beginning of the parsing, Bison initializes all these fields to 1 -for @code{yylloc}. +When @code{YYLTYPE} is not defined, at the beginning of the parsing, Bison +initializes all these fields to 1 for @code{yylloc}. To initialize +@code{yylloc} with a custom location type (or to chose a different +initialization), use the @code{%initial-action} directive. @xref{Initial +Action Decl, , Performing Actions before Parsing}. @node Actions and Locations @subsection Actions and Locations @@ -3813,6 +3926,8 @@ for @code{yylloc}. @cindex actions, location @vindex @@$ @vindex @@@var{n} +@vindex @@@var{name} +@vindex @@[@var{name}] Actions are not only useful for defining language semantics, but also for describing the behavior of the output parser with locations. @@ -3824,6 +3939,11 @@ The location of the @var{n}th component of the right hand side is @code{@@@var{n}}, while the location of the left hand side grouping is @code{@@$}. +In addition, the named references construct @code{@@@var{name}} and +@code{@@[@var{name}]} may also be used to address the symbol locations. +@xref{Named References,,Using Named References}, for more information +about using the named references construct. + Here is a basic example using the default data type for locations: @example @@ -4495,8 +4615,8 @@ number which Bison printed. With @acronym{GLR} parsers, add an @code{%expect-rr} declaration as well. @end itemize -Now Bison will warn you if you introduce an unexpected conflict, but -will keep silent otherwise. +Now Bison will report an error if you introduce an unexpected conflict, +but will keep silent otherwise. @node Start Decl @subsection The Start-Symbol @@ -4577,7 +4697,7 @@ The following Bison declaration says that you want the parser to be a push parser (@pxref{Decl Summary,,%define api.push-pull}): @example -%define api.push-pull "push" +%define api.push-pull push @end example In almost all cases, you want to ensure that your push parser is also @@ -4588,7 +4708,7 @@ what you are doing, your declarations should look like this: @example %define api.pure -%define api.push-pull "push" +%define api.push-pull push @end example There is a major notable functional difference between the pure push parser @@ -4637,14 +4757,14 @@ for use by the next invocation of the @code{yypush_parse} function. Bison also supports both the push parser interface along with the pull parser interface in the same generated parser. In order to get this functionality, -you should replace the @code{%define api.push-pull "push"} declaration with the -@code{%define api.push-pull "both"} declaration. Doing this will create all of +you should replace the @code{%define api.push-pull push} declaration with the +@code{%define api.push-pull both} declaration. Doing this will create all of the symbols mentioned earlier along with the two extra symbols, @code{yyparse} and @code{yypull_parse}. @code{yyparse} can be used exactly as it normally would be used. However, the user should note that it is implemented in the generated parser by calling @code{yypull_parse}. This makes the @code{yyparse} function that is generated with the -@code{%define api.push-pull "both"} declaration slower than the normal +@code{%define api.push-pull both} declaration slower than the normal @code{yyparse} function. If the user calls the @code{yypull_parse} function it will parse the rest of the input stream. It is possible to @code{yypush_parse} tokens to select a subgrammar @@ -4661,8 +4781,8 @@ yypstate_delete (ps); @end example Adding the @code{%define api.pure} declaration does exactly the same thing to -the generated parser with @code{%define api.push-pull "both"} as it did for -@code{%define api.push-pull "push"}. +the generated parser with @code{%define api.push-pull both} as it did for +@code{%define api.push-pull push}. @node Decl Summary @subsection Bison Declaration Summary @@ -4752,7 +4872,9 @@ use this form instead. @var{qualifier} identifies the purpose of @var{code} and thus the location(s) where Bison should generate it. -Not all values of @var{qualifier} are available for all target languages: +Not all @var{qualifier}s are accepted for all target languages. +Unaccepted @var{qualifier}s produce an error. +Some of the accepted @var{qualifier}s are: @itemize @bullet @item requires @@ -4831,34 +4953,41 @@ already defined, so that the debugging facilities are compiled. @end deffn @deffn {Directive} %define @var{variable} +@deffnx {Directive} %define @var{variable} @var{value} @deffnx {Directive} %define @var{variable} "@var{value}" Define a variable to adjust Bison's behavior. -The possible choices for @var{variable}, as well as their meanings, depend on -the selected target language and/or the parser skeleton (@pxref{Decl -Summary,,%language}, @pxref{Decl Summary,,%skeleton}). -Bison will warn if a @var{variable} is defined multiple times. +It is an error if a @var{variable} is defined by @code{%define} multiple +times, but see @ref{Bison Options,,-D @var{name}[=@var{value}]}. -Omitting @code{"@var{value}"} is always equivalent to specifying it as +@var{value} must be placed in quotation marks if it contains any +character other than a letter, underscore, period, dash, or non-initial +digit. + +Omitting @code{"@var{value}"} entirely is always equivalent to specifying @code{""}. -Some @var{variable}s may be used as Booleans. +Some @var{variable}s take Boolean values. In this case, Bison will complain if the variable definition does not meet one of the following four conditions: @enumerate -@item @code{"@var{value}"} is @code{"true"} +@item @code{@var{value}} is @code{true} -@item @code{"@var{value}"} is omitted (or is @code{""}). -This is equivalent to @code{"true"}. +@item @code{@var{value}} is omitted (or @code{""} is specified). +This is equivalent to @code{true}. -@item @code{"@var{value}"} is @code{"false"}. +@item @code{@var{value}} is @code{false}. @item @var{variable} is never defined. -In this case, Bison selects a default value, which may depend on the selected -target language and/or parser skeleton. +In this case, Bison selects a default value. @end enumerate +What @var{variable}s are accepted, as well as their meanings and default +values, depend on the selected target language and/or the parser +skeleton (@pxref{Decl Summary,,%language}, @pxref{Decl +Summary,,%skeleton}). +Unaccepted @var{variable}s produce an error. Some of the accepted @var{variable}s are: @itemize @bullet @@ -4873,7 +5002,7 @@ Some of the accepted @var{variable}s are: @item Accepted Values: Boolean -@item Default Value: @code{"false"} +@item Default Value: @code{false} @end itemize @item api.push-pull @@ -4882,89 +5011,97 @@ Some of the accepted @var{variable}s are: @itemize @bullet @item Language(s): C (deterministic parsers only) -@item Purpose: Requests a pull parser, a push parser, or both. +@item Purpose: Request a pull parser, a push parser, or both. @xref{Push Decl, ,A Push Parser}. (The current push parsing interface is experimental and may evolve. More user feedback will help to stabilize it.) -@item Accepted Values: @code{"pull"}, @code{"push"}, @code{"both"} +@item Accepted Values: @code{pull}, @code{push}, @code{both} -@item Default Value: @code{"pull"} +@item Default Value: @code{pull} @end itemize +@c ================================================== lr.default-reductions + @item lr.default-reductions @cindex default reductions @findex %define lr.default-reductions @cindex delayed syntax errors @cindex syntax errors delayed +@cindex @acronym{LAC} +@findex %nonassoc @itemize @bullet @item Language(s): all -@item Purpose: Specifies the kind of states that are permitted to +@item Purpose: Specify the kind of states that are permitted to contain default reductions. -That is, in such a state, Bison declares the reduction with the largest -lookahead set to be the default reduction and then removes that +That is, in such a state, Bison selects the reduction with the largest +lookahead set to be the default parser action and then removes that lookahead set. -The advantages of default reductions are discussed below. -The disadvantage is that, when the generated parser encounters a -syntactically unacceptable token, the parser might then perform -unnecessary default reductions before it can detect the syntax error. - -(This feature is experimental. +(The ability to specify where default reductions should be used is +experimental. More user feedback will help to stabilize it.) @item Accepted Values: @itemize -@item @code{"all"}. -For @acronym{LALR} and @acronym{IELR} parsers (@pxref{Decl -Summary,,lr.type}) by default, all states are permitted to contain -default reductions. -The advantage is that parser table sizes can be significantly reduced. -The reason Bison does not by default attempt to address the disadvantage -of delayed syntax error detection is that this disadvantage is already -inherent in @acronym{LALR} and @acronym{IELR} parser tables. -That is, unlike in a canonical @acronym{LR} state, the lookahead sets of -reductions in an @acronym{LALR} or @acronym{IELR} state can contain -tokens that are syntactically incorrect for some left contexts. - -@item @code{"consistent"}. +@item @code{all}. +This is the traditional Bison behavior. +The main advantage is a significant decrease in the size of the parser +tables. +The disadvantage is that, when the generated parser encounters a +syntactically unacceptable token, the parser might then perform +unnecessary default reductions before it can detect the syntax error. +Such delayed syntax error detection is usually inherent in +@acronym{LALR} and @acronym{IELR} parser tables anyway due to +@acronym{LR} state merging (@pxref{Decl Summary,,lr.type}). +Furthermore, the use of @code{%nonassoc} can contribute to delayed +syntax error detection even in the case of canonical @acronym{LR}. +As an experimental feature, delayed syntax error detection can be +overcome in all cases by enabling @acronym{LAC} (@pxref{Decl +Summary,,parse.lac}, for details, including a discussion of the effects +of delayed syntax error detection). + +@item @code{consistent}. @cindex consistent states A consistent state is a state that has only one possible action. If that action is a reduction, then the parser does not need to request a lookahead token from the scanner before performing that action. -However, the parser only recognizes the ability to ignore the lookahead -token when such a reduction is encoded as a default reduction. -Thus, if default reductions are permitted in and only in consistent -states, then a canonical @acronym{LR} parser reports a syntax error as -soon as it @emph{needs} the syntactically unacceptable token from the -scanner. - -@item @code{"accepting"}. +However, the parser recognizes the ability to ignore the lookahead token +in this way only when such a reduction is encoded as a default +reduction. +Thus, if default reductions are permitted only in consistent states, +then a canonical @acronym{LR} parser that does not employ +@code{%nonassoc} detects a syntax error as soon as it @emph{needs} the +syntactically unacceptable token from the scanner. + +@item @code{accepting}. @cindex accepting state -By default, the only default reduction permitted in a canonical -@acronym{LR} parser is the accept action in the accepting state, which -the parser reaches only after reading all tokens from the input. -Thus, the default canonical @acronym{LR} parser reports a syntax error -as soon as it @emph{reaches} the syntactically unacceptable token -without performing any extra reductions. +In the accepting state, the default reduction is actually the accept +action. +In this case, a canonical @acronym{LR} parser that does not employ +@code{%nonassoc} detects a syntax error as soon as it @emph{reaches} the +syntactically unacceptable token in the input. +That is, it does not perform any extra reductions. @end itemize @item Default Value: @itemize -@item @code{"accepting"} if @code{lr.type} is @code{"canonical LR"}. -@item @code{"all"} otherwise. +@item @code{accepting} if @code{lr.type} is @code{canonical-lr}. +@item @code{all} otherwise. @end itemize @end itemize +@c ============================================ lr.keep-unreachable-states + @item lr.keep-unreachable-states @findex %define lr.keep-unreachable-states @itemize @bullet @item Language(s): all -@item Purpose: Requests that Bison allow unreachable parser states to remain in -the parser tables. +@item Purpose: Request that Bison allow unreachable parser states to +remain in the parser tables. Bison considers a state to be unreachable if there exists no sequence of transitions from the start state to that state. A state can become unreachable during conflict resolution if Bison disables a @@ -4974,7 +5111,7 @@ are useless in the generated parser. @item Accepted Values: Boolean -@item Default Value: @code{"false"} +@item Default Value: @code{false} @item Caveats: @@ -5000,6 +5137,8 @@ However, Bison does not compute which goto actions are useless. @end itemize @end itemize +@c ================================================== lr.type + @item lr.type @findex %define lr.type @cindex @acronym{LALR} @@ -5009,14 +5148,14 @@ However, Bison does not compute which goto actions are useless. @itemize @bullet @item Language(s): all -@item Purpose: Specifies the type of parser tables within the +@item Purpose: Specify the type of parser tables within the @acronym{LR}(1) family. (This feature is experimental. More user feedback will help to stabilize it.) @item Accepted Values: @itemize -@item @code{"LALR"}. +@item @code{lalr}. While Bison generates @acronym{LALR} parser tables by default for historical reasons, @acronym{IELR} or canonical @acronym{LR} is almost always preferable for deterministic parsers. @@ -5036,6 +5175,10 @@ In this case, the use of @acronym{LALR} parser tables is guaranteed not to alter the language accepted by the parser. @acronym{LALR} parser tables are the smallest parser tables Bison can currently generate, so they may be preferable. +Nevertheless, once you begin to resolve conflicts statically, +@acronym{GLR} begins to behave more like a deterministic parser, and so +@acronym{IELR} and canonical @acronym{LR} can be helpful to avoid +@acronym{LALR}'s mysterious behavior. @item Occasionally during development, an especially malformed grammar with a major recurring flaw may severely impede the @acronym{IELR} or @@ -5045,7 +5188,7 @@ investigate such problems while ignoring the more subtle differences from @acronym{IELR} and canonical @acronym{LR}. @end itemize -@item @code{"IELR"}. +@item @code{ielr}. @acronym{IELR} is a minimal @acronym{LR} algorithm. That is, given any grammar (@acronym{LR} or non-@acronym{LR}), @acronym{IELR} and canonical @acronym{LR} always accept exactly the same @@ -5059,23 +5202,29 @@ grammars, the number of conflicts for @acronym{IELR} is often an order of magnitude less as well. This can significantly reduce the complexity of developing of a grammar. -@item @code{"canonical LR"}. +@item @code{canonical-lr}. @cindex delayed syntax errors @cindex syntax errors delayed -The only advantage of canonical @acronym{LR} over @acronym{IELR} is -that, for every left context of every canonical @acronym{LR} state, the -set of tokens accepted by that state is the exact set of tokens that is -syntactically acceptable in that left context. -Thus, the only difference in parsing behavior is that the canonical -@acronym{LR} parser can report a syntax error as soon as possible -without performing any unnecessary reductions. -@xref{Decl Summary,,lr.default-reductions}, for further details. -Even when canonical @acronym{LR} behavior is ultimately desired, -@acronym{IELR}'s elimination of duplicate conflicts should still -facilitate the development of a grammar. +@cindex @acronym{LAC} +@findex %nonassoc +While inefficient, canonical @acronym{LR} parser tables can be an +interesting means to explore a grammar because they have a property that +@acronym{IELR} and @acronym{LALR} tables do not. +That is, if @code{%nonassoc} is not used and default reductions are left +disabled (@pxref{Decl Summary,,lr.default-reductions}), then, for every +left context of every canonical @acronym{LR} state, the set of tokens +accepted by that state is guaranteed to be the exact set of tokens that +is syntactically acceptable in that left context. +It might then seem that an advantage of canonical @acronym{LR} parsers +in production is that, under the above constraints, they are guaranteed +to detect a syntax error as soon as possible without performing any +unnecessary reductions. +However, @acronym{IELR} parsers using @acronym{LAC} (@pxref{Decl +Summary,,parse.lac}) are also able to achieve this behavior without +sacrificing @code{%nonassoc} or default reductions. @end itemize -@item Default Value: @code{"LALR"} +@item Default Value: @code{lalr} @end itemize @item namespace @@ -5084,7 +5233,7 @@ facilitate the development of a grammar. @itemize @item Languages(s): C++ -@item Purpose: Specifies the namespace for the parser class. +@item Purpose: Specify the namespace for the parser class. For example, if you specify: @smallexample @@ -5129,6 +5278,89 @@ For example, if you specify: The parser namespace is @code{foo} and @code{yylex} is referenced as @code{bar::lex}. @end itemize + +@c ================================================== parse.lac +@item parse.lac +@findex %define parse.lac +@cindex @acronym{LAC} +@cindex lookahead correction + +@itemize +@item Languages(s): C + +@item Purpose: Enable @acronym{LAC} (lookahead correction) to improve +syntax error handling. + +Canonical @acronym{LR}, @acronym{IELR}, and @acronym{LALR} can suffer +from a couple of problems upon encountering a syntax error. First, the +parser might perform additional parser stack reductions before +discovering the syntax error. Such reductions perform user semantic +actions that are unexpected because they are based on an invalid token, +and they cause error recovery to begin in a different syntactic context +than the one in which the invalid token was encountered. Second, when +verbose error messages are enabled (with @code{%error-verbose} or +@code{#define YYERROR_VERBOSE}), the expected token list in the syntax +error message can both contain invalid tokens and omit valid tokens. + +The culprits for the above problems are @code{%nonassoc}, default +reductions in inconsistent states, and parser state merging. Thus, +@acronym{IELR} and @acronym{LALR} suffer the most. Canonical +@acronym{LR} can suffer only if @code{%nonassoc} is used or if default +reductions are enabled for inconsistent states. + +@acronym{LAC} is a new mechanism within the parsing algorithm that +completely solves these problems for canonical @acronym{LR}, +@acronym{IELR}, and @acronym{LALR} without sacrificing @code{%nonassoc}, +default reductions, or state mering. Conceptually, the mechanism is +straight-forward. Whenever the parser fetches a new token from the +scanner so that it can determine the next parser action, it immediately +suspends normal parsing and performs an exploratory parse using a +temporary copy of the normal parser state stack. During this +exploratory parse, the parser does not perform user semantic actions. +If the exploratory parse reaches a shift action, normal parsing then +resumes on the normal parser stacks. If the exploratory parse reaches +an error instead, the parser reports a syntax error. If verbose syntax +error messages are enabled, the parser must then discover the list of +expected tokens, so it performs a separate exploratory parse for each +token in the grammar. + +There is one subtlety about the use of @acronym{LAC}. That is, when in +a consistent parser state with a default reduction, the parser will not +attempt to fetch a token from the scanner because no lookahead is needed +to determine the next parser action. Thus, whether default reductions +are enabled in consistent states (@pxref{Decl +Summary,,lr.default-reductions}) affects how soon the parser detects a +syntax error: when it @emph{reaches} an erroneous token or when it +eventually @emph{needs} that token as a lookahead. The latter behavior +is probably more intuitive, so Bison currently provides no way to +achieve the former behavior while default reductions are fully enabled. + +Thus, when @acronym{LAC} is in use, for some fixed decision of whether +to enable default reductions in consistent states, canonical +@acronym{LR} and @acronym{IELR} behave exactly the same for both +syntactically acceptable and syntactically unacceptable input. While +@acronym{LALR} still does not support the full language-recognition +power of canonical @acronym{LR} and @acronym{IELR}, @acronym{LAC} at +least enables @acronym{LALR}'s syntax error handling to correctly +reflect @acronym{LALR}'s language-recognition power. + +Because @acronym{LAC} requires many parse actions to be performed twice, +it can have a performance penalty. However, not all parse actions must +be performed twice. Specifically, during a series of default reductions +in consistent states and shift actions, the parser never has to initiate +an exploratory parse. Moreover, the most time-consuming tasks in a +parse are often the file I/O, the lexical analysis performed by the +scanner, and the user's semantic actions, but none of these are +performed during the exploratory parse. Finally, the base of the +temporary stack used during an exploratory parse is a pointer into the +normal parser state stack so that the stack is never physically copied. +In our experience, the performance penalty of @acronym{LAC} has proven +insignificant for practical grammars. + +@item Accepted Values: @code{none}, @code{full} + +@item Default Value: @code{none} +@end itemize @end itemize @end deffn @@ -5456,8 +5688,8 @@ exp: @dots{} @{ @dots{}; *randomness += 1; @dots{} @} More user feedback will help to stabilize it.) You call the function @code{yypush_parse} to parse a single token. This -function is available if either the @code{%define api.push-pull "push"} or -@code{%define api.push-pull "both"} declaration is used. +function is available if either the @code{%define api.push-pull push} or +@code{%define api.push-pull both} declaration is used. @xref{Push Decl, ,A Push Parser}. @deftypefun int yypush_parse (yypstate *yyps) @@ -5474,7 +5706,7 @@ is required to finish parsing the grammar. More user feedback will help to stabilize it.) You call the function @code{yypull_parse} to parse the rest of the input -stream. This function is available if the @code{%define api.push-pull "both"} +stream. This function is available if the @code{%define api.push-pull both} declaration is used. @xref{Push Decl, ,A Push Parser}. @@ -5490,12 +5722,12 @@ The value returned by @code{yypull_parse} is the same as for @code{yyparse}. More user feedback will help to stabilize it.) You call the function @code{yypstate_new} to create a new parser instance. -This function is available if either the @code{%define api.push-pull "push"} or -@code{%define api.push-pull "both"} declaration is used. +This function is available if either the @code{%define api.push-pull push} or +@code{%define api.push-pull both} declaration is used. @xref{Push Decl, ,A Push Parser}. @deftypefun yypstate *yypstate_new (void) -The fuction will return a valid parser instance if there was memory available +The function will return a valid parser instance if there was memory available or 0 if no memory was available. In impure mode, it will also return 0 if a parser instance is currently allocated. @@ -5509,8 +5741,8 @@ allocated. More user feedback will help to stabilize it.) You call the function @code{yypstate_delete} to delete a parser instance. -function is available if either the @code{%define api.push-pull "push"} or -@code{%define api.push-pull "both"} declaration is used. +function is available if either the @code{%define api.push-pull push} or +@code{%define api.push-pull both} declaration is used. @xref{Push Decl, ,A Push Parser}. @deftypefun void yypstate_delete (yypstate *yyps) @@ -6316,8 +6548,10 @@ This particular ambiguity was first encountered in the specifications of Algol 60 and is called the ``dangling @code{else}'' ambiguity. To avoid warnings from Bison about predictable, legitimate shift/reduce -conflicts, use the @code{%expect @var{n}} declaration. There will be no -warning as long as the number of shift/reduce conflicts is exactly @var{n}. +conflicts, use the @code{%expect @var{n}} declaration. +There will be no warning as long as the number of shift/reduce conflicts +is exactly @var{n}, and Bison will report an error if there is a +different number. @xref{Expect Decl, ,Suppressing Conflict Warnings}. The definition of @code{if_stmt} above is solely to blame for the @@ -6959,7 +7193,7 @@ that allows variable-length arrays. The default is 200. Do not allow @code{YYINITDEPTH} to be greater than @code{YYMAXDEPTH}. @c FIXME: C++ output. -Because of semantical differences between C and C++, the deterministic +Because of semantic differences between C and C++, the deterministic parsers in C produced by Bison cannot grow when compiled by C++ compilers. In this precise case (compiling a C parser as C++) you are suggested to grow @code{YYINITDEPTH}. The Bison maintainers hope to fix @@ -7966,8 +8200,8 @@ Treat warnings as errors. @end table A category can be turned off by prefixing its name with @samp{no-}. For -instance, @option{-Wno-syntax} will hide the warnings about unused -variables. +instance, @option{-Wno-yacc} will hide the warnings about +@acronym{POSIX} Yacc incompatibilities. @end table @noindent @@ -7982,8 +8216,32 @@ already defined, so that the debugging facilities are compiled. @item -D @var{name}[=@var{value}] @itemx --define=@var{name}[=@var{value}] -Same as running @samp{%define @var{name} "@var{value}"} (@pxref{Decl -Summary, ,%define}). +@itemx -F @var{name}[=@var{value}] +@itemx --force-define=@var{name}[=@var{value}] +Each of these is equivalent to @samp{%define @var{name} "@var{value}"} +(@pxref{Decl Summary, ,%define}) except that Bison processes multiple +definitions for the same @var{name} as follows: + +@itemize +@item +Bison quietly ignores all command-line definitions for @var{name} except +the last. +@item +If that command-line definition is specified by a @code{-D} or +@code{--define}, Bison reports an error for any @code{%define} +definition for @var{name}. +@item +If that command-line definition is specified by a @code{-F} or +@code{--force-define} instead, Bison quietly ignores all @code{%define} +definitions for @var{name}. +@item +Otherwise, Bison reports an error if there are multiple @code{%define} +definitions for @var{name}. +@end itemize + +You should avoid using @code{-F} and @code{--force-define} in your +makefiles unless you are confident that it is safe to quietly ignore any +conflicting @code{%define} that may be added to the grammar file. @item -L @var{language} @itemx --language=@var{language} @@ -8109,9 +8367,9 @@ More user feedback will help to stabilize it.) @section Option Cross Key Here is a list of options, alphabetized by long option, to help you find -the corresponding short option. +the corresponding short option and directive. -@multitable {@option{--defines=@var{defines-file}}} {@option{-D @var{name}[=@var{value}]}} {@code{%nondeterministic-parser}} +@multitable {@option{--force-define=@var{name}[=@var{value}]}} {@option{-F @var{name}[=@var{value}]}} {@code{%nondeterministic-parser}} @headitem Long Option @tab Short Option @tab Bison Directive @include cross-options.texi @end multitable @@ -8171,8 +8429,8 @@ int yyparse (void); @c - initial action The C++ deterministic parser is selected using the skeleton directive, -@samp{%skeleton "lalr1.c"}, or the synonymous command-line option -@option{--skeleton=lalr1.c}. +@samp{%skeleton "lalr1.cc"}, or the synonymous command-line option +@option{--skeleton=lalr1.cc}. @xref{Decl Summary}. When run, @command{bison} will create several entities in the @samp{yy} @@ -8321,11 +8579,19 @@ this class is detailed below. It can be extended using the it describes an additional member of the parser class, and an additional argument for its constructor. -@defcv {Type} {parser} {semantic_value_type} -@defcvx {Type} {parser} {location_value_type} +@defcv {Type} {parser} {semantic_type} +@defcvx {Type} {parser} {location_type} The types for semantics value and locations. @end defcv +@defcv {Type} {parser} {token} +A structure that contains (only) the definition of the tokens as the +@code{yytokentype} enumeration. To refer to the token @code{FOO}, the +scanner should use @code{yy::parser::token::FOO}. The scanner can use +@samp{typedef yy::parser::token token;} to ``import'' the token enumeration +(@pxref{Calc++ Scanner}). +@end defcv + @deftypemethod {parser} {} parser (@var{type1} @var{arg1}, ...) Build a new parser object. There are no arguments by default, unless @samp{%parse-param @{@var{type1} @var{arg1}@}} was used. @@ -8364,7 +8630,7 @@ The parser invokes the scanner by calling @code{yylex}. Contrary to C parsers, C++ parsers are always pure: there is no point in using the @code{%define api.pure} directive. Therefore the interface is as follows. -@deftypemethod {parser} {int} yylex (semantic_value_type& @var{yylval}, location_type& @var{yylloc}, @var{type1} @var{arg1}, ...) +@deftypemethod {parser} {int} yylex (semantic_type* @var{yylval}, location_type* @var{yylloc}, @var{type1} @var{arg1}, ...) Return the next token. Its type is the return value, its semantic value and location being @var{yylval} and @var{yylloc}. Invocations of @samp{%lex-param @{@var{type1} @var{arg1}@}} yield additional arguments. @@ -8604,7 +8870,7 @@ global variables. @noindent Then we request the location tracking feature, and initialize the -first location's file name. Afterwards new locations are computed +first location's file name. Afterward new locations are computed relatively to the previous locations: the file name will be automatically propagated. @@ -8994,7 +9260,7 @@ in a file; Bison itself defines a class representing a @dfn{location}, a range composed of a pair of positions (possibly spanning several files). The location class is an inner class of the parser; the name is @code{Location} by default, and may also be renamed using -@code{%define location_type "@var{class-name}}. +@code{%define location_type "@var{class-name}"}. The location class treats the position as a completely opaque value. By default, the class name is @code{Position}, but this can be changed @@ -9138,7 +9404,7 @@ changed using @code{%define location_type "@var{class-name}".} @deftypemethod {Lexer} {int} yylex () Return the next token. Its type is the return value, its semantic -value and location are saved and returned by the ther methods in the +value and location are saved and returned by the their methods in the interface. Use @code{%define lex_throws} to specify any uncaught exceptions. @@ -9156,7 +9422,7 @@ The return type can be changed using @code{%define position_type @end deftypemethod @deftypemethod {Lexer} {Object} getLVal () -Return the semantical value of the last token that yylex returned. +Return the semantic value of the last token that yylex returned. The return type can be changed using @code{%define stype "@var{class-name}".} @@ -9226,11 +9492,6 @@ Start error recovery without printing an error message. @xref{Error Recovery}. @end deffn -@deffn {Statement} {return YYFAIL;} -Print an error message and start error recovery. -@xref{Error Recovery}. -@end deffn - @deftypefn {Function} {boolean} recovering () Return whether error recovery is being done. In this state, the parser reads token until it reaches a known state, and then restarts normal @@ -9272,7 +9533,7 @@ corresponds to these C macros.}. @item Java lacks unions, so @code{%union} has no effect. Instead, semantic values have a common base type: @code{Object} or as specified by -@code{%define stype}. Angle backets on @code{%token}, @code{type}, +@samp{%define stype}. Angle brackets on @code{%token}, @code{type}, @code{$@var{n}} and @code{$$} specify subtypes rather than fields of an union. The type of @code{$$}, even with angle brackets, is the base type since Java casts are not allow on the left-hand side of assignments. @@ -9281,7 +9542,7 @@ left-hand side of assignments. See @pxref{Java Semantic Values} and @pxref{Java Action Features}. @item -The prolog declarations have a different meaning than in C/C++ code. +The prologue declarations have a different meaning than in C/C++ code. @table @asis @item @code{%code imports} blocks are placed at the beginning of the Java source code. They may @@ -9847,6 +10108,16 @@ In an action, the location of the @var{n}-th symbol of the right-hand side of the rule. @xref{Locations, , Locations Overview}. @end deffn +@deffn {Variable} @@@var{name} +In an action, the location of a symbol addressed by name. +@xref{Locations, , Locations Overview}. +@end deffn + +@deffn {Variable} @@[@var{name}] +In an action, the location of a symbol addressed by name. +@xref{Locations, , Locations Overview}. +@end deffn + @deffn {Variable} $$ In an action, the semantic value of the left-hand side of the rule. @xref{Actions}. @@ -9857,6 +10128,16 @@ In an action, the semantic value of the @var{n}-th symbol of the right-hand side of the rule. @xref{Actions}. @end deffn +@deffn {Variable} $@var{name} +In an action, the semantic value of a symbol addressed by name. +@xref{Actions}. +@end deffn + +@deffn {Variable} $[@var{name}] +In an action, the semantic value of a symbol addressed by name. +@xref{Actions}. +@end deffn + @deffn {Delimiter} %% Delimiter used to separate the grammar rule section from the Bison declarations section or the epilogue. @@ -9937,6 +10218,7 @@ Precedence}. @deffn {Directive} %define @var{define-variable} @deffnx {Directive} %define @var{define-variable} @var{value} +@deffnx {Directive} %define @var{define-variable} "@var{value}" Define a variable to adjust Bison's behavior. @xref{Decl Summary,,%define}. @end deffn @@ -10403,6 +10685,14 @@ performs some operation. @item Input stream A continuous flow of data between devices or programs. +@item @acronym{LAC} (Lookahead Correction) +A parsing mechanism that fixes the problem of delayed syntax error +detection, which is caused by LR state merging, default reductions, and +the use of @code{%nonassoc}. Delayed syntax error detection results in +unexpected semantic actions, initiation of error recovery in the wrong +syntactic context, and an incorrect list of expected tokens in a verbose +syntax error message. @xref{Decl Summary,,parse.lac}. + @item Language construct One of the typical usage schemas of the language. For example, one of the constructs of the C language is the @code{if} statement. @@ -10530,32 +10820,59 @@ grammatically indivisible. The piece of text it represents is a token. @bye -@c LocalWords: texinfo setfilename settitle setchapternewpage finalout -@c LocalWords: ifinfo smallbook shorttitlepage titlepage GPL FIXME iftex -@c LocalWords: akim fn cp syncodeindex vr tp synindex dircategory direntry -@c LocalWords: ifset vskip pt filll insertcopying sp ISBN Etienne Suvasa -@c LocalWords: ifnottex yyparse detailmenu GLR RPN Calc var Decls Rpcalc -@c LocalWords: rpcalc Lexer Expr ltcalc mfcalc yylex -@c LocalWords: yyerror pxref LR yylval cindex dfn LALR samp gpl BNF xref -@c LocalWords: const int paren ifnotinfo AC noindent emph expr stmt findex -@c LocalWords: glr YYSTYPE TYPENAME prog dprec printf decl init stmtMerge -@c LocalWords: pre STDC GNUC endif yy YY alloca lf stddef stdlib YYDEBUG -@c LocalWords: NUM exp subsubsection kbd Ctrl ctype EOF getchar isdigit -@c LocalWords: ungetc stdin scanf sc calc ulator ls lm cc NEG prec yyerrok -@c LocalWords: longjmp fprintf stderr yylloc YYLTYPE cos ln -@c LocalWords: smallexample symrec val tptr FNCT fnctptr func struct sym -@c LocalWords: fnct putsym getsym fname arith fncts atan ptr malloc sizeof -@c LocalWords: strlen strcpy fctn strcmp isalpha symbuf realloc isalnum -@c LocalWords: ptypes itype YYPRINT trigraphs yytname expseq vindex dtype -@c LocalWords: Rhs YYRHSLOC LE nonassoc op deffn typeless yynerrs -@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 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 notype -@c LocalWords: hexflag STR exdent itemset asis DYYDEBUG YYFPRINTF args -@c LocalWords: infile ypp yxx outfile itemx tex leaderfill -@c LocalWords: hbox hss hfill tt ly yyin fopen fclose ofirst gcc ll -@c LocalWords: nbar yytext fst snd osplit ntwo strdup AST -@c LocalWords: YYSTACK DVI fdl printindex IELR +@c Local Variables: +@c fill-column: 76 +@c End: + +@c LocalWords: texinfo setfilename settitle setchapternewpage finalout texi FSF +@c LocalWords: ifinfo smallbook shorttitlepage titlepage GPL FIXME iftex FSF's +@c LocalWords: akim fn cp syncodeindex vr tp synindex dircategory direntry Naur +@c LocalWords: ifset vskip pt filll insertcopying sp ISBN Etienne Suvasa Multi +@c LocalWords: ifnottex yyparse detailmenu GLR RPN Calc var Decls Rpcalc multi +@c LocalWords: rpcalc Lexer Expr ltcalc mfcalc yylex defaultprec Donnelly Gotos +@c LocalWords: yyerror pxref LR yylval cindex dfn LALR samp gpl BNF xref yypush +@c LocalWords: const int paren ifnotinfo AC noindent emph expr stmt findex lr +@c LocalWords: glr YYSTYPE TYPENAME prog dprec printf decl init stmtMerge POSIX +@c LocalWords: pre STDC GNUC endif yy YY alloca lf stddef stdlib YYDEBUG yypull +@c LocalWords: NUM exp subsubsection kbd Ctrl ctype EOF getchar isdigit nonfree +@c LocalWords: ungetc stdin scanf sc calc ulator ls lm cc NEG prec yyerrok rr +@c LocalWords: longjmp fprintf stderr yylloc YYLTYPE cos ln Stallman Destructor +@c LocalWords: smallexample symrec val tptr FNCT fnctptr func struct sym enum +@c LocalWords: fnct putsym getsym fname arith fncts atan ptr malloc sizeof Lex +@c LocalWords: strlen strcpy fctn strcmp isalpha symbuf realloc isalnum DOTDOT +@c LocalWords: ptypes itype YYPRINT trigraphs yytname expseq vindex dtype Unary +@c LocalWords: Rhs YYRHSLOC LE nonassoc op deffn typeless yynerrs nonterminal +@c LocalWords: yychar yydebug msg YYNTOKENS YYNNTS YYNRULES YYNSTATES reentrant +@c LocalWords: cparse clex deftypefun NE defmac YYACCEPT YYABORT param yypstate +@c LocalWords: strncmp intval tindex lvalp locp llocp typealt YYBACKUP subrange +@c LocalWords: YYEMPTY YYEOF YYRECOVERING yyclearin GE def UMINUS maybeword loc +@c LocalWords: Johnstone Shamsa Sadaf Hussain Tomita TR uref YYMAXDEPTH inline +@c LocalWords: YYINITDEPTH stmnts ref stmnt initdcl maybeasm notype Lookahead +@c LocalWords: hexflag STR exdent itemset asis DYYDEBUG YYFPRINTF args Autoconf +@c LocalWords: infile ypp yxx outfile itemx tex leaderfill Troubleshouting sqrt +@c LocalWords: hbox hss hfill tt ly yyin fopen fclose ofirst gcc ll lookahead +@c LocalWords: nbar yytext fst snd osplit ntwo strdup AST Troublereporting th +@c LocalWords: YYSTACK DVI fdl printindex IELR nondeterministic nonterminals ps +@c LocalWords: subexpressions declarator nondeferred config libintl postfix LAC +@c LocalWords: preprocessor nonpositive unary nonnumeric typedef extern rhs +@c LocalWords: yytokentype filename destructor multicharacter nonnull EBCDIC +@c LocalWords: lvalue nonnegative XNUM CHR chr TAGLESS tagless stdout api TOK +@c LocalWords: destructors Reentrancy nonreentrant subgrammar nonassociative +@c LocalWords: deffnx namespace xml goto lalr ielr runtime lex yacc yyps env +@c LocalWords: yystate variadic Unshift NLS gettext po UTF Automake LOCALEDIR +@c LocalWords: YYENABLE bindtextdomain Makefile DEFS CPPFLAGS DBISON DeRemer +@c LocalWords: autoreconf Pennello multisets nondeterminism Generalised baz +@c LocalWords: redeclare automata Dparse localedir datadir XSLT midrule Wno +@c LocalWords: makefiles Graphviz multitable headitem hh basename Doxygen fno +@c LocalWords: doxygen ival sval deftypemethod deallocate pos deftypemethodx +@c LocalWords: Ctor defcv defcvx arg accessors arithmetics CPP ifndef CALCXX +@c LocalWords: lexer's calcxx bool LPAREN RPAREN deallocation cerrno climits +@c LocalWords: cstdlib Debian undef yywrap unput noyywrap nounput zA yyleng +@c LocalWords: errno strtol ERANGE str strerror iostream argc argv Javadoc +@c LocalWords: bytecode initializers superclass stype ASTNode autoboxing nls +@c LocalWords: toString deftypeivar deftypeivarx deftypeop YYParser strictfp +@c LocalWords: superclasses boolean getErrorVerbose setErrorVerbose deftypecv +@c LocalWords: getDebugStream setDebugStream getDebugLevel setDebugLevel url +@c LocalWords: bisonVersion deftypecvx bisonSkeleton getStartPos getEndPos +@c LocalWords: getLVal defvar deftypefn deftypefnx gotos msgfmt +@c LocalWords: subdirectory Solaris nonassociativity