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.

diff --git a/ChangeLog b/ChangeLog
index 3c4a350f68163bc195afbcd2bd2ee37006831bf5..ccb6506081ccea0e0d2f9884a5d04bbad664ca52 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,20 @@
+2002-07-30  Akim Demaille  <akim@epita.fr>
+
+       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.
+

 2002-07-30  Akim Demaille  <akim@epita.fr>
 
        `stage' was accidently included in a previous patch.
 2002-07-30  Akim Demaille  <akim@epita.fr>
 
        `stage' was accidently included in a previous patch.

diff --git a/NEWS b/NEWS
index 144d865d57774e368941b40bef18877bb6b3146c..6123e57a797e8b411be059b3133bfec82ac05142 100644 (file)
--- a/NEWS
+++ b/NEWS
@@ -8,7 +8,7 @@ Changes in version 1.49b:
      %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
      %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
   ambiguities.  Contributed by Paul Hilfinger.
 
 * Output Directory


@@ -58,6 +58,10 @@ Changes in version 1.49b:
 * Useless rules, useless nonterminals
   They are now reported, as a warning, with their locations.
 
 * 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
 
 * Incorrect `Token not used'
   On a grammar such as
 

diff --git a/src/LR0.c b/src/LR0.c
index 00ff736ce9e8d8b25dd029f664cab48fff18d147..184a25f4dbba970f8825bcc07889017f02849a80 100644 (file)
--- a/src/LR0.c
+++ b/src/LR0.c
@@ -282,11 +282,6 @@ save_reductions (state_t *state)
   int count = 0;
   int i;
 
   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)
     {
   /* Find and count the active items that represent ends of rules. */
   for (i = 0; i < nritemset; ++i)
     {

diff --git a/src/output.c b/src/output.c
index 1ec4d6b03fd3cab790f19d00c553075515ec9066..5f0fa05f3760c9d3d1862767c66c3fdfcfac1e7a 100644 (file)
--- a/src/output.c
+++ b/src/output.c
@@ -598,6 +598,16 @@ action_row (state_t *state)
        }
     }
 
        }
     }
 

+  /* 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".  */
 
   /* If have no default rule, the default is an error.
      So replace any action which says "error" with "use default".  */
 


@@ -671,6 +681,7 @@ static void
 token_actions (void)
 {
   state_number_t i;
 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);
   int nconflict = conflicts_total_count ();
 
   rule_number_t *yydefact = XCALLOC (rule_number_t, nstates);


@@ -678,6 +689,13 @@ token_actions (void)
   actrow = XCALLOC (action_t, ntokens);
   conflrow = XCALLOC (unsigned int, ntokens);
 
   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);
   if (glr_parser)
     {
       conflict_list = XCALLOC (unsigned int, 1 + 2 * nconflict);


@@ -696,6 +714,17 @@ token_actions (void)
 
   muscle_insert_rule_number_table ("defact", yydefact,
                                   yydefact[0], 1, nstates);
 
   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);
   XFREE (actrow);
   XFREE (conflrow);
   XFREE (yydefact);

diff --git a/src/print.c b/src/print.c
index 1227765b2f010454a2e51e40b12b847895345338..2a07affacecb9029829eeaf4a78f34484e5d3d9a 100644 (file)
--- a/src/print.c
+++ b/src/print.c
@@ -286,8 +286,11 @@ print_reduction (FILE *out, size_t width,
     fputc (' ', out);
   if (!enabled)
     fputc ('[', out);
     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);
   if (!enabled)
     fputc (']', out);
   fputc ('\n', out);


@@ -393,19 +396,6 @@ print_reductions (FILE *out, state_t *state)
 static void
 print_actions (FILE *out, state_t *state)
 {
 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);
   /* Print shifts.  */
   print_transitions (state, out, TRUE);
   print_errs (out, state);

diff --git a/tests/conflicts.at b/tests/conflicts.at
index 84b4fcdaba5f510866f8f4ced984b0c0fabd4510..d0da937bfb1718cd7e0c7ad8363f7e7e702e067a 100644 (file)
--- a/tests/conflicts.at
+++ b/tests/conflicts.at
@@ -37,7 +37,9 @@ exp: e 'e';
 e: 'e' | /* Nothing. */;
 ]])
 
 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
 
 
 AT_CLEANUP
 


@@ -203,7 +205,7 @@ state 3
 
     0 $accept: exp $end .
 
 
     0 $accept: exp $end .
 

-    $default   accept
+    $default  accept

 
 
 state 4
 
 
 state 4


@@ -306,7 +308,7 @@ state 3
 
     0 $accept: exp $end .
 
 
     0 $accept: exp $end .
 

-    $default   accept
+    $default  accept

 
 
 state 4
 
 
 state 4


@@ -369,8 +371,9 @@ id : '0';
 ]])
 
 AT_CHECK([bison input.y -o input.c --report=all], 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], [],
 
 # Check the contents of the report.
 AT_CHECK([cat input.output], [],


@@ -458,7 +461,7 @@ state 5
 
     0 $accept: exp $end .
 
 
     0 $accept: exp $end .
 

-    $default   accept
+    $default  accept

 ]])
 
 AT_CLEANUP
 ]])
 
 AT_CLEANUP

diff --git a/tests/regression.at b/tests/regression.at
index ca5c2f971cc69451a9d77cf89b02e8c264703fe0..f8768f762bff4dc7f50d780e10e5f5847c3dbf5f 100644 (file)
--- a/tests/regression.at
+++ b/tests/regression.at
@@ -228,7 +228,7 @@ state 5
 
     0 $accept: expr $end .
 
 
     0 $accept: expr $end .
 

-    $default   accept
+    $default  accept

 
 
 state 6
 
 
 state 6


@@ -456,7 +456,7 @@ state 5
 
     0 $accept: CONST_DEC_PART $end .
 
 
     0 $accept: CONST_DEC_PART $end .
 

-    $default   accept
+    $default  accept

 
 
 state 6
 
 
 state 6


@@ -601,7 +601,7 @@ static const unsigned char yyr2[] =
 };
 static const unsigned char yydefact[] =
 {
 };
 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[] =
        6,     5
 };
 static const signed char yydefgoto[] =