1 /* Find and resolve or report look-ahead conflicts for bison,
2 Copyright (C) 1984, 1989, 1992, 2000, 2001, 2002
3 Free Software Foundation, Inc.
5 This file is part of Bison, the GNU Compiler Compiler.
7 Bison is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 Bison is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with Bison; see the file COPYING. If not, write to the Free
19 Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
31 #include "conflicts.h"
35 /* -1 stands for not specified. */
36 int expected_conflicts
= -1;
37 static char *conflicts
= NULL
;
38 struct obstack solved_conflicts_obstack
;
40 static bitset shiftset
;
41 static bitset lookaheadset
;
45 enum conflict_resolution_e
55 /*----------------------------------------------------------------.
56 | Explain how an SR conflict between TOKEN and RULE was resolved: |
58 `----------------------------------------------------------------*/
61 log_resolution (rule_t
*rule
, symbol_number_t token
,
62 enum conflict_resolution_e resolution
)
64 if (report_flag
& report_solved_conflicts
)
66 /* The description of the resolution. */
69 case shift_resolution
:
70 case right_resolution
:
71 obstack_fgrow2 (&solved_conflicts_obstack
,
73 Conflict between rule %d and token %s resolved as shift"),
77 case reduce_resolution
:
79 obstack_fgrow2 (&solved_conflicts_obstack
,
81 Conflict between rule %d and token %s resolved as reduce"),
85 case nonassoc_resolution
:
86 obstack_fgrow2 (&solved_conflicts_obstack
,
88 Conflict between rule %d and token %s resolved as an error"),
97 case shift_resolution
:
98 obstack_fgrow2 (&solved_conflicts_obstack
,
101 symbols
[token
]->tag
);
104 case reduce_resolution
:
105 obstack_fgrow2 (&solved_conflicts_obstack
,
111 case left_resolution
:
112 obstack_fgrow1 (&solved_conflicts_obstack
,
114 symbols
[token
]->tag
);
117 case right_resolution
:
118 obstack_fgrow1 (&solved_conflicts_obstack
,
120 symbols
[token
]->tag
);
122 case nonassoc_resolution
:
123 obstack_fgrow1 (&solved_conflicts_obstack
,
125 symbols
[token
]->tag
);
128 obstack_sgrow (&solved_conflicts_obstack
, ".\n");
133 /*------------------------------------------------------------------.
134 | Turn off the shift recorded for the specified token in the |
135 | specified state. Used when we resolve a shift-reduce conflict in |
136 | favor of the reduction. |
137 `------------------------------------------------------------------*/
140 flush_shift (state_t
*state
, int token
)
142 transitions_t
*transitions
= state
->transitions
;
145 bitset_reset (lookaheadset
, token
);
146 for (i
= 0; i
< transitions
->num
; i
++)
147 if (!TRANSITION_IS_DISABLED (transitions
, i
)
148 && TRANSITION_SYMBOL (transitions
, i
) == token
)
149 TRANSITION_DISABLE (transitions
, i
);
153 /*-------------------------------------------------------------------.
154 | Turn off the reduce recorded for the specified token for the |
155 | specified lookahead. Used when we resolve a shift-reduce conflict |
156 | in favor of the shift. |
157 `-------------------------------------------------------------------*/
160 flush_reduce (bitset lookaheads
, int token
)
162 bitset_reset (lookaheads
, token
);
166 /*------------------------------------------------------------------.
167 | Attempt to resolve shift-reduce conflict for one rule by means of |
168 | precedence declarations. It has already been checked that the |
169 | rule has a precedence. A conflict is resolved by modifying the |
170 | shift or reduce tables so that there is no longer a conflict. |
172 | LOOKAHEAD is the number of the lookahead bitset to consider. |
174 | ERRS can be used to store discovered explicit errors. |
175 `------------------------------------------------------------------*/
178 resolve_sr_conflict (state_t
*state
, int ruleno
,
182 reductions_t
*reds
= state
->reductions
;
183 /* Find the rule to reduce by to get precedence of reduction. */
184 rule_t
*redrule
= reds
->rules
[ruleno
];
185 int redprec
= redrule
->prec
->prec
;
186 bitset lookaheads
= reds
->lookaheads
[ruleno
];
189 for (i
= 0; i
< ntokens
; i
++)
190 if (bitset_test (lookaheads
, i
)
191 && bitset_test (lookaheadset
, i
)
194 /* Shift-reduce conflict occurs for token number i
195 and it has a precedence.
196 The precedence of shifting is that of token i. */
197 if (symbols
[i
]->prec
< redprec
)
199 log_resolution (redrule
, i
, reduce_resolution
);
200 flush_shift (state
, i
);
202 else if (symbols
[i
]->prec
> redprec
)
204 log_resolution (redrule
, i
, shift_resolution
);
205 flush_reduce (lookaheads
, i
);
208 /* Matching precedence levels.
209 For left association, keep only the reduction.
210 For right association, keep only the shift.
211 For nonassociation, keep neither. */
213 switch (symbols
[i
]->assoc
)
216 log_resolution (redrule
, i
, right_resolution
);
217 flush_reduce (lookaheads
, i
);
221 log_resolution (redrule
, i
, left_resolution
);
222 flush_shift (state
, i
);
226 log_resolution (redrule
, i
, nonassoc_resolution
);
227 flush_shift (state
, i
);
228 flush_reduce (lookaheads
, i
);
229 /* Record an explicit error for this token. */
230 errs
[nerrs
++] = symbols
[i
];
238 /* Some tokens have been explicitly made errors. Allocate a
239 permanent errs structure for this state, to record them. */
240 state_errs_set (state
, nerrs
, errs
);
242 if (obstack_object_size (&solved_conflicts_obstack
))
244 obstack_1grow (&solved_conflicts_obstack
, '\0');
245 state
->solved_conflicts
= obstack_finish (&solved_conflicts_obstack
);
250 /*-------------------------------------------------------------------.
251 | Solve the S/R conflicts of STATE using the |
252 | precedence/associativity, and flag it inconsistent if it still has |
253 | conflicts. ERRS can be used as storage to compute the list of |
254 | lookaheads on which this STATE raises a syntax error (%nonassoc). |
255 `-------------------------------------------------------------------*/
258 set_conflicts (state_t
*state
, symbol_t
**errs
)
261 transitions_t
*transitions
= state
->transitions
;
262 reductions_t
*reds
= state
->reductions
;
264 if (state
->consistent
)
267 bitset_zero (lookaheadset
);
269 FOR_EACH_SHIFT (transitions
, i
)
270 bitset_set (lookaheadset
, TRANSITION_SYMBOL (transitions
, i
));
272 /* Loop over all rules which require lookahead in this state. First
273 check for shift-reduce conflict, and try to resolve using
275 for (i
= 0; i
< reds
->num
; ++i
)
276 if (reds
->rules
[i
]->prec
&& reds
->rules
[i
]->prec
->prec
277 && !bitset_disjoint_p (reds
->lookaheads
[i
], lookaheadset
))
279 resolve_sr_conflict (state
, i
, errs
);
283 /* Loop over all rules which require lookahead in this state. Check
284 for conflicts not resolved above. */
285 for (i
= 0; i
< reds
->num
; ++i
)
287 if (!bitset_disjoint_p (reds
->lookaheads
[i
], lookaheadset
))
288 conflicts
[state
->number
] = 1;
290 bitset_or (lookaheadset
, lookaheadset
, reds
->lookaheads
[i
]);
295 /*----------------------------------------------------------------.
296 | Solve all the S/R conflicts using the precedence/associativity, |
297 | and flag as inconsistent the states that still have conflicts. |
298 `----------------------------------------------------------------*/
301 conflicts_solve (void)
304 /* List of lookaheads on which we explicitly raise a syntax error. */
305 symbol_t
**errs
= XMALLOC (symbol_t
*, ntokens
+ 1);
307 conflicts
= XCALLOC (char, nstates
);
308 shiftset
= bitset_create (ntokens
, BITSET_FIXED
);
309 lookaheadset
= bitset_create (ntokens
, BITSET_FIXED
);
310 obstack_init (&solved_conflicts_obstack
);
312 for (i
= 0; i
< nstates
; i
++)
314 set_conflicts (states
[i
], errs
);
316 /* For uniformity of the code, make sure all the states have a valid
318 if (!states
[i
]->errs
)
319 states
[i
]->errs
= errs_new (0, 0);
326 /*---------------------------------------------.
327 | Count the number of shift/reduce conflicts. |
328 `---------------------------------------------*/
331 count_sr_conflicts (state_t
*state
)
335 transitions_t
*transitions
= state
->transitions
;
336 reductions_t
*reds
= state
->reductions
;
341 bitset_zero (lookaheadset
);
342 bitset_zero (shiftset
);
344 FOR_EACH_SHIFT (transitions
, i
)
345 bitset_set (shiftset
, TRANSITION_SYMBOL (transitions
, i
));
347 for (i
= 0; i
< reds
->num
; ++i
)
348 bitset_or (lookaheadset
, lookaheadset
, reds
->lookaheads
[i
]);
350 bitset_and (lookaheadset
, lookaheadset
, shiftset
);
352 src_count
= bitset_count (lookaheadset
);
358 /*----------------------------------------------------------------.
359 | Count the number of reduce/reduce conflicts. If ONE_PER_TOKEN, |
360 | count one conflict for each token that has any reduce/reduce |
361 | conflicts. Otherwise, count one conflict for each pair of |
362 | conflicting reductions. |
363 +`----------------------------------------------------------------*/
366 count_rr_conflicts (state_t
*state
, int one_per_token
)
369 reductions_t
*reds
= state
->reductions
;
372 for (i
= 0; i
< ntokens
; i
++)
376 for (j
= 0; j
< reds
->num
; ++j
)
377 if (bitset_test (reds
->lookaheads
[j
], i
))
381 rrc_count
+= one_per_token
? 1 : count
-1;
388 /*--------------------------------------------------------------.
389 | Return a human readable string which reports shift/reduce and |
390 | reduce/reduce conflict numbers (SRC_NUM, RRC_NUM). |
391 `--------------------------------------------------------------*/
394 conflict_report (int src_num
, int rrc_num
)
396 static char res
[4096];
401 sprintf (cp
, ngettext ("%d shift/reduce conflict",
402 "%d shift/reduce conflicts", src_num
), src_num
);
406 if (src_num
> 0 && rrc_num
> 0)
408 sprintf (cp
, " %s ", _("and"));
414 sprintf (cp
, ngettext ("%d reduce/reduce conflict",
415 "%d reduce/reduce conflicts", rrc_num
), rrc_num
);
425 /*----------------------------------------------------------------.
426 | Same as above, but report the number of conflicts a` la POSIX. |
427 `----------------------------------------------------------------*/
430 conflict_report_yacc (int src_num
, int rrc_num
)
432 /* If invoked with `--yacc', use the output format specified by
434 fprintf (stderr
, _("conflicts: "));
436 fprintf (stderr
, _(" %d shift/reduce"), src_num
);
437 if (src_num
> 0 && rrc_num
> 0)
438 fprintf (stderr
, ",");
440 fprintf (stderr
, _(" %d reduce/reduce"), rrc_num
);
445 /*-----------------------------------------------------------.
446 | Output the detailed description of states with conflicts. |
447 `-----------------------------------------------------------*/
450 conflicts_output (FILE *out
)
452 bool printed_sth
= false;
454 for (i
= 0; i
< nstates
; i
++)
456 state_t
*s
= states
[i
];
459 fprintf (out
, _("State %d contains "), i
);
460 fprintf (out
, "%s.\n",
461 conflict_report (count_sr_conflicts (s
),
462 count_rr_conflicts (s
, true)));
470 /*--------------------------------------------------------.
471 | Total the number of S/R and R/R conflicts. Unlike the |
472 | code in conflicts_output, however, count EACH pair of |
473 | reductions for the same state and lookahead as one |
475 `--------------------------------------------------------*/
478 conflicts_total_count (void)
483 /* Conflicts by state. */
485 for (i
= 0; i
< nstates
; i
++)
488 count
+= count_sr_conflicts (states
[i
]);
489 count
+= count_rr_conflicts (states
[i
], false);
495 /*------------------------------------------.
496 | Reporting the total number of conflicts. |
497 `------------------------------------------*/
500 conflicts_print (void)
502 /* Is the number of SR conflicts OK? Either EXPECTED_CONFLICTS is
503 not set, and then we want 0 SR, or else it is specified, in which
504 case we want equality. */
510 /* Conflicts by state. */
514 for (i
= 0; i
< nstates
; i
++)
517 src_total
+= count_sr_conflicts (states
[i
]);
518 rrc_total
+= count_rr_conflicts (states
[i
], true);
522 src_ok
= src_total
== (expected_conflicts
== -1 ? 0 : expected_conflicts
);
524 /* If there are no RR conflicts, and as many SR conflicts as
525 expected, then there is nothing to report. */
526 if (!rrc_total
&& src_ok
)
529 /* Report the total number of conflicts on STDERR. */
531 conflict_report_yacc (src_total
, rrc_total
);
533 warn ("%s", conflict_report (src_total
, rrc_total
));
535 if (expected_conflicts
!= -1 && !src_ok
)
536 complain (ngettext ("expected %d shift/reduce conflict",
537 "expected %d shift/reduce conflicts",
544 conflicts_free (void)
547 bitset_free (shiftset
);
548 bitset_free (lookaheadset
);
549 obstack_free (&solved_conflicts_obstack
, NULL
);