src/reduce.c

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