1 | /* Print information on generated parser, for bison, |
2 | |
3 | Copyright (C) 1984, 1986, 1989, 2000-2005, 2007, 2009-2015, 2018-2019 |
4 | Free Software Foundation, Inc. |
5 | |
6 | This file is part of Bison, the GNU Compiler Compiler. |
7 | |
8 | This program is free software: you can redistribute it and/or modify |
9 | it under the terms of the GNU General Public License as published by |
10 | the Free Software Foundation, either version 3 of the License, or |
11 | (at your option) any later version. |
12 | |
13 | This program is distributed in the hope that it will be useful, |
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. |
17 | |
18 | You should have received a copy of the GNU General Public License |
19 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
20 | |
21 | #include <config.h> |
22 | #include "system.h" |
23 | |
24 | #include <bitset.h> |
25 | |
26 | #include "closure.h" |
27 | #include "conflicts.h" |
28 | #include "files.h" |
29 | #include "getargs.h" |
30 | #include "gram.h" |
31 | #include "lalr.h" |
32 | #include "lr0.h" |
33 | #include "muscle-tab.h" |
34 | #include "print.h" |
35 | #include "reader.h" |
36 | #include "reduce.h" |
37 | #include "state.h" |
38 | #include "symtab.h" |
39 | #include "tables.h" |
40 | |
41 | static bitset no_reduce_set; |
42 | |
43 | |
44 | |
45 | /*---------------------------------------. |
46 | | *WIDTH := max (*WIDTH, strlen (STR)). | |
47 | `---------------------------------------*/ |
48 | |
49 | static void |
50 | max_length (size_t *width, const char *str) |
51 | { |
52 | size_t len = strlen (str); |
53 | if (len > *width) |
54 | *width = len; |
55 | } |
56 | |
57 | /*--------------------------------. |
58 | | Report information on a state. | |
59 | `--------------------------------*/ |
60 | |
61 | static void |
62 | print_core (FILE *out, state *s) |
63 | { |
64 | item_number *sitems = s->items; |
65 | size_t snritems = s->nitems; |
66 | /* Output all the items of a state, not only its kernel. */ |
67 | if (report_flag & report_itemsets) |
68 | { |
69 | closure (sitems, snritems); |
70 | sitems = itemset; |
71 | snritems = nitemset; |
72 | } |
73 | |
74 | if (!snritems) |
75 | return; |
76 | |
77 | fputc ('\n', out); |
78 | |
79 | rule const *previous_rule = NULL; |
80 | for (size_t i = 0; i < snritems; i++) |
81 | { |
82 | item_number *sp1 = ritem + sitems[i]; |
83 | rule const *r = item_rule (sp1); |
84 | item_print (sp1, previous_rule, out); |
85 | previous_rule = r; |
86 | |
87 | /* Display the lookahead tokens? */ |
88 | if (report_flag & report_lookahead_tokens |
89 | && item_number_is_rule_number (*sp1)) |
90 | state_rule_lookahead_tokens_print (s, r, out); |
91 | fputc ('\n', out); |
92 | } |
93 | } |
94 | |
95 | |
96 | /*------------------------------------------------------------. |
97 | | Report the shifts iff DISPLAY_SHIFTS_P or the gotos of S on | |
98 | | OUT. | |
99 | `------------------------------------------------------------*/ |
100 | |
101 | static void |
102 | print_transitions (state *s, FILE *out, bool display_transitions_p) |
103 | { |
104 | transitions *trans = s->transitions; |
105 | size_t width = 0; |
106 | |
107 | /* Compute the width of the lookahead token column. */ |
108 | for (int i = 0; i < trans->num; i++) |
109 | if (!TRANSITION_IS_DISABLED (trans, i) |
110 | && TRANSITION_IS_SHIFT (trans, i) == display_transitions_p) |
111 | { |
112 | symbol *sym = symbols[TRANSITION_SYMBOL (trans, i)]; |
113 | max_length (&width, sym->tag); |
114 | } |
115 | |
116 | /* Nothing to report. */ |
117 | if (!width) |
118 | return; |
119 | |
120 | fputc ('\n', out); |
121 | width += 2; |
122 | |
123 | /* Report lookahead tokens and shifts. */ |
124 | for (int i = 0; i < trans->num; i++) |
125 | if (!TRANSITION_IS_DISABLED (trans, i) |
126 | && TRANSITION_IS_SHIFT (trans, i) == display_transitions_p) |
127 | { |
128 | symbol *sym = symbols[TRANSITION_SYMBOL (trans, i)]; |
129 | const char *tag = sym->tag; |
130 | state *s1 = trans->states[i]; |
131 | |
132 | fprintf (out, " %s" , tag); |
133 | for (int j = width - strlen (tag); j > 0; --j) |
134 | fputc (' ', out); |
135 | if (display_transitions_p) |
136 | fprintf (out, _("shift, and go to state %d\n" ), s1->number); |
137 | else |
138 | fprintf (out, _("go to state %d\n" ), s1->number); |
139 | } |
140 | } |
141 | |
142 | |
143 | /*--------------------------------------------------------. |
144 | | Report the explicit errors of S raised from %nonassoc. | |
145 | `--------------------------------------------------------*/ |
146 | |
147 | static void |
148 | print_errs (FILE *out, state *s) |
149 | { |
150 | errs *errp = s->errs; |
151 | size_t width = 0; |
152 | |
153 | /* Compute the width of the lookahead token column. */ |
154 | for (int i = 0; i < errp->num; ++i) |
155 | if (errp->symbols[i]) |
156 | max_length (&width, errp->symbols[i]->tag); |
157 | |
158 | /* Nothing to report. */ |
159 | if (!width) |
160 | return; |
161 | |
162 | fputc ('\n', out); |
163 | width += 2; |
164 | |
165 | /* Report lookahead tokens and errors. */ |
166 | for (int i = 0; i < errp->num; ++i) |
167 | if (errp->symbols[i]) |
168 | { |
169 | const char *tag = errp->symbols[i]->tag; |
170 | fprintf (out, " %s" , tag); |
171 | for (int j = width - strlen (tag); j > 0; --j) |
172 | fputc (' ', out); |
173 | fputs (_("error (nonassociative)\n" ), out); |
174 | } |
175 | } |
176 | |
177 | |
178 | /*-------------------------------------------------------------------------. |
179 | | Report a reduction of RULE on LOOKAHEAD_TOKEN (which can be 'default'). | |
180 | | If not ENABLED, the rule is masked by a shift or a reduce (S/R and | |
181 | | R/R conflicts). | |
182 | `-------------------------------------------------------------------------*/ |
183 | |
184 | static void |
185 | print_reduction (FILE *out, size_t width, |
186 | const char *lookahead_token, |
187 | rule *r, bool enabled) |
188 | { |
189 | fprintf (out, " %s" , lookahead_token); |
190 | for (int j = width - strlen (lookahead_token); j > 0; --j) |
191 | fputc (' ', out); |
192 | if (!enabled) |
193 | fputc ('[', out); |
194 | if (r->number) |
195 | fprintf (out, _("reduce using rule %d (%s)" ), r->number, |
196 | r->lhs->symbol->tag); |
197 | else |
198 | fprintf (out, _("accept" )); |
199 | if (!enabled) |
200 | fputc (']', out); |
201 | fputc ('\n', out); |
202 | } |
203 | |
204 | |
205 | /*-------------------------------------------. |
206 | | Report on OUT the reduction actions of S. | |
207 | `-------------------------------------------*/ |
208 | |
209 | static void |
210 | print_reductions (FILE *out, state *s) |
211 | { |
212 | reductions *reds = s->reductions; |
213 | if (reds->num == 0) |
214 | return; |
215 | |
216 | rule *default_reduction = NULL; |
217 | if (yydefact[s->number] != 0) |
218 | default_reduction = &rules[yydefact[s->number] - 1]; |
219 | |
220 | transitions *trans = s->transitions; |
221 | |
222 | bitset_zero (no_reduce_set); |
223 | { |
224 | int i; |
225 | FOR_EACH_SHIFT (trans, i) |
226 | bitset_set (no_reduce_set, TRANSITION_SYMBOL (trans, i)); |
227 | } |
228 | for (int i = 0; i < s->errs->num; ++i) |
229 | if (s->errs->symbols[i]) |
230 | bitset_set (no_reduce_set, s->errs->symbols[i]->content->number); |
231 | |
232 | /* Compute the width of the lookahead token column. */ |
233 | size_t width = 0; |
234 | if (default_reduction) |
235 | width = strlen (_("$default" )); |
236 | |
237 | if (reds->lookahead_tokens) |
238 | for (int i = 0; i < ntokens; i++) |
239 | { |
240 | bool count = bitset_test (no_reduce_set, i); |
241 | |
242 | for (int j = 0; j < reds->num; ++j) |
243 | if (bitset_test (reds->lookahead_tokens[j], i)) |
244 | { |
245 | if (! count) |
246 | { |
247 | if (reds->rules[j] != default_reduction) |
248 | max_length (&width, symbols[i]->tag); |
249 | count = true; |
250 | } |
251 | else |
252 | max_length (&width, symbols[i]->tag); |
253 | } |
254 | } |
255 | |
256 | /* Nothing to report. */ |
257 | if (!width) |
258 | return; |
259 | |
260 | fputc ('\n', out); |
261 | width += 2; |
262 | |
263 | bool default_reduction_only = true; |
264 | |
265 | /* Report lookahead tokens (or $default) and reductions. */ |
266 | if (reds->lookahead_tokens) |
267 | for (int i = 0; i < ntokens; i++) |
268 | { |
269 | bool defaulted = false; |
270 | bool count = bitset_test (no_reduce_set, i); |
271 | if (count) |
272 | default_reduction_only = false; |
273 | |
274 | for (int j = 0; j < reds->num; ++j) |
275 | if (bitset_test (reds->lookahead_tokens[j], i)) |
276 | { |
277 | if (! count) |
278 | { |
279 | if (reds->rules[j] != default_reduction) |
280 | { |
281 | default_reduction_only = false; |
282 | print_reduction (out, width, |
283 | symbols[i]->tag, |
284 | reds->rules[j], true); |
285 | } |
286 | else |
287 | defaulted = true; |
288 | count = true; |
289 | } |
290 | else |
291 | { |
292 | default_reduction_only = false; |
293 | if (defaulted) |
294 | print_reduction (out, width, |
295 | symbols[i]->tag, |
296 | default_reduction, true); |
297 | defaulted = false; |
298 | print_reduction (out, width, |
299 | symbols[i]->tag, |
300 | reds->rules[j], false); |
301 | } |
302 | } |
303 | } |
304 | |
305 | if (default_reduction) |
306 | { |
307 | char *default_reductions = |
308 | muscle_percent_define_get ("lr.default-reduction" ); |
309 | print_reduction (out, width, _("$default" ), default_reduction, true); |
310 | aver (STREQ (default_reductions, "most" ) |
311 | || (STREQ (default_reductions, "consistent" ) |
312 | && default_reduction_only) |
313 | || (reds->num == 1 && reds->rules[0]->number == 0)); |
314 | (void) default_reduction_only; |
315 | free (default_reductions); |
316 | } |
317 | } |
318 | |
319 | |
320 | /*--------------------------------------------------------------. |
321 | | Report on OUT all the actions (shifts, gotos, reductions, and | |
322 | | explicit erros from %nonassoc) of S. | |
323 | `--------------------------------------------------------------*/ |
324 | |
325 | static void |
326 | print_actions (FILE *out, state *s) |
327 | { |
328 | /* Print shifts. */ |
329 | print_transitions (s, out, true); |
330 | print_errs (out, s); |
331 | print_reductions (out, s); |
332 | /* Print gotos. */ |
333 | print_transitions (s, out, false); |
334 | } |
335 | |
336 | |
337 | /*----------------------------------. |
338 | | Report all the data on S on OUT. | |
339 | `----------------------------------*/ |
340 | |
341 | static void |
342 | print_state (FILE *out, state *s) |
343 | { |
344 | fputs ("\n\n" , out); |
345 | fprintf (out, _("State %d" ), s->number); |
346 | fputc ('\n', out); |
347 | print_core (out, s); |
348 | print_actions (out, s); |
349 | if ((report_flag & report_solved_conflicts) && s->solved_conflicts) |
350 | { |
351 | fputc ('\n', out); |
352 | fputs (s->solved_conflicts, out); |
353 | } |
354 | } |
355 | |
356 | /*-----------------------------------------. |
357 | | Print information on the whole grammar. | |
358 | `-----------------------------------------*/ |
359 | |
360 | static void |
361 | print_terminal_symbols (FILE *out) |
362 | { |
363 | /* TERMINAL (type #) : rule #s terminal is on RHS */ |
364 | fprintf (out, "%s\n\n" , _("Terminals, with rules where they appear" )); |
365 | for (symbol_number i = 0; i < max_user_token_number + 1; i++) |
366 | if (token_translations[i] != undeftoken->content->number) |
367 | { |
368 | const char *tag = symbols[token_translations[i]]->tag; |
369 | fprintf (out, "%4s%s" , "" , tag); |
370 | if (symbols[token_translations[i]]->content->type_name) |
371 | fprintf (out, " <%s>" , |
372 | symbols[token_translations[i]]->content->type_name); |
373 | fprintf (out, " (%d)" , i); |
374 | |
375 | for (rule_number r = 0; r < nrules; r++) |
376 | for (item_number *rhsp = rules[r].rhs; *rhsp >= 0; rhsp++) |
377 | if (item_number_as_symbol_number (*rhsp) == token_translations[i]) |
378 | { |
379 | fprintf (out, " %d" , r); |
380 | break; |
381 | } |
382 | fputc ('\n', out); |
383 | } |
384 | fputs ("\n\n" , out); |
385 | } |
386 | |
387 | |
388 | static void |
389 | print_nonterminal_symbols (FILE *out) |
390 | { |
391 | fprintf (out, "%s\n\n" , _("Nonterminals, with rules where they appear" )); |
392 | for (symbol_number i = ntokens; i < nsyms; i++) |
393 | { |
394 | const char *tag = symbols[i]->tag; |
395 | bool on_left = false; |
396 | bool on_right = false; |
397 | |
398 | for (rule_number r = 0; r < nrules; r++) |
399 | { |
400 | on_left |= rules[r].lhs->number == i; |
401 | for (item_number *rhsp = rules[r].rhs; !on_right && 0 <= *rhsp; ++rhsp) |
402 | on_right |= item_number_as_symbol_number (*rhsp) == i; |
403 | if (on_left && on_right) |
404 | break; |
405 | } |
406 | |
407 | int column = 4 + strlen (tag); |
408 | fprintf (out, "%4s%s" , "" , tag); |
409 | if (symbols[i]->content->type_name) |
410 | column += fprintf (out, " <%s>" , |
411 | symbols[i]->content->type_name); |
412 | fprintf (out, " (%d)\n" , i); |
413 | |
414 | if (on_left) |
415 | { |
416 | fprintf (out, "%8s%s" , "" , _("on left:" )); |
417 | for (rule_number r = 0; r < nrules; r++) |
418 | if (rules[r].lhs->number == i) |
419 | fprintf (out, " %d" , r); |
420 | fputc ('\n', out); |
421 | } |
422 | |
423 | if (on_right) |
424 | { |
425 | fprintf (out, "%8s%s" , "" , _("on right:" )); |
426 | for (rule_number r = 0; r < nrules; r++) |
427 | for (item_number *rhsp = rules[r].rhs; 0 <= *rhsp; ++rhsp) |
428 | if (item_number_as_symbol_number (*rhsp) == i) |
429 | { |
430 | fprintf (out, " %d" , r); |
431 | break; |
432 | } |
433 | fputc ('\n', out); |
434 | } |
435 | } |
436 | } |
437 | |
438 | void |
439 | print_results (void) |
440 | { |
441 | /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but |
442 | that conflicts with Posix. */ |
443 | FILE *out = xfopen (spec_verbose_file, "w" ); |
444 | |
445 | reduce_output (out); |
446 | grammar_rules_partial_print (out, |
447 | _("Rules useless in parser due to conflicts" ), |
448 | rule_useless_in_parser_p); |
449 | conflicts_output (out); |
450 | |
451 | grammar_rules_print (out); |
452 | print_terminal_symbols (out); |
453 | print_nonterminal_symbols (out); |
454 | |
455 | /* Storage for print_reductions. */ |
456 | no_reduce_set = bitset_create (ntokens, BITSET_FIXED); |
457 | for (state_number i = 0; i < nstates; i++) |
458 | print_state (out, states[i]); |
459 | bitset_free (no_reduce_set); |
460 | |
461 | xfclose (out); |
462 | } |
463 | |