From 5967f0cf594cf19cd596b171392cc51bbd0ee596 Mon Sep 17 00:00:00 2001 From: "Joel E. Denny" Date: Mon, 7 May 2007 02:56:56 +0000 Subject: [PATCH] If conflict resolution makes states unreachable, remove those states, report rules that are then unused, and don't report conflicts in those states. * src/conflicts.c, src/conflicts.h (conflicts_update_state_numbers): New global function. * src/lalr.c, src/lalr.h (lalr_update_state_numbers): New global function. * src/main.c (main): After conflict resolution, remove the unreachable states and update all data structures that reference states by number. * src/state.c (state_new): Initialize each state's reachable member to false. (state_mark_reachable_states): New static function. (state_remove_unreachable_states): New global function. * src/state.h (struct state): Add member bool reachable. (state_remove_unreachable_states): Prototype. * tests/conflicts.at (Unreachable States After Conflict Resolution): New test case. * tests/existing.at (GNU pic Grammar): Update test case output now that an unused rule is discovered. --- ChangeLog | 22 +++++ src/conflicts.c | 10 +++ src/conflicts.h | 13 +++ src/lalr.c | 31 +++++++ src/lalr.h | 12 +++ src/main.c | 7 ++ src/state.c | 39 +++++++++ src/state.h | 12 +++ tests/conflicts.at | 198 +++++++++++++++++++++++++++++++++++++++++++++ tests/existing.at | 4 +- 10 files changed, 347 insertions(+), 1 deletion(-) diff --git a/ChangeLog b/ChangeLog index 53361e3d..6d0cec9d 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,25 @@ +2007-05-06 Joel E. Denny + + If conflict resolution makes states unreachable, remove those states, + report rules that are then unused, and don't report conflicts in those + states. + * src/conflicts.c, src/conflicts.h (conflicts_update_state_numbers): + New global function. + * src/lalr.c, src/lalr.h (lalr_update_state_numbers): New global + function. + * src/main.c (main): After conflict resolution, remove the unreachable + states and update all data structures that reference states by number. + * src/state.c (state_new): Initialize each state's reachable member to + false. + (state_mark_reachable_states): New static function. + (state_remove_unreachable_states): New global function. + * src/state.h (struct state): Add member bool reachable. + (state_remove_unreachable_states): Prototype. + * tests/conflicts.at (Unreachable States After Conflict Resolution): + New test case. + * tests/existing.at (GNU pic Grammar): Update test case output now that + an unused rule is discovered. + 2007-05-06 Joel E. Denny Minor code cleanup in parser table construction. diff --git a/src/conflicts.c b/src/conflicts.c index 7bb3e08e..16fa0ae0 100644 --- a/src/conflicts.c +++ b/src/conflicts.c @@ -327,6 +327,16 @@ conflicts_solve (void) } +void +conflicts_update_state_numbers (state_number old_to_new[], + state_number nstates_old) +{ + for (state_number i = 0; i < nstates_old; ++i) + if (old_to_new[i] != nstates_old) + conflicts[old_to_new[i]] = conflicts[i]; +} + + /*---------------------------------------------. | Count the number of shift/reduce conflicts. | `---------------------------------------------*/ diff --git a/src/conflicts.h b/src/conflicts.h index 2b8df518..055905eb 100644 --- a/src/conflicts.h +++ b/src/conflicts.h @@ -23,6 +23,19 @@ # include "state.h" void conflicts_solve (void); + +/** + * Update state numbers recorded in internal arrays such that: + * - \c nstates_old is the old number of states. + * - Where \c i is the old state number, old_to_new[i] is either: + * - \c nstates_old if state \c i is removed because it is unreachable. + * - The new state number. + * - The highest new state number is the number of remaining states - 1. + * - The numerical order of the remaining states has not changed. + */ +void conflicts_update_state_numbers (state_number old_to_new[], + state_number nstates_old); + void conflicts_print (void); int conflicts_total_count (void); void conflicts_output (FILE *out); diff --git a/src/lalr.c b/src/lalr.c index 805797cf..00455b06 100644 --- a/src/lalr.c +++ b/src/lalr.c @@ -453,6 +453,37 @@ lalr (void) } +void +lalr_update_state_numbers (state_number old_to_new[], state_number nstates_old) +{ + goto_number ngotos_reachable = 0; + symbol_number nonterminal = 0; + aver (nsyms == nvars + ntokens); + for (goto_number i = 0; i < ngotos; ++i) + { + while (i == goto_map[nonterminal]) + goto_map[nonterminal++] = ngotos_reachable; + /* If old_to_new[from_state[i]] = nstates_old, remove this goto + entry. */ + if (old_to_new[from_state[i]] != nstates_old) + { + /* from_state[i] is not removed, so it and thus to_state[i] are + reachable, so to_state[i] != nstates_old. */ + aver (old_to_new[to_state[i]] != nstates_old); + from_state[ngotos_reachable] = old_to_new[from_state[i]]; + to_state[ngotos_reachable] = old_to_new[to_state[i]]; + ++ngotos_reachable; + } + } + while (nonterminal <= nvars) + { + aver (ngotos == goto_map[nonterminal]); + goto_map[nonterminal++] = ngotos_reachable; + } + ngotos = ngotos_reachable; +} + + void lalr_free (void) { diff --git a/src/lalr.h b/src/lalr.h index fe148d03..0c68cd74 100644 --- a/src/lalr.h +++ b/src/lalr.h @@ -46,6 +46,18 @@ */ void lalr (void); +/** + * Update state numbers recorded in #goto_map, #from_state, and #to_state such + * that: + * - \c nstates_old is the old number of states. + * - Where \c i is the old state number, old_to_new[i] is either: + * - \c nstates_old if state \c i is removed because it is unreachable. + * Thus, remove all goto entries involving this state. + * - The new state number. + */ +void lalr_update_state_numbers (state_number old_to_new[], + state_number nstates_old); + /** Release the information related to lookahead tokens. diff --git a/src/main.c b/src/main.c index d64f9219..84b2566f 100644 --- a/src/main.c +++ b/src/main.c @@ -115,6 +115,13 @@ main (int argc, char *argv[]) declarations. */ timevar_push (TV_CONFLICTS); conflicts_solve (); + { + state_number old_to_new[nstates]; + 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); + } conflicts_print (); timevar_pop (TV_CONFLICTS); diff --git a/src/state.c b/src/state.c index 280a2f41..bae3575e 100644 --- a/src/state.c +++ b/src/state.c @@ -145,6 +145,7 @@ state_new (symbol_number accessing_symbol, res->errs = NULL; res->consistent = 0; res->solved_conflicts = NULL; + res->reachable = false; res->nitems = nitems; memcpy (res->items, core, items_size); @@ -352,6 +353,44 @@ state_hash_lookup (size_t nitems, item_number *core) return entry; } + +/*------------------------------------------------------. +| Mark S and all states reachable from S as reachable. | +`------------------------------------------------------*/ + +static void +state_mark_reachable_states (state *s) +{ + if (s->reachable) + return; + s->reachable = true; + for (int i = 0; i < s->transitions->num; ++i) + if (!TRANSITION_IS_DISABLED (s->transitions, i)) + state_mark_reachable_states (s->transitions->states[i]); +} + +void +state_remove_unreachable_states (state_number old_to_new[]) +{ + state_number nstates_reachable = 0; + state_mark_reachable_states (states[0]); + for (state_number i = 0; i < nstates; ++i) + { + if (states[i]->reachable) + { + states[nstates_reachable] = states[i]; + states[nstates_reachable]->number = nstates_reachable; + old_to_new[i] = nstates_reachable++; + } + else + { + state_free (states[i]); + old_to_new[i] = nstates; + } + } + nstates = nstates_reachable; +} + /* All the decorated states, indexed by the state number. */ state **states = NULL; diff --git a/src/state.h b/src/state.h index 28933e13..668aa73f 100644 --- a/src/state.h +++ b/src/state.h @@ -209,6 +209,11 @@ struct state a human readable description of the resolution. */ const char *solved_conflicts; + /* Conflict resolution sometimes makes states unreachable. Initialized to 0 + in state_new and then used by state_remove_unreachable_states after + conflicts_solve. */ + bool reachable; + /* Its items. Must be last, since ITEMS can be arbitrarily large. */ size_t nitems; @@ -248,9 +253,16 @@ state *state_hash_lookup (size_t core_size, item_number *core); /* Insert STATE in the state hash table. */ void state_hash_insert (state *s); +/* Remove unreachable states, renumber remaining states, update NSTATES, and + write to OLD_TO_NEW a mapping of old state numbers to new state numbers such + that the old value of NSTATES is written as the new state number for removed + states. The size of OLD_TO_NEW must be the old value of NSTATES. */ +void state_remove_unreachable_states (state_number old_to_new[]); + /* All the states, indexed by the state number. */ extern state **states; /* Free all the states. */ void states_free (void); + #endif /* !STATE_H_ */ diff --git a/tests/conflicts.at b/tests/conflicts.at index 436ba858..79a77307 100644 --- a/tests/conflicts.at +++ b/tests/conflicts.at @@ -617,3 +617,201 @@ e: e '+' e AT_CHECK([bison -o input.c input.y]) AT_CLEANUP + + +## ---------------------------------------------- ## +## Unreachable States After Conflict Resolution. ## +## ---------------------------------------------- ## + +AT_SETUP([[Unreachable States After Conflict Resolution]]) + +# If conflict resolution makes states unreachable, remove those states, report +# rules that are then unused, and don't report conflicts in those states. Test +# what happens when a nonterminal becomes useless as a result of state removal +# since that causes lalr.o's goto map to be rewritten. + +AT_DATA([[input.y]], +[[%output "input.c" +%left 'a' + +%% + +start: resolved_conflict 'a' reported_conflicts 'a' ; + +/* S/R conflict resolved as shift, so the state with item + * (resolved_conflict: 'a' . unreachable1) and all it transition successors are + * unreachable, and the associated production is useless. */ +resolved_conflict: + 'a' unreachable1 + | %prec 'a' + ; + +/* S/R conflict that need not be reported since it is unreachable because of + * the previous conflict resolution. Nonterminal unreachable1 and all its + * productions are useless. */ +unreachable1: + 'a' unreachable2 + | + ; + +/* Likewise for a R/R conflict and nonterminal unreachable2. */ +unreachable2: | ; + +/* Make sure remaining S/R and R/R conflicts are still reported correctly even + * when their states are renumbered due to state removal. */ +reported_conflicts: + 'a' + | 'a' + | + ; + +]]) + +AT_CHECK([[bison --report=all input.y]], 0, [], +[[input.y: conflicts: 1 shift/reduce, 1 reduce/reduce +input.y:12.5-20: warning: rule never reduced because of conflicts: resolved_conflict: 'a' unreachable1 +input.y:20.5-20: warning: rule never reduced because of conflicts: unreachable1: 'a' unreachable2 +input.y:21.4: warning: rule never reduced because of conflicts: unreachable1: /* empty */ +input.y:25.13: warning: rule never reduced because of conflicts: unreachable2: /* empty */ +input.y:25.16: warning: rule never reduced because of conflicts: unreachable2: /* empty */ +input.y:31.5-7: warning: rule never reduced because of conflicts: reported_conflicts: 'a' +input.y:32.4: warning: rule never reduced because of conflicts: reported_conflicts: /* empty */ +]]) + +AT_CHECK([[cat input.output]], 0, +[[Rules never reduced + + 2 resolved_conflict: 'a' unreachable1 + + 4 unreachable1: 'a' unreachable2 + 5 | /* empty */ + + 6 unreachable2: /* empty */ + 7 | /* empty */ + + 9 reported_conflicts: 'a' + 10 | /* empty */ + + +State 4 conflicts: 1 shift/reduce +State 5 conflicts: 1 reduce/reduce + + +Grammar + + 0 $accept: start $end + + 1 start: resolved_conflict 'a' reported_conflicts 'a' + + 2 resolved_conflict: 'a' unreachable1 + 3 | /* empty */ + + 4 unreachable1: 'a' unreachable2 + 5 | /* empty */ + + 6 unreachable2: /* empty */ + 7 | /* empty */ + + 8 reported_conflicts: 'a' + 9 | 'a' + 10 | /* empty */ + + +Terminals, with rules where they appear + +$end (0) 0 +'a' (97) 1 2 4 8 9 +error (256) + + +Nonterminals, with rules where they appear + +$accept (4) + on left: 0 +start (5) + on left: 1, on right: 0 +resolved_conflict (6) + on left: 2 3, on right: 1 +unreachable1 (7) + on left: 4 5, on right: 2 +unreachable2 (8) + on left: 6 7, on right: 4 +reported_conflicts (9) + on left: 8 9 10, on right: 1 + + +state 0 + + 0 $accept: . start $end + 1 start: . resolved_conflict 'a' reported_conflicts 'a' + 2 resolved_conflict: . 'a' unreachable1 + 3 | . ['a'] + + $default reduce using rule 3 (resolved_conflict) + + start go to state 1 + resolved_conflict go to state 2 + + Conflict between rule 3 and token 'a' resolved as reduce (%left 'a'). + + +state 1 + + 0 $accept: start . $end + + $end shift, and go to state 3 + + +state 2 + + 1 start: resolved_conflict . 'a' reported_conflicts 'a' + + 'a' shift, and go to state 4 + + +state 3 + + 0 $accept: start $end . + + $default accept + + +state 4 + + 1 start: resolved_conflict 'a' . reported_conflicts 'a' + 8 reported_conflicts: . 'a' + 9 | . 'a' + 10 | . ['a'] + + 'a' shift, and go to state 5 + + 'a' [reduce using rule 10 (reported_conflicts)] + + reported_conflicts go to state 6 + + +state 5 + + 8 reported_conflicts: 'a' . ['a'] + 9 | 'a' . ['a'] + + 'a' reduce using rule 8 (reported_conflicts) + 'a' [reduce using rule 9 (reported_conflicts)] + $default reduce using rule 8 (reported_conflicts) + + +state 6 + + 1 start: resolved_conflict 'a' reported_conflicts . 'a' + + 'a' shift, and go to state 7 + + +state 7 + + 1 start: resolved_conflict 'a' reported_conflicts 'a' . + + $default reduce using rule 1 (start) +]]) + +AT_CLEANUP diff --git a/tests/existing.at b/tests/existing.at index 9db625a9..cb385f53 100644 --- a/tests/existing.at +++ b/tests/existing.at @@ -1520,6 +1520,8 @@ expr: # Pass plenty of options, to exercise plenty of code, even if we # don't actually check the output. But SEGV is watching us, and # so might do dmalloc. -AT_CHECK([[bison --verbose --defines input.y]], 0, [], []) +AT_CHECK([[bison --verbose --defines input.y]], 0, [], +[[input.y:453.11-48: warning: rule never reduced because of conflicts: path: ORDINAL LAST object_type relative_path +]]) AT_CLEANUP -- 2.47.2