Instead of mapping the LHS of unused rules to -1, keep the LHS

valid, but flag the rules as invalid.
* src/gram.h (rule_t): `useful' is a new member.
* src/print.c (print_grammar): Adjust.
* src/derives.c (set_derives): Likewise.
* src/reader.c (packgram, reduce_output): Likewise.
* src/reduce.c (reduce_grammar_tables): Likewise.
* tests/reduce.at (Underivable Rules, Useless Rules): New.

diff --git a/ChangeLog b/ChangeLog
index bfc68eddac3e41809869d006ec3dae162be38cb3..ef134526d79a5bd31efb257961a1fbedd545e98d 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,15 @@
+2001-11-30  Akim Demaille  <akim@epita.fr>
+
+       Instead of mapping the LHS of unused rules to -1, keep the LHS
+       valid, but flag the rules as invalid.
+
+       * src/gram.h (rule_t): `useful' is a new member.
+       * src/print.c (print_grammar): Adjust.
+       * src/derives.c (set_derives): Likewise.
+       * src/reader.c (packgram, reduce_output): Likewise.
+       * src/reduce.c (reduce_grammar_tables): Likewise.
+       * tests/reduce.at (Underivable Rules, Useless Rules): New.
+
 2001-11-30  Akim Demaille  <akim@epita.fr>
 
        * src/reduce.c (reduce_output): Formatting changes.

diff --git a/src/derives.c b/src/derives.c
index f0c41165a8bca1eadae1775612cf7892238dce8a..45fecffe7c5f190b44831f085e387fe1c6726ad9 100644 (file)
--- a/src/derives.c
+++ b/src/derives.c
@@ -63,7 +63,6 @@ void
 set_derives (void)
 {
   int i;
-  int lhs;
   shorts *p;
   short *q;
   shorts **dset;
@@ -74,16 +73,14 @@ set_derives (void)
 
   p = delts;
   for (i = nrules; i > 0; i--)
-    {
-      lhs = rule_table[i].lhs;
-      if (lhs >= 0)
-       {
-         p->next = dset[lhs];
-         p->value = i;
-         dset[lhs] = p;
-         p++;
-       }
-    }
+    if (rule_table[i].useful)
+      {
+       int lhs = rule_table[i].lhs;
+       p->next = dset[lhs];
+       p->value = i;
+       dset[lhs] = p;
+       p++;
+      }
 
   derives = XCALLOC (short *, nvars) - ntokens;
   q = XCALLOC (short, nvars + nrules);

diff --git a/src/gram.h b/src/gram.h
index 531d1d9aa3a1ea72f2dcfb0089dfaff143be0c5e..ca55d007b55ed79062969415f4b054469c0c673c 100644 (file)
--- a/src/gram.h
+++ b/src/gram.h
@@ -59,6 +59,8 @@
 
    RULE_TABLE[R].line -- the line where R was defined.
 
+   RULE_TABLE[R].useful -- TRUE iff the rule is used.
+
    The right hand side is stored as symbol numbers in a portion of
    RITEM.
 
@@ -119,6 +121,7 @@ typedef struct rule_s
   short precsym;
   short assoc;
   short line;
+  bool useful;
 } rule_t;
 
 extern struct rule_s *rule_table;

diff --git a/src/print.c b/src/print.c
index 977be596d836699711d3053ba788234b5bd22f4c..9ac1feb3b34c5e8bf365a46262696d3a9bd33357 100644 (file)
--- a/src/print.c
+++ b/src/print.c
@@ -216,7 +216,7 @@ print_grammar (FILE *out)
   fprintf (out, "  %s\n", _("Number, Line, Rule"));
   for (i = 1; i <= nrules; i++)
     /* Don't print rules disabled in reduce_grammar_tables.  */
-    if (rule_table[i].lhs >= 0)
+    if (rule_table[i].useful)
       {
        fprintf (out, _("  %3d %3d %s ->"),
                 i, rule_table[i].line, tags[rule_table[i].lhs]);

diff --git a/src/reader.c b/src/reader.c
index 8e7d99494a9d1a5bdb54689669e13eb4bdb77ab7..0cce616d937e495829fdd7cc0dbb5ce1ad069b6d 100644 (file)
--- a/src/reader.c
+++ b/src/reader.c
@@ -1971,6 +1971,7 @@ packgram (void)
       rule_table[ruleno].lhs = p->sym->value;
       rule_table[ruleno].rhs = itemno;
       rule_table[ruleno].line = p->line;
+      rule_table[ruleno].useful = TRUE;
 
       p = p->next;
       while (p && p->sym)

diff --git a/src/reduce.c b/src/reduce.c
index 626c195c0432c67d433443b616e763258cab1844..190f357746a43f9165e380302ab82efb89ae395c 100644 (file)
--- a/src/reduce.c
+++ b/src/reduce.c
@@ -310,20 +310,12 @@ reduce_grammar_tables (void)
 
     }
 #endif /* 0 */
