1 /* Find and resolve or report lookahead conflicts for bison,
3 Copyright (C) 1984, 1989, 1992, 2000-2015, 2018-2022 Free Software
6 This file is part of Bison, the GNU Compiler Compiler.
8 This program is free software: you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program. If not, see <https://www.gnu.org/licenses/>. */
27 #include "conflicts.h"
28 #include "counterexample.h"
34 #include "print-xml.h"
39 /* -1 stands for not specified. */
40 int expected_sr_conflicts
= -1;
41 int expected_rr_conflicts
= -1;
43 /* CONFLICTS[STATE-NUM] -- Whether that state has unresolved conflicts. */
44 static bool *conflicts
;
46 static struct obstack solved_conflicts_obstack
;
47 static struct obstack solved_conflicts_xml_obstack
;
49 static bitset shift_set
;
50 static bitset lookahead_set
;
53 has_conflicts (const state
*s
)
55 return conflicts
[s
->number
];
60 enum conflict_resolution
70 /*----------------------------------------------------------------.
71 | Explain how an SR conflict between TOKEN and RULE was resolved: |
73 `----------------------------------------------------------------*/
76 log_resolution (rule
*r
, symbol_number token
,
77 enum conflict_resolution resolution
)
79 if (report_flag
& report_solved_conflicts
)
81 /* The description of the resolution. */
84 case shift_resolution
:
85 case right_resolution
:
86 obstack_sgrow (&solved_conflicts_obstack
, " ");
87 obstack_printf (&solved_conflicts_obstack
,
88 _("Conflict between rule %d and token %s"
89 " resolved as shift"),
94 case reduce_resolution
:
96 obstack_sgrow (&solved_conflicts_obstack
, " ");
97 obstack_printf (&solved_conflicts_obstack
,
98 _("Conflict between rule %d and token %s"
99 " resolved as reduce"),
101 symbols
[token
]->tag
);
104 case nonassoc_resolution
:
105 obstack_sgrow (&solved_conflicts_obstack
, " ");
106 obstack_printf (&solved_conflicts_obstack
,
107 _("Conflict between rule %d and token %s"
108 " resolved as an error"),
110 symbols
[token
]->tag
);
117 case shift_resolution
:
118 obstack_printf (&solved_conflicts_obstack
,
120 r
->prec
->symbol
->tag
,
121 symbols
[token
]->tag
);
124 case reduce_resolution
:
125 obstack_printf (&solved_conflicts_obstack
,
128 r
->prec
->symbol
->tag
);
131 case left_resolution
:
132 obstack_printf (&solved_conflicts_obstack
,
134 symbols
[token
]->tag
);
137 case right_resolution
:
138 obstack_printf (&solved_conflicts_obstack
,
140 symbols
[token
]->tag
);
143 case nonassoc_resolution
:
144 obstack_printf (&solved_conflicts_obstack
,
146 symbols
[token
]->tag
);
150 obstack_sgrow (&solved_conflicts_obstack
, ".\n");
156 /* The description of the resolution. */
159 case shift_resolution
:
160 case right_resolution
:
161 obstack_printf (&solved_conflicts_xml_obstack
,
162 " <resolution rule=\"%d\" symbol=\"%s\""
165 xml_escape (symbols
[token
]->tag
));
168 case reduce_resolution
:
169 case left_resolution
:
170 obstack_printf (&solved_conflicts_xml_obstack
,
171 " <resolution rule=\"%d\" symbol=\"%s\""
174 xml_escape (symbols
[token
]->tag
));
177 case nonassoc_resolution
:
178 obstack_printf (&solved_conflicts_xml_obstack
,
179 " <resolution rule=\"%d\" symbol=\"%s\""
182 xml_escape (symbols
[token
]->tag
));
189 case shift_resolution
:
190 obstack_printf (&solved_conflicts_xml_obstack
,
192 xml_escape_n (0, r
->prec
->symbol
->tag
),
193 xml_escape_n (1, symbols
[token
]->tag
));
196 case reduce_resolution
:
197 obstack_printf (&solved_conflicts_xml_obstack
,
199 xml_escape_n (0, symbols
[token
]->tag
),
200 xml_escape_n (1, r
->prec
->symbol
->tag
));
203 case left_resolution
:
204 obstack_printf (&solved_conflicts_xml_obstack
,
206 xml_escape (symbols
[token
]->tag
));
209 case right_resolution
:
210 obstack_printf (&solved_conflicts_xml_obstack
,
212 xml_escape (symbols
[token
]->tag
));
215 case nonassoc_resolution
:
216 obstack_printf (&solved_conflicts_xml_obstack
,
218 xml_escape (symbols
[token
]->tag
));
222 obstack_sgrow (&solved_conflicts_xml_obstack
, "</resolution>\n");
227 /*------------------------------------------------------------------.
228 | Turn off the shift recorded for the specified token in the |
229 | specified state. Used when we resolve a shift/reduce conflict in |
230 | favor of the reduction or as an error (%nonassoc). |
231 `------------------------------------------------------------------*/
234 flush_shift (state
*s
, int token
)
236 transitions
*trans
= s
->transitions
;
238 bitset_reset (lookahead_set
, token
);
239 for (int i
= 0; i
< trans
->num
; ++i
)
240 if (!TRANSITION_IS_DISABLED (trans
, i
)
241 && TRANSITION_SYMBOL (trans
, i
) == token
)
242 TRANSITION_DISABLE (trans
, i
);
246 /*--------------------------------------------------------------------.
247 | Turn off the reduce recorded for the specified token in the |
248 | specified lookahead set. Used when we resolve a shift/reduce |
249 | conflict in favor of the shift or as an error (%nonassoc). |
250 `--------------------------------------------------------------------*/
253 flush_reduce (bitset lookaheads
, int token
)
255 bitset_reset (lookaheads
, token
);
259 /*------------------------------------------------------------------.
260 | Attempt to resolve shift/reduce conflict for one rule by means of |
261 | precedence declarations. It has already been checked that the |
262 | rule has a precedence. A conflict is resolved by modifying the |
263 | shift or reduce tables so that there is no longer a conflict. |
265 | RULENO is the number of the lookahead bitset to consider. |
267 | ERRORS and NERRS can be used to store discovered explicit |
269 `------------------------------------------------------------------*/
272 resolve_sr_conflict (state
*s
, int ruleno
, symbol
**errors
, int *nerrs
)
274 reductions
*reds
= s
->reductions
;
275 /* Find the rule to reduce by to get precedence of reduction. */
276 rule
*redrule
= reds
->rules
[ruleno
];
277 int redprec
= redrule
->prec
->prec
;
278 bitset lookaheads
= reds
->lookaheads
[ruleno
];
280 for (symbol_number i
= 0; i
< ntokens
; ++i
)
281 if (bitset_test (lookaheads
, i
)
282 && bitset_test (lookahead_set
, i
)
283 && symbols
[i
]->content
->prec
)
285 /* Shift/reduce conflict occurs for token number i
286 and it has a precedence.
287 The precedence of shifting is that of token i. */
288 if (symbols
[i
]->content
->prec
< redprec
)
290 register_precedence (redrule
->prec
->number
, i
);
291 log_resolution (redrule
, i
, reduce_resolution
);
294 else if (symbols
[i
]->content
->prec
> redprec
)
296 register_precedence (i
, redrule
->prec
->number
);
297 log_resolution (redrule
, i
, shift_resolution
);
298 flush_reduce (lookaheads
, i
);
301 /* Matching precedence levels.
302 For non-defined associativity, keep both: unexpected
303 associativity conflict.
304 For left associativity, keep only the reduction.
305 For right associativity, keep only the shift.
306 For nonassociativity, keep neither. */
308 switch (symbols
[i
]->content
->assoc
)
313 case precedence_assoc
:
317 register_assoc (i
, redrule
->prec
->number
);
318 log_resolution (redrule
, i
, right_resolution
);
319 flush_reduce (lookaheads
, i
);
323 register_assoc (i
, redrule
->prec
->number
);
324 log_resolution (redrule
, i
, left_resolution
);
329 register_assoc (i
, redrule
->prec
->number
);
330 log_resolution (redrule
, i
, nonassoc_resolution
);
332 flush_reduce (lookaheads
, i
);
333 /* Record an explicit error for this token. */
334 errors
[(*nerrs
)++] = symbols
[i
];
341 /*-------------------------------------------------------------------.
342 | Solve the S/R conflicts of state S using the |
343 | precedence/associativity, and flag it inconsistent if it still has |
344 | conflicts. ERRORS can be used as storage to compute the list of |
345 | lookahead tokens on which S raises a syntax error (%nonassoc). |
346 `-------------------------------------------------------------------*/
349 set_conflicts (state
*s
, symbol
**errors
)
354 reductions
*reds
= s
->reductions
;
357 bitset_zero (lookahead_set
);
360 transitions
*trans
= s
->transitions
;
362 FOR_EACH_SHIFT (trans
, i
)
363 bitset_set (lookahead_set
, TRANSITION_SYMBOL (trans
, i
));
366 /* Loop over all rules which require lookahead in this state. First
367 check for shift/reduce conflict, and try to resolve using
369 for (int i
= 0; i
< reds
->num
; ++i
)
370 if (reds
->rules
[i
]->prec
371 && reds
->rules
[i
]->prec
->prec
372 && !bitset_disjoint_p (reds
->lookaheads
[i
], lookahead_set
))
373 resolve_sr_conflict (s
, i
, errors
, &nerrs
);
376 /* Some tokens have been explicitly made errors. Allocate a
377 permanent errs structure for this state, to record them. */
378 state_errs_set (s
, nerrs
, errors
);
380 if (obstack_object_size (&solved_conflicts_obstack
))
381 s
->solved_conflicts
= obstack_finish0 (&solved_conflicts_obstack
);
382 if (obstack_object_size (&solved_conflicts_xml_obstack
))
383 s
->solved_conflicts_xml
= obstack_finish0 (&solved_conflicts_xml_obstack
);
385 /* Loop over all rules which require lookahead in this state. Check
386 for conflicts not resolved above.
388 reds->lookaheads can be NULL if the LR type is LR(0). */
389 if (reds
->lookaheads
)
390 for (int i
= 0; i
< reds
->num
; ++i
)
392 if (!bitset_disjoint_p (reds
->lookaheads
[i
], lookahead_set
))
393 conflicts
[s
->number
] = true;
394 bitset_or (lookahead_set
, lookahead_set
, reds
->lookaheads
[i
]);
399 /*----------------------------------------------------------------.
400 | Solve all the S/R conflicts using the precedence/associativity, |
401 | and flag as inconsistent the states that still have conflicts. |
402 `----------------------------------------------------------------*/
405 conflicts_solve (void)
407 /* List of lookahead tokens on which we explicitly raise a syntax error. */
408 symbol
**errors
= xnmalloc (ntokens
+ 1, sizeof *errors
);
410 conflicts
= xcalloc (nstates
, sizeof *conflicts
);
411 shift_set
= bitset_create (ntokens
, BITSET_FIXED
);
412 lookahead_set
= bitset_create (ntokens
, BITSET_FIXED
);
413 obstack_init (&solved_conflicts_obstack
);
414 obstack_init (&solved_conflicts_xml_obstack
);
416 for (state_number i
= 0; i
< nstates
; ++i
)
418 set_conflicts (states
[i
], errors
);
420 /* For uniformity of the code, make sure all the states have a valid
422 if (!states
[i
]->errs
)
423 states
[i
]->errs
= errs_new (0, 0);
431 conflicts_update_state_numbers (state_number old_to_new
[],
432 state_number nstates_old
)
434 for (state_number i
= 0; i
< nstates_old
; ++i
)
435 if (old_to_new
[i
] != nstates_old
)
436 conflicts
[old_to_new
[i
]] = conflicts
[i
];
440 /*---------------------------------------------.
441 | Count the number of shift/reduce conflicts. |
442 `---------------------------------------------*/
445 count_state_sr_conflicts (const state
*s
)
447 transitions
*trans
= s
->transitions
;
448 reductions
*reds
= s
->reductions
;
453 bitset_zero (lookahead_set
);
454 bitset_zero (shift_set
);
458 FOR_EACH_SHIFT (trans
, i
)
459 bitset_set (shift_set
, TRANSITION_SYMBOL (trans
, i
));
462 for (int i
= 0; i
< reds
->num
; ++i
)
463 bitset_or (lookahead_set
, lookahead_set
, reds
->lookaheads
[i
]);
465 bitset_and (lookahead_set
, lookahead_set
, shift_set
);
467 return bitset_count (lookahead_set
);
470 /*---------------------------------------------.
471 | The total number of shift/reduce conflicts. |
472 `---------------------------------------------*/
475 count_sr_conflicts (void)
478 /* Conflicts by state. */
479 for (state_number i
= 0; i
< nstates
; ++i
)
481 res
+= count_state_sr_conflicts (states
[i
]);
487 /*-----------------------------------------------------------------.
488 | Count the number of reduce/reduce conflicts. Count one conflict |
489 | for each reduction after the first for a given token. |
490 `-----------------------------------------------------------------*/
493 count_state_rr_conflicts (const state
*s
)
495 reductions
*reds
= s
->reductions
;
498 for (symbol_number i
= 0; i
< ntokens
; ++i
)
501 for (int j
= 0; j
< reds
->num
; ++j
)
502 count
+= bitset_test (reds
->lookaheads
[j
], i
);
511 count_rr_conflicts (void)
514 /* Conflicts by state. */
515 for (state_number i
= 0; i
< nstates
; ++i
)
517 res
+= count_state_rr_conflicts (states
[i
]);
522 /*------------------------------------------------------------------.
523 | For a given rule, the number of shift/reduce conflicts in a given |
525 `------------------------------------------------------------------*/
528 count_rule_state_sr_conflicts (rule
*r
, state
*s
)
531 transitions
*trans
= s
->transitions
;
532 reductions
*reds
= s
->reductions
;
534 for (int i
= 0; i
< reds
->num
; ++i
)
535 if (reds
->rules
[i
] == r
)
537 bitset lookaheads
= reds
->lookaheads
[i
];
539 FOR_EACH_SHIFT (trans
, j
)
540 res
+= bitset_test (lookaheads
, TRANSITION_SYMBOL (trans
, j
));
546 /*----------------------------------------------------------------------.
547 | For a given rule, count the number of states for which it is involved |
548 | in shift/reduce conflicts. |
549 `----------------------------------------------------------------------*/
552 count_rule_sr_conflicts (rule
*r
)
555 for (state_number i
= 0; i
< nstates
; ++i
)
557 res
+= count_rule_state_sr_conflicts (r
, states
[i
]);
561 /*-----------------------------------------------------------------.
562 | For a given rule, count the number of states in which it is |
563 | involved in reduce/reduce conflicts. |
564 `-----------------------------------------------------------------*/
567 count_rule_state_rr_conflicts (rule
*r
, state
*s
)
570 const reductions
*reds
= s
->reductions
;
571 bitset lookaheads
= bitset_create (ntokens
, BITSET_FIXED
);
573 for (int i
= 0; i
< reds
->num
; ++i
)
574 if (reds
->rules
[i
] == r
)
575 for (int j
= 0; j
< reds
->num
; ++j
)
576 if (reds
->rules
[j
] != r
)
578 bitset_and (lookaheads
,
580 reds
->lookaheads
[j
]);
581 res
+= bitset_count (lookaheads
);
583 bitset_free (lookaheads
);
588 count_rule_rr_conflicts (rule
*r
)
591 for (state_number i
= 0; i
< nstates
; ++i
)
592 res
+= count_rule_state_rr_conflicts (r
, states
[i
]);
596 /*-----------------------------------------------------------.
597 | Output the detailed description of states with conflicts. |
598 `-----------------------------------------------------------*/
601 conflicts_output (FILE *out
)
603 bool printed_sth
= false;
604 for (state_number i
= 0; i
< nstates
; ++i
)
607 const state
*s
= states
[i
];
608 int src
= count_state_sr_conflicts (s
);
609 int rrc
= count_state_rr_conflicts (s
);
610 fprintf (out
, _("State %d "), i
);
613 _("conflicts: %d shift/reduce, %d reduce/reduce\n"),
616 fprintf (out
, _("conflicts: %d shift/reduce\n"), src
);
618 fprintf (out
, _("conflicts: %d reduce/reduce\n"), rrc
);
625 /*--------------------------------------------.
626 | Total the number of S/R and R/R conflicts. |
627 `--------------------------------------------*/
630 conflicts_total_count (void)
632 return count_sr_conflicts () + count_rr_conflicts ();
636 report_counterexamples (void)
638 for (state_number sn
= 0; sn
< nstates
; ++sn
)
640 counterexample_report_state (states
[sn
], stderr
, "");
643 /*------------------------------------------------.
644 | Report per-rule %expect/%expect-rr mismatches. |
645 `------------------------------------------------*/
648 report_rule_expectation_mismatches (void)
650 for (rule_number i
= 0; i
< nrules
; i
+= 1)
653 int expected_sr
= r
->expected_sr_conflicts
;
654 int expected_rr
= r
->expected_rr_conflicts
;
656 if (expected_sr
!= -1 || expected_rr
!= -1)
658 int sr
= count_rule_sr_conflicts (r
);
659 if (sr
!= expected_sr
&& (sr
!= 0 || expected_sr
!= -1))
660 complain (&r
->location
, complaint
,
661 _("shift/reduce conflicts for rule %d:"
662 " %d found, %d expected"),
663 r
->code
, sr
, expected_sr
);
664 int rr
= count_rule_rr_conflicts (r
);
665 if (rr
!= expected_rr
&& (rr
!= 0 || expected_rr
!= -1))
666 complain (&r
->location
, complaint
,
667 _("reduce/reduce conflicts for rule %d:"
668 " %d found, %d expected"),
669 r
->code
, rr
, expected_rr
);
674 /*---------------------------------.
675 | Reporting numbers of conflicts. |
676 `---------------------------------*/
679 conflicts_print (void)
681 report_rule_expectation_mismatches ();
683 if (! glr_parser
&& expected_rr_conflicts
!= -1)
685 complain (NULL
, Wother
, _("%%expect-rr applies only to GLR parsers"));
686 expected_rr_conflicts
= -1;
689 // The warning flags used to emit a diagnostic, if we did.
690 warnings unexpected_conflicts_warning
= Wnone
;
691 /* The following two blocks scream for factoring, but i18n support
692 would make it ugly. */
694 int total
= count_sr_conflicts ();
695 /* If %expect is not used, but %expect-rr is, then expect 0 sr. */
697 (expected_sr_conflicts
== -1 && expected_rr_conflicts
!= -1)
699 : expected_sr_conflicts
;
702 if (expected
!= total
)
704 complain (NULL
, complaint
,
705 _("shift/reduce conflicts: %d found, %d expected"),
708 unexpected_conflicts_warning
= complaint
;
713 complain (NULL
, Wconflicts_sr
,
714 ngettext ("%d shift/reduce conflict",
715 "%d shift/reduce conflicts",
718 unexpected_conflicts_warning
= Wconflicts_sr
;
723 int total
= count_rr_conflicts ();
724 /* If %expect-rr is not used, but %expect is, then expect 0 rr. */
726 (expected_rr_conflicts
== -1 && expected_sr_conflicts
!= -1)
728 : expected_rr_conflicts
;
731 if (expected
!= total
)
733 complain (NULL
, complaint
,
734 _("reduce/reduce conflicts: %d found, %d expected"),
737 unexpected_conflicts_warning
= complaint
;
742 complain (NULL
, Wconflicts_rr
,
743 ngettext ("%d reduce/reduce conflict",
744 "%d reduce/reduce conflicts",
747 unexpected_conflicts_warning
= Wconflicts_rr
;
751 if (warning_is_enabled (Wcounterexamples
))
752 report_counterexamples ();
753 else if (unexpected_conflicts_warning
!= Wnone
)
754 subcomplain (NULL
, unexpected_conflicts_warning
,
755 _("rerun with option '-Wcounterexamples'"
756 " to generate conflict counterexamples"));
760 conflicts_free (void)
763 bitset_free (shift_set
);
764 bitset_free (lookahead_set
);
765 obstack_free (&solved_conflicts_obstack
, NULL
);
766 obstack_free (&solved_conflicts_xml_obstack
, NULL
);