src/conflicts.c

   1 /* Find and resolve or report look-ahead conflicts for bison,
   2    Copyright 1984, 1989, 1992, 2000, 2001 Free Software Foundation, Inc.
   3
   4    This file is part of Bison, the GNU Compiler Compiler.
   5
   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.
  10
  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.
  15
  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.  */
  20
  21 #include "system.h"
  22 #include "getargs.h"
  23 #include "files.h"
  24 #include "gram.h"
  25 #include "state.h"
  26 #include "lalr.h"
  27 #include "conflicts.h"
  28 #include "reader.h"
  29 #include "LR0.h"
  30
  31 int any_conflicts = 0;
  32 errs **err_table = NULL;
  33 int expected_conflicts;
  34 static char *conflicts = NULL;
  35
  36 static unsigned *shiftset = NULL;
  37 static unsigned *lookaheadset = NULL;
  38 static int src_count;
  39 static int rrc_count;
  40 \f
  41
  42 static inline void
  43 log_resolution (int state, int LAno, int token, char *resolution)
  44 {
  45   obstack_fgrow4 (&output_obstack,
  46                   _("\
  47 Conflict in state %d between rule %d and token %s resolved as %s.\n"),
  48                   state, LAruleno[LAno], tags[token], resolution);
  49 }
  50
  51
  52 /*------------------------------------------------------------------.
  53 | Turn off the shift recorded for the specified token in the        |
  54 | specified state.  Used when we resolve a shift-reduce conflict in |
  55 | favor of the reduction.                                           |
  56 `------------------------------------------------------------------*/
  57
  58 static void
  59 flush_shift (int state, int token)
  60 {
  61   shifts *shiftp;
  62   int k, i;
  63
  64   shiftp = shift_table[state];
  65
  66   if (shiftp)
  67     {
  68       k = shiftp->nshifts;
  69       for (i = 0; i < k; i++)
  70         {
  71           if (shiftp->shifts[i]
  72               && token == accessing_symbol[shiftp->shifts[i]])
  73             (shiftp->shifts[i]) = 0;
  74         }
  75     }
  76 }
  77
  78
  79 /*------------------------------------------------------------------.
  80 | Attempt to resolve shift-reduce conflict for one rule by means of |
  81 | precedence declarations.  It has already been checked that the    |
  82 | rule has a precedence.  A conflict is resolved by modifying the   |
  83 | shift or reduce tables so that there is no longer a conflict.     |
  84 `------------------------------------------------------------------*/
  85
  86 static void
  87 resolve_sr_conflict (int state, int lookaheadnum)
  88 {
  89   int i;
  90   int mask;
  91   unsigned *fp1;
  92   unsigned *fp2;
  93   int redprec;
  94   errs *errp = (errs *) xcalloc (sizeof (errs) + ntokens * sizeof (short), 1);
  95   short *errtokens = errp->errs;
  96
  97   /* find the rule to reduce by to get precedence of reduction  */
  98   redprec = rprec[LAruleno[lookaheadnum]];
  99
 100   mask = 1;
 101   fp1 = LA + lookaheadnum * tokensetsize;
 102   fp2 = lookaheadset;
 103   for (i = 0; i < ntokens; i++)
 104     {
 105       if ((mask & *fp2 & *fp1) && sprec[i])
 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.  */
 109         {
 110           if (sprec[i] < redprec)
 111             {
 112               log_resolution (state, lookaheadnum, i, _("reduce"));
 113               *fp2 &= ~mask;    /* flush the shift for this token */
 114               flush_shift (state, i);
 115             }
 116           else if (sprec[i] > redprec)
 117             {
 118               log_resolution (state, lookaheadnum, i, _("shift"));
 119               *fp1 &= ~mask;    /* flush the reduce for this token */
 120             }
 121           else
 122             {
 123               /* Matching precedence levels.
 124                  For left association, keep only the reduction.
 125                  For right association, keep only the shift.
 126                  For nonassociation, keep neither.  */
 127
 128               switch (sassoc[i])
 129                 {
 130                 case right_assoc:
 131                   log_resolution (state, lookaheadnum, i, _("shift"));
 132                   break;
 133
 134                 case left_assoc:
 135                   log_resolution (state, lookaheadnum, i, _("reduce"));
 136                   break;
 137
 138                 case non_assoc:
 139                   log_resolution (state, lookaheadnum, i, _("an error"));
 140                   break;
 141                 }
 142
 143               if (sassoc[i] != right_assoc)
 144                 {
 145                   *fp2 &= ~mask;        /* flush the shift for this token */
 146                   flush_shift (state, i);
 147                 }
 148               if (sassoc[i] != left_assoc)
 149                 {
 150                   *fp1 &= ~mask;        /* flush the reduce for this token */
 151                 }
 152               if (sassoc[i] == non_assoc)
 153                 {
 154                   /* Record an explicit error for this token.  */
 155                   *errtokens++ = i;
 156                 }
 157             }
 158         }
 159
 160       mask <<= 1;
 161       if (mask == 0)
 162         {
 163           mask = 1;
 164           fp2++;
 165           fp1++;
 166         }
 167     }
 168   errp->nerrs = errtokens - errp->errs;
 169   if (errp->nerrs)
 170     {
 171       /* Some tokens have been explicitly made errors.  Allocate
 172          a permanent errs structure for this state, to record them.  */
 173       i = (char *) errtokens - (char *) errp;
 174       err_table[state] = (errs *) xcalloc ((unsigned int) i, 1);
 175       bcopy (errp, err_table[state], i);
 176     }
 177   else
 178     err_table[state] = 0;
 179   free (errp);
 180 }
 181
 182
 183 static void
 184 set_conflicts (int state)
 185 {
 186   int i;
 187   int k;
 188   shifts *shiftp;
 189   unsigned *fp2;
 190   unsigned *fp3;
 191   unsigned *fp4;
 192   unsigned *fp1;
 193   int symbol;
 194
 195   if (consistent[state])
 196     return;
 197
 198   for (i = 0; i < tokensetsize; i++)
 199     lookaheadset[i] = 0;
 200
 201   shiftp = shift_table[state];
 202   if (shiftp)
 203     {
 204       k = shiftp->nshifts;
 205       for (i = 0; i < k; i++)
 206         {
 207           symbol = accessing_symbol[shiftp->shifts[i]];
 208           if (ISVAR (symbol))
 209             break;
 210           SETBIT (lookaheadset, symbol);
 211         }
 212     }
 213
 214   k = lookaheads[state + 1];
 215   fp4 = lookaheadset + tokensetsize;
 216
 217   /* Loop over all rules which require lookahead in this state.  First
 218      check for shift-reduce conflict, and try to resolve using
 219      precedence */
 220   for (i = lookaheads[state]; i < k; i++)
 221     if (rprec[LAruleno[i]])
 222       {
 223         fp1 = LA + i * tokensetsize;
 224         fp2 = fp1;
 225         fp3 = lookaheadset;
 226
 227         while (fp3 < fp4)
 228           {
 229             if (*fp2++ & *fp3++)
 230               {
 231                 resolve_sr_conflict (state, i);
 232                 break;
 233               }
 234           }
 235       }
 236
 237
 238   /* Loop over all rules which require lookahead in this state.  Check
 239      for conflicts not resolved above.  */
 240   for (i = lookaheads[state]; i < k; i++)
 241     {
 242       fp1 = LA + i * tokensetsize;
 243       fp2 = fp1;
 244       fp3 = lookaheadset;
 245
 246       while (fp3 < fp4)
 247         {
 248           if (*fp2++ & *fp3++)
 249             {
 250               conflicts[state] = 1;
 251               any_conflicts = 1;
 252             }
 253         }
 254
 255       fp2 = fp1;
 256       fp3 = lookaheadset;
 257
 258       while (fp3 < fp4)
 259         *fp3++ |= *fp2++;
 260     }
 261 }
 262
 263 void
 264 solve_conflicts (void)
 265 {
 266   int i;
 267
 268   conflicts = XCALLOC (char, nstates);
 269   shiftset = XCALLOC (unsigned, tokensetsize);
 270   lookaheadset = XCALLOC (unsigned, tokensetsize);
 271
 272   err_table = XCALLOC (errs *, nstates);
 273
 274   any_conflicts = 0;
 275
 276   for (i = 0; i < nstates; i++)
 277     set_conflicts (i);
 278 }
 279
 280
 281 /*---------------------------------------------.
 282 | Count the number of shift/reduce conflicts.  |
 283 `---------------------------------------------*/
 284
 285 static void
 286 count_sr_conflicts (int state)
 287 {
 288   int i;
 289   int k;
 290   int mask;
 291   shifts *shiftp;
 292   unsigned *fp1;
 293   unsigned *fp2;
 294   unsigned *fp3;
 295   int symbol;
 296
 297   src_count = 0;
 298
 299   shiftp = shift_table[state];
 300   if (!shiftp)
 301     return;
 302
 303   for (i = 0; i < tokensetsize; i++)
 304     {
 305       shiftset[i] = 0;
 306       lookaheadset[i] = 0;
 307     }
 308
 309   k = shiftp->nshifts;
 310   for (i = 0; i < k; i++)
 311     {
 312       if (!shiftp->shifts[i])
 313         continue;
 314       symbol = accessing_symbol[shiftp->shifts[i]];
 315       if (ISVAR (symbol))
 316         break;
 317       SETBIT (shiftset, symbol);
 318     }
 319
 320   k = lookaheads[state + 1];
 321   fp3 = lookaheadset + tokensetsize;
 322
 323   for (i = lookaheads[state]; i < k; i++)
 324     {
 325       fp1 = LA + i * tokensetsize;
 326       fp2 = lookaheadset;
 327
 328       while (fp2 < fp3)
 329         *fp2++ |= *fp1++;
 330     }
 331
 332   fp1 = shiftset;
 333   fp2 = lookaheadset;
 334
 335   while (fp2 < fp3)
 336     *fp2++ &= *fp1++;
 337
 338   mask = 1;
 339   fp2 = lookaheadset;
 340   for (i = 0; i < ntokens; i++)
 341     {
 342       if (mask & *fp2)
 343         src_count++;
 344
 345       mask <<= 1;
 346       if (mask == 0)
 347         {
 348           mask = 1;
 349           fp2++;
 350         }
 351     }
 352 }
 353
 354
 355 /*----------------------------------------------.
 356 | Count the number of reduce/reduce conflicts.  |
 357 `----------------------------------------------*/
 358
 359 static void
 360 count_rr_conflicts (int state)
 361 {
 362   int i;
 363   int j;
 364   int count;
 365   unsigned mask;
 366   unsigned *baseword;
 367   unsigned *wordp;
 368   int m;
 369   int n;
 370
 371   rrc_count = 0;
 372
 373   m = lookaheads[state];
 374   n = lookaheads[state + 1];
 375
 376   if (n - m < 2)
 377     return;
 378
 379   mask = 1;
 380   baseword = LA + m * tokensetsize;
 381   for (i = 0; i < ntokens; i++)
 382     {
 383       wordp = baseword;
 384
 385       count = 0;
 386       for (j = m; j < n; j++)
 387         {
 388           if (mask & *wordp)
 389             count++;
 390
 391           wordp += tokensetsize;
 392         }
 393
 394       if (count >= 2)
 395         rrc_count++;
 396
 397       mask <<= 1;
 398       if (mask == 0)
 399         {
 400           mask = 1;
 401           baseword++;
 402         }
 403     }
 404 }
 405
 406 /*--------------------------------------------------------------.
 407 | Return a human readable string which reports shift/reduce and |
 408 | reduce/reduce conflict numbers (SRC_NUM, RRC_NUM).            |
 409 `--------------------------------------------------------------*/
 410
 411 static const char *
 412 conflict_report (int src_num, int rrc_num)
 413 {
 414   static char res[4096];
 415   char *cp = res;
 416
 417   if (src_num == 1)
 418     {
 419       sprintf (cp, _(" 1 shift/reduce conflict"));
 420       cp += strlen (cp);
 421     }
 422   else if (src_num > 1)
 423     {
 424       sprintf (cp, _(" %d shift/reduce conflicts"), src_num);
 425       cp += strlen (cp);
 426     }
 427
 428   if (src_num > 0 && rrc_num > 0)
 429     {
 430       sprintf (cp, _(" and"));
 431       cp += strlen (cp);
 432     }
 433
 434   if (rrc_num == 1)
 435     {
 436       sprintf (cp, _(" 1 reduce/reduce conflict"));
 437       cp += strlen (cp);
 438     }
 439   else if (rrc_num > 1)
 440     {
 441       sprintf (cp, _(" %d reduce/reduce conflicts"), rrc_num);
 442       cp += strlen (cp);
 443     }
 444
 445   *cp++ = '.';
 446   *cp++ = '\n';
 447   *cp++ = '\0';
 448
 449   return res;
 450 }
 451
 452
 453 /*---------------------------------------------.
 454 | Compute and give a report on the conflicts.  |
 455 `---------------------------------------------*/
 456
 457 void
 458 print_conflicts (FILE *out)
 459 {
 460   int i;
 461   int src_total;
 462   int rrc_total;
 463
 464   src_total = 0;
 465   rrc_total = 0;
 466
 467   /* Count the total number of conflicts, and if wanted, give a
 468      detailed report in FOUTPUT.  */
 469   for (i = 0; i < nstates; i++)
 470     {
 471       if (conflicts[i])
 472         {
 473           count_sr_conflicts (i);
 474           count_rr_conflicts (i);
 475           src_total += src_count;
 476           rrc_total += rrc_count;
 477
 478           if (verbose_flag)
 479             {
 480               fprintf (out, _("State %d contains"), i);
 481               fputs (conflict_report (src_count, rrc_count), out);
 482             }
 483         }
 484     }
 485
 486   /* Report the total number of conflicts on STDERR.  */
 487   if (yacc_flag)
 488     {
 489       /* If invoked with `--yacc', use the output format specified by
 490          POSIX.  */
 491       fprintf (stderr, _("conflicts: "));
 492       if (src_total > 0)
 493         fprintf (stderr, _(" %d shift/reduce"), src_total);
 494       if (src_total > 0 && rrc_total > 0)
 495         fprintf (stderr, ",");
 496       if (rrc_total > 0)
 497         fprintf (stderr, _(" %d reduce/reduce"), rrc_total);
 498       putc ('\n', stderr);
 499     }
 500   else
 501     {
 502       fprintf (stderr, _("%s contains"), infile);
 503       fputs (conflict_report (src_total, rrc_total), stderr);
 504     }
 505 }
 506
 507
 508 void
 509 print_reductions (int state)
 510 {
 511   int i;
 512   int j;
 513   int k;
 514   unsigned *fp1;
 515   unsigned *fp2;
 516   unsigned *fp3;
 517   unsigned *fp4;
 518   int rule;
 519   int symbol;
 520   unsigned mask;
 521   int m;
 522   int n;
 523   int default_LA;
 524   int default_rule = 0;
 525   int cmax;
 526   int count;
 527   shifts *shiftp;
 528   errs *errp;
 529   int nodefault = 0;
 530
 531   for (i = 0; i < tokensetsize; i++)
 532     shiftset[i] = 0;
 533
 534   shiftp = shift_table[state];
 535   if (shiftp)
 536     {
 537       k = shiftp->nshifts;
 538       for (i = 0; i < k; i++)
 539         {
 540           if (!shiftp->shifts[i])
 541             continue;
 542           symbol = accessing_symbol[shiftp->shifts[i]];
 543           if (ISVAR (symbol))
 544             break;
 545           /* if this state has a shift for the error token,
 546              don't use a default rule.  */
 547           if (symbol == error_token_number)
 548             nodefault = 1;
 549           SETBIT (shiftset, symbol);
 550         }
 551     }
 552
 553   errp = err_table[state];
 554   if (errp)
 555     {
 556       k = errp->nerrs;
 557       for (i = 0; i < k; i++)
 558         {
 559           if (!errp->errs[i])
 560             continue;
 561           symbol = errp->errs[i];
 562           SETBIT (shiftset, symbol);
 563         }
 564     }
 565
 566   m = lookaheads[state];
 567   n = lookaheads[state + 1];
 568
 569   if (n - m == 1 && !nodefault)
 570     {
 571       default_rule = LAruleno[m];
 572
 573       fp1 = LA + m * tokensetsize;
 574       fp2 = shiftset;
 575       fp3 = lookaheadset;
 576       fp4 = lookaheadset + tokensetsize;
 577
 578       while (fp3 < fp4)
 579         *fp3++ = *fp1++ & *fp2++;
 580
 581       mask = 1;
 582       fp3 = lookaheadset;
 583
 584       for (i = 0; i < ntokens; i++)
 585         {
 586           if (mask & *fp3)
 587             obstack_fgrow3 (&output_obstack,
 588                             _("    %-4s\t[reduce using rule %d (%s)]\n"),
 589                             tags[i], default_rule, tags[rlhs[default_rule]]);
 590
 591           mask <<= 1;
 592           if (mask == 0)
 593             {
 594               mask = 1;
 595               fp3++;
 596             }
 597         }
 598
 599       obstack_fgrow2 (&output_obstack,
 600                       _("    $default\treduce using rule %d (%s)\n\n"),
 601                       default_rule, tags[rlhs[default_rule]]);
 602     }
 603   else if (n - m >= 1)
 604     {
 605       cmax = 0;
 606       default_LA = -1;
 607       fp4 = lookaheadset + tokensetsize;
 608
 609       if (!nodefault)
 610         for (i = m; i < n; i++)
 611           {
 612             fp1 = LA + i * tokensetsize;
 613             fp2 = shiftset;
 614             fp3 = lookaheadset;
 615
 616             while (fp3 < fp4)
 617               *fp3++ = *fp1++ & (~(*fp2++));
 618
 619             count = 0;
 620             mask = 1;
 621             fp3 = lookaheadset;
 622             for (j = 0; j < ntokens; j++)
 623               {
 624                 if (mask & *fp3)
 625                   count++;
 626
 627                 mask <<= 1;
 628                 if (mask == 0)
 629                   {
 630                     mask = 1;
 631                     fp3++;
 632                   }
 633               }
 634
 635             if (count > cmax)
 636               {
 637                 cmax = count;
 638                 default_LA = i;
 639                 default_rule = LAruleno[i];
 640               }
 641
 642             fp2 = shiftset;
 643             fp3 = lookaheadset;
 644
 645             while (fp3 < fp4)
 646               *fp2++ |= *fp3++;
 647           }
 648
 649       for (i = 0; i < tokensetsize; i++)
 650         shiftset[i] = 0;
 651
 652       if (shiftp)
 653         {
 654           k = shiftp->nshifts;
 655           for (i = 0; i < k; i++)
 656             {
 657               if (!shiftp->shifts[i])
 658                 continue;
 659               symbol = accessing_symbol[shiftp->shifts[i]];
 660               if (ISVAR (symbol))
 661                 break;
 662               SETBIT (shiftset, symbol);
 663             }
 664         }
 665
 666       mask = 1;
 667       fp1 = LA + m * tokensetsize;
 668       fp2 = shiftset;
 669       for (i = 0; i < ntokens; i++)
 670         {
 671           int defaulted = 0;
 672
 673           if (mask & *fp2)
 674             count = 1;
 675           else
 676             count = 0;
 677
 678           fp3 = fp1;
 679           for (j = m; j < n; j++)
 680             {
 681               if (mask & *fp3)
 682                 {
 683                   if (count == 0)
 684                     {
 685                       if (j != default_LA)
 686                         {
 687                           rule = LAruleno[j];
 688                           obstack_fgrow3 (&output_obstack,
 689                                    _("    %-4s\treduce using rule %d (%s)\n"),
 690                                    tags[i], rule, tags[rlhs[rule]]);
 691                         }
 692                       else
 693                         defaulted = 1;
 694
 695                       count++;
 696                     }
 697                   else
 698                     {
 699                       if (defaulted)
 700                         {
 701                           rule = LAruleno[default_LA];
 702                           obstack_fgrow3 (&output_obstack,
 703                                    _("    %-4s\treduce using rule %d (%s)\n"),
 704                                    tags[i], rule, tags[rlhs[rule]]);
 705                           defaulted = 0;
 706                         }
 707                       rule = LAruleno[j];
 708                       obstack_fgrow3 (&output_obstack,
 709                                _("    %-4s\t[reduce using rule %d (%s)]\n"),
 710                                tags[i], rule, tags[rlhs[rule]]);
 711                     }
 712                 }
 713
 714               fp3 += tokensetsize;
 715             }
 716
 717           mask <<= 1;
 718           if (mask == 0)
 719             {
 720               mask = 1;
 721               /* We tried incrementing just fp1, and just fp2; both seem wrong.
 722                  It seems necessary to increment both in sync.  */
 723               fp1++;
 724               fp2++;
 725             }
 726         }
 727
 728       if (default_LA >= 0)
 729         obstack_fgrow2 (&output_obstack,
 730                         _("    $default\treduce using rule %d (%s)\n"),
 731                         default_rule, tags[rlhs[default_rule]]);
 732
 733       obstack_1grow (&output_obstack, '\n');
 734     }
 735 }
 736
 737
 738 void
 739 free_conflicts (void)
 740 {
 741   XFREE (conflicts);
 742   XFREE (shiftset);
 743   XFREE (lookaheadset);
 744 }