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