| /* Find and resolve or report lookahead conflicts for bison, |
| |
| Copyright (C) 1984, 1989, 1992, 2000-2015, 2018-2019 Free Software |
| Foundation, Inc. |
| |
| This file is part of Bison, the GNU Compiler Compiler. |
| |
| This program is free software: you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation, either version 3 of the License, or |
| (at your option) any later version. |
| |
| This program is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
| |
| #include <config.h> |
| #include "system.h" |
| |
| #include <bitset.h> |
| |
| #include "complain.h" |
| #include "conflicts.h" |
| #include "files.h" |
| #include "getargs.h" |
| #include "gram.h" |
| #include "lalr.h" |
| #include "lr0.h" |
| #include "print-xml.h" |
| #include "reader.h" |
| #include "state.h" |
| #include "symtab.h" |
| |
| /* -1 stands for not specified. */ |
| int expected_sr_conflicts = -1; |
| int expected_rr_conflicts = -1; |
| |
| /* CONFLICTS[STATE-NUM] -- Whether that state has unresolved conflicts. */ |
| static bool *conflicts; |
| |
| static struct obstack solved_conflicts_obstack; |
| static struct obstack solved_conflicts_xml_obstack; |
| |
| static bitset shift_set; |
| static bitset lookahead_set; |
| |
| |
| |
| enum conflict_resolution |
| { |
| shift_resolution, |
| reduce_resolution, |
| left_resolution, |
| right_resolution, |
| nonassoc_resolution |
| }; |
| |
| |
| /*----------------------------------------------------------------. |
| | Explain how an SR conflict between TOKEN and RULE was resolved: | |
| | RESOLUTION. | |
| `----------------------------------------------------------------*/ |
| |
| static inline void |
| log_resolution (rule *r, symbol_number token, |
| enum conflict_resolution resolution) |
| { |
| if (report_flag & report_solved_conflicts) |
| { |
| /* The description of the resolution. */ |
| switch (resolution) |
| { |
| case shift_resolution: |
| case right_resolution: |
| obstack_sgrow (&solved_conflicts_obstack, " "); |
| obstack_printf (&solved_conflicts_obstack, |
| _("Conflict between rule %d and token %s" |
| " resolved as shift"), |
| r->number, |
| symbols[token]->tag); |
| break; |
| |
| case reduce_resolution: |
| case left_resolution: |
| obstack_sgrow (&solved_conflicts_obstack, " "); |
| obstack_printf (&solved_conflicts_obstack, |
| _("Conflict between rule %d and token %s" |
| " resolved as reduce"), |
| r->number, |
| symbols[token]->tag); |
| break; |
| |
| case nonassoc_resolution: |
| obstack_sgrow (&solved_conflicts_obstack, " "); |
| obstack_printf (&solved_conflicts_obstack, |
| _("Conflict between rule %d and token %s" |
| " resolved as an error"), |
| r->number, |
| symbols[token]->tag); |
| break; |
| } |
| |
| /* The reason. */ |
| switch (resolution) |
| { |
| case shift_resolution: |
| obstack_printf (&solved_conflicts_obstack, |
| " (%s < %s)", |
| r->prec->symbol->tag, |
| symbols[token]->tag); |
| break; |
| |
| case reduce_resolution: |
| obstack_printf (&solved_conflicts_obstack, |
| " (%s < %s)", |
| symbols[token]->tag, |
| r->prec->symbol->tag); |
| break; |
| |
| case left_resolution: |
| obstack_printf (&solved_conflicts_obstack, |
| " (%%left %s)", |
| symbols[token]->tag); |
| break; |
| |
| case right_resolution: |
| obstack_printf (&solved_conflicts_obstack, |
| " (%%right %s)", |
| symbols[token]->tag); |
| break; |
| |
| case nonassoc_resolution: |
| obstack_printf (&solved_conflicts_obstack, |
| " (%%nonassoc %s)", |
| symbols[token]->tag); |
| break; |
| } |
| |
| obstack_sgrow (&solved_conflicts_obstack, ".\n"); |
| } |
| |
| /* XML report */ |
| if (xml_flag) |
| { |
| /* The description of the resolution. */ |
| switch (resolution) |
| { |
| case shift_resolution: |
| case right_resolution: |
| obstack_printf (&solved_conflicts_xml_obstack, |
| " <resolution rule=\"%d\" symbol=\"%s\"" |
| " type=\"shift\">", |
| r->number, |
| xml_escape (symbols[token]->tag)); |
| break; |
| |
| case reduce_resolution: |
| case left_resolution: |
| obstack_printf (&solved_conflicts_xml_obstack, |
| " <resolution rule=\"%d\" symbol=\"%s\"" |
| " type=\"reduce\">", |
| r->number, |
| xml_escape (symbols[token]->tag)); |
| break; |
| |
| case nonassoc_resolution: |
| obstack_printf (&solved_conflicts_xml_obstack, |
| " <resolution rule=\"%d\" symbol=\"%s\"" |
| " type=\"error\">", |
| r->number, |
| xml_escape (symbols[token]->tag)); |
| break; |
| } |
| |
| /* The reason. */ |
| switch (resolution) |
| { |
| case shift_resolution: |
| obstack_printf (&solved_conflicts_xml_obstack, |
| "%s < %s", |
| xml_escape_n (0, r->prec->symbol->tag), |
| xml_escape_n (1, symbols[token]->tag)); |
| break; |
| |
| case reduce_resolution: |
| obstack_printf (&solved_conflicts_xml_obstack, |
| "%s < %s", |
| xml_escape_n (0, symbols[token]->tag), |
| xml_escape_n (1, r->prec->symbol->tag)); |
| break; |
| |
| case left_resolution: |
| obstack_printf (&solved_conflicts_xml_obstack, |
| "%%left %s", |
| xml_escape (symbols[token]->tag)); |
| break; |
| |
| case right_resolution: |
| obstack_printf (&solved_conflicts_xml_obstack, |
| "%%right %s", |
| xml_escape (symbols[token]->tag)); |
| break; |
| |
| case nonassoc_resolution: |
| obstack_printf (&solved_conflicts_xml_obstack, |
| "%%nonassoc %s", |
| xml_escape (symbols[token]->tag)); |
| break; |
| } |
| |
| obstack_sgrow (&solved_conflicts_xml_obstack, "</resolution>\n"); |
| } |
| } |
| |
| |
| /*------------------------------------------------------------------. |
| | 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 or as an error (%nonassoc). | |
| `------------------------------------------------------------------*/ |
| |
| static void |
| flush_shift (state *s, int token) |
| { |
| transitions *trans = s->transitions; |
| |
| bitset_reset (lookahead_set, token); |
| for (int i = 0; i < trans->num; ++i) |
| if (!TRANSITION_IS_DISABLED (trans, i) |
| && TRANSITION_SYMBOL (trans, i) == token) |
| TRANSITION_DISABLE (trans, i); |
| } |
| |
| |
| /*--------------------------------------------------------------------. |
| | 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 |
| flush_reduce (bitset lookahead_tokens, int token) |
| { |
| bitset_reset (lookahead_tokens, token); |
| } |
| |
| |
| /*------------------------------------------------------------------. |
| | Attempt to resolve shift-reduce conflict for one rule by means of | |
| | precedence declarations. It has already been checked that the | |
| | rule has a precedence. A conflict is resolved by modifying the | |
| | shift or reduce tables so that there is no longer a conflict. | |
| | | |
| | RULENO is the number of the lookahead bitset to consider. | |
| | | |
| | ERRORS and NERRS can be used to store discovered explicit | |
| | errors. | |
| `------------------------------------------------------------------*/ |
| |
| static void |
| resolve_sr_conflict (state *s, int ruleno, symbol **errors, int *nerrs) |
| { |
| reductions *reds = s->reductions; |
| /* Find the rule to reduce by to get precedence of reduction. */ |
| rule *redrule = reds->rules[ruleno]; |
| int redprec = redrule->prec->prec; |
| bitset lookahead_tokens = reds->lookahead_tokens[ruleno]; |
| |
| for (symbol_number i = 0; i < ntokens; ++i) |
| if (bitset_test (lookahead_tokens, i) |
| && bitset_test (lookahead_set, i) |
| && symbols[i]->content->prec) |
| { |
| /* Shift-reduce conflict occurs for token number i |
| and it has a precedence. |
| The precedence of shifting is that of token i. */ |
| if (symbols[i]->content->prec < redprec) |
| { |
| register_precedence (redrule->prec->number, i); |
| log_resolution (redrule, i, reduce_resolution); |
| flush_shift (s, i); |
| } |
| else if (symbols[i]->content->prec > redprec) |
| { |
| register_precedence (i, redrule->prec->number); |
| log_resolution (redrule, i, shift_resolution); |
| flush_reduce (lookahead_tokens, i); |
| } |
| else |
| /* Matching precedence levels. |
| For non-defined associativity, keep both: unexpected |
| associativity conflict. |
| For left associativity, keep only the reduction. |
| For right associativity, keep only the shift. |
| For nonassociativity, keep neither. */ |
| |
| switch (symbols[i]->content->assoc) |
| { |
| case undef_assoc: |
| abort (); |
| |
| case precedence_assoc: |
| break; |
| |
| case right_assoc: |
| register_assoc (i, redrule->prec->number); |
| log_resolution (redrule, i, right_resolution); |
| flush_reduce (lookahead_tokens, i); |
| break; |
| |
| case left_assoc: |
| register_assoc (i, redrule->prec->number); |
| log_resolution (redrule, i, left_resolution); |
| flush_shift (s, i); |
| break; |
| |
| case non_assoc: |
| register_assoc (i, redrule->prec->number); |
| log_resolution (redrule, i, nonassoc_resolution); |
| flush_shift (s, i); |
| flush_reduce (lookahead_tokens, i); |
| /* Record an explicit error for this token. */ |
| errors[(*nerrs)++] = symbols[i]; |
| break; |
| } |
| } |
| } |
| |
| |
| /*-------------------------------------------------------------------. |
| | Solve the S/R conflicts of state S using the | |
| | precedence/associativity, and flag it inconsistent if it still has | |
| | conflicts. ERRORS can be used as storage to compute the list of | |
| | lookahead tokens on which S raises a syntax error (%nonassoc). | |
| `-------------------------------------------------------------------*/ |
| |
| static void |
| set_conflicts (state *s, symbol **errors) |
| { |
| if (s->consistent) |
| return; |
| |
| reductions *reds = s->reductions; |
| int nerrs = 0; |
| |
| bitset_zero (lookahead_set); |
| |
| { |
| transitions *trans = s->transitions; |
| int i; |
| FOR_EACH_SHIFT (trans, i) |
| bitset_set (lookahead_set, TRANSITION_SYMBOL (trans, i)); |
| } |
| |
| /* Loop over all rules which require lookahead in this state. First |
| check for shift-reduce conflict, and try to resolve using |
| precedence. */ |
| for (int 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, &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)) |
| s->solved_conflicts = obstack_finish0 (&solved_conflicts_obstack); |
| if (obstack_object_size (&solved_conflicts_xml_obstack)) |
| s->solved_conflicts_xml = obstack_finish0 (&solved_conflicts_xml_obstack); |
| |
| /* Loop over all rules which require lookahead in this state. Check |
| for conflicts not resolved above. |
| |
| reds->lookahead_tokens can be NULL if the LR type is LR(0). */ |
| if (reds->lookahead_tokens) |
| for (int i = 0; i < reds->num; ++i) |
| { |
| if (!bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set)) |
| conflicts[s->number] = true; |
| bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]); |
| } |
| } |
| |
| |
| /*----------------------------------------------------------------. |
| | Solve all the S/R conflicts using the precedence/associativity, | |
| | and flag as inconsistent the states that still have conflicts. | |
| `----------------------------------------------------------------*/ |
| |
| void |
| conflicts_solve (void) |
| { |
| /* List of lookahead tokens on which we explicitly raise a syntax error. */ |
| symbol **errors = xnmalloc (ntokens + 1, sizeof *errors); |
| |
| conflicts = xcalloc (nstates, sizeof *conflicts); |
| shift_set = bitset_create (ntokens, BITSET_FIXED); |
| lookahead_set = bitset_create (ntokens, BITSET_FIXED); |
| obstack_init (&solved_conflicts_obstack); |
| obstack_init (&solved_conflicts_xml_obstack); |
| |
| for (state_number i = 0; i < nstates; ++i) |
| { |
| set_conflicts (states[i], errors); |
| |
| /* For uniformity of the code, make sure all the states have a valid |
| 'errs' member. */ |
| if (!states[i]->errs) |
| states[i]->errs = errs_new (0, 0); |
| } |
| |
| free (errors); |
| } |
| |
| |
| void |
| conflicts_update_state_numbers (state_number old_to_new[], |
| state_number nstates_old) |
| { |
| for (state_number i = 0; i < nstates_old; ++i) |
| if (old_to_new[i] != nstates_old) |
| conflicts[old_to_new[i]] = conflicts[i]; |
| } |
| |
| |
| /*---------------------------------------------. |
| | Count the number of shift/reduce conflicts. | |
| `---------------------------------------------*/ |
| |
| static size_t |
| count_state_sr_conflicts (const state *s) |
| { |
| transitions *trans = s->transitions; |
| reductions *reds = s->reductions; |
| |
| if (!trans) |
| return 0; |
| |
| bitset_zero (lookahead_set); |
| bitset_zero (shift_set); |
| |
| { |
| int i; |
| FOR_EACH_SHIFT (trans, i) |
| bitset_set (shift_set, TRANSITION_SYMBOL (trans, i)); |
| } |
| |
| for (int i = 0; i < reds->num; ++i) |
| bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]); |
| |
| bitset_and (lookahead_set, lookahead_set, shift_set); |
| |
| return bitset_count (lookahead_set); |
| } |
| |
| /*---------------------------------------------. |
| | The total number of shift/reduce conflicts. | |
| `---------------------------------------------*/ |
| |
| static size_t |
| count_sr_conflicts (void) |
| { |
| size_t res = 0; |
| /* Conflicts by state. */ |
| for (state_number i = 0; i < nstates; ++i) |
| if (conflicts[i]) |
| res += count_state_sr_conflicts (states[i]); |
| return res; |
| } |
| |
| |
| |
| /*-----------------------------------------------------------------. |
| | Count the number of reduce/reduce conflicts. Count one conflict | |
| | for each reduction after the first for a given token. | |
| `-----------------------------------------------------------------*/ |
| |
| static size_t |
| count_state_rr_conflicts (const state *s) |
| { |
| reductions *reds = s->reductions; |
| size_t res = 0; |
| |
| for (symbol_number i = 0; i < ntokens; ++i) |
| { |
| int count = 0; |
| for (int j = 0; j < reds->num; ++j) |
| count += bitset_test (reds->lookahead_tokens[j], i); |
| if (2 <= count) |
| res += count-1; |
| } |
| |
| return res; |
| } |
| |
| static size_t |
| count_rr_conflicts (void) |
| { |
| size_t res = 0; |
| /* Conflicts by state. */ |
| for (state_number i = 0; i < nstates; ++i) |
| if (conflicts[i]) |
| res += count_state_rr_conflicts (states[i]); |
| return res; |
| } |
| |
| |
| /*------------------------------------------------------------------. |
| | For a given rule, the number of shift/reduce conflicts in a given | |
| | state. | |
| `------------------------------------------------------------------*/ |
| |
| static size_t |
| count_rule_state_sr_conflicts (rule *r, state *s) |
| { |
| size_t res = 0; |
| transitions *trans = s->transitions; |
| reductions *reds = s->reductions; |
| |
| for (int i = 0; i < reds->num; ++i) |
| if (reds->rules[i] == r) |
| { |
| bitset lookaheads = reds->lookahead_tokens[i]; |
| int j; |
| FOR_EACH_SHIFT (trans, j) |
| res += bitset_test (lookaheads, TRANSITION_SYMBOL (trans, j)); |
| } |
| |
| return res; |
| } |
| |
| /*----------------------------------------------------------------------. |
| | For a given rule, count the number of states for which it is involved | |
| | in shift/reduce conflicts. | |
| `----------------------------------------------------------------------*/ |
| |
| static size_t |
| count_rule_sr_conflicts (rule *r) |
| { |
| size_t res = 0; |
| for (state_number i = 0; i < nstates; ++i) |
| if (conflicts[i]) |
| res += count_rule_state_sr_conflicts (r, states[i]); |
| return res; |
| } |
| |
| /*-----------------------------------------------------------------. |
| | For a given rule, count the number of states in which it is | |
| | involved in reduce/reduce conflicts. | |
| `-----------------------------------------------------------------*/ |
| |
| static size_t |
| count_rule_state_rr_conflicts (rule *r, state *s) |
| { |
| 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) |
| 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 |
| count_rule_rr_conflicts (rule *r) |
| { |
| size_t res = 0; |
| for (state_number i = 0; i < nstates; ++i) |
| res += count_rule_state_rr_conflicts (r, states[i]); |
| return res; |
| } |
| |
| /*-----------------------------------------------------------. |
| | Output the detailed description of states with conflicts. | |
| `-----------------------------------------------------------*/ |
| |
| void |
| conflicts_output (FILE *out) |
| { |
| bool printed_sth = false; |
| for (state_number i = 0; i < nstates; ++i) |
| if (conflicts[i]) |
| { |
| const state *s = states[i]; |
| int src = count_state_sr_conflicts (s); |
| int rrc = count_state_rr_conflicts (s); |
| fprintf (out, _("State %d "), i); |
| if (src && rrc) |
| fprintf (out, |
| _("conflicts: %d shift/reduce, %d reduce/reduce\n"), |
| src, rrc); |
| else if (src) |
| fprintf (out, _("conflicts: %d shift/reduce\n"), src); |
| else if (rrc) |
| fprintf (out, _("conflicts: %d reduce/reduce\n"), rrc); |
| printed_sth = true; |
| } |
| if (printed_sth) |
| fputs ("\n\n", out); |
| } |
| |
| /*--------------------------------------------. |
| | Total the number of S/R and R/R conflicts. | |
| `--------------------------------------------*/ |
| |
| int |
| conflicts_total_count (void) |
| { |
| return count_sr_conflicts () + count_rr_conflicts (); |
| } |
| |
| /*------------------------------. |
| | Reporting per-rule conflicts. | |
| `------------------------------*/ |
| |
| static void |
| rule_conflicts_print (void) |
| { |
| for (rule_number 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); |
| 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); |
| int rr = count_rule_rr_conflicts (r); |
| 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")); |
| expected_rr_conflicts = -1; |
| } |
| |
| /* Screams for factoring, but almost useless because of the |
| different strings to translate. */ |
| { |
| int total = count_sr_conflicts (); |
| /* If %expect is not used, but %expect-rr is, then expect 0 sr. */ |
| int expected = |
| (expected_sr_conflicts == -1 && expected_rr_conflicts != -1) |
| ? 0 |
| : expected_sr_conflicts; |
| if (expected != -1) |
| { |
| if (expected != total) |
| complain (NULL, complaint, |
| _("shift/reduce conflicts: %d found, %d expected"), |
| total, expected); |
| } |
| else if (total) |
| complain (NULL, Wconflicts_sr, |
| ngettext ("%d shift/reduce conflict", |
| "%d shift/reduce conflicts", |
| total), |
| total); |
| } |
| |
| { |
| int total = count_rr_conflicts (); |
| /* If %expect-rr is not used, but %expect is, then expect 0 rr. */ |
| int expected = |
| (expected_rr_conflicts == -1 && expected_sr_conflicts != -1) |
| ? 0 |
| : expected_rr_conflicts; |
| if (expected != -1) |
| { |
| if (expected != total) |
| complain (NULL, complaint, |
| _("reduce/reduce conflicts: %d found, %d expected"), |
| total, expected); |
| } |
| else if (total) |
| complain (NULL, Wconflicts_rr, |
| ngettext ("%d reduce/reduce conflict", |
| "%d reduce/reduce conflicts", |
| total), |
| total); |
| } |
| } |
| |
| void |
| conflicts_free (void) |
| { |
| free (conflicts); |
| bitset_free (shift_set); |
| bitset_free (lookahead_set); |
| obstack_free (&solved_conflicts_obstack, NULL); |
| obstack_free (&solved_conflicts_xml_obstack, NULL); |
| } |