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   int src_total = 0;
 443   int rrc_total = 0;
 444
 445   /* Conflicts by state.  */
 446   for (i = 0; i < nstates; i++)
 447     if (conflicts[i])
 448       {
 449         src_total += count_sr_conflicts (i);
 450         rrc_total += count_rr_conflicts (i);
 451       }
 452
 453   /* Report the total number of conflicts on STDERR.  */
 454   if (src_total || rrc_total)
 455     {
 456       if (yacc_flag)
 457         {
 458           /* If invoked with `--yacc', use the output format specified by
 459              POSIX.  */
 460           fprintf (stderr, _("conflicts: "));
 461           if (src_total > 0)
 462             fprintf (stderr, _(" %d shift/reduce"), src_total);
 463           if (src_total > 0 && rrc_total > 0)
 464             fprintf (stderr, ",");
 465           if (rrc_total > 0)
 466             fprintf (stderr, _(" %d reduce/reduce"), rrc_total);
 467           putc ('\n', stderr);
 468         }
 469       else
 470         {
 471           fprintf (stderr, _("%s contains "), infile);
 472           fputs (conflict_report (src_total, rrc_total), stderr);
 473         }
 474     }
 475
 476   if (expected_conflicts != -1
 477       && src_total != expected_conflicts)
 478     {
 479       complain_message_count++;
 480       fprintf (stderr, ngettext ("expected %d shift/reduce conflict\n",
 481                                  "expected %d shift/reduce conflicts\n",
 482                                  expected_conflicts),
 483                expected_conflicts);
 484     }
 485 }
 486
 487
 488 void
 489 print_reductions (FILE *out, int state)
 490 {
 491   int i;
 492   int j;
 493   int k;
 494   unsigned *fp1;
 495   unsigned *fp2;
 496   unsigned *fp3;
 497   unsigned *fp4;
 498   int rule;
 499   int symbol;
 500   unsigned mask;
 501   int m;
 502   int n;
 503   int default_LA;
 504   int default_rule = 0;
 505   int cmax;
 506   int count;
 507   shifts *shiftp;
 508   errs *errp;
 509   int nodefault = 0;
 510
 511   for (i = 0; i < tokensetsize; i++)
 512     shiftset[i] = 0;
 513
 514   shiftp = state_table[state].shift_table;
 515   if (shiftp)
 516     {
 517       k = shiftp->nshifts;
 518       for (i = 0; i < k; i++)
 519         {
 520           if (!shiftp->shifts[i])
 521             continue;
 522           symbol = state_table[shiftp->shifts[i]].accessing_symbol;
 523           if (ISVAR (symbol))
 524             break;
 525           /* if this state has a shift for the error token,
 526              don't use a default rule.  */
 527           if (symbol == error_token_number)
 528             nodefault = 1;
 529           SETBIT (shiftset, symbol);
 530         }
 531     }
 532
 533   errp = err_table[state];
 534   if (errp)
 535     {
 536       k = errp->nerrs;
 537       for (i = 0; i < k; i++)
 538         {
 539           if (!errp->errs[i])
 540             continue;
 541           symbol = errp->errs[i];
 542           SETBIT (shiftset, symbol);
 543         }
 544     }
 545
 546   m = state_table[state].lookaheads;
 547   n = state_table[state + 1].lookaheads;
 548
 549   if (n - m == 1 && !nodefault)
 550     {
 551       default_rule = LAruleno[m];
 552
 553       fp1 = LA (m);
 554       fp2 = shiftset;
 555       fp3 = lookaheadset;
 556       fp4 = lookaheadset + tokensetsize;
 557
 558       while (fp3 < fp4)
 559         *fp3++ = *fp1++ & *fp2++;
 560
 561       mask = 1;
 562       fp3 = lookaheadset;
 563
 564       for (i = 0; i < ntokens; i++)
 565         {
 566           if (mask & *fp3)
 567             fprintf (out, _("    %-4s\t[reduce using rule %d (%s)]\n"),
 568                      tags[i], default_rule,
 569                      tags[rule_table[default_rule].lhs]);
 570
 571           mask <<= 1;
 572           if (mask == 0)
 573             {
 574               mask = 1;
 575               fp3++;
 576             }
 577         }
 578
 579       fprintf (out, _("    $default\treduce using rule %d (%s)\n\n"),
 580                default_rule, tags[rule_table[default_rule].lhs]);
 581     }
 582   else if (n - m >= 1)
 583     {
 584       cmax = 0;
 585       default_LA = -1;
 586       fp4 = lookaheadset + tokensetsize;
 587
 588       if (!nodefault)
 589         for (i = m; i < n; i++)
 590           {
 591             fp1 = LA (i);
 592             fp2 = shiftset;
 593             fp3 = lookaheadset;
 594
 595             while (fp3 < fp4)
 596               *fp3++ = *fp1++ & (~(*fp2++));
 597
 598             count = 0;
 599             mask = 1;
 600             fp3 = lookaheadset;
 601             for (j = 0; j < ntokens; j++)
 602               {
 603                 if (mask & *fp3)
 604                   count++;
 605
 606                 mask <<= 1;
 607                 if (mask == 0)
 608                   {
 609                     mask = 1;
 610                     fp3++;
 611                   }
 612               }
 613
 614             if (count > cmax)
 615               {
 616                 cmax = count;
 617                 default_LA = i;
 618                 default_rule = LAruleno[i];
 619               }
 620
 621             fp2 = shiftset;
 622             fp3 = lookaheadset;
 623
 624             while (fp3 < fp4)
 625               *fp2++ |= *fp3++;
 626           }
 627
 628       for (i = 0; i < tokensetsize; i++)
 629         shiftset[i] = 0;
 630
 631       if (shiftp)
 632         {
 633           k = shiftp->nshifts;
 634           for (i = 0; i < k; i++)
 635             {
 636               if (!shiftp->shifts[i])
 637                 continue;
 638               symbol = state_table[shiftp->shifts[i]].accessing_symbol;
 639               if (ISVAR (symbol))
 640                 break;
 641               SETBIT (shiftset, symbol);
 642             }
 643         }
 644
 645       mask = 1;
 646       fp1 = LA (m);
 647       fp2 = shiftset;
 648       for (i = 0; i < ntokens; i++)
 649         {
 650           int defaulted = 0;
 651
 652           if (mask & *fp2)
 653             count = 1;
 654           else
 655             count = 0;
 656
 657           fp3 = fp1;
 658           for (j = m; j < n; j++)
 659             {
 660               if (mask & *fp3)
 661                 {
 662                   if (count == 0)
 663                     {
 664                       if (j != default_LA)
 665                         {
 666                           rule = LAruleno[j];
 667                           fprintf (out,
 668                                    _("    %-4s\treduce using rule %d (%s)\n"),
 669                                    tags[i], rule, tags[rule_table[rule].lhs]);
 670                         }
 671                       else
 672                         defaulted = 1;
 673
 674                       count++;
 675                     }
 676                   else
 677                     {
 678                       if (defaulted)
 679                         {
 680                           rule = LAruleno[default_LA];
 681                           fprintf (out,
 682                                    _("    %-4s\treduce using rule %d (%s)\n"),
 683                                    tags[i], rule, tags[rule_table[rule].lhs]);
 684                           defaulted = 0;
 685                         }
 686                       rule = LAruleno[j];
 687                       fprintf (out,
 688                                _("    %-4s\t[reduce using rule %d (%s)]\n"),
 689                                tags[i], rule, tags[rule_table[rule].lhs]);
 690                     }
 691                 }
 692
 693               fp3 += tokensetsize;
 694             }
 695
 696           mask <<= 1;
 697           if (mask == 0)
 698             {
 699               mask = 1;
 700               /* We tried incrementing just fp1, and just fp2; both seem wrong.
 701                  It seems necessary to increment both in sync.  */
 702               fp1++;
 703               fp2++;
 704             }
 705         }
 706
 707       if (default_LA >= 0)
 708         fprintf (out, _("    $default\treduce using rule %d (%s)\n"),
 709                  default_rule, tags[rule_table[default_rule].lhs]);
 710     }
 711 }
 712
 713
 714 void
 715 free_conflicts (void)
 716 {
 717   XFREE (conflicts);
 718   XFREE (shiftset);
 719   XFREE (lookaheadset);
 720 }