* src/gram.h (rule_s): prec and precsym are now pointers

[bison.git] / src / reduce.c

diff --git a/src/reduce.c b/src/reduce.c
index 05d15d23297c198ac3f98ffdb7e1d4b7ba737e2e..23ad38bc3364f02599a07f5c0f65ad3feecc98c4 100644 (file)
--- a/src/reduce.c
+++ b/src/reduce.c
@@ -1,5 +1,5 @@
 /* Grammar reduction for Bison.
 /* Grammar reduction for Bison.

-   Copyright 1988, 1989, 2000, 2001  Free Software Foundation, Inc.
+   Copyright (C) 1988, 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.
 


@@ -26,6 +26,7 @@
    user's parser.  */
 
 #include "system.h"
    user's parser.  */
 
 #include "system.h"

+#include "quotearg.h"

 #include "getargs.h"
 #include "files.h"
 #include "symtab.h"
 #include "getargs.h"
 #include "files.h"
 #include "symtab.h"


@@ -57,15 +58,6 @@ static int nuseless_productions;
 static int nuseful_nonterminals;
 int nuseless_nonterminals;
 \f
 static int nuseful_nonterminals;
 int nuseless_nonterminals;
 \f

-static int
-bits_size (bitset S)
-{
-  int i, count = 0;
-
-  BITSET_EXECUTE (S, 0, i, { ++count; });
-  return count;
-}
-\f

 /*-------------------------------------------------------------------.
 | Another way to do this would be with a set for each production and |
 | then do subset tests against N0, but even for the C grammar the    |
 /*-------------------------------------------------------------------.
 | Another way to do this would be with a set for each production and |
 | then do subset tests against N0, but even for the C grammar the    |


@@ -81,10 +73,9 @@ useful_production (int i, bitset N0)
   /* A production is useful if all of the nonterminals in its appear
      in the set of useful nonterminals.  */
 
   /* A production is useful if all of the nonterminals in its appear
      in the set of useful nonterminals.  */
 

-  for (r = &ritem[rules[i].rhs]; *r >= 0; r++)
-    if (ISVAR (n = *r))
-      if (!bitset_test (N0, n - ntokens))
-       return FALSE;
+  for (r = rules[i].rhs; *r >= 0; r++)
+    if (ISVAR (n = *r) && !bitset_test (N0, n - ntokens))
+      return FALSE;

   return TRUE;
 }
 
   return TRUE;
 }
 


@@ -103,7 +94,6 @@ useless_nonterminals (void)
      set of all productions which have a RHS all in N.  */
 
   Np = bitset_create (nvars, BITSET_FIXED);
      set of all productions which have a RHS all in N.  */
 
   Np = bitset_create (nvars, BITSET_FIXED);

-  bitset_zero (Np);

 
 
   /* The set being computed is a set of nonterminals which can derive
 
 
   /* The set being computed is a set of nonterminals which can derive


@@ -125,17 +115,13 @@ useless_nonterminals (void)
   while (1)
     {
       bitset_copy (Np, N);
   while (1)
     {
       bitset_copy (Np, N);

-      for (i = 1; i <= nrules; i++)
-       {
-         if (!bitset_test (P, i))
-           {
-             if (useful_production (i, N))
-               {
-                 bitset_set (Np, rules[i].lhs - ntokens);
-                 bitset_set (P, i);
-               }
-           }
-       }
+      for (i = 1; i < nrules + 1; i++)
+       if (!bitset_test (P, i)
+           && useful_production (i, N))
+         {
+           bitset_set (Np, rules[i].lhs->number - ntokens);
+           bitset_set (P, i);
+         }

       if (bitset_equal_p (N, Np))
        break;
       Ns = Np;
       if (bitset_equal_p (N, Np))
        break;
       Ns = Np;


@@ -179,9 +165,7 @@ inaccessable_symbols (void)
      user can know.  */
 
   Vp = bitset_create (nsyms, BITSET_FIXED);
      user can know.  */
 
   Vp = bitset_create (nsyms, BITSET_FIXED);

