src/conflicts.c

   1 /* Find and resolve or report lookahead conflicts for bison,
   2
   3    Copyright (C) 1984, 1989, 1992, 2000, 2001, 2002, 2003, 2004, 2005, 2006,
   4    2007 Free Software Foundation, Inc.
   5
   6    This file is part of Bison, the GNU Compiler Compiler.
   7
   8    This program is free software: you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation, either version 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  20
  21 #include <config.h>
  22 #include "system.h"
  23
  24 #include <bitset.h>
  25
  26 #include "LR0.h"
  27 #include "complain.h"
  28 #include "conflicts.h"
  29 #include "files.h"
  30 #include "getargs.h"
  31 #include "gram.h"
  32 #include "lalr.h"
  33 #include "reader.h"
  34 #include "state.h"
  35 #include "symtab.h"
  36
  37 /* -1 stands for not specified. */
  38 int expected_sr_conflicts = -1;
  39 int expected_rr_conflicts = -1;
  40 static char *conflicts;
  41 static struct obstack solved_conflicts_obstack;
  42
  43 static bitset shift_set;
  44 static bitset lookahead_set;
  45
  46 \f
  47
  48 enum conflict_resolution
  49   {
  50     shift_resolution,
  51     reduce_resolution,
  52     left_resolution,
  53     right_resolution,
  54     nonassoc_resolution
  55   };
  56
  57
  58 /*----------------------------------------------------------------.
  59 | Explain how an SR conflict between TOKEN and RULE was resolved: |
  60 | RESOLUTION.                                                     |
  61 `----------------------------------------------------------------*/
  62
  63 static inline void
  64 log_resolution (rule *r, symbol_number token,
  65                 enum conflict_resolution resolution)
  66 {
  67   if (report_flag & report_solved_conflicts)
  68     {
  69       /* The description of the resolution. */
  70       switch (resolution)
  71         {
  72         case shift_resolution:
  73         case right_resolution:
  74           obstack_fgrow2 (&solved_conflicts_obstack,
  75                           _("\
  76     Conflict between rule %d and token %s resolved as shift"),
  77                           r->number,
  78                           symbols[token]->tag);
  79           break;
  80         case reduce_resolution:
  81         case left_resolution:
  82           obstack_fgrow2 (&solved_conflicts_obstack,
  83                           _("\
  84     Conflict between rule %d and token %s resolved as reduce"),
  85                           r->number,
  86                           symbols[token]->tag);
  87           break;
  88         case nonassoc_resolution:
  89           obstack_fgrow2 (&solved_conflicts_obstack,
  90                           _("\
  91     Conflict between rule %d and token %s resolved as an error"),
  92                           r->number,
  93                           symbols[token]->tag);
  94           break;
  95         }
  96
  97       /* The reason. */
  98       switch (resolution)
  99         {
 100         case shift_resolution:
 101           obstack_fgrow2 (&solved_conflicts_obstack,
 102                           " (%s < %s)",
 103                           r->prec->tag,
 104                           symbols[token]->tag);
 105           break;
 106
 107         case reduce_resolution:
 108           obstack_fgrow2 (&solved_conflicts_obstack,
 109                           " (%s < %s)",
 110                           symbols[token]->tag,
 111                           r->prec->tag);
 112           break;
 113
 114         case left_resolution:
 115           obstack_fgrow1 (&solved_conflicts_obstack,
 116                           " (%%left %s)",
 117                           symbols[token]->tag);
 118           break;
 119
 120         case right_resolution:
 121           obstack_fgrow1 (&solved_conflicts_obstack,
 122                           " (%%right %s)",
 123                           symbols[token]->tag);
 124           break;
 125         case nonassoc_resolution:
 126           obstack_fgrow1 (&solved_conflicts_obstack,
 127                           " (%%nonassoc %s)",
 128                           symbols[token]->tag);
 129           break;
 130         }
 131       obstack_sgrow (&solved_conflicts_obstack, ".\n");
 132     }
 133 }
 134
 135
 136 /*------------------------------------------------------------------.
 137 | Turn off the shift recorded for the specified token in the        |
 138 | specified state.  Used when we resolve a shift-reduce conflict in |
 139 | favor of the reduction or as an error (%nonassoc).                |
 140 `------------------------------------------------------------------*/
 141
 142 static void
 143 flush_shift (state *s, int token)
 144 {
 145   transitions *trans = s->transitions;
 146   int i;
 147
 148   bitset_reset (lookahead_set, token);
 149   for (i = 0; i < trans->num; i++)
 150     if (!TRANSITION_IS_DISABLED (trans, i)
 151         && TRANSITION_SYMBOL (trans, i) == token)
 152       TRANSITION_DISABLE (trans, i);
 153 }
 154
 155
 156 /*--------------------------------------------------------------------.
 157 | Turn off the reduce recorded for the specified token in the         |
 158 | specified lookahead set.  Used when we resolve a shift-reduce       |
 159 | conflict in favor of the shift or as an error (%nonassoc).          |
 160 `--------------------------------------------------------------------*/
 161
 162 static void
 163 flush_reduce (bitset lookahead_tokens, int token)
 164 {
 165   bitset_reset (lookahead_tokens, token);
 166 }
 167
 168
 169 /*------------------------------------------------------------------.
 170 | Attempt to resolve shift-reduce conflict for one rule by means of |
 171 | precedence declarations.  It has already been checked that the    |
 172 | rule has a precedence.  A conflict is resolved by modifying the   |
 173 | shift or reduce tables so that there is no longer a conflict.     |
 174 |                                                                   |
 175 | RULENO is the number of the lookahead bitset to consider.         |
 176 |                                                                   |
 177 | ERRORS and NERRS can be used to store discovered explicit         |
 178 | errors.                                                           |
 179 `------------------------------------------------------------------*/
 180
 181 static void
 182 resolve_sr_conflict (state *s, int ruleno, symbol **errors, int *nerrs)
 183 {
 184   symbol_number i;
 185   reductions *reds = s->reductions;
 186   /* Find the rule to reduce by to get precedence of reduction.  */
 187   rule *redrule = reds->rules[ruleno];
 188   int redprec = redrule->prec->prec;
 189   bitset lookahead_tokens = reds->lookahead_tokens[ruleno];
 190
 191   for (i = 0; i < ntokens; i++)
 192     if (bitset_test (lookahead_tokens, i)
 193         && bitset_test (lookahead_set, i)
 194         && symbols[i]->prec)
 195       {
 196         /* Shift-reduce conflict occurs for token number i
 197            and it has a precedence.
 198            The precedence of shifting is that of token i.  */
 199         if (symbols[i]->prec < redprec)
 200           {
 201             log_resolution (redrule, i, reduce_resolution);
 202             flush_shift (s, i);
 203           }
 204         else if (symbols[i]->prec > redprec)
 205           {
 206             log_resolution (redrule, i, shift_resolution);
 207             flush_reduce (lookahead_tokens, i);
 208           }
 209         else
 210           /* Matching precedence levels.
 211              For left association, keep only the reduction.
 212              For right association, keep only the shift.
 213              For nonassociation, keep neither.  */
 214
 215           switch (symbols[i]->assoc)
 216             {
 217             default:
 218               abort ();
 219
 220             case right_assoc:
 221               log_resolution (redrule, i, right_resolution);
 222               flush_reduce (lookahead_tokens, i);
 223               break;
 224
 225             case left_assoc:
 226               log_resolution (redrule, i, left_resolution);
 227               flush_shift (s, i);
 228               break;
 229
 230             case non_assoc:
 231               log_resolution (redrule, i, nonassoc_resolution);
 232               flush_shift (s, i);
 233               flush_reduce (lookahead_tokens, i);
 234               /* Record an explicit error for this token.  */
 235               errors[(*nerrs)++] = symbols[i];
 236               break;
 237             }
 238       }
 239 }
 240
 241
 242 /*-------------------------------------------------------------------.
 243 | Solve the S/R conflicts of state S using the                       |
 244 | precedence/associativity, and flag it inconsistent if it still has |
 245 | conflicts.  ERRORS can be used as storage to compute the list of   |
 246 | lookahead tokens on which S raises a syntax error (%nonassoc).     |
 247 `-------------------------------------------------------------------*/
 248
 249 static void
 250 set_conflicts (state *s, symbol **errors)
 251 {
 252   int i;
 253   transitions *trans = s->transitions;
 254   reductions *reds = s->reductions;
 255   int nerrs = 0;
 256
 257   if (s->consistent)
 258     return;
 259
 260   bitset_zero (lookahead_set);
 261
 262   FOR_EACH_SHIFT (trans, i)
 263     bitset_set (lookahead_set, TRANSITION_SYMBOL (trans, i));
 264
 265   /* Loop over all rules which require lookahead in this state.  First
 266      check for shift-reduce conflict, and try to resolve using
 267      precedence.  */
 268   for (i = 0; i < reds->num; ++i)
 269     if (reds->rules[i]->prec && reds->rules[i]->prec->prec
 270         && !bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
 271       resolve_sr_conflict (s, i, errors, &nerrs);
 272
 273   if (nerrs)
 274     {
 275       /* Some tokens have been explicitly made errors.  Allocate a
 276          permanent errs structure for this state, to record them.  */
 277       state_errs_set (s, nerrs, errors);
 278     }
 279   if (obstack_object_size (&solved_conflicts_obstack))
 280     {
 281       obstack_1grow (&solved_conflicts_obstack, '\0');
 282       s->solved_conflicts = obstack_finish (&solved_conflicts_obstack);
 283     }
 284
 285   /* Loop over all rules which require lookahead in this state.  Check
 286      for conflicts not resolved above.  */
 287   for (i = 0; i < reds->num; ++i)
 288     {
 289       if (!bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
 290         conflicts[s->number] = 1;
 291       bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
 292     }
 293 }
 294
 295
 296 /*----------------------------------------------------------------.
 297 | Solve all the S/R conflicts using the precedence/associativity, |
 298 | and flag as inconsistent the states that still have conflicts.  |
 299 `----------------------------------------------------------------*/
 300
 301 void
 302 conflicts_solve (void)
 303 {
 304   state_number i;
 305   /* List of lookahead tokens on which we explicitly raise a syntax error.  */
 306   symbol **errors = xnmalloc (ntokens + 1, sizeof *errors);
 307
 308   conflicts = xcalloc (nstates, sizeof *conflicts);
 309   shift_set = bitset_create (ntokens, BITSET_FIXED);
 310   lookahead_set = bitset_create (ntokens, BITSET_FIXED);
 311   obstack_init (&solved_conflicts_obstack);
 312
 313   for (i = 0; i < nstates; i++)
 314     {
 315       set_conflicts (states[i], errors);
 316
 317       /* For uniformity of the code, make sure all the states have a valid
 318          `errs' member.  */
 319       if (!states[i]->errs)
 320         states[i]->errs = errs_new (0, 0);
 321     }
 322
 323   free (errors);
 324 }
 325
 326
 327 void
 328 conflicts_update_state_numbers (state_number old_to_new[],
 329                                 state_number nstates_old)
 330 {
 331   state_number i;
 332   for (i = 0; i < nstates_old; ++i)
 333     if (old_to_new[i] != nstates_old)
 334       conflicts[old_to_new[i]] = conflicts[i];
 335 }
 336
 337
 338 /*---------------------------------------------.
 339 | Count the number of shift/reduce conflicts.  |
 340 `---------------------------------------------*/
 341
 342 static int
 343 count_sr_conflicts (state *s)
 344 {
 345   int i;
 346   int src_count = 0;
 347   transitions *trans = s->transitions;
 348   reductions *reds = s->reductions;
 349
 350   if (!trans)
 351     return 0;
 352
 353   bitset_zero (lookahead_set);
 354   bitset_zero (shift_set);
 355
 356   FOR_EACH_SHIFT (trans, i)
 357     bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));
 358
 359   for (i = 0; i < reds->num; ++i)
 360     bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
 361
 362   bitset_and (lookahead_set, lookahead_set, shift_set);
 363
 364   src_count = bitset_count (lookahead_set);
 365
 366   return src_count;
 367 }
 368
 369
 370 /*----------------------------------------------------------------.
 371 | Count the number of reduce/reduce conflicts.  If ONE_PER_TOKEN, |
 372 | count one conflict for each token that has any reduce/reduce    |
 373 | conflicts.  Otherwise, count one conflict for each pair of      |
 374 | conflicting reductions.                                         |
 375 +`----------------------------------------------------------------*/
 376
 377 static int
 378 count_rr_conflicts (state *s, bool one_per_token)
 379 {
 380   int i;
 381   reductions *reds = s->reductions;
 382   int rrc_count = 0;
 383
 384   for (i = 0; i < ntokens; i++)
 385     {
 386       int count = 0;
 387       int j;
 388       for (j = 0; j < reds->num; ++j)
 389         if (bitset_test (reds->lookahead_tokens[j], i))
 390           count++;
 391
 392       if (count >= 2)
 393         rrc_count += one_per_token ? 1 : count-1;
 394     }
 395
 396   return rrc_count;
 397 }
 398
 399
 400 /*--------------------------------------------------------.
 401 | Report the number of conflicts, using the Yacc format.  |
 402 `--------------------------------------------------------*/
 403
 404 static void
 405 conflict_report (FILE *out, int src_num, int rrc_num)
 406 {
 407   if (src_num && rrc_num)
 408     fprintf (out, _("conflicts: %d shift/reduce, %d reduce/reduce\n"),
 409              src_num, rrc_num);
 410   else if (src_num)
 411     fprintf (out, _("conflicts: %d shift/reduce\n"), src_num);
 412   else if (rrc_num)
 413     fprintf (out, _("conflicts: %d reduce/reduce\n"), rrc_num);
 414 }
 415
 416
 417 /*-----------------------------------------------------------.
 418 | Output the detailed description of states with conflicts.  |
 419 `-----------------------------------------------------------*/
 420
 421 void
 422 conflicts_output (FILE *out)
 423 {
 424   bool printed_sth = false;
 425   state_number i;
 426   for (i = 0; i < nstates; i++)
 427     {
 428       state *s = states[i];
 429       if (conflicts[i])
 430         {
 431           fprintf (out, _("State %d "), i);
 432           conflict_report (out, count_sr_conflicts (s),
 433                            count_rr_conflicts (s, true));
 434           printed_sth = true;
 435         }
 436     }
 437   if (printed_sth)
 438     fputs ("\n\n", out);
 439 }
 440
 441 /*--------------------------------------------------------.
 442 | Total the number of S/R and R/R conflicts.  Unlike the  |
 443 | code in conflicts_output, however, count EACH pair of   |
 444 | reductions for the same state and lookahead as one      |
 445 | conflict.                                               |
 446 `--------------------------------------------------------*/
 447
 448 int
 449 conflicts_total_count (void)
 450 {
 451   state_number i;
 452   int count;
 453
 454   /* Conflicts by state.  */
 455   count = 0;
 456   for (i = 0; i < nstates; i++)
 457     if (conflicts[i])
 458       {
 459         count += count_sr_conflicts (states[i]);
 460         count += count_rr_conflicts (states[i], false);
 461       }
 462   return count;
 463 }
 464
 465
 466 /*------------------------------------------.
 467 | Reporting the total number of conflicts.  |
 468 `------------------------------------------*/
 469
 470 void
 471 conflicts_print (void)
 472 {
 473   /* Is the number of SR conflicts OK?  Either EXPECTED_CONFLICTS is
 474      not set, and then we want 0 SR, or else it is specified, in which
 475      case we want equality.  */
 476   bool src_ok;
 477   bool rrc_ok;
 478
 479   int src_total = 0;
 480   int rrc_total = 0;
 481   int src_expected;
 482   int rrc_expected;
 483
 484   /* Conflicts by state.  */
 485   {
 486     state_number i;
 487
 488     for (i = 0; i < nstates; i++)
 489       if (conflicts[i])
 490         {
 491           src_total += count_sr_conflicts (states[i]);
 492           rrc_total += count_rr_conflicts (states[i], true);
 493         }
 494   }
 495
 496   if (! glr_parser && rrc_total > 0 && expected_rr_conflicts != -1)
 497     {
 498       warn (_("%%expect-rr applies only to GLR parsers"));
 499       expected_rr_conflicts = -1;
 500     }
 501
 502   src_expected = expected_sr_conflicts == -1 ? 0 : expected_sr_conflicts;
 503   rrc_expected = expected_rr_conflicts == -1 ? 0 : expected_rr_conflicts;
 504   src_ok = src_total == src_expected;
 505   rrc_ok = rrc_total == rrc_expected;
 506
 507   /* If there are as many RR conflicts and SR conflicts as
 508      expected, then there is nothing to report.  */
 509   if (rrc_ok & src_ok)
 510     return;
 511
 512   /* Report the total number of conflicts on STDERR.  */
 513   if (src_total | rrc_total)
 514     {
 515       if (! yacc_flag)
 516         fprintf (stderr, "%s: ", current_file);
 517       conflict_report (stderr, src_total, rrc_total);
 518     }
 519
 520   if (expected_sr_conflicts != -1 || expected_rr_conflicts != -1)
 521     {
 522       if (! src_ok)
 523         complain (ngettext ("expected %d shift/reduce conflict",
 524                             "expected %d shift/reduce conflicts",
 525                             src_expected),
 526                   src_expected);
 527       if (! rrc_ok)
 528         complain (ngettext ("expected %d reduce/reduce conflict",
 529                             "expected %d reduce/reduce conflicts",
 530                             rrc_expected),
 531                   rrc_expected);
 532     }
 533 }
 534
 535
 536 void
 537 conflicts_free (void)
 538 {
 539   free (conflicts);
 540   bitset_free (shift_set);
 541   bitset_free (lookahead_set);
 542   obstack_free (&solved_conflicts_obstack, NULL);
 543 }