[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: incorrect yychar for unambiguous GLR
From: |
Joel E. Denny |
Subject: |
Re: incorrect yychar for unambiguous GLR |
Date: |
Mon, 30 Jan 2006 06:16:38 -0500 (EST) |
On Wed, 11 Jan 2006, Paul Eggert wrote:
> "Joel E. Denny" <address@hidden> writes:
>
> > Why must the lookahead token be maintained in two variables? Why not just
> > maintain yychar and invoke YYTRANSLATE whenever yytoken is needed?
>
> In the case of yacc.c, it's most likely efficiency: the desire to
> avoid reinvoking YYTRANSLATE. The tradeoffs are no doubt different
> for GLR. (And I doubt whether anybody's measured the efficiency in
> the yacc case either, at least not recently....)
I installed the following. I haven't done any timings, but I think these
changes have no measureable impact on performance.
Joel
2006-01-30 Joel E. Denny <address@hidden>
During deterministic GLR operation, user actions should be able to
influence the parse by changing yychar. To make this easier to fix and
to make glr.c easier to evolve in general, don't maintain yytoken in
parallel with yychar; just compute yytoken when needed.
* tests/glr-regression.at (Incorrect lookahead during deterministic
GLR): Check that setting yychar in a user action has the intended
effect.
* data/glr.c (yyGLRStack): Remove yytokenp member.
(yyclearin): Don't set *yytokenp.
(yyprocessOneStack, yyreportSyntaxError, yyrecoverSyntaxError): Examine
yychar rather than *yytokenp to determine the current lookahead.
Compute yytoken locally when needed.
(yyparse): Likewise. Remove the local yytoken that yytokenp used to
point to.
* doc/bison.texinfo (Bison Options): Remove stray sentence fragment
after `--report' documentation.
Index: data/glr.c
===================================================================
RCS file: /sources/bison/bison/data/glr.c,v
retrieving revision 1.162
diff -p -u -r1.162 glr.c
--- data/glr.c 23 Jan 2006 08:39:52 -0000 1.162
+++ data/glr.c 30 Jan 2006 10:40:07 -0000
@@ -803,7 +803,6 @@ struct yyGLRStack {
YYSTYPE yyval;
YYLTYPE yyloc;
])[
- yySymbol* yytokenp;
YYJMP_BUF yyexception_buffer;
yyGLRStackItem* yyitems;
yyGLRStackItem* yynextFree;
@@ -910,7 +909,7 @@ yyuserAction (yyRuleNum yyn, int yyrhsle
# undef YYRECOVERING
# define YYRECOVERING (yystackp->yyerrState != 0)
# undef yyclearin
-# define yyclearin (yychar = *(yystackp->yytokenp) = YYEMPTY)
+# define yyclearin (yychar = YYEMPTY)
# undef YYFILL
# define YYFILL(N) yyfill (yyvsp, &yylow, N, yynormal)
# undef YYBACKUP
@@ -1929,7 +1928,6 @@ yyprocessOneStack (yyGLRStack* yystackp,
int yyaction;
const short int* yyconflicts;
yyRuleNum yyrule;
- yySymbol* const yytokenp = yystackp->yytokenp;
while (yystackp->yytops.yystates[yyk] != NULL)
{
@@ -1953,15 +1951,18 @@ yyprocessOneStack (yyGLRStack* yystackp,
}
else
{
+ yySymbol yytoken;
yystackp->yytops.yylookaheadNeeds[yyk] = yytrue;
- if (*yytokenp == YYEMPTY)
+ if (yychar == YYEMPTY)
{
YYDPRINTF ((stderr, "Reading a token: "));
yychar = YYLEX;
- *yytokenp = YYTRANSLATE (yychar);
- YY_SYMBOL_PRINT ("Next token is", *yytokenp, &yylval, &yylloc);
+ yytoken = YYTRANSLATE (yychar);
+ YY_SYMBOL_PRINT ("Next token is", yytoken, &yylval, &yylloc);
}
- yygetLRActions (yystate, *yytokenp, &yyaction, &yyconflicts);
+ else
+ yytoken = YYTRANSLATE (yychar);
+ yygetLRActions (yystate, yytoken, &yyaction, &yyconflicts);
while (*yyconflicts != 0)
{
@@ -1999,12 +2000,12 @@ yyreportSyntaxError (yyGLRStack* yystack
if (yystackp->yyerrState == 0)
{
#if YYERROR_VERBOSE
- yySymbol* const yytokenp = yystackp->yytokenp;
int yyn;
yyn = yypact[yystackp->yytops.yystates[0]->yylrState];
if (YYPACT_NINF < yyn && yyn < YYLAST)
{
- size_t yysize0 = yytnamerr (NULL, yytokenName (*yytokenp));
+ yySymbol yytoken = YYTRANSLATE (yychar);
+ size_t yysize0 = yytnamerr (NULL, yytokenName (yytoken));
size_t yysize = yysize0;
size_t yysize1;
yybool yysize_overflow = yyfalse;
@@ -2032,7 +2033,7 @@ yyreportSyntaxError (yyGLRStack* yystack
int yyxend = yychecklim < YYNTOKENS ? yychecklim : YYNTOKENS;
int yycount = 1;
- yyarg[0] = yytokenName (*yytokenp);
+ yyarg[0] = yytokenName (yytoken);
yyfmt = yystpcpy (yyformat, yyunexpected);
for (yyx = yyxbegin; yyx < yyxend; ++yyx)
@@ -2100,7 +2101,6 @@ yyreportSyntaxError (yyGLRStack* yystack
/*ARGSUSED*/ static void
yyrecoverSyntaxError (yyGLRStack* yystackp]b4_user_formals[)
{
- yySymbol* const yytokenp = yystackp->yytokenp;
size_t yyk;
int yyj;
@@ -2109,9 +2109,10 @@ yyrecoverSyntaxError (yyGLRStack* yystac
reductions. Skip tokens until we can proceed. */
while (YYID (yytrue))
{
- if (*yytokenp == YYEOF)
+ yySymbol yytoken;
+ if (yychar == YYEOF)
yyFail (yystackp][]b4_lpure_args[, NULL);
- if (*yytokenp != YYEMPTY)
+ if (yychar != YYEMPTY)
{]b4_location_if([[
/* We throw away the lookahead, but the error range
of the shifted error token must take it into account. */
@@ -2120,18 +2121,19 @@ yyrecoverSyntaxError (yyGLRStack* yystac
yyerror_range[1].yystate.yyloc = yys->yyloc;
yyerror_range[2].yystate.yyloc = yylloc;
YYLLOC_DEFAULT ((yys->yyloc), yyerror_range, 2);]])[
+ yytoken = YYTRANSLATE (yychar);
yydestruct ("Error: discarding",
- *yytokenp, &yylval]b4_location_if([,
&yylloc])[]b4_user_args[);
+ yytoken, &yylval]b4_location_if([,
&yylloc])[]b4_user_args[);
}
YYDPRINTF ((stderr, "Reading a token: "));
yychar = YYLEX;
- *yytokenp = YYTRANSLATE (yychar);
- YY_SYMBOL_PRINT ("Next token is", *yytokenp, &yylval, &yylloc);
+ yytoken = YYTRANSLATE (yychar);
+ YY_SYMBOL_PRINT ("Next token is", yytoken, &yylval, &yylloc);
yyj = yypact[yystackp->yytops.yystates[0]->yylrState];
if (yyis_pact_ninf (yyj))
return;
- yyj += *yytokenp;
- if (yyj < 0 || YYLAST < yyj || yycheck[yyj] != *yytokenp)
+ yyj += yytoken;
+ if (yyj < 0 || YYLAST < yyj || yycheck[yyj] != yytoken)
{
if (yydefact[yystackp->yytops.yystates[0]->yylrState] != 0)
return;
@@ -2209,7 +2211,6 @@ yyrecoverSyntaxError (yyGLRStack* yystac
]b4_c_ansi_function_def([yyparse], [int], b4_parse_param)[
{
int yyresult;
- yySymbol yytoken;
yyGLRStack yystack;
yyGLRStack* const yystackp = &yystack;
size_t yyposn;
@@ -2217,7 +2218,6 @@ yyrecoverSyntaxError (yyGLRStack* yystac
YYDPRINTF ((stderr, "Starting parse\n"));
yychar = YYEMPTY;
- yytoken = YYEMPTY;
yylval = yyval_default;
]b4_location_if([
#if YYLTYPE_IS_TRIVIAL
@@ -2244,7 +2244,6 @@ b4_syncline(address@hidden@], address@hidden@])])dnl
case 2: goto yyexhaustedlab;
default: goto yybuglab;
}
- yystack.yytokenp = &yytoken;
yyglrShift (&yystack, 0, 0, 0, &yylval, &yylloc);
yyposn = 0;
@@ -2277,24 +2276,24 @@ b4_syncline(address@hidden@], address@hidden@])])dnl
}
else
{
- if (yytoken == YYEMPTY)
+ yySymbol yytoken;
+ if (yychar == YYEMPTY)
{
YYDPRINTF ((stderr, "Reading a token: "));
yychar = YYLEX;
yytoken = YYTRANSLATE (yychar);
YY_SYMBOL_PRINT ("Next token is", yytoken, &yylval, &yylloc);
}
+ else
+ yytoken = YYTRANSLATE (yychar);
yygetLRActions (yystate, yytoken, &yyaction, &yyconflicts);
if (*yyconflicts != 0)
break;
if (yyisShiftAction (yyaction))
{
YY_SYMBOL_PRINT ("Shifting", yytoken, &yylval, &yylloc);
- if (yytoken != YYEOF)
- {
- yychar = YYEMPTY;
- yytoken = YYEMPTY;
- }
+ if (yychar != YYEOF)
+ yychar = YYEMPTY;
yyposn += 1;
yyglrShift (&yystack, 0, yyaction, yyposn, &yylval, &yylloc);
if (0 < yystack.yyerrState)
@@ -2346,12 +2345,11 @@ b4_syncline(address@hidden@], address@hidden@])])dnl
/* If any yyglrShift call fails, it will fail after shifting. Thus,
a copy of yylval will already be on stack 0 in the event of a
- failure in the following loop. Thus, yytoken is set to YYEMPTY
+ failure in the following loop. Thus, yychar is set to YYEMPTY
before the loop to make sure the user destructor for yylval isn't
called twice. */
- yytoken_to_shift = yytoken;
+ yytoken_to_shift = YYTRANSLATE (yychar);
yychar = YYEMPTY;
- yytoken = YYEMPTY;
yyposn += 1;
for (yys = 0; yys < yyn; yys += 1)
{
@@ -2412,9 +2410,10 @@ b4_syncline(address@hidden@], address@hidden@])])dnl
goto yyreturn;
yyreturn:
- if (yytoken != YYEOF && yytoken != YYEMPTY)
+ if (yychar != YYEOF && yychar != YYEMPTY)
yydestruct ("Cleanup: discarding lookahead",
- yytoken, &yylval]b4_location_if([, &yylloc])[]b4_user_args[);
+ YYTRANSLATE (yychar),
+ &yylval]b4_location_if([, &yylloc])[]b4_user_args[);
/* If the stack is well-formed, pop the stack until it is empty,
destroying its entries as we go. But free the stack regardless
Index: doc/bison.texinfo
===================================================================
RCS file: /sources/bison/bison/doc/bison.texinfo,v
retrieving revision 1.174
diff -p -u -r1.174 bison.texinfo
--- doc/bison.texinfo 20 Jan 2006 22:23:44 -0000 1.174
+++ doc/bison.texinfo 30 Jan 2006 10:40:07 -0000
@@ -6889,8 +6889,6 @@ Implies @code{state} and augments the de
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
Index: tests/glr-regression.at
===================================================================
RCS file: /sources/bison/bison/tests/glr-regression.at,v
retrieving revision 1.28
diff -p -u -r1.28 glr-regression.at
--- tests/glr-regression.at 20 Jan 2006 00:08:30 -0000 1.28
+++ tests/glr-regression.at 30 Jan 2006 10:40:07 -0000
@@ -1016,7 +1016,8 @@ AT_CLEANUP
## ------------------------------------------------------------------------- ##
## Incorrect lookahead during deterministic GLR. See ##
-## <http://lists.gnu.org/archive/html/help-bison/2005-07/msg00017.html>. ##
+## <http://lists.gnu.org/archive/html/help-bison/2005-07/msg00017.html> and ##
+## <http://lists.gnu.org/archive/html/bison-patches/2006-01/msg00060.html>. ##
## ------------------------------------------------------------------------- ##
AT_SETUP([Incorrect lookahead during deterministic GLR])
@@ -1027,7 +1028,8 @@ AT_DATA_GRAMMAR([glr-regr13.y],
- Defaulted state with initial yychar: yychar == YYEMPTY.
- Nondefaulted state: yychar != YYEMPTY.
- Defaulted state after lookahead: yychar != YYEMPTY.
- - Defaulted state after shift: yychar == YYEMPTY. */
+ - Defaulted state after shift: yychar == YYEMPTY.
+ - User action changing the lookahead. */
%{
#include <stdio.h>
@@ -1045,7 +1047,7 @@ AT_DATA_GRAMMAR([glr-regr13.y],
%%
start:
- defstate_init defstate_shift 'b' {
+ defstate_init defstate_shift 'b' change_lookahead 'a' {
USE ($3);
print_look_ahead ("start <- defstate_init defstate_shift 'b'");
}
@@ -1075,6 +1077,11 @@ nondefstate:
print_look_ahead ("nondefstate <- 'b'");
}
;
+change_lookahead:
+ {
+ yychar = 'a';
+ }
+ ;
%%
- Re: incorrect yychar for unambiguous GLR, Joel E. Denny, 2006/01/06
- Re: incorrect yychar for unambiguous GLR, Joel E. Denny, 2006/01/10
- Re: incorrect yychar for unambiguous GLR, Paul Hilfinger, 2006/01/10
- Re: incorrect yychar for unambiguous GLR, Joel E. Denny, 2006/01/11
- Re: incorrect yychar for unambiguous GLR, Paul Hilfinger, 2006/01/11
- Re: incorrect yychar for unambiguous GLR, Joel E. Denny, 2006/01/11
- Re: incorrect yychar for unambiguous GLR, Joel E. Denny, 2006/01/11
- Re: incorrect yychar for unambiguous GLR, Paul Eggert, 2006/01/12
- Re: incorrect yychar for unambiguous GLR,
Joel E. Denny <=
Re: incorrect yychar for unambiguous GLR, Paul Eggert, 2006/01/11
Re: incorrect yychar for unambiguous GLR, Paul Hilfinger, 2006/01/10
- Re: incorrect yychar for unambiguous GLR, Joel E. Denny, 2006/01/10
- Re: incorrect yychar for unambiguous GLR, Paul Eggert, 2006/01/11
- Re: incorrect yychar for unambiguous GLR, Joel E. Denny, 2006/01/11
- Re: incorrect yychar for unambiguous GLR, Joel E. Denny, 2006/01/30
- Re: incorrect yychar for unambiguous GLR, Paul Eggert, 2006/01/30
- Re: incorrect yychar for unambiguous GLR, Joel E. Denny, 2006/01/30
Re: incorrect yychar for unambiguous GLR, Paul Hilfinger, 2006/01/11