(AUTOMAKE_OPTIONS): 1.6.

[bison.git] / src / closure.c

diff --git a/src/closure.c b/src/closure.c
index 401ddc5eeb18db9caa98231dd77da503cb49bd8a..06c50364b3399b530684a163910604354ea44c4d 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,345 +18,277 @@
    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.  */
 

-
-/* Subroutines of file LR0.c.
-
-Entry points:
-
-  closure (items, n)
-
-Given a vector of item numbers items, of length n, set up ruleset and
-itemset to indicate what rules could be run and which items could be
-accepted when those items are the active ones.
-
-ruleset contains a bit for each rule.  closure sets the bits for all
-rules which could potentially describe the next input to be read.
-
-itemset is a vector of item numbers; itemsetend points to just beyond
-the end of the part of it that is significant.  closure places there
-the indices of all items which represent units of input that could
-arrive next.
-
-  initialize_closure (n)
-
-Allocates the itemset and ruleset vectors, and precomputes useful data
-so that closure can be called.  n is the number of elements to
-allocate for itemset.
-
-  finalize_closure ()
-
-Frees itemset, ruleset and internal data.
-
-*/
-
-#include <stdio.h>

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

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

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

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

 
 

-
-extern short **derives;
-extern char **tags;
-
-extern void initialize_closure PARAMS((int));
-extern void closure PARAMS((short *, int));
-extern void finalize_closure PARAMS((void));
-
-static void set_fderives PARAMS((void));
-static void set_firsts PARAMS((void));
-
-extern void RTC PARAMS((unsigned *, int));
-
+/* 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;
+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

 
 

-#ifdef DEBUG
-static void print_closure PARAMS((int));
-static void print_fderives PARAMS((void));
-static void print_firsts PARAMS((void));
-#endif
+/*-----------------.
+| Debugging code.  |
+`-----------------*/

 
 

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

 {
 {

-  itemset = NEW2(n, short);
-
-  rulesetsize = WORDSIZE(nrules + 1);
-  ruleset = NEW2(rulesetsize, unsigned);
-
-  set_fderives();
+  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);

 }
 
 
 }
 
 

-
-/* set fderives to an nvars by nrules matrix of bits
-   indicating which rules can help derive the beginning of the data
-   for each nonterminal.  For example, if symbol 5 can be derived as
-   the sequence of symbols 8 3 20, and one of the rules for deriving
-   symbol 8 is rule 4, then the [5 - ntokens, 4] bit in fderives is set.  */

 static void
 static void

-set_fderives (void)
+print_firsts (void)

 {
 {

-  register unsigned *rrow;
-  register unsigned *vrow;
-  register int j;
-  register unsigned cword;
-  register short *rp;
-  register int b;
-
-  int ruleno;
-  int i;
-
-  fderives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
-
-  set_firsts();
-
-  rrow = fderives + ntokens * rulesetsize;
+  int i, j;

 
 

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

   for (i = ntokens; i < nsyms; i++)
     {
   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;
+      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);

     }
     }

-
-#ifdef DEBUG
-  print_fderives();
-#endif
-
-  FREE(firsts);
+  fprintf (stderr, "\n\n");

 }
 
 
 }
 
 

-
-/* 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. */
-

 static void
 static void

-set_firsts (void)
+print_fderives (void)

 {
 {

-  register unsigned *row;
-/*   register int done; JF unused */
-  register int symbol;
-  register short *sp;
-  register int rowsize;
-
-  int i;
-
-  varsetsize = rowsize = WORDSIZE(nvars);
-
-  firsts = NEW2(nvars * rowsize, unsigned);
+  int i, j;

 
 

-  row = firsts;
+  fprintf (stderr, "FDERIVES\n");

   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;
+      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);
+         }

     }
     }

-
-  RTC(firsts, nvars);
-
-#ifdef DEBUG
-  print_firsts ();
-#endif
+  fprintf (stderr, "\n\n");

 }
 
 }
 

+/*--------------------------------------------------------.
+| Display the MATRIX array of SIZE bitsets of size SIZE.  |
+`--------------------------------------------------------*/

 
 

