]> git.saurik.com Git - bison.git/blame_incremental - src/conflicts.c
Use ASCII for Sebastien Fricker's name.
[bison.git] / src / conflicts.c
... / ...
CommitLineData
1/* Find and resolve or report lookahead conflicts for bison,
2
3 Copyright (C) 1984, 1989, 1992, 2000, 2001, 2002, 2003, 2004, 2005, 2006
4 Free Software Foundation, Inc.
5
6 This file is part of Bison, the GNU Compiler Compiler.
7
8 Bison is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
11 any later version.
12
13 Bison is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with Bison; see the file COPYING. If not, write to the Free
20 Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 02110-1301, USA. */
22
23#include <config.h>
24#include "system.h"
25
26#include <bitset.h>
27
28#include "LR0.h"
29#include "complain.h"
30#include "conflicts.h"
31#include "files.h"
32#include "getargs.h"
33#include "gram.h"
34#include "lalr.h"
35#include "reader.h"
36#include "state.h"
37#include "symtab.h"
38
39/* -1 stands for not specified. */
40int expected_sr_conflicts = -1;
41int expected_rr_conflicts = -1;
42static char *conflicts;
43static struct obstack solved_conflicts_obstack;
44
45static bitset shift_set;
46static bitset lookahead_set;
47
48\f
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_fgrow2 (&solved_conflicts_obstack,
77 _("\
78 Conflict between rule %d and token %s resolved as shift"),
79 r->number,
80 symbols[token]->tag);
81 break;
82 case reduce_resolution:
83 case left_resolution:
84 obstack_fgrow2 (&solved_conflicts_obstack,
85 _("\
86 Conflict between rule %d and token %s resolved as reduce"),
87 r->number,
88 symbols[token]->tag);
89 break;
90 case nonassoc_resolution:
91 obstack_fgrow2 (&solved_conflicts_obstack,
92 _("\
93 Conflict between rule %d and token %s resolved as an error"),
94 r->number,
95 symbols[token]->tag);
96 break;
97 }
98
99 /* The reason. */
100 switch (resolution)
101 {
102 case shift_resolution:
103 obstack_fgrow2 (&solved_conflicts_obstack,
104 " (%s < %s)",
105 r->prec->tag,
106 symbols[token]->tag);
107 break;
108
109 case reduce_resolution:
110 obstack_fgrow2 (&solved_conflicts_obstack,
111 " (%s < %s)",
112 symbols[token]->tag,
113 r->prec->tag);
114 break;
115
116 case left_resolution:
117 obstack_fgrow1 (&solved_conflicts_obstack,
118 " (%%left %s)",
119 symbols[token]->tag);
120 break;
121
122 case right_resolution:
123 obstack_fgrow1 (&solved_conflicts_obstack,
124 " (%%right %s)",
125 symbols[token]->tag);
126 break;
127 case nonassoc_resolution:
128 obstack_fgrow1 (&solved_conflicts_obstack,
129 " (%%nonassoc %s)",
130 symbols[token]->tag);
131 break;
132 }
133 obstack_sgrow (&solved_conflicts_obstack, ".\n");
134 }
135}
136
137
138/*------------------------------------------------------------------.
139| Turn off the shift recorded for the specified token in the |
140| specified state. Used when we resolve a shift-reduce conflict in |
141| favor of the reduction. |
142`------------------------------------------------------------------*/
143
144static void
145flush_shift (state *s, int token)
146{
147 transitions *trans = s->transitions;
148 int i;
149
150 bitset_reset (lookahead_set, token);
151 for (i = 0; i < trans->num; i++)
152 if (!TRANSITION_IS_DISABLED (trans, i)
153 && TRANSITION_SYMBOL (trans, i) == token)
154 TRANSITION_DISABLE (trans, i);
155}
156
157
158/*--------------------------------------------------------------------.
159| Turn off the reduce recorded for the specified token for the |
160| specified lookahead. Used when we resolve a shift-reduce conflict |
161| in favor of the shift. |
162`--------------------------------------------------------------------*/
163
164static void
165flush_reduce (bitset lookahead_tokens, int token)
166{
167 bitset_reset (lookahead_tokens, token);
168}
169
170
171/*------------------------------------------------------------------.
172| Attempt to resolve shift-reduce conflict for one rule by means of |
173| precedence declarations. It has already been checked that the |
174| rule has a precedence. A conflict is resolved by modifying the |
175| shift or reduce tables so that there is no longer a conflict. |
176| |
177| RULENO is the number of the lookahead bitset to consider. |
178| |
179| ERRORS can be used to store discovered explicit errors. |
180`------------------------------------------------------------------*/
181
182static void
183resolve_sr_conflict (state *s, int ruleno, symbol **errors)
184{
185 symbol_number i;
186 reductions *reds = s->reductions;
187 /* Find the rule to reduce by to get precedence of reduction. */
188 rule *redrule = reds->rules[ruleno];
189 int redprec = redrule->prec->prec;
190 bitset lookahead_tokens = reds->lookahead_tokens[ruleno];
191 int nerrs = 0;
192
193 for (i = 0; i < ntokens; i++)
194 if (bitset_test (lookahead_tokens, i)
195 && bitset_test (lookahead_set, i)
196 && symbols[i]->prec)
197 {
198 /* Shift-reduce conflict occurs for token number i
199 and it has a precedence.
200 The precedence of shifting is that of token i. */
201 if (symbols[i]->prec < redprec)
202 {
203 log_resolution (redrule, i, reduce_resolution);
204 flush_shift (s, i);
205 }
206 else if (symbols[i]->prec > redprec)
207 {
208 log_resolution (redrule, i, shift_resolution);
209 flush_reduce (lookahead_tokens, i);
210 }
211 else
212 /* Matching precedence levels.
213 For left association, keep only the reduction.
214 For right association, keep only the shift.
215 For nonassociation, keep neither. */
216
217 switch (symbols[i]->assoc)
218 {
219 default:
220 abort ();
221
222 case right_assoc:
223 log_resolution (redrule, i, right_resolution);
224 flush_reduce (lookahead_tokens, i);
225 break;
226
227 case left_assoc:
228 log_resolution (redrule, i, left_resolution);
229 flush_shift (s, i);
230 break;
231
232 case non_assoc:
233 log_resolution (redrule, i, nonassoc_resolution);
234 flush_shift (s, i);
235 flush_reduce (lookahead_tokens, i);
236 /* Record an explicit error for this token. */
237 errors[nerrs++] = symbols[i];
238 break;
239 }
240 }
241
242 if (nerrs)
243 {
244 /* Some tokens have been explicitly made errors. Allocate a
245 permanent errs structure for this state, to record them. */
246 state_errs_set (s, nerrs, errors);
247 }
248
249 if (obstack_object_size (&solved_conflicts_obstack))
250 {
251 obstack_1grow (&solved_conflicts_obstack, '\0');
252 s->solved_conflicts = obstack_finish (&solved_conflicts_obstack);
253 }
254}
255
256
257/*-------------------------------------------------------------------.
258| Solve the S/R conflicts of state S using the |
259| precedence/associativity, and flag it inconsistent if it still has |
260| conflicts. ERRORS can be used as storage to compute the list of |
261| lookahead tokens on which S raises a syntax error (%nonassoc). |
262`-------------------------------------------------------------------*/
263
264static void
265set_conflicts (state *s, symbol **errors)
266{
267 int i;
268 transitions *trans = s->transitions;
269 reductions *reds = s->reductions;
270
271 if (s->consistent)
272 return;
273
274 bitset_zero (lookahead_set);
275
276 FOR_EACH_SHIFT (trans, i)
277 bitset_set (lookahead_set, TRANSITION_SYMBOL (trans, i));
278
279 /* Loop over all rules which require lookahead in this state. First
280 check for shift-reduce conflict, and try to resolve using
281 precedence. */
282 for (i = 0; i < reds->num; ++i)
283 if (reds->rules[i]->prec && reds->rules[i]->prec->prec
284 && !bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
285 resolve_sr_conflict (s, i, errors);
286
287 /* Loop over all rules which require lookahead in this state. Check
288 for conflicts not resolved above. */
289 for (i = 0; i < reds->num; ++i)
290 {
291 if (!bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
292 conflicts[s->number] = 1;
293
294 bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
295 }
296}
297
298
299/*----------------------------------------------------------------.
300| Solve all the S/R conflicts using the precedence/associativity, |
301| and flag as inconsistent the states that still have conflicts. |
302`----------------------------------------------------------------*/
303
304void
305conflicts_solve (void)
306{
307 state_number i;
308 /* List of lookahead tokens on which we explicitly raise a syntax error. */
309 symbol **errors = xnmalloc (ntokens + 1, sizeof *errors);
310
311 conflicts = xcalloc (nstates, sizeof *conflicts);
312 shift_set = bitset_create (ntokens, BITSET_FIXED);
313 lookahead_set = bitset_create (ntokens, BITSET_FIXED);
314 obstack_init (&solved_conflicts_obstack);
315
316 for (i = 0; i < nstates; i++)
317 {
318 set_conflicts (states[i], errors);
319
320 /* For uniformity of the code, make sure all the states have a valid
321 `errs' member. */
322 if (!states[i]->errs)
323 states[i]->errs = errs_new (0, 0);
324 }
325
326 free (errors);
327}
328
329
330/*---------------------------------------------.
331| Count the number of shift/reduce conflicts. |
332`---------------------------------------------*/
333
334static int
335count_sr_conflicts (state *s)
336{
337 int i;
338 int src_count = 0;
339 transitions *trans = s->transitions;
340 reductions *reds = s->reductions;
341
342 if (!trans)
343 return 0;
344
345 bitset_zero (lookahead_set);
346 bitset_zero (shift_set);
347
348 FOR_EACH_SHIFT (trans, i)
349 bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));
350
351 for (i = 0; i < reds->num; ++i)
352 bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
353
354 bitset_and (lookahead_set, lookahead_set, shift_set);
355
356 src_count = bitset_count (lookahead_set);
357
358 return src_count;
359}
360
361
362/*----------------------------------------------------------------.
363| Count the number of reduce/reduce conflicts. If ONE_PER_TOKEN, |
364| count one conflict for each token that has any reduce/reduce |
365| conflicts. Otherwise, count one conflict for each pair of |
366| conflicting reductions. |
367+`----------------------------------------------------------------*/
368
369static int
370count_rr_conflicts (state *s, bool one_per_token)
371{
372 int i;
373 reductions *reds = s->reductions;
374 int rrc_count = 0;
375
376 for (i = 0; i < ntokens; i++)
377 {
378 int count = 0;
379 int j;
380 for (j = 0; j < reds->num; ++j)
381 if (bitset_test (reds->lookahead_tokens[j], i))
382 count++;
383
384 if (count >= 2)
385 rrc_count += one_per_token ? 1 : count-1;
386 }
387
388 return rrc_count;
389}
390
391
392/*--------------------------------------------------------.
393| Report the number of conflicts, using the Yacc format. |
394`--------------------------------------------------------*/
395
396static void
397conflict_report (FILE *out, int src_num, int rrc_num)
398{
399 if (src_num && rrc_num)
400 fprintf (out, _("conflicts: %d shift/reduce, %d reduce/reduce\n"),
401 src_num, rrc_num);
402 else if (src_num)
403 fprintf (out, _("conflicts: %d shift/reduce\n"), src_num);
404 else if (rrc_num)
405 fprintf (out, _("conflicts: %d reduce/reduce\n"), rrc_num);
406}
407
408
409/*-----------------------------------------------------------.
410| Output the detailed description of states with conflicts. |
411`-----------------------------------------------------------*/
412
413void
414conflicts_output (FILE *out)
415{
416 bool printed_sth = false;
417 state_number i;
418 for (i = 0; i < nstates; i++)
419 {
420 state *s = states[i];
421 if (conflicts[i])
422 {
423 fprintf (out, _("State %d "), i);
424 conflict_report (out, count_sr_conflicts (s),
425 count_rr_conflicts (s, true));
426 printed_sth = true;
427 }
428 }
429 if (printed_sth)
430 fputs ("\n\n", out);
431}
432
433/*--------------------------------------------------------.
434| Total the number of S/R and R/R conflicts. Unlike the |
435| code in conflicts_output, however, count EACH pair of |
436| reductions for the same state and lookahead as one |
437| conflict. |
438`--------------------------------------------------------*/
439
440int
441conflicts_total_count (void)
442{
443 state_number i;
444 int count;
445
446 /* Conflicts by state. */
447 count = 0;
448 for (i = 0; i < nstates; i++)
449 if (conflicts[i])
450 {
451 count += count_sr_conflicts (states[i]);
452 count += count_rr_conflicts (states[i], false);
453 }
454 return count;
455}
456
457
458/*------------------------------------------.
459| Reporting the total number of conflicts. |
460`------------------------------------------*/
461
462void
463conflicts_print (void)
464{
465 /* Is the number of SR conflicts OK? Either EXPECTED_CONFLICTS is
466 not set, and then we want 0 SR, or else it is specified, in which
467 case we want equality. */
468 bool src_ok;
469 bool rrc_ok;
470
471 int src_total = 0;
472 int rrc_total = 0;
473 int src_expected;
474 int rrc_expected;
475
476 /* Conflicts by state. */
477 {
478 state_number i;
479
480 for (i = 0; i < nstates; i++)
481 if (conflicts[i])
482 {
483 src_total += count_sr_conflicts (states[i]);
484 rrc_total += count_rr_conflicts (states[i], true);
485 }
486 }
487
488 if (! glr_parser && rrc_total > 0 && expected_rr_conflicts != -1)
489 {
490 warn (_("%%expect-rr applies only to GLR parsers"));
491 expected_rr_conflicts = -1;
492 }
493
494 src_expected = expected_sr_conflicts == -1 ? 0 : expected_sr_conflicts;
495 rrc_expected = expected_rr_conflicts == -1 ? 0 : expected_rr_conflicts;
496 src_ok = src_total == src_expected;
497 rrc_ok = rrc_total == rrc_expected;
498
499 /* If there are as many RR conflicts and SR conflicts as
500 expected, then there is nothing to report. */
501 if (rrc_ok & src_ok)
502 return;
503
504 /* Report the total number of conflicts on STDERR. */
505 if (src_total | rrc_total)
506 {
507 if (! yacc_flag)
508 fprintf (stderr, "%s: ", current_file);
509 conflict_report (stderr, src_total, rrc_total);
510 }
511
512 if (expected_sr_conflicts != -1 || expected_rr_conflicts != -1)
513 {
514 if (! src_ok)
515 complain (ngettext ("expected %d shift/reduce conflict",
516 "expected %d shift/reduce conflicts",
517 src_expected),
518 src_expected);
519 if (! rrc_ok)
520 complain (ngettext ("expected %d reduce/reduce conflict",
521 "expected %d reduce/reduce conflicts",
522 rrc_expected),
523 rrc_expected);
524 }
525}
526
527
528void
529conflicts_free (void)
530{
531 free (conflicts);
532 bitset_free (shift_set);
533 bitset_free (lookahead_set);
534 obstack_free (&solved_conflicts_obstack, NULL);
535}