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;
 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   while (1)
 144     {
 145       for (i = WORDSIZE (nvars) - 1; i >= 0; i--)
 146         Np[i] = N[i];
 147       for (i = 1; i <= nrules; i++)
 148         {
 149           if (!BITISSET (P, i))
 150             {
 151               if (useful_production (i, N))
 152                 {
 153                   SETBIT (Np, rlhs[i] - ntokens);
 154                   SETBIT (P, i);
 155                 }
 156             }
 157         }
 158       if (bits_equal (N, Np, WORDSIZE (nvars)))
 159         break;
 160       Ns = Np;
 161       Np = N;
 162       N = Ns;
 163     }
 164   XFREE (N);
 165   N = Np;
 166 }
 167
 168
 169 static void
 170 inaccessable_symbols (void)
 171 {
 172   BSet Vp, Vs, Pp;
 173   int i;
 174   short t;
 175   rule r;
 176
 177   /* Find out which productions are reachable and which symbols are
 178      used.  Starting with an empty set of productions and a set of
 179      symbols which only has the start symbol in it, iterate over all
 180      productions until the set of productions remains unchanged for an
 181      iteration.  For each production which has a LHS in the set of
 182      reachable symbols, add the production to the set of reachable
 183      productions, and add all of the nonterminals in the RHS of the
 184      production to the set of reachable symbols.
 185
 186      Consider only the (partially) reduced grammar which has only
 187      nonterminals in N and productions in P.
 188
 189      The result is the set P of productions in the reduced grammar,
 190      and the set V of symbols in the reduced grammar.
 191
 192      Although this algorithm also computes the set of terminals which
 193      are reachable, no terminal will be deleted from the grammar. Some
 194      terminals might not be in the grammar but might be generated by
 195      semantic routines, and so the user might want them available with
 196      specified numbers.  (Is this true?)  However, the nonreachable
 197      terminals are printed (if running in verbose mode) so that the
 198      user can know.  */
 199
 200   Vp = XCALLOC (unsigned, WORDSIZE (nsyms));
 201   Pp = XCALLOC (unsigned, WORDSIZE (nrules + 1));
 202
 203   /* If the start symbol isn't useful, then nothing will be useful. */
 204   if (!BITISSET (N, start_symbol - ntokens))
 205     goto end_iteration;
 206
 207   SETBIT (V, start_symbol);
 208
 209   while (1)
 210     {
 211       for (i = WORDSIZE (nsyms) - 1; i >= 0; i--)
 212         Vp[i] = V[i];
 213       for (i = 1; i <= nrules; i++)
 214         {
 215           if (!BITISSET (Pp, i) && BITISSET (P, i) && BITISSET (V, rlhs[i]))
 216             {
 217               for (r = &ritem[rrhs[i]]; *r >= 0; r++)
 218                 {
 219                   if (ISTOKEN (t = *r) || BITISSET (N, t - ntokens))
 220                     {
 221                       SETBIT (Vp, t);
 222                     }
 223                 }
 224               SETBIT (Pp, i);
 225             }
 226         }
 227       if (bits_equal (V, Vp, WORDSIZE (nsyms)))
 228         {
 229           break;
 230         }
 231       Vs = Vp;
 232       Vp = V;
 233       V = Vs;
 234     }
 235 end_iteration:
 236
 237   XFREE (V);
 238   V = Vp;
 239
 240   /* Tokens 0, 1, and 2 are internal to Bison.  Consider them useful. */
 241   SETBIT (V, 0);                /* end-of-input token */
 242   SETBIT (V, 1);                /* error token */
 243   SETBIT (V, 2);                /* some undefined token */
 244
 245   XFREE (P);
 246   P = Pp;
 247
 248   nuseful_productions = bits_size (P, WORDSIZE (nrules + 1));
 249   nuseless_productions = nrules - nuseful_productions;
 250
 251   nuseful_nonterminals = 0;
 252   for (i = ntokens; i < nsyms; i++)
 253     if (BITISSET (V, i))
 254       nuseful_nonterminals++;
 255   nuseless_nonterminals = nvars - nuseful_nonterminals;
 256
 257   /* A token that was used in %prec should not be warned about.  */
 258   for (i = 1; i < nrules; i++)
 259     if (rprecsym[i] != 0)
 260       SETBIT (V1, rprecsym[i]);
 261 }
 262
 263 static void
 264 reduce_grammar_tables (void)
 265 {
 266 /* This is turned off because we would need to change the numbers
 267    in the case statements in the actions file.  */
 268 #if 0
 269   /* remove useless productions */
 270   if (nuseless_productions > 0)
 271     {
 272       short np, pn, ni, pi;
 273
 274       np = 0;
 275       ni = 0;
 276       for (pn = 1; pn <= nrules; pn++)
 277         {
 278           if (BITISSET (P, pn))
 279             {
 280               np++;
 281               if (pn != np)
 282                 {
 283                   rlhs[np] = rlhs[pn];
 284                   rline[np] = rline[pn];
 285                   rprec[np] = rprec[pn];
 286                   rassoc[np] = rassoc[pn];
 287                   rrhs[np] = rrhs[pn];
 288                   if (rrhs[np] != ni)
 289                     {
 290                       pi = rrhs[np];
 291                       rrhs[np] = ni;
 292                       while (ritem[pi] >= 0)
 293                         ritem[ni++] = ritem[pi++];
 294                       ritem[ni++] = -np;
 295                     }
 296                 }
 297               else
 298                 {
 299                   while (ritem[ni++] >= 0);
 300                 }
 301             }
 302         }
 303       ritem[ni] = 0;
 304       nrules -= nuseless_productions;
 305       nitems = ni;
 306
 307       /* Is it worth it to reduce the amount of memory for the
 308          grammar? Probably not.  */
 309
 310     }
 311 #endif /* 0 */
 312   /* Disable useless productions,
 313      since they may contain useless nonterms
 314      that would get mapped below to -1 and confuse everyone.  */
 315   if (nuseless_productions > 0)
 316     {
 317       int pn;
 318
 319       for (pn = 1; pn <= nrules; pn++)
 320         {
 321           if (!BITISSET (P, pn))
 322             {
 323               rlhs[pn] = -1;
 324             }
 325         }
 326     }
 327
 328   /* remove useless symbols */
 329   if (nuseless_nonterminals > 0)
 330     {
 331
 332       int i, n;
 333 /*      short  j; JF unused */
 334       short *nontermmap;
 335       rule r;
 336
 337       /* Create a map of nonterminal number to new nonterminal
 338          number. -1 in the map means it was useless and is being
 339          eliminated.  */
 340
 341       nontermmap = XCALLOC (short, nvars) - ntokens;
 342       for (i = ntokens; i < nsyms; i++)
 343         nontermmap[i] = -1;
 344
 345       n = ntokens;
 346       for (i = ntokens; i < nsyms; i++)
 347         if (BITISSET (V, i))
 348           nontermmap[i] = n++;
 349
 350       /* Shuffle elements of tables indexed by symbol number.  */
 351
 352       for (i = ntokens; i < nsyms; i++)
 353         {
 354           n = nontermmap[i];
 355           if (n >= 0)
 356             {
 357               sassoc[n] = sassoc[i];
 358               sprec[n] = sprec[i];
 359               tags[n] = tags[i];
 360             }
 361           else
 362             {
 363               free (tags[i]);
 364             }
 365         }
 366
 367       /* Replace all symbol numbers in valid data structures.  */
 368
 369       for (i = 1; i <= nrules; i++)
 370         {
 371           /* Ignore the rules disabled above.  */
 372           if (rlhs[i] >= 0)
 373             rlhs[i] = nontermmap[rlhs[i]];
 374           if (ISVAR (rprecsym[i]))
 375             /* Can this happen?  */
 376             rprecsym[i] = nontermmap[rprecsym[i]];
 377         }
 378
 379       for (r = ritem; *r; r++)
 380         if (ISVAR (*r))
 381           *r = nontermmap[*r];
 382
 383       start_symbol = nontermmap[start_symbol];
 384
 385       nsyms -= nuseless_nonterminals;
 386       nvars -= nuseless_nonterminals;
 387
 388       free (&nontermmap[ntokens]);
 389     }
 390 }
 391
 392 static void
 393 print_results (void)
 394 {
 395   int i;
 396 /*  short j; JF unused */
 397   rule r;
 398   bool b;
 399
 400   if (nuseless_nonterminals > 0)
 401     {
 402       obstack_sgrow (&output_obstack, _("Useless nonterminals:"));
 403       obstack_sgrow (&output_obstack, "\n\n");
 404       for (i = ntokens; i < nsyms; i++)
 405         if (!BITISSET (V, i))
 406           obstack_fgrow1 (&output_obstack, "   %s\n", tags[i]);
 407     }
 408   b = FALSE;
 409   for (i = 0; i < ntokens; i++)
 410     {
 411       if (!BITISSET (V, i) && !BITISSET (V1, i))
 412         {
 413           if (!b)
 414             {
 415               obstack_sgrow (&output_obstack, "\n\n");
 416               obstack_sgrow (&output_obstack,
 417                                    _("Terminals which are not used:"));
 418               obstack_sgrow (&output_obstack, "\n\n");
 419               b = TRUE;
 420             }
 421           obstack_fgrow1 (&output_obstack, "   %s\n", tags[i]);
 422         }
 423     }
 424
 425   if (nuseless_productions > 0)
 426     {
 427       obstack_sgrow (&output_obstack, "\n\n");
 428       obstack_sgrow (&output_obstack, _("Useless rules:"));
 429       obstack_sgrow (&output_obstack, "\n\n");
 430       for (i = 1; i <= nrules; i++)
 431         {
 432           if (!BITISSET (P, i))
 433             {
 434               obstack_fgrow1 (&output_obstack, "#%-4d  ", i);
 435               obstack_fgrow1 (&output_obstack, "%s :\t", tags[rlhs[i]]);
 436               for (r = &ritem[rrhs[i]]; *r >= 0; r++)
 437                 obstack_fgrow1 (&output_obstack, " %s", tags[*r]);
 438               obstack_sgrow (&output_obstack, ";\n");
 439             }
 440         }
 441     }
 442   if (nuseless_nonterminals > 0 || nuseless_productions > 0 || b)
 443     obstack_sgrow (&output_obstack, "\n\n");
 444 }
 445 \f
 446 #if 0                           /* XXX currently unused.  */
 447 static void
 448 dump_grammar (void)
 449 {
 450   int i;
 451   rule r;
 452
 453   obstack_fgrow5 (&output_obstack,
 454          "ntokens = %d, nvars = %d, nsyms = %d, nrules = %d, nitems = %d\n\n",
 455          ntokens, nvars, nsyms, nrules, nitems);
 456   obstack_sgrow (&output_obstack,
 457                        _("Variables\n---------\n\n"));
 458   obstack_sgrow (&output_obstack,
 459                        _("Value  Sprec    Sassoc    Tag\n"));
 460   for (i = ntokens; i < nsyms; i++)
 461     obstack_fgrow4 (&output_obstack,
 462                     "%5d  %5d  %5d  %s\n", i, sprec[i], sassoc[i], tags[i]);
 463   obstack_sgrow (&output_obstack, "\n\n");
 464   obstack_sgrow (&output_obstack, _("Rules\n-----\n\n"));
 465   for (i = 1; i <= nrules; i++)
 466     {
 467       obstack_fgrow5 (&output_obstack, "%-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         obstack_fgrow1 (&output_obstack, "%5d", *r);
 471       obstack_fgrow1 (&output_obstack, " [%d]\n", -(*r));
 472     }
 473   obstack_sgrow (&output_obstack, "\n\n");
 474   obstack_sgrow (&output_obstack,
 475                        _("Rules interpreted\n-----------------\n\n"));
 476   for (i = 1; i <= nrules; i++)
 477     {
 478       obstack_fgrow2 (&output_obstack, "%-5d  %s :", i, tags[rlhs[i]]);
 479       for (r = &ritem[rrhs[i]]; *r > 0; r++)
 480         obstack_fgrow1 (&output_obstack, " %s", tags[*r]);
 481       obstack_grow1 (&output_obstack, '\n');
 482     }
 483   obstack_sgrow (&output_obstack, "\n\n");
 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       obstack_fgrow1 (&output_obstack, "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 }