* 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.

diff --git a/ChangeLog b/ChangeLog
index 68d1c9e14031ca6b6fc2b26e3089f2434d474618..d82bb04f4591ae94f5068f8e429d2ee8d3033532 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,21 @@
+2005-05-20  Paul Hilfinger  <hilfingr@CS.Berkeley.EDU>
+
+       * 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  <eggert@cs.ucla.edu>
 
        * COPYING, ChangeLog, GNUmakefile, HACKING, Makefile.am,
 2005-05-13  Paul Eggert  <eggert@cs.ucla.edu>
 
        * COPYING, ChangeLog, GNUmakefile, HACKING, Makefile.am,

diff --git a/data/glr.c b/data/glr.c
index cce04afd1877f483c138645d1e1f8662de76e274..3d1b0ef531d13856635fb44d10a29ad1787c55ad 100644 (file)
--- 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, "%s ", Title);                                \
       yysymprint (stderr,                                      \
                   Type, Value]b4_location_if([, Location])[);  \

-      YYFPRINTF (stderr, "\n");                                        \

     }                                                          \
 } while (0)
 
     }                                                          \
 } while (0)
 


@@ -575,15 +574,26 @@ typedef struct yyGLRStack yyGLRStack;
 typedef struct yyGLRStateSet yyGLRStateSet;
 
 struct yyGLRState {
 typedef struct yyGLRStateSet yyGLRStateSet;
 
 struct yyGLRState {

+  /** Type tag: always true. */

   yybool yyisState;
   yybool yyisState;

+  /** Type tag for yysemantics. If true, yysval applies, otherwise
+   *  yyfirstVal applies. */

   yybool yyresolved;
   yybool yyresolved;

+  /** Number of corresponding LALR(1) machine state. */

   yyStateNum yylrState;
   yyStateNum yylrState;

+  /** Preceding state in this stack */

   yyGLRState* yypred;
   yyGLRState* yypred;

+  /** Source position of the first token produced by my symbol */

   size_t yyposn;
   union {
   size_t yyposn;
   union {

+    /** First in a chain of alternative reductions producing the
+     *  non-terminal corresponding to this state, threaded through 
+     *  yynext. */

     yySemanticOption* yyfirstVal;
     yySemanticOption* yyfirstVal;

+    /** Semantic value for this state. */

     YYSTYPE yysval;
   } yysemantics;
     YYSTYPE yysval;
   } yysemantics;

+  /** Source location for this state. */

   YYLTYPE yyloc;
 };
 
   YYLTYPE yyloc;
 };
 


@@ -593,12 +603,19 @@ struct yyGLRStateSet {
 };
 
 struct yySemanticOption {
 };
 
 struct yySemanticOption {

+  /** Type tag: always false. */

   yybool yyisState;
   yybool yyisState;

+  /** Rule number for this reduction */

   yyRuleNum yyrule;
   yyRuleNum yyrule;

+  /** The last RHS state in the list of states to be reduced. */

   yyGLRState* yystate;
   yyGLRState* yystate;

+  /** Next sibling in chain of options. To facilitate merging,
+   *  options are chained in decreasing order by address. */

   yySemanticOption* yynext;
 };
 
   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;
 union yyGLRStackItem {
   yyGLRState yystate;
   yySemanticOption yyoption;


@@ -1282,9 +1299,8 @@ yyidenticalOptions (yySemanticOption* yyy0, yySemanticOption* yyy1)
     return yyfalse;
 }
 
     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)
 {
 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)
        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
 }
 
 /** 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);
              yychar = YYLEX;
              *yytokenp = YYTRANSLATE (yychar);
              YY_SYMBOL_PRINT ("Next token is", *yytokenp, yylvalp, yyllocp);

+             YYDPRINTF ((stderr, "\n"));

            }
          yygetLRActions (yystate, *yytokenp, &yyaction, &yyconflicts);
 
            }
          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);
        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;
        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);
              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];
              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);
                  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)
                }
              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);
              if (yyisShiftAction (yyaction))
                {
                  YY_SYMBOL_PRINT ("Shifting", yytoken, yylvalp, yyllocp);

+                 YYDPRINTF ((stderr, "\n"));

                  if (yytoken != YYEOF)
                    yytoken = YYEMPTY;
                  yyposn += 1;
                  if (yytoken != YYEOF)
                    yytoken = YYEMPTY;
                  yyposn += 1;

diff --git a/tests/glr-regression.at b/tests/glr-regression.at
index 3abd07b7b9573533c2ced23ba548533fb1fa967b..fd822a180cede7d00eda06974321a366377539f5 100644 (file)
--- 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 <stdio.h>
+#include <stdarg.h>
+
+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<MergeRule>
+;
+
+NT2 : NT1             { $$ = RULE(3); } %merge<MergeRule>
+    | P1 NT1 O1 T3 P2 { $$ = RULE(4); } %merge<MergeRule>
+;
+
+NT3 : T3              { $$ = RULE(5); } %merge<MergeRule>
+    | P1 NT1 O1 T3 P2 { $$ = RULE(6); } %merge<MergeRule>
+;
+
+NT4 : NT3              { $$ = RULE(7); } %merge<MergeRule>
+    | NT2              { $$ = RULE(8); } %merge<MergeRule>
+    | P1 NT2 O1 NT3 P2 { $$ = RULE(9); } %merge<MergeRule>
+;
+
+NT5 : NT4              { $$ = RULE(10); } %merge<MergeRule>
+;
+
+NT6 : P1 NT1 O1 T3 P2  { $$ = RULE(11) | $2; } %merge<MergeRule>
+    | NT5              { $$ = RULE(12) | $1; } %merge<MergeRule>
+;
+
+%%
+
+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
 AT_CLEANUP