src/conflicts.c

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