-  bitset_zero (Vp);

   Pp = bitset_create (nrules + 1, BITSET_FIXED);
   Pp = bitset_create (nrules + 1, BITSET_FIXED);

-  bitset_zero (Pp);

 
   /* If the start symbol isn't useful, then nothing will be useful. */
   if (bitset_test (N, start_symbol - ntokens))
 
   /* If the start symbol isn't useful, then nothing will be useful. */
   if (bitset_test (N, start_symbol - ntokens))


@@ -191,13 +175,13 @@ inaccessable_symbols (void)
       while (1)
        {
          bitset_copy (Vp, V);
       while (1)
        {
          bitset_copy (Vp, V);

-         for (i = 1; i <= nrules; i++)
+         for (i = 1; i < nrules + 1; i++)

            {
              if (!bitset_test (Pp, i)
                  && bitset_test (P, i)
            {
              if (!bitset_test (Pp, i)
                  && bitset_test (P, i)

-                 && bitset_test (V, rules[i].lhs))
+                 && bitset_test (V, rules[i].lhs->number))

                {
                {

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

                    if (ISTOKEN (t = *r) || bitset_test (N, t - ntokens))
                      bitset_set (Vp, t);
                  bitset_set (Pp, i);
                    if (ISTOKEN (t = *r) || bitset_test (N, t - ntokens))
                      bitset_set (Vp, t);
                  bitset_set (Pp, i);


@@ -222,7 +206,7 @@ inaccessable_symbols (void)
   bitset_free (P);
   P = Pp;
 
   bitset_free (P);
   P = Pp;
 

-  nuseful_productions = bits_size (P);
+  nuseful_productions = bitset_count (P);

   nuseless_productions = nrules - nuseful_productions;
 
   nuseful_nonterminals = 0;
   nuseless_productions = nrules - nuseful_productions;
 
   nuseful_nonterminals = 0;


@@ -232,75 +216,62 @@ inaccessable_symbols (void)
   nuseless_nonterminals = nvars - nuseful_nonterminals;
 
   /* A token that was used in %prec should not be warned about.  */
   nuseless_nonterminals = nvars - nuseful_nonterminals;
 
   /* A token that was used in %prec should not be warned about.  */

-  for (i = 1; i < nrules; i++)
+  for (i = 1; i < nrules + 1; i++)

     if (rules[i].precsym != 0)
     if (rules[i].precsym != 0)

-      bitset_set (V1, rules[i].precsym);
+      bitset_set (V1, rules[i].precsym->number);

 }
 
 }
 

+
+/*-------------------------------------------------------------------.
+| Put the useless productions at the end of RULES, and adjust NRULES |
+| accordingly.                                                       |
+`-------------------------------------------------------------------*/
+

 static void
 reduce_grammar_tables (void)
 {
 static void
 reduce_grammar_tables (void)
 {

-  /* This is turned off because we would need to change the numbers in
-     the case statements in the actions file.
-
-     We don't disable it via CPP so that it is still checked with the
-     rest of the code, to avoid its becoming completely obsolete.
+  /* Flag useless productions.  */
+  {
+    int pn;
+    for (pn = 1; pn < nrules + 1; pn++)
+      rules[pn].useful = bitset_test (P, pn);
+  }

 
 

-     FIXME: I think the comment above demonstrates this code must be
-     turned off for *semantic* parser, not in the general case.  Try
-     to understand this better --akim.  */
+  /* Map the nonterminals to their new index: useful first, useless
+     afterwards.  Kept for later report.  */
+  {
+    int useful = 1;
+    int useless = nrules + 1 - nuseless_productions;
+    rule_t *rules_sorted = XMALLOC (rule_t, nrules + 1) - 1;
+    int i;
+    for (i = 1; i < nrules + 1; ++i)
+      rules_sorted[rules[i].useful ? useful++ : useless++] = rules[i];
+    free (rules + 1);
+    rules = rules_sorted;

 
 

-  if (0)
-    /* remove useless productions */
-    if (nuseless_productions > 0)
+    /* Renumber the rules markers in RITEMS.  */
+    for (i = 1; i < nrules + 1; ++i)

       {
       {

-       short np, pn, ni, pi;
-
-       np = 0;
-       ni = 0;
-       for (pn = 1; pn <= nrules; pn++)
-         if (bitset_test (P, pn))
-           {
-             np++;
-             if (pn != np)
-               {
-                 rules[np].lhs   = rules[pn].lhs;
-                 rules[np].line  = rules[pn].line;
-                 rules[np].prec  = rules[pn].prec;
-                 rules[np].assoc = rules[pn].assoc;
-                 rules[np].rhs   = rules[pn].rhs;
-                 if (rules[np].rhs != ni)
-                   {
-                     pi = rules[np].rhs;
-                     rules[np].rhs = ni;
-                     while (ritem[pi] >= 0)
-                       ritem[ni++] = ritem[pi++];
-                     ritem[ni++] = -np;
-                   }
-               }
-             else
-               {
-                 while (ritem[ni++] >= 0)
-                   /* Nothing. */;
-               }
-           }
-
-       ritem[ni] = 0;
-       nrules -= nuseless_productions;
-       nitems = ni;
-       nritems = ni;
-
-       /* Is it worth it to reduce the amount of memory for the
-          grammar? Probably not.  */
+       short *rhsp = rules[i].rhs;
+       for (/* Nothing. */; *rhsp >= 0; ++rhsp)
+         /* Nothing. */;
+       *rhsp = -i;
+       rules[i].number = i;

       }
       }

+    nrules -= nuseless_productions;
+  }

 
 

-  /* Disable useless productions. */
-  if (nuseless_productions > 0)
-    {
-      int pn;
-      for (pn = 1; pn <= nrules; pn++)
-       rules[pn].useful = bitset_test (P, pn);
-    }
+  /* Adjust NRITEMS and NITEMS.  */
+  {
+    int r;
+    int length;
+    for (r = nrules + 1; r < nrules + 1 + nuseless_productions; ++r)
+      {
+       length = rule_rhs_length (&rules[r]);
+       nritems -= length + 1;
+       nitems -= length + 1;
+      }
+  }

 }
 
 
 }
 
 


@@ -330,6 +301,8 @@ nonterminals_reduce (void)
   {
     bucket **symbols_sorted = XMALLOC (bucket *, nvars) - ntokens;
 
   {
     bucket **symbols_sorted = XMALLOC (bucket *, nvars) - ntokens;
 

+    for (i = ntokens; i < nsyms; i++)
+      symbols[i]->number = nontermmap[i];

     for (i = ntokens; i < nsyms; i++)
       symbols_sorted[nontermmap[i]] = symbols[i];
     for (i = ntokens; i < nsyms; i++)
     for (i = ntokens; i < nsyms; i++)
       symbols_sorted[nontermmap[i]] = symbols[i];
     for (i = ntokens; i < nsyms; i++)


@@ -337,16 +310,6 @@ nonterminals_reduce (void)
     free (symbols_sorted + ntokens);
   }
 
     free (symbols_sorted + ntokens);
   }
 

-  /* Replace all symbol numbers in valid data structures.  */
-
-  for (i = 1; i <= nrules; i++)
-    {
-      rules[i].lhs = nontermmap[rules[i].lhs];
-      if (ISVAR (rules[i].precsym))
-       /* Can this happen?  */
-       rules[i].precsym = nontermmap[rules[i].precsym];
-    }
-

   for (i = 0; i < nritems; ++i)
     if (ISVAR (ritem[i]))
       ritem[i] = nontermmap[ritem[i]];
   for (i = 0; i < nritems; ++i)
     if (ISVAR (ritem[i]))
       ritem[i] = nontermmap[ritem[i]];


@@ -372,7 +335,8 @@ reduce_output (FILE *out)
       int i;
       fprintf (out, "%s\n\n", _("Useless nonterminals:"));
       for (i = 0; i < nuseless_nonterminals; ++i)
       int i;
       fprintf (out, "%s\n\n", _("Useless nonterminals:"));
       for (i = 0; i < nuseless_nonterminals; ++i)

-       fprintf (out, "   %s\n", symbols[nsyms + i]->tag);
+       fprintf (out, "   %s\n", quotearg_style (escape_quoting_style,
+                                                symbols[nsyms + i]->tag));

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


@@ -385,7 +349,8 @@ reduce_output (FILE *out)
          if (!b)
            fprintf (out, "%s\n\n", _("Terminals which are not used:"));
          b = TRUE;
          if (!b)
            fprintf (out, "%s\n\n", _("Terminals which are not used:"));
          b = TRUE;

-         fprintf (out, "   %s\n", symbols[i]->tag);
+         fprintf (out, "   %s\n", quotearg_style (escape_quoting_style,
+                                                  symbols[i]->tag));

        }
     if (b)
       fputs ("\n\n", out);
        }
     if (b)
       fputs ("\n\n", out);


@@ -395,16 +360,17 @@ reduce_output (FILE *out)
     {
       int i;
       fprintf (out, "%s\n\n", _("Useless rules:"));
     {
       int i;
       fprintf (out, "%s\n\n", _("Useless rules:"));

-      for (i = 1; i <= nrules; i++)
-       if (!rules[i].useful)
-         {
-           rule r;
-           fprintf (out, "#%-4d  ", i - 1);
-           fprintf (out, "%s:", symbols[rules[i].lhs]->tag);
-           for (r = &ritem[rules[i].rhs]; *r >= 0; r++)
-             fprintf (out, " %s", symbols[*r]->tag);
-           fputs (";\n", out);
-         }
+      for (i = nrules + 1; i < nuseless_productions + nrules + 1; i++)
+       {
+         rule r;
+         fprintf (out, "#%-4d  ", rules[i].user_number - 1);
+         fprintf (out, "%s:", quotearg_style (escape_quoting_style,
+                                              rules[i].lhs->tag));
+         for (r = rules[i].rhs; *r >= 0; r++)
+           fprintf (out, " %s", quotearg_style (escape_quoting_style,
+                                                symbols[*r]->tag));
+         fputs (";\n", out);
+       }

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


@@ -424,33 +390,39 @@ dump_grammar (FILE *out)
   for (i = ntokens; i < nsyms; i++)
     fprintf (out, "%5d  %5d   %5d  %s\n",
             i,
   for (i = ntokens; i < nsyms; i++)
     fprintf (out, "%5d  %5d   %5d  %s\n",
             i,

-            symbols[i]->prec, symbols[i]->assoc, symbols[i]->tag);
+            symbols[i]->prec, symbols[i]->assoc,
+            quotearg_style (escape_quoting_style, symbols[i]->tag));

   fprintf (out, "\n\n");
   fprintf (out, "Rules\n-----\n\n");
   fprintf (out, "Num (Prec, Assoc, Useful, Ritem Range) Lhs -> Rhs (Ritem range) [Num]\n");
   fprintf (out, "\n\n");
   fprintf (out, "Rules\n-----\n\n");
   fprintf (out, "Num (Prec, Assoc, Useful, Ritem Range) Lhs -> Rhs (Ritem range) [Num]\n");

-  for (i = 1; i <= nrules; i++)
+  for (i = 1; i < nrules + nuseless_productions + 1; i++)

     {
       int rhs_count = 0;
       /* Find the last RHS index in ritems. */
     {
       int rhs_count = 0;
       /* Find the last RHS index in ritems. */

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

        ++rhs_count;
       fprintf (out, "%3d (%2d, %2d, %2d, %2d-%2d)   %2d ->",
               i - 1,
        ++rhs_count;
       fprintf (out, "%3d (%2d, %2d, %2d, %2d-%2d)   %2d ->",
               i - 1,

-              rules[i].prec, rules[i].assoc, rules[i].useful,
-              rules[i].rhs, rules[i].rhs + rhs_count - 1,
-              rules[i].lhs);
+              rules[i].prec->prec,
+              rules[i].prec->assoc,
+              rules[i].useful,
+              rules[i].rhs - ritem,
+              rules[i].rhs - ritem + rhs_count - 1,
+              rules[i].lhs->number);

       /* Dumped the RHS. */
       /* Dumped the RHS. */

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

        fprintf (out, "%3d", *r);
       fprintf (out, "  [%d]\n", -(*r) - 1);
     }
   fprintf (out, "\n\n");
   fprintf (out, "Rules interpreted\n-----------------\n\n");
        fprintf (out, "%3d", *r);
       fprintf (out, "  [%d]\n", -(*r) - 1);
     }
   fprintf (out, "\n\n");
   fprintf (out, "Rules interpreted\n-----------------\n\n");

-  for (i = 1; i <= nrules; i++)
+  for (i = 1; i < nrules + nuseless_productions + 1; i++)

     {
     {

-      fprintf (out, "%-5d  %s :", i, symbols[rules[i].lhs]->tag);
-      for (r = &ritem[rules[i].rhs]; *r >= 0; r++)
-       fprintf (out, " %s", symbols[*r]->tag);
+      fprintf (out, "%-5d  %s :",
+              i, quotearg_style (escape_quoting_style, rules[i].lhs->tag));
+      for (r = rules[i].rhs; *r >= 0; r++)
+       fprintf (out, " %s",
+                quotearg_style (escape_quoting_style, symbols[*r]->tag));

       fputc ('\n', out);
     }
   fprintf (out, "\n\n");
       fputc ('\n', out);
     }
   fprintf (out, "\n\n");


@@ -499,19 +471,14 @@ reduce_grammar (void)
   /* Allocate the global sets used to compute the reduced grammar */
 
   N = bitset_create (nvars, BITSET_FIXED);
   /* Allocate the global sets used to compute the reduced grammar */
 
   N = bitset_create (nvars, BITSET_FIXED);

-  bitset_zero (N);

   P =  bitset_create (nrules + 1, BITSET_FIXED);
   P =  bitset_create (nrules + 1, BITSET_FIXED);

-  bitset_zero (P);

   V = bitset_create (nsyms, BITSET_FIXED);
   V = bitset_create (nsyms, BITSET_FIXED);

-  bitset_zero (V);

   V1 = bitset_create (nsyms, BITSET_FIXED);
   V1 = bitset_create (nsyms, BITSET_FIXED);

-  bitset_zero (V1);

 
   useless_nonterminals ();
   inaccessable_symbols ();
 
   reduced = (bool) (nuseless_nonterminals + nuseless_productions > 0);
 
   useless_nonterminals ();
   inaccessable_symbols ();
 
   reduced = (bool) (nuseless_nonterminals + nuseless_productions > 0);

-

   if (!reduced)
     return;
 
   if (!reduced)
     return;
 


@@ -519,9 +486,10 @@ reduce_grammar (void)
 
   if (!bitset_test (N, start_symbol - ntokens))
     fatal (_("Start symbol %s does not derive any sentence"),
 
   if (!bitset_test (N, start_symbol - ntokens))
     fatal (_("Start symbol %s does not derive any sentence"),

-          symbols[start_symbol]->tag);
+          quotearg_style (escape_quoting_style, symbols[start_symbol]->tag));

 
 

-  reduce_grammar_tables ();
+  if (nuseless_productions > 0)
+    reduce_grammar_tables ();

   if (nuseless_nonterminals > 0)
     nonterminals_reduce ();
 
   if (nuseless_nonterminals > 0)
     nonterminals_reduce ();