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 "xalloc.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 = XCALLOC (unsigned, WORDSIZE (nvars));
 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   XFREE (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 = XCALLOC (unsigned, WORDSIZE (nsyms));
 202   Pp = XCALLOC (unsigned, WORDSIZE (nrules + 1));
 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   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 (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 = XCALLOC (short, nvars) - 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       fputs (_("Useless nonterminals:"), foutput);
 405       fputs ("\n\n", foutput);
 406       for (i = ntokens; i < nsyms; i++)
 407         if (!BITISSET (V, i))
 408           fprintf (foutput, "   %s\n", tags[i]);
 409     }
 410   b = FALSE;
 411   for (i = 0; i < ntokens; i++)
 412     {
 413       if (!BITISSET (V, i) && !BITISSET (V1, i))
 414         {
 415           if (!b)
 416             {
 417               fputs ("\n\n", foutput);
 418               fprintf (foutput, _("Terminals which are not used:"));
 419               fputs ("\n\n", foutput);
 420               b = TRUE;
 421             }
 422           fprintf (foutput, "   %s\n", tags[i]);
 423         }
 424     }
 425
 426   if (nuseless_productions > 0)
 427     {
 428       fputs ("\n\n", foutput);
 429       fprintf (foutput, _("Useless rules:"));
 430       fputs ("\n\n", foutput);
 431       for (i = 1; i <= nrules; i++)
 432         {
 433           if (!BITISSET (P, i))
 434             {
 435               fprintf (foutput, "#%-4d  ", i);
 436               fprintf (foutput, "%s :\t", tags[rlhs[i]]);
 437               for (r = &ritem[rrhs[i]]; *r >= 0; r++)
 438                 {
 439                   fprintf (foutput, " %s", tags[*r]);
 440                 }
 441               fprintf (foutput, ";\n");
 442             }
 443         }
 444     }
 445   if (nuseless_nonterminals > 0 || nuseless_productions > 0 || b)
 446     fputs ("\n\n", foutput);
 447 }
 448 \f
 449 #if 0                           /* XXX currently unused.  */
 450 static void
 451 dump_grammar (void)
 452 {
 453   int i;
 454   rule r;
 455
 456   fprintf (foutput,
 457            "ntokens = %d, nvars = %d, nsyms = %d, nrules = %d, nitems = %d\n\n",
 458            ntokens, nvars, nsyms, nrules, nitems);
 459   fprintf (foutput, _("Variables\n---------\n\n"));
 460   fprintf (foutput, _("Value  Sprec    Sassoc    Tag\n"));
 461   for (i = ntokens; i < nsyms; i++)
 462     fprintf (foutput, "%5d  %5d  %5d  %s\n", i, sprec[i], sassoc[i], tags[i]);
 463   fprintf (foutput, "\n\n");
 464   fprintf (foutput, _("Rules\n-----\n\n"));
 465   for (i = 1; i <= nrules; i++)
 466     {
 467       fprintf (foutput, "%-5d(%5d%5d)%5d : (@%-5d)",
 468                i, rprec[i], rassoc[i], rlhs[i], rrhs[i]);
 469       for (r = &ritem[rrhs[i]]; *r > 0; r++)
 470         fprintf (foutput, "%5d", *r);
 471       fprintf (foutput, " [%d]\n", -(*r));
 472     }
 473   fprintf (foutput, "\n\n");
 474   fprintf (foutput, _("Rules interpreted\n-----------------\n\n"));
 475   for (i = 1; i <= nrules; i++)
 476     {
 477       fprintf (foutput, "%-5d  %s :", i, tags[rlhs[i]]);
 478       for (r = &ritem[rrhs[i]]; *r > 0; r++)
 479         fprintf (foutput, " %s", tags[*r]);
 480       fprintf (foutput, "\n");
 481     }
 482   fprintf (foutput, "\n\n");
 483 }
 484
 485 #endif
 486
 487
 488 static void
 489 print_notices (void)
 490 {
 491   if (yacc_flag && nuseless_productions)
 492     fprintf (stderr, _("%d rules never reduced\n"), nuseless_productions);
 493
 494   fprintf (stderr, _("%s contains "), infile);
 495
 496   if (nuseless_nonterminals > 0)
 497     {
 498       fprintf (stderr, _("%d useless nonterminal%s"),
 499                nuseless_nonterminals,
 500                (nuseless_nonterminals == 1 ? "" : "s"));
 501     }
 502   if (nuseless_nonterminals > 0 && nuseless_productions > 0)
 503     fprintf (stderr, _(" and "));
 504
 505   if (nuseless_productions > 0)
 506     {
 507       fprintf (stderr, _("%d useless rule%s"),
 508                nuseless_productions, (nuseless_productions == 1 ? "" : "s"));
 509     }
 510   fprintf (stderr, "\n");
 511   fflush (stderr);
 512 }
 513 \f
 514 void
 515 reduce_grammar (void)
 516 {
 517   bool reduced;
 518
 519   /* Allocate the global sets used to compute the reduced grammar */
 520
 521   N = XCALLOC (unsigned, WORDSIZE (nvars));
 522   P = XCALLOC (unsigned, WORDSIZE (nrules + 1));
 523   V = XCALLOC (unsigned, WORDSIZE (nsyms));
 524   V1 = XCALLOC (unsigned, WORDSIZE (nsyms));
 525
 526   useless_nonterminals ();
 527   inaccessable_symbols ();
 528
 529   reduced = (bool) (nuseless_nonterminals + nuseless_productions > 0);
 530
 531   if (verbose_flag)
 532     print_results ();
 533
 534   if (reduced == FALSE)
 535     goto done_reducing;
 536
 537   print_notices ();
 538
 539   if (!BITISSET (N, start_symbol - ntokens))
 540     fatal (_("Start symbol %s does not derive any sentence"),
 541            tags[start_symbol]);
 542
 543   reduce_grammar_tables ();
 544 #if 0
 545   if (verbose_flag)
 546     {
 547       fprintf (foutput, "REDUCED GRAMMAR\n\n");
 548       dump_grammar ();
 549     }
 550 #endif
 551
 552   if (statistics_flag)
 553     fprintf (stderr, _("reduced %s defines %d terminal%s, %d nonterminal%s\
 554 , and %d production%s.\n"),
 555              infile,
 556              ntokens,
 557              (ntokens == 1 ? "" : "s"),
 558              nvars,
 559              (nvars == 1 ? "" : "s"),
 560              nrules,
 561              (nrules == 1 ? "" : "s"));
 562
 563 done_reducing:
 564   /* Free the global sets used to compute the reduced grammar */
 565
 566   XFREE (N);
 567   XFREE (V);
 568   XFREE (P);
 569 }