Add lib/subpipe.c.

[bison.git] / src / nullable.c

diff --git a/src/nullable.c b/src/nullable.c
index dae7a62a561f1abfba0a83dda503f07b6986defa..c0b60f64d40235e653e2f9b7033030341d0d0580 100644 (file)
--- a/src/nullable.c
+++ b/src/nullable.c
@@ -1,5 +1,5 @@
 /* Part of the bison parser generator,
 /* Part of the bison parser generator,

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


@@ -24,113 +24,114 @@
    do so.  */
 
 #include "system.h"
    do so.  */
 
 #include "system.h"

-#include "types.h"
+#include "getargs.h"
+#include "symtab.h"

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

-#include "xalloc.h"
+#include "reduce.h"

 #include "nullable.h"
 
 #include "nullable.h"
 

-char *nullable = NULL;
+/* Linked list of rules.  */
+typedef struct rule_list_s
+{
+  struct rule_list_s *next;
+  rule_t *value;
+} rule_list_t;

 
 

-void
-set_nullable (void)
+bool *nullable = NULL;
+
+static void
+nullable_print (FILE *out)

 {
 {

-  short *r;
-  short *s1;
-  short *s2;
-  int ruleno;
-  int symbol;
-  shorts *p;
-
-  short *squeue;
-  short *rcount;
-  shorts **rsets;
-  shorts *relts;
-  char any_tokens;
-  short *r1;
-
-#ifdef TRACE
-  fprintf (stderr, _("Entering set_nullable"));
-#endif
-
-  nullable = XCALLOC (char, nvars) - ntokens;
-
-  squeue = XCALLOC (short, nvars);
-  s1 = s2 = squeue;
+  int i;
+  fputs ("NULLABLE\n", out);
+  for (i = ntokens; i < nsyms; i++)
+    fprintf (out, "\t%s: %s\n", symbols[i]->tag, nullable[i] ? "yes" : "no");
+  fputs ("\n\n", out);
+}

 
 

-  rcount = XCALLOC (short, nrules + 1);
-  rsets = XCALLOC (shorts *, nvars) - ntokens;
+void
+nullable_compute (void)
+{
+  rule_number_t ruleno;
+  symbol_number_t *s1;
+  symbol_number_t *s2;
+  rule_list_t *p;
+
+  symbol_number_t *squeue = XCALLOC (symbol_number_t, nvars);
+  short *rcount = XCALLOC (short, nrules);
+  /* RITEM contains all the rules, including useless productions.
+     Hence we must allocate room for useless nonterminals too.  */
+  rule_list_t **rsets = XCALLOC (rule_list_t *, nvars) - ntokens;

   /* This is said to be more elements than we actually use.
   /* This is said to be more elements than we actually use.

-     Supposedly nitems - nrules is enough.
-     But why take the risk?  */
-  relts = XCALLOC (shorts, nitems + nvars + 1);
+     Supposedly NRITEMS - NRULES is enough.  But why take the risk?  */
+  rule_list_t *relts = XCALLOC (rule_list_t, nritems + nvars + 1);
+
+  nullable = XCALLOC (bool, nvars) - ntokens;
+
+  s1 = s2 = squeue;

   p = relts;
 
   p = relts;
 

-  r = ritem;
-  while (*r)
-    {
-      if (*r < 0)
-       {
-         symbol = rlhs[-(*r++)];
-         if (symbol >= 0 && !nullable[symbol])
-           {
-             nullable[symbol] = 1;
-             *s2++ = symbol;
-           }
-       }
-      else
-       {
-         r1 = r;
-         any_tokens = 0;
-         for (symbol = *r++; symbol > 0; symbol = *r++)
-           {
-             if (ISTOKEN (symbol))
+  for (ruleno = 0; ruleno < nrules; ++ruleno)
+    if (rules[ruleno].useful)
+      {
+       rule_t *rule = &rules[ruleno];
+       if (rule->rhs[0] >= 0)
+         {
+           /* This rule has a non empty RHS. */
+           item_number_t *r = NULL;
+           int any_tokens = 0;
+           for (r = rule->rhs; *r >= 0; ++r)
+             if (ISTOKEN (*r))

                any_tokens = 1;
                any_tokens = 1;

-           }

 
 

-         if (!any_tokens)
-           {
-             ruleno = -symbol;
-             r = r1;
-             for (symbol = *r++; symbol > 0; symbol = *r++)
+           /* This rule has only nonterminals: schedule it for the second
+              pass.  */
+           if (!any_tokens)
+             for (r = rule->rhs; *r >= 0; ++r)

                {
                  rcount[ruleno]++;
                {
                  rcount[ruleno]++;

-                 p->next = rsets[symbol];
-                 p->value = ruleno;
-                 rsets[symbol] = p;
+                 p->next = rsets[*r];
+                 p->value = rule;
+                 rsets[*r] = p;

                  p++;
                }
                  p++;
                }

-           }
-       }
-    }
+         }
+       else
+         {
+           /* This rule has an empty RHS. */
+           assert (item_number_as_rule_number (rule->rhs[0]) == ruleno);
+           if (rule->useful && !nullable[rule->lhs->number])
+             {
+               nullable[rule->lhs->number] = 1;
+               *s2++ = rule->lhs->number;
+             }
+         }
+      }

 
   while (s1 < s2)
 
   while (s1 < s2)

-    {
-      p = rsets[*s1++];
-      while (p)
-       {
-         ruleno = p->value;
-         p = p->next;
-         if (--rcount[ruleno] == 0)
+    for (p = rsets[*s1++]; p; p = p->next)
+      {
+       rule_t *rule = p->value;
+       if (--rcount[rule->number] == 0)
+         if (rule->useful && !nullable[rule->lhs->number])

            {
            {

-             symbol = rlhs[ruleno];
-             if (symbol >= 0 && !nullable[symbol])
-               {
-                 nullable[symbol] = 1;
-                 *s2++ = symbol;
-               }
+             nullable[rule->lhs->number] = 1;
+             *s2++ = rule->lhs->number;

            }
            }

-       }
-    }
+      }

 
   XFREE (squeue);
   XFREE (rcount);
   XFREE (rsets + ntokens);
   XFREE (relts);
 
   XFREE (squeue);
   XFREE (rcount);
   XFREE (rsets + ntokens);
   XFREE (relts);

+
+  if (trace_flag & trace_sets)
+    nullable_print (stderr);

 }
 
 
 void
 }
 
 
 void

-free_nullable (void)
+nullable_free (void)

 {
   XFREE (nullable + ntokens);
 }
 {
   XFREE (nullable + ntokens);
 }