src/conflicts.c

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