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 = state_table[state].shift_table;
  61   int i;
  62
  63   if (shiftp)
  64     for (i = 0; i < shiftp->nshifts; i++)
  65       if (shiftp->shifts[i] && SHIFT_SYMBOL (shiftp, i) == token)
  66         shiftp->shifts[i] = 0;
  67 }
  68
  69
  70 /*------------------------------------------------------------------.
  71 | Attempt to resolve shift-reduce conflict for one rule by means of |
  72 | precedence declarations.  It has already been checked that the    |
  73 | rule has a precedence.  A conflict is resolved by modifying the   |
  74 | shift or reduce tables so that there is no longer a conflict.     |
  75 `------------------------------------------------------------------*/
  76
  77 static void
  78 resolve_sr_conflict (int state, int lookaheadnum)
  79 {
  80   int i;
  81   /* find the rule to reduce by to get precedence of reduction  */
  82   int redprec = rule_table[LAruleno[lookaheadnum]].prec;
  83   errs *errp = ERRS_ALLOC (ntokens + 1);
  84   short *errtokens = errp->errs;
  85
  86   for (i = 0; i < ntokens; i++)
  87     {
  88       if (BITISSET (LA (lookaheadnum), i)
  89           && BITISSET (lookaheadset, i)
  90           && sprec[i])
  91         /* Shift-reduce conflict occurs for token number i
  92            and it has a precedence.
  93            The precedence of shifting is that of token i.  */
  94         {
  95           if (sprec[i] < redprec)
  96             {
  97               log_resolution (state, lookaheadnum, i, _("reduce"));
  98               /* flush the shift for this token */
  99               RESETBIT (lookaheadset, i);
 100               flush_shift (state, i);
 101             }
 102           else if (sprec[i] > redprec)
 103             {
 104               log_resolution (state, lookaheadnum, i, _("shift"));
 105               /* flush the reduce for this token */
 106               RESETBIT (LA (lookaheadnum), i);
 107             }
 108           else
 109             {
 110               /* Matching precedence levels.
 111                  For left association, keep only the reduction.
 112                  For right association, keep only the shift.
 113                  For nonassociation, keep neither.  */
 114
 115               switch (sassoc[i])
 116                 {
 117                 case right_assoc:
 118                   log_resolution (state, lookaheadnum, i, _("shift"));
 119                   break;
 120
 121                 case left_assoc:
 122                   log_resolution (state, lookaheadnum, i, _("reduce"));
 123                   break;
 124
 125                 case non_assoc:
 126                   log_resolution (state, lookaheadnum, i, _("an error"));
 127                   break;
 128                 }
 129
 130               if (sassoc[i] != right_assoc)
 131                 {
 132                   /* flush the shift for this token */
 133                   RESETBIT (lookaheadset, i);
 134                   flush_shift (state, i);
 135                 }
 136               if (sassoc[i] != left_assoc)
 137                 {
 138                   /* flush the reduce for this token */
 139                   RESETBIT (LA (lookaheadnum), i);
 140                 }
 141               if (sassoc[i] == non_assoc)
 142                 {
 143                   /* Record an explicit error for this token.  */
 144                   *errtokens++ = i;
 145                 }
 146             }
 147         }
 148     }
 149   errp->nerrs = errtokens - errp->errs;
 150   if (errp->nerrs)
 151     {
 152       /* Some tokens have been explicitly made errors.  Allocate
 153          a permanent errs structure for this state, to record them.  */
 154       i = (char *) errtokens - (char *) errp;
 155       err_table[state] = ERRS_ALLOC (i + 1);
 156       bcopy (errp, err_table[state], i);
 157     }
 158   else
 159     err_table[state] = 0;
 160   free (errp);
 161 }
 162
 163
 164 static void
 165 set_conflicts (int state)
 166 {
 167   int i, j;
 168   shifts *shiftp;
 169
 170   if (state_table[state].consistent)
 171     return;
 172
 173   for (i = 0; i < tokensetsize; i++)
 174     lookaheadset[i] = 0;
 175
 176   shiftp = state_table[state].shift_table;
 177   if (shiftp)
 178     for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 179       SETBIT (lookaheadset, SHIFT_SYMBOL (shiftp, i));
 180
 181   /* Loop over all rules which require lookahead in this state.  First
 182      check for shift-reduce conflict, and try to resolve using
 183      precedence */
 184   for (i = state_table[state].lookaheads;
 185        i < state_table[state + 1].lookaheads;
 186        ++i)
 187     if (rule_table[LAruleno[i]].prec)
 188       for (j = 0; j < tokensetsize; ++j)
 189         if (LA (i)[j] & lookaheadset[j])
 190           {
 191             resolve_sr_conflict (state, i);
 192             break;
 193           }
 194
 195
 196   /* Loop over all rules which require lookahead in this state.  Check
 197      for conflicts not resolved above.  */
 198   for (i = state_table[state].lookaheads;
 199        i < state_table[state + 1].lookaheads;
 200        ++i)
 201     {
 202       for (j = 0; j < tokensetsize; ++j)
 203         if (LA (i)[j] & lookaheadset[j])
 204           conflicts[state] = 1;
 205
 206       for (j = 0; j < tokensetsize; ++j)
 207         lookaheadset[j] |= LA (i)[j];
 208     }
 209 }
 210
 211 void
 212 solve_conflicts (void)
 213 {
 214   int i;
 215
 216   conflicts = XCALLOC (char, nstates);
 217   shiftset = XCALLOC (unsigned, tokensetsize);
 218   lookaheadset = XCALLOC (unsigned, tokensetsize);
 219
 220   err_table = XCALLOC (errs *, nstates);
 221
 222   for (i = 0; i < nstates; i++)
 223     set_conflicts (i);
 224 }
 225
 226
 227 /*---------------------------------------------.
 228 | Count the number of shift/reduce conflicts.  |
 229 `---------------------------------------------*/
 230
 231 static int
 232 count_sr_conflicts (int state)
 233 {
 234   int i, k;
 235   int src_count = 0;
 236   shifts *shiftp = state_table[state].shift_table;
 237
 238   if (!shiftp)
 239     return 0;
 240
 241   for (i = 0; i < tokensetsize; i++)
 242     {
 243       shiftset[i] = 0;
 244       lookaheadset[i] = 0;
 245     }
 246
 247   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 248     SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i));
 249
 250   for (i = state_table[state].lookaheads;
 251        i < state_table[state + 1].lookaheads;
 252        ++i)
 253     for (k = 0; k < tokensetsize; ++k)
 254       lookaheadset[k] |= LA (i)[k];
 255
 256   for (k = 0; k < tokensetsize; ++k)
 257     lookaheadset[k] &= shiftset[k];
 258
 259   for (i = 0; i < ntokens; i++)
 260     if (BITISSET (lookaheadset, i))
 261       src_count++;
 262
 263   return src_count;
 264 }
 265
 266
 267 /*----------------------------------------------.
 268 | Count the number of reduce/reduce conflicts.  |
 269 `----------------------------------------------*/
 270
 271 static int
 272 count_rr_conflicts (int state)
 273 {
 274   int i;
 275   int rrc_count = 0;
 276
 277   int m = state_table[state].lookaheads;
 278   int n = state_table[state + 1].lookaheads;
 279
 280   if (n - m < 2)
 281     return 0;
 282
 283   for (i = 0; i < ntokens; i++)
 284     {
 285       int count = 0;
 286       int j;
 287       for (j = m; j < n; j++)
 288         if (BITISSET (LA (m), j))
 289           count++;
 290
 291       if (count >= 2)
 292         rrc_count++;
 293     }
 294
 295   return rrc_count;
 296 }
 297
 298 /*--------------------------------------------------------------.
 299 | Return a human readable string which reports shift/reduce and |
 300 | reduce/reduce conflict numbers (SRC_NUM, RRC_NUM).            |
 301 `--------------------------------------------------------------*/
 302
 303 static const char *
 304 conflict_report (int src_num, int rrc_num)
 305 {
 306   static char res[4096];
 307   char *cp = res;
 308
 309   if (src_num >= 1)
 310     {
 311       sprintf (cp, ngettext ("%d shift/reduce conflict",
 312                              "%d shift/reduce conflicts", src_num), src_num);
 313       cp += strlen (cp);
 314     }
 315
 316   if (src_num > 0 && rrc_num > 0)
 317     {
 318       sprintf (cp, " %s ", _("and"));
 319       cp += strlen (cp);
 320     }
 321
 322   if (rrc_num >= 1)
 323     {
 324       sprintf (cp, ngettext ("%d reduce/reduce conflict",
 325                              "%d reduce/reduce conflicts", rrc_num), rrc_num);
 326       cp += strlen (cp);
 327     }
 328
 329   *cp++ = '.';
 330   *cp++ = '\n';
 331   *cp++ = '\0';
 332
 333   return res;
 334 }
 335
 336
 337 /*-----------------------------------------------------------.
 338 | Output the detailed description of states with conflicts.  |
 339 `-----------------------------------------------------------*/
 340
 341 void
 342 conflicts_output (FILE *out)
 343 {
 344   bool printed_sth = FALSE;
 345   int i;
 346   for (i = 0; i < nstates; i++)
 347     if (conflicts[i])
 348       {
 349         fprintf (out, _("State %d contains "), i);
 350         fputs (conflict_report (count_sr_conflicts (i),
 351                                 count_rr_conflicts (i)), out);
 352         printed_sth = TRUE;
 353       }
 354   if (printed_sth)
 355     fputs ("\n\n", out);
 356 }
 357
 358
 359 /*------------------------------------------.
 360 | Reporting the total number of conflicts.  |
 361 `------------------------------------------*/
 362
 363 void
 364 conflicts_print (void)
 365 {
 366   int i;
 367
 368   /* Is the number of SR conflicts OK?  Either EXPECTED_CONFLICTS is
 369      not set, and then we want 0 SR, or else it is specified, in which
 370      case we want equality.  */
 371   int src_ok = 0;
 372
 373   int src_total = 0;
 374   int rrc_total = 0;
 375
 376   /* Conflicts by state.  */
 377   for (i = 0; i < nstates; i++)
 378     if (conflicts[i])
 379       {
 380         src_total += count_sr_conflicts (i);
 381         rrc_total += count_rr_conflicts (i);
 382       }
 383
 384   src_ok = src_total == (expected_conflicts == -1 ? 0 : expected_conflicts);
 385
 386   /* If there are no RR conflicts, and as many SR conflicts as
 387      expected, then there is nothing to report.  */
 388   if (!rrc_total && src_ok)
 389     return;
 390
 391   /* Report the total number of conflicts on STDERR.  */
 392   if (yacc_flag)
 393     {
 394       /* If invoked with `--yacc', use the output format specified by
 395          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       fputs (conflict_report (src_total, rrc_total), stderr);
 409     }
 410
 411   if (expected_conflicts != -1 && !src_ok)
 412     {
 413       complain_message_count++;
 414       fprintf (stderr, ngettext ("expected %d shift/reduce conflict\n",
 415                                  "expected %d shift/reduce conflicts\n",
 416                                  expected_conflicts),
 417                expected_conflicts);
 418     }
 419 }
 420
 421
 422 void
 423 print_reductions (FILE *out, int state)
 424 {
 425   int i;
 426   int j;
 427   int m;
 428   int n;
 429   shifts *shiftp;
 430   errs *errp;
 431   int nodefault = 0;
 432
 433   for (i = 0; i < tokensetsize; i++)
 434     shiftset[i] = 0;
 435
 436   shiftp = state_table[state].shift_table;
 437   if (shiftp)
 438     for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 439       {
 440         /* if this state has a shift for the error token, don't use a
 441            default rule.  */
 442         if (SHIFT_IS_ERROR (shiftp, i))
 443           nodefault = 1;
 444         SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i));
 445       }
 446
 447   errp = err_table[state];
 448   if (errp)
 449     for (i = 0; i < errp->nerrs; i++)
 450       if (errp->errs[i])
 451         SETBIT (shiftset, errp->errs[i]);
 452
 453   m = state_table[state].lookaheads;
 454   n = state_table[state + 1].lookaheads;
 455
 456   if (n - m == 1 && !nodefault)
 457     {
 458       int k;
 459       int default_rule = LAruleno[m];
 460
 461       for (k = 0; k < tokensetsize; ++k)
 462         lookaheadset[k] = LA (m)[k] & shiftset[k];
 463
 464       for (i = 0; i < ntokens; i++)
 465         if (BITISSET (lookaheadset, i))
 466           fprintf (out, _("    %-4s\t[reduce using rule %d (%s)]\n"),
 467                    tags[i], default_rule,
 468                    tags[rule_table[default_rule].lhs]);
 469
 470       fprintf (out, _("    $default\treduce using rule %d (%s)\n\n"),
 471                default_rule, tags[rule_table[default_rule].lhs]);
 472     }
 473   else if (n - m >= 1)
 474     {
 475       int k;
 476
 477       int cmax = 0;
 478       int default_LA = -1;
 479       int default_rule = 0;
 480
 481       if (!nodefault)
 482         for (i = m; i < n; i++)
 483           {
 484             int count = 0;
 485
 486             for (k = 0; k < tokensetsize; ++k)
 487               lookaheadset[k] = LA (i)[k] & ~shiftset[k];
 488
 489             for (j = 0; j < ntokens; j++)
 490               if (BITISSET (lookaheadset, j))
 491                 count++;
 492
 493             if (count > cmax)
 494               {
 495                 cmax = count;
 496                 default_LA = i;
 497                 default_rule = LAruleno[i];
 498               }
 499
 500             for (k = 0; k < tokensetsize; ++k)
 501               shiftset[k] |= lookaheadset[k];
 502           }
 503
 504       for (i = 0; i < tokensetsize; i++)
 505         shiftset[i] = 0;
 506
 507       if (shiftp)
 508         for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
 509           SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i));
 510
 511       for (i = 0; i < ntokens; i++)
 512         {
 513           int defaulted = 0;
 514           int count = BITISSET (shiftset, i);
 515
 516           for (j = m; j < n; j++)
 517             {
 518               if (BITISSET (LA (m), j))
 519                 {
 520                   if (count == 0)
 521                     {
 522                       if (j != default_LA)
 523                         fprintf (out,
 524                                  _("    %-4s\treduce using rule %d (%s)\n"),
 525                                  tags[i],
 526                                  LAruleno[j],
 527                                  tags[rule_table[LAruleno[j]].lhs]);
 528                       else
 529                         defaulted = 1;
 530
 531                       count++;
 532                     }
 533                   else
 534                     {
 535                       if (defaulted)
 536                         fprintf (out,
 537                                  _("    %-4s\treduce using rule %d (%s)\n"),
 538                                  tags[i],
 539                                  LAruleno[default_LA],
 540                                  tags[rule_table[LAruleno[default_LA]].lhs]);
 541                       defaulted = 0;
 542                       fprintf (out,
 543                                _("    %-4s\t[reduce using rule %d (%s)]\n"),
 544                                tags[i],
 545                                LAruleno[j],
 546                                tags[rule_table[LAruleno[j]].lhs]);
 547                     }
 548                 }
 549             }
 550         }
 551
 552       if (default_LA >= 0)
 553         fprintf (out, _("    $default\treduce using rule %d (%s)\n"),
 554                  default_rule, tags[rule_table[default_rule].lhs]);
 555     }
 556 }
 557
 558
 559 void
 560 free_conflicts (void)
 561 {
 562   XFREE (conflicts);
 563   XFREE (shiftset);
 564   XFREE (lookaheadset);
 565 }