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