src/reduce.c

   1 /* Grammar reduction for Bison.
   2    Copyright 1988, 1989, 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
   7    it 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,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU 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
  18    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  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 "system.h"
  29 #include "getargs.h"
  30 #include "files.h"
  31 #include "symtab.h"
  32 #include "gram.h"
  33 #include "complain.h"
  34 #include "reduce.h"
  35 #include "reader.h"
  36 #include "getargs.h"
  37
  38 typedef unsigned *BSet;
  39 typedef short *rule;
  40
  41
  42 /* Set of all nonterminals which are not useless.  */
  43 static BSet N;
  44
  45 /* Set of all rules which have no useless nonterminals in their RHS.  */
  46 static BSet P;
  47
  48 /* Set of all accessible symbols.  */
  49 static BSet V;
  50
  51 /* Set of symbols used to define rule precedence (so they are
  52    `useless', but no warning should be issued).  */
  53 static BSet V1;
  54
  55 static int nuseful_productions;
  56 static int nuseless_productions;
  57 static int nuseful_nonterminals;
  58 int nuseless_nonterminals;
  59 \f
  60 static bool
  61 bits_equal (BSet L, BSet R, int n)
  62 {
  63   int i;
  64
  65   for (i = n - 1; i >= 0; i--)
  66     if (L[i] != R[i])
  67       return FALSE;
  68   return TRUE;
  69 }
  70
  71
  72 static int
  73 nbits (unsigned i)
  74 {
  75   int count = 0;
  76
  77   while (i != 0)
  78     {
  79       i ^= (i & ((unsigned) (-(int) i)));
  80       ++count;
  81     }
  82   return count;
  83 }
  84
  85
  86 static int
  87 bits_size (BSet S, int n)
  88 {
  89   int i, count = 0;
  90
  91   for (i = n - 1; i >= 0; i--)
  92     count += nbits (S[i]);
  93   return count;
  94 }
  95 \f
  96 /*-------------------------------------------------------------------.
  97 | Another way to do this would be with a set for each production and |
  98 | then do subset tests against N0, but even for the C grammar the    |
  99 | whole reducing process takes only 2 seconds on my 8Mhz AT.         |
 100 `-------------------------------------------------------------------*/
 101
 102 static bool
 103 useful_production (int i, BSet N0)
 104 {
 105   rule r;
 106   short n;
 107
 108   /* A production is useful if all of the nonterminals in its appear
 109      in the set of useful nonterminals.  */
 110
 111   for (r = &ritem[rule_table[i].rhs]; *r >= 0; r++)
 112     if (ISVAR (n = *r))
 113       if (!BITISSET (N0, n - ntokens))
 114         return FALSE;
 115   return TRUE;
 116 }
 117
 118
 119 /*---------------------------------------------------------.
 120 | Remember that rules are 1-origin, symbols are 0-origin.  |
 121 `---------------------------------------------------------*/
 122
 123 static void
 124 useless_nonterminals (void)
 125 {
 126   BSet Np, Ns;
 127   int i;
 128
 129   /* N is set as built.  Np is set being built this iteration. P is
 130      set of all productions which have a RHS all in N.  */
 131
 132   Np = XCALLOC (unsigned, WORDSIZE (nvars));
 133
 134   /* The set being computed is a set of nonterminals which can derive
 135      the empty string or strings consisting of all terminals. At each
 136      iteration a nonterminal is added to the set if there is a
 137      production with that nonterminal as its LHS for which all the
 138      nonterminals in its RHS are already in the set.  Iterate until
 139      the set being computed remains unchanged.  Any nonterminals not
 140      in the set at that point are useless in that they will never be
 141      used in deriving a sentence of the language.
 142
 143      This iteration doesn't use any special traversal over the
 144      productions.  A set is kept of all productions for which all the
 145      nonterminals in the RHS are in useful.  Only productions not in
 146      this set are scanned on each iteration.  At the end, this set is
 147      saved to be used when finding useful productions: only
 148      productions in this set will appear in the final grammar.  */
 149
 150   while (1)
 151     {
 152       for (i = WORDSIZE (nvars) - 1; i >= 0; i--)
 153         Np[i] = N[i];
 154       for (i = 1; i <= nrules; i++)
 155         {
 156           if (!BITISSET (P, i))
 157             {
 158               if (useful_production (i, N))
 159                 {
 160                   SETBIT (Np, rule_table[i].lhs - ntokens);
 161                   SETBIT (P, i);
 162                 }
 163             }
 164         }
 165       if (bits_equal (N, Np, WORDSIZE (nvars)))
 166         break;
 167       Ns = Np;
 168       Np = N;
 169       N = Ns;
 170     }
 171   XFREE (N);
 172   N = Np;
 173 }
 174
 175
 176 static void
 177 inaccessable_symbols (void)
 178 {
 179   BSet Vp, Vs, Pp;
 180   int i;
 181   short t;
 182   rule r;
 183
 184   /* Find out which productions are reachable and which symbols are
 185      used.  Starting with an empty set of productions and a set of
 186      symbols which only has the start symbol in it, iterate over all
 187      productions until the set of productions remains unchanged for an
 188      iteration.  For each production which has a LHS in the set of
 189      reachable symbols, add the production to the set of reachable
 190      productions, and add all of the nonterminals in the RHS of the
 191      production to the set of reachable symbols.
 192
 193      Consider only the (partially) reduced grammar which has only
 194      nonterminals in N and productions in P.
 195
 196      The result is the set P of productions in the reduced grammar,
 197      and the set V of symbols in the reduced grammar.
 198
 199      Although this algorithm also computes the set of terminals which
 200      are reachable, no terminal will be deleted from the grammar. Some
 201      terminals might not be in the grammar but might be generated by
 202      semantic routines, and so the user might want them available with
 203      specified numbers.  (Is this true?)  However, the nonreachable
 204      terminals are printed (if running in verbose mode) so that the
 205      user can know.  */
 206
 207   Vp = XCALLOC (unsigned, WORDSIZE (nsyms));
 208   Pp = XCALLOC (unsigned, WORDSIZE (nrules + 1));
 209
 210   /* If the start symbol isn't useful, then nothing will be useful. */
 211   if (BITISSET (N, start_symbol - ntokens))
 212     {
 213       SETBIT (V, start_symbol);
 214
 215       while (1)
 216         {
 217           for (i = WORDSIZE (nsyms) - 1; i >= 0; i--)
 218             Vp[i] = V[i];
 219           for (i = 1; i <= nrules; i++)
 220             {
 221               if (!BITISSET (Pp, i)
 222                   && BITISSET (P, i)
 223                   && BITISSET (V, rule_table[i].lhs))
 224                 {
 225                   for (r = &ritem[rule_table[i].rhs]; *r >= 0; r++)
 226                     if (ISTOKEN (t = *r) || BITISSET (N, t - ntokens))
 227                       SETBIT (Vp, t);
 228                   SETBIT (Pp, i);
 229                 }
 230             }
 231           if (bits_equal (V, Vp, WORDSIZE (nsyms)))
 232             break;
 233           Vs = Vp;
 234           Vp = V;
 235           V = Vs;
 236         }
 237     }
 238
 239   XFREE (V);
 240   V = Vp;
 241
 242   /* Tokens 0, 1, and 2 are internal to Bison.  Consider them useful. */
 243   SETBIT (V, 0);                /* end-of-input token */
 244   SETBIT (V, 1);                /* error token */
 245   SETBIT (V, 2);                /* some undefined token */
 246
 247   XFREE (P);
 248   P = Pp;
 249
 250   nuseful_productions = bits_size (P, WORDSIZE (nrules + 1));
 251   nuseless_productions = nrules - nuseful_productions;
 252
 253   nuseful_nonterminals = 0;
 254   for (i = ntokens; i < nsyms; i++)
 255     if (BITISSET (V, i))
 256       nuseful_nonterminals++;
 257   nuseless_nonterminals = nvars - nuseful_nonterminals;
 258
 259   /* A token that was used in %prec should not be warned about.  */
 260   for (i = 1; i < nrules; i++)
 261     if (rule_table[i].precsym != 0)
 262       SETBIT (V1, rule_table[i].precsym);
 263 }
 264
 265 static void
 266 reduce_grammar_tables (void)
 267 {
 268   /* This is turned off because we would need to change the numbers in
 269      the case statements in the actions file.
 270
 271      We don't disable it via CPP so that it is still checked with the
 272      rest of the code, to avoid its becoming completely obsolete.
 273
 274      FIXME: I think the comment above demonstrates this code must be
 275      turned off for *semantic* parser, not in the general case.  Try
 276      to understand this better --akim.  */
 277
 278   if (0)
 279     /* remove useless productions */
 280     if (nuseless_productions > 0)
 281       {
 282         short np, pn, ni, pi;
 283
 284         np = 0;
 285         ni = 0;
 286         for (pn = 1; pn <= nrules; pn++)
 287           if (BITISSET (P, pn))
 288             {
 289               np++;
 290               if (pn != np)
 291                 {
 292                   rule_table[np].lhs   = rule_table[pn].lhs;
 293                   rule_table[np].line  = rule_table[pn].line;
 294                   rule_table[np].prec  = rule_table[pn].prec;
 295                   rule_table[np].assoc = rule_table[pn].assoc;
 296                   rule_table[np].rhs   = rule_table[pn].rhs;
 297                   if (rule_table[np].rhs != ni)
 298                     {
 299                       pi = rule_table[np].rhs;
 300                       rule_table[np].rhs = ni;
 301                       while (ritem[pi] >= 0)
 302                         ritem[ni++] = ritem[pi++];
 303                       ritem[ni++] = -np;
 304                     }
 305                 }
 306               else
 307                 {
 308                   while (ritem[ni++] >= 0)
 309                     /* Nothing. */;
 310                 }
 311             }
 312
 313         ritem[ni] = 0;
 314         nrules -= nuseless_productions;
 315         nitems = ni;
 316         nritems = ni;
 317
 318         /* Is it worth it to reduce the amount of memory for the
 319            grammar? Probably not.  */
 320       }
 321
 322   /* Disable useless productions. */
 323   if (nuseless_productions > 0)
 324     {
 325       int pn;
 326       for (pn = 1; pn <= nrules; pn++)
 327         rule_table[pn].useful = BITISSET (P, pn);
 328     }
 329 }
 330
 331
 332 /*------------------------------.
 333 | Remove useless nonterminals.  |
 334 `------------------------------*/
 335
 336 static void
 337 nonterminals_reduce (void)
 338 {
 339   int i, n;
 340   rule r;
 341
 342   /* Map the nonterminals to their new index: useful first, useless
 343      afterwards.  Kept for later report.  */
 344
 345   short *nontermmap = XCALLOC (short, nvars) - ntokens;
 346   n = ntokens;
 347   for (i = ntokens; i < nsyms; i++)
 348     if (BITISSET (V, i))
 349       nontermmap[i] = n++;
 350   for (i = ntokens; i < nsyms; i++)
 351     if (!BITISSET (V, i))
 352       nontermmap[i] = n++;
 353
 354
 355   /* Shuffle elements of tables indexed by symbol number.  */
 356   {
 357     bucket **symbols_sorted = XMALLOC (bucket *, nvars) - ntokens;
 358
 359     for (i = ntokens; i < nsyms; i++)
 360       symbols_sorted[nontermmap[i]] = symbols[i];
 361     for (i = ntokens; i < nsyms; i++)
 362       symbols[i] = symbols_sorted[i];
 363     free (symbols_sorted + ntokens);
 364   }
 365
 366   /* Replace all symbol numbers in valid data structures.  */
 367
 368   for (i = 1; i <= nrules; i++)
 369     {
 370       rule_table[i].lhs = nontermmap[rule_table[i].lhs];
 371       if (ISVAR (rule_table[i].precsym))
 372         /* Can this happen?  */
 373         rule_table[i].precsym = nontermmap[rule_table[i].precsym];
 374     }
 375
 376   for (i = 0; i < nritems; ++i)
 377     if (ISVAR (ritem[i]))
 378       ritem[i] = nontermmap[ritem[i]];
 379
 380   start_symbol = nontermmap[start_symbol];
 381
 382   nsyms -= nuseless_nonterminals;
 383   nvars -= nuseless_nonterminals;
 384
 385   free (nontermmap + ntokens);
 386 }
 387
 388
 389 /*------------------------------------------------------------------.
 390 | Output the detailed results of the reductions.  For FILE.output.  |
 391 `------------------------------------------------------------------*/
 392
 393 void
 394 reduce_output (FILE *out)
 395 {
 396   if (nuseless_nonterminals > 0)
 397     {
 398       int i;
 399       fprintf (out, "%s\n\n", _("Useless nonterminals:"));
 400       for (i = 0; i < nuseless_nonterminals; ++i)
 401         fprintf (out, "   %s\n", symbols[nsyms + i]->tag);
 402       fputs ("\n\n", out);
 403     }
 404
 405   {
 406     bool b = FALSE;
 407     int i;
 408     for (i = 0; i < ntokens; i++)
 409       if (!BITISSET (V, i) && !BITISSET (V1, i))
 410         {
 411           if (!b)
 412             fprintf (out, "%s\n\n", _("Terminals which are not used:"));
 413           b = TRUE;
 414           fprintf (out, "   %s\n", symbols[i]->tag);
 415         }
 416     if (b)
 417       fputs ("\n\n", out);
 418   }
 419
 420   if (nuseless_productions > 0)
 421     {
 422       int i;
 423       fprintf (out, "%s\n\n", _("Useless rules:"));
 424       for (i = 1; i <= nrules; i++)
 425         if (!rule_table[i].useful)
 426           {
 427             rule r;
 428             fprintf (out, "#%-4d  ", i - 1);
 429             fprintf (out, "%s:", symbols[rule_table[i].lhs]->tag);
 430             for (r = &ritem[rule_table[i].rhs]; *r >= 0; r++)
 431               fprintf (out, " %s", symbols[*r]->tag);
 432             fputs (";\n", out);
 433           }
 434       fputs ("\n\n", out);
 435     }
 436 }
 437 \f
 438 static void
 439 dump_grammar (FILE *out)
 440 {
 441   int i;
 442   rule r;
 443
 444   fprintf (out, "REDUCED GRAMMAR\n\n");
 445   fprintf (out,
 446            "ntokens = %d, nvars = %d, nsyms = %d, nrules = %d, nitems = %d\n\n",
 447            ntokens, nvars, nsyms, nrules, nitems);
 448   fprintf (out, "Variables\n---------\n\n");
 449   fprintf (out, "Value  Sprec  Sassoc  Tag\n");
 450   for (i = ntokens; i < nsyms; i++)
 451     fprintf (out, "%5d  %5d   %5d  %s\n",
 452              i,
 453              symbols[i]->prec, symbols[i]->assoc, symbols[i]->tag);
 454   fprintf (out, "\n\n");
 455   fprintf (out, "Rules\n-----\n\n");
 456   fprintf (out, "Num (Prec, Assoc, Useful, Ritem Range) Lhs -> Rhs (Ritem range) [Num]\n");
 457   for (i = 1; i <= nrules; i++)
 458     {
 459       int rhs_count = 0;
 460       /* Find the last RHS index in ritems. */
 461       for (r = &ritem[rule_table[i].rhs]; *r >= 0; ++r)
 462         ++rhs_count;
 463       fprintf (out, "%3d (%2d, %2d, %2d, %2d-%2d)   %2d ->",
 464                i - 1,
 465                rule_table[i].prec, rule_table[i].assoc, rule_table[i].useful,
 466                rule_table[i].rhs, rule_table[i].rhs + rhs_count - 1,
 467                rule_table[i].lhs);
 468       /* Dumped the RHS. */
 469       for (r = &ritem[rule_table[i].rhs]; *r >= 0; r++)
 470         fprintf (out, "%3d", *r);
 471       fprintf (out, "  [%d]\n", -(*r) - 1);
 472     }
 473   fprintf (out, "\n\n");
 474   fprintf (out, "Rules interpreted\n-----------------\n\n");
 475   for (i = 1; i <= nrules; i++)
 476     {
 477       fprintf (out, "%-5d  %s :", i, symbols[rule_table[i].lhs]->tag);
 478       for (r = &ritem[rule_table[i].rhs]; *r >= 0; r++)
 479         fprintf (out, " %s", symbols[*r]->tag);
 480       fputc ('\n', out);
 481     }
 482   fprintf (out, "\n\n");
 483 }
 484
 485
 486
 487 /*-------------------------------.
 488 | Report the results to STDERR.  |
 489 `-------------------------------*/
 490
 491 static void
 492 reduce_print (void)
 493 {
 494   if (yacc_flag && nuseless_productions)
 495     fprintf (stderr, ngettext ("%d rule never reduced\n",
 496                                "%d rules never reduced\n",
 497                                nuseless_productions),
 498              nuseless_productions);
 499
 500   fprintf (stderr, _("%s contains "), infile);
 501
 502   if (nuseless_nonterminals > 0)
 503     fprintf (stderr, ngettext ("%d useless nonterminal",
 504                                "%d useless nonterminals",
 505                                nuseless_nonterminals),
 506              nuseless_nonterminals);
 507
 508   if (nuseless_nonterminals > 0 && nuseless_productions > 0)
 509     fprintf (stderr, _(" and "));
 510
 511   if (nuseless_productions > 0)
 512     fprintf (stderr, ngettext ("%d useless rule",
 513                                "%d useless rules",
 514                                nuseless_productions),
 515              nuseless_productions);
 516   fprintf (stderr, "\n");
 517   fflush (stderr);
 518 }
 519 \f
 520 void
 521 reduce_grammar (void)
 522 {
 523   bool reduced;
 524
 525   /* Allocate the global sets used to compute the reduced grammar */
 526
 527   N = XCALLOC (unsigned, WORDSIZE (nvars));
 528   P = XCALLOC (unsigned, WORDSIZE (nrules + 1));
 529   V = XCALLOC (unsigned, WORDSIZE (nsyms));
 530   V1 = XCALLOC (unsigned, WORDSIZE (nsyms));
 531
 532   useless_nonterminals ();
 533   inaccessable_symbols ();
 534
 535   reduced = (bool) (nuseless_nonterminals + nuseless_productions > 0);
 536
 537   if (!reduced)
 538     return;
 539
 540   reduce_print ();
 541
 542   if (!BITISSET (N, start_symbol - ntokens))
 543     fatal (_("Start symbol %s does not derive any sentence"),
 544            symbols[start_symbol]->tag);
 545
 546   reduce_grammar_tables ();
 547   if (nuseless_nonterminals > 0)
 548     nonterminals_reduce ();
 549
 550   if (trace_flag)
 551     {
 552       dump_grammar (stderr);
 553
 554       fprintf (stderr, "reduced %s defines %d terminals, %d nonterminals\
 555 , and %d productions.\n",
 556                infile, ntokens, nvars, nrules);
 557     }
 558 }
 559
 560
 561 /*-----------------------------------------------------------.
 562 | Free the global sets used to compute the reduced grammar.  |
 563 `-----------------------------------------------------------*/
 564
 565 void
 566 reduce_free (void)
 567 {
 568   XFREE (N);
 569   XFREE (V);
 570   XFREE (V1);
 571   XFREE (P);
 572 }