%define lr.keep_unreachable_states

[Joel E. Denny]

I committed this.

Index: ChangeLog
===================================================================
RCS file: /sources/bison/bison/ChangeLog,v
retrieving revision 1.1740
diff -p -u -r1.1740 ChangeLog
--- ChangeLog   19 Oct 2007 02:46:21 -0000      1.1740
+++ ChangeLog   19 Oct 2007 06:04:12 -0000
@@ -1,6 +1,15 @@
 2007-10-19  Joel E. Denny  <address@hidden>
 
-       * 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  <address@hidden>
+
+       * 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
Index: NEWS
===================================================================
RCS file: /sources/bison/bison/NEWS,v
retrieving revision 1.177
diff -p -u -r1.177 NEWS
--- NEWS        19 Oct 2007 02:46:21 -0000      1.177
+++ NEWS        19 Oct 2007 06:04:12 -0000
@@ -3,8 +3,9 @@ Bison News
 
 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.
 
@@ -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".
 
+  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
Index: doc/bison.texinfo
===================================================================
RCS file: /sources/bison/bison/doc/bison.texinfo,v
retrieving revision 1.240
diff -p -u -r1.240 bison.texinfo
--- doc/bison.texinfo   19 Oct 2007 02:46:21 -0000      1.240
+++ doc/bison.texinfo   19 Oct 2007 06:04:16 -0000
@@ -4851,6 +4851,48 @@ Some of the accepted @var{variable}s are
 @item Default Value: @code{"pull"}
 @end itemize
 
address@hidden lr.keep_unreachable_states
address@hidden %define lr.keep_unreachable_states
+
address@hidden @bullet
address@hidden Language(s): all
+
address@hidden 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.
+
address@hidden Accepted Values: Boolean
+
address@hidden Default Value: @code{"false"}
+
address@hidden Caveats:
+
address@hidden @bullet
address@hidden 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.
+
address@hidden 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.
address@hidden itemize
address@hidden itemize
+
 @item namespace
 @findex %define namespace
 
Index: src/main.c
===================================================================
RCS file: /sources/bison/bison/src/main.c,v
retrieving revision 1.98
diff -p -u -r1.98 main.c
--- src/main.c  21 Sep 2007 22:53:57 -0000      1.98
+++ src/main.c  19 Oct 2007 06:04:16 -0000
@@ -114,14 +114,16 @@ main (int argc, char *argv[])
      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);
 
Index: tests/conflicts.at
===================================================================
RCS file: /sources/bison/bison/tests/conflicts.at,v
retrieving revision 1.37
diff -p -u -r1.37 conflicts.at
--- tests/conflicts.at  17 Oct 2007 04:35:35 -0000      1.37
+++ tests/conflicts.at  19 Oct 2007 06:04:16 -0000
@@ -636,7 +636,7 @@ AT_DATA([[input.y]],
 
 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:
@@ -812,6 +812,19 @@ state 7
     $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