Commit | Line | Data |
---|---|---|
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 | 43 | static bitset N; |
572909b5 | 44 | |
00238958 | 45 | /* Set of all rules which have no useless nonterminals in their RHS. */ |
ed86e78c | 46 | static bitset P; |
00238958 AD |
47 | |
48 | /* Set of all accessible symbols. */ | |
ed86e78c | 49 | static 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 | 53 | static bitset V1; |
572909b5 | 54 | |
17ee7397 PE |
55 | static rule_number nuseful_productions; |
56 | rule_number nuseless_productions; | |
015acc48 | 57 | static int nuseful_nonterminals; |
17ee7397 | 58 | symbol_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 | 66 | static bool |
17ee7397 | 67 | useful_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 | 85 | static void |
d2729d44 | 86 | useless_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 | 134 | static void |
d2729d44 | 135 | inaccessable_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 | 233 | static void |
d2729d44 | 234 | reduce_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 |
285 | static void |
286 | nonterminals_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 | |
344 | void | |
345 | reduce_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 | 381 | static void |
337c5bd1 | 382 | reduce_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 | |
396 | void | |
397 | reduce_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 |
440 | bool |
441 | reduce_token_unused_in_grammar (symbol_number i) | |
442 | { | |
443 | aver (i < ntokens); | |
444 | return !bitset_test (V, i) && !bitset_test (V1, i); | |
445 | } | |
446 | ||
447 | bool | |
448 | reduce_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 | ||
458 | void | |
459 | reduce_free (void) | |
460 | { | |
ed86e78c AD |
461 | bitset_free (N); |
462 | bitset_free (V); | |
463 | bitset_free (V1); | |
464 | bitset_free (P); | |
572909b5 | 465 | } |