Update version number to 1.75g.

[bison.git] / src / nullable.c

diff --git a/src/nullable.c b/src/nullable.c
index f8c9b32e5cf523b36742cb375ef0a087188ce2be..beedf2b140f06281beb326df5b400cc70f684367 100644 (file)
--- a/src/nullable.c
+++ b/src/nullable.c
@@ -1,5 +1,6 @@
-/* Part of the bison parser generator,
-   Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc.
+/* Calculate which nonterminals can expand into the null string for Bison.
+
+   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,14 +25,21 @@
    do so.  */
 
 #include "system.h"
    do so.  */
 
 #include "system.h"

+

 #include "getargs.h"
 #include "getargs.h"

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

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

-#include "reduce.h"

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

+#include "reduce.h"
+#include "symtab.h"
+
+/* Linked list of rules.  */
+typedef struct rule_list
+{
+  struct rule_list *next;
+  rule *value;
+} rule_list;

 
 

-char *nullable = NULL;
+bool *nullable = NULL;

 
 static void
 nullable_print (FILE *out)
 
 static void
 nullable_print (FILE *out)


@@ -39,95 +47,96 @@ 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", symbols[i]->tag, nullable[i] ? "yes" : "no");
+    fprintf (out, "\t%s: %s\n", symbols[i]->tag,
+            nullable[i - ntokens] ? "yes" : "no");

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

-set_nullable (void)
+nullable_compute (void)

 {
 {

-  int ruleno;
-  short *s1;
-  short *s2;
-  shorts *p;
+  rule_number ruleno;
+  symbol_number *s1;
+  symbol_number *s2;
+  rule_list *p;

 
 

-  short *squeue = XCALLOC (short, nvars);
-  short *rcount = XCALLOC (short, nrules + 1);
+  symbol_number *squeue = CALLOC (squeue, nvars);
+  short *rcount = CALLOC (rcount, nrules);

   /* RITEM contains all the rules, including useless productions.
      Hence we must allocate room for useless nonterminals too.  */
   /* RITEM contains all the rules, including useless productions.
      Hence we must allocate room for useless nonterminals too.  */

-  shorts **rsets = XCALLOC (shorts *, nvars) - ntokens;
+  rule_list **rsets = CALLOC (rsets, nvars);

   /* This is said to be more elements than we actually use.
      Supposedly NRITEMS - NRULES is enough.  But why take the risk?  */
   /* This is said to be more elements than we actually use.
      Supposedly NRITEMS - NRULES is enough.  But why take the risk?  */

-  shorts *relts = XCALLOC (shorts, nritems + nvars + 1);
-
-  if (trace_flag)
-    fprintf (stderr, "Entering set_nullable\n");
+  rule_list *relts = CALLOC (relts, nritems + nvars + 1);

 
 

-  nullable = XCALLOC (char, nvars) - ntokens;
+  CALLOC (nullable, nvars);

 
   s1 = s2 = squeue;
   p = relts;
 
 
   s1 = s2 = squeue;
   p = relts;
 

-  for (ruleno = 1; ruleno < nrules + 1; ++ruleno)
+  for (ruleno = 0; ruleno < nrules; ++ruleno)

     if (rules[ruleno].useful)
       {
     if (rules[ruleno].useful)
       {

-       if (ritem[rules[ruleno].rhs] >= 0)
+       rule *rules_ruleno = &rules[ruleno];
+       if (rules_ruleno->rhs[0] >= 0)

          {
            /* This rule has a non empty RHS. */
          {
            /* This rule has a non empty RHS. */

-           short *r;
+           item_number *r = NULL;

            int any_tokens = 0;
            int any_tokens = 0;

-           for (r = &ritem[rules[ruleno].rhs]; *r >= 0; ++r)
+           for (r = rules_ruleno->rhs; *r >= 0; ++r)

              if (ISTOKEN (*r))
                any_tokens = 1;
 
            /* This rule has only nonterminals: schedule it for the second
               pass.  */
            if (!any_tokens)
              if (ISTOKEN (*r))
                any_tokens = 1;
 
            /* This rule has only nonterminals: schedule it for the second
               pass.  */
            if (!any_tokens)

-             for (r = &ritem[rules[ruleno].rhs]; *r >= 0; ++r)
+             for (r = rules_ruleno->rhs; *r >= 0; ++r)

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

-                 p->next = rsets[*r];
-                 p->value = ruleno;
-                 rsets[*r] = p;
+                 p->next = rsets[*r - ntokens];
+                 p->value = rules_ruleno;
+                 rsets[*r - ntokens] = p;

                  p++;
                }
          }
        else
          {
            /* This rule has an empty RHS. */
                  p++;
                }
          }
        else
          {
            /* This rule has an empty RHS. */

-           assert (ritem[rules[ruleno].rhs] == -ruleno);
-           if (rules[ruleno].useful && !nullable[rules[ruleno].lhs])
+           if (item_number_as_rule_number (rules_ruleno->rhs[0]) != ruleno)
+             abort ();
+           if (rules_ruleno->useful
+               && ! nullable[rules_ruleno->lhs->number - ntokens])

              {
              {

-               nullable[rules[ruleno].lhs] = 1;
-               *s2++ = rules[ruleno].lhs;
+               nullable[rules_ruleno->lhs->number - ntokens] = 1;
+               *s2++ = rules_ruleno->lhs->number;

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

-    for (p = rsets[*s1++]; p; p = p->next)
+    for (p = rsets[*s1++ - ntokens]; p; p = p->next)

       {
       {

-       ruleno = p->value;
-       if (--rcount[ruleno] == 0)
-         if (rules[ruleno].useful && !nullable[rules[ruleno].lhs])
+       rule *r = p->value;
+       if (--rcount[r->number] == 0)
+         if (r->useful && ! nullable[r->lhs->number - ntokens])

            {
            {

-             nullable[rules[ruleno].lhs] = 1;
-             *s2++ = rules[ruleno].lhs;
+             nullable[r->lhs->number - ntokens] = 1;
+             *s2++ = r->lhs->number;

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

-  XFREE (rsets + ntokens);
+  XFREE (rsets);

   XFREE (relts);
 
   XFREE (relts);
 

-  if (trace_flag)
+  if (trace_flag & trace_sets)

     nullable_print (stderr);
 }
 
 
 void
     nullable_print (stderr);
 }
 
 
 void

-free_nullable (void)
+nullable_free (void)

 {
 {

-  XFREE (nullable + ntokens);
+  XFREE (nullable);

 }
 }