From 8710fc41aaebc5d167a2783a4b8b60849a803869 Mon Sep 17 00:00:00 2001 From: "Joel E. Denny" Date: Mon, 6 Mar 2006 07:39:11 +0000 Subject: [PATCH] * tests/glr-regression.at (Uninitialized location when reporting ambiguity): New test case. * data/glr.c (yyresolveLocations): New function, which uses YYLLOC_DEFAULT. (yyresolveValue): Invoke yyresolveLocations before reporting an ambiguity. * doc/bison.texinfo (Default Action for Locations): Note YYLLOC_DEFAULT's usage for ambiguity locations. (GLR Semantic Actions): Cross-reference those notes. --- ChangeLog | 12 +++++++ data/glr.c | 52 +++++++++++++++++++++++++++ doc/bison.texinfo | 17 ++++++--- tests/glr-regression.at | 79 +++++++++++++++++++++++++++++++++++++++++ 4 files changed, 156 insertions(+), 4 deletions(-) diff --git a/ChangeLog b/ChangeLog index 1dce2553..ecd42da6 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,15 @@ +2006-03-06 Joel E. Denny + + * tests/glr-regression.at (Uninitialized location when reporting + ambiguity): New test case. + * data/glr.c (yyresolveLocations): New function, which uses + YYLLOC_DEFAULT. + (yyresolveValue): Invoke yyresolveLocations before reporting an + ambiguity. + * doc/bison.texinfo (Default Action for Locations): Note + YYLLOC_DEFAULT's usage for ambiguity locations. + (GLR Semantic Actions): Cross-reference those notes. + 2006-03-04 Joel E. Denny * tests/glr-regression.at (Leaked semantic values when reporting diff --git a/data/glr.c b/data/glr.c index 13fd2ff2..a810bcdc 100644 --- a/data/glr.c +++ b/data/glr.c @@ -1803,6 +1803,57 @@ yyreportAmbiguity (yySemanticOption* yyx0, return yyabort; } +/** Starting at and including state S, resolve the location for each of the + * previous N states that is unresolved. The first semantic option of a state + * is always chosen. */ +static void +yyresolveLocations (yyGLRState* yys, int yyn, + yyGLRStack *yystackp]b4_user_formals[) +{ + if (0 < yyn) + { + yyresolveLocations (yys->yypred, yyn-1, yystackp]b4_user_args[); + if (!yys->yyresolved) + { + yySemanticOption *yyoption; + yyGLRStackItem yyrhs[1 + YYMAXRHS]; + int yynrhs; + int yychar_current; + YYSTYPE yylval_current; + YYLTYPE yylloc_current; + yyoption = yys->yysemantics.yyfirstVal; + YYASSERT (yyoption != NULL); + yynrhs = yyrhsLength (yyoption->yyrule); + if (yynrhs > 0) + { + yyGLRState *yys; + int yyi; + yyresolveLocations (yyoption->yystate, yynrhs, + yystackp]b4_user_args[); + for (yys = yyoption->yystate, yyi = yynrhs; + yyi >= 1; + yys = yys->yypred, yyi -= 1) + yyrhs[yyi].yystate.yyloc = yys->yyloc; + } + else + { + yyGLRState *yyprevious = yyoption->yystate; + YYASSERT (yyprevious->yyresolved); + yyrhs[0].yystate.yyloc = yyprevious->yyloc; + } + yychar_current = yychar; + yylval_current = yylval; + yylloc_current = yylloc; + yychar = yyoption->yyrawchar; + yylval = yyoption->yyval; + yylloc = yyoption->yyloc; + YYLLOC_DEFAULT ((yys->yyloc), yyrhs, yynrhs); + yychar = yychar_current; + yylval = yylval_current; + yylloc = yylloc_current; + } + } +} /** Resolve the ambiguity represented in state S, perform the indicated * actions, and set the semantic value of S. If result != yyok, the chain of @@ -1837,6 +1888,7 @@ yyresolveValue (yyGLRState* yys, yyGLRStack* yystackp]b4_user_formals[) switch (yypreference (yybest, yyp)) { case 0: + yyresolveLocations (yys, 1, yystackp]b4_user_args[); return yyreportAmbiguity (yybest, yyp]b4_pure_args[); break; case 1: diff --git a/doc/bison.texinfo b/doc/bison.texinfo index eb36845f..27d2bd4a 100644 --- a/doc/bison.texinfo +++ b/doc/bison.texinfo @@ -1135,13 +1135,16 @@ 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 +(@pxref{Action Features}), which you can invoke in a 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. +Also, see @ref{Location Default Action, ,Default Action for Locations}, which +describes a special usage of @code{YYLLOC_DEFAULT} in @acronym{GLR} parsers. + @node Compiler Requirements @subsection Considerations when Compiling @acronym{GLR} Parsers @cindex @code{inline} @@ -3571,6 +3574,7 @@ This location is stored in @code{yylloc}. @node Location Default Action @subsection Default Action for Locations @vindex YYLLOC_DEFAULT +@cindex @acronym{GLR} parsers and @code{YYLLOC_DEFAULT} Actually, actions are not the best place to compute locations. Since locations are much more general than semantic values, there is room in @@ -3578,6 +3582,9 @@ the output parser to redefine the default action to take for each rule. The @code{YYLLOC_DEFAULT} macro is invoked each time a rule is matched, before the associated action is run. It is also invoked while processing a syntax error, to compute the error's location. +Before reporting an unresolvable syntactic ambiguity, a @acronym{GLR} +parser invokes @code{YYLLOC_DEFAULT} recursively to compute the location +of that ambiguity. Most of the time, this macro is general enough to suppress location dedicated code from semantic actions. @@ -3586,9 +3593,11 @@ The @code{YYLLOC_DEFAULT} macro takes three parameters. The first one is the location of the grouping (the result of the computation). When a rule is matched, the second parameter identifies locations of all right hand side elements of the rule being matched, and the third -parameter is the size of the rule's right hand side. When processing -a syntax error, the second parameter identifies locations of -the symbols that were discarded during error processing, and the third +parameter is the size of the rule's right hand side. +When a @acronym{GLR} parser reports an ambiguity, which of multiple candidate +right hand sides it passes to @code{YYLLOC_DEFAULT} is undefined. +When processing a syntax error, the second parameter identifies locations +of the symbols that were discarded during error processing, and the third parameter is the number of discarded symbols. By default, @code{YYLLOC_DEFAULT} is defined this way: diff --git a/tests/glr-regression.at b/tests/glr-regression.at index c9b745bc..a36de9e2 100644 --- a/tests/glr-regression.at +++ b/tests/glr-regression.at @@ -1576,3 +1576,82 @@ AT_CHECK([[./glr-regr16]], 0, [], ]) AT_CLEANUP + + +## ------------------------------------------------------------------------- ## +## Uninitialized location when reporting ambiguity. ## +## ------------------------------------------------------------------------- ## + +AT_SETUP([Uninitialized location when reporting ambiguity]) +AT_DATA_GRAMMAR([glr-regr17.y], +[[ +%glr-parser +%locations +%pure-parser +%error-verbose + +%union { int dummy; } + +%{ + static void yyerror (YYLTYPE *, char const *); + static int yylex (YYSTYPE *, YYLTYPE *); +%} + +%initial-action { + @$.first_line = 1; + @$.first_column = 1; + @$.last_line = 1; + @$.last_column = 1; +} + +%% + +/* Tests multiple levels of yyresolveLocations recursion. */ +start: ambig1 | ambig2 ; +ambig1: sub_ambig1 | sub_ambig2 ; +ambig2: sub_ambig1 | sub_ambig2 ; + +/* Tests non-empty RHS as well as empty RHS with either initial location or + location of previous token. Both empty RHS locations are printed in the + error message. */ +sub_ambig1: empty 'a' 'b' empty ; +sub_ambig2: empty 'a' 'b' empty ; +empty: ; + +%% + +static void +yyerror (YYLTYPE *locp, char const *msg) +{ + fprintf (stderr, "Error at %d.%d-%d.%d: %s.\n", locp->first_line, + locp->first_column, locp->last_line, locp->last_column, msg); +} + +/*ARGSUSED*/ static int +yylex (YYSTYPE *lvalp, YYLTYPE *llocp) +{ + static const char input[] = "ab"; + static const char *inputp = input; + llocp->first_line = llocp->last_line = 2; + llocp->first_column = inputp - input + 1; + llocp->last_column = llocp->first_column + 1; + return *inputp++; +} + +int +main (void) +{ + return yyparse () != 1; +} +]]) + +AT_CHECK([[bison -o glr-regr17.c glr-regr17.y]], 0, [], +[glr-regr17.y: conflicts: 3 reduce/reduce +]) +AT_COMPILE([glr-regr17]) + +AT_CHECK([[./glr-regr17]], 0, [], +[Error at 1.1-2.3: syntax is ambiguous. +]) + +AT_CLEANUP -- 2.47.2