src/reduce.c

   1 /* Grammar reduction for Bison.
   2
   3    Copyright (C) 1988, 1989, 2000, 2001, 2002, 2003, 2005, 2006, 2007,
   4    2008, 2009, 2010 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
  22 /* Reduce the grammar: Find and eliminate unreachable terminals,
  23    nonterminals, and productions.  David S. Bakin.  */
  24
  25 /* Don't eliminate unreachable terminals: They may be used by the
  26    user's parser.  */
  27
  28 #include <config.h>
  29 #include "system.h"
  30
  31 #include <bitset.h>
  32 #include <quotearg.h>
  33
  34 #include "complain.h"
  35 #include "files.h"
  36 #include "getargs.h"
  37 #include "gram.h"
  38 #include "print-xml.h"
  39 #include "reader.h"
  40 #include "reduce.h"
  41 #include "symtab.h"
  42
  43 /* Set of all nonterminals which are not useless.  */
  44 static bitset N;
  45
  46 /* Set of all rules which have no useless nonterminals in their RHS.  */
  47 static bitset P;
  48
  49 /* Set of all accessible symbols.  */
  50 static bitset V;
  51
  52 /* Set of symbols used to define rule precedence (so they are
  53    `useless', but no warning should be issued).  */
  54 static bitset V1;
  55
  56 static rule_number nuseful_productions;
  57 rule_number nuseless_productions;
  58 static int nuseful_nonterminals;
  59 symbol_number nuseless_nonterminals;
  60 \f
  61 /*-------------------------------------------------------------------.
  62 | Another way to do this would be with a set for each production and |
  63 | then do subset tests against N0, but even for the C grammar the    |
  64 | whole reducing process takes only 2 seconds on my 8Mhz AT.         |
  65 `-------------------------------------------------------------------*/
  66
  67 static bool
  68 useful_production (rule_number r, bitset N0)
  69 {
  70   item_number *rhsp;
  71
  72   /* A production is useful if all of the nonterminals in its appear
  73      in the set of useful nonterminals.  */
  74
  75   for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
  76     if (ISVAR (*rhsp) && !bitset_test (N0, *rhsp - ntokens))
  77       return false;
  78   return true;
  79 }
  80
  81
  82 /*---------------------------------------------------------.
  83 | Remember that rules are 1-origin, symbols are 0-origin.  |
  84 `---------------------------------------------------------*/
  85
  86 static void
  87 useless_nonterminals (void)
  88 {
  89   bitset Np, Ns;
  90   rule_number r;
  91
  92   /* N is set as built.  Np is set being built this iteration. P is
  93      set of all productions which have a RHS all in N.  */
  94
  95   Np = bitset_create (nvars, BITSET_FIXED);
  96
  97
  98   /* The set being computed is a set of nonterminals which can derive
  99      the empty string or strings consisting of all terminals. At each
 100      iteration a nonterminal is added to the set if there is a
 101      production with that nonterminal as its LHS for which all the
 102      nonterminals in its RHS are already in the set.  Iterate until
 103      the set being computed remains unchanged.  Any nonterminals not
 104      in the set at that point are useless in that they will never be
 105      used in deriving a sentence of the language.
 106
 107      This iteration doesn't use any special traversal over the
 108      productions.  A set is kept of all productions for which all the
 109      nonterminals in the RHS are in useful.  Only productions not in
 110      this set are scanned on each iteration.  At the end, this set is
 111      saved to be used when finding useful productions: only
 112      productions in this set will appear in the final grammar.  */
 113
 114   while (1)
 115     {
 116       bitset_copy (Np, N);
 117       for (r = 0; r < nrules; r++)
 118         if (!bitset_test (P, r)
 119             && useful_production (r, N))
 120           {
 121             bitset_set (Np, rules[r].lhs->number - ntokens);
 122             bitset_set (P, r);
 123           }
 124       if (bitset_equal_p (N, Np))
 125         break;
 126       Ns = Np;
 127       Np = N;
 128       N = Ns;
 129     }
 130   bitset_free (N);
 131   N = Np;
 132 }
 133
 134
 135 static void
 136 inaccessable_symbols (void)
 137 {
 138   bitset Vp, Vs, Pp;
 139
 140   /* Find out which productions are reachable and which symbols are
 141      used.  Starting with an empty set of productions and a set of
 142      symbols which only has the start symbol in it, iterate over all
 143      productions until the set of productions remains unchanged for an
 144      iteration.  For each production which has a LHS in the set of
 145      reachable symbols, add the production to the set of reachable
 146      productions, and add all of the nonterminals in the RHS of the
 147      production to the set of reachable symbols.
 148
 149      Consider only the (partially) reduced grammar which has only
 150      nonterminals in N and productions in P.
 151
 152      The result is the set P of productions in the reduced grammar,
 153      and the set V of symbols in the reduced grammar.
 154
 155      Although this algorithm also computes the set of terminals which
 156      are reachable, no terminal will be deleted from the grammar. Some
 157      terminals might not be in the grammar but might be generated by
 158      semantic routines, and so the user might want them available with
 159      specified numbers.  (Is this true?)  However, the nonreachable
 160      terminals are printed (if running in verbose mode) so that the
 161      user can know.  */
 162
 163   Vp = bitset_create (nsyms, BITSET_FIXED);
 164   Pp = bitset_create (nrules, BITSET_FIXED);
 165
 166   /* If the start symbol isn't useful, then nothing will be useful. */
 167   if (bitset_test (N, accept->number - ntokens))
 168     {
 169       bitset_set (V, accept->number);
 170
 171       while (1)
 172         {
 173           rule_number r;
 174           bitset_copy (Vp, V);
 175           for (r = 0; r < nrules; r++)
 176             {
 177               if (!bitset_test (Pp, r)
 178                   && bitset_test (P, r)
 179                   && bitset_test (V, rules[r].lhs->number))
 180                 {
 181                   item_number *rhsp;
 182                   for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
 183                     if (ISTOKEN (*rhsp) || bitset_test (N, *rhsp - ntokens))
 184                       bitset_set (Vp, *rhsp);
 185                   bitset_set (Pp, r);
 186                 }
 187             }
 188           if (bitset_equal_p (V, Vp))
 189             break;
 190           Vs = Vp;
 191           Vp = V;
 192           V = Vs;
 193         }
 194     }
 195
 196   bitset_free (V);
 197   V = Vp;
 198
 199   /* Tokens 0, 1, and 2 are internal to Bison.  Consider them useful. */
 200   bitset_set (V, endtoken->number);             /* end-of-input token */
 201   bitset_set (V, errtoken->number);             /* error token */
 202   bitset_set (V, undeftoken->number);           /* some undefined token */
 203
 204   bitset_free (P);
 205   P = Pp;
 206
 207   nuseful_productions = bitset_count (P);
 208   nuseless_productions = nrules - nuseful_productions;
 209
 210   nuseful_nonterminals = 0;
 211   {
 212     symbol_number i;
 213     for (i = ntokens; i < nsyms; i++)
 214       if (bitset_test (V, i))
 215         nuseful_nonterminals++;
 216   }
 217   nuseless_nonterminals = nvars - nuseful_nonterminals;
 218
 219   /* A token that was used in %prec should not be warned about.  */
 220   {
 221     rule_number r;
 222     for (r = 0; r < nrules; ++r)
 223       if (rules[r].precsym != 0)
 224         bitset_set (V1, rules[r].precsym->number);
 225   }
 226 }
 227
 228
 229 /*-------------------------------------------------------------------.
 230 | Put the useless productions at the end of RULES, and adjust NRULES |
 231 | accordingly.                                                       |
 232 `-------------------------------------------------------------------*/
 233
 234 static void
 235 reduce_grammar_tables (void)
 236 {
 237   /* Report and flag useless productions.  */
 238   {
 239     rule_number r;
 240     for (r = 0; r < nrules; r++)
 241       rules[r].useful = bitset_test (P, r);
 242     grammar_rules_useless_report (_("rule useless in grammar"));
 243   }
 244
 245   /* Map the nonterminals to their new index: useful first, useless
 246      afterwards.  Kept for later report.  */
 247   {
 248     int useful = 0;
 249     int useless = nrules - nuseless_productions;
 250     rule *rules_sorted = xnmalloc (nrules, sizeof *rules_sorted);
 251     rule_number r;
 252     for (r = 0; r < nrules; ++r)
 253       rules_sorted[rules[r].useful ? useful++ : useless++] = rules[r];
 254     free (rules);
 255     rules = rules_sorted;
 256
 257     /* Renumber the rules markers in RITEMS.  */
 258     for (r = 0; r < nrules; ++r)
 259       {
 260         item_number *rhsp = rules[r].rhs;
 261         for (/* Nothing. */; *rhsp >= 0; ++rhsp)
 262           /* Nothing. */;
 263         *rhsp = rule_number_as_item_number (r);
 264         rules[r].number = r;
 265       }
 266     nrules -= nuseless_productions;
 267   }
 268
 269   /* Adjust NRITEMS.  */
 270   {
 271     rule_number r;
 272     int length;
 273     for (r = nrules; r < nrules + nuseless_productions; ++r)
 274       {
 275         length = rule_rhs_length (&rules[r]);
 276         nritems -= length + 1;
 277       }
 278   }
 279 }
 280
 281
 282 /*------------------------------.
 283 | Remove useless nonterminals.  |
 284 `------------------------------*/
 285
 286 static void
 287 nonterminals_reduce (void)
 288 {
 289   symbol_number i, n;
 290
 291   /* Map the nonterminals to their new index: useful first, useless
 292      afterwards.  Kept for later report.  */
 293
 294   symbol_number *nontermmap = xnmalloc (nvars, sizeof *nontermmap);
 295   n = ntokens;
 296   for (i = ntokens; i < nsyms; i++)
 297     if (bitset_test (V, i))
 298       nontermmap[i - ntokens] = n++;
 299   for (i = ntokens; i < nsyms; i++)
 300     if (!bitset_test (V, i))
 301       {
 302         nontermmap[i - ntokens] = n++;
 303         warn_at (symbols[i]->location, _("nonterminal useless in grammar: %s"),
 304                  symbols[i]->tag);
 305       }
 306
 307
 308   /* Shuffle elements of tables indexed by symbol number.  */
 309   {
 310     symbol **symbols_sorted = xnmalloc (nvars, sizeof *symbols_sorted);
 311
 312     for (i = ntokens; i < nsyms; i++)
 313       symbols[i]->number = nontermmap[i - ntokens];
 314     for (i = ntokens; i < nsyms; i++)
 315       symbols_sorted[nontermmap[i - ntokens] - ntokens] = symbols[i];
 316     for (i = ntokens; i < nsyms; i++)
 317       symbols[i] = symbols_sorted[i - ntokens];
 318     free (symbols_sorted);
 319   }
 320
 321   {
 322     rule_number r;
 323     for (r = 0; r < nrules; ++r)
 324       {
 325         item_number *rhsp;
 326         for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
 327           if (ISVAR (*rhsp))
 328             *rhsp =  symbol_number_as_item_number (nontermmap[*rhsp
 329                                                               - ntokens]);
 330       }
 331     accept->number = nontermmap[accept->number - ntokens];
 332   }
 333
 334   nsyms -= nuseless_nonterminals;
 335   nvars -= nuseless_nonterminals;
 336
 337   free (nontermmap);
 338 }
 339
 340
 341 /*------------------------------------------------------------------.
 342 | Output the detailed results of the reductions.  For FILE.output.  |
 343 `------------------------------------------------------------------*/
 344
 345 void
 346 reduce_output (FILE *out)
 347 {
 348   if (nuseless_nonterminals > 0)
 349     {
 350       int i;
 351       fprintf (out, "%s\n\n", _("Nonterminals useless in grammar"));
 352       for (i = 0; i < nuseless_nonterminals; ++i)
 353         fprintf (out, "   %s\n", symbols[nsyms + i]->tag);
 354       fputs ("\n\n", out);
 355     }
 356
 357   {
 358     bool b = false;
 359     int i;
 360     for (i = 0; i < ntokens; i++)
 361       if (reduce_token_unused_in_grammar (i))
 362         {
 363           if (!b)
 364             fprintf (out, "%s\n\n", _("Terminals unused in grammar"));
 365           b = true;
 366           fprintf (out, "   %s\n", symbols[i]->tag);
 367         }
 368     if (b)
 369       fputs ("\n\n", out);
 370   }
 371
 372   if (nuseless_productions > 0)
 373     grammar_rules_partial_print (out, _("Rules useless in grammar"),
 374                                  rule_useless_in_grammar_p);
 375 }
 376 \f
 377
 378 /*-------------------------------.
 379 | Report the results to STDERR.  |
 380 `-------------------------------*/
 381
 382 static void
 383 reduce_print (void)
 384 {
 385   if (nuseless_nonterminals > 0)
 386     {
 387       fprintf (stderr, "%s: %s: ", grammar_file, _("warning"));
 388       fprintf (stderr, ngettext ("%d nonterminal useless in grammar",
 389                                  "%d nonterminals useless in grammar",
 390                                  nuseless_nonterminals),
 391                nuseless_nonterminals);
 392       fprintf (stderr, "\n");
 393     }
 394   if (nuseless_productions > 0)
 395     {
 396       fprintf (stderr, "%s: %s: ", grammar_file, _("warning"));
 397       fprintf (stderr, ngettext ("%d rule useless in grammar",
 398                                  "%d rules useless in grammar",
 399                                  nuseless_productions),
 400                nuseless_productions);
 401       fprintf (stderr, "\n");
 402     }
 403 }
 404 \f
 405 void
 406 reduce_grammar (void)
 407 {
 408   bool reduced;
 409
 410   /* Allocate the global sets used to compute the reduced grammar */
 411
 412   N = bitset_create (nvars, BITSET_FIXED);
 413   P =  bitset_create (nrules, BITSET_FIXED);
 414   V = bitset_create (nsyms, BITSET_FIXED);
 415   V1 = bitset_create (nsyms, BITSET_FIXED);
 416
 417   useless_nonterminals ();
 418   inaccessable_symbols ();
 419
 420   reduced = (nuseless_nonterminals + nuseless_productions > 0);
 421   if (!reduced)
 422     return;
 423
 424   reduce_print ();
 425
 426   if (!bitset_test (N, accept->number - ntokens))
 427     fatal_at (startsymbol_location,
 428               _("start symbol %s does not derive any sentence"),
 429               startsymbol->tag);
 430
 431   /* First reduce the nonterminals, as they renumber themselves in the
 432      whole grammar.  If you change the order, nonterms would be
 433      renumbered only in the reduced grammar.  */
 434   if (nuseless_nonterminals > 0)
 435     nonterminals_reduce ();
 436   if (nuseless_productions > 0)
 437     reduce_grammar_tables ();
 438
 439   if (trace_flag & trace_grammar)
 440     {
 441       grammar_dump (stderr, "Reduced Grammar");
 442
 443       fprintf (stderr, "reduced %s defines %d terminals, %d nonterminals\
 444 , and %d productions.\n",
 445                grammar_file, ntokens, nvars, nrules);
 446     }
 447 }
 448
 449 bool
 450 reduce_token_unused_in_grammar (symbol_number i)
 451 {
 452   aver (i < ntokens);
 453   return !bitset_test (V, i) && !bitset_test (V1, i);
 454 }
 455
 456 bool
 457 reduce_nonterminal_useless_in_grammar (symbol_number i)
 458 {
 459   aver (ntokens <= i && i < nsyms + nuseless_nonterminals);
 460   return nsyms <= i;
 461 }
 462
 463 /*-----------------------------------------------------------.
 464 | Free the global sets used to compute the reduced grammar.  |
 465 `-----------------------------------------------------------*/
 466
 467 void
 468 reduce_free (void)
 469 {
 470   bitset_free (N);
 471   bitset_free (V);
 472   bitset_free (V1);
 473   bitset_free (P);
 474 }