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