Re: incorrect yychar for unambiguous GLR

[Joel E. Denny]

On Fri, 6 Jan 2006, Joel E. Denny wrote:

> On Tue, 19 Jul 2005, Joel E. Denny wrote:
> 
> > Should yychar be reliable in semantic actions when declaring %glr-parser?
> 
> I've installed this patch, which fixes the GLR lookahead bugs I've 
> encountered and adds some related test cases.  Although my original post 
> was mainly about deterministic operation, this patch also addresses 
> nondeterministic operation.
> 
> This is a complex patch.  More pairs of eyes would be helpful.

The following patch extends the existing documentation for look-aheads, 
and it adds a new section addressing the above GLR functionality.

I haven't committed this patch because I'd like others to review it first.  
Although there might be other issues, at least the following issues need 
to be addressed:

1. I've documented the use of YYEOF, yylval, and yylloc in semantic 
actions.  Was this intentionally omitted before?  Why?

2. I haven't fully grasped the structure of this documentation.  Am I 
putting information in the right places?

3. I tend to follow the usual LaTeX and HTML coding style: one line break 
after a sentence, two line breaks after a paragraph.  This makes editing 
much easier for me: it's easier to reorder sentences, and it's easier to 
fix line-wrapping after editing. I did this in the text I edited in this 
patch, but this isn't the current style.  Why?  Either way, the resulting 
".info" file looks fine.

Thanks.

Joel

2006-01-10  Joel E. Denny  <address@hidden>

        * doc/bison.texinfo: Fix some typos.
        (GLR Semantic Actions): New subsection discussing special
        considerations because GLR semantic actions might be deferred.
        (Actions): Mention look-ahead usage of yylval.
        (Actions and Locations): Mention look-ahead usage of yylloc.
        (Special Features for Use in Actions): Add YYEOF entry and mention it
        in the yychar entry.
        In the yychar entry, remove mention of the local yychar case (pure
        parser) since this is irrelevant information when writing semantic
        actions and since it's already discussed in `Bison Symbols' where
        yychar is otherwise described as an external variable.
        In the yychar entry, don't call it the `current' look-ahead since it
        isn't when semantic actions are deferred.
        In the yychar and yyclearin entries, add note about deferred semantic
        actions.
        Add yylloc and yylval entries discussing look-ahead usage.
        (Look-Ahead Tokens): When discussing yychar, don't call it the
        `current' look-ahead, and do mention yylval and yylloc.
        (Error Recovery): Cross-reference `Action Features' when mentioning
        yyclearin.
        (Bison Symbols): In the yychar entry, don't call it the `current'
        look-ahead.
        In the yylloc and yylval entries, mention look-ahead usage.

Index: doc/bison.texinfo
===================================================================
RCS file: /sources/bison/bison/doc/bison.texinfo,v
retrieving revision 1.171
diff -p -u -r1.171 bison.texinfo
--- doc/bison.texinfo   3 Jan 2006 22:35:45 -0000       1.171
+++ doc/bison.texinfo   10 Jan 2006 19:54:03 -0000
@@ -44,7 +44,7 @@ This manual is for @acronym{GNU} Bison (
 @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
 
@@ -733,9 +734,10 @@ user-defined function on the resulting v
 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
@@ -1094,6 +1096,52 @@ productions that participate in any part
 and the parser will report an error during any parse that results in
 the offending merge.
 
address@hidden GLR Semantic Actions
address@hidden GLR Semantic Actions
+
address@hidden 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.
+
address@hidden yychar
address@hidden @acronym{GLR} parsers and @code{yychar}
address@hidden yylval
address@hidden @acronym{GLR} parsers and @code{yylval}
address@hidden yylloc
address@hidden @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.
address@hidden, ,Look-Ahead Tokens}.
+
address@hidden yyclearin
address@hidden @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}.
+
address@hidden YYERROR
address@hidden @acronym{GLR} parsers and @code{YYERROR}
+Another bison feature requiring special consideration is @code{YYERROR}
+(@pxref{Action Features}), which you may invoke in any semantic action to
+initiate error recovery.
+During deterministic @acronym{GLR} operation, the effect of @code{YYERROR} is
+similar to its effect in an @acronym{LALR}(1) parser.
+In a deferred semantic action, its effect is currently not well tested.
address@hidden The effect is probably a syntax error at the split point.
+
 @node Compiler Requirements
 @subsection Considerations when Compiling @acronym{GLR} Parsers
 @cindex @code{inline}
