maint: update gnu-web-doc-update.
[bison.git] / src / reduce.c
CommitLineData
572909b5 1/* Grammar reduction for Bison.
c4882934 2
c932d613 3 Copyright (C) 1988-1989, 2000-2003, 2005-2012 Free Software
ea0a7676 4 Foundation, Inc.
572909b5 5
015acc48 6 This file is part of Bison, the GNU Compiler Compiler.
572909b5 7
f16b0819 8 This program is free software: you can redistribute it and/or modify
015acc48 9 it under the terms of the GNU General Public License as published by
f16b0819
PE
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
572909b5 12
f16b0819 13 This program is distributed in the hope that it will be useful,
015acc48
AD
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
572909b5 17
015acc48 18 You should have received a copy of the GNU General Public License
f16b0819 19 along with this program. If not, see <http://www.gnu.org/licenses/>. */
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
2cec9080 28#include <config.h>
572909b5 29#include "system.h"
17ee7397
PE
30
31#include <bitset.h>
17ee7397
PE
32
33#include "complain.h"
572909b5 34#include "files.h"
17ee7397 35#include "getargs.h"
572909b5 36#include "gram.h"
41d7a5f2 37#include "print-xml.h"
b2ca4022 38#include "reader.h"
17ee7397
PE
39#include "reduce.h"
40#include "symtab.h"
572909b5 41
00238958 42/* Set of all nonterminals which are not useless. */
ed86e78c 43static bitset N;
572909b5 44
00238958 45/* Set of all rules which have no useless nonterminals in their RHS. */
ed86e78c 46static bitset P;
00238958
AD
47
48/* Set of all accessible symbols. */
ed86e78c 49static bitset V;
00238958
AD
50
51/* Set of symbols used to define rule precedence (so they are
52 `useless', but no warning should be issued). */
ed86e78c 53static bitset V1;
572909b5 54
17ee7397
PE
55static rule_number nuseful_productions;
56rule_number nuseless_productions;
015acc48 57static int nuseful_nonterminals;
17ee7397 58symbol_number nuseless_nonterminals;
572909b5 59\f
015acc48
AD
60/*-------------------------------------------------------------------.
61| Another way to do this would be with a set for each production and |
62| then do subset tests against N0, but even for the C grammar the |
63| whole reducing process takes only 2 seconds on my 8Mhz AT. |
64`-------------------------------------------------------------------*/
572909b5 65
a083fbbf 66static bool
17ee7397 67useful_production (rule_number r, bitset N0)
572909b5 68{
17ee7397 69 item_number *rhsp;
572909b5 70
015acc48
AD
71 /* A production is useful if all of the nonterminals in its appear
72 in the set of useful nonterminals. */
572909b5 73
9222837b
AD
74 for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
75 if (ISVAR (*rhsp) && !bitset_test (N0, *rhsp - ntokens))
8307162d
PE
76 return false;
77 return true;
572909b5
RS
78}
79
80
015acc48
AD
81/*---------------------------------------------------------.
82| Remember that rules are 1-origin, symbols are 0-origin. |
83`---------------------------------------------------------*/
572909b5 84
a083fbbf 85static void
d2729d44 86useless_nonterminals (void)
572909b5 87{
ed86e78c 88 bitset Np, Ns;
17ee7397 89 rule_number r;
015acc48
AD
90
91 /* N is set as built. Np is set being built this iteration. P is
92 set of all productions which have a RHS all in N. */
93
ed86e78c 94 Np = bitset_create (nvars, BITSET_FIXED);
ed86e78c 95
015acc48
AD
96
97 /* The set being computed is a set of nonterminals which can derive
98 the empty string or strings consisting of all terminals. At each
99 iteration a nonterminal is added to the set if there is a
100 production with that nonterminal as its LHS for which all the
101 nonterminals in its RHS are already in the set. Iterate until
102 the set being computed remains unchanged. Any nonterminals not
103 in the set at that point are useless in that they will never be
104 used in deriving a sentence of the language.
105
106 This iteration doesn't use any special traversal over the
107 productions. A set is kept of all productions for which all the
108 nonterminals in the RHS are in useful. Only productions not in
109 this set are scanned on each iteration. At the end, this set is
110 saved to be used when finding useful productions: only
111 productions in this set will appear in the final grammar. */
572909b5 112
572909b5
RS
113 while (1)
114 {
ed86e78c 115 bitset_copy (Np, N);
4b3d3a8e 116 for (r = 0; r < nrules; r++)
9222837b
AD
117 if (!bitset_test (P, r)
118 && useful_production (r, N))
f9abaa2c 119 {
9222837b
AD
120 bitset_set (Np, rules[r].lhs->number - ntokens);
121 bitset_set (P, r);
f9abaa2c 122 }
ed86e78c 123 if (bitset_equal_p (N, Np))
572909b5
RS
124 break;
125 Ns = Np;
126 Np = N;
127 N = Ns;
128 }
ed86e78c 129 bitset_free (N);
572909b5
RS
130 N = Np;
131}
015acc48
AD
132
133
a083fbbf 134static void
d2729d44 135inaccessable_symbols (void)
572909b5 136{
ed86e78c 137 bitset Vp, Vs, Pp;
015acc48
AD
138
139 /* Find out which productions are reachable and which symbols are
140 used. Starting with an empty set of productions and a set of
141 symbols which only has the start symbol in it, iterate over all
142 productions until the set of productions remains unchanged for an
143 iteration. For each production which has a LHS in the set of
144 reachable symbols, add the production to the set of reachable
145 productions, and add all of the nonterminals in the RHS of the
146 production to the set of reachable symbols.
147
148 Consider only the (partially) reduced grammar which has only
149 nonterminals in N and productions in P.
150
151 The result is the set P of productions in the reduced grammar,
152 and the set V of symbols in the reduced grammar.
153
154 Although this algorithm also computes the set of terminals which
155 are reachable, no terminal will be deleted from the grammar. Some
156 terminals might not be in the grammar but might be generated by
157 semantic routines, and so the user might want them available with
158 specified numbers. (Is this true?) However, the nonreachable
159 terminals are printed (if running in verbose mode) so that the
160 user can know. */
161
ed86e78c 162 Vp = bitset_create (nsyms, BITSET_FIXED);
4b3d3a8e 163 Pp = bitset_create (nrules, BITSET_FIXED);
572909b5
RS
164
165 /* If the start symbol isn't useful, then nothing will be useful. */
88bce5a2 166 if (bitset_test (N, accept->number - ntokens))
572909b5 167 {
88bce5a2 168 bitset_set (V, accept->number);
2c5f66ed
AD
169
170 while (1)
572909b5 171 {
17ee7397 172 rule_number r;
ed86e78c 173 bitset_copy (Vp, V);
4b3d3a8e 174 for (r = 0; r < nrules; r++)
572909b5 175 {
9222837b
AD
176 if (!bitset_test (Pp, r)
177 && bitset_test (P, r)
178 && bitset_test (V, rules[r].lhs->number))
572909b5 179 {
17ee7397 180 item_number *rhsp;
9222837b
AD
181 for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
182 if (ISTOKEN (*rhsp) || bitset_test (N, *rhsp - ntokens))
183 bitset_set (Vp, *rhsp);
184 bitset_set (Pp, r);
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. */
88bce5a2 199 bitset_set (V, endtoken->number); /* end-of-input token */
72a23c97
AD
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;
9222837b 210 {
17ee7397 211 symbol_number i;
9222837b
AD
212 for (i = ntokens; i < nsyms; i++)
213 if (bitset_test (V, i))
214 nuseful_nonterminals++;
215 }
572909b5
RS
216 nuseless_nonterminals = nvars - nuseful_nonterminals;
217
218 /* A token that was used in %prec should not be warned about. */
9222837b 219 {
17ee7397 220 rule_number r;
4b3d3a8e
AD
221 for (r = 0; r < nrules; ++r)
222 if (rules[r].precsym != 0)
223 bitset_set (V1, rules[r].precsym->number);
9222837b 224 }
572909b5 225}
015acc48 226
c3b407f4
AD
227
228/*-------------------------------------------------------------------.
229| Put the useless productions at the end of RULES, and adjust NRULES |
230| accordingly. |
231`-------------------------------------------------------------------*/
232
a083fbbf 233static void
d2729d44 234reduce_grammar_tables (void)
572909b5 235{
6b98e4b5 236 /* Report and flag useless productions. */
c3b407f4 237 {
17ee7397 238 rule_number r;
4b3d3a8e 239 for (r = 0; r < nrules; r++)
c8f002c7 240 rules[r].useful = bitset_test (P, r);
cff03fb2 241 grammar_rules_useless_report (_("rule useless in grammar"));
c3b407f4 242 }
572909b5 243
c3b407f4
AD
244 /* Map the nonterminals to their new index: useful first, useless
245 afterwards. Kept for later report. */
246 {
4b3d3a8e
AD
247 int useful = 0;
248 int useless = nrules - nuseless_productions;
da2a7671 249 rule *rules_sorted = xnmalloc (nrules, sizeof *rules_sorted);
17ee7397 250 rule_number r;
4b3d3a8e 251 for (r = 0; r < nrules; ++r)
9222837b 252 rules_sorted[rules[r].useful ? useful++ : useless++] = rules[r];
4b3d3a8e 253 free (rules);
c3b407f4 254 rules = rules_sorted;
076ab033 255
cc9305dd 256 /* Renumber the rules markers in RITEMS. */
4b3d3a8e 257 for (r = 0; r < nrules; ++r)
cc9305dd 258 {
17ee7397 259 item_number *rhsp = rules[r].rhs;
cc9305dd
AD
260 for (/* Nothing. */; *rhsp >= 0; ++rhsp)
261 /* Nothing. */;
12b0043a 262 *rhsp = rule_number_as_item_number (r);
9222837b 263 rules[r].number = r;
cc9305dd 264 }
c3b407f4
AD
265 nrules -= nuseless_productions;
266 }
076ab033 267
a900a624 268 /* Adjust NRITEMS. */
c3b407f4 269 {
a737b216 270 rule_number r;
c3b407f4 271 int length;
4b3d3a8e 272 for (r = nrules; r < nrules + nuseless_productions; ++r)
076ab033 273 {
c3b407f4
AD
274 length = rule_rhs_length (&rules[r]);
275 nritems -= length + 1;
076ab033 276 }
c3b407f4 277 }
00238958 278}
572909b5 279
572909b5 280
00238958
AD
281/*------------------------------.
282| Remove useless nonterminals. |
283`------------------------------*/
572909b5 284
00238958
AD
285static void
286nonterminals_reduce (void)
287{
17ee7397 288 symbol_number i, n;
572909b5 289
68f1e3ed
AD
290 /* Map the nonterminals to their new index: useful first, useless
291 afterwards. Kept for later report. */
572909b5 292
da2a7671 293 symbol_number *nontermmap = xnmalloc (nvars, sizeof *nontermmap);
00238958
AD
294 n = ntokens;
295 for (i = ntokens; i < nsyms; i++)
ed86e78c 296 if (bitset_test (V, i))
c4882934 297 nontermmap[i - ntokens] = n++;
760b53a8 298 for (i = ntokens; i < nsyms; i++)
ed86e78c 299 if (!bitset_test (V, i))
6b98e4b5 300 {
c4882934 301 nontermmap[i - ntokens] = n++;
cff03fb2 302 warn_at (symbols[i]->location, _("nonterminal useless in grammar: %s"),
97650f4e 303 symbols[i]->tag);
6b98e4b5 304 }
572909b5 305
00238958 306
760b53a8
AD
307 /* Shuffle elements of tables indexed by symbol number. */
308 {
da2a7671 309 symbol **symbols_sorted = xnmalloc (nvars, sizeof *symbols_sorted);
760b53a8 310
bba97eb2 311 for (i = ntokens; i < nsyms; i++)
c4882934 312 symbols[i]->number = nontermmap[i - ntokens];
760b53a8 313 for (i = ntokens; i < nsyms; i++)
c4882934 314 symbols_sorted[nontermmap[i - ntokens] - ntokens] = symbols[i];
760b53a8 315 for (i = ntokens; i < nsyms; i++)
c4882934
PE
316 symbols[i] = symbols_sorted[i - ntokens];
317 free (symbols_sorted);
760b53a8 318 }
572909b5 319
0c2d3f4c 320 {
17ee7397 321 rule_number r;
4b3d3a8e 322 for (r = 0; r < nrules; ++r)
0c2d3f4c 323 {
17ee7397 324 item_number *rhsp;
0c2d3f4c
AD
325 for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
326 if (ISVAR (*rhsp))
c4882934
PE
327 *rhsp = symbol_number_as_item_number (nontermmap[*rhsp
328 - ntokens]);
0c2d3f4c 329 }
c4882934 330 accept->number = nontermmap[accept->number - ntokens];
0c2d3f4c 331 }
572909b5 332
00238958
AD
333 nsyms -= nuseless_nonterminals;
334 nvars -= nuseless_nonterminals;
572909b5 335
c4882934 336 free (nontermmap);
572909b5 337}
015acc48 338
337c5bd1 339
00238958
AD
340/*------------------------------------------------------------------.
341| Output the detailed results of the reductions. For FILE.output. |
342`------------------------------------------------------------------*/
337c5bd1
AD
343
344void
345reduce_output (FILE *out)
572909b5 346{
572909b5
RS
347 if (nuseless_nonterminals > 0)
348 {
d2d1b42b 349 int i;
cff03fb2 350 fprintf (out, "%s\n\n", _("Nonterminals useless in grammar"));
760b53a8 351 for (i = 0; i < nuseless_nonterminals; ++i)
97650f4e 352 fprintf (out, " %s\n", symbols[nsyms + i]->tag);
d2d1b42b 353 fputs ("\n\n", out);
572909b5 354 }
d2d1b42b
AD
355
356 {
8307162d 357 bool b = false;
d2d1b42b
AD
358 int i;
359 for (i = 0; i < ntokens; i++)
d80fb37a 360 if (reduce_token_unused_in_grammar (i))
572909b5
RS
361 {
362 if (!b)
d80fb37a 363 fprintf (out, "%s\n\n", _("Terminals unused in grammar"));
8307162d 364 b = true;
97650f4e 365 fprintf (out, " %s\n", symbols[i]->tag);
572909b5 366 }
d2d1b42b
AD
367 if (b)
368 fputs ("\n\n", out);
369 }
572909b5
RS
370
371 if (nuseless_productions > 0)
cff03fb2
JD
372 grammar_rules_partial_print (out, _("Rules useless in grammar"),
373 rule_useless_in_grammar_p);
572909b5
RS
374}
375\f
572909b5 376
337c5bd1
AD
377/*-------------------------------.
378| Report the results to STDERR. |
379`-------------------------------*/
380
a083fbbf 381static void
337c5bd1 382reduce_print (void)
572909b5 383{
572909b5 384 if (nuseless_nonterminals > 0)
4631c34f
JD
385 warn (ngettext ("%d nonterminal useless in grammar",
386 "%d nonterminals useless in grammar",
387 nuseless_nonterminals),
388 nuseless_nonterminals);
572909b5 389 if (nuseless_productions > 0)
4631c34f
JD
390 warn (ngettext ("%d rule useless in grammar",
391 "%d rules useless in grammar",
392 nuseless_productions),
393 nuseless_productions);
015acc48
AD
394}
395\f
396void
397reduce_grammar (void)
398{
399 bool reduced;
400
401 /* Allocate the global sets used to compute the reduced grammar */
402
ed86e78c 403 N = bitset_create (nvars, BITSET_FIXED);
4b3d3a8e 404 P = bitset_create (nrules, BITSET_FIXED);
ed86e78c 405 V = bitset_create (nsyms, BITSET_FIXED);
ed86e78c 406 V1 = bitset_create (nsyms, BITSET_FIXED);
015acc48
AD
407
408 useless_nonterminals ();
409 inaccessable_symbols ();
410
4d56beff 411 reduced = (nuseless_nonterminals + nuseless_productions > 0);
337c5bd1
AD
412 if (!reduced)
413 return;
015acc48 414
337c5bd1 415 reduce_print ();
015acc48 416
88bce5a2 417 if (!bitset_test (N, accept->number - ntokens))
1bfb97db
AD
418 fatal_at (startsymbol_location,
419 _("start symbol %s does not derive any sentence"),
420 startsymbol->tag);
015acc48 421
bb88b0fc
AD
422 /* First reduce the nonterminals, as they renumber themselves in the
423 whole grammar. If you change the order, nonterms would be
424 renumbered only in the reduced grammar. */
00238958
AD
425 if (nuseless_nonterminals > 0)
426 nonterminals_reduce ();
bb88b0fc
AD
427 if (nuseless_productions > 0)
428 reduce_grammar_tables ();
9bfe901c 429
273a74fa 430 if (trace_flag & trace_grammar)
9bfe901c 431 {
78ab8f67 432 grammar_dump (stderr, "Reduced Grammar");
9bfe901c
AD
433
434 fprintf (stderr, "reduced %s defines %d terminals, %d nonterminals\
435, and %d productions.\n",
95612cfa 436 grammar_file, ntokens, nvars, nrules);
9bfe901c 437 }
337c5bd1 438}
015acc48 439
d80fb37a
JD
440bool
441reduce_token_unused_in_grammar (symbol_number i)
442{
443 aver (i < ntokens);
444 return !bitset_test (V, i) && !bitset_test (V1, i);
445}
446
447bool
448reduce_nonterminal_useless_in_grammar (symbol_number i)
449{
450 aver (ntokens <= i && i < nsyms + nuseless_nonterminals);
451 return nsyms <= i;
452}
015acc48 453
337c5bd1
AD
454/*-----------------------------------------------------------.
455| Free the global sets used to compute the reduced grammar. |
456`-----------------------------------------------------------*/
457
458void
459reduce_free (void)
460{
ed86e78c
AD
461 bitset_free (N);
462 bitset_free (V);
463 bitset_free (V1);
464 bitset_free (P);
572909b5 465}