* 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: 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
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.
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
@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
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);
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:
$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
projects / bison.git / commitdiff
