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