src/reduce.c

   1 /* Grammar reduction for Bison.
   2    Copyright (C) 1988, 1989, 2000 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 "gram.h"
  32 #include "alloc.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 /* N is set of all nonterminals which are not useless.  P is set of
  43    all rules which have no useless nonterminals in their RHS.  V is
  44    the set of all accessible symbols.  */
  45
  46 static BSet N, P, V, V1;
  47
  48 static int nuseful_productions;
  49 static int nuseless_productions;
  50 static int nuseful_nonterminals;
  51 static int nuseless_nonterminals;
  52 \f
  53 static bool
  54 bits_equal (BSet L, BSet R, int n)
  55 {
  56   int i;
  57
  58   for (i = n - 1; i >= 0; i--)
  59     if (L[i] != R[i])
  60       return FALSE;
  61   return TRUE;
  62 }
  63
  64
  65 static int
  66 nbits (unsigned i)
  67 {
  68   int count = 0;
  69
  70   while (i != 0)
  71     {
  72       i ^= (i & ((unsigned) (-(int) i)));
  73       ++count;
  74     }
  75   return count;
  76 }
  77
  78
  79 static int
  80 bits_size (BSet S, int n)
  81 {
  82   int i, count = 0;
  83
  84   for (i = n - 1; i >= 0; i--)
  85     count += nbits (S[i]);
  86   return count;
  87 }
  88 \f
  89 /*-------------------------------------------------------------------.
  90 | Another way to do this would be with a set for each production and |
  91 | then do subset tests against N0, but even for the C grammar the    |
  92 | whole reducing process takes only 2 seconds on my 8Mhz AT.         |
  93 `-------------------------------------------------------------------*/
  94
  95 static bool
  96 useful_production (int i, BSet N0)
  97 {
  98   rule r;
  99   short n;
 100
 101   /* A production is useful if all of the nonterminals in its appear
 102      in the set of useful nonterminals.  */
 103
 104   for (r = &ritem[rrhs[i]]; *r > 0; r++)
 105     if (ISVAR (n = *r))
 106       if (!BITISSET (N0, n - ntokens))
 107         return FALSE;
 108   return TRUE;
 109 }
 110
 111
 112 /*---------------------------------------------------------.
 113 | Remember that rules are 1-origin, symbols are 0-origin.  |
 114 `---------------------------------------------------------*/
 115
 116 static void
 117 useless_nonterminals (void)
 118 {
 119   BSet Np, Ns;
 120   int i, n;
 121
 122   /* N is set as built.  Np is set being built this iteration. P is
 123      set of all productions which have a RHS all in N.  */
 124
 125   Np = NEW2 (WORDSIZE (nvars), unsigned);
 126
 127   /* The set being computed is a set of nonterminals which can derive
 128      the empty string or strings consisting of all terminals. At each
 129      iteration a nonterminal is added to the set if there is a
 130      production with that nonterminal as its LHS for which all the
 131      nonterminals in its RHS are already in the set.  Iterate until
 132      the set being computed remains unchanged.  Any nonterminals not
 133      in the set at that point are useless in that they will never be
 134      used in deriving a sentence of the language.
 135
 136      This iteration doesn't use any special traversal over the
 137      productions.  A set is kept of all productions for which all the
 138      nonterminals in the RHS are in useful.  Only productions not in
 139      this set are scanned on each iteration.  At the end, this set is
 140      saved to be used when finding useful productions: only
 141      productions in this set will appear in the final grammar.  */
 142
 143   n = 0;
 144   while (1)
 145     {
 146       for (i = WORDSIZE (nvars) - 1; i >= 0; i--)
 147         Np[i] = N[i];
 148       for (i = 1; i <= nrules; i++)
 149         {
 150           if (!BITISSET (P, i))
 151             {
 152               if (useful_production (i, N))
 153                 {
 154                   SETBIT (Np, rlhs[i] - ntokens);
 155                   SETBIT (P, i);
 156                 }
 157             }
 158         }
 159       if (bits_equal (N, Np, WORDSIZE (nvars)))
 160         break;
 161       Ns = Np;
 162       Np = N;
 163       N = Ns;
 164     }
 165   FREE (N);
 166   N = Np;
 167 }
 168
 169
 170 static void
 171 inaccessable_symbols (void)
 172 {
 173   BSet Vp, Vs, Pp;
 174   int i, n;
 175   short t;
 176   rule r;
 177
 178   /* Find out which productions are reachable and which symbols are
 179      used.  Starting with an empty set of productions and a set of
 180      symbols which only has the start symbol in it, iterate over all
 181      productions until the set of productions remains unchanged for an
 182      iteration.  For each production which has a LHS in the set of
 183      reachable symbols, add the production to the set of reachable
 184      productions, and add all of the nonterminals in the RHS of the
 185      production to the set of reachable symbols.
 186
 187      Consider only the (partially) reduced grammar which has only
 188      nonterminals in N and productions in P.
 189
 190      The result is the set P of productions in the reduced grammar,
 191      and the set V of symbols in the reduced grammar.
 192
 193      Although this algorithm also computes the set of terminals which
 194      are reachable, no terminal will be deleted from the grammar. Some
 195      terminals might not be in the grammar but might be generated by
 196      semantic routines, and so the user might want them available with
 197      specified numbers.  (Is this true?)  However, the nonreachable
 198      terminals are printed (if running in verbose mode) so that the
 199      user can know.  */
 200
 201   Vp = NEW2 (WORDSIZE (nsyms), unsigned);
 202   Pp = NEW2 (WORDSIZE (nrules + 1), unsigned);
 203
 204   /* If the start symbol isn't useful, then nothing will be useful. */
 205   if (!BITISSET (N, start_symbol - ntokens))
 206     goto end_iteration;
 207
 208   SETBIT (V, start_symbol);
 209
 210   n = 0;
 211   while (1)
 212     {
 213       for (i = WORDSIZE (nsyms) - 1; i >= 0; i--)
 214         Vp[i] = V[i];
 215       for (i = 1; i <= nrules; i++)
 216         {
 217           if (!BITISSET (Pp, i) && BITISSET (P, i) && BITISSET (V, rlhs[i]))
 218             {
 219               for (r = &ritem[rrhs[i]]; *r >= 0; r++)
 220                 {
 221                   if (ISTOKEN (t = *r) || BITISSET (N, t - ntokens))
 222                     {
 223                       SETBIT (Vp, t);
 224                     }
 225                 }
 226               SETBIT (Pp, i);
 227             }
 228         }
 229       if (bits_equal (V, Vp, WORDSIZE (nsyms)))
 230         {
 231           break;
 232         }
 233       Vs = Vp;
 234       Vp = V;
 235       V = Vs;
 236     }
 237 end_iteration:
 238
 239   FREE (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   FREE (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 (rprecsym[i] != 0)
 262       SETBIT (V1, rprecsym[i]);
 263 }
 264
 265 static void
 266 reduce_grammar_tables (void)
 267 {
 268 /* This is turned off because we would need to change the numbers
 269    in the case statements in the actions file.  */
 270 #if 0
 271   /* remove useless productions */
 272   if (nuseless_productions > 0)
 273     {
 274       short np, pn, ni, pi;
 275
 276       np = 0;
 277       ni = 0;
 278       for (pn = 1; pn <= nrules; pn++)
 279         {
 280           if (BITISSET (P, pn))
 281             {
 282               np++;
 283               if (pn != np)
 284                 {
 285                   rlhs[np] = rlhs[pn];
 286                   rline[np] = rline[pn];
 287                   rprec[np] = rprec[pn];
 288                   rassoc[np] = rassoc[pn];
 289                   rrhs[np] = rrhs[pn];
 290                   if (rrhs[np] != ni)
 291                     {
 292                       pi = rrhs[np];
 293                       rrhs[np] = ni;
 294                       while (ritem[pi] >= 0)
 295                         ritem[ni++] = ritem[pi++];
 296                       ritem[ni++] = -np;
 297                     }
 298                 }
 299               else
 300                 {
 301                   while (ritem[ni++] >= 0);
 302                 }
 303             }
 304         }
 305       ritem[ni] = 0;
 306       nrules -= nuseless_productions;
 307       nitems = ni;
 308
 309       /* Is it worth it to reduce the amount of memory for the
 310          grammar? Probably not.  */
 311
 312     }
 313 #endif /* 0 */
 314   /* Disable useless productions,
 315      since they may contain useless nonterms
 316      that would get mapped below to -1 and confuse everyone.  */
 317   if (nuseless_productions > 0)
 318     {
 319       int pn;
 320
 321       for (pn = 1; pn <= nrules; pn++)
 322         {
 323           if (!BITISSET (P, pn))
 324             {
 325               rlhs[pn] = -1;
 326             }
 327         }
 328     }
 329
 330   /* remove useless symbols */
 331   if (nuseless_nonterminals > 0)
 332     {
 333
 334       int i, n;
 335 /*      short  j; JF unused */
 336       short *nontermmap;
 337       rule r;
 338
 339       /* Create a map of nonterminal number to new nonterminal
 340          number. -1 in the map means it was useless and is being
 341          eliminated.  */
 342
 343       nontermmap = NEW2 (nvars, short) - ntokens;
 344       for (i = ntokens; i < nsyms; i++)
 345         nontermmap[i] = -1;
 346
 347       n = ntokens;
 348       for (i = ntokens; i < nsyms; i++)
 349         if (BITISSET (V, i))
 350           nontermmap[i] = n++;
 351
 352       /* Shuffle elements of tables indexed by symbol number.  */
 353
 354       for (i = ntokens; i < nsyms; i++)
 355         {
 356           n = nontermmap[i];
 357           if (n >= 0)
 358             {
 359               sassoc[n] = sassoc[i];
 360               sprec[n] = sprec[i];
 361               tags[n] = tags[i];
 362             }
 363           else
 364             {
 365               free (tags[i]);
 366             }
 367         }
 368
 369       /* Replace all symbol numbers in valid data structures.  */
 370
 371       for (i = 1; i <= nrules; i++)
 372         {
 373           /* Ignore the rules disabled above.  */
 374           if (rlhs[i] >= 0)
 375             rlhs[i] = nontermmap[rlhs[i]];
 376           if (ISVAR (rprecsym[i]))
 377             /* Can this happen?  */
 378             rprecsym[i] = nontermmap[rprecsym[i]];
 379         }
 380
 381       for (r = ritem; *r; r++)
 382         if (ISVAR (*r))
 383           *r = nontermmap[*r];
 384
 385       start_symbol = nontermmap[start_symbol];
 386
 387       nsyms -= nuseless_nonterminals;
 388       nvars -= nuseless_nonterminals;
 389
 390       free (&nontermmap[ntokens]);
 391     }
 392 }
 393
 394 static void
 395 print_results (void)
 396 {
 397   int i;
 398 /*  short j; JF unused */
 399   rule r;
 400   bool b;
 401
 402   if (nuseless_nonterminals > 0)
 403     {
 404       fprintf (foutput, _("Useless nonterminals:\n\n"));
 405       for (i = ntokens; i < nsyms; i++)
 406         if (!BITISSET (V, i))
 407           fprintf (foutput, "   %s\n", tags[i]);
 408     }
 409   b = FALSE;
 410   for (i = 0; i < ntokens; i++)
 411     {
 412       if (!BITISSET (V, i) && !BITISSET (V1, i))
 413         {
 414           if (!b)
 415             {
 416               fprintf (foutput, _("\n\nTerminals which are not used:\n\n"));
 417               b = TRUE;
 418             }
 419           fprintf (foutput, "   %s\n", tags[i]);
 420         }
 421     }
 422
 423   if (nuseless_productions > 0)
 424     {
 425       fprintf (foutput, _("\n\nUseless rules:\n\n"));
 426       for (i = 1; i <= nrules; i++)
 427         {
 428           if (!BITISSET (P, i))
 429             {
 430               fprintf (foutput, "#%-4d  ", i);
 431               fprintf (foutput, "%s :\t", tags[rlhs[i]]);
 432               for (r = &ritem[rrhs[i]]; *r >= 0; r++)
 433                 {
 434                   fprintf (foutput, " %s", tags[*r]);
 435                 }
 436               fprintf (foutput, ";\n");
 437             }
 438         }
 439     }
 440   if (nuseless_nonterminals > 0 || nuseless_productions > 0 || b)
 441     fprintf (foutput, "\n\n");
 442 }
 443 \f
 444 #if 0                           /* XXX currently unused.  */
 445 static void
 446 dump_grammar (void)
 447 {
 448   int i;
 449   rule r;
 450
 451   fprintf (foutput,
 452            "ntokens = %d, nvars = %d, nsyms = %d, nrules = %d, nitems = %d\n\n",
 453            ntokens, nvars, nsyms, nrules, nitems);
 454   fprintf (foutput, _("Variables\n---------\n\n"));
 455   fprintf (foutput, _("Value  Sprec    Sassoc    Tag\n"));
 456   for (i = ntokens; i < nsyms; i++)
 457     fprintf (foutput, "%5d  %5d  %5d  %s\n", i, sprec[i], sassoc[i], tags[i]);
 458   fprintf (foutput, "\n\n");
 459   fprintf (foutput, _("Rules\n-----\n\n"));
 460   for (i = 1; i <= nrules; i++)
 461     {
 462       fprintf (foutput, "%-5d(%5d%5d)%5d : (@%-5d)",
 463                i, rprec[i], rassoc[i], rlhs[i], rrhs[i]);
 464       for (r = &ritem[rrhs[i]]; *r > 0; r++)
 465         fprintf (foutput, "%5d", *r);
 466       fprintf (foutput, " [%d]\n", -(*r));
 467     }
 468   fprintf (foutput, "\n\n");
 469   fprintf (foutput, _("Rules interpreted\n-----------------\n\n"));
 470   for (i = 1; i <= nrules; i++)
 471     {
 472       fprintf (foutput, "%-5d  %s :", i, tags[rlhs[i]]);
 473       for (r = &ritem[rrhs[i]]; *r > 0; r++)
 474         fprintf (foutput, " %s", tags[*r]);
 475       fprintf (foutput, "\n");
 476     }
 477   fprintf (foutput, "\n\n");
 478 }
 479
 480 #endif
 481
 482
 483 static void
 484 print_notices (void)
 485 {
 486   if (fixed_outfiles && nuseless_productions)
 487     fprintf (stderr, _("%d rules never reduced\n"), nuseless_productions);
 488
 489   fprintf (stderr, _("%s contains "), infile);
 490
 491   if (nuseless_nonterminals > 0)
 492     {
 493       fprintf (stderr, _("%d useless nonterminal%s"),
 494                nuseless_nonterminals,
 495                (nuseless_nonterminals == 1 ? "" : "s"));
 496     }
 497   if (nuseless_nonterminals > 0 && nuseless_productions > 0)
 498     fprintf (stderr, _(" and "));
 499
 500   if (nuseless_productions > 0)
 501     {
 502       fprintf (stderr, _("%d useless rule%s"),
 503                nuseless_productions, (nuseless_productions == 1 ? "" : "s"));
 504     }
 505   fprintf (stderr, "\n");
 506   fflush (stderr);
 507 }
 508 \f
 509 void
 510 reduce_grammar (void)
 511 {
 512   bool reduced;
 513
 514   /* Allocate the global sets used to compute the reduced grammar */
 515
 516   N = NEW2 (WORDSIZE (nvars), unsigned);
 517   P = NEW2 (WORDSIZE (nrules + 1), unsigned);
 518   V = NEW2 (WORDSIZE (nsyms), unsigned);
 519   V1 = NEW2 (WORDSIZE (nsyms), unsigned);
 520
 521   useless_nonterminals ();
 522   inaccessable_symbols ();
 523
 524   reduced = (bool) (nuseless_nonterminals + nuseless_productions > 0);
 525
 526   if (verboseflag)
 527     print_results ();
 528
 529   if (reduced == FALSE)
 530     goto done_reducing;
 531
 532   print_notices ();
 533
 534   if (!BITISSET (N, start_symbol - ntokens))
 535     fatal (_("Start symbol %s does not derive any sentence"),
 536            tags[start_symbol]);
 537
 538   reduce_grammar_tables ();
 539 #if 0
 540   if (verboseflag)
 541     {
 542       fprintf (foutput, "REDUCED GRAMMAR\n\n");
 543       dump_grammar ();
 544     }
 545 #endif
 546
 547   if (statisticsflag)
 548     fprintf (stderr, _("reduced %s defines %d terminal%s, %d nonterminal%s\
 549 , and %d production%s.\n"),
 550              infile,
 551              ntokens,
 552              (ntokens == 1 ? "" : "s"),
 553              nvars,
 554              (nvars == 1 ? "" : "s"),
 555              nrules,
 556              (nrules == 1 ? "" : "s"));
 557
 558 done_reducing:
 559   /* Free the global sets used to compute the reduced grammar */
 560
 561   FREE (N);
 562   FREE (V);
 563   FREE (P);
 564 }