• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 &lt; %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 &lt; %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