(AUTOMAKE_OPTIONS): 1.6.

[bison.git] / src / closure.c

diff --git a/src/closure.c b/src/closure.c
index 09d835002645d855dc801728866291ca26e6cdf5..06c50364b3399b530684a163910604354ea44c4d 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,29 +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;
 short *itemset;

-short *itemsetend;
-static unsigned *ruleset;
+int nitemset;

 
 

-/* internal data.  See comments before set_fderives and set_firsts.  */
-static unsigned *fderives;
-static unsigned *firsts;
-
-#define FDERIVES(Symbol)   (fderives + (Symbol) * rulesetsize)
-#define   FIRSTS(Symbol)   (firsts   + (Symbol) * varsetsize)
+static bitset ruleset;

 
 

-/* number of words required to hold a bit for each rule */
-static int rulesetsize;
+/* internal data.  See comments before set_fderives and set_firsts.  */
+static bitsetv fderives = NULL;
+static bitsetv firsts = NULL;

 
 

-/* number of words required to hold a bit for each variable */
-static int varsetsize;
+/* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var.  */
+#define FDERIVES(Var)   fderives[(Var) - ntokens]
+#define   FIRSTS(Var)   firsts[(Var) - ntokens]

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


@@ -49,35 +48,35 @@ static int varsetsize;
 `-----------------*/
 
 static void
 `-----------------*/
 
 static void

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

 {
 {

-  short *isp;
-
-  fprintf (stderr, "n = %d\n", n);
-  for (isp = itemset; isp < itemsetend; isp++)
-    fprintf (stderr, "   %d\n", *isp);
-  fprintf (stderr, "\n\n");
+  size_t i;
+  fprintf (stderr, "Closure: %s\n", title);
+  for (i = 0; i < size; ++i)
+    {
+      short *rp;
+      fprintf (stderr, "  %2d: .", array[i]);
+      for (rp = &ritem[array[i]]; *rp >= 0; ++rp)
+       fprintf (stderr, " %s", symbols[*rp]->tag);
+      fprintf (stderr, "  (rule %d)\n", -*rp - 1);
+    }
+  fputs ("\n\n", stderr);

 }
 
 
 static void
 print_firsts (void)
 {
 }
 
 
 static void
 print_firsts (void)
 {

-  int i;
-  int j;
-  unsigned *rowp;
+  int i, j;

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

-

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

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

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

-       if (BITISSET (rowp, 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");
 }


@@ -86,66 +85,104 @@ print_firsts (void)
 static void
 print_fderives (void)
 {
 static void
 print_fderives (void)
 {

-  int i;
-  int j;
-  unsigned *rp;
+  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]);
-      rp = FDERIVES (i);
-
+      fprintf (stderr, "\t%s derives\n", symbols[i]->tag);

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

-       if (BITISSET (rp, j))
-         fprintf (stderr, "\t\t%d (%s)\n", j, tags[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);
+         }

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

-\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.  |
-`-------------------------------------------------------------------*/
+
+/*--------------------------------------------------------.
+| Display the MATRIX array of SIZE bitsets of size SIZE.  |
+`--------------------------------------------------------*/

 
 static void
 
 static void

-set_firsts (void)
+bitmatrix_print (const char *title, bitsetv matrix)

 {
 {

-  unsigned *row;
-  int symbol;
-  short *sp;
-  int rowsize;
+  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);

 
 

-  int i;
+  /* End title. */
+  fprintf (stderr, "%s END\n\n", title);
+}
+\f
+/*------------------------------------------------------------------.
+| 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.                                                      |
+`------------------------------------------------------------------*/

 
 

-  varsetsize = rowsize = WORDSIZE (nvars);
+static void
+set_firsts (void)
+{
+  int i, j;

 
 

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

 
 

-  row = firsts;

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

-    {
-      sp = derives[i];
-      while (*sp >= 0)
-       {
-         symbol = ritem[rule_table[*sp++].rhs];
-         if (ISVAR (symbol))
-           {
-             symbol -= ntokens;
-             SETBIT (row, symbol);
-           }
-       }
-
-      row += rowsize;
-    }
+    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);
+      }

 
 

-  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 ();


@@ -164,51 +201,22 @@ set_firsts (void)
 static void
 set_fderives (void)
 {
 static void
 set_fderives (void)
 {

-  unsigned *rrow;
-  unsigned *vrow;
-  int j;
-  unsigned cword;
-  short *rp;
-  int b;
-
-  int ruleno;
-  int i;
+  int i, j, k;

 
 

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

 
   set_firsts ();
 
 
   set_firsts ();
 

-  rrow = FDERIVES (ntokens);
-
-  for (i = ntokens; i < nsyms; i++)
-    {
-      vrow = FIRSTS (i - ntokens);
-      cword = *vrow++;
-      b = 0;
-      for (j = ntokens; j < nsyms; j++)
-       {
-         if (cword & (1 << b))
-           {
-             rp = derives[j];
-             while ((ruleno = *rp++) > 0)
-               SETBIT (rrow, ruleno);
-           }
-
-         b++;
-         if (b >= BITS_PER_WORD && j + 1 < nsyms)
-           {
-             cword = *vrow++;
-             b = 0;
-           }
-       }
-
-      rrow += rulesetsize;
-    }
+  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]);

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

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

 }
 \f
 
 }
 \f
 


