src/conflicts.c

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