Point to an official beta.

[bison.git] / src / reduce.c

diff --git a/src/reduce.c b/src/reduce.c
index bef2ae90307d279f78161917446f4ebca66482b6..61ad2b2e0657046058ae292827697f888a28ad96 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"


@@ -36,9 +37,6 @@
 #include "getargs.h"
 #include "bitset.h"
 
 #include "getargs.h"
 #include "bitset.h"
 

-typedef short *rule;
-
-

 /* Set of all nonterminals which are not useless.  */
 static bitset N;
 
 /* Set of all nonterminals which are not useless.  */
 static bitset N;
 


@@ -53,7 +51,7 @@ static bitset V;
 static bitset V1;
 
 static int nuseful_productions;
 static bitset V1;
 
 static int nuseful_productions;

-static int nuseless_productions;
+int nuseless_productions;

 static int nuseful_nonterminals;
 int nuseless_nonterminals;
 \f
 static int nuseful_nonterminals;
 int nuseless_nonterminals;
 \f


@@ -66,13 +64,13 @@ int nuseless_nonterminals;
 static bool
 useful_production (int i, bitset N0)
 {
 static bool
 useful_production (int i, bitset N0)
 {

-  rule r;
+  item_number_t *r;

   short n;
 
   /* A production is useful if all of the nonterminals in its appear
      in the set of useful nonterminals.  */
 
   short n;
 
   /* 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++)
+  for (r = rules[i].rhs; *r >= 0; r++)

     if (ISVAR (n = *r) && !bitset_test (N0, n - ntokens))
       return FALSE;
   return TRUE;
     if (ISVAR (n = *r) && !bitset_test (N0, n - ntokens))
       return FALSE;
   return TRUE;


@@ -114,11 +112,11 @@ useless_nonterminals (void)
   while (1)
     {
       bitset_copy (Np, N);
   while (1)
     {
       bitset_copy (Np, N);

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

        if (!bitset_test (P, i)
            && useful_production (i, N))
          {
        if (!bitset_test (P, i)
            && useful_production (i, N))
          {

-           bitset_set (Np, rules[i].lhs - ntokens);
+           bitset_set (Np, rules[i].lhs->number - ntokens);

            bitset_set (P, i);
          }
       if (bitset_equal_p (N, Np))
            bitset_set (P, i);
          }
       if (bitset_equal_p (N, Np))


@@ -138,7 +136,7 @@ inaccessable_symbols (void)
   bitset Vp, Vs, Pp;
   int i;
   short t;
   bitset Vp, Vs, Pp;
   int i;
   short t;

-  rule r;
+  item_number_t *r;

 
   /* Find out which productions are reachable and which symbols are
      used.  Starting with an empty set of productions and a set of
 
   /* Find out which productions are reachable and which symbols are
      used.  Starting with an empty set of productions and a set of


@@ -174,13 +172,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);


@@ -198,9 +196,9 @@ inaccessable_symbols (void)
   V = Vp;
 
   /* Tokens 0, 1, and 2 are internal to Bison.  Consider them useful. */
   V = Vp;
 
   /* Tokens 0, 1, and 2 are internal to Bison.  Consider them useful. */

-  bitset_set (V, 0);           /* end-of-input token */
-  bitset_set (V, 1);           /* error token */
-  bitset_set (V, 2);           /* some undefined token */
+  bitset_set (V, eoftoken->number);            /* end-of-input token */
+  bitset_set (V, errtoken->number);            /* error token */
+  bitset_set (V, undeftoken->number);          /* some undefined token */

 
   bitset_free (P);
   P = Pp;
 
   bitset_free (P);
   P = Pp;


@@ -215,75 +213,61 @@ 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.  */
+       item_number_t *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;
+      }
+  }

 }
 
 
 }
 
 


