OLD | NEW |
(Empty) | |
| 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 2007 Free Software 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 |
| 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_fgrow2 (&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_fgrow2 (&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_fgrow2 (&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_fgrow2 (&solved_conflicts_obstack, |
| 106 " (%s < %s)", |
| 107 r->prec->tag, |
| 108 symbols[token]->tag); |
| 109 break; |
| 110 |
| 111 case reduce_resolution: |
| 112 obstack_fgrow2 (&solved_conflicts_obstack, |
| 113 " (%s < %s)", |
| 114 symbols[token]->tag, |
| 115 r->prec->tag); |
| 116 break; |
| 117 |
| 118 case left_resolution: |
| 119 obstack_fgrow1 (&solved_conflicts_obstack, |
| 120 " (%%left %s)", |
| 121 symbols[token]->tag); |
| 122 break; |
| 123 |
| 124 case right_resolution: |
| 125 obstack_fgrow1 (&solved_conflicts_obstack, |
| 126 " (%%right %s)", |
| 127 symbols[token]->tag); |
| 128 break; |
| 129 |
| 130 case nonassoc_resolution: |
| 131 obstack_fgrow1 (&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_fgrow2 (&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_fgrow2 (&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_fgrow2 (&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_fgrow2 (&solved_conflicts_xml_obstack, |
| 178 "%s < %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_fgrow2 (&solved_conflicts_xml_obstack, |
| 185 "%s < %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_fgrow1 (&solved_conflicts_xml_obstack, |
| 192 "%%left %s", |
| 193 xml_escape (symbols[token]->tag)); |
| 194 break; |
| 195 |
| 196 case right_resolution: |
| 197 obstack_fgrow1 (&solved_conflicts_xml_obstack, |
| 198 "%%right %s", |
| 199 xml_escape (symbols[token]->tag)); |
| 200 break; |
| 201 |
| 202 case nonassoc_resolution: |
| 203 obstack_fgrow1 (&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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 (src_total | rrc_total) |
| 598 { |
| 599 if (! yacc_flag) |
| 600 fprintf (stderr, "%s: ", current_file); |
| 601 conflict_report (stderr, src_total, rrc_total); |
| 602 } |
| 603 |
| 604 if (expected_sr_conflicts != -1 || expected_rr_conflicts != -1) |
| 605 { |
| 606 if (! src_ok) |
| 607 complain (ngettext ("expected %d shift/reduce conflict", |
| 608 "expected %d shift/reduce conflicts", |
| 609 src_expected), |
| 610 src_expected); |
| 611 if (! rrc_ok) |
| 612 complain (ngettext ("expected %d reduce/reduce conflict", |
| 613 "expected %d reduce/reduce conflicts", |
| 614 rrc_expected), |
| 615 rrc_expected); |
| 616 } |
| 617 } |
| 618 |
| 619 |
| 620 void |
| 621 conflicts_free (void) |
| 622 { |
| 623 free (conflicts); |
| 624 bitset_free (shift_set); |
| 625 bitset_free (lookahead_set); |
| 626 obstack_free (&solved_conflicts_obstack, NULL); |
| 627 obstack_free (&solved_conflicts_xml_obstack, NULL); |
| 628 } |
OLD | NEW |