@@ -217,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 ();
 }


@@ -228,76 +235,53 @@ new_closure (int n)
 void
 closure (short *core, int n)
 {
 void
 closure (short *core, int n)
 {

-  int ruleno;
-  short *csp;
+  /* Index over CORE. */
+  int c;

 
 

-  int itemno;
-  int i;
+  /* A bit index over RULESET. */
+  int ruleno;

 
   if (trace_flag)
 
   if (trace_flag)

-    {
-      fprintf (stderr, "Entering closure (items = {");
-      for (i = 0; i < n; ++i)
-       fprintf (stderr, " %d ", core[i]);
-      fprintf (stderr, "}, nitems = %d)\n", n);
-    }
+    print_closure ("input", core, n);

 
   if (n == 0)
     {
 
   if (n == 0)
     {

-      for (i = 0; i < rulesetsize; ++i)
-       ruleset[i] = FDERIVES (start_symbol)[i];
+      bitset_copy (ruleset, FDERIVES (start_symbol));

     }
   else
     {
     }
   else
     {

-      for (i = 0; i < rulesetsize; ++i)
-       ruleset[i] = 0;
-
-      for (i = 0; i < n; ++i)
-       {
-         int symbol = ritem[core[i]];
-         if (ISVAR (symbol))
-           {
-             int j;
-             for (j = 0; j < rulesetsize; ++j)
-               ruleset[j] |= FDERIVES (symbol)[j];
-           }
-       }
+      bitset_zero (ruleset);
+
+      for (c = 0; c < n; ++c)
+       if (ISVAR (ritem[core[c]]))
+         bitset_or (ruleset, ruleset, FDERIVES (ritem[core[c]]));

     }
 
     }
 

-  ruleno = 0;
-  itemsetend = itemset;
-  csp = core;
-  for (i= 0; i < rulesetsize; ++i)
+  nitemset = 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++;
+      }
+
+  while (c < n)

     {
     {

-      int word = ruleset[i];
-      if (word == 0)
-       {
-         ruleno += BITS_PER_WORD;
-       }
-      else
-       {
-         int b;
-
-         for (b = 0; b < BITS_PER_WORD; b++)
-           {
-             if (word & (1 << b))
-               {
-                 itemno = rule_table[ruleno].rhs;
-                 while (csp < (core + n ) && *csp < itemno)
-                   *itemsetend++ = *csp++;
-                 *itemsetend++ = itemno;
-               }
-
-             ruleno++;
-           }
-       }
+      itemset[nitemset] = core[c];
+      nitemset++;
+      c++;

     }
 
     }
 

-  while (csp < (core + n))
-    *itemsetend++ = *csp++;
-

   if (trace_flag)
   if (trace_flag)

-    print_closure (n);
+    print_closure ("output", itemset, nitemset);

 }
 
 
 }
 
 


@@ -305,6 +289,6 @@ void
 free_closure (void)
 {
   XFREE (itemset);
 free_closure (void)
 {
   XFREE (itemset);

-  XFREE (ruleset);
-  XFREE (fderives + ntokens * rulesetsize);
+  bitset_free (ruleset);
+  bitsetv_free (fderives);

 }
 }