Update.

[bison.git] / src / closure.c

diff --git a/src/closure.c b/src/closure.c
index ab745b8db04585258a42c538cbc63fd154a3cc31..3d5ac28d0bcf69957980add665f832f67a517bd7 100644 (file)
--- a/src/closure.c
+++ b/src/closure.c
@@ -1,5 +1,5 @@
 /* Subroutines for bison
 /* Subroutines for bison

-   Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc.
+   Copyright (C) 1984, 1989, 2000, 2001, 2002 Free Software Foundation, Inc.

 
    This file is part of Bison, the GNU Compiler Compiler.
 
 
    This file is part of Bison, the GNU Compiler Compiler.
 


@@ -19,24 +19,26 @@
    02111-1307, USA.  */
 
 #include "system.h"
    02111-1307, USA.  */
 
 #include "system.h"

+#include "quotearg.h"
+#include "bitset.h"
+#include "bitsetv.h"
+#include "bitsetv-print.h"

 #include "getargs.h"
 #include "symtab.h"
 #include "gram.h"
 #include "reader.h"
 #include "closure.h"
 #include "derives.h"
 #include "getargs.h"
 #include "symtab.h"
 #include "gram.h"
 #include "reader.h"
 #include "closure.h"
 #include "derives.h"

-#include "bitset.h"
-#include "warshall.h"

 
 /* NITEMSET is the size of the array ITEMSET.  */
 
 /* NITEMSET is the size of the array ITEMSET.  */

-short *itemset;
-int nitemset;
+item_number_t *itemset;
+int nritemset;

 
 static bitset ruleset;
 
 /* internal data.  See comments before set_fderives and set_firsts.  */
 
 static bitset ruleset;
 
 /* internal data.  See comments before set_fderives and set_firsts.  */

-static bitset *fderives = NULL;
-static bitset *firsts = NULL;
+static bitsetv fderives = NULL;
+static bitsetv firsts = NULL;

 
 /* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var.  */
 #define FDERIVES(Var)   fderives[(Var) - ntokens]
 
 /* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var.  */
 #define FDERIVES(Var)   fderives[(Var) - ntokens]


@@ -48,13 +50,13 @@ static bitset *firsts = NULL;
 `-----------------*/
 
 static void
 `-----------------*/
 
 static void

