* src/LR0.c (new_state): Display `nstates' as the name of the

[bison.git] / src / closure.c

diff --git a/src/closure.c b/src/closure.c
index 45b85c6812db2bde254193c709f347528809a3f8..9e595c81c8dc07c443f6c7c0ff2b4c9e413a7011 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,32 +19,28 @@
    02111-1307, USA.  */
 
 #include "system.h"
    02111-1307, USA.  */
 
 #include "system.h"

+#include "bitset.h"
+#include "bitsetv.h"

 #include "getargs.h"
 #include "getargs.h"

+#include "symtab.h"

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

-#include "warshall.h"

 
 /* NITEMSET is the size of the array ITEMSET.  */
 short *itemset;
 int nitemset;
 
 
 /* NITEMSET is the size of the array ITEMSET.  */
 short *itemset;
 int nitemset;
 

-static unsigned *ruleset;
+static bitset ruleset;

 
 /* internal data.  See comments before set_fderives and set_firsts.  */
 
 /* internal data.  See comments before set_fderives and set_firsts.  */

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

 
 /* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var.  */
 
 /* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var.  */

-#define FDERIVES(Var)   (fderives + ((Var) - ntokens) * rulesetsize)
-#define   FIRSTS(Var)   (firsts   + ((Var) - ntokens) * varsetsize)
-
-/* number of words required to hold a bit for each rule */
-static int rulesetsize;
-
-/* number of words required to hold a bit for each variable */
-static int varsetsize;
+#define FDERIVES(Var)   fderives[(Var) - ntokens]
+#define   FIRSTS(Var)   firsts[(Var) - ntokens]

 \f
 
 /*-----------------.
 \f
 
 /*-----------------.


@@ -61,8 +57,8 @@ print_closure (const char *title, short *array, size_t size)
       short *rp;
       fprintf (stderr, "  %2d: .", array[i]);
       for (rp = &ritem[array[i]]; *rp >= 0; ++rp)
       short *rp;
       fprintf (stderr, "  %2d: .", array[i]);
       for (rp = &ritem[array[i]]; *rp >= 0; ++rp)

-       fprintf (stderr, " %s", tags[*rp]);
-      fprintf (stderr, "  (rule %d)\n", -*rp);
+       fprintf (stderr, " %s", symbols[*rp]->tag);
+      fprintf (stderr, "  (rule %d)\n", -*rp - 1);

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


@@ -76,10 +72,11 @@ print_firsts (void)
   fprintf (stderr, "FIRSTS\n");
   for (i = ntokens; i < nsyms; i++)
     {
   fprintf (stderr, "FIRSTS\n");
   for (i = ntokens; i < nsyms; i++)
     {

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

       for (j = 0; j < nvars; j++)
       for (j = 0; j < nvars; j++)

-       if (BITISSET (FIRSTS (i), j))
-         fprintf (stderr, "\t\t%d (%s)\n", j + ntokens, tags[j + ntokens]);
+       if (bitset_test (FIRSTS (i), j))
+         fprintf (stderr, "\t\t%d (%s)\n",
+                  j + ntokens, symbols[j + ntokens]->tag);

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


@@ -88,55 +85,104 @@ print_firsts (void)
 static void
 print_fderives (void)
 {
 static void
 print_fderives (void)
 {

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

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

-

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

-      fprintf (stderr, "\t%s derives\n", tags[i]);
-      for (j = 0; j <= nrules; j++)
-       if (BITISSET (FDERIVES (i), j))
+      fprintf (stderr, "\t%s derives\n", symbols[i]->tag);
+      for (j = 0; j < nrules + 1; j++)
+       if (bitset_test (FDERIVES (i), j))

          {
            short *rhsp;
          {
            short *rhsp;

-           fprintf (stderr, "\t\t%d:", j);
-           for (rhsp = ritem + rule_table[j].rhs; *rhsp >= 0; ++rhsp)
-             fprintf (stderr, " %s", tags[*rhsp]);
+           fprintf (stderr, "\t\t%d:", j - 1);
+           for (rhsp = rules[j].rhs; *rhsp >= 0; ++rhsp)
+             fprintf (stderr, " %s", symbols[*rhsp]->tag);

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

+
+/*--------------------------------------------------------.
+| Display the MATRIX array of SIZE bitsets of size SIZE.  |
+`--------------------------------------------------------*/
+
+static void
+bitmatrix_print (const char *title, bitsetv matrix)
+{
+  size_t i, j;
+  size_t size = bitset_size (matrix[0]);
+
+  /* Title. */
+  fprintf (stderr, "%s BEGIN\n", title);
+
+  /* Column numbers. */
+  fputs ("   ", stderr);
+  for (i = 0; i < size; ++i)
+    putc (i / 10 ? '0' + i / 10 : ' ', stderr);
+  putc ('\n', stderr);
+  fputs ("   ", stderr);
+  for (i = 0; i < size; ++i)
+    fprintf (stderr, "%d", i % 10);
+  putc ('\n', stderr);
+
+  /* Bar. */
+  fputs ("  .", stderr);
+  for (i = 0; i < size; ++i)
+    putc ('-', stderr);
+  fputs (".\n", stderr);
+
+  /* Contents. */
+  for (i = 0; i < size; ++i)
+    {
+      fprintf (stderr, "%2d|", i);
+      for (j = 0; j < size; ++j)
+       fputs (bitset_test (matrix[i], j) ? "1" : " ", stderr);
+      fputs ("|\n", stderr);
+    }
+
+  /* Bar. */
+  fputs ("  `", stderr);
+  for (i = 0; i < size; ++i)
+    putc ('-', stderr);
+  fputs ("'\n", stderr);
+
+  /* End title. */
+  fprintf (stderr, "%s END\n\n", title);
+}

 \f
 \f