@@ -3140,6 +3188,12 @@ As long as @code{bar} is used only in th
 always refers to the @code{expr} which precedes @code{bar} in the
 definition of @code{foo}.
 
address@hidden yylval
+Note that 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}.
address@hidden Features, ,Special Features for Use in Actions}.
+
 @node Action Types
 @subsection Data Types of Values in Actions
 @cindex action data types
@@ -3457,6 +3511,12 @@ exp:    @dots{}
 @end group
 @end example
 
address@hidden yylloc
+Note that 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}.
address@hidden Features, ,Special Features for Use in Actions}.
+
 @node Location Default Action
 @subsection Default Action for Locations
 @vindex YYLLOC_DEFAULT
@@ -4763,6 +4823,12 @@ In either case, the rest of the action i
 Value stored in @code{yychar} when there is no look-ahead token.
 @end deffn
 
address@hidden {Macro} YYEOF
address@hidden YYEOF
+Value stored in @code{yychar} when the look-ahead is the end of the input
+stream.
address@hidden deffn
+
 @deffn {Macro} YYERROR;
 @findex YYERROR
 Cause an immediate syntax error.  This statement initiates error
@@ -4779,15 +4845,22 @@ is recovering from a syntax error, and 0
 @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 the look-ahead token.
+When there is no look-ahead token, the value @code{YYEMPTY} is stored in the
+variable.
+When the look-ahead is the end of the input stream, the value @code{YYEOF} is
+stored in the variable.
+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}).
address@hidden Recovery}.
 @end deffn
 
 @deffn {Macro} yyerrok;
@@ -4796,6 +4869,22 @@ errors.  This is useful primarily in err
 @xref{Error Recovery}.
 @end deffn
 
address@hidden {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}).
address@hidden and Locations, ,Actions and Locations}.
address@hidden deffn
+
address@hidden {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}).
address@hidden, ,Actions}.
address@hidden deffn
+
 @deffn {Value} @@$
 @findex @@$
 Acts like a structure variable containing information on the textual location
@@ -5033,7 +5122,11 @@ doing so would produce on the stack the 
 '!'}.  No rule allows that sequence.
 
 @vindex yychar
-The current look-ahead token is stored in the variable @code{yychar}.
address@hidden yylval
address@hidden yylloc
+The look-ahead token is stored in the variable @code{yychar}.
+Its semantic value and location, if any, are stored in the variables
address@hidden and @code{yylloc}.
 @xref{Action Features, ,Special Features for Use in Actions}.
 
 @node Shift/Reduce
@@ -5850,6 +5943,7 @@ The previous look-ahead token is reanaly
 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.
address@hidden 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
@@ -8039,7 +8133,7 @@ token.  @xref{Action Features, ,Special 
 @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}.
@@ -8100,7 +8194,7 @@ the next token.  @xref{Lexical, ,The Lex
 
 @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
@@ -8109,9 +8203,12 @@ macro is deprecated, and is supported on
 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
address@hidden)  You can ignore this variable if you don't use the
address@hidden@@} feature in the grammar actions.  @xref{Token Locations,
-,Textual Locations of Tokens}.
address@hidden)
+You can ignore this variable if you don't use the @samp{@@} feature in the
+grammar actions.
address@hidden Locations, ,Textual Locations of Tokens}.
+In semantic actions, it stores the location of the look-ahead token.
address@hidden and Locations, ,Actions and Locations}.
 @end deffn
 
 @deffn {Type} YYLTYPE
@@ -8123,7 +8220,10 @@ members.  @xref{Location Type, , Data Ty
 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
address@hidden)  @xref{Token Values, ,Semantic Values of Tokens}.
address@hidden)
address@hidden Values, ,Semantic Values of Tokens}.
+In semantic actions, it stores the semantic value of the look-ahead token.
address@hidden, ,Actions}.
 @end deffn
 
 @deffn {Macro} YYMAXDEPTH
@@ -8384,7 +8484,7 @@ grammatically indivisible.  The piece of
 @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
address@hidden LocalWords: YYEMPTY YYRECOVERING yyclearin GE def UMINUS 
maybeword
address@hidden 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