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