-/*-------------------------------------------------------------------.
-| Set FIRSTS to be an NVARS by NVARS bit matrix indicating which     |
-| items can represent the beginning of the input corresponding to    |
-| which other items.                                                 |
-|                                                                    |
-| For example, if some rule expands symbol 5 into the sequence of    |
-| symbols 8 3 20, the symbol 8 can be the beginning of the data for  |
-| symbol 5, so the bit [8 - ntokens, 5 - ntokens] in firsts is set.  |
-`-------------------------------------------------------------------*/
+/*------------------------------------------------------------------.
+| Set FIRSTS to be an NVARS array of NVARS bitsets indicating which |
+| items can represent the beginning of the input corresponding to   |
+| which other items.                                                |
+|                                                                   |
+| For example, if some rule expands symbol 5 into the sequence of   |
+| 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.                                                      |
+`------------------------------------------------------------------*/

 
 static void
 set_firsts (void)
 {
   int i, j;
 
 
 static void
 set_firsts (void)
 {
   int i, j;
 

-  varsetsize = WORDSIZE (nvars);
-
-  firsts = XCALLOC (unsigned, nvars * varsetsize);
+  firsts = bitsetv_create (nvars, nvars, BITSET_FIXED);

 
   for (i = ntokens; i < nsyms; i++)
     for (j = 0; derives[i][j] >= 0; ++j)
       {
 
   for (i = ntokens; i < nsyms; i++)
     for (j = 0; derives[i][j] >= 0; ++j)
       {

-       int symbol = ritem[rule_table[derives[i][j]].rhs];
+       int symbol = rules[derives[i][j]].rhs[0];

        if (ISVAR (symbol))
        if (ISVAR (symbol))

-         SETBIT (FIRSTS (i), symbol - ntokens);
+         bitset_set (FIRSTS (i), symbol - ntokens);

       }
 
       }
 

-  RTC (firsts, nvars);
+  if (trace_flag)
+    bitmatrix_print ("RTC: Input", firsts);
+  bitsetv_reflexive_transitive_closure (firsts);
+  if (trace_flag)
+    bitmatrix_print ("RTC: Output", firsts);

 
   if (trace_flag)
     print_firsts ();
 
   if (trace_flag)
     print_firsts ();


@@ -157,20 +203,20 @@ set_fderives (void)
 {
   int i, j, k;
 
 {
   int i, j, k;
 

-  fderives = XCALLOC (unsigned, nvars * rulesetsize);
+  fderives = bitsetv_create (nvars, nrules + 1, BITSET_FIXED);

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

-      if (BITISSET (FIRSTS (i), j - ntokens))
+      if (bitset_test (FIRSTS (i), j - ntokens))

        for (k = 0; derives[j][k] > 0; ++k)
        for (k = 0; derives[j][k] > 0; ++k)

-         SETBIT (FDERIVES (i), derives[j][k]);
+         bitset_set (FDERIVES (i), derives[j][k]);

 
   if (trace_flag)
     print_fderives ();
 
 
   if (trace_flag)
     print_fderives ();
 

-  XFREE (firsts);
+  bitsetv_free (firsts);

 }
 \f
 
 }
 \f
 


@@ -179,8 +225,7 @@ new_closure (int n)
 {
   itemset = XCALLOC (short, n);
 
 {
   itemset = XCALLOC (short, n);
 

-  rulesetsize = WORDSIZE (nrules + 1);
-  ruleset = XCALLOC (unsigned, rulesetsize);
+  ruleset = bitset_create (nrules + 1, BITSET_FIXED);

 
   set_fderives ();
 }
 
   set_fderives ();
 }


@@ -193,37 +238,24 @@ closure (short *core, int n)
   /* Index over CORE. */
   int c;
 
   /* Index over CORE. */
   int c;
 

-  /* Index over RULESET. */
-  int r;
-

   /* A bit index over RULESET. */
   int ruleno;
 
   if (trace_flag)
     print_closure ("input", core, n);
 
   /* A bit index over RULESET. */
   int ruleno;
 
   if (trace_flag)
     print_closure ("input", core, n);
 

-  if (n == 0)
-    {
-      for (r = 0; r < rulesetsize; ++r)
-       ruleset[r] = FDERIVES (start_symbol)[r];
-    }
-  else
-    {
-      for (r = 0; r < rulesetsize; ++r)
-       ruleset[r] = 0;
+  bitset_zero (ruleset);

 
 

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

 
   nitemset = 0;
   c = 0;
   for (ruleno = 0; ruleno < nrules + 1; ++ruleno)
 
   nitemset = 0;
   c = 0;
   for (ruleno = 0; ruleno < nrules + 1; ++ruleno)

-    if (BITISSET (ruleset, ruleno))
+    if (bitset_test (ruleset, ruleno))

       {
       {

-       int itemno = rule_table[ruleno].rhs;
+       int itemno = rules[ruleno].rhs - ritem;

        while (c < n && core[c] < itemno)
          {
            itemset[nitemset] = core[c];
        while (c < n && core[c] < itemno)
          {
            itemset[nitemset] = core[c];


@@ -250,6 +282,6 @@ void
 free_closure (void)
 {
   XFREE (itemset);
 free_closure (void)
 {
   XFREE (itemset);

-  XFREE (ruleset);
-  XFREE (fderives);
+  bitset_free (ruleset);
+  bitsetv_free (fderives);

 }
 }