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
41static bitset no_reduce_set;
42
43#if 0
44static void
45print_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
57static void
58max_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
69static void
70print_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
127static void
128print_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
175static void
176print_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
214static void
215print_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
239static void
240print_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
353static void
354print_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
369static void
370print_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)				\
389do {						\
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
399static void
400print_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
499void
500print_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