From 31984206a710101776d1db64009aff6c7962551c Mon Sep 17 00:00:00 2001 From: "Joel E. Denny" Date: Fri, 19 Oct 2007 06:14:44 +0000 Subject: [PATCH] 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. --- ChangeLog | 11 ++++++++++- NEWS | 12 ++++++++++-- doc/bison.texinfo | 42 ++++++++++++++++++++++++++++++++++++++++++ src/main.c | 18 ++++++++++-------- tests/conflicts.at | 15 ++++++++++++++- 5 files changed, 86 insertions(+), 12 deletions(-) diff --git a/ChangeLog b/ChangeLog index c2826cb8..25a026b7 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,6 +1,15 @@ 2007-10-19 Joel E. Denny - * 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 + + * 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 diff --git a/NEWS b/NEWS index bf260476..96cfa7a7 100644 --- a/NEWS +++ b/NEWS @@ -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 diff --git a/doc/bison.texinfo b/doc/bison.texinfo index 74feb9fb..a706a96d 100644 --- 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 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 diff --git a/src/main.c b/src/main.c index d979bae8..2b308298 100644 --- a/src/main.c +++ b/src/main.c @@ -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); diff --git a/tests/conflicts.at b/tests/conflicts.at index 2db956ee..14b128bd 100644 --- a/tests/conflicts.at +++ b/tests/conflicts.at @@ -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 -- 2.47.2