diff options
author | Paul Hilfinger <hilfingr@eecs.berkeley.edu> | 2013-02-26 16:28:36 -0800 |
---|---|---|
committer | Akim Demaille <akim.demaille@gmail.com> | 2018-11-21 22:08:47 +0100 |
commit | b34b12c4f9b920ffcfb9f94ce7a894afa3ba8fed (patch) | |
tree | afeb6a189342746949cac34a0059b09343223df0 /src/conflicts.c | |
parent | 487a2a9ecae81a401e1eb613837cbeb02df45f6e (diff) | |
download | bison-b34b12c4f9b920ffcfb9f94ce7a894afa3ba8fed.tar.gz |
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."
Diffstat (limited to 'src/conflicts.c')
-rw-r--r-- | src/conflicts.c | 123 |
1 files changed, 117 insertions, 6 deletions
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) { |