04-fyi-unused-rules.patch

[Akim Demaille]

Index: ChangeLog
from  Akim Demaille  <address@hidden>
        
        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.
        
Index: src/derives.c
--- src/derives.c Sun, 18 Nov 2001 13:46:49 +0100 akim
+++ src/derives.c Thu, 29 Nov 2001 23:33:54 +0100 akim
@@ -63,7 +63,6 @@
 set_derives (void)
 {
   int i;
-  int lhs;
   shorts *p;
   short *q;
   shorts **dset;
@@ -74,16 +73,14 @@
 
   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);
Index: src/gram.h
--- src/gram.h Fri, 16 Nov 2001 01:37:30 +0100 akim
+++ src/gram.h Thu, 29 Nov 2001 23:33:43 +0100 akim
@@ -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 @@
   short precsym;
   short assoc;
   short line;
+  bool useful;
 } rule_t;
 
 extern struct rule_s *rule_table;
Index: src/print.c
--- src/print.c Thu, 29 Nov 2001 23:08:07 +0100 akim
+++ src/print.c Thu, 29 Nov 2001 23:32:37 +0100 akim
@@ -216,7 +216,7 @@
   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]);
Index: src/reader.c
--- src/reader.c Thu, 29 Nov 2001 21:52:19 +0100 akim
+++ src/reader.c Thu, 29 Nov 2001 23:54:47 +0100 akim
@@ -1877,6 +1877,7 @@
       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)
Index: src/reduce.c
--- src/reduce.c Thu, 29 Nov 2001 23:08:07 +0100 akim
+++ src/reduce.c Thu, 29 Nov 2001 23:58:24 +0100 akim
@@ -310,20 +310,12 @@
 
     }
 #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 @@
   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 @@
 
   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 @@
   nsyms -= nuseless_nonterminals;
   nvars -= nuseless_nonterminals;
 
-  free (&nontermmap[ntokens]);
+  free (nontermmap + ntokens);
 }
 
 
@@ -436,11 +426,11 @@
       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);
Index: tests/reduce.at
--- tests/reduce.at Thu, 29 Nov 2001 22:49:28 +0100 akim
+++ tests/reduce.at Thu, 29 Nov 2001 23:59:53 +0100 akim
@@ -106,3 +106,101 @@ exp: useful;
 ]])
 
 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