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