I’m surprised (and somewhat disappointed) that there are no answers about this thread. I like Paul’s contribution a lot, and was expecting some comments.
Since none of the 0 responses were about critical issue I failed to see, I will install these patches in master (when the CI is done checking the one below). The previous email was about fixing the computation of per-rule SR conflicts. This one is about fixing the computation of the per-rule RR conflicts. In both cases ‘fixing’ might be an unfair way to describe the change: I find ‘my’ way to compute easier to understand that Paul’s, since when you sum them, you get the overall numbers of conflicts. It’s also easier for the human to compute, since you get the numbers of conflicts that you see in the *.output file. However, Paul’s computations might have advantages that I have not foreseen, or are more important than I think (e.g., robustness to changes in the lookahead sets). While I’m very happy with per-rule %expect (s/r), I’m not entirely satisfied with the current %expect-rr (r/r). More on this later. commit 6ca1b418e4ff6e5c7e61e00fb26b401b33d7cb1e Author: Akim Demaille <[email protected]> Date: Fri Nov 9 17:29:29 2018 +0100 %expect-rr: tune the number of conflicts per rule Currently on a grammar such as exp : a '1' | a '2' | a '3' | b '1' | b '2' | b '3' a: b: we count only one rr-conflict on the `b:` rule, i.e., we expect: b: %expect-rr 1 although there are 3 conflicts in total. That's because in the conflicted state we count only a single conflict, although there are three (one for each of the lookaheads: '1', '2', '3'). State 0 0 $accept: . exp $end 1 exp: . a '1' 2 | . a '2' 3 | . a '3' 4 | . b '1' 5 | . b '2' 6 | . b '3' 7 a: . %empty ['1', '2', '3'] 8 b: . %empty ['1', '2', '3'] '1' reduce using rule 7 (a) '1' [reduce using rule 8 (b)] '2' reduce using rule 7 (a) '2' [reduce using rule 8 (b)] '3' reduce using rule 7 (a) '3' [reduce using rule 8 (b)] $default reduce using rule 7 (a) exp go to state 1 a go to state 2 b go to state 3 See https://lists.gnu.org/archive/html/bison-patches/2013-02/msg00106.html. * src/conflicts.c (rule_has_state_rr_conflicts): Rename as... (count_rule_state_sr_conflicts): this. DWIM. (count_rule_rr_conflicts): Adjust. * tests/conflicts.at (%expect-rr in grammar rules) (%expect-rr too much in grammar rules) (%expect-rr not enough in grammar rules): New. diff --git a/src/conflicts.c b/src/conflicts.c index af67aaea..f081f2af 100644 --- a/src/conflicts.c +++ b/src/conflicts.c @@ -483,7 +483,7 @@ count_state_rr_conflicts (state *s) int count = 0; for (int j = 0; j < reds->num; ++j) count += bitset_test (reds->lookahead_tokens[j], i); - if (count >= 2) + if (2 <= count) res += count-1; } @@ -546,23 +546,25 @@ count_rule_sr_conflicts (rule *r) | involved in reduce/reduce conflicts. | `-----------------------------------------------------------------*/ -static bool -rule_has_state_rr_conflicts (rule *r, state *s) +static size_t +count_rule_state_rr_conflicts (rule *r, state *s) { - reductions *reds = s->reductions; + size_t res = 0; + const reductions *reds = s->reductions; + bitset lookaheads = bitset_create (ntokens, BITSET_FIXED); for (int i = 0; i < reds->num; ++i) if (reds->rules[i] == r) - { - bitset lookaheads = reds->lookahead_tokens[i]; - for (int j = 0; j < reds->num; ++j) - if (reds->rules[j] != r && - !bitset_disjoint_p (lookaheads, reds->lookahead_tokens[j])) - return true; - break; - } - - return false; + for (int j = 0; j < reds->num; ++j) + if (reds->rules[j] != r) + { + bitset_and (lookaheads, + reds->lookahead_tokens[i], + reds->lookahead_tokens[j]); + res += bitset_count (lookaheads); + } + bitset_free (lookaheads); + return res; } static size_t @@ -570,8 +572,7 @@ count_rule_rr_conflicts (rule *r) { size_t res = 0; for (state_number i = 0; i < nstates; ++i) - if (conflicts[i] && rule_has_state_rr_conflicts (r, states[i])) - res++; + res += count_rule_state_rr_conflicts (r, states[i]); return res; } diff --git a/tests/conflicts.at b/tests/conflicts.at index c5fd512f..bddd8b83 100644 --- a/tests/conflicts.at +++ b/tests/conflicts.at @@ -1318,6 +1318,89 @@ AT_BISON_CHECK([-o input.c input.y], 1, [], AT_CLEANUP +## ---------------------------- ## +## %expect-rr in grammar rule. ## +## ---------------------------- ## + +AT_SETUP([%expect-rr in grammar rule]) + +AT_DATA([input.y], +[[%glr-parser +%expect-rr 3 +%% +exp +: a '1' +| a '2' +| a '3' +| b '1' +| b '2' +| b '3' +a: +b: %expect-rr 3 +]]) + +AT_BISON_CHECK([-o input.c input.y]) +AT_CLEANUP + + +## ------------------------------------- ## +## %expect-rr too much in grammar rule. ## +## ------------------------------------- ## + +AT_SETUP([%expect-rr too much in grammar rule]) + +AT_DATA([input.y], +[[%glr-parser +%expect-rr 3 +%% +exp +: a '1' +| a '2' +| a '3' +| b '1' +| b '2' +| b '3' +a: +b: %expect-rr 4 +]]) + +AT_BISON_CHECK([-fcaret -o input.c input.y], 1, [], +[[input.y:12.4-15: error: reduce/reduce conflicts for rule 8: 3 found, 4 expected + b: %expect-rr 4 + ^^^^^^^^^^^^ +]]) +AT_CLEANUP + + +## --------------------------------------- ## +## %expect-rr not enough in grammar rule. ## +## --------------------------------------- ## + +AT_SETUP([%expect-rr not enough in grammar rule]) + +AT_DATA([input.y], +[[%glr-parser +%expect-rr 3 +%% +exp +: a '1' +| a '2' +| a '3' +| b '1' +| b '2' +| b '3' +a: +b: %expect-rr 2 +]]) + +AT_BISON_CHECK([-fcaret -o input.c input.y], 1, [], +[[input.y:12.4-15: error: reduce/reduce conflicts for rule 8: 3 found, 2 expected + b: %expect-rr 2 + ^^^^^^^^^^^^ +]]) +AT_CLEANUP + + ## ------------------------- ## ## %prec with user strings. ## ## ------------------------- ##
