1 /* Find and resolve or report lookahead conflicts for bison,
2
3 Copyright (C) 1984, 1989, 1992, 2000-2007, 2009-2012 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 "LR0.h"
27 #include "complain.h"
28 #include "conflicts.h"
29 #include "files.h"
30 #include "getargs.h"
31 #include "gram.h"
32 #include "lalr.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. */
39 int expected_sr_conflicts = -1;
40 int expected_rr_conflicts = -1;
41 static char *conflicts;
42 static struct obstack solved_conflicts_obstack;
43 static struct obstack solved_conflicts_xml_obstack;
44
45 static bitset shift_set;
46 static bitset lookahead_set;
47
48
49
50 enum 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
65 static inline void
log_resolution(rule * r,symbol_number token,enum conflict_resolution resolution)66 log_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->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->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 < %s",
179 xml_escape_n (0, r->prec->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 < %s",
186 xml_escape_n (0, symbols[token]->tag),
187 xml_escape_n (1, r->prec->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
220 static void
flush_shift(state * s,int token)221 flush_shift (state *s, int token)
222 {
223 transitions *trans = s->transitions;
224 int i;
225
226 bitset_reset (lookahead_set, token);
227 for (i = 0; i < trans->num; i++)
228 if (!TRANSITION_IS_DISABLED (trans, i)
229 && TRANSITION_SYMBOL (trans, i) == token)
230 TRANSITION_DISABLE (trans, i);
231 }
232
233
234 /*--------------------------------------------------------------------.
235 | Turn off the reduce recorded for the specified token in the |
236 | specified lookahead set. Used when we resolve a shift-reduce |
237 | conflict in favor of the shift or as an error (%nonassoc). |
238 `--------------------------------------------------------------------*/
239
240 static void
flush_reduce(bitset lookahead_tokens,int token)241 flush_reduce (bitset lookahead_tokens, int token)
242 {
243 bitset_reset (lookahead_tokens, token);
244 }
245
246
247 /*------------------------------------------------------------------.
248 | Attempt to resolve shift-reduce conflict for one rule by means of |
249 | precedence declarations. It has already been checked that the |
250 | rule has a precedence. A conflict is resolved by modifying the |
251 | shift or reduce tables so that there is no longer a conflict. |
252 | |
253 | RULENO is the number of the lookahead bitset to consider. |
254 | |
255 | ERRORS and NERRS can be used to store discovered explicit |
256 | errors. |
257 `------------------------------------------------------------------*/
258
259 static void
resolve_sr_conflict(state * s,int ruleno,symbol ** errors,int * nerrs)260 resolve_sr_conflict (state *s, int ruleno, symbol **errors, int *nerrs)
261 {
262 symbol_number i;
263 reductions *reds = s->reductions;
264 /* Find the rule to reduce by to get precedence of reduction. */
265 rule *redrule = reds->rules[ruleno];
266 int redprec = redrule->prec->prec;
267 bitset lookahead_tokens = reds->lookahead_tokens[ruleno];
268
269 for (i = 0; i < ntokens; i++)
270 if (bitset_test (lookahead_tokens, i)
271 && bitset_test (lookahead_set, i)
272 && symbols[i]->prec)
273 {
274 /* Shift-reduce conflict occurs for token number i
275 and it has a precedence.
276 The precedence of shifting is that of token i. */
277 if (symbols[i]->prec < redprec)
278 {
279 log_resolution (redrule, i, reduce_resolution);
280 flush_shift (s, i);
281 }
282 else if (symbols[i]->prec > redprec)
283 {
284 log_resolution (redrule, i, shift_resolution);
285 flush_reduce (lookahead_tokens, i);
286 }
287 else
288 /* Matching precedence levels.
289 For left association, keep only the reduction.
290 For right association, keep only the shift.
291 For nonassociation, keep neither. */
292
293 switch (symbols[i]->assoc)
294 {
295 default:
296 abort ();
297
298 case right_assoc:
299 log_resolution (redrule, i, right_resolution);
300 flush_reduce (lookahead_tokens, i);
301 break;
302
303 case left_assoc:
304 log_resolution (redrule, i, left_resolution);
305 flush_shift (s, i);
306 break;
307
308 case non_assoc:
309 log_resolution (redrule, i, nonassoc_resolution);
310 flush_shift (s, i);
311 flush_reduce (lookahead_tokens, i);
312 /* Record an explicit error for this token. */
313 errors[(*nerrs)++] = symbols[i];
314 break;
315 }
316 }
317 }
318
319
320 /*-------------------------------------------------------------------.
321 | Solve the S/R conflicts of state S using the |
322 | precedence/associativity, and flag it inconsistent if it still has |
323 | conflicts. ERRORS can be used as storage to compute the list of |
324 | lookahead tokens on which S raises a syntax error (%nonassoc). |
325 `-------------------------------------------------------------------*/
326
327 static void
set_conflicts(state * s,symbol ** errors)328 set_conflicts (state *s, symbol **errors)
329 {
330 int i;
331 transitions *trans = s->transitions;
332 reductions *reds = s->reductions;
333 int nerrs = 0;
334
335 if (s->consistent)
336 return;
337
338 bitset_zero (lookahead_set);
339
340 FOR_EACH_SHIFT (trans, i)
341 bitset_set (lookahead_set, TRANSITION_SYMBOL (trans, i));
342
343 /* Loop over all rules which require lookahead in this state. First
344 check for shift-reduce conflict, and try to resolve using
345 precedence. */
346 for (i = 0; i < reds->num; ++i)
347 if (reds->rules[i]->prec && reds->rules[i]->prec->prec
348 && !bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
349 resolve_sr_conflict (s, i, errors, &nerrs);
350
351 if (nerrs)
352 {
353 /* Some tokens have been explicitly made errors. Allocate a
354 permanent errs structure for this state, to record them. */
355 state_errs_set (s, nerrs, errors);
356 }
357 if (obstack_object_size (&solved_conflicts_obstack))
358 {
359 obstack_1grow (&solved_conflicts_obstack, '\0');
360 s->solved_conflicts = obstack_finish (&solved_conflicts_obstack);
361 }
362 if (obstack_object_size (&solved_conflicts_xml_obstack))
363 {
364 obstack_1grow (&solved_conflicts_xml_obstack, '\0');
365 s->solved_conflicts_xml = obstack_finish (&solved_conflicts_xml_obstack);
366 }
367
368 /* Loop over all rules which require lookahead in this state. Check
369 for conflicts not resolved above. */
370 for (i = 0; i < reds->num; ++i)
371 {
372 if (!bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
373 conflicts[s->number] = 1;
374 bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
375 }
376 }
377
378
379 /*----------------------------------------------------------------.
380 | Solve all the S/R conflicts using the precedence/associativity, |
381 | and flag as inconsistent the states that still have conflicts. |
382 `----------------------------------------------------------------*/
383
384 void
conflicts_solve(void)385 conflicts_solve (void)
386 {
387 state_number i;
388 /* List of lookahead tokens on which we explicitly raise a syntax error. */
389 symbol **errors = xnmalloc (ntokens + 1, sizeof *errors);
390
391 conflicts = xcalloc (nstates, sizeof *conflicts);
392 shift_set = bitset_create (ntokens, BITSET_FIXED);
393 lookahead_set = bitset_create (ntokens, BITSET_FIXED);
394 obstack_init (&solved_conflicts_obstack);
395 obstack_init (&solved_conflicts_xml_obstack);
396
397 for (i = 0; i < nstates; i++)
398 {
399 set_conflicts (states[i], errors);
400
401 /* For uniformity of the code, make sure all the states have a valid
402 `errs' member. */
403 if (!states[i]->errs)
404 states[i]->errs = errs_new (0, 0);
405 }
406
407 free (errors);
408 }
409
410
411 void
conflicts_update_state_numbers(state_number old_to_new[],state_number nstates_old)412 conflicts_update_state_numbers (state_number old_to_new[],
413 state_number nstates_old)
414 {
415 state_number i;
416 for (i = 0; i < nstates_old; ++i)
417 if (old_to_new[i] != nstates_old)
418 conflicts[old_to_new[i]] = conflicts[i];
419 }
420
421
422 /*---------------------------------------------.
423 | Count the number of shift/reduce conflicts. |
424 `---------------------------------------------*/
425
426 static int
count_sr_conflicts(state * s)427 count_sr_conflicts (state *s)
428 {
429 int i;
430 int src_count = 0;
431 transitions *trans = s->transitions;
432 reductions *reds = s->reductions;
433
434 if (!trans)
435 return 0;
436
437 bitset_zero (lookahead_set);
438 bitset_zero (shift_set);
439
440 FOR_EACH_SHIFT (trans, i)
441 bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));
442
443 for (i = 0; i < reds->num; ++i)
444 bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
445
446 bitset_and (lookahead_set, lookahead_set, shift_set);
447
448 src_count = bitset_count (lookahead_set);
449
450 return src_count;
451 }
452
453
454 /*----------------------------------------------------------------.
455 | Count the number of reduce/reduce conflicts. If ONE_PER_TOKEN, |
456 | count one conflict for each token that has any reduce/reduce |
457 | conflicts. Otherwise, count one conflict for each pair of |
458 | conflicting reductions. |
459 +`----------------------------------------------------------------*/
460
461 static int
count_rr_conflicts(state * s,bool one_per_token)462 count_rr_conflicts (state *s, bool one_per_token)
463 {
464 int i;
465 reductions *reds = s->reductions;
466 int rrc_count = 0;
467
468 for (i = 0; i < ntokens; i++)
469 {
470 int count = 0;
471 int j;
472 for (j = 0; j < reds->num; ++j)
473 if (bitset_test (reds->lookahead_tokens[j], i))
474 count++;
475
476 if (count >= 2)
477 rrc_count += one_per_token ? 1 : count-1;
478 }
479
480 return rrc_count;
481 }
482
483
484 /*--------------------------------------------------------.
485 | Report the number of conflicts, using the Yacc format. |
486 `--------------------------------------------------------*/
487
488 static void
conflict_report(FILE * out,int src_num,int rrc_num)489 conflict_report (FILE *out, int src_num, int rrc_num)
490 {
491 if (src_num && rrc_num)
492 fprintf (out, _("conflicts: %d shift/reduce, %d reduce/reduce\n"),
493 src_num, rrc_num);
494 else if (src_num)
495 fprintf (out, _("conflicts: %d shift/reduce\n"), src_num);
496 else if (rrc_num)
497 fprintf (out, _("conflicts: %d reduce/reduce\n"), rrc_num);
498 }
499
500
501 /*-----------------------------------------------------------.
502 | Output the detailed description of states with conflicts. |
503 `-----------------------------------------------------------*/
504
505 void
conflicts_output(FILE * out)506 conflicts_output (FILE *out)
507 {
508 bool printed_sth = false;
509 state_number i;
510 for (i = 0; i < nstates; i++)
511 {
512 state *s = states[i];
513 if (conflicts[i])
514 {
515 fprintf (out, _("State %d "), i);
516 conflict_report (out, count_sr_conflicts (s),
517 count_rr_conflicts (s, true));
518 printed_sth = true;
519 }
520 }
521 if (printed_sth)
522 fputs ("\n\n", out);
523 }
524
525 /*--------------------------------------------------------.
526 | Total the number of S/R and R/R conflicts. Unlike the |
527 | code in conflicts_output, however, count EACH pair of |
528 | reductions for the same state and lookahead as one |
529 | conflict. |
530 `--------------------------------------------------------*/
531
532 int
conflicts_total_count(void)533 conflicts_total_count (void)
534 {
535 state_number i;
536 int count;
537
538 /* Conflicts by state. */
539 count = 0;
540 for (i = 0; i < nstates; i++)
541 if (conflicts[i])
542 {
543 count += count_sr_conflicts (states[i]);
544 count += count_rr_conflicts (states[i], false);
545 }
546 return count;
547 }
548
549
550 /*------------------------------------------.
551 | Reporting the total number of conflicts. |
552 `------------------------------------------*/
553
554 void
conflicts_print(void)555 conflicts_print (void)
556 {
557 /* Is the number of SR conflicts OK? Either EXPECTED_CONFLICTS is
558 not set, and then we want 0 SR, or else it is specified, in which
559 case we want equality. */
560 bool src_ok;
561 bool rrc_ok;
562
563 int src_total = 0;
564 int rrc_total = 0;
565 int src_expected;
566 int rrc_expected;
567
568 /* Conflicts by state. */
569 {
570 state_number i;
571
572 for (i = 0; i < nstates; i++)
573 if (conflicts[i])
574 {
575 src_total += count_sr_conflicts (states[i]);
576 rrc_total += count_rr_conflicts (states[i], true);
577 }
578 }
579
580 if (! glr_parser && rrc_total > 0 && expected_rr_conflicts != -1)
581 {
582 warn (_("%%expect-rr applies only to GLR parsers"));
583 expected_rr_conflicts = -1;
584 }
585
586 src_expected = expected_sr_conflicts == -1 ? 0 : expected_sr_conflicts;
587 rrc_expected = expected_rr_conflicts == -1 ? 0 : expected_rr_conflicts;
588 src_ok = src_total == src_expected;
589 rrc_ok = rrc_total == rrc_expected;
590
591 /* If there are as many RR conflicts and SR conflicts as
592 expected, then there is nothing to report. */
593 if (rrc_ok & src_ok)
594 return;
595
596 /* Report the total number of conflicts on STDERR. */
597 if (expected_sr_conflicts == -1 && expected_rr_conflicts == -1)
598 {
599 if (!(warnings_flag & warnings_conflicts_sr))
600 src_total = 0;
601 if (!(warnings_flag & warnings_conflicts_rr))
602 rrc_total = 0;
603 }
604 if (src_total | rrc_total)
605 {
606 if (expected_sr_conflicts == -1 && expected_rr_conflicts == -1)
607 set_warning_issued ();
608 if (! yacc_flag)
609 fprintf (stderr, "%s: ", current_file);
610 conflict_report (stderr, src_total, rrc_total);
611 }
612
613 if (expected_sr_conflicts != -1 || expected_rr_conflicts != -1)
614 {
615 if (! src_ok)
616 complain (ngettext ("expected %d shift/reduce conflict",
617 "expected %d shift/reduce conflicts",
618 src_expected),
619 src_expected);
620 if (! rrc_ok)
621 complain (ngettext ("expected %d reduce/reduce conflict",
622 "expected %d reduce/reduce conflicts",
623 rrc_expected),
624 rrc_expected);
625 }
626 }
627
628
629 void
conflicts_free(void)630 conflicts_free (void)
631 {
632 free (conflicts);
633 bitset_free (shift_set);
634 bitset_free (lookahead_set);
635 obstack_free (&solved_conflicts_obstack, NULL);
636 obstack_free (&solved_conflicts_xml_obstack, NULL);
637 }
638