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