Add %define lr.keep_unreachable_states.

* NEWS (2.3a+): Mention it in the entry for unreachable state removal.
* doc/bison.texinfo (Decl Summary): Mention it in the %define entry.
* src/main.c (main): Implement it.
* tests/conflicts.at (Unreachable States After Conflict Resolution):
Extend to test it, and fix a typo.

diff --git a/ChangeLog b/ChangeLog
index c2826cb84319f9312590b14588c64471d0ca4b9f..25a026b7b2918cfb5d179deb595a1492285bfa98 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,6 +1,15 @@
 2007-10-19  Joel E. Denny  <jdenny@ces.clemson.edu>
 
 2007-10-19  Joel E. Denny  <jdenny@ces.clemson.edu>
 

-       * NEWS: Add entry for recent .output file lookahead set fix.
+       Add %define lr.keep_unreachable_states.
+       * NEWS (2.3a+): Mention it in the entry for unreachable state removal.
+       * doc/bison.texinfo (Decl Summary): Mention it in the %define entry.
+       * src/main.c (main): Implement it.
+       * tests/conflicts.at (Unreachable States After Conflict Resolution):
+       Extend to test it, and fix a typo.
+
+2007-10-19  Joel E. Denny  <jdenny@ces.clemson.edu>
+
+       * NEWS (2.3a+): Add entry for recent .output file lookahead set fix.

        * doc/bison.texinfo (Understanding): Remove a bogus lookahead set in
        the example .output text.
        * tests/regression.at (Extra lookahead sets in report): Improve wording
        * doc/bison.texinfo (Understanding): Remove a bogus lookahead set in
        the example .output text.
        * tests/regression.at (Extra lookahead sets in report): Improve wording

diff --git a/NEWS b/NEWS
index bf260476b0253dd1cc70431f1a5680e021625695..96cfa7a773830c03ccf49634cf384e430031ebda 100644 (file)
--- a/NEWS
+++ b/NEWS
@@ -3,8 +3,9 @@ Bison News
 
 Changes in version 2.3a+ (????-??-??):
 
 
 Changes in version 2.3a+ (????-??-??):
 

-* Previously, Bison sometimes generated parser tables with states that were
-  unreachable due to conflicts in predecessor states.  Bison now:
+* Previously, Bison sometimes generated parser tables containing unreachable
+  states.  A state can become unreachable during conflict resolution if Bison
+  disables a shift action leading to it from a predecessor state.  Bison now:

 
     1. Removes unreachable states.
 
 
     1. Removes unreachable states.
 


@@ -15,6 +16,13 @@ Changes in version 2.3a+ (????-??-??):
     3. For any rule used only in such states, Bison now reports the rule as
        "never reduced because of conflicts".
 
     3. For any rule used only in such states, Bison now reports the rule as
        "never reduced because of conflicts".
 

