src/reduce.c

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