From 9d774affbae6fe069f68ea20ec0401dda019e6b6 Mon Sep 17 00:00:00 2001 From: "Joel E. Denny" Date: Tue, 17 Jul 2007 06:56:36 +0000 Subject: [PATCH] Improve handling of multiple S/R conflicts in the same state and of S/R conflicts involving multiple reductions. * src/conflicts.c (resolve_sr_conflict): Don't assign the error action set for a state here or Bison will abort if it is reassigned on a later conflicted reduction in the same state. Similarly, don't finalize and assign the solved conflicts report here or it will be lost if it is reassigned on a later conflicted reduction in the same state. (set_conflicts): Instead, assign them both here after all S/R conflicts in the state have been fully examined. * src/print.c (shift_set): Rename to... (no_reduce_set): ... this. (print_reductions): Update for rename, and add %nonassoc error action tokens to no_reduce_set so that, when printing the first remaining reduction on an error action token, the reduction is enclosed in brackets. (print_results): Update for rename. * tests/conflicts.at (Solved conflicts report for multiple reductions in a state): New test case. (%nonassoc error actions for multiple reductions in a state): New test case. * src/main.c (main): Don't depend on C99 features. --- ChangeLog | 26 ++++++++ src/conflicts.c | 45 +++++++------ src/main.c | 3 +- src/print.c | 17 ++--- tests/conflicts.at | 153 ++++++++++++++++++++++++++++++++++++++++++++- 5 files changed, 211 insertions(+), 33 deletions(-) diff --git a/ChangeLog b/ChangeLog index f30378d7..205ce5ef 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,29 @@ +2007-07-17 Joel E. Denny + + Improve handling of multiple S/R conflicts in the same state and of S/R + conflicts involving multiple reductions. + * src/conflicts.c (resolve_sr_conflict): Don't assign the error action + set for a state here or Bison will abort if it is reassigned on a + later conflicted reduction in the same state. + Similarly, don't finalize and assign the solved conflicts report here + or it will be lost if it is reassigned on a later conflicted reduction + in the same state. + (set_conflicts): Instead, assign them both here after all S/R conflicts + in the state have been fully examined. + * src/print.c (shift_set): Rename to... + (no_reduce_set): ... this. + (print_reductions): Update for rename, and add %nonassoc error action + tokens to no_reduce_set so that, when printing the first remaining + reduction on an error action token, the reduction is enclosed in + brackets. + (print_results): Update for rename. + * tests/conflicts.at (Solved conflicts report for multiple reductions + in a state): New test case. + (%nonassoc error actions for multiple reductions in a state): New test + case. + + * src/main.c (main): Don't depend on C99 features. + 2007-07-16 Joel E. Denny * build-aux/.cvsignore: Add compile. diff --git a/src/conflicts.c b/src/conflicts.c index f74604fa..ade54bd7 100644 --- a/src/conflicts.c +++ b/src/conflicts.c @@ -138,7 +138,7 @@ log_resolution (rule *r, symbol_number token, /*------------------------------------------------------------------. | Turn off the shift recorded for the specified token in the | | specified state. Used when we resolve a shift-reduce conflict in | -| favor of the reduction. | +| favor of the reduction or as an error (%nonassoc). | `------------------------------------------------------------------*/ static void @@ -156,9 +156,9 @@ flush_shift (state *s, int token) /*--------------------------------------------------------------------. -| Turn off the reduce recorded for the specified token for the | -| specified lookahead. Used when we resolve a shift-reduce conflict | -| in favor of the shift. | +| Turn off the reduce recorded for the specified token in the | +| specified lookahead set. Used when we resolve a shift-reduce | +| conflict in favor of the shift or as an error (%nonassoc). | `--------------------------------------------------------------------*/ static void @@ -176,11 +176,12 @@ flush_reduce (bitset lookahead_tokens, int token) | | | RULENO is the number of the lookahead bitset to consider. | | | -| ERRORS can be used to store discovered explicit errors. | +| ERRORS and NERRS can be used to store discovered explicit | +| errors. | `------------------------------------------------------------------*/ static void -resolve_sr_conflict (state *s, int ruleno, symbol **errors) +resolve_sr_conflict (state *s, int ruleno, symbol **errors, int *nerrs) { symbol_number i; reductions *reds = s->reductions; @@ -188,7 +189,6 @@ resolve_sr_conflict (state *s, int ruleno, symbol **errors) rule *redrule = reds->rules[ruleno]; int redprec = redrule->prec->prec; bitset lookahead_tokens = reds->lookahead_tokens[ruleno]; - int nerrs = 0; for (i = 0; i < ntokens; i++) if (bitset_test (lookahead_tokens, i) @@ -234,23 +234,10 @@ resolve_sr_conflict (state *s, int ruleno, symbol **errors) flush_shift (s, i); flush_reduce (lookahead_tokens, i); /* Record an explicit error for this token. */ - errors[nerrs++] = symbols[i]; + errors[(*nerrs)++] = symbols[i]; break; } } - - if (nerrs) - { - /* Some tokens have been explicitly made errors. Allocate a - permanent errs structure for this state, to record them. */ - state_errs_set (s, nerrs, errors); - } - - if (obstack_object_size (&solved_conflicts_obstack)) - { - obstack_1grow (&solved_conflicts_obstack, '\0'); - s->solved_conflicts = obstack_finish (&solved_conflicts_obstack); - } } @@ -267,6 +254,7 @@ set_conflicts (state *s, symbol **errors) int i; transitions *trans = s->transitions; reductions *reds = s->reductions; + int nerrs = 0; if (s->consistent) return; @@ -282,7 +270,19 @@ set_conflicts (state *s, symbol **errors) for (i = 0; i < reds->num; ++i) if (reds->rules[i]->prec && reds->rules[i]->prec->prec && !bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set)) - resolve_sr_conflict (s, i, errors); + resolve_sr_conflict (s, i, errors, &nerrs); + + if (nerrs) + { + /* Some tokens have been explicitly made errors. Allocate a + permanent errs structure for this state, to record them. */ + state_errs_set (s, nerrs, errors); + } + if (obstack_object_size (&solved_conflicts_obstack)) + { + obstack_1grow (&solved_conflicts_obstack, '\0'); + s->solved_conflicts = obstack_finish (&solved_conflicts_obstack); + } /* Loop over all rules which require lookahead in this state. Check for conflicts not resolved above. */ @@ -290,7 +290,6 @@ set_conflicts (state *s, symbol **errors) { if (!bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set)) conflicts[s->number] = 1; - bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]); } } diff --git a/src/main.c b/src/main.c index 84b2566f..84636083 100644 --- a/src/main.c +++ b/src/main.c @@ -116,11 +116,12 @@ main (int argc, char *argv[]) timevar_push (TV_CONFLICTS); conflicts_solve (); { - state_number old_to_new[nstates]; + 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/src/print.c b/src/print.c index f16816a0..07fd1d04 100644 --- a/src/print.c +++ b/src/print.c @@ -40,7 +40,7 @@ #include "symtab.h" #include "tables.h" -static bitset shift_set; +static bitset no_reduce_set; #if 0 static void @@ -252,9 +252,12 @@ print_reductions (FILE *out, state *s) if (yydefact[s->number] != 0) default_rule = &rules[yydefact[s->number] - 1]; - bitset_zero (shift_set); + bitset_zero (no_reduce_set); FOR_EACH_SHIFT (trans, i) - bitset_set (shift_set, TRANSITION_SYMBOL (trans, i)); + bitset_set (no_reduce_set, TRANSITION_SYMBOL (trans, i)); + for (i = 0; i < s->errs->num; ++i) + if (s->errs->symbols[i]) + bitset_set (no_reduce_set, s->errs->symbols[i]->number); /* Compute the width of the lookahead token column. */ if (default_rule) @@ -263,7 +266,7 @@ print_reductions (FILE *out, state *s) if (reds->lookahead_tokens) for (i = 0; i < ntokens; i++) { - bool count = bitset_test (shift_set, i); + bool count = bitset_test (no_reduce_set, i); for (j = 0; j < reds->num; ++j) if (bitset_test (reds->lookahead_tokens[j], i)) @@ -293,7 +296,7 @@ print_reductions (FILE *out, state *s) for (i = 0; i < ntokens; i++) { bool defaulted = false; - bool count = bitset_test (shift_set, i); + bool count = bitset_test (no_reduce_set, i); for (j = 0; j < reds->num; ++j) if (bitset_test (reds->lookahead_tokens[j], i)) @@ -498,10 +501,10 @@ print_results (void) if (report_flag & report_itemsets) new_closure (nritems); /* Storage for print_reductions. */ - shift_set = bitset_create (ntokens, BITSET_FIXED); + no_reduce_set = bitset_create (ntokens, BITSET_FIXED); for (i = 0; i < nstates; i++) print_state (out, states[i]); - bitset_free (shift_set); + bitset_free (no_reduce_set); if (report_flag & report_itemsets) free_closure (); diff --git a/tests/conflicts.at b/tests/conflicts.at index 21ba86d7..2bf750f0 100644 --- a/tests/conflicts.at +++ b/tests/conflicts.at @@ -90,7 +90,7 @@ expr: expr '<' expr int main (int argc, const char *argv[]) { - input = argc <= 1 ? "" : argv[1]; + input = argc <= 1 ? "" : argv[1]; return yyparse (); } ]]) @@ -810,8 +810,157 @@ state 6 state 7 1 start: resolved_conflict 'a' reported_conflicts 'a' . - + $default reduce using rule 1 (start) ]]) AT_CLEANUP + + +## ------------------------------------------------------------ ## +## Solved conflicts report for multiple reductions in a state. ## +## ------------------------------------------------------------ ## + +AT_SETUP([[Solved conflicts report for multiple reductions in a state]]) + +# Used to lose earlier solved conflict messages even within a single S/R/R. + +AT_DATA([[input.y]], +[[%left 'a' +%right 'b' +%right 'c' +%right 'd' +%% +start: + 'a' + | empty_a 'a' + | 'b' + | empty_b 'b' + | 'c' + | empty_c1 'c' + | empty_c2 'c' + | empty_c3 'c' + ; +empty_a: %prec 'a' ; +empty_b: %prec 'b' ; +empty_c1: %prec 'c' ; +empty_c2: %prec 'c' ; +empty_c3: %prec 'd' ; +]]) +AT_CHECK([[bison --report=all -o input.c input.y]], 0, [], [ignore]) +AT_CHECK([[cat input.output | sed -n '/^state 0$/,/^state 1$/p']], 0, +[[state 0 + + 0 $accept: . start $end + 1 start: . 'a' + 2 | . empty_a 'a' + 3 | . 'b' + 4 | . empty_b 'b' + 5 | . 'c' + 6 | . empty_c1 'c' + 7 | . empty_c2 'c' + 8 | . empty_c3 'c' + 9 empty_a: . ['a'] + 10 empty_b: . [] + 11 empty_c1: . [] + 12 empty_c2: . [] + 13 empty_c3: . ['c'] + + 'b' shift, and go to state 1 + + 'c' reduce using rule 13 (empty_c3) + $default reduce using rule 9 (empty_a) + + start go to state 2 + empty_a go to state 3 + empty_b go to state 4 + empty_c1 go to state 5 + empty_c2 go to state 6 + empty_c3 go to state 7 + + Conflict between rule 9 and token 'a' resolved as reduce (%left 'a'). + Conflict between rule 10 and token 'b' resolved as shift (%right 'b'). + Conflict between rule 11 and token 'c' resolved as shift (%right 'c'). + Conflict between rule 12 and token 'c' resolved as shift (%right 'c'). + Conflict between rule 13 and token 'c' resolved as reduce ('c' < 'd'). + + +state 1 +]]) + +AT_CLEANUP + + +## ------------------------------------------------------------ ## +## %nonassoc error actions for multiple reductions in a state. ## +## ------------------------------------------------------------ ## + +# Used to abort when trying to resolve conflicts as %nonassoc error actions for +# multiple reductions in a state. + +# For a %nonassoc error action token, used to print the first remaining +# reduction on that token without brackets. + +AT_SETUP([[%nonassoc error actions for multiple reductions in a state]]) + +AT_DATA([[input.y]], +[[%nonassoc 'a' 'b' 'c' +%% +start: + 'a' + | empty_a 'a' + | 'b' + | empty_b 'b' + | 'c' + | empty_c1 'c' + | empty_c2 'c' + | empty_c3 'c' + ; +empty_a: %prec 'a' ; +empty_b: %prec 'b' ; +empty_c1: %prec 'c' ; +empty_c2: %prec 'c' ; +empty_c3: %prec 'c' ; +]]) + +AT_CHECK([[bison --report=all -o input.c input.y]], 0, [], [ignore]) +AT_CHECK([[cat input.output | sed -n '/^state 0$/,/^state 1$/p']], 0, +[[state 0 + + 0 $accept: . start $end + 1 start: . 'a' + 2 | . empty_a 'a' + 3 | . 'b' + 4 | . empty_b 'b' + 5 | . 'c' + 6 | . empty_c1 'c' + 7 | . empty_c2 'c' + 8 | . empty_c3 'c' + 9 empty_a: . [] + 10 empty_b: . [] + 11 empty_c1: . [] + 12 empty_c2: . ['c'] + 13 empty_c3: . ['c'] + + 'a' error (nonassociative) + 'b' error (nonassociative) + 'c' error (nonassociative) + + 'c' [reduce using rule 12 (empty_c2)] + 'c' [reduce using rule 13 (empty_c3)] + + start go to state 1 + empty_a go to state 2 + empty_b go to state 3 + empty_c1 go to state 4 + empty_c2 go to state 5 + empty_c3 go to state 6 + + Conflict between rule 9 and token 'a' resolved as an error (%nonassoc 'a'). + Conflict between rule 10 and token 'b' resolved as an error (%nonassoc 'b'). + Conflict between rule 11 and token 'c' resolved as an error (%nonassoc 'c'). + + +state 1 +]]) +AT_CLEANUP -- 2.45.2