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           else
 356             {
 357               free (tags[i]);
 358             }
 359         }
 360
 361       /* Replace all symbol numbers in valid data structures.  */
 362
 363       for (i = 1; i <= nrules; i++)
 364         {
 365           /* Ignore the rules disabled above.  */
 366           if (rule_table[i].lhs >= 0)
 367             rule_table[i].lhs = nontermmap[rule_table[i].lhs];
 368           if (ISVAR (rule_table[i].precsym))
 369             /* Can this happen?  */
 370             rule_table[i].precsym = nontermmap[rule_table[i].precsym];
 371         }
 372
 373       for (r = ritem; *r; r++)
 374         if (ISVAR (*r))
 375           *r = nontermmap[*r];
 376
 377       start_symbol = nontermmap[start_symbol];
 378
 379       nsyms -= nuseless_nonterminals;
 380       nvars -= nuseless_nonterminals;
 381
 382       free (&nontermmap[ntokens]);
 383     }
 384 }
 385
 386
 387 /*-----------------------------------------------------------------.
 388 | Ouput the detailed results of the reductions.  For FILE.output.  |
 389 `-----------------------------------------------------------------*/
 390
 391 void
 392 reduce_output (FILE *out)
 393 {
 394   int i;
 395   rule r;
 396   bool b;
 397
 398   if (nuseless_nonterminals > 0)
 399     {
 400       fprintf (out, _("Useless nonterminals:"));
 401       fprintf (out, "\n\n");
 402       for (i = ntokens; i < nsyms; i++)
 403         if (!BITISSET (V, i))
 404           fprintf (out, "   %s\n", tags[i]);
 405     }
 406   b = FALSE;
 407   for (i = 0; i < ntokens; i++)
 408     {
 409       if (!BITISSET (V, i) && !BITISSET (V1, i))
 410         {
 411           if (!b)
 412             {
 413               fprintf (out, "\n\n");
 414               fprintf (out, _("Terminals which are not used:"));
 415               fprintf (out, "\n\n");
 416               b = TRUE;
 417             }
 418           fprintf (out, "   %s\n", tags[i]);
 419         }
 420     }
 421
 422   if (nuseless_productions > 0)
 423     {
 424       fprintf (out, "\n\n");
 425       fprintf (out, _("Useless rules:"));
 426       fprintf (out, "\n\n");
 427       for (i = 1; i <= nrules; i++)
 428         if (!BITISSET (P, i))
 429           {
 430             fprintf (out, "#%-4d  ", i);
 431             fprintf (out, "%s :\t", tags[rule_table[i].lhs]);
 432             for (r = &ritem[rule_table[i].rhs]; *r >= 0; r++)
 433               fprintf (out, " %s", tags[*r]);
 434             fprintf (out, ";\n");
 435           }
 436     }
 437   if (nuseless_nonterminals > 0 || nuseless_productions > 0 || b)
 438     fprintf (out, "\n\n");
 439 }
 440 \f
 441 #if TRACE
 442 static void
 443 dump_grammar (FILE *out)
 444 {
 445   int i;
 446   rule r;
 447
 448   fprintf (out, "REDUCED GRAMMAR\n\n");
 449   fprintf (out,
 450          "ntokens = %d, nvars = %d, nsyms = %d, nrules = %d, nitems = %d\n\n",
 451          ntokens, nvars, nsyms, nrules, nitems);
 452   fprintf (out, _("Variables\n---------\n\n"));
 453   fprintf (out, _("Value  Sprec    Sassoc    Tag\n"));
 454   for (i = ntokens; i < nsyms; i++)
 455     fprintf (out, "%5d  %5d  %5d  %s\n", i, sprec[i], sassoc[i], tags[i]);
 456   fprintf (out, "\n\n");
 457   fprintf (out, _("Rules\n-----\n\n"));
 458   for (i = 1; i <= nrules; i++)
 459     {
 460       fprintf (out, "%-5d(%5d%5d)%5d : (@%-5d)",
 461                i,
 462                rule_table[i].prec,
 463                rule_table[i].assoc,
 464                rule_table[i].lhs,
 465                rule_table[i].rhs);
 466       for (r = &ritem[rule_table[i].rhs]; *r > 0; r++)
 467         fprintf (out, "%5d", *r);
 468       fprintf (out, " [%d]\n", -(*r));
 469     }
 470   fprintf (out, "\n\n");
 471   fprintf (out, _("Rules interpreted\n-----------------\n\n"));
 472   for (i = 1; i <= nrules; i++)
 473     {
 474       fprintf (out, "%-5d  %s :", i, tags[rule_table[i].lhs]);
 475       for (r = &ritem[rule_table[i].rhs]; *r > 0; r++)
 476         fprintf (out, " %s", tags[*r]);
 477       fputc ('\n', out);
 478     }
 479   fprintf (out, "\n\n");
 480 }
 481 #endif
 482
 483
 484
 485 /*-------------------------------.
 486 | Report the results to STDERR.  |
 487 `-------------------------------*/
 488
 489 static void
 490 reduce_print (void)
 491 {
 492   if (yacc_flag && nuseless_productions)
 493     fprintf (stderr, _("%d rules never reduced\n"), nuseless_productions);
 494
 495   fprintf (stderr, _("%s contains "), infile);
 496
 497   if (nuseless_nonterminals > 0)
 498     {
 499       fprintf (stderr, _("%d useless nonterminal%s"),
 500                nuseless_nonterminals,
 501                (nuseless_nonterminals == 1 ? "" : "s"));
 502     }
 503   if (nuseless_nonterminals > 0 && nuseless_productions > 0)
 504     fprintf (stderr, _(" and "));
 505
 506   if (nuseless_productions > 0)
 507     {
 508       fprintf (stderr, _("%d useless rule%s"),
 509                nuseless_productions, (nuseless_productions == 1 ? "" : "s"));
 510     }
 511   fprintf (stderr, "\n");
 512   fflush (stderr);
 513 }
 514 \f
 515 void
 516 reduce_grammar (void)
 517 {
 518   bool reduced;
 519
 520   /* Allocate the global sets used to compute the reduced grammar */
 521
 522   N = XCALLOC (unsigned, WORDSIZE (nvars));
 523   P = XCALLOC (unsigned, WORDSIZE (nrules + 1));
 524   V = XCALLOC (unsigned, WORDSIZE (nsyms));
 525   V1 = XCALLOC (unsigned, WORDSIZE (nsyms));
 526
 527   useless_nonterminals ();
 528   inaccessable_symbols ();
 529
 530   reduced = (bool) (nuseless_nonterminals + nuseless_productions > 0);
 531
 532   if (!reduced)
 533     return;
 534
 535   reduce_print ();
 536
 537   if (!BITISSET (N, start_symbol - ntokens))
 538     fatal (_("Start symbol %s does not derive any sentence"),
 539            tags[start_symbol]);
 540
 541   reduce_grammar_tables ();
 542 #if TRACE
 543   dump_grammar (stderr);
 544 #endif
 545
 546   if (statistics_flag)
 547     fprintf (stderr, _("reduced %s defines %d terminal%s, %d nonterminal%s\
 548 , and %d production%s.\n"),
 549              infile,
 550              ntokens,
 551              (ntokens == 1 ? "" : "s"),
 552              nvars,
 553              (nvars == 1 ? "" : "s"),
 554              nrules,
 555              (nrules == 1 ? "" : "s"));
 556 }
 557
 558
 559 /*-----------------------------------------------------------.
 560 | Free the global sets used to compute the reduced grammar.  |
 561 `-----------------------------------------------------------*/
 562
 563 void
 564 reduce_free (void)
 565 {
 566   XFREE (N);
 567   XFREE (V);
 568   XFREE (V1);
 569   XFREE (P);
 570 }