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