+  This feature can be disabled with the following directive:
+
+    %define lr.keep_unreachable_states
+
+  See the %define entry in the `Bison Declaration Summary' in the Bison manual
+  for further discussion.
+

 * When instructed to generate a `.output' file including lookahead sets
   (using `--report=lookahead', for example), Bison now prints each reduction's
   lookahead set only next to the associated state's one item that (1) is
 * When instructed to generate a `.output' file including lookahead sets
   (using `--report=lookahead', for example), Bison now prints each reduction's
   lookahead set only next to the associated state's one item that (1) is

diff --git a/doc/bison.texinfo b/doc/bison.texinfo
index 74feb9fbbe00122ecec3be6d7bb8d96bf6d4268d..a706a96dad2151e091d141146d36cc2419f800d7 100644 (file)
--- a/doc/bison.texinfo
+++ b/doc/bison.texinfo
@@ -4851,6 +4851,48 @@ Some of the accepted @var{variable}s are:
 @item Default Value: @code{"pull"}
 @end itemize
 
 @item Default Value: @code{"pull"}
 @end itemize
 

+@item lr.keep_unreachable_states
+@findex %define lr.keep_unreachable_states
+
+@itemize @bullet
+@item Language(s): all
+
+@item Purpose: Requests that Bison allow unreachable parser states to remain in
+the parser tables.
+Bison considers a state to be unreachable if there exists no sequence of
+transitions from the start state to that state.
+A state can become unreachable during conflict resolution if Bison disables a
+shift action leading to it from a predecessor state.
+Keeping unreachable states is sometimes useful for analysis purposes, but they
+are useless in the generated parser.
+
+@item Accepted Values: Boolean
+
+@item Default Value: @code{"false"}
+
+@item Caveats:
+
+@itemize @bullet
+@item Unreachable states may contain conflicts and may reduce rules not
+reduced in any other state.
+Thus, keeping unreachable states may induce warnings that are irrelevant to
+your parser's behavior, and it may eliminate warnings that are relevant.
+Of course, the change in warnings may actually be relevant to a parser table
+analysis that wants to keep unreachable states, so this behavior will likely
+remain in future Bison releases.
+
+@item While Bison is able to remove unreachable states, it is not guaranteed to
+remove other kinds of useless states.
+Specifically, when Bison disables reduce actions during conflict resolution,
+some goto actions may become useless, and thus some additional states may
+become useless.
+If Bison were to compute which goto actions were useless and then disable those
+actions, it could identify such states as unreachable and then remove those
+states.
+However, Bison does not compute which goto actions are useless.
+@end itemize
+@end itemize
+

 @item namespace
 @findex %define namespace
 
 @item namespace
 @findex %define namespace
 

diff --git a/src/main.c b/src/main.c
index d979bae8df777869ee8390a74f171ff5b4f2f21c..2b30829846e7d9394e3f1090bae51d94e423ca3c 100644 (file)
--- a/src/main.c
+++ b/src/main.c
@@ -114,14 +114,16 @@ main (int argc, char *argv[])
      declarations.  */
   timevar_push (TV_CONFLICTS);
   conflicts_solve ();
      declarations.  */
   timevar_push (TV_CONFLICTS);
   conflicts_solve ();

-  {
-    state_number *old_to_new = xnmalloc (nstates, sizeof *old_to_new);
-    state_number nstates_old = nstates;
-    state_remove_unreachable_states (old_to_new);
-    lalr_update_state_numbers (old_to_new, nstates_old);
-    conflicts_update_state_numbers (old_to_new, nstates_old);
-    free (old_to_new);
-  }
+  muscle_percent_define_default ("lr.keep_unreachable_states", "false");
+  if (!muscle_percent_define_flag_if ("lr.keep_unreachable_states"))
+    {
+      state_number *old_to_new = xnmalloc (nstates, sizeof *old_to_new);
+      state_number nstates_old = nstates;
+      state_remove_unreachable_states (old_to_new);
+      lalr_update_state_numbers (old_to_new, nstates_old);
+      conflicts_update_state_numbers (old_to_new, nstates_old);
+      free (old_to_new);
+    }

   conflicts_print ();
   timevar_pop (TV_CONFLICTS);
 
   conflicts_print ();
   timevar_pop (TV_CONFLICTS);
 

diff --git a/tests/conflicts.at b/tests/conflicts.at
index 2db956ee67ac1244d0607829489f0adb4bfeaa4b..14b128bd71367dab3e2d13ca5f8cd3a51ac5254a 100644 (file)
--- a/tests/conflicts.at
+++ b/tests/conflicts.at
@@ -636,7 +636,7 @@ AT_DATA([[input.y]],
 
 start: resolved_conflict 'a' reported_conflicts 'a' ;
 
 
 start: resolved_conflict 'a' reported_conflicts 'a' ;
 

-/* S/R conflict resolved as shift, so the state with item
+/* S/R conflict resolved as reduce, so the state with item

  * (resolved_conflict: 'a' . unreachable1) and all it transition successors are
  * unreachable, and the associated production is useless.  */
 resolved_conflict:
  * (resolved_conflict: 'a' . unreachable1) and all it transition successors are
  * unreachable, and the associated production is useless.  */
 resolved_conflict:


@@ -812,6 +812,19 @@ state 7
     $default  reduce using rule 1 (start)
 ]])
 
     $default  reduce using rule 1 (start)
 ]])
 

+AT_DATA([[input-keep.y]],
+[[%define lr.keep_unreachable_states
+]])
+AT_CHECK([[cat input.y >> input-keep.y]])
+
+AT_CHECK([[bison input-keep.y]], 0, [],
+[[input-keep.y: conflicts: 2 shift/reduce, 2 reduce/reduce
+input-keep.y:22.4: warning: rule never reduced because of conflicts: unreachable1: /* empty */
+input-keep.y:26.16: warning: rule never reduced because of conflicts: unreachable2: /* empty */
+input-keep.y:32.5-7: warning: rule never reduced because of conflicts: reported_conflicts: 'a'
+input-keep.y:33.4: warning: rule never reduced because of conflicts: reported_conflicts: /* empty */
+]])
+

 AT_CLEANUP
 
 
 AT_CLEANUP