src/reduce.c

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