From 5e6f62f2f10547c6552d3eb4003c44d66f172686 Mon Sep 17 00:00:00 2001 From: Paul Hilfinger Date: Sat, 21 May 2005 08:35:51 +0000 Subject: [PATCH] * data/glr.c (YY_SYMBOL_PRINT): Don't print newline at end to fix a small glitch in debugging output. (yyprocessOneStack, yyrecoverSyntaxError, yyparse): Print newline after YY_SYMBOL_PRINT where needed. (struct yyGLRState): Add some comments. (struct yySemanticOption): Add some comments. (union yyGLRStackItem): Add comment. (yymergeOptionSets): Correct this to properly perform the union, avoiding infinite reported by Michael Rosien. Update comment. * tests/glr-regression.at: Add test for GLR merging error reported by M. Rosien. --- ChangeLog | 18 +++++++ data/glr.c | 79 +++++++++++++++++++++++++------ tests/glr-regression.at | 102 ++++++++++++++++++++++++++++++++++++++++ 3 files changed, 185 insertions(+), 14 deletions(-) diff --git a/ChangeLog b/ChangeLog index 68d1c9e1..d82bb04f 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,21 @@ +2005-05-20 Paul Hilfinger + + * data/glr.c (YY_SYMBOL_PRINT): Don't print newline at end to + fix a small glitch in debugging output. + (yyprocessOneStack, yyrecoverSyntaxError, yyparse): Print newline + after YY_SYMBOL_PRINT where needed. + + (struct yyGLRState): Add some comments. + (struct yySemanticOption): Add some comments. + (union yyGLRStackItem): Add comment. + + (yymergeOptionSets): Correct this to properly perform the union, + avoiding infinite reported by Michael Rosien. + Update comment. + + * tests/glr-regression.at: Add test for GLR merging error reported + by M. Rosien. + 2005-05-13 Paul Eggert * COPYING, ChangeLog, GNUmakefile, HACKING, Makefile.am, diff --git a/data/glr.c b/data/glr.c index cce04afd..3d1b0ef5 100644 --- a/data/glr.c +++ b/data/glr.c @@ -509,7 +509,6 @@ do { \ YYFPRINTF (stderr, "%s ", Title); \ yysymprint (stderr, \ Type, Value]b4_location_if([, Location])[); \ - YYFPRINTF (stderr, "\n"); \ } \ } while (0) @@ -575,15 +574,26 @@ typedef struct yyGLRStack yyGLRStack; typedef struct yyGLRStateSet yyGLRStateSet; struct yyGLRState { + /** Type tag: always true. */ yybool yyisState; + /** Type tag for yysemantics. If true, yysval applies, otherwise + * yyfirstVal applies. */ yybool yyresolved; + /** Number of corresponding LALR(1) machine state. */ yyStateNum yylrState; + /** Preceding state in this stack */ yyGLRState* yypred; + /** Source position of the first token produced by my symbol */ size_t yyposn; union { + /** First in a chain of alternative reductions producing the + * non-terminal corresponding to this state, threaded through + * yynext. */ yySemanticOption* yyfirstVal; + /** Semantic value for this state. */ YYSTYPE yysval; } yysemantics; + /** Source location for this state. */ YYLTYPE yyloc; }; @@ -593,12 +603,19 @@ struct yyGLRStateSet { }; struct yySemanticOption { + /** Type tag: always false. */ yybool yyisState; + /** Rule number for this reduction */ yyRuleNum yyrule; + /** The last RHS state in the list of states to be reduced. */ yyGLRState* yystate; + /** Next sibling in chain of options. To facilitate merging, + * options are chained in decreasing order by address. */ yySemanticOption* yynext; }; +/** Type of the items in the GLR stack. The yyisState field + * indicates which item of the union is valid. */ union yyGLRStackItem { yyGLRState yystate; yySemanticOption yyoption; @@ -1282,9 +1299,8 @@ yyidenticalOptions (yySemanticOption* yyy0, yySemanticOption* yyy1) return yyfalse; } -/** Assuming identicalOptions (Y0,Y1), (destructively) merge the - * alternative semantic values for the RHS-symbols of Y1 into the - * corresponding semantic value sets of the symbols of Y0. */ +/** Assuming identicalOptions (Y0,Y1), destructively merge the + * alternative semantic values for the RHS-symbols of Y1 and Y0. */ static void yymergeOptionSets (yySemanticOption* yyy0, yySemanticOption* yyy1) { @@ -1294,16 +1310,46 @@ yymergeOptionSets (yySemanticOption* yyy0, yySemanticOption* yyy1) yyn = yyrhsLength (yyy0->yyrule); yyn > 0; yys0 = yys0->yypred, yys1 = yys1->yypred, yyn -= 1) - if (yys0 == yys1) - break; - else if (! yys0->yyresolved && ! yys1->yyresolved) - { - yySemanticOption* yyz; - for (yyz = yys0->yysemantics.yyfirstVal; yyz->yynext != NULL; - yyz = yyz->yynext) - continue; - yyz->yynext = yys1->yysemantics.yyfirstVal; - } + { + if (yys0 == yys1) + break; + else if (yys0->yyresolved) + { + yys1->yyresolved = yytrue; + yys1->yysemantics.yysval = yys0->yysemantics.yysval; + } + else if (yys1->yyresolved) + { + yys0->yyresolved = yytrue; + yys0->yysemantics.yysval = yys1->yysemantics.yysval; + } + else + { + yySemanticOption** yyz0p; + yySemanticOption* yyz1; + yyz0p = &yys0->yysemantics.yyfirstVal; + yyz1 = yys1->yysemantics.yyfirstVal; + while (yytrue) + { + if (yyz1 == *yyz0p || yyz1 == NULL) + break; + else if (*yyz0p == NULL) + { + *yyz0p = yyz1; + break; + } + else if (*yyz0p < yyz1) + { + yySemanticOption* yyz = *yyz0p; + *yyz0p = yyz1; + yyz1 = yyz1->yynext; + (*yyz0p)->yynext = yyz; + } + yyz0p = &(*yyz0p)->yynext; + } + yys1->yysemantics.yyfirstVal = yys0->yysemantics.yyfirstVal; + } + } } /** Y0 and Y1 represent two possible actions to take in a given @@ -1579,6 +1625,7 @@ yyprocessOneStack (yyGLRStack* yystack, int yyk, yychar = YYLEX; *yytokenp = YYTRANSLATE (yychar); YY_SYMBOL_PRINT ("Next token is", *yytokenp, yylvalp, yyllocp); + YYDPRINTF ((stderr, "\n")); } yygetLRActions (yystate, *yytokenp, &yyaction, &yyconflicts); @@ -1744,6 +1791,7 @@ yyrecoverSyntaxError (yyGLRStack* yystack, yychar = YYLEX; *yytokenp = YYTRANSLATE (yychar); YY_SYMBOL_PRINT ("Next token is", *yytokenp, yylvalp, yyllocp); + YYDPRINTF ((stderr, "\n")); yyj = yypact[yystack->yytops.yystates[0]->yylrState]; if (yyis_pact_ninf (yyj)) return; @@ -1786,6 +1834,7 @@ yyrecoverSyntaxError (yyGLRStack* yystack, YYLLOC_DEFAULT (yyerrloc, yystack->yyerror_range, 2);]])[ YY_SYMBOL_PRINT ("Shifting", yystos[yytable[yyj]], yylvalp, &yyerrloc); + YYDPRINTF ((stderr, "\n")); yyglrShift (yystack, 0, yytable[yyj], yys->yyposn, *yylvalp, &yyerrloc]b4_user_args[); yys = yystack->yytops.yystates[0]; @@ -1905,6 +1954,7 @@ b4_syncline([@oline@], [@ofile@])])dnl yychar = YYLEX; yytoken = YYTRANSLATE (yychar); YY_SYMBOL_PRINT ("Next token is", yytoken, yylvalp, yyllocp); + YYDPRINTF ((stderr, "\n")); } yygetLRActions (yystate, yytoken, &yyaction, &yyconflicts); if (*yyconflicts != 0) @@ -1912,6 +1962,7 @@ b4_syncline([@oline@], [@ofile@])])dnl if (yyisShiftAction (yyaction)) { YY_SYMBOL_PRINT ("Shifting", yytoken, yylvalp, yyllocp); + YYDPRINTF ((stderr, "\n")); if (yytoken != YYEOF) yytoken = YYEMPTY; yyposn += 1; diff --git a/tests/glr-regression.at b/tests/glr-regression.at index 3abd07b7..fd822a18 100644 --- a/tests/glr-regression.at +++ b/tests/glr-regression.at @@ -221,4 +221,106 @@ AT_CHECK([[echo s VARIABLE_3 t v x | ./glr-regr2a]], 0, ]], []) +AT_CLEANUP + +## ------------------------------------------------------------ ## +## Improper merging of GLR delayed action sets ## +## ------------------------------------------------------------ ## + +AT_SETUP([Improper merging of GLR delayed action sets]) + +AT_DATA_GRAMMAR([glr-regr3.y], +[[/* Regression Test: Improper merging of GLR delayed action sets. */ +/* Reported by M. Rosien */ + +%{ +#include +#include + +static int MergeRule (int x0, int x1); +static void yyerror(char const * s); + +#define RULE(x) (1 << (x)) + +%} + +%glr-parser + +%token BAD_CHAR +%token P1 P2 T1 T2 T3 T4 O1 O2 + +%% + +S : P1 T4 O2 NT6 P2 { printf ("Result: %x\n", $4); } +; + +NT1 : P1 T1 O1 T2 P2 { $$ = RULE(2); } %merge +; + +NT2 : NT1 { $$ = RULE(3); } %merge + | P1 NT1 O1 T3 P2 { $$ = RULE(4); } %merge +; + +NT3 : T3 { $$ = RULE(5); } %merge + | P1 NT1 O1 T3 P2 { $$ = RULE(6); } %merge +; + +NT4 : NT3 { $$ = RULE(7); } %merge + | NT2 { $$ = RULE(8); } %merge + | P1 NT2 O1 NT3 P2 { $$ = RULE(9); } %merge +; + +NT5 : NT4 { $$ = RULE(10); } %merge +; + +NT6 : P1 NT1 O1 T3 P2 { $$ = RULE(11) | $2; } %merge + | NT5 { $$ = RULE(12) | $1; } %merge +; + +%% + +static int MergeRule (int x0, int x1) { + return x0 | x1; +} + +static void yyerror(char const * s) { + fprintf(stderr,"error: %s\n",s); +} + +FILE *yyin = NULL; + +int P[] = { P1, P2 }; +int O[] = { O1, O2 }; +int T[] = { T1, T2, T3, T4 }; + +int yylex (void) +{ + char inp[3]; + if (fscanf (yyin, "%2s", inp) == EOF) + return 0; + switch (inp[0]) + { + case 'p': return P[inp[1] - '1']; + case 't': return T[inp[1] - '1']; + case 'o': return O[inp[1] - '1']; + } + return BAD_CHAR; +} + +int main(int argc, char* argv[]) { + yyin = stdin; + if (argc == 2 && !(yyin = fopen (argv[1], "r"))) return 1; + return yyparse (); +} +]]) + +AT_CHECK([[bison -o glr-regr3.c glr-regr3.y]], 0, [], +[glr-regr3.y: conflicts: 1 shift/reduce, 1 reduce/reduce +]) +AT_COMPILE([glr-regr3]) + +AT_CHECK([[echo p1 t4 o2 p1 p1 t1 o1 t2 p2 o1 t3 p2 p2 | ./glr-regr3]], 0, +[[Result: 1c04 +]], []) + AT_CLEANUP -- 2.45.2