1/* Find and resolve or report lookahead conflicts for bison,
2
3 Copyright (C) 1984, 1989, 1992, 2000-2015, 2018-2019 Free Software
4 Foundation, Inc.
5
6 This file is part of Bison, the GNU Compiler Compiler.
7
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.
12
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.
17
18 You should have received a copy of the GNU General Public License
19 along with this program. If not, see <http://www.gnu.org/licenses/>. */
20
21#include <config.h>
22#include "system.h"
23
24#include <bitset.h>
25
26#include "complain.h"
27#include "conflicts.h"
28#include "files.h"
29#include "getargs.h"
30#include "gram.h"
31#include "lalr.h"
32#include "lr0.h"
33#include "print-xml.h"
34#include "reader.h"
35#include "state.h"
36#include "symtab.h"
37
38/* -1 stands for not specified. */
39int expected_sr_conflicts = -1;
40int expected_rr_conflicts = -1;
41static char *conflicts;
42static struct obstack solved_conflicts_obstack;
43static struct obstack solved_conflicts_xml_obstack;
44
45static bitset shift_set;
46static bitset lookahead_set;
47
48
49
50enum conflict_resolution
51 {
52 shift_resolution,
53 reduce_resolution,
54 left_resolution,
55 right_resolution,
56 nonassoc_resolution
57 };
58
59
60/*----------------------------------------------------------------.
61| Explain how an SR conflict between TOKEN and RULE was resolved: |
62| RESOLUTION. |
63`----------------------------------------------------------------*/
64
65static inline void
66log_resolution (rule *r, symbol_number token,
67 enum conflict_resolution resolution)
68{
69 if (report_flag & report_solved_conflicts)
70 {
71 /* The description of the resolution. */
72 switch (resolution)
73 {
74 case shift_resolution:
75 case right_resolution:
76 obstack_printf (&solved_conflicts_obstack,
77 _(" Conflict between rule %d and token %s"
78 " resolved as shift"),
79 r->number,
80 symbols[token]->tag);
81 break;
82
83 case reduce_resolution:
84 case left_resolution:
85 obstack_printf (&solved_conflicts_obstack,
86 _(" Conflict between rule %d and token %s"
87 " resolved as reduce"),
88 r->number,
89 symbols[token]->tag);
90 break;
91
92 case nonassoc_resolution:
93 obstack_printf (&solved_conflicts_obstack,
94 _(" Conflict between rule %d and token %s"
95 " resolved as an error"),
96 r->number,
97 symbols[token]->tag);
98 break;
99 }
100
101 /* The reason. */
102 switch (resolution)
103 {
104 case shift_resolution:
105 obstack_printf (&solved_conflicts_obstack,
106 " (%s < %s)",
107 r->prec->symbol->tag,
108 symbols[token]->tag);
109 break;
110
111 case reduce_resolution:
112 obstack_printf (&solved_conflicts_obstack,
113 " (%s < %s)",
114 symbols[token]->tag,
115 r->prec->symbol->tag);
116 break;
117
118 case left_resolution:
119 obstack_printf (&solved_conflicts_obstack,
120 " (%%left %s)",
121 symbols[token]->tag);
122 break;
123
124 case right_resolution:
125 obstack_printf (&solved_conflicts_obstack,
126 " (%%right %s)",
127 symbols[token]->tag);
128 break;
129
130 case nonassoc_resolution:
131 obstack_printf (&solved_conflicts_obstack,
132 " (%%nonassoc %s)",
133 symbols[token]->tag);
134 break;
135 }
136
137 obstack_sgrow (&solved_conflicts_obstack, ".\n");
138 }
139
140 /* XML report */
141 if (xml_flag)
142 {
143 /* The description of the resolution. */
144 switch (resolution)
145 {
146 case shift_resolution:
147 case right_resolution:
148 obstack_printf (&solved_conflicts_xml_obstack,
149 " <resolution rule=\"%d\" symbol=\"%s\""
150 " type=\"shift\">",
151 r->number,
152 xml_escape (symbols[token]->tag));
153 break;
154
155 case reduce_resolution:
156 case left_resolution:
157 obstack_printf (&solved_conflicts_xml_obstack,
158 " <resolution rule=\"%d\" symbol=\"%s\""
159 " type=\"reduce\">",
160 r->number,
161 xml_escape (symbols[token]->tag));
162 break;
163
164 case nonassoc_resolution:
165 obstack_printf (&solved_conflicts_xml_obstack,
166 " <resolution rule=\"%d\" symbol=\"%s\""
167 " type=\"error\">",
168 r->number,
169 xml_escape (symbols[token]->tag));
170 break;
171 }
172
173 /* The reason. */
174 switch (resolution)
175 {
176 case shift_resolution:
177 obstack_printf (&solved_conflicts_xml_obstack,
178 "%s &lt; %s",
179 xml_escape_n (0, r->prec->symbol->tag),
180 xml_escape_n (1, symbols[token]->tag));
181 break;
182
183 case reduce_resolution:
184 obstack_printf (&solved_conflicts_xml_obstack,
185 "%s &lt; %s",
186 xml_escape_n (0, symbols[token]->tag),
187 xml_escape_n (1, r->prec->symbol->tag));
188 break;
189
190 case left_resolution:
191 obstack_printf (&solved_conflicts_xml_obstack,
192 "%%left %s",
193 xml_escape (symbols[token]->tag));
194 break;
195
196 case right_resolution:
197 obstack_printf (&solved_conflicts_xml_obstack,
198 "%%right %s",
199 xml_escape (symbols[token]->tag));
200 break;
201
202 case nonassoc_resolution:
203 obstack_printf (&solved_conflicts_xml_obstack,
204 "%%nonassoc %s",
205 xml_escape (symbols[token]->tag));
206 break;
207 }
208
209 obstack_sgrow (&solved_conflicts_xml_obstack, "</resolution>\n");
210 }
211}
212
213
214/*------------------------------------------------------------------.
215| Turn off the shift recorded for the specified token in the |
216| specified state. Used when we resolve a shift-reduce conflict in |
217| favor of the reduction or as an error (%nonassoc). |
218`------------------------------------------------------------------*/
219
220static void
221flush_shift (state *s, int token)
222{
223 transitions *trans = s->transitions;
224
225 bitset_reset (lookahead_set, token);
226 for (int i = 0; i < trans->num; ++i)
227 if (!TRANSITION_IS_DISABLED (trans, i)
228 && TRANSITION_SYMBOL (trans, i) == token)
229 TRANSITION_DISABLE (trans, i);
230}
231
232
233/*--------------------------------------------------------------------.
234| Turn off the reduce recorded for the specified token in the |
235| specified lookahead set. Used when we resolve a shift-reduce |
236| conflict in favor of the shift or as an error (%nonassoc). |
237`--------------------------------------------------------------------*/
238
239static void
240flush_reduce (bitset lookahead_tokens, int token)
241{
242 bitset_reset (lookahead_tokens, token);
243}
244
245
246/*------------------------------------------------------------------.
247| Attempt to resolve shift-reduce conflict for one rule by means of |
248| precedence declarations. It has already been checked that the |
249| rule has a precedence. A conflict is resolved by modifying the |
250| shift or reduce tables so that there is no longer a conflict. |
251| |
252| RULENO is the number of the lookahead bitset to consider. |
253| |
254| ERRORS and NERRS can be used to store discovered explicit |
255| errors. |
256`------------------------------------------------------------------*/
257
258static void
259resolve_sr_conflict (state *s, int ruleno, symbol **errors, int *nerrs)
260{
261 reductions *reds = s->reductions;
262 /* Find the rule to reduce by to get precedence of reduction. */
263 rule *redrule = reds->rules[ruleno];
264 int redprec = redrule->prec->prec;
265 bitset lookahead_tokens = reds->lookahead_tokens[ruleno];
266
267 for (symbol_number i = 0; i < ntokens; ++i)
268 if (bitset_test (lookahead_tokens, i)
269 && bitset_test (lookahead_set, i)
270 && symbols[i]->content->prec)
271 {
272 /* Shift-reduce conflict occurs for token number i
273 and it has a precedence.
274 The precedence of shifting is that of token i. */
275 if (symbols[i]->content->prec < redprec)
276 {
277 register_precedence (redrule->prec->number, i);
278 log_resolution (redrule, i, reduce_resolution);
279 flush_shift (s, i);
280 }
281 else if (symbols[i]->content->prec > redprec)
282 {
283 register_precedence (i, redrule->prec->number);
284 log_resolution (redrule, i, shift_resolution);
285 flush_reduce (lookahead_tokens, i);
286 }
287 else
288 /* Matching precedence levels.
289 For non-defined associativity, keep both: unexpected
290 associativity conflict.
291 For left associativity, keep only the reduction.
292 For right associativity, keep only the shift.
293 For nonassociativity, keep neither. */
294
295 switch (symbols[i]->content->assoc)
296 {
297 case undef_assoc:
298 abort ();
299
300 case precedence_assoc:
301 break;
302
303 case right_assoc:
304 register_assoc (i, redrule->prec->number);
305 log_resolution (redrule, i, right_resolution);
306 flush_reduce (lookahead_tokens, i);
307 break;
308
309 case left_assoc:
310 register_assoc (i, redrule->prec->number);
311 log_resolution (redrule, i, left_resolution);
312 flush_shift (s, i);
313 break;
314
315 case non_assoc:
316 register_assoc (i, redrule->prec->number);
317 log_resolution (redrule, i, nonassoc_resolution);
318 flush_shift (s, i);
319 flush_reduce (lookahead_tokens, i);
320 /* Record an explicit error for this token. */
321 errors[(*nerrs)++] = symbols[i];
322 break;
323 }
324 }
325}
326
327
328/*-------------------------------------------------------------------.
329| Solve the S/R conflicts of state S using the |
330| precedence/associativity, and flag it inconsistent if it still has |
331| conflicts. ERRORS can be used as storage to compute the list of |
332| lookahead tokens on which S raises a syntax error (%nonassoc). |
333`-------------------------------------------------------------------*/
334
335static void
336set_conflicts (state *s, symbol **errors)
337{
338 if (s->consistent)
339 return;
340
341 reductions *reds = s->reductions;
342 int nerrs = 0;
343
344 bitset_zero (lookahead_set);
345
346 {
347 transitions *trans = s->transitions;
348 int i;
349 FOR_EACH_SHIFT (trans, i)
350 bitset_set (lookahead_set, TRANSITION_SYMBOL (trans, i));
351 }
352
353 /* Loop over all rules which require lookahead in this state. First
354 check for shift-reduce conflict, and try to resolve using
355 precedence. */
356 for (int i = 0; i < reds->num; ++i)
357 if (reds->rules[i]->prec && reds->rules[i]->prec->prec
358 && !bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
359 resolve_sr_conflict (s, i, errors, &nerrs);
360
361 if (nerrs)
362 /* Some tokens have been explicitly made errors. Allocate a
363 permanent errs structure for this state, to record them. */
364 state_errs_set (s, nerrs, errors);
365
366 if (obstack_object_size (&solved_conflicts_obstack))
367 s->solved_conflicts = obstack_finish0 (&solved_conflicts_obstack);
368 if (obstack_object_size (&solved_conflicts_xml_obstack))
369 s->solved_conflicts_xml = obstack_finish0 (&solved_conflicts_xml_obstack);
370
371 /* Loop over all rules which require lookahead in this state. Check
372 for conflicts not resolved above.
373
374 reds->lookahead_tokens can be NULL if the LR type is LR(0). */
375 if (reds->lookahead_tokens)
376 for (int i = 0; i < reds->num; ++i)
377 {
378 if (!bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
379 conflicts[s->number] = 1;
380 bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
381 }
382}
383
384
385/*----------------------------------------------------------------.
386| Solve all the S/R conflicts using the precedence/associativity, |
387| and flag as inconsistent the states that still have conflicts. |
388`----------------------------------------------------------------*/
389
390void
391conflicts_solve (void)
392{
393 /* List of lookahead tokens on which we explicitly raise a syntax error. */
394 symbol **errors = xnmalloc (ntokens + 1, sizeof *errors);
395
396 conflicts = xcalloc (nstates, sizeof *conflicts);
397 shift_set = bitset_create (ntokens, BITSET_FIXED);
398 lookahead_set = bitset_create (ntokens, BITSET_FIXED);
399 obstack_init (&solved_conflicts_obstack);
400 obstack_init (&solved_conflicts_xml_obstack);
401
402 for (state_number i = 0; i < nstates; ++i)
403 {
404 set_conflicts (states[i], errors);
405
406 /* For uniformity of the code, make sure all the states have a valid
407 'errs' member. */
408 if (!states[i]->errs)
409 states[i]->errs = errs_new (0, 0);
410 }
411
412 free (errors);
413}
414
415
416void
417conflicts_update_state_numbers (state_number old_to_new[],
418 state_number nstates_old)
419{
420 for (state_number i = 0; i < nstates_old; ++i)
421 if (old_to_new[i] != nstates_old)
422 conflicts[old_to_new[i]] = conflicts[i];
423}
424
425
426/*---------------------------------------------.
427| Count the number of shift/reduce conflicts. |
428`---------------------------------------------*/
429
430static size_t
431count_state_sr_conflicts (state *s)
432{
433 transitions *trans = s->transitions;
434 reductions *reds = s->reductions;
435
436 if (!trans)
437 return 0;
438
439 bitset_zero (lookahead_set);
440 bitset_zero (shift_set);
441
442 {
443 int i;
444 FOR_EACH_SHIFT (trans, i)
445 bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));
446 }
447
448 for (int i = 0; i < reds->num; ++i)
449 bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
450
451 bitset_and (lookahead_set, lookahead_set, shift_set);
452
453 return bitset_count (lookahead_set);
454}
455
456/*---------------------------------------------.
457| The total number of shift/reduce conflicts. |
458`---------------------------------------------*/
459
460static size_t
461count_sr_conflicts (void)
462{
463 size_t res = 0;
464 /* Conflicts by state. */
465 for (state_number i = 0; i < nstates; ++i)
466 if (conflicts[i])
467 res += count_state_sr_conflicts (states[i]);
468 return res;
469}
470
471
472
473/*-----------------------------------------------------------------.
474| Count the number of reduce/reduce conflicts. Count one conflict |
475| for each reduction after the first for a given token. |
476`-----------------------------------------------------------------*/
477
478static size_t
479count_state_rr_conflicts (state *s)
480{
481 reductions *reds = s->reductions;
482 size_t res = 0;
483
484 for (symbol_number i = 0; i < ntokens; ++i)
485 {
486 int count = 0;
487 for (int j = 0; j < reds->num; ++j)
488 count += bitset_test (reds->lookahead_tokens[j], i);
489 if (2 <= count)
490 res += count-1;
491 }
492
493 return res;
494}
495
496static size_t
497count_rr_conflicts (void)
498{
499 size_t res = 0;
500 /* Conflicts by state. */
501 for (state_number i = 0; i < nstates; ++i)
502 if (conflicts[i])
503 res += count_state_rr_conflicts (states[i]);
504 return res;
505}
506
507
508/*------------------------------------------------------------------.
509| For a given rule, the number of shift/reduce conflicts in a given |
510| state. |
511`------------------------------------------------------------------*/
512
513static size_t
514count_rule_state_sr_conflicts (rule *r, state *s)
515{
516 size_t res = 0;
517 transitions *trans = s->transitions;
518 reductions *reds = s->reductions;
519
520 for (int i = 0; i < reds->num; ++i)
521 if (reds->rules[i] == r)
522 {
523 bitset lookaheads = reds->lookahead_tokens[i];
524 int j;
525 FOR_EACH_SHIFT (trans, j)
526 res += bitset_test (lookaheads, TRANSITION_SYMBOL (trans, j));
527 }
528
529 return res;
530}
531
532/*----------------------------------------------------------------------.
533| For a given rule, count the number of states for which it is involved |
534| in shift/reduce conflicts. |
535`----------------------------------------------------------------------*/
536
537static size_t
538count_rule_sr_conflicts (rule *r)
539{
540 size_t res = 0;
541 for (state_number i = 0; i < nstates; ++i)
542 if (conflicts[i])
543 res += count_rule_state_sr_conflicts (r, states[i]);
544 return res;
545}
546
547/*-----------------------------------------------------------------.
548| For a given rule, count the number of states in which it is |
549| involved in reduce/reduce conflicts. |
550`-----------------------------------------------------------------*/
551
552static size_t
553count_rule_state_rr_conflicts (rule *r, state *s)
554{
555 size_t res = 0;
556 const reductions *reds = s->reductions;
557 bitset lookaheads = bitset_create (ntokens, BITSET_FIXED);
558
559 for (int i = 0; i < reds->num; ++i)
560 if (reds->rules[i] == r)
561 for (int j = 0; j < reds->num; ++j)
562 if (reds->rules[j] != r)
563 {
564 bitset_and (lookaheads,
565 reds->lookahead_tokens[i],
566 reds->lookahead_tokens[j]);
567 res += bitset_count (lookaheads);
568 }
569 bitset_free (lookaheads);
570 return res;
571}
572
573static size_t
574count_rule_rr_conflicts (rule *r)
575{
576 size_t res = 0;
577 for (state_number i = 0; i < nstates; ++i)
578 res += count_rule_state_rr_conflicts (r, states[i]);
579 return res;
580}
581
582/*-----------------------------------------------------------.
583| Output the detailed description of states with conflicts. |
584`-----------------------------------------------------------*/
585
586void
587conflicts_output (FILE *out)
588{
589 bool printed_sth = false;
590 for (state_number i = 0; i < nstates; ++i)
591 {
592 state *s = states[i];
593 if (conflicts[i])
594 {
595 int src = count_state_sr_conflicts (s);
596 int rrc = count_state_rr_conflicts (s);
597 fprintf (out, _("State %d "), i);
598 if (src && rrc)
599 fprintf (out,
600 _("conflicts: %d shift/reduce, %d reduce/reduce\n"),
601 src, rrc);
602 else if (src)
603 fprintf (out, _("conflicts: %d shift/reduce\n"), src);
604 else if (rrc)
605 fprintf (out, _("conflicts: %d reduce/reduce\n"), rrc);
606 printed_sth = true;
607 }
608 }
609 if (printed_sth)
610 fputs ("\n\n", out);
611}
612
613/*--------------------------------------------.
614| Total the number of S/R and R/R conflicts. |
615`--------------------------------------------*/
616
617int
618conflicts_total_count (void)
619{
620 return count_sr_conflicts () + count_rr_conflicts ();
621}
622
623/*------------------------------.
624| Reporting per-rule conflicts. |
625`------------------------------*/
626
627static void
628rule_conflicts_print (void)
629{
630 for (rule_number i = 0; i < nrules; i += 1)
631 {
632 rule *r = &rules[i];
633 int expected_sr = r->expected_sr_conflicts;
634 int expected_rr = r->expected_rr_conflicts;
635
636 if (expected_sr != -1 || expected_rr != -1)
637 {
638 int sr = count_rule_sr_conflicts (r);
639 if (sr != expected_sr && (sr != 0 || expected_sr != -1))
640 complain (&r->location, complaint,
641 _("shift/reduce conflicts for rule %d:"
642 " %d found, %d expected"),
643 r->user_number, sr, expected_sr);
644 int rr = count_rule_rr_conflicts (r);
645 if (rr != expected_rr && (rr != 0 || expected_rr != -1))
646 complain (&r->location, complaint,
647 _("reduce/reduce conflicts for rule %d:"
648 " %d found, %d expected"),
649 r->user_number, rr, expected_rr);
650 }
651 }
652}
653
654/*---------------------------------.
655| Reporting numbers of conflicts. |
656`---------------------------------*/
657
658void
659conflicts_print (void)
660{
661 rule_conflicts_print ();
662
663 if (! glr_parser && expected_rr_conflicts != -1)
664 {
665 complain (NULL, Wother, _("%%expect-rr applies only to GLR parsers"));
666 expected_rr_conflicts = -1;
667 }
668
669 /* Screams for factoring, but almost useless because of the
670 different strings to translate. */
671 {
672 int total = count_sr_conflicts ();
673 /* If %expect is not used, but %expect-rr is, then expect 0 sr. */
674 int expected =
675 (expected_sr_conflicts == -1 && expected_rr_conflicts != -1)
676 ? 0
677 : expected_sr_conflicts;
678 if (expected != -1)
679 {
680 if (expected != total)
681 complain (NULL, complaint,
682 _("shift/reduce conflicts: %d found, %d expected"),
683 total, expected);
684 }
685 else if (total)
686 complain (NULL, Wconflicts_sr,
687 ngettext ("%d shift/reduce conflict",
688 "%d shift/reduce conflicts",
689 total),
690 total);
691 }
692
693 {
694 int total = count_rr_conflicts ();
695 /* If %expect-rr is not used, but %expect is, then expect 0 rr. */
696 int expected =
697 (expected_rr_conflicts == -1 && expected_sr_conflicts != -1)
698 ? 0
699 : expected_rr_conflicts;
700 if (expected != -1)
701 {
702 if (expected != total)
703 complain (NULL, complaint,
704 _("reduce/reduce conflicts: %d found, %d expected"),
705 total, expected);
706 }
707 else if (total)
708 complain (NULL, Wconflicts_rr,
709 ngettext ("%d reduce/reduce conflict",
710 "%d reduce/reduce conflicts",
711 total),
712 total);
713 }
714}
715
716void
717conflicts_free (void)
718{
719 free (conflicts);
720 bitset_free (shift_set);
721 bitset_free (lookahead_set);
722 obstack_free (&solved_conflicts_obstack, NULL);
723 obstack_free (&solved_conflicts_xml_obstack, NULL);
724}
725