Update.

[bison.git] / src / closure.c

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

-   Copyright (C) 1984, 1989, 2000 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.
 


@@ -18,66 +18,71 @@
    Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
    02111-1307, USA.  */
 
    Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
    02111-1307, USA.  */
 

-

 #include "system.h"
 #include "system.h"

-#include "alloc.h"
+#include "quotearg.h"
+#include "bitset.h"
+#include "bitsetv.h"
+#include "bitsetv-print.h"
+#include "getargs.h"
+#include "symtab.h"

 #include "gram.h"
 #include "gram.h"

+#include "reader.h"

 #include "closure.h"
 #include "closure.h"

+#include "derives.h"

 
 

-extern short **derives;
-
-extern void RTC PARAMS ((unsigned *, int));
+/* NITEMSET is the size of the array ITEMSET.  */
+item_number_t *itemset;
+int nritemset;

 
 

-short *itemset;
-short *itemsetend;
-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;

 
 

-/* 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;
+/* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var.  */
+#define FDERIVES(Var)   fderives[(Var) - ntokens]
+#define   FIRSTS(Var)   firsts[(Var) - ntokens]

 \f
 \f

-#if DEBUG

 
 /*-----------------.
 | Debugging code.  |
 `-----------------*/
 
 static void
 
 /*-----------------.
 | Debugging code.  |
 `-----------------*/
 
 static void

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

 {
 {

-  short *isp;
-
-  printf ("\n\nn = %d\n\n", n);
-  for (isp = itemset; isp < itemsetend; isp++)
-    printf ("   %d\n", *isp);
+  size_t i;
+  fprintf (stderr, "Closure: %s\n", title);
+  for (i = 0; i < size; ++i)
+    {
+      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, "  (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;
-
-  printf ("\n\n\nFIRSTS\n\n");
+  symbol_number_t i, j;

 
 

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

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

-      printf ("\n\n%s firsts\n\n", tags[i]);
-
-      rowp = firsts + ((i - ntokens) * varsetsize);
-
-      for (j = 0; j < nvars; j++)
-       if (BITISSET (rowp, j))
-         printf ("   %s\n", tags[j + ntokens]);
+      bitset_iterator iter;
+      fprintf (stderr, "\t%s firsts\n", symbols[i]->tag);
+      BITSET_FOR_EACH (iter, FIRSTS (i), j, 0)
+       {
+         fprintf (stderr, "\t\t%s\n",
+                  symbols[j + ntokens]->tag);
+       }

     }
     }

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

 }
 
 
 }
 
 


@@ -85,71 +90,56 @@ static void
 print_fderives (void)
 {
   int i;
 print_fderives (void)
 {
   int i;

-  int j;
-  unsigned *rp;
-
-  printf ("\n\n\nFDERIVES\n");
+  rule_number_t r;

 
 

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

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

-      printf ("\n\n%s derives\n\n", tags[i]);
-      rp = fderives + i * rulesetsize;
-
-      for (j = 0; j <= nrules; j++)
-       if (BITISSET (rp, j))
-         printf ("   %d\n", j);
+      bitset_iterator iter;
+      fprintf (stderr, "\t%s derives\n", symbols[i]->tag);
+      BITSET_FOR_EACH (iter, FDERIVES (i), r, 0)
+       {
+         fprintf (stderr, "\t\t%3d ", r);
+         rule_rhs_print (&rules[r], stderr);
+       }

     }
     }

-
-  fflush (stdout);
+  fprintf (stderr, "\n\n");

 }
 }

