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