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