Stop storing rules from 1 to nrules + 1.

[bison.git] / src / nullable.c

diff --git a/src/nullable.c b/src/nullable.c
index 2797180c4496e51341627394bbb84bb352c36831..6a70fa572be96a66dd3aa90c4b8dc6374234408f 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 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.
 


@@ -25,12 +25,18 @@
 
 #include "system.h"
 #include "getargs.h"
 
 #include "system.h"
 #include "getargs.h"

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

 #include "gram.h"
 #include "reduce.h"
 #include "nullable.h"
 
 #include "gram.h"
 #include "reduce.h"
 #include "nullable.h"
 

+/* Linked list of rule numbers.  */
+typedef struct rule_list_s
+{
+  struct rule_list_s *next;
+  rule_number_t value;
+} rule_list_t;
+

 char *nullable = NULL;
 
 static void
 char *nullable = NULL;
 
 static void


@@ -39,91 +45,83 @@ nullable_print (FILE *out)
   int i;
   fputs ("NULLABLE\n", out);
   for (i = ntokens; i < nsyms; i++)
   int i;
   fputs ("NULLABLE\n", out);
   for (i = ntokens; i < nsyms; i++)

-    fprintf (out, "\t%s: %s\n", tags[i], nullable[i] ? "yes" : "no");
+    fprintf (out, "\t%s: %s\n", symbols[i]->tag, nullable[i] ? "yes" : "no");

   fputs ("\n\n", out);
 }
 
 void
 set_nullable (void)
 {
   fputs ("\n\n", out);
 }
 
 void
 set_nullable (void)
 {

-  short *r;
-  short *s1;
-  short *s2;
-  shorts *p;
+  rule_number_t ruleno;
+  symbol_number_t *s1;
+  symbol_number_t *s2;
+  rule_list_t *p;

 
 

-  short *squeue;
-  short *rcount;
-  shorts **rsets;
-  shorts *relts;
+  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.
+     Supposedly NRITEMS - NRULES is enough.  But why take the risk?  */
+  rule_list_t *relts = XCALLOC (rule_list_t, nritems + nvars + 1);

 
   if (trace_flag)
     fprintf (stderr, "Entering set_nullable\n");
 
   nullable = XCALLOC (char, nvars) - ntokens;
 
 
   if (trace_flag)
     fprintf (stderr, "Entering set_nullable\n");
 
   nullable = XCALLOC (char, nvars) - ntokens;
 

-  squeue = XCALLOC (short, nvars);

   s1 = s2 = squeue;
   s1 = s2 = squeue;

-
-  rcount = XCALLOC (short, nrules + 1);
-
-  /* RITEM contains all the rules, including useless productions.
-     Hence we must allocate room for useless nonterminals too.  */
-  rsets = XCALLOC (shorts *, nvars + nuseless_nonterminals) - ntokens;
-  /* 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 + nuseless_nonterminals + 1);

   p = relts;
 
   p = relts;
 

-  for (r = ritem; *r; ++r)
-    {
-      /* Walk RITEM to find (i), if there are any tokens in the
-        RHS, and (ii), to find RULENO. */
-      int ruleno;
-      int any_tokens = 0;
-      short *r1;
-      for (r1 = r; *r1 > 0; ++r1)
-       if (ISTOKEN (*r1))
-         any_tokens = 1;
-      ruleno = -*r1;
-
-      /* Examine the RHS of the rule.  */
-      if (!any_tokens)
-       for (/* Nothing. */; *r > 0; ++r)
+  for (ruleno = 0; ruleno < nrules; ++ruleno)
+    if (rules[ruleno].useful)
+      {
+       rule_t *rule = &rules[ruleno];
+       if (rule->rhs[0] >= 0)

          {
          {

-           rcount[ruleno]++;
-           p->next = rsets[*r];
-           p->value = ruleno;
-           rsets[*r] = p;
-           p++;
+           /* 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;
+
+           /* This rule has only nonterminals: schedule it for the second
+              pass.  */
+           if (!any_tokens)
+             for (r = rule->rhs; *r >= 0; ++r)
+               {
+                 rcount[ruleno]++;
+                 p->next = rsets[*r];
+                 p->value = ruleno;
+                 rsets[*r] = p;
+                 p++;
+               }

          }
          }

-
-      /* Examine its LHS. */
-      if (rule_table[ruleno].useful && !nullable[rule_table[ruleno].lhs])
-       {
-         nullable[rule_table[ruleno].lhs] = 1;
-         *s2++ = rule_table[ruleno].lhs;
-        }
-    }
+       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)
-       {
-         int ruleno = p->value;
-         p = p->next;
-         if (--rcount[ruleno] == 0)
+    for (p = rsets[*s1++]; p; p = p->next)
+      {
+       ruleno = p->value;
+       if (--rcount[ruleno] == 0)
+         if (rules[ruleno].useful && !nullable[rules[ruleno].lhs->number])

            {
            {

-             int symbol = rule_table[ruleno].lhs;
-             if (symbol >= 0 && !nullable[symbol])
-               {
-                 nullable[symbol] = 1;
-                 *s2++ = symbol;
-               }
+             nullable[rules[ruleno].lhs->number] = 1;
+             *s2++ = rules[ruleno].lhs->number;

            }
            }

-       }
-    }
+      }

 
   XFREE (squeue);
   XFREE (rcount);
 
   XFREE (squeue);
   XFREE (rcount);