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
41static bitset no_reduce_set;
42
43
44
45/*---------------------------------------.
46| *WIDTH := max (*WIDTH, strlen (STR)). |
47`---------------------------------------*/
48
49static void
50max_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
61static void
62print_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
101static void
102print_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
147static void
148print_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
184static void
185print_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
209static void
210print_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
325static void
326print_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
341static void
342print_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
360static void
361print_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
388static void
389print_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
438void
439print_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