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