From b408954b40e74d85ee90544ea7e296dbc99356c9 Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Sun, 26 May 2002 20:25:52 +0000 Subject: [PATCH] * src/state.h (state_t): `solved_conflicts' is a new member. * src/LR0.c (new_state): Set it to 0. * src/conflicts.h, src/conflicts.c (print_conflicts) (free_conflicts, solve_conflicts): Rename as... (conflicts_print, conflicts_free, conflicts_solve): these. Adjust callers. * src/conflicts.c (enum conflict_resolution_e) (solved_conflicts_obstack): New, used by... (log_resolution): this. Adjust to attach the conflict resolution to each state. Complete the description with the precedence/associativity information. (resolve_sr_conflict): Adjust. * src/print.c (print_state): Output its solved_conflicts. * tests/conflicts.at (Unresolved SR Conflicts) (Solved SR Conflicts): Exercise --report=all. --- ChangeLog | 19 ++++++++ NEWS | 13 ++++-- TODO | 16 ------- src/LR0.c | 3 +- src/conflicts.c | 111 ++++++++++++++++++++++++++++++++++++++------- src/conflicts.h | 6 +-- src/getargs.c | 3 ++ src/getargs.h | 1 + src/main.c | 4 +- src/print.c | 3 ++ src/state.h | 7 ++- tests/conflicts.at | 26 +++++++---- 12 files changed, 159 insertions(+), 53 deletions(-) diff --git a/ChangeLog b/ChangeLog index 4a450cbc..980b2193 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,22 @@ +2002-05-26 Akim Demaille + + * src/state.h (state_t): `solved_conflicts' is a new member. + * src/LR0.c (new_state): Set it to 0. + * src/conflicts.h, src/conflicts.c (print_conflicts) + (free_conflicts, solve_conflicts): Rename as... + (conflicts_print, conflicts_free, conflicts_solve): these. + Adjust callers. + * src/conflicts.c (enum conflict_resolution_e) + (solved_conflicts_obstack): New, used by... + (log_resolution): this. + Adjust to attach the conflict resolution to each state. + Complete the description with the precedence/associativity + information. + (resolve_sr_conflict): Adjust. + * src/print.c (print_state): Output its solved_conflicts. + * tests/conflicts.at (Unresolved SR Conflicts) + (Solved SR Conflicts): Exercise --report=all. + 2002-05-26 Akim Demaille * src/LR0.c, src/derives.c, src/gram.c, src/gram.h, src/lalr.c, diff --git a/NEWS b/NEWS index 0d083b56..e4acf388 100644 --- a/NEWS +++ b/NEWS @@ -73,7 +73,7 @@ Changes in version 1.49b: * Semantic parser This old option, which has been broken for ages, is removed. -* New translations +* New translation Croatian, thanks to Denis Lackovic. * Incorrect token definitions @@ -87,9 +87,14 @@ Changes in version 1.49b: * Reports In addition to --verbose, bison supports --report=THINGS, which produces additional information: - - `itemset' complete the core item sets with their closure - `lookahead' explicitly associate lookaheads to items + - itemset + complete the core item sets with their closure + - lookahead + explicitly associate lookaheads to items + - solved + describe shift/reduce conflicts solving. + Bison used to systematically output this information on top of + the report. Solved conflicts are now attached to their states. Changes in version 1.35, 2002-03-25: diff --git a/TODO b/TODO index 89c5a070..607366b3 100644 --- a/TODO +++ b/TODO @@ -40,22 +40,6 @@ When implementing multiple-%union support, bare the following in mind: Provide better assistance for understanding the conflicts by providing a sample text exhibiting the (LALR) ambiguity. -* report -Solved conflicts should not be reported in the beginning of the file. -Rather they should be reported within each state description. Also, -now that the symbol providing the precedence of a rule is kept, it is -possible to explain why a conflict was solved this way. E.g., instead -of - - Conflict in state 8 between rule 2 and token '+' resolved as reduce. - -we can (in state 8) report something like - - Conflict between rule 2 and token '+' resolved as reduce - because '*' < '+'. - -or something like that. - * Coding system independence Paul notes: diff --git a/src/LR0.c b/src/LR0.c index 269a8b87..efe9589a 100644 --- a/src/LR0.c +++ b/src/LR0.c @@ -200,8 +200,9 @@ new_state (symbol_number_t symbol, size_t core_size, item_number_t *core) p = STATE_ALLOC (core_size); p->accessing_symbol = symbol; p->number = nstates; - p->nitems = core_size; + p->solved_conflicts = NULL; + p->nitems = core_size; memcpy (p->items, core, core_size * sizeof (core[0])); /* If this is the eoftoken, and this is not the initial state, then diff --git a/src/conflicts.c b/src/conflicts.c index df3c931d..0ba2e5ac 100644 --- a/src/conflicts.c +++ b/src/conflicts.c @@ -35,22 +35,93 @@ /* -1 stands for not specified. */ int expected_conflicts = -1; static char *conflicts = NULL; +struct obstack solved_conflicts_obstack; static bitset shiftset; static bitset lookaheadset; + +enum conflict_resolution_e + { + shift_resolution, + reduce_resolution, + left_resolution, + right_resolution, + nonassoc_resolution, + }; + + static inline void -log_resolution (state_t *state, int LAno, int token, const char *resolution) +log_resolution (int lookahead, int token, + enum conflict_resolution_e resolution) { - if (report_flag & report_states) - obstack_fgrow4 (&output_obstack, - _("\ -Conflict in state %d between rule %d and token %s resolved as %s.\n"), - state->number, - LArule[LAno]->number, - symbols[token]->tag, - resolution); + if (report_flag & report_solved_conflicts) + { + /* The description of the resolution. */ + switch (resolution) + { + case shift_resolution: + case left_resolution: + obstack_fgrow2 (&solved_conflicts_obstack, + _("\ + Conflict between rule %d and token %s resolved as shift"), + LArule[lookahead]->number, + symbols[token]->tag); + break; + case reduce_resolution: + case right_resolution: + obstack_fgrow2 (&solved_conflicts_obstack, + _("\ + Conflict between rule %d and token %s resolved as reduce"), + LArule[lookahead]->number, + symbols[token]->tag); + break; + case nonassoc_resolution: + obstack_fgrow2 (&solved_conflicts_obstack, + _("\ + Conflict between rule %d and token %s resolved as an error"), + LArule[lookahead]->number, + symbols[token]->tag); + break; + } + + /* The reason. */ + switch (resolution) + { + case shift_resolution: + obstack_fgrow2 (&solved_conflicts_obstack, + " (%s < %s)", + LArule[lookahead]->prec->tag, + symbols[token]->tag); + break; + + case reduce_resolution: + obstack_fgrow2 (&solved_conflicts_obstack, + " (%s < %s)", + symbols[token]->tag, + LArule[lookahead]->prec->tag); + break; + + case left_resolution: + obstack_printf (&solved_conflicts_obstack, + " (%%left %s)", + symbols[token]->tag); + break; + + case right_resolution: + obstack_fgrow1 (&solved_conflicts_obstack, + " (%%right %s)", + symbols[token]->tag); + break; + case nonassoc_resolution: + obstack_fgrow1 (&solved_conflicts_obstack, + " (%%nonassoc %s)", + symbols[token]->tag); + break; + } + obstack_sgrow (&solved_conflicts_obstack, ".\n"); + } } @@ -112,12 +183,12 @@ resolve_sr_conflict (state_t *state, int lookahead) The precedence of shifting is that of token i. */ if (symbols[i]->prec < redprec) { - log_resolution (state, lookahead, i, _("reduce")); + log_resolution (lookahead, i, reduce_resolution); flush_shift (state, i); } else if (symbols[i]->prec > redprec) { - log_resolution (state, lookahead, i, _("shift")); + log_resolution (lookahead, i, shift_resolution); flush_reduce (lookahead, i); } else @@ -129,17 +200,17 @@ resolve_sr_conflict (state_t *state, int lookahead) switch (symbols[i]->assoc) { case right_assoc: - log_resolution (state, lookahead, i, _("shift")); + log_resolution (lookahead, i, right_resolution); flush_reduce (lookahead, i); break; case left_assoc: - log_resolution (state, lookahead, i, _("reduce")); + log_resolution (lookahead, i, left_resolution); flush_shift (state, i); break; case non_assoc: - log_resolution (state, lookahead, i, _("an error")); + log_resolution (lookahead, i, nonassoc_resolution); flush_shift (state, i); flush_reduce (lookahead, i); /* Record an explicit error for this token. */ @@ -152,6 +223,12 @@ resolve_sr_conflict (state_t *state, int lookahead) permanent errs structure for this state, to record them. */ state->errs = errs_dup (errp); free (errp); + + if (obstack_object_size (&solved_conflicts_obstack)) + { + obstack_1grow (&solved_conflicts_obstack, '\0'); + state->solved_conflicts = obstack_finish (&solved_conflicts_obstack); + } } @@ -195,13 +272,14 @@ set_conflicts (state_t *state) } void -solve_conflicts (void) +conflicts_solve (void) { size_t i; conflicts = XCALLOC (char, nstates); shiftset = bitset_create (ntokens, BITSET_FIXED); lookaheadset = bitset_create (ntokens, BITSET_FIXED); + obstack_init (&solved_conflicts_obstack); for (i = 0; i < nstates; i++) set_conflicts (states[i]); @@ -393,9 +471,10 @@ conflicts_print (void) void -free_conflicts (void) +conflicts_free (void) { XFREE (conflicts); bitset_free (shiftset); bitset_free (lookaheadset); + obstack_free (&solved_conflicts_obstack, NULL); } diff --git a/src/conflicts.h b/src/conflicts.h index 10f4d7ee..bd21253e 100644 --- a/src/conflicts.h +++ b/src/conflicts.h @@ -1,5 +1,5 @@ /* Find and resolve or report look-ahead conflicts for bison, - Copyright 2000, 2001 Free Software Foundation, Inc. + Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -22,10 +22,10 @@ # define CONFLICTS_H_ # include "state.h" -void solve_conflicts PARAMS ((void)); +void conflicts_solve PARAMS ((void)); void conflicts_print PARAMS ((void)); void conflicts_output PARAMS ((FILE *out)); -void free_conflicts PARAMS ((void)); +void conflicts_free PARAMS ((void)); /* Were there conflicts? */ extern int expected_conflicts; diff --git a/src/getargs.c b/src/getargs.c index 25d042ce..b4f160f0 100644 --- a/src/getargs.c +++ b/src/getargs.c @@ -55,6 +55,7 @@ static const char * const report_args[] = "state", "states", "itemset", "itemsets", "lookahead", "lookaheads", + "solved", "all", 0 }; @@ -65,6 +66,7 @@ static const int report_types[] = report_states, report_states, report_states | report_itemsets, report_states | report_itemsets, report_states | report_lookaheads, report_states | report_lookaheads, + report_states | report_solved_conflicts, report_all }; @@ -140,6 +142,7 @@ THINGS is a list of comma separated words that can include:\n\ `state' describe the states\n\ `itemset' complete the core item sets with their closure\n\ `lookahead' explicitly associate lookaheads to items\n\ + `solved' describe shift/reduce conflicts solving\n\ `all' include all the above information\n\ `none' disable the report\n\ "), stream); diff --git a/src/getargs.h b/src/getargs.h index 76feac2d..8b0de9a4 100644 --- a/src/getargs.h +++ b/src/getargs.h @@ -43,6 +43,7 @@ enum report_states = 1 << 0, report_itemsets = 1 << 1, report_lookaheads = 1 << 2, + report_solved_conflicts = 1 << 3, report_all = ~0 }; diff --git a/src/main.c b/src/main.c index d9461cc4..c0faa97a 100644 --- a/src/main.c +++ b/src/main.c @@ -84,7 +84,7 @@ main (int argc, char *argv[]) lookahead is not enough to disambiguate the parsing. In file conflicts. Also resolve s/r conflicts based on precedence declarations. */ - solve_conflicts (); + conflicts_solve (); conflicts_print (); /* Output file names. */ @@ -107,7 +107,7 @@ main (int argc, char *argv[]) output (); reduce_free (); - free_conflicts (); + conflicts_free (); free_nullable (); free_derives (); grammar_free (); diff --git a/src/print.c b/src/print.c index b99c233d..d8a4f008 100644 --- a/src/print.c +++ b/src/print.c @@ -364,6 +364,9 @@ print_state (FILE *out, state_t *state) fputs ("\n\n", out); print_core (out, state); print_actions (out, state); + if ((report_flag & report_solved_conflicts) + && state->solved_conflicts) + fputs (state->solved_conflicts, out); fputs ("\n\n", out); } diff --git a/src/state.h b/src/state.h index c2282474..95b716d8 100644 --- a/src/state.h +++ b/src/state.h @@ -184,7 +184,12 @@ typedef struct state_s short lookaheadsp; int nlookaheads; - /* Its items. */ + /* If some conflicts were solved thanks to precedence/associativity, + a human readable description of the resolution. */ + const char *solved_conflicts; + + /* Its items. Must be last, since ITEMS can be arbitrarily large. + */ unsigned short nitems; item_number_t items[1]; } state_t; diff --git a/tests/conflicts.at b/tests/conflicts.at index e436311f..6d546783 100644 --- a/tests/conflicts.at +++ b/tests/conflicts.at @@ -136,7 +136,7 @@ AT_DATA([input.y], exp: exp OP exp | NUM; ]]) -AT_CHECK([bison input.y -o input.c -v], 0, [], +AT_CHECK([bison input.y -o input.c --report=all], 0, [], [input.y contains 1 shift/reduce conflict. ]) @@ -172,6 +172,8 @@ exp (6) state 0 $axiom -> . exp $ (rule 0) + exp -> . exp OP exp (rule 1) + exp -> . NUM (rule 2) NUM shift, and go to state 1 @@ -206,7 +208,9 @@ state 3 state 4 + exp -> . exp OP exp (rule 1) exp -> exp OP . exp (rule 1) + exp -> . NUM (rule 2) NUM shift, and go to state 1 @@ -216,8 +220,8 @@ state 4 state 5 - exp -> exp . OP exp (rule 1) - exp -> exp OP exp . (rule 1) + exp -> exp . OP exp [$, OP] (rule 1) + exp -> exp OP exp . [$, OP] (rule 1) OP shift, and go to state 4 @@ -244,14 +248,11 @@ AT_DATA([input.y], exp: exp OP exp | NUM; ]]) -AT_CHECK([bison input.y -o input.c -v], 0, [], []) +AT_CHECK([bison input.y -o input.c --report=all], 0, [], []) # Check the contents of the report. AT_CHECK([cat input.output], [], -[[Conflict in state 5 between rule 2 and token OP resolved as shift. - - -Grammar +[[Grammar Number, Line, Rule 0 4 $axiom -> exp $ @@ -278,6 +279,8 @@ exp (6) state 0 $axiom -> . exp $ (rule 0) + exp -> . exp OP exp (rule 1) + exp -> . NUM (rule 2) NUM shift, and go to state 1 @@ -312,7 +315,9 @@ state 3 state 4 + exp -> . exp OP exp (rule 1) exp -> exp OP . exp (rule 1) + exp -> . NUM (rule 2) NUM shift, and go to state 1 @@ -322,13 +327,14 @@ state 4 state 5 - exp -> exp . OP exp (rule 1) - exp -> exp OP exp . (rule 1) + exp -> exp . OP exp [$] (rule 1) + exp -> exp OP exp . [$] (rule 1) OP shift, and go to state 4 $default reduce using rule 1 (exp) + Conflict between rule 2 and token OP resolved as reduce (%right OP). ]]) -- 2.45.2