@@ -294,12 +278,12 @@ reduce_grammar_tables (void)
 static void
 nonterminals_reduce (void)
 {
 static void
 nonterminals_reduce (void)
 {

-  int i, n;
+  token_number_t i, n;

 
   /* Map the nonterminals to their new index: useful first, useless
      afterwards.  Kept for later report.  */
 
 
   /* Map the nonterminals to their new index: useful first, useless
      afterwards.  Kept for later report.  */
 

-  short *nontermmap = XCALLOC (short, nvars) - ntokens;
+  token_number_t *nontermmap = XCALLOC (token_number_t, nvars) - ntokens;

   n = ntokens;
   for (i = ntokens; i < nsyms; i++)
     if (bitset_test (V, i))
   n = ntokens;
   for (i = ntokens; i < nsyms; i++)
     if (bitset_test (V, i))


@@ -311,8 +295,10 @@ nonterminals_reduce (void)
 
   /* Shuffle elements of tables indexed by symbol number.  */
   {
 
   /* Shuffle elements of tables indexed by symbol number.  */
   {

-    bucket **symbols_sorted = XMALLOC (bucket *, nvars) - ntokens;
+    symbol_t **symbols_sorted = XMALLOC (symbol_t *, 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++)


@@ -320,19 +306,9 @@ 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]))
   for (i = 0; i < nritems; ++i)
     if (ISVAR (ritem[i]))

-      ritem[i] = nontermmap[ritem[i]];
+      ritem[i] = token_number_as_item_number (nontermmap[ritem[i]]);

 
   start_symbol = nontermmap[start_symbol];
 
 
   start_symbol = nontermmap[start_symbol];
 


@@ -355,7 +331,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);
     }
 


@@ -368,7 +345,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);


@@ -378,66 +356,22 @@ 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++)
+       {
+         item_number_t *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);
     }
 }
 \f
       fputs ("\n\n", out);
     }
 }
 \f

-static void
-dump_grammar (FILE *out)
-{
-  int i;
-  rule r;
-
-  fprintf (out, "REDUCED GRAMMAR\n\n");
-  fprintf (out,
-          "ntokens = %d, nvars = %d, nsyms = %d, nrules = %d, nitems = %d\n\n",
-          ntokens, nvars, nsyms, nrules, nitems);
-  fprintf (out, "Variables\n---------\n\n");
-  fprintf (out, "Value  Sprec  Sassoc  Tag\n");
-  for (i = ntokens; i < nsyms; i++)
-    fprintf (out, "%5d  %5d   %5d  %s\n",
-            i,
-            symbols[i]->prec, symbols[i]->assoc, 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");
-  for (i = 1; i <= nrules; i++)
-    {
-      int rhs_count = 0;
-      /* Find the last RHS index in ritems. */
-      for (r = &ritem[rules[i].rhs]; *r >= 0; ++r)
-       ++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);
-      /* Dumped the RHS. */
-      for (r = &ritem[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");
-  for (i = 1; i <= nrules; 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);
-      fputc ('\n', out);
-    }
-  fprintf (out, "\n\n");
-}
+

 
 
 
 
 
 


@@ -490,7 +424,6 @@ reduce_grammar (void)
   inaccessable_symbols ();
 
   reduced = (bool) (nuseless_nonterminals + nuseless_productions > 0);
   inaccessable_symbols ();
 
   reduced = (bool) (nuseless_nonterminals + nuseless_productions > 0);

-

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


@@ -498,15 +431,19 @@ 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 ();
+  /* First reduce the nonterminals, as they renumber themselves in the
+     whole grammar.  If you change the order, nonterms would be
+     renumbered only in the reduced grammar.  */

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

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

 
   if (trace_flag)
     {
 
   if (trace_flag)
     {

-      dump_grammar (stderr);
+      grammar_dump (stderr, "Reduced Grammar");

 
       fprintf (stderr, "reduced %s defines %d terminals, %d nonterminals\
 , and %d productions.\n",
 
       fprintf (stderr, "reduced %s defines %d terminals, %d nonterminals\
 , and %d productions.\n",