-print_closure (const char *title, short *array, size_t size)
+print_closure (const char *title, item_number_t *array, size_t size)

 {
   size_t i;
   fprintf (stderr, "Closure: %s\n", title);
   for (i = 0; i < size; ++i)
     {
 {
   size_t i;
   fprintf (stderr, "Closure: %s\n", title);
   for (i = 0; i < size; ++i)
     {

-      short *rp;
+      item_number_t *rp;

       fprintf (stderr, "  %2d: .", array[i]);
       for (rp = &ritem[array[i]]; *rp >= 0; ++rp)
        fprintf (stderr, " %s", symbols[*rp]->tag);
       fprintf (stderr, "  %2d: .", array[i]);
       for (rp = &ritem[array[i]]; *rp >= 0; ++rp)
        fprintf (stderr, " %s", symbols[*rp]->tag);


@@ -67,16 +69,18 @@ print_closure (const char *title, short *array, size_t size)
 static void
 print_firsts (void)
 {
 static void
 print_firsts (void)
 {

-  int i, j;
+  symbol_number_t i, j;

 
   fprintf (stderr, "FIRSTS\n");
   for (i = ntokens; i < nsyms; i++)
     {
 
   fprintf (stderr, "FIRSTS\n");
   for (i = ntokens; i < nsyms; i++)
     {

+      bitset_iterator iter;

       fprintf (stderr, "\t%s firsts\n", symbols[i]->tag);
       fprintf (stderr, "\t%s firsts\n", symbols[i]->tag);

-      for (j = 0; j < nvars; j++)
-       if (bitset_test (FIRSTS (i), j))
-         fprintf (stderr, "\t\t%d (%s)\n",
-                  j + ntokens, symbols[j + ntokens]->tag);
+      BITSET_FOR_EACH (iter, FIRSTS (i), j, 0)
+       {
+         fprintf (stderr, "\t\t%s\n",
+                  symbols[j + ntokens]->tag);
+       }

     }
   fprintf (stderr, "\n\n");
 }
     }
   fprintf (stderr, "\n\n");
 }


@@ -85,21 +89,19 @@ print_firsts (void)
 static void
 print_fderives (void)
 {
 static void
 print_fderives (void)
 {

-  int i, j;
+  int i;
+  rule_number_t r;

 
   fprintf (stderr, "FDERIVES\n");
   for (i = ntokens; i < nsyms; i++)
     {
 
   fprintf (stderr, "FDERIVES\n");
   for (i = ntokens; i < nsyms; i++)
     {

+      bitset_iterator iter;

       fprintf (stderr, "\t%s derives\n", symbols[i]->tag);
       fprintf (stderr, "\t%s derives\n", symbols[i]->tag);

-      for (j = 0; j <= nrules; j++)
-       if (bitset_test (FDERIVES (i), j))
-         {
-           short *rhsp;
-           fprintf (stderr, "\t\t%d:", j - 1);
-           for (rhsp = &ritem[rules[j].rhs]; *rhsp >= 0; ++rhsp)
-             fprintf (stderr, " %s", symbols[*rhsp]->tag);
-           fputc ('\n', stderr);
-         }
+      BITSET_FOR_EACH (iter, FDERIVES (i), r, 0)
+       {
+         fprintf (stderr, "\t\t%3d ", r);
+         rule_rhs_print (&rules[r], stderr);
+       }

     }
   fprintf (stderr, "\n\n");
 }
     }
   fprintf (stderr, "\n\n");
 }


@@ -118,24 +120,25 @@ print_fderives (void)
 static void
 set_firsts (void)
 {
 static void
 set_firsts (void)
 {

-  int i, j;
+  symbol_number_t i, j;
+
+  firsts = bitsetv_create (nvars, nvars, BITSET_FIXED);

 
 

-  firsts = XCALLOC (bitset, nvars);

   for (i = ntokens; i < nsyms; i++)
   for (i = ntokens; i < nsyms; i++)

-    {
-      FIRSTS (i) = bitset_create (nvars, BITSET_FIXED);
-      bitset_zero (FIRSTS (i));
-      for (j = 0; derives[i][j] >= 0; ++j)
-       {
-         int symbol = ritem[rules[derives[i][j]].rhs];
-         if (ISVAR (symbol))
-           bitset_set (FIRSTS (i), symbol - ntokens);
-       }
-    }
+    for (j = 0; derives[i][j]; ++j)
+      {
+       int symbol = derives[i][j]->rhs[0];
+       if (ISVAR (symbol))
+         bitset_set (FIRSTS (i), symbol - ntokens);
+      }

 
 

-  RTC (firsts, nvars);
+  if (trace_flag & trace_sets)
+    bitsetv_matrix_dump (stderr, "RTC: Firsts Input", firsts);
+  bitsetv_reflexive_transitive_closure (firsts);
+  if (trace_flag & trace_sets)
+    bitsetv_matrix_dump (stderr, "RTC: Firsts Output", firsts);

 
 

-  if (trace_flag)
+  if (trace_flag & trace_sets)

     print_firsts ();
 }
 
     print_firsts ();
 }
 


@@ -152,40 +155,33 @@ set_firsts (void)
 static void
 set_fderives (void)
 {
 static void
 set_fderives (void)
 {

-  int i, j, k;
+  symbol_number_t i, j;
+  rule_number_t k;

 
 

-  fderives = XCALLOC (bitset, nvars);
-  bitset_stats_init ();
-  for (i = 0 ; i < nvars; ++i)
-    {
-      fderives[i] = bitset_create (nrules + 1, BITSET_FIXED);
-      bitset_zero (fderives[i]);
-    }
+  fderives = bitsetv_create (nvars, nrules, BITSET_FIXED);

 
   set_firsts ();
 
   for (i = ntokens; i < nsyms; ++i)
     for (j = ntokens; j < nsyms; ++j)
       if (bitset_test (FIRSTS (i), j - ntokens))
 
   set_firsts ();
 
   for (i = ntokens; i < nsyms; ++i)
     for (j = ntokens; j < nsyms; ++j)
       if (bitset_test (FIRSTS (i), j - ntokens))

-       for (k = 0; derives[j][k] > 0; ++k)
-         bitset_set (FDERIVES (i), derives[j][k]);
+       for (k = 0; derives[j][k]; ++k)
+         bitset_set (FDERIVES (i), derives[j][k]->number);

 
 

-  if (trace_flag)
+  if (trace_flag & trace_sets)

     print_fderives ();
 
     print_fderives ();
 

-  for (i = ntokens; i < nsyms; ++i)
-    bitset_free (FIRSTS (i));
-  XFREE (firsts);
+  bitsetv_free (firsts);

 }
 }

+

 \f
 
 void
 new_closure (int n)
 {
 \f
 
 void
 new_closure (int n)
 {

-  itemset = XCALLOC (short, n);
+  itemset = XCALLOC (item_number_t, n);

 
 

-  ruleset = bitset_create (nrules + 1, BITSET_FIXED);
-  bitset_zero (ruleset);
+  ruleset = bitset_create (nrules, BITSET_FIXED);

 
   set_fderives ();
 }
 
   set_fderives ();
 }


@@ -193,70 +189,56 @@ new_closure (int n)
 
 
 void
 
 
 void

-closure (short *core, int n)
+closure (item_number_t *core, int n)

 {
   /* Index over CORE. */
   int c;
 
 {
   /* Index over CORE. */
   int c;
 

-  /* An index over RULESET. */
-  int r;
-

   /* A bit index over RULESET. */
   /* A bit index over RULESET. */

-  int ruleno;
+  rule_number_t ruleno;

 
 

-  if (trace_flag)
+  bitset_iterator iter;
+
+  if (trace_flag & trace_sets)

     print_closure ("input", core, n);
 
     print_closure ("input", core, n);
 

-  if (n == 0)
-    {
-      bitset_copy (ruleset, FDERIVES (start_symbol));
-    }
-  else
-    {
-      bitset_zero (ruleset);
+  bitset_zero (ruleset);

 
 

-      for (c = 0; c < n; ++c)
-       if (ISVAR (ritem[core[c]]))
-         bitset_or (ruleset, ruleset, FDERIVES (ritem[core[c]]));
-    }
+  for (c = 0; c < n; ++c)
+    if (ISVAR (ritem[core[c]]))
+      bitset_or (ruleset, ruleset, FDERIVES (ritem[core[c]]));

 
 

-  nitemset = 0;
+  nritemset = 0;

   c = 0;
   c = 0;

-  for (ruleno = 0; ruleno < nrules + 1; ++ruleno)
-    if (bitset_test (ruleset, ruleno))
-      {
-       int itemno = rules[ruleno].rhs;
-       while (c < n && core[c] < itemno)
-         {
-           itemset[nitemset] = core[c];
-           nitemset++;
-           c++;
-         }
-       itemset[nitemset] = itemno;
-       nitemset++;
-      }
+  BITSET_FOR_EACH (iter, ruleset, ruleno, 0)
+    {
+      item_number_t itemno = rules[ruleno].rhs - ritem;
+      while (c < n && core[c] < itemno)
+       {
+         itemset[nritemset] = core[c];
+         nritemset++;
+         c++;
+       }
+      itemset[nritemset] = itemno;
+      nritemset++;
+    };

 
   while (c < n)
     {
 
   while (c < n)
     {

-      itemset[nitemset] = core[c];
-      nitemset++;
+      itemset[nritemset] = core[c];
+      nritemset++;

       c++;
     }
 
       c++;
     }
 

-  if (trace_flag)
-    print_closure ("output", itemset, nitemset);
+  if (trace_flag & trace_sets)
+    print_closure ("output", itemset, nritemset);

 }
 
 
 void
 free_closure (void)
 {
 }
 
 
 void
 free_closure (void)
 {

-  int i;

   XFREE (itemset);
   XFREE (itemset);

-

   bitset_free (ruleset);
   bitset_free (ruleset);

-
-  for (i = 0 ; i < nvars; ++i)
-    bitset_free (fderives[i]);
-  free (fderives);
+  bitsetv_free (fderives);

 }
 }