-  /* Disable useless productions,
-     since they may contain useless nonterms
-     that would get mapped below to -1 and confuse everyone.  */
+  /* Disable useless productions. */
   if (nuseless_productions > 0)
     {
       int pn;
-
       for (pn = 1; pn <= nrules; pn++)
-       {
-         if (!BITISSET (P, pn))
-           {
-             rule_table[pn].lhs = -1;
-           }
-       }
+       rule_table[pn].useful = BITISSET (P, pn);
     }
 }
 
@@ -338,8 +330,8 @@ nonterminals_reduce (void)
   int i, n;
   rule r;
 
-  /* Create a map of nonterminal number to new nonterminal number. -1
-     in the map means it was useless and is being eliminated.  */
+  /* Map the nonterminals to their new index: useful first, useless
+     afterwards.  Kept for later report.  */
 
   short *nontermmap = XCALLOC (short, nvars) - ntokens;
   n = ntokens;
@@ -379,9 +371,7 @@ nonterminals_reduce (void)
 
   for (i = 1; i <= nrules; i++)
     {
-      /* Ignore the rules disabled above.  */
-      if (rule_table[i].lhs >= 0)
-       rule_table[i].lhs = nontermmap[rule_table[i].lhs];
+      rule_table[i].lhs = nontermmap[rule_table[i].lhs];
       if (ISVAR (rule_table[i].precsym))
        /* Can this happen?  */
        rule_table[i].precsym = nontermmap[rule_table[i].precsym];
@@ -396,7 +386,7 @@ nonterminals_reduce (void)
   nsyms -= nuseless_nonterminals;
   nvars -= nuseless_nonterminals;
 
-  free (&nontermmap[ntokens]);
+  free (nontermmap + ntokens);
 }
 
 
@@ -436,11 +426,11 @@ reduce_output (FILE *out)
       int i;
       fprintf (out, "%s\n\n", _("Useless rules:"));
       for (i = 1; i <= nrules; i++)
-       if (!BITISSET (P, i))
+       if (!rule_table[i].useful)
          {
            rule r;
            fprintf (out, "#%-4d  ", i);
-           fprintf (out, "%s :\t", tags[rule_table[i].lhs]);
+           fprintf (out, "%s:", tags[rule_table[i].lhs]);
            for (r = &ritem[rule_table[i].rhs]; *r >= 0; r++)
              fprintf (out, " %s", tags[*r]);
            fputs (";\n", out);

diff --git a/tests/reduce.at b/tests/reduce.at
index 73856df91cffb323624eec4c34f57cd071651c73..f38758228315853d5edb7249e7ea80635655c8ac 100644 (file)
--- a/tests/reduce.at
+++ b/tests/reduce.at
@@ -108,3 +108,101 @@ AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
 ]])
 
 AT_CLEANUP
+
+
+
+## --------------- ##
+## Useless Rules.  ##
+## --------------- ##
+
+AT_SETUP([Useless Rules])
+
+AT_DATA([[input.y]],
+[[%verbose
+%output="input.c"
+%token useful
+%%
+exp: useful;
+useless1: '1';
+useless2: '2';
+useless3: '3';
+useless4: '4';
+useless5: '5';
+useless6: '6';
+useless7: '7';
+useless8: '8';
+useless9: '9';
+]])
+
+AT_CHECK([[bison input.y]], 0, [],
+[[input.y contains 9 useless nonterminals and 9 useless rules
+]])
+
+AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
+[[Useless nonterminals:
+   useless1
+   useless2
+   useless3
+   useless4
+   useless5
+   useless6
+   useless7
+   useless8
+   useless9
+Terminals which are not used:
+   '1'
+   '2'
+   '3'
+   '4'
+   '5'
+   '6'
+   '7'
+   '8'
+   '9'
+Useless rules:
+#2     useless1: '1';
+#3     useless2: '2';
+#4     useless3: '3';
+#5     useless4: '4';
+#6     useless5: '5';
+#7     useless6: '6';
+#8     useless7: '7';
+#9     useless8: '8';
+#10    useless9: '9';
+]])
+
+AT_CLEANUP
+
+
+
+## ------------------- ##
+## Underivable Rules.  ##
+## ------------------- ##
+
+AT_SETUP([Underivable Rules])
+
+AT_DATA([[input.y]],
+[[%verbose
+%output="input.c"
+%token useful
+%%
+exp: useful | underivable;
+underivable: indirection;
+indirection: underivable;
+]])
+
+AT_CHECK([[bison input.y]], 0, [],
+[[input.y contains 2 useless nonterminals and 3 useless rules
+]])
+
+AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
+[[Useless nonterminals:
+   underivable
+   indirection
+Useless rules:
+#2     exp: underivable;
+#3     underivable: indirection;
+#4     indirection: underivable;
+]])
+
+AT_CLEANUP