1/* Find and resolve or report lookahead conflicts for bison, 2 3 Copyright (C) 1984, 1989, 1992, 2000-2007, 2009-2012 Free Software 4 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. */ 39int expected_sr_conflicts = -1; 40int expected_rr_conflicts = -1; 41static char *conflicts; 42static struct obstack solved_conflicts_obstack; 43static struct obstack solved_conflicts_xml_obstack; 44 45static bitset shift_set; 46static bitset lookahead_set; 47 48 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_printf (&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_printf (&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_printf (&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_printf (&solved_conflicts_obstack, 106 " (%s < %s)", 107 r->prec->tag, 108 symbols[token]->tag); 109 break; 110 111 case reduce_resolution: 112 obstack_printf (&solved_conflicts_obstack, 113 " (%s < %s)", 114 symbols[token]->tag, 115 r->prec->tag); 116 break; 117 118 case left_resolution: 119 obstack_printf (&solved_conflicts_obstack, 120 " (%%left %s)", 121 symbols[token]->tag); 122 break; 123 124 case right_resolution: 125 obstack_printf (&solved_conflicts_obstack, 126 " (%%right %s)", 127 symbols[token]->tag); 128 break; 129 130 case nonassoc_resolution: 131 obstack_printf (&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_printf (&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_printf (&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_printf (&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_printf (&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_printf (&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_printf (&solved_conflicts_xml_obstack, 192 "%%left %s", 193 xml_escape (symbols[token]->tag)); 194 break; 195 196 case right_resolution: 197 obstack_printf (&solved_conflicts_xml_obstack, 198 "%%right %s", 199 xml_escape (symbols[token]->tag)); 200 break; 201 202 case nonassoc_resolution: 203 obstack_printf (&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 220static void 221flush_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 240static void 241flush_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 259static void 260resolve_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 327static void 328set_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 384void 385conflicts_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 411void 412conflicts_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 426static int 427count_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 461static int 462count_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 488static void 489conflict_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 505void 506conflicts_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 532int 533conflicts_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 554void 555conflicts_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 (expected_sr_conflicts == -1 && expected_rr_conflicts == -1) 598 { 599 if (!(warnings_flag & warnings_conflicts_sr)) 600 src_total = 0; 601 if (!(warnings_flag & warnings_conflicts_rr)) 602 rrc_total = 0; 603 } 604 if (src_total | rrc_total) 605 { 606 if (expected_sr_conflicts == -1 && expected_rr_conflicts == -1) 607 set_warning_issued (); 608 if (! yacc_flag) 609 fprintf (stderr, "%s: ", current_file); 610 conflict_report (stderr, src_total, rrc_total); 611 } 612 613 if (expected_sr_conflicts != -1 || expected_rr_conflicts != -1) 614 { 615 if (! src_ok) 616 complain (ngettext ("expected %d shift/reduce conflict", 617 "expected %d shift/reduce conflicts", 618 src_expected), 619 src_expected); 620 if (! rrc_ok) 621 complain (ngettext ("expected %d reduce/reduce conflict", 622 "expected %d reduce/reduce conflicts", 623 rrc_expected), 624 rrc_expected); 625 } 626} 627 628 629void 630conflicts_free (void) 631{ 632 free (conflicts); 633 bitset_free (shift_set); 634 bitset_free (lookahead_set); 635 obstack_free (&solved_conflicts_obstack, NULL); 636 obstack_free (&solved_conflicts_xml_obstack, NULL); 637} 638