From b34b12c4f9b920ffcfb9f94ce7a894afa3ba8fed Mon Sep 17 00:00:00 2001 From: Paul Hilfinger Date: Tue, 26 Feb 2013 16:28:36 -0800 Subject: allow %expect and %expect-rr modifiers on individual rules This change allows one to document (and check) which rules participate in shift/reduce and reduce/reduce conflicts. This is particularly important GLR parsers, where conflicts are a normal occurrence. For example, %glr-parser %expect 1 %% ... argument_list: arguments %expect 1 | arguments ',' | %empty ; arguments: expression | argument_list ',' expression ; ... Looking at the output from -v, one can see that the shift-reduce conflict here is due to the fact that the parser does not know whether to reduce arguments to argument_list until it sees the token AFTER the following ','. By marking the rule with %expect 1 (because there is a conflict in one state), we document the source of the 1 overall shift- reduce conflict. In GLR parsers, we can use %expect-rr in a rule for reduce/reduce conflicts. In this case, we mark each of the conflicting rules. For example, %glr-parser %expect-rr 1 %% stmt: target_list '=' expr ';' | expr_list ';' ; target_list: target | target ',' target_list ; target: ID %expect-rr 1 ; expr_list: expr | expr ',' expr_list ; expr: ID %expect-rr 1 | ... ; In a statement such as x, y = 3, 4; the parser must reduce x to a target or an expr, but does not know which until it sees the '='. So we notate the two possible reductions to indicate that each conflicts in one rule. See https://lists.gnu.org/archive/html/bison-patches/2013-02/msg00105.html. * doc/bison.texi (Suppressing Conflict Warnings): Document %expect, %expect-rr in grammar rules. * src/conflicts.c (count_state_rr_conflicts): Adjust comment. (rule_has_state_sr_conflicts): New static function. (count_rule_sr_conflicts): New static function. (rule_nast_state_rr_conflicts): New static function. (count_rule_rr_conflicts): New static function. (rule_conflicts_print): New static function. (conflicts_print): Also use rule_conflicts_print to report on individual rules. * src/gram.h (struct rule): Add new fields expected_sr_conflicts, expected_rr_conflicts. * src/reader.c (grammar_midrule_action): Transfer expected_sr_conflicts, expected_rr_conflicts to new rule, and turn off in current_rule. (grammar_current_rule_expect_sr): New function. (grammar_current_rule_expect_rr): New function. (packgram): Transfer expected_sr_conflicts, expected_rr_conflicts to new rule. * src/reader.h (grammar_current_rule_expect_sr): New function. (grammar_current_rule_expect_rr): New function. * src/symlist.c (symbol_list_sym_new): Initialize expected_sr_conflicts, expected_rr_conflicts. * src/symlist.h (struct symbol_list): Add new fields expected_sr_conflicts, expected_rr_conflicts. * tests/conflicts.at: Add tests "%expect in grammar rule not enough", "%expect in grammar rule right.", "%expect in grammar rule too much." --- src/conflicts.c | 123 +++++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 117 insertions(+), 6 deletions(-) (limited to 'src/conflicts.c') diff --git a/src/conflicts.c b/src/conflicts.c index 6a6f88d9..d57b7231 100644 --- a/src/conflicts.c +++ b/src/conflicts.c @@ -470,8 +470,8 @@ count_sr_conflicts (void) /*----------------------------------------------------------------. | Count the number of reduce/reduce conflicts. If ONE_PER_TOKEN, | | count one conflict for each token that has any reduce/reduce | -| conflicts. Otherwise, count one conflict for each pair of | -| conflicting reductions. | +| conflicts. Otherwise, count one conflict for each reduction | +| after the first for a given token. | `----------------------------------------------------------------*/ static size_t @@ -504,6 +504,86 @@ count_rr_conflicts (bool one_per_token) } +/*----------------------------------------------------------------------. +| For a given rule, count the number of states for which it is involved | +| in shift/reduce conflicts. | +`----------------------------------------------------------------------*/ + +static bool +rule_has_state_sr_conflicts (rule *r, state *s) +{ + int i; + int j; + transitions *trans = s->transitions; + reductions *reds = s->reductions; + + for (i = 0; i < reds->num; i++) + if (reds->rules[i] == r) + break; + if (i >= reds->num) + return false; + + FOR_EACH_SHIFT (trans, j) + if (bitset_test (reds->lookahead_tokens[i], TRANSITION_SYMBOL (trans, j))) + return true; + + return false; +} + +static size_t +count_rule_sr_conflicts (rule *r) +{ + state_number i; + size_t res; + + res = 0; + for (i = 0; i < nstates; i++) + if (conflicts[i] && rule_has_state_sr_conflicts (r, states[i])) + res++; + return res; +} + +/*-----------------------------------------------------------------. +| For a given rule, count the number of states in which it is | +| involved in reduce/reduce conflicts. | +`-----------------------------------------------------------------*/ + +static bool +rule_has_state_rr_conflicts (rule *r, state *s) +{ + int i; + reductions *reds = s->reductions; + size_t res; + bitset lookaheads; + + for (i = 0; i < reds->num; i++) + if (reds->rules[i] == r) + break; + if (i >= reds->num) + return 0; + lookaheads = reds->lookahead_tokens[i]; + + for (i = 0; i < reds->num; i++) + if (reds->rules[i] != r && + !bitset_disjoint_p (lookaheads, reds->lookahead_tokens[i])) + return true; + + return false; +} + +static size_t +count_rule_rr_conflicts (rule *r) +{ + state_number i; + size_t res; + + res = 0; + for (i = 0; i < nstates; i++) + if (conflicts[i] && rule_has_state_rr_conflicts (r, states[i])) + res++; + return res; +} + /*-----------------------------------------------------------. | Output the detailed description of states with conflicts. | `-----------------------------------------------------------*/ @@ -548,14 +628,46 @@ conflicts_total_count (void) return count_sr_conflicts () + count_rr_conflicts (false); } +/*------------------------------. +| Reporting per-rule conflicts. | +`------------------------------*/ -/*------------------------------------------. -| Reporting the total number of conflicts. | -`------------------------------------------*/ +static void +rule_conflicts_print (void) +{ + rule_number i; + + for (i = 0; i < nrules; i += 1) + { + rule *r = &rules[i]; + int expected_sr = r->expected_sr_conflicts; + int expected_rr = r->expected_rr_conflicts; + + if (expected_sr != -1 || expected_rr != -1) + { + int sr = count_rule_sr_conflicts (r); + int rr = count_rule_rr_conflicts (r); + if (sr != expected_sr && (sr != 0 || expected_sr != -1)) + complain (&r->location, complaint, _("\ +shift/reduce conflicts for rule %d: %d found, %d expected"), + r->user_number, sr, expected_sr); + if (rr != expected_rr && (rr != 0 || expected_rr != -1)) + complain (&r->location, complaint, _("\ +reduce/reduce conflicts for rule %d: %d found, %d expected"), + r->user_number, rr, expected_rr); + } + } +} + +/*---------------------------------. +| Reporting numbers of conflicts. | +`---------------------------------*/ void conflicts_print (void) { + rule_conflicts_print (); + if (! glr_parser && expected_rr_conflicts != -1) { complain (NULL, Wother, _("%%expect-rr applies only to GLR parsers")); @@ -609,7 +721,6 @@ conflicts_print (void) } } - void conflicts_free (void) { -- cgit v1.2.1