05-rules-never-reduced.patch

[Akim Demaille]

Index: ChangeLog
from  Akim Demaille  <address@hidden>
        Report rules which are never reduced by the parser: those hidden
        by conflicts.
        
        * src/LR0.c (save_reductions): Don't make the final state too
        different: save its reduction (accept) instead of having a state
        without any action (no shift or goto, no reduce).
        Note: the final state is now a ``regular'' state, i.e., the
        parsers now contain `reduce 0' as default reduction.
        Nevertheless, since they decide to `accept' when yystate =
        final_state, they still will not reduce rule 0.
        * src/print.c (print_actions, print_reduction): Adjust.
        * src/output.c (action_row): Track reduced rules.
        (token_actions): Report rules never reduced.
        * tests/conflicts.at, tests/regression.at: Adjust.
        
        
Index: NEWS
--- NEWS Fri, 28 Jun 2002 21:50:19 +0200 akim
+++ NEWS Tue, 30 Jul 2002 12:22:56 +0200 akim
@@ -8,7 +8,7 @@
      %glr-parser
   causes Bison to produce a Generalized LR (GLR) parser, capable of handling
   almost any context-free grammar, ambiguous or not.  The new declarations
-  %dprec and %merge on grammar rules allow parse-time resolution of 
+  %dprec and %merge on grammar rules allow parse-time resolution of
   ambiguities.  Contributed by Paul Hilfinger.
 
 * Output Directory
@@ -57,6 +57,10 @@
 
 * Useless rules, useless nonterminals
   They are now reported, as a warning, with their locations.
+
+* Rules never reduced
+  Rules that can never be reduced because of conflicts are now
+  reported.
 
 * Incorrect `Token not used'
   On a grammar such as
Index: src/LR0.c
--- src/LR0.c Mon, 29 Jul 2002 19:31:35 +0200 akim
+++ src/LR0.c Tue, 30 Jul 2002 12:16:21 +0200 akim
@@ -282,11 +282,6 @@
   int count = 0;
   int i;
 
-  /* If this is the final state, we want it to have no reductions at
-     all, although it has one for `START_SYMBOL $end .'.  */
-  if (final_state && state->number == final_state->number)
-    return;
-
   /* Find and count the active items that represent ends of rules. */
   for (i = 0; i < nritemset; ++i)
     {
Index: src/output.c
--- src/output.c Mon, 29 Jul 2002 19:31:35 +0200 akim
+++ src/output.c Tue, 30 Jul 2002 12:01:56 +0200 akim
@@ -598,6 +598,16 @@
        }
     }
 
+  /* Find the rules which are reduced.  */
+  if (!glr_parser)
+    {
+      for (i = 0; i < ntokens; i++)
+       if (actrow[i] < 0 && actrow[i] != ACTION_MIN)
+         rules[item_number_as_rule_number (actrow[i])].useful = TRUE;
+      if (default_rule)
+       default_rule->useful = TRUE;
+    }
+
   /* If have no default rule, the default is an error.
      So replace any action which says "error" with "use default".  */
 
