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