-void
-closure (short *core, int n)
+static void
+bitmatrix_print (const char *title, bitsetv matrix)

 {
 {

-  register int ruleno;
-  register unsigned word;
-  register short *csp;
-  register unsigned *dsp;
-  register 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
+  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)

     {
     {

-      while (rsp < rsend)
-       *rsp++ = 0;
-
-      csp = core;
-      while (csp < csend)
-       {
-         symbol = ritem[*csp++];
-         if (ISVAR(symbol))
-           {
-             dsp = fderives + symbol * rulesetsize;
-             rsp = ruleset;
-             while (rsp < rsend)
-               *rsp++ |= *dsp++;
-           }
-       }
+      fprintf (stderr, "%2d|", i);
+      for (j = 0; j < size; ++j)
+       fputs (bitset_test (matrix[i], j) ? "1" : " ", stderr);
+      fputs ("|\n", stderr);

     }
 
     }
 

-  ruleno = 0;
-  itemsetend = itemset;
-  csp = core;
-  rsp = ruleset;
-  while (rsp < rsend)
-    {
-      word = *rsp++;
-      if (word == 0)
-       {
-         ruleno += BITS_PER_WORD;
-       }
-      else
-       {
-         register 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++;
-           }
-       }
-    }
-
-  while (csp < csend)
-    *itemsetend++ = *csp++;
+  /* Bar. */
+  fputs ("  `", stderr);
+  for (i = 0; i < size; ++i)
+    putc ('-', stderr);
+  fputs ("'\n", stderr);

 
 

-#ifdef DEBUG
-  print_closure(n);
-#endif
+  /* 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.                                                      |
+`------------------------------------------------------------------*/

 
 

-
-void
-finalize_closure (void)
+static void
+set_firsts (void)

 {
 {

-  FREE(itemset);
-  FREE(ruleset);
-  FREE(fderives + ntokens * rulesetsize);
-}
+  int i, j;

 
 

+  firsts = bitsetv_create (nvars, nvars, BITSET_FIXED);

 
 

+  for (i = ntokens; i < nsyms; 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);
+      }
+
+  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 ();
+}

 
 

-#ifdef DEBUG
+/*-------------------------------------------------------------------.
+| Set FDERIVES to an NVARS by NRULES matrix of bits indicating which |
+| rules can help derive the beginning of the data for each           |
+| nonterminal.                                                       |
+|                                                                    |
+| For example, if symbol 5 can be derived as the sequence of symbols |
+| 8 3 20, and one of the rules for deriving symbol 8 is rule 4, then |
+| the [5 - NTOKENS, 4] bit in FDERIVES is set.                       |
+`-------------------------------------------------------------------*/

 
 static void
 
 static void

-print_closure(int n)
+set_fderives (void)

 {
 {

-  register short *isp;
+  int i, j, k;

 
 

-  printf ("\n\nn = %d\n\n", n);
-  for (isp = itemset; isp < itemsetend; isp++)
-    printf ("   %d\n", *isp);
-}
+  fderives = bitsetv_create (nvars, nrules + 1, BITSET_FIXED);

 
 

+  set_firsts ();

 
 

-static void
-print_firsts (void)
-{
-  register int i;
-  register int j;
-  register unsigned *rowp;
+  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]);

 
 

-  printf ("\n\n\nFIRSTS\n\n");
+  if (trace_flag)
+    print_fderives ();

 
 

-  for (i = ntokens; i < nsyms; i++)
-    {
-      printf ("\n\n%s firsts\n\n", tags[i]);
+  bitsetv_free (firsts);
+}
+\f

 
 

-      rowp = firsts + ((i - ntokens) * varsetsize);
+void
+new_closure (int n)
+{
+  itemset = XCALLOC (short, n);

 
 

-      for (j = 0; j < nvars; j++)
-       if (BITISSET (rowp, j))
-         printf ("   %s\n", tags[j + ntokens]);
-    }
+  ruleset = bitset_create (nrules + 1, BITSET_FIXED);
+
+  set_fderives ();

 }
 
 
 }
 
 

-static void
-print_fderives (void)
+
+void
+closure (short *core, int n)

 {
 {

-  register int i;
-  register int j;
-  register unsigned *rp;
+  /* Index over CORE. */
+  int c;

 
 

-  printf ("\n\n\nFDERIVES\n");
+  /* A bit index over RULESET. */
+  int ruleno;

 
 

-  for (i = ntokens; i < nsyms; i++)
+  if (trace_flag)
+    print_closure ("input", core, n);
+
+  if (n == 0)
+    {
+      bitset_copy (ruleset, FDERIVES (start_symbol));
+    }
+  else

     {
     {

-      printf ("\n\n%s derives\n\n", tags[i]);
-      rp = fderives + i * rulesetsize;
+      bitset_zero (ruleset);

 
 

-      for (j = 0; j <= nrules; j++)
-       if (BITISSET (rp, j))
-         printf ("   %d\n", j);
+      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)
+    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)
+    {
+      itemset[nitemset] = core[c];
+      nitemset++;
+      c++;

     }
 
     }
 

-  fflush(stdout);
+  if (trace_flag)
+    print_closure ("output", itemset, nitemset);

 }
 
 }
 

-#endif
+
+void
+free_closure (void)
+{
+  XFREE (itemset);
+  bitset_free (ruleset);
+  bitsetv_free (fderives);
+}