-#endif

 \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)
 {
 
 static void
 set_firsts (void)
 {

-  unsigned *row;
-  int symbol;
-  short *sp;
-  int rowsize;
+  symbol_number_t i, j;

 
 

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

 
 

-  varsetsize = rowsize = WORDSIZE (nvars);
-
-  firsts = NEW2 (nvars * rowsize, unsigned);
-
-  row = firsts;

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

-    {
-      sp = derives[i];
-      while (*sp >= 0)
-       {
-         symbol = ritem[rrhs[*sp++]];
-         if (ISVAR (symbol))
-           {
-             symbol -= ntokens;
-             SETBIT (row, symbol);
-           }
-       }
-
-      row += rowsize;
-    }
-
-  RTC (firsts, nvars);
-
-#ifdef DEBUG
-  print_firsts ();
-#endif
+    for (j = 0; derives[i][j]; ++j)
+      {
+       int symbol = derives[i][j]->rhs[0];
+       if (ISVAR (symbol))
+         bitset_set (FIRSTS (i), symbol - ntokens);
+      }
+
+  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 & trace_sets)
+    print_firsts ();

 }
 
 /*-------------------------------------------------------------------.
 }
 
 /*-------------------------------------------------------------------.


@@ -165,64 +155,33 @@ 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;
+  symbol_number_t i, j;
+  rule_number_t k;

 
 

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

 
   set_firsts ();
 
 
   set_firsts ();
 

-  rrow = fderives + ntokens * rulesetsize;
-
-  for (i = ntokens; i < nsyms; i++)
-    {
-      vrow = firsts + ((i - ntokens) * varsetsize);
-      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]; ++k)
+         bitset_set (FDERIVES (i), derives[j][k]->number);

 
 

-#ifdef DEBUG
-  print_fderives ();
-#endif
+  if (trace_flag & trace_sets)
+    print_fderives ();

 
 

-  FREE (firsts);
+  bitsetv_free (firsts);

 }
 }

+

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

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

 
 

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

 
   set_fderives ();
 }
 
   set_fderives ();
 }


@@ -230,91 +189,56 @@ new_closure (int n)
 
 
 void
 
 
 void

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

 {
 {

-  int ruleno;
-  unsigned word;
-  short *csp;
-  unsigned *dsp;
-  unsigned *rsp;
-
-  short *csend;
-  unsigned *rsend;
-  int symbol;
-  int itemno;
-
-  rsp = ruleset;
-  rsend = ruleset + rulesetsize;
-  csend = core + n;
-
-  if (n == 0)
-    {
-      dsp = fderives + start_symbol * rulesetsize;
-      while (rsp < rsend)
-       *rsp++ = *dsp++;
-    }
-  else
-    {
-      while (rsp < rsend)
-       *rsp++ = 0;
+  /* Index over CORE. */
+  int c;

 
 

-      csp = core;
-      while (csp < csend)
-       {
-         symbol = ritem[*csp++];
-         if (ISVAR (symbol))
-           {
-             dsp = fderives + symbol * rulesetsize;
-             rsp = ruleset;
-             while (rsp < rsend)
-               *rsp++ |= *dsp++;
-           }
-       }
-    }
+  /* A bit index over RULESET. */
+  rule_number_t ruleno;
+
+  bitset_iterator iter;
+
+  if (trace_flag & trace_sets)
+    print_closure ("input", core, n);
+
+  bitset_zero (ruleset);

 
 

-  ruleno = 0;
-  itemsetend = itemset;
-  csp = core;
-  rsp = ruleset;
-  while (rsp < rsend)
+  for (c = 0; c < n; ++c)
+    if (ISVAR (ritem[core[c]]))
+      bitset_or (ruleset, ruleset, FDERIVES (ritem[core[c]]));
+
+  nritemset = 0;
+  c = 0;
+  BITSET_FOR_EACH (iter, ruleset, ruleno, 0)

     {
     {

-      word = *rsp++;
-      if (word == 0)
-       {
-         ruleno += BITS_PER_WORD;
-       }
-      else
+      item_number_t itemno = rules[ruleno].rhs - ritem;
+      while (c < n && core[c] < itemno)

        {
        {

-         int b;
-
-         for (b = 0; b < BITS_PER_WORD; b++)
-           {
-             if (word & (1 << b))
-               {
-                 itemno = rrhs[ruleno];
-                 while (csp < csend && *csp < itemno)
-                   *itemsetend++ = *csp++;
-                 *itemsetend++ = itemno;
-               }
-
-             ruleno++;
-           }
+         itemset[nritemset] = core[c];
+         nritemset++;
+         c++;

        }
        }

-    }
+      itemset[nritemset] = itemno;
+      nritemset++;
+    };

 
 

-  while (csp < csend)
-    *itemsetend++ = *csp++;
+  while (c < n)
+    {
+      itemset[nritemset] = core[c];
+      nritemset++;
+      c++;
+    }

 
 

-#if DEBUG
-  print_closure (n);
-#endif
+  if (trace_flag & trace_sets)
+    print_closure ("output", itemset, nritemset);

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

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

 }
 }