src/conflicts.c

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