@@ -671,6 +681,7 @@
 token_actions (void)
 {
   state_number_t i;
+  rule_number_t r;
   int nconflict = conflicts_total_count ();
 
   rule_number_t *yydefact = XCALLOC (rule_number_t, nstates);
@@ -678,6 +689,13 @@
   actrow = XCALLOC (action_t, ntokens);
   conflrow = XCALLOC (unsigned int, ntokens);
 
+  /* Now that the parser was computed, we can find which rules are
+     really reduced, and which are not because of SR or RR conflicts.
+     */
+  if (!glr_parser)
+    for (r = 0; r < nrules; ++r)
+      rules[r].useful = FALSE;
+
   if (glr_parser)
     {
       conflict_list = XCALLOC (unsigned int, 1 + 2 * nconflict);
@@ -696,6 +714,17 @@
 
   muscle_insert_rule_number_table ("defact", yydefact,
                                   yydefact[0], 1, nstates);
+
+  if (!glr_parser)
+    for (r = 0; r < nrules ; ++r)
+      if (!rules[r].useful)
+       {
+         LOCATION_PRINT (stderr, rules[r].location);
+         fprintf (stderr, ": %s: %s: ",
+                  _("warning"), _("rule never reduced because of conflicts"));
+         rule_print (&rules[r], stderr);
+       }
+
   XFREE (actrow);
   XFREE (conflrow);
   XFREE (yydefact);
Index: src/print.c
--- src/print.c Mon, 29 Jul 2002 19:31:35 +0200 akim
+++ src/print.c Tue, 30 Jul 2002 12:17:54 +0200 akim
@@ -286,8 +286,11 @@
     fputc (' ', out);
   if (!enabled)
     fputc ('[', out);
-  fprintf (out, _("reduce using rule %d (%s)"),
-          rule->number, rule->lhs->tag);
+  if (rule->number)
+    fprintf (out, _("reduce using rule %d (%s)"),
+            rule->number, rule->lhs->tag);
+  else
+    fprintf (out, _("accept"));
   if (!enabled)
     fputc (']', out);
   fputc ('\n', out);
@@ -393,19 +396,6 @@
 static void
 print_actions (FILE *out, state_t *state)
 {
-  reductions_t *redp = state->reductions;
-  transitions_t *transitions = state->transitions;
-
-  if (transitions->num == 0 && redp->num == 0)
-    {
-      fputc ('\n', out);
-      if (state->number == final_state->number)
-       fprintf (out, _("    $default\taccept\n"));
-      else
-       fprintf (out, _("    NO ACTIONS\n"));
-      return;
-    }
-
   /* Print shifts.  */
   print_transitions (state, out, TRUE);
   print_errs (out, state);
Index: tests/conflicts.at
--- tests/conflicts.at Sun, 28 Jul 2002 16:59:35 +0200 akim
+++ tests/conflicts.at Tue, 30 Jul 2002 12:29:52 +0200 akim
@@ -37,7 +37,9 @@ exp: e 'e';
 e: 'e' | /* Nothing. */;
 ]])
 
-AT_CHECK([bison input.y -o input.c])
+AT_CHECK([bison input.y -o input.c], 0, [],
+[[input.y:4.8: warning: rule never reduced because of conflicts: e: /* empty */
+]])
 
 AT_CLEANUP
 
@@ -203,7 +205,7 @@ exp: exp OP exp | NUM;
 
     0 $accept: exp $end .
 
-    $default   accept
+    $default  accept
 
 
 state 4
@@ -306,7 +308,7 @@ exp: exp OP exp | NUM;
 
     0 $accept: exp $end .
 
-    $default   accept
+    $default  accept
 
 
 state 4
@@ -369,8 +371,9 @@ num: '0';
 ]])
 
 AT_CHECK([bison input.y -o input.c --report=all], 0, [],
-[input.y contains 1 reduce/reduce conflict.
-])
+[[input.y contains 1 reduce/reduce conflict.
+input.y:4.4-8: warning: rule never reduced because of conflicts: id: '0'
+]])
 
 # Check the contents of the report.
 AT_CHECK([cat input.output], [],
@@ -458,7 +461,7 @@ num: '0';
 
     0 $accept: exp $end .
 
-    $default   accept
+    $default  accept
 ]])
 
 AT_CLEANUP
Index: tests/regression.at
--- tests/regression.at Sun, 28 Jul 2002 16:59:35 +0200 akim
+++ tests/regression.at Tue, 30 Jul 2002 12:33:50 +0200 akim
@@ -228,7 +228,7 @@ expr:
 
     0 $accept: expr $end .
 
-    $default   accept
+    $default  accept
 
 
 state 6
@@ -456,7 +456,7 @@ exp: "a";
 
     0 $accept: CONST_DEC_PART $end .
 
-    $default   accept
+    $default  accept
 
 
 state 6
@@ -601,7 +601,7 @@ else: "else" statement;
 };
 static const unsigned char yydefact[] =
 {
-       3,     0,     0,     2,     0,     0,     0,     3,     4,     3,
+       3,     0,     0,     2,     0,     0,     1,     3,     4,     3,
        6,     5
 };
 static const signed char yydefgoto[] =