]> git.saurik.com Git - bison.git/blame - src/reduce.c
* data/bison.simple (yyr1): Its type is that of a token number.
[bison.git] / src / reduce.c
CommitLineData
572909b5 1/* Grammar reduction for Bison.
8b3df748 2 Copyright (C) 1988, 1989, 2000, 2001, 2002 Free Software Foundation, Inc.
572909b5 3
015acc48 4 This file is part of Bison, the GNU Compiler Compiler.
572909b5 5
015acc48
AD
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.
572909b5 10
015acc48
AD
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.
572909b5 15
015acc48
AD
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. */
572909b5
RS
20
21
015acc48
AD
22/* Reduce the grammar: Find and eliminate unreachable terminals,
23 nonterminals, and productions. David S. Bakin. */
572909b5 24
015acc48
AD
25/* Don't eliminate unreachable terminals: They may be used by the
26 user's parser. */
572909b5 27
572909b5 28#include "system.h"
8b3df748 29#include "quotearg.h"
ceed8467 30#include "getargs.h"
572909b5 31#include "files.h"
0e78e603 32#include "symtab.h"
572909b5 33#include "gram.h"
a0f6b076 34#include "complain.h"
015acc48 35#include "reduce.h"
b2ca4022
AD
36#include "reader.h"
37#include "getargs.h"
ed86e78c 38#include "bitset.h"
572909b5 39
00238958 40/* Set of all nonterminals which are not useless. */
ed86e78c 41static bitset N;
572909b5 42
00238958 43/* Set of all rules which have no useless nonterminals in their RHS. */
ed86e78c 44static bitset P;
00238958
AD
45
46/* Set of all accessible symbols. */
ed86e78c 47static bitset V;
00238958
AD
48
49/* Set of symbols used to define rule precedence (so they are
50 `useless', but no warning should be issued). */
ed86e78c 51static bitset V1;
572909b5 52
015acc48
AD
53static int nuseful_productions;
54static int nuseless_productions;
55static int nuseful_nonterminals;
630e182b 56int nuseless_nonterminals;
572909b5 57\f
015acc48
AD
58/*-------------------------------------------------------------------.
59| Another way to do this would be with a set for each production and |
60| then do subset tests against N0, but even for the C grammar the |
61| whole reducing process takes only 2 seconds on my 8Mhz AT. |
62`-------------------------------------------------------------------*/
572909b5 63
a083fbbf 64static bool
ed86e78c 65useful_production (int i, bitset N0)
572909b5 66{
62a3e4f0 67 item_number_t *r;
572909b5
RS
68 short n;
69
015acc48
AD
70 /* A production is useful if all of the nonterminals in its appear
71 in the set of useful nonterminals. */
572909b5 72
99013900 73 for (r = rules[i].rhs; *r >= 0; r++)
914feea9
AD
74 if (ISVAR (n = *r) && !bitset_test (N0, n - ntokens))
75 return FALSE;
572909b5
RS
76 return TRUE;
77}
78
79
015acc48
AD
80/*---------------------------------------------------------.
81| Remember that rules are 1-origin, symbols are 0-origin. |
82`---------------------------------------------------------*/
572909b5 83
a083fbbf 84static void
d2729d44 85useless_nonterminals (void)
572909b5 86{
ed86e78c 87 bitset Np, Ns;
342b8b6e 88 int i;
015acc48
AD
89
90 /* N is set as built. Np is set being built this iteration. P is
91 set of all productions which have a RHS all in N. */
92
ed86e78c 93 Np = bitset_create (nvars, BITSET_FIXED);
ed86e78c 94
015acc48
AD
95
96 /* The set being computed is a set of nonterminals which can derive
97 the empty string or strings consisting of all terminals. At each
98 iteration a nonterminal is added to the set if there is a
99 production with that nonterminal as its LHS for which all the
100 nonterminals in its RHS are already in the set. Iterate until
101 the set being computed remains unchanged. Any nonterminals not
102 in the set at that point are useless in that they will never be
103 used in deriving a sentence of the language.
104
105 This iteration doesn't use any special traversal over the
106 productions. A set is kept of all productions for which all the
107 nonterminals in the RHS are in useful. Only productions not in
108 this set are scanned on each iteration. At the end, this set is
109 saved to be used when finding useful productions: only
110 productions in this set will appear in the final grammar. */
572909b5 111
572909b5
RS
112 while (1)
113 {
ed86e78c 114 bitset_copy (Np, N);
18bcecb0 115 for (i = 1; i < nrules + 1; i++)
f9abaa2c
AD
116 if (!bitset_test (P, i)
117 && useful_production (i, N))
118 {
bba97eb2 119 bitset_set (Np, rules[i].lhs->number - ntokens);
f9abaa2c
AD
120 bitset_set (P, i);
121 }
ed86e78c 122 if (bitset_equal_p (N, Np))
572909b5
RS
123 break;
124 Ns = Np;
125 Np = N;
126 N = Ns;
127 }
ed86e78c 128 bitset_free (N);
572909b5
RS
129 N = Np;
130}
015acc48
AD
131
132
a083fbbf 133static void
d2729d44 134inaccessable_symbols (void)
572909b5 135{
ed86e78c 136 bitset Vp, Vs, Pp;
342b8b6e 137 int i;
572909b5 138 short t;
62a3e4f0 139 item_number_t *r;
015acc48
AD
140
141 /* Find out which productions are reachable and which symbols are
142 used. Starting with an empty set of productions and a set of
143 symbols which only has the start symbol in it, iterate over all
144 productions until the set of productions remains unchanged for an
145 iteration. For each production which has a LHS in the set of
146 reachable symbols, add the production to the set of reachable
147 productions, and add all of the nonterminals in the RHS of the
148 production to the set of reachable symbols.
149
150 Consider only the (partially) reduced grammar which has only
151 nonterminals in N and productions in P.
152
153 The result is the set P of productions in the reduced grammar,
154 and the set V of symbols in the reduced grammar.
155
156 Although this algorithm also computes the set of terminals which
157 are reachable, no terminal will be deleted from the grammar. Some
158 terminals might not be in the grammar but might be generated by
159 semantic routines, and so the user might want them available with
160 specified numbers. (Is this true?) However, the nonreachable
161 terminals are printed (if running in verbose mode) so that the
162 user can know. */
163
ed86e78c 164 Vp = bitset_create (nsyms, BITSET_FIXED);
ed86e78c 165 Pp = bitset_create (nrules + 1, BITSET_FIXED);
572909b5
RS
166
167 /* If the start symbol isn't useful, then nothing will be useful. */
ed86e78c 168 if (bitset_test (N, start_symbol - ntokens))
572909b5 169 {
ed86e78c 170 bitset_set (V, start_symbol);
2c5f66ed
AD
171
172 while (1)
572909b5 173 {
ed86e78c 174 bitset_copy (Vp, V);
18bcecb0 175 for (i = 1; i < nrules + 1; i++)
572909b5 176 {
ed86e78c
AD
177 if (!bitset_test (Pp, i)
178 && bitset_test (P, i)
bba97eb2 179 && bitset_test (V, rules[i].lhs->number))
572909b5 180 {
99013900 181 for (r = rules[i].rhs; *r >= 0; r++)
ed86e78c
AD
182 if (ISTOKEN (t = *r) || bitset_test (N, t - ntokens))
183 bitset_set (Vp, t);
184 bitset_set (Pp, i);
572909b5 185 }
572909b5 186 }
ed86e78c 187 if (bitset_equal_p (V, Vp))
2c5f66ed
AD
188 break;
189 Vs = Vp;
190 Vp = V;
191 V = Vs;
572909b5 192 }
572909b5 193 }
572909b5 194
ed86e78c 195 bitset_free (V);
572909b5
RS
196 V = Vp;
197
198 /* Tokens 0, 1, and 2 are internal to Bison. Consider them useful. */
72a23c97
AD
199 bitset_set (V, eoftoken->number); /* end-of-input token */
200 bitset_set (V, errtoken->number); /* error token */
201 bitset_set (V, undeftoken->number); /* some undefined token */
572909b5 202
ed86e78c 203 bitset_free (P);
572909b5
RS
204 P = Pp;
205
914feea9 206 nuseful_productions = bitset_count (P);
572909b5
RS
207 nuseless_productions = nrules - nuseful_productions;
208
209 nuseful_nonterminals = 0;
210 for (i = ntokens; i < nsyms; i++)
ed86e78c 211 if (bitset_test (V, i))
572909b5
RS
212 nuseful_nonterminals++;
213 nuseless_nonterminals = nvars - nuseful_nonterminals;
214
215 /* A token that was used in %prec should not be warned about. */
11652ab3 216 for (i = 1; i < nrules + 1; i++)
1a2b5d37 217 if (rules[i].precsym != 0)
03b31c0c 218 bitset_set (V1, rules[i].precsym->number);
572909b5 219}
015acc48 220
c3b407f4
AD
221
222/*-------------------------------------------------------------------.
223| Put the useless productions at the end of RULES, and adjust NRULES |
224| accordingly. |
225`-------------------------------------------------------------------*/
226
a083fbbf 227static void
d2729d44 228reduce_grammar_tables (void)
572909b5 229{
c3b407f4
AD
230 /* Flag useless productions. */
231 {
232 int pn;
233 for (pn = 1; pn < nrules + 1; pn++)
234 rules[pn].useful = bitset_test (P, pn);
235 }
572909b5 236
c3b407f4
AD
237 /* Map the nonterminals to their new index: useful first, useless
238 afterwards. Kept for later report. */
239 {
240 int useful = 1;
241 int useless = nrules + 1 - nuseless_productions;
242 rule_t *rules_sorted = XMALLOC (rule_t, nrules + 1) - 1;
243 int i;
244 for (i = 1; i < nrules + 1; ++i)
245 rules_sorted[rules[i].useful ? useful++ : useless++] = rules[i];
246 free (rules + 1);
247 rules = rules_sorted;
076ab033 248
cc9305dd
AD
249 /* Renumber the rules markers in RITEMS. */
250 for (i = 1; i < nrules + 1; ++i)
251 {
62a3e4f0 252 item_number_t *rhsp = rules[i].rhs;
cc9305dd
AD
253 for (/* Nothing. */; *rhsp >= 0; ++rhsp)
254 /* Nothing. */;
255 *rhsp = -i;
d7e1f00c 256 rules[i].number = i;
cc9305dd 257 }
c3b407f4
AD
258 nrules -= nuseless_productions;
259 }
076ab033 260
c3b407f4
AD
261 /* Adjust NRITEMS and NITEMS. */
262 {
263 int r;
264 int length;
265 for (r = nrules + 1; r < nrules + 1 + nuseless_productions; ++r)
076ab033 266 {
c3b407f4
AD
267 length = rule_rhs_length (&rules[r]);
268 nritems -= length + 1;
076ab033 269 }
c3b407f4 270 }
00238958 271}
572909b5 272
572909b5 273
00238958
AD
274/*------------------------------.
275| Remove useless nonterminals. |
276`------------------------------*/
572909b5 277
00238958
AD
278static void
279nonterminals_reduce (void)
280{
5fbb0954 281 token_number_t i, n;
572909b5 282
68f1e3ed
AD
283 /* Map the nonterminals to their new index: useful first, useless
284 afterwards. Kept for later report. */
572909b5 285
5fbb0954 286 token_number_t *nontermmap = XCALLOC (token_number_t, nvars) - ntokens;
00238958
AD
287 n = ntokens;
288 for (i = ntokens; i < nsyms; i++)
ed86e78c 289 if (bitset_test (V, i))
00238958 290 nontermmap[i] = n++;
760b53a8 291 for (i = ntokens; i < nsyms; i++)
ed86e78c 292 if (!bitset_test (V, i))
760b53a8 293 nontermmap[i] = n++;
572909b5 294
00238958 295
760b53a8
AD
296 /* Shuffle elements of tables indexed by symbol number. */
297 {
db8837cb 298 symbol_t **symbols_sorted = XMALLOC (symbol_t *, nvars) - ntokens;
760b53a8 299
bba97eb2
AD
300 for (i = ntokens; i < nsyms; i++)
301 symbols[i]->number = nontermmap[i];
760b53a8 302 for (i = ntokens; i < nsyms; i++)
0e78e603 303 symbols_sorted[nontermmap[i]] = symbols[i];
760b53a8 304 for (i = ntokens; i < nsyms; i++)
0e78e603
AD
305 symbols[i] = symbols_sorted[i];
306 free (symbols_sorted + ntokens);
760b53a8 307 }
572909b5 308
9e7f6bbd
AD
309 for (i = 0; i < nritems; ++i)
310 if (ISVAR (ritem[i]))
5fbb0954 311 ritem[i] = token_number_as_item_number (nontermmap[ritem[i]]);
572909b5 312
00238958 313 start_symbol = nontermmap[start_symbol];
572909b5 314
00238958
AD
315 nsyms -= nuseless_nonterminals;
316 nvars -= nuseless_nonterminals;
572909b5 317
68f1e3ed 318 free (nontermmap + ntokens);
572909b5 319}
015acc48 320
337c5bd1 321
00238958
AD
322/*------------------------------------------------------------------.
323| Output the detailed results of the reductions. For FILE.output. |
324`------------------------------------------------------------------*/
337c5bd1
AD
325
326void
327reduce_output (FILE *out)
572909b5 328{
572909b5
RS
329 if (nuseless_nonterminals > 0)
330 {
d2d1b42b
AD
331 int i;
332 fprintf (out, "%s\n\n", _("Useless nonterminals:"));
760b53a8 333 for (i = 0; i < nuseless_nonterminals; ++i)
8b3df748
AD
334 fprintf (out, " %s\n", quotearg_style (escape_quoting_style,
335 symbols[nsyms + i]->tag));
d2d1b42b 336 fputs ("\n\n", out);
572909b5 337 }
d2d1b42b
AD
338
339 {
340 bool b = FALSE;
341 int i;
342 for (i = 0; i < ntokens; i++)
ed86e78c 343 if (!bitset_test (V, i) && !bitset_test (V1, i))
572909b5
RS
344 {
345 if (!b)
d2d1b42b
AD
346 fprintf (out, "%s\n\n", _("Terminals which are not used:"));
347 b = TRUE;
8b3df748
AD
348 fprintf (out, " %s\n", quotearg_style (escape_quoting_style,
349 symbols[i]->tag));
572909b5 350 }
d2d1b42b
AD
351 if (b)
352 fputs ("\n\n", out);
353 }
572909b5
RS
354
355 if (nuseless_productions > 0)
356 {
d2d1b42b
AD
357 int i;
358 fprintf (out, "%s\n\n", _("Useless rules:"));
c3b407f4
AD
359 for (i = nrules + 1; i < nuseless_productions + nrules + 1; i++)
360 {
62a3e4f0 361 item_number_t *r;
d7e1f00c 362 fprintf (out, "#%-4d ", rules[i].user_number - 1);
8b3df748
AD
363 fprintf (out, "%s:", quotearg_style (escape_quoting_style,
364 rules[i].lhs->tag));
c3b407f4 365 for (r = rules[i].rhs; *r >= 0; r++)
8b3df748
AD
366 fprintf (out, " %s", quotearg_style (escape_quoting_style,
367 symbols[*r]->tag));
c3b407f4
AD
368 fputs (";\n", out);
369 }
d2d1b42b 370 fputs ("\n\n", out);
572909b5 371 }
572909b5
RS
372}
373\f
4a120d45 374static void
337c5bd1 375dump_grammar (FILE *out)
572909b5
RS
376{
377 int i;
62a3e4f0 378 item_number_t *r;
572909b5 379
2c5f66ed 380 fprintf (out, "REDUCED GRAMMAR\n\n");
337c5bd1 381 fprintf (out,
5123689b
AD
382 "ntokens = %d, nvars = %d, nsyms = %d, nrules = %d, nritems = %d\n\n",
383 ntokens, nvars, nsyms, nrules, nritems);
6013d43f 384 fprintf (out, "Variables\n---------\n\n");
cb487d7d 385 fprintf (out, "Value Sprec Sassoc Tag\n");
572909b5 386 for (i = ntokens; i < nsyms; i++)
0e78e603
AD
387 fprintf (out, "%5d %5d %5d %s\n",
388 i,
8b3df748
AD
389 symbols[i]->prec, symbols[i]->assoc,
390 quotearg_style (escape_quoting_style, symbols[i]->tag));
337c5bd1 391 fprintf (out, "\n\n");
6013d43f 392 fprintf (out, "Rules\n-----\n\n");
3067fbef 393 fprintf (out, "Num (Prec, Assoc, Useful, Ritem Range) Lhs -> Rhs (Ritem range) [Num]\n");
c3b407f4 394 for (i = 1; i < nrules + nuseless_productions + 1; i++)
572909b5 395 {
3067fbef
AD
396 int rhs_count = 0;
397 /* Find the last RHS index in ritems. */
99013900 398 for (r = rules[i].rhs; *r >= 0; ++r)
3067fbef
AD
399 ++rhs_count;
400 fprintf (out, "%3d (%2d, %2d, %2d, %2d-%2d) %2d ->",
3d4daee3 401 i - 1,
03b31c0c
AD
402 rules[i].prec->prec,
403 rules[i].prec->assoc,
404 rules[i].useful,
405 rules[i].rhs - ritem,
406 rules[i].rhs - ritem + rhs_count - 1,
bba97eb2 407 rules[i].lhs->number);
3067fbef 408 /* Dumped the RHS. */
99013900 409 for (r = rules[i].rhs; *r >= 0; r++)
3067fbef 410 fprintf (out, "%3d", *r);
3d4daee3 411 fprintf (out, " [%d]\n", -(*r) - 1);
572909b5 412 }
337c5bd1 413 fprintf (out, "\n\n");
6013d43f 414 fprintf (out, "Rules interpreted\n-----------------\n\n");
c3b407f4 415 for (i = 1; i < nrules + nuseless_productions + 1; i++)
572909b5 416 {
8b3df748
AD
417 fprintf (out, "%-5d %s :",
418 i, quotearg_style (escape_quoting_style, rules[i].lhs->tag));
99013900 419 for (r = rules[i].rhs; *r >= 0; r++)
8b3df748
AD
420 fprintf (out, " %s",
421 quotearg_style (escape_quoting_style, symbols[*r]->tag));
337c5bd1 422 fputc ('\n', out);
572909b5 423 }
337c5bd1 424 fprintf (out, "\n\n");
572909b5
RS
425}
426
427
337c5bd1
AD
428
429/*-------------------------------.
430| Report the results to STDERR. |
431`-------------------------------*/
432
a083fbbf 433static void
337c5bd1 434reduce_print (void)
572909b5 435{
89cab50d 436 if (yacc_flag && nuseless_productions)
cb487d7d
AD
437 fprintf (stderr, ngettext ("%d rule never reduced\n",
438 "%d rules never reduced\n",
439 nuseless_productions),
440 nuseless_productions);
572909b5 441
015acc48 442 fprintf (stderr, _("%s contains "), infile);
572909b5
RS
443
444 if (nuseless_nonterminals > 0)
cb487d7d
AD
445 fprintf (stderr, ngettext ("%d useless nonterminal",
446 "%d useless nonterminals",
447 nuseless_nonterminals),
448 nuseless_nonterminals);
449
572909b5 450 if (nuseless_nonterminals > 0 && nuseless_productions > 0)
015acc48 451 fprintf (stderr, _(" and "));
572909b5
RS
452
453 if (nuseless_productions > 0)
cb487d7d
AD
454 fprintf (stderr, ngettext ("%d useless rule",
455 "%d useless rules",
456 nuseless_productions),
457 nuseless_productions);
015acc48
AD
458 fprintf (stderr, "\n");
459 fflush (stderr);
460}
461\f
462void
463reduce_grammar (void)
464{
465 bool reduced;
466
467 /* Allocate the global sets used to compute the reduced grammar */
468
ed86e78c 469 N = bitset_create (nvars, BITSET_FIXED);
ed86e78c 470 P = bitset_create (nrules + 1, BITSET_FIXED);
ed86e78c 471 V = bitset_create (nsyms, BITSET_FIXED);
ed86e78c 472 V1 = bitset_create (nsyms, BITSET_FIXED);
015acc48
AD
473
474 useless_nonterminals ();
475 inaccessable_symbols ();
476
477 reduced = (bool) (nuseless_nonterminals + nuseless_productions > 0);
337c5bd1
AD
478 if (!reduced)
479 return;
015acc48 480
337c5bd1 481 reduce_print ();
015acc48 482
ed86e78c 483 if (!bitset_test (N, start_symbol - ntokens))
015acc48 484 fatal (_("Start symbol %s does not derive any sentence"),
8b3df748 485 quotearg_style (escape_quoting_style, symbols[start_symbol]->tag));
015acc48 486
bb88b0fc
AD
487 /* First reduce the nonterminals, as they renumber themselves in the
488 whole grammar. If you change the order, nonterms would be
489 renumbered only in the reduced grammar. */
00238958
AD
490 if (nuseless_nonterminals > 0)
491 nonterminals_reduce ();
bb88b0fc
AD
492 if (nuseless_productions > 0)
493 reduce_grammar_tables ();
9bfe901c
AD
494
495 if (trace_flag)
496 {
497 dump_grammar (stderr);
498
499 fprintf (stderr, "reduced %s defines %d terminals, %d nonterminals\
500, and %d productions.\n",
501 infile, ntokens, nvars, nrules);
502 }
337c5bd1 503}
015acc48 504
015acc48 505
337c5bd1
AD
506/*-----------------------------------------------------------.
507| Free the global sets used to compute the reduced grammar. |
508`-----------------------------------------------------------*/
509
510void
511reduce_free (void)
512{
ed86e78c
AD
513 bitset_free (N);
514 bitset_free (V);
515 bitset_free (V1);
516 bitset_free (P);
572909b5 517}