Commit | Line | Data |
---|---|---|
08089d5d | 1 | /* Find and resolve or report look-ahead conflicts for bison, |
22c821f3 | 2 | Copyright 1984, 1989, 1992, 2000, 2001 Free Software Foundation, Inc. |
08089d5d | 3 | |
ceed8467 | 4 | This file is part of Bison, the GNU Compiler Compiler. |
08089d5d | 5 | |
ceed8467 AD |
6 | Bison is free software; you can redistribute it and/or modify it |
7 | under the terms of the GNU General Public License as published by | |
8 | the Free Software Foundation; either version 2, or (at your option) | |
9 | any later version. | |
08089d5d | 10 | |
ceed8467 AD |
11 | Bison is distributed in the hope that it will be useful, but |
12 | WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | General Public License for more details. | |
08089d5d | 15 | |
ceed8467 AD |
16 | You should have received a copy of the GNU General Public License |
17 | along with Bison; see the file COPYING. If not, write to the Free | |
18 | Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA | |
19 | 02111-1307, USA. */ | |
08089d5d | 20 | |
08089d5d | 21 | #include "system.h" |
7da99ede | 22 | #include "complain.h" |
ceed8467 | 23 | #include "getargs.h" |
0e78e603 | 24 | #include "symtab.h" |
08089d5d DM |
25 | #include "files.h" |
26 | #include "gram.h" | |
27 | #include "state.h" | |
720d742f | 28 | #include "lalr.h" |
0619caf0 | 29 | #include "conflicts.h" |
b2ca4022 AD |
30 | #include "reader.h" |
31 | #include "LR0.h" | |
d2729d44 | 32 | |
7da99ede AD |
33 | /* -1 stands for not specified. */ |
34 | int expected_conflicts = -1; | |
342b8b6e | 35 | static char *conflicts = NULL; |
08089d5d | 36 | |
342b8b6e AD |
37 | static unsigned *shiftset = NULL; |
38 | static unsigned *lookaheadset = NULL; | |
c29240e7 | 39 | \f |
08089d5d | 40 | |
c29240e7 | 41 | static inline void |
065fbd27 | 42 | log_resolution (state_t *state, int LAno, int token, char *resolution) |
08089d5d | 43 | { |
64d15509 AD |
44 | if (verbose_flag) |
45 | obstack_fgrow4 (&output_obstack, | |
46 | _("\ | |
c29240e7 | 47 | Conflict in state %d between rule %d and token %s resolved as %s.\n"), |
ad949da9 AD |
48 | state->number, LAruleno[LAno], symbols[token]->tag, |
49 | resolution); | |
08089d5d DM |
50 | } |
51 | ||
52 | ||
c29240e7 AD |
53 | /*------------------------------------------------------------------. |
54 | | Turn off the shift recorded for the specified token in the | | |
55 | | specified state. Used when we resolve a shift-reduce conflict in | | |
56 | | favor of the reduction. | | |
57 | `------------------------------------------------------------------*/ | |
58 | ||
4a120d45 | 59 | static void |
065fbd27 | 60 | flush_shift (state_t *state, int token) |
08089d5d | 61 | { |
065fbd27 | 62 | shifts *shiftp = state->shifts; |
9f136c07 | 63 | int i; |
c29240e7 | 64 | |
709ae8c6 | 65 | RESETBIT (lookaheadset, token); |
d954473d AD |
66 | for (i = 0; i < shiftp->nshifts; i++) |
67 | if (!SHIFT_IS_DISABLED (shiftp, i) && SHIFT_SYMBOL (shiftp, i) == token) | |
68 | SHIFT_DISABLE (shiftp, i); | |
08089d5d DM |
69 | } |
70 | ||
71 | ||
709ae8c6 AD |
72 | /*-------------------------------------------------------------------. |
73 | | Turn off the reduce recorded for the specified token for the | | |
74 | | specified lookahead. Used when we resolve a shift-reduce conflict | | |
75 | | in favor of the shift. | | |
76 | `-------------------------------------------------------------------*/ | |
77 | ||
78 | static void | |
79 | flush_reduce (int lookahead, int token) | |
80 | { | |
81 | RESETBIT (LA (lookahead), token); | |
82 | } | |
83 | ||
84 | ||
c29240e7 AD |
85 | /*------------------------------------------------------------------. |
86 | | Attempt to resolve shift-reduce conflict for one rule by means of | | |
87 | | precedence declarations. It has already been checked that the | | |
88 | | rule has a precedence. A conflict is resolved by modifying the | | |
89 | | shift or reduce tables so that there is no longer a conflict. | | |
90 | `------------------------------------------------------------------*/ | |
08089d5d | 91 | |
4a120d45 | 92 | static void |
065fbd27 | 93 | resolve_sr_conflict (state_t *state, int lookahead) |
08089d5d | 94 | { |
c29240e7 | 95 | int i; |
9f136c07 | 96 | /* find the rule to reduce by to get precedence of reduction */ |
1a2b5d37 | 97 | int redprec = rules[LAruleno[lookahead]].prec; |
2cec70b9 AD |
98 | errs *errp = errs_new (ntokens + 1); |
99 | errp->nerrs = 0; | |
08089d5d | 100 | |
08089d5d | 101 | for (i = 0; i < ntokens; i++) |
709ae8c6 | 102 | if (BITISSET (LA (lookahead), i) |
92b16366 | 103 | && BITISSET (lookaheadset, i) |
0e78e603 | 104 | && symbols[i]->prec) |
92b16366 | 105 | { |
709ae8c6 AD |
106 | /* Shift-reduce conflict occurs for token number i |
107 | and it has a precedence. | |
108 | The precedence of shifting is that of token i. */ | |
0e78e603 | 109 | if (symbols[i]->prec < redprec) |
92b16366 | 110 | { |
709ae8c6 | 111 | log_resolution (state, lookahead, i, _("reduce")); |
92b16366 AD |
112 | flush_shift (state, i); |
113 | } | |
0e78e603 | 114 | else if (symbols[i]->prec > redprec) |
92b16366 | 115 | { |
709ae8c6 AD |
116 | log_resolution (state, lookahead, i, _("shift")); |
117 | flush_reduce (lookahead, i); | |
92b16366 AD |
118 | } |
119 | else | |
709ae8c6 AD |
120 | /* Matching precedence levels. |
121 | For left association, keep only the reduction. | |
122 | For right association, keep only the shift. | |
123 | For nonassociation, keep neither. */ | |
124 | ||
5a670b1e | 125 | switch (symbols[i]->assoc) |
709ae8c6 AD |
126 | { |
127 | case right_assoc: | |
128 | log_resolution (state, lookahead, i, _("shift")); | |
129 | flush_reduce (lookahead, i); | |
130 | break; | |
131 | ||
132 | case left_assoc: | |
133 | log_resolution (state, lookahead, i, _("reduce")); | |
134 | flush_shift (state, i); | |
135 | break; | |
136 | ||
137 | case non_assoc: | |
138 | log_resolution (state, lookahead, i, _("an error")); | |
139 | flush_shift (state, i); | |
140 | flush_reduce (lookahead, i); | |
141 | /* Record an explicit error for this token. */ | |
2cec70b9 | 142 | errp->errs[errp->nerrs++] = i; |
709ae8c6 AD |
143 | break; |
144 | } | |
92b16366 AD |
145 | } |
146 | ||
92b16366 AD |
147 | /* Some tokens have been explicitly made errors. Allocate a |
148 | permanent errs structure for this state, to record them. */ | |
2cec70b9 | 149 | state->errs = errs_dup (errp); |
c29240e7 | 150 | free (errp); |
08089d5d DM |
151 | } |
152 | ||
153 | ||
4a120d45 | 154 | static void |
065fbd27 | 155 | set_conflicts (state_t *state) |
08089d5d | 156 | { |
d8cf039f | 157 | int i, j; |
c29240e7 | 158 | shifts *shiftp; |
c29240e7 | 159 | |
065fbd27 | 160 | if (state->consistent) |
c29240e7 | 161 | return; |
08089d5d | 162 | |
c29240e7 AD |
163 | for (i = 0; i < tokensetsize; i++) |
164 | lookaheadset[i] = 0; | |
08089d5d | 165 | |
065fbd27 | 166 | shiftp = state->shifts; |
d954473d AD |
167 | for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) |
168 | if (!SHIFT_IS_DISABLED (shiftp, i)) | |
169 | SETBIT (lookaheadset, SHIFT_SYMBOL (shiftp, i)); | |
08089d5d | 170 | |
c29240e7 AD |
171 | /* Loop over all rules which require lookahead in this state. First |
172 | check for shift-reduce conflict, and try to resolve using | |
173 | precedence */ | |
065fbd27 | 174 | for (i = 0; i < state->nlookaheads; ++i) |
1a2b5d37 | 175 | if (rules[LAruleno[state->lookaheadsp + i]].prec) |
d8cf039f | 176 | for (j = 0; j < tokensetsize; ++j) |
065fbd27 | 177 | if (LA (state->lookaheadsp + i)[j] & lookaheadset[j]) |
c29240e7 | 178 | { |
065fbd27 | 179 | resolve_sr_conflict (state, state->lookaheadsp + i); |
d8cf039f | 180 | break; |
c29240e7 | 181 | } |
08089d5d | 182 | |
08089d5d | 183 | |
c29240e7 AD |
184 | /* Loop over all rules which require lookahead in this state. Check |
185 | for conflicts not resolved above. */ | |
065fbd27 | 186 | for (i = 0; i < state->nlookaheads; ++i) |
08089d5d | 187 | { |
d8cf039f | 188 | for (j = 0; j < tokensetsize; ++j) |
065fbd27 AD |
189 | if (LA (state->lookaheadsp + i)[j] & lookaheadset[j]) |
190 | conflicts[state->number] = 1; | |
08089d5d | 191 | |
d8cf039f | 192 | for (j = 0; j < tokensetsize; ++j) |
065fbd27 | 193 | lookaheadset[j] |= LA (state->lookaheadsp + i)[j]; |
c29240e7 AD |
194 | } |
195 | } | |
08089d5d DM |
196 | |
197 | void | |
342b8b6e | 198 | solve_conflicts (void) |
08089d5d | 199 | { |
c29240e7 | 200 | int i; |
08089d5d | 201 | |
d7913476 AD |
202 | conflicts = XCALLOC (char, nstates); |
203 | shiftset = XCALLOC (unsigned, tokensetsize); | |
204 | lookaheadset = XCALLOC (unsigned, tokensetsize); | |
08089d5d | 205 | |
c29240e7 | 206 | for (i = 0; i < nstates; i++) |
29e88316 | 207 | set_conflicts (states[i]); |
08089d5d DM |
208 | } |
209 | ||
210 | ||
c29240e7 AD |
211 | /*---------------------------------------------. |
212 | | Count the number of shift/reduce conflicts. | | |
213 | `---------------------------------------------*/ | |
214 | ||
0df87bb6 | 215 | static int |
065fbd27 | 216 | count_sr_conflicts (state_t *state) |
08089d5d | 217 | { |
52afa962 | 218 | int i, k; |
0df87bb6 | 219 | int src_count = 0; |
065fbd27 | 220 | shifts *shiftp = state->shifts; |
08089d5d | 221 | |
c29240e7 | 222 | if (!shiftp) |
0df87bb6 | 223 | return 0; |
08089d5d DM |
224 | |
225 | for (i = 0; i < tokensetsize; i++) | |
226 | { | |
227 | shiftset[i] = 0; | |
228 | lookaheadset[i] = 0; | |
229 | } | |
230 | ||
52afa962 | 231 | for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) |
9839bbe5 AD |
232 | if (!SHIFT_IS_DISABLED (shiftp, i)) |
233 | SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i)); | |
08089d5d | 234 | |
065fbd27 | 235 | for (i = 0; i < state->nlookaheads; ++i) |
52afa962 | 236 | for (k = 0; k < tokensetsize; ++k) |
065fbd27 | 237 | lookaheadset[k] |= LA (state->lookaheadsp + i)[k]; |
08089d5d | 238 | |
52afa962 AD |
239 | for (k = 0; k < tokensetsize; ++k) |
240 | lookaheadset[k] &= shiftset[k]; | |
08089d5d | 241 | |
08089d5d | 242 | for (i = 0; i < ntokens; i++) |
52afa962 AD |
243 | if (BITISSET (lookaheadset, i)) |
244 | src_count++; | |
0df87bb6 AD |
245 | |
246 | return src_count; | |
08089d5d DM |
247 | } |
248 | ||
249 | ||
c29240e7 AD |
250 | /*----------------------------------------------. |
251 | | Count the number of reduce/reduce conflicts. | | |
252 | `----------------------------------------------*/ | |
253 | ||
0df87bb6 | 254 | static int |
065fbd27 | 255 | count_rr_conflicts (state_t *state) |
08089d5d | 256 | { |
c29240e7 | 257 | int i; |
0df87bb6 | 258 | int rrc_count = 0; |
08089d5d | 259 | |
065fbd27 | 260 | if (state->nlookaheads < 2) |
0df87bb6 | 261 | return 0; |
08089d5d | 262 | |
08089d5d DM |
263 | for (i = 0; i < ntokens; i++) |
264 | { | |
0df87bb6 AD |
265 | int count = 0; |
266 | int j; | |
065fbd27 | 267 | for (j = 0; j < state->nlookaheads; ++j) |
3460813b | 268 | if (BITISSET (LA (state->lookaheadsp + j), i)) |
52afa962 | 269 | count++; |
08089d5d | 270 | |
c29240e7 AD |
271 | if (count >= 2) |
272 | rrc_count++; | |
08089d5d | 273 | } |
0df87bb6 AD |
274 | |
275 | return rrc_count; | |
08089d5d DM |
276 | } |
277 | ||
ff4423cc AD |
278 | /*--------------------------------------------------------------. |
279 | | Return a human readable string which reports shift/reduce and | | |
280 | | reduce/reduce conflict numbers (SRC_NUM, RRC_NUM). | | |
281 | `--------------------------------------------------------------*/ | |
c29240e7 | 282 | |
ff4423cc AD |
283 | static const char * |
284 | conflict_report (int src_num, int rrc_num) | |
c29240e7 | 285 | { |
ff4423cc AD |
286 | static char res[4096]; |
287 | char *cp = res; | |
288 | ||
7da99ede | 289 | if (src_num >= 1) |
22c821f3 | 290 | { |
7da99ede AD |
291 | sprintf (cp, ngettext ("%d shift/reduce conflict", |
292 | "%d shift/reduce conflicts", src_num), src_num); | |
22c821f3 AD |
293 | cp += strlen (cp); |
294 | } | |
c29240e7 | 295 | |
0619caf0 | 296 | if (src_num > 0 && rrc_num > 0) |
22c821f3 | 297 | { |
7da99ede | 298 | sprintf (cp, " %s ", _("and")); |
22c821f3 AD |
299 | cp += strlen (cp); |
300 | } | |
c29240e7 | 301 | |
7da99ede | 302 | if (rrc_num >= 1) |
22c821f3 | 303 | { |
7da99ede AD |
304 | sprintf (cp, ngettext ("%d reduce/reduce conflict", |
305 | "%d reduce/reduce conflicts", rrc_num), rrc_num); | |
22c821f3 AD |
306 | cp += strlen (cp); |
307 | } | |
ff4423cc AD |
308 | |
309 | *cp++ = '.'; | |
310 | *cp++ = '\n'; | |
311 | *cp++ = '\0'; | |
c29240e7 | 312 | |
ff4423cc | 313 | return res; |
c29240e7 AD |
314 | } |
315 | ||
316 | ||
0df87bb6 AD |
317 | /*-----------------------------------------------------------. |
318 | | Output the detailed description of states with conflicts. | | |
319 | `-----------------------------------------------------------*/ | |
c29240e7 AD |
320 | |
321 | void | |
0df87bb6 | 322 | conflicts_output (FILE *out) |
c29240e7 | 323 | { |
d2d1b42b | 324 | bool printed_sth = FALSE; |
c29240e7 | 325 | int i; |
0df87bb6 AD |
326 | for (i = 0; i < nstates; i++) |
327 | if (conflicts[i]) | |
328 | { | |
7da99ede | 329 | fprintf (out, _("State %d contains "), i); |
29e88316 AD |
330 | fputs (conflict_report (count_sr_conflicts (states[i]), |
331 | count_rr_conflicts (states[i])), out); | |
d2d1b42b | 332 | printed_sth = TRUE; |
0df87bb6 | 333 | } |
d2d1b42b AD |
334 | if (printed_sth) |
335 | fputs ("\n\n", out); | |
0df87bb6 | 336 | } |
c29240e7 | 337 | |
c29240e7 | 338 | |
0df87bb6 AD |
339 | /*------------------------------------------. |
340 | | Reporting the total number of conflicts. | | |
341 | `------------------------------------------*/ | |
0619caf0 | 342 | |
0df87bb6 AD |
343 | void |
344 | conflicts_print (void) | |
345 | { | |
346 | int i; | |
347 | ||
a034c8b8 AD |
348 | /* Is the number of SR conflicts OK? Either EXPECTED_CONFLICTS is |
349 | not set, and then we want 0 SR, or else it is specified, in which | |
350 | case we want equality. */ | |
351 | int src_ok = 0; | |
352 | ||
0df87bb6 AD |
353 | int src_total = 0; |
354 | int rrc_total = 0; | |
355 | ||
356 | /* Conflicts by state. */ | |
357 | for (i = 0; i < nstates; i++) | |
358 | if (conflicts[i]) | |
359 | { | |
29e88316 AD |
360 | src_total += count_sr_conflicts (states[i]); |
361 | rrc_total += count_rr_conflicts (states[i]); | |
0df87bb6 | 362 | } |
c29240e7 | 363 | |
a034c8b8 AD |
364 | src_ok = src_total == (expected_conflicts == -1 ? 0 : expected_conflicts); |
365 | ||
366 | /* If there are no RR conflicts, and as many SR conflicts as | |
367 | expected, then there is nothing to report. */ | |
368 | if (!rrc_total && src_ok) | |
369 | return; | |
370 | ||
0619caf0 | 371 | /* Report the total number of conflicts on STDERR. */ |
a034c8b8 | 372 | if (yacc_flag) |
09b503c8 | 373 | { |
a034c8b8 AD |
374 | /* If invoked with `--yacc', use the output format specified by |
375 | POSIX. */ | |
376 | fprintf (stderr, _("conflicts: ")); | |
377 | if (src_total > 0) | |
378 | fprintf (stderr, _(" %d shift/reduce"), src_total); | |
379 | if (src_total > 0 && rrc_total > 0) | |
380 | fprintf (stderr, ","); | |
381 | if (rrc_total > 0) | |
382 | fprintf (stderr, _(" %d reduce/reduce"), rrc_total); | |
383 | putc ('\n', stderr); | |
384 | } | |
385 | else | |
386 | { | |
387 | fprintf (stderr, _("%s contains "), infile); | |
388 | fputs (conflict_report (src_total, rrc_total), stderr); | |
09b503c8 | 389 | } |
7da99ede | 390 | |
a034c8b8 | 391 | if (expected_conflicts != -1 && !src_ok) |
7da99ede AD |
392 | { |
393 | complain_message_count++; | |
81e895c0 AD |
394 | fprintf (stderr, ngettext ("expected %d shift/reduce conflict\n", |
395 | "expected %d shift/reduce conflicts\n", | |
7da99ede AD |
396 | expected_conflicts), |
397 | expected_conflicts); | |
398 | } | |
c29240e7 AD |
399 | } |
400 | ||
401 | ||
08089d5d | 402 | void |
342b8b6e | 403 | free_conflicts (void) |
08089d5d | 404 | { |
d7913476 AD |
405 | XFREE (conflicts); |
406 | XFREE (shiftset); | |
407 | XFREE (lookaheadset); | |
08089d5d | 408 | } |