Re: Complain about hidden left recursion in GLR parsing

[Sylvain Schmitz]

There is a bug in the patch I sent earlier; here is the same patch, 
corrected.

--
Sorry,

  Sylvain

--- bison/src/closure.c 2005-12-10 00:51:25.000000000 +0100
+++ bison-cvs20060222/src/closure.c     2006-03-13 19:45:24.000000000 +0100
@@ -29,9 +29,11 @@
 #include <quotearg.h>
 
 #include "closure.h"
+#include "complain.h"
 #include "derives.h"
 #include "getargs.h"
 #include "gram.h"
+#include "nullable.h"
 #include "reader.h"
 #include "symtab.h"
 
@@ -44,6 +46,7 @@
 /* internal data.  See comments before set_fderives and set_firsts.  */
 static bitsetv fderives = NULL;
 static bitsetv firsts = NULL;
+static bitsetv next_vars = NULL;
 
 /* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var.  */
 #define FDERIVES(Var)   fderives[(Var) - ntokens]
@@ -120,6 +123,10 @@
 | symbols 8 3 20, the symbol 8 can be the beginning of the data for |
 | symbol 5, so the bit [8 - ntokens] in first[5 - ntokens] (= FIRST |
 | (5)) is set.                                                      |
+|                                                                   |
+| NEXT_VARS is similar but also takes nullable symbols into         |
+| account.  It is used for the detection of hidden left recursion   |
+| in GLR parsing.                                                   |
 `------------------------------------------------------------------*/
 
 static void
@@ -128,13 +135,29 @@
   symbol_number i, j;
 
   firsts = bitsetv_create (nvars, nvars, BITSET_FIXED);
+  next_vars = bitsetv_create (nvars, nvars, BITSET_FIXED);
 
   for (i = ntokens; i < nsyms; i++)
     for (j = 0; derives[i - ntokens][j]; ++j)
       {
        item_number sym = derives[i - ntokens][j]->rhs[0];
        if (ISVAR (sym))
-         bitset_set (FIRSTS (i), sym - ntokens);
+          {
+            int k = 1;
+            bitset_set (FIRSTS (i), sym - ntokens);
+            bitset_set (next_vars [i - ntokens], sym - ntokens);
+            /* Keep going in the rule right hand side if the current
+               symbol is nullable. */
+            while (nullable[sym - ntokens] 
+                   && (sym = derives[i - ntokens][j]->rhs[k]) >= 0
+                   && ISVAR (sym))
+              {
+                bitset_set (next_vars [i - ntokens], sym - ntokens);
+                k++;
+              }
+            if (ISVAR (sym))
+              bitset_set (next_vars [i - ntokens], sym - ntokens);            
+          }
       }
 
   if (trace_flag & trace_sets)
@@ -145,6 +168,43 @@
 
   if (trace_flag & trace_sets)
     print_firsts ();
+
+
+  if (glr_parser)
+    {
+      bitsetv_transitive_closure (next_vars);
+      for (i = ntokens; i < nsyms; i++)
+        if (bitset_test (next_vars[i - ntokens], i - ntokens))
+            for (j = 0; derives[i - ntokens][j]; ++j)
+              {
+                item_number sym = derives[i - ntokens][j]->rhs[0];
+                if (ISVAR(sym) && nullable[sym - ntokens])
+                  {
+                    int k = 1;
+                    while ((sym = derives[i - ntokens][j]->rhs[k++]) >= 0
+                           && ISVAR (sym)
+                           && nullable[sym - ntokens] 
+                           && !bitset_test (next_vars[sym-ntokens],i-ntokens));
+
+                    if (sym >= 0
+                        &&
+                        ((ISVAR (sym)
+                          && bitset_test (next_vars[sym-ntokens],i-ntokens))
+                         ||
+                         ((sym = derives[i - ntokens][j]->rhs[k++]) >= 0
+                          && ISVAR (sym)
+                          && bitset_test (next_vars[sym-ntokens],i-ntokens))))
+                      {
+                        complain_at (derives[i - ntokens][j]->location,
+                                     "%s: %s: ",
+                                     _("error"),
+                                     _("hidden left recursion in rule"));
+                        rule_print (derives[i - ntokens][j], stderr);
+                      }
+                  }
+              }
+    }
+  bitsetv_free (next_vars);
 }
 
 /*-------------------------------------------------------------------.