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[rule_table[i].rhs]; *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, rule_table[i].lhs - 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     {
 205       SETBIT (V, start_symbol);
 206
 207       while (1)
 208         {
 209           for (i = WORDSIZE (nsyms) - 1; i >= 0; i--)
 210             Vp[i] = V[i];
 211           for (i = 1; i <= nrules; i++)
 212             {
 213               if (!BITISSET (Pp, i)
 214                   && BITISSET (P, i)
 215                   && BITISSET (V, rule_table[i].lhs))
 216                 {
 217                   for (r = &ritem[rule_table[i].rhs]; *r >= 0; r++)
 218                     if (ISTOKEN (t = *r) || BITISSET (N, t - ntokens))
 219                       SETBIT (Vp, t);
 220                   SETBIT (Pp, i);
 221                 }
 222             }
 223           if (bits_equal (V, Vp, WORDSIZE (nsyms)))
 224             break;
 225           Vs = Vp;
 226           Vp = V;
 227           V = Vs;
 228         }
 229     }
 230
 231   XFREE (V);
 232   V = Vp;
 233
 234   /* Tokens 0, 1, and 2 are internal to Bison.  Consider them useful. */
 235   SETBIT (V, 0);                /* end-of-input token */
 236   SETBIT (V, 1);                /* error token */
 237   SETBIT (V, 2);                /* some undefined token */
 238
 239   XFREE (P);
 240   P = Pp;
 241
 242   nuseful_productions = bits_size (P, WORDSIZE (nrules + 1));
 243   nuseless_productions = nrules - nuseful_productions;
 244
 245   nuseful_nonterminals = 0;
 246   for (i = ntokens; i < nsyms; i++)
 247     if (BITISSET (V, i))
 248       nuseful_nonterminals++;
 249   nuseless_nonterminals = nvars - nuseful_nonterminals;
 250
 251   /* A token that was used in %prec should not be warned about.  */
 252   for (i = 1; i < nrules; i++)
 253     if (rule_table[i].precsym != 0)
 254       SETBIT (V1, rule_table[i].precsym);
 255 }
 256
 257 static void
 258 reduce_grammar_tables (void)
 259 {
 260 /* This is turned off because we would need to change the numbers
 261    in the case statements in the actions file.  */
 262 #if 0
 263   /* remove useless productions */
 264   if (nuseless_productions > 0)
 265     {
 266       short np, pn, ni, pi;
 267
 268       np = 0;
 269       ni = 0;
 270       for (pn = 1; pn <= nrules; pn++)
 271         {
 272           if (BITISSET (P, pn))
 273             {
 274               np++;
 275               if (pn != np)
 276                 {
 277                   rule_table[np].lhs = rule_table[pn].lhs;
 278                   rline[np] = rline[pn];
 279                   rule_table[np].prec = rule_table[pn].prec;
 280                   rule_table[np].assoc = rule_table[pn].assoc;
 281                   rule_table[np].rhs = rule_table[pn].rhs;
 282                   if (rule_table[np].rhs != ni)
 283                     {
 284                       pi = rule_table[np].rhs;
 285                       rule_table[np].rhs = ni;
 286                       while (ritem[pi] >= 0)
 287                         ritem[ni++] = ritem[pi++];
 288                       ritem[ni++] = -np;
 289                     }
 290                 }
 291               else
 292                 {
 293                   while (ritem[ni++] >= 0);
 294                 }
 295             }
 296         }
 297       ritem[ni] = 0;
 298       nrules -= nuseless_productions;
 299       nitems = ni;
 300
 301       /* Is it worth it to reduce the amount of memory for the
 302          grammar? Probably not.  */
 303
 304     }
 305 #endif /* 0 */
 306   /* Disable useless productions,
 307      since they may contain useless nonterms
 308      that would get mapped below to -1 and confuse everyone.  */
 309   if (nuseless_productions > 0)
 310     {
 311       int pn;
 312
 313       for (pn = 1; pn <= nrules; pn++)
 314         {
 315           if (!BITISSET (P, pn))
 316             {
 317               rule_table[pn].lhs = -1;
 318             }
 319         }
 320     }
 321
 322   /* remove useless symbols */
 323   if (nuseless_nonterminals > 0)
 324     {
 325
 326       int i, n;
 327 /*      short  j; JF unused */
 328       short *nontermmap;
 329       rule r;
 330
 331       /* Create a map of nonterminal number to new nonterminal
 332          number. -1 in the map means it was useless and is being
 333          eliminated.  */
 334
 335       nontermmap = XCALLOC (short, nvars) - ntokens;
 336       for (i = ntokens; i < nsyms; i++)
 337         nontermmap[i] = -1;
 338
 339       n = ntokens;
 340       for (i = ntokens; i < nsyms; i++)
 341         if (BITISSET (V, i))
 342           nontermmap[i] = n++;
 343
 344       /* Shuffle elements of tables indexed by symbol number.  */
 345
 346       for (i = ntokens; i < nsyms; i++)
 347         {
 348           n = nontermmap[i];
 349           if (n >= 0)
 350             {
 351               sassoc[n] = sassoc[i];
 352               sprec[n] = sprec[i];
 353               tags[n] = tags[i];
 354             }
 355         }
 356
 357       /* Replace all symbol numbers in valid data structures.  */
 358
 359       for (i = 1; i <= nrules; i++)
 360         {
 361           /* Ignore the rules disabled above.  */
 362           if (rule_table[i].lhs >= 0)
 363             rule_table[i].lhs = nontermmap[rule_table[i].lhs];
 364           if (ISVAR (rule_table[i].precsym))
 365             /* Can this happen?  */
 366             rule_table[i].precsym = nontermmap[rule_table[i].precsym];
 367         }
 368
 369       for (r = ritem; *r; r++)
 370         if (ISVAR (*r))
 371           *r = nontermmap[*r];
 372
 373       start_symbol = nontermmap[start_symbol];
 374
 375       nsyms -= nuseless_nonterminals;
 376       nvars -= nuseless_nonterminals;
 377
 378       free (&nontermmap[ntokens]);
 379     }
 380 }
 381
 382
 383 /*-----------------------------------------------------------------.
 384 | Ouput the detailed results of the reductions.  For FILE.output.  |
 385 `-----------------------------------------------------------------*/
 386
 387 void
 388 reduce_output (FILE *out)
 389 {
 390   int i;
 391   rule r;
 392   bool b;
 393
 394   if (nuseless_nonterminals > 0)
 395     {
 396       fprintf (out, _("Useless nonterminals:"));
 397       fprintf (out, "\n\n");
 398       for (i = ntokens; i < nsyms; i++)
 399         if (!BITISSET (V, i))
 400           fprintf (out, "   %s\n", tags[i]);
 401     }
 402   b = FALSE;
 403   for (i = 0; i < ntokens; i++)
 404     {
 405       if (!BITISSET (V, i) && !BITISSET (V1, i))
 406         {
 407           if (!b)
 408             {
 409               fprintf (out, "\n\n");
 410               fprintf (out, _("Terminals which are not used:"));
 411               fprintf (out, "\n\n");
 412               b = TRUE;
 413             }
 414           fprintf (out, "   %s\n", tags[i]);
 415         }
 416     }
 417
 418   if (nuseless_productions > 0)
 419     {
 420       fprintf (out, "\n\n");
 421       fprintf (out, _("Useless rules:"));
 422       fprintf (out, "\n\n");
 423       for (i = 1; i <= nrules; i++)
 424         if (!BITISSET (P, i))
 425           {
 426             fprintf (out, "#%-4d  ", i);
 427             fprintf (out, "%s :\t", tags[rule_table[i].lhs]);
 428             for (r = &ritem[rule_table[i].rhs]; *r >= 0; r++)
 429               fprintf (out, " %s", tags[*r]);
 430             fprintf (out, ";\n");
 431           }
 432     }
 433   if (nuseless_nonterminals > 0 || nuseless_productions > 0 || b)
 434     fprintf (out, "\n\n");
 435 }
 436 \f
 437 static void
 438 dump_grammar (FILE *out)
 439 {
 440   int i;
 441   rule r;
 442
 443   fprintf (out, "REDUCED GRAMMAR\n\n");
 444   fprintf (out,
 445            "ntokens = %d, nvars = %d, nsyms = %d, nrules = %d, nitems = %d\n\n",
 446            ntokens, nvars, nsyms, nrules, nitems);
 447   fprintf (out, "Variables\n---------\n\n");
 448   fprintf (out, "Value  Sprec  Sassoc  Tag\n");
 449   for (i = ntokens; i < nsyms; i++)
 450     fprintf (out, "%5d  %5d   %5d  %s\n", i, sprec[i], sassoc[i], tags[i]);
 451   fprintf (out, "\n\n");
 452   fprintf (out, "Rules\n-----\n\n");
 453   fprintf (out, "Num (Prec, Assoc) Lhs : (@Rhs) Ritems [Num?]\n");
 454   for (i = 1; i <= nrules; i++)
 455     {
 456       fprintf (out, "%-5d(%5d%5d)%5d : (@%-5d)",
 457                i,
 458                rule_table[i].prec,
 459                rule_table[i].assoc,
 460                rule_table[i].lhs,
 461                rule_table[i].rhs);
 462       for (r = &ritem[rule_table[i].rhs]; *r > 0; r++)
 463         fprintf (out, "%5d", *r);
 464       fprintf (out, " [%d]\n", -(*r));
 465     }
 466   fprintf (out, "\n\n");
 467   fprintf (out, "Rules interpreted\n-----------------\n\n");
 468   for (i = 1; i <= nrules; i++)
 469     {
 470       fprintf (out, "%-5d  %s :", i, tags[rule_table[i].lhs]);
 471       for (r = &ritem[rule_table[i].rhs]; *r > 0; r++)
 472         fprintf (out, " %s", tags[*r]);
 473       fputc ('\n', out);
 474     }
 475   fprintf (out, "\n\n");
 476 }
 477
 478
 479
 480 /*-------------------------------.
 481 | Report the results to STDERR.  |
 482 `-------------------------------*/
 483
 484 static void
 485 reduce_print (void)
 486 {
 487   if (yacc_flag && nuseless_productions)
 488     fprintf (stderr, ngettext ("%d rule never reduced\n",
 489                                "%d rules never reduced\n",
 490                                nuseless_productions),
 491              nuseless_productions);
 492
 493   fprintf (stderr, _("%s contains "), infile);
 494
 495   if (nuseless_nonterminals > 0)
 496     fprintf (stderr, ngettext ("%d useless nonterminal",
 497                                "%d useless nonterminals",
 498                                nuseless_nonterminals),
 499              nuseless_nonterminals);
 500
 501   if (nuseless_nonterminals > 0 && nuseless_productions > 0)
 502     fprintf (stderr, _(" and "));
 503
 504   if (nuseless_productions > 0)
 505     fprintf (stderr, ngettext ("%d useless rule",
 506                                "%d useless rules",
 507                                nuseless_productions),
 508              nuseless_productions);
 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 (!reduced)
 531     return;
 532
 533   reduce_print ();
 534
 535   if (!BITISSET (N, start_symbol - ntokens))
 536     fatal (_("Start symbol %s does not derive any sentence"),
 537            tags[start_symbol]);
 538
 539   reduce_grammar_tables ();
 540
 541   if (trace_flag)
 542     {
 543       dump_grammar (stderr);
 544
 545       fprintf (stderr, "reduced %s defines %d terminals, %d nonterminals\
 546 , and %d productions.\n",
 547                infile, ntokens, nvars, nrules);
 548     }
 549 }
 550
 551
 552 /*-----------------------------------------------------------.
 553 | Free the global sets used to compute the reduced grammar.  |
 554 `-----------------------------------------------------------*/
 555
 556 void
 557 reduce_free (void)
 558 {
 559   XFREE (N);
 560   XFREE (V);
 561   XFREE (V1);
 562   XFREE (P);
 563 }