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_total;
  39 static int rrc_total;
  40 static int src_count;
  41 static int rrc_count;
  42 \f
  43
  44 static inline void
  45 log_resolution (int state, int LAno, int token, char *resolution)
  46 {
  47   obstack_fgrow4 (&output_obstack,
  48                   _("\
  49 Conflict in state %d between rule %d and token %s resolved as %s.\n"),
  50                   state, LAruleno[LAno], tags[token], resolution);
  51 }
  52
  53
  54 /*------------------------------------------------------------------.
  55 | Turn off the shift recorded for the specified token in the        |
  56 | specified state.  Used when we resolve a shift-reduce conflict in |
  57 | favor of the reduction.                                           |
  58 `------------------------------------------------------------------*/
  59
  60 static void
  61 flush_shift (int state, int token)
  62 {
  63   shifts *shiftp;
  64   int k, i;
  65
  66   shiftp = shift_table[state];
  67
  68   if (shiftp)
  69     {
  70       k = shiftp->nshifts;
  71       for (i = 0; i < k; i++)
  72         {
  73           if (shiftp->shifts[i]
  74               && token == accessing_symbol[shiftp->shifts[i]])
  75             (shiftp->shifts[i]) = 0;
  76         }
  77     }
  78 }
  79
  80
  81 /*------------------------------------------------------------------.
  82 | Attempt to resolve shift-reduce conflict for one rule by means of |
  83 | precedence declarations.  It has already been checked that the    |
  84 | rule has a precedence.  A conflict is resolved by modifying the   |
  85 | shift or reduce tables so that there is no longer a conflict.     |
  86 `------------------------------------------------------------------*/
  87
  88 static void
  89 resolve_sr_conflict (int state, int lookaheadnum)
  90 {
  91   int i;
  92   int mask;
  93   unsigned *fp1;
  94   unsigned *fp2;
  95   int redprec;
  96   errs *errp = (errs *) xcalloc (sizeof (errs) + ntokens * sizeof (short), 1);
  97   short *errtokens = errp->errs;
  98
  99   /* find the rule to reduce by to get precedence of reduction  */
 100   redprec = rprec[LAruleno[lookaheadnum]];
 101
 102   mask = 1;
 103   fp1 = LA + lookaheadnum * tokensetsize;
 104   fp2 = lookaheadset;
 105   for (i = 0; i < ntokens; i++)
 106     {
 107       if ((mask & *fp2 & *fp1) && sprec[i])
 108         /* Shift-reduce conflict occurs for token number i
 109            and it has a precedence.
 110            The precedence of shifting is that of token i.  */
 111         {
 112           if (sprec[i] < redprec)
 113             {
 114               log_resolution (state, lookaheadnum, i, _("reduce"));
 115               *fp2 &= ~mask;    /* flush the shift for this token */
 116               flush_shift (state, i);
 117             }
 118           else if (sprec[i] > redprec)
 119             {
 120               log_resolution (state, lookaheadnum, i, _("shift"));
 121               *fp1 &= ~mask;    /* flush the reduce for this token */
 122             }
 123           else
 124             {
 125               /* Matching precedence levels.
 126                  For left association, keep only the reduction.
 127                  For right association, keep only the shift.
 128                  For nonassociation, keep neither.  */
 129
 130               switch (sassoc[i])
 131                 {
 132                 case right_assoc:
 133                   log_resolution (state, lookaheadnum, i, _("shift"));
 134                   break;
 135
 136                 case left_assoc:
 137                   log_resolution (state, lookaheadnum, i, _("reduce"));
 138                   break;
 139
 140                 case non_assoc:
 141                   log_resolution (state, lookaheadnum, i, _("an error"));
 142                   break;
 143                 }
 144
 145               if (sassoc[i] != right_assoc)
 146                 {
 147                   *fp2 &= ~mask;        /* flush the shift for this token */
 148                   flush_shift (state, i);
 149                 }
 150               if (sassoc[i] != left_assoc)
 151                 {
 152                   *fp1 &= ~mask;        /* flush the reduce for this token */
 153                 }
 154               if (sassoc[i] == non_assoc)
 155                 {
 156                   /* Record an explicit error for this token.  */
 157                   *errtokens++ = i;
 158                 }
 159             }
 160         }
 161
 162       mask <<= 1;
 163       if (mask == 0)
 164         {
 165           mask = 1;
 166           fp2++;
 167           fp1++;
 168         }
 169     }
 170   errp->nerrs = errtokens - errp->errs;
 171   if (errp->nerrs)
 172     {
 173       /* Some tokens have been explicitly made errors.  Allocate
 174          a permanent errs structure for this state, to record them.  */
 175       i = (char *) errtokens - (char *) errp;
 176       err_table[state] = (errs *) xcalloc ((unsigned int) i, 1);
 177       bcopy (errp, err_table[state], i);
 178     }
 179   else
 180     err_table[state] = 0;
 181   free (errp);
 182 }
 183
 184
 185 static void
 186 set_conflicts (int state)
 187 {
 188   int i;
 189   int k;
 190   shifts *shiftp;
 191   unsigned *fp2;
 192   unsigned *fp3;
 193   unsigned *fp4;
 194   unsigned *fp1;
 195   int symbol;
 196
 197   if (consistent[state])
 198     return;
 199
 200   for (i = 0; i < tokensetsize; i++)
 201     lookaheadset[i] = 0;
 202
 203   shiftp = shift_table[state];
 204   if (shiftp)
 205     {
 206       k = shiftp->nshifts;
 207       for (i = 0; i < k; i++)
 208         {
 209           symbol = accessing_symbol[shiftp->shifts[i]];
 210           if (ISVAR (symbol))
 211             break;
 212           SETBIT (lookaheadset, symbol);
 213         }
 214     }
 215
 216   k = lookaheads[state + 1];
 217   fp4 = lookaheadset + tokensetsize;
 218
 219   /* Loop over all rules which require lookahead in this state.  First
 220      check for shift-reduce conflict, and try to resolve using
 221      precedence */
 222   for (i = lookaheads[state]; i < k; i++)
 223     if (rprec[LAruleno[i]])
 224       {
 225         fp1 = LA + i * tokensetsize;
 226         fp2 = fp1;
 227         fp3 = lookaheadset;
 228
 229         while (fp3 < fp4)
 230           {
 231             if (*fp2++ & *fp3++)
 232               {
 233                 resolve_sr_conflict (state, i);
 234                 break;
 235               }
 236           }
 237       }
 238
 239
 240   /* Loop over all rules which require lookahead in this state.  Check
 241      for conflicts not resolved above.  */
 242   for (i = lookaheads[state]; i < k; i++)
 243     {
 244       fp1 = LA + i * tokensetsize;
 245       fp2 = fp1;
 246       fp3 = lookaheadset;
 247
 248       while (fp3 < fp4)
 249         {
 250           if (*fp2++ & *fp3++)
 251             {
 252               conflicts[state] = 1;
 253               any_conflicts = 1;
 254             }
 255         }
 256
 257       fp2 = fp1;
 258       fp3 = lookaheadset;
 259
 260       while (fp3 < fp4)
 261         *fp3++ |= *fp2++;
 262     }
 263 }
 264
 265 void
 266 solve_conflicts (void)
 267 {
 268   int i;
 269
 270   conflicts = XCALLOC (char, nstates);
 271   shiftset = XCALLOC (unsigned, tokensetsize);
 272   lookaheadset = XCALLOC (unsigned, tokensetsize);
 273
 274   err_table = XCALLOC (errs *, nstates);
 275
 276   any_conflicts = 0;
 277
 278   for (i = 0; i < nstates; i++)
 279     set_conflicts (i);
 280 }
 281
 282
 283 /*---------------------------------------------.
 284 | Count the number of shift/reduce conflicts.  |
 285 `---------------------------------------------*/
 286
 287 static void
 288 count_sr_conflicts (int state)
 289 {
 290   int i;
 291   int k;
 292   int mask;
 293   shifts *shiftp;
 294   unsigned *fp1;
 295   unsigned *fp2;
 296   unsigned *fp3;
 297   int symbol;
 298
 299   src_count = 0;
 300
 301   shiftp = shift_table[state];
 302   if (!shiftp)
 303     return;
 304
 305   for (i = 0; i < tokensetsize; i++)
 306     {
 307       shiftset[i] = 0;
 308       lookaheadset[i] = 0;
 309     }
 310
 311   k = shiftp->nshifts;
 312   for (i = 0; i < k; i++)
 313     {
 314       if (!shiftp->shifts[i])
 315         continue;
 316       symbol = accessing_symbol[shiftp->shifts[i]];
 317       if (ISVAR (symbol))
 318         break;
 319       SETBIT (shiftset, symbol);
 320     }
 321
 322   k = lookaheads[state + 1];
 323   fp3 = lookaheadset + tokensetsize;
 324
 325   for (i = lookaheads[state]; i < k; i++)
 326     {
 327       fp1 = LA + i * tokensetsize;
 328       fp2 = lookaheadset;
 329
 330       while (fp2 < fp3)
 331         *fp2++ |= *fp1++;
 332     }
 333
 334   fp1 = shiftset;
 335   fp2 = lookaheadset;
 336
 337   while (fp2 < fp3)
 338     *fp2++ &= *fp1++;
 339
 340   mask = 1;
 341   fp2 = lookaheadset;
 342   for (i = 0; i < ntokens; i++)
 343     {
 344       if (mask & *fp2)
 345         src_count++;
 346
 347       mask <<= 1;
 348       if (mask == 0)
 349         {
 350           mask = 1;
 351           fp2++;
 352         }
 353     }
 354 }
 355
 356
 357 /*----------------------------------------------.
 358 | Count the number of reduce/reduce conflicts.  |
 359 `----------------------------------------------*/
 360
 361 static void
 362 count_rr_conflicts (int state)
 363 {
 364   int i;
 365   int j;
 366   int count;
 367   unsigned mask;
 368   unsigned *baseword;
 369   unsigned *wordp;
 370   int m;
 371   int n;
 372
 373   rrc_count = 0;
 374
 375   m = lookaheads[state];
 376   n = lookaheads[state + 1];
 377
 378   if (n - m < 2)
 379     return;
 380
 381   mask = 1;
 382   baseword = LA + m * tokensetsize;
 383   for (i = 0; i < ntokens; i++)
 384     {
 385       wordp = baseword;
 386
 387       count = 0;
 388       for (j = m; j < n; j++)
 389         {
 390           if (mask & *wordp)
 391             count++;
 392
 393           wordp += tokensetsize;
 394         }
 395
 396       if (count >= 2)
 397         rrc_count++;
 398
 399       mask <<= 1;
 400       if (mask == 0)
 401         {
 402           mask = 1;
 403           baseword++;
 404         }
 405     }
 406 }
 407
 408 /*--------------------------------------------------------------.
 409 | Return a human readable string which reports shift/reduce and |
 410 | reduce/reduce conflict numbers (SRC_NUM, RRC_NUM).            |
 411 `--------------------------------------------------------------*/
 412
 413 static const char *
 414 conflict_report (int src_num, int rrc_num)
 415 {
 416   static char res[4096];
 417   char *cp = res;
 418
 419   if (src_num == 1)
 420     {
 421       sprintf (cp, _(" 1 shift/reduce conflict"));
 422       cp += strlen (cp);
 423     }
 424   else if (src_num > 1)
 425     {
 426       sprintf (cp, _(" %d shift/reduce conflicts"), src_num);
 427       cp += strlen (cp);
 428     }
 429
 430   if (src_num > 0 && rrc_num > 0)
 431     {
 432       sprintf (cp, _(" and"));
 433       cp += strlen (cp);
 434     }
 435
 436   if (rrc_num == 1)
 437     {
 438       sprintf (cp, _(" 1 reduce/reduce conflict"));
 439       cp += strlen (cp);
 440     }
 441   else if (rrc_num > 1)
 442     {
 443       sprintf (cp, _(" %d reduce/reduce conflicts"), rrc_num);
 444       cp += strlen (cp);
 445     }
 446
 447   *cp++ = '.';
 448   *cp++ = '\n';
 449   *cp++ = '\0';
 450
 451   return res;
 452 }
 453
 454
 455 /*---------------------------------------------.
 456 | Compute and give a report on the conflicts.  |
 457 `---------------------------------------------*/
 458
 459 void
 460 print_conflicts (FILE *out)
 461 {
 462   int i;
 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 }