1/* Output a graph of the generated parser, for Bison.
2
3   Copyright (C) 2001-2007, 2009-2012 Free Software Foundation, Inc.
4
5   This file is part of Bison, the GNU Compiler Compiler.
6
7   This program is free software: you can redistribute it and/or modify
8   it under the terms of the GNU General Public License as published by
9   the Free Software Foundation, either version 3 of the License, or
10   (at your option) any later version.
11
12   This program is distributed in the hope that it will be useful,
13   but WITHOUT ANY WARRANTY; without even the implied warranty of
14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15   GNU General Public License for more details.
16
17   You should have received a copy of the GNU General Public License
18   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
19
20#include <config.h>
21#include "system.h"
22
23#include "LR0.h"
24#include "closure.h"
25#include "complain.h"
26#include "conflicts.h"
27#include "files.h"
28#include "getargs.h"
29#include "gram.h"
30#include "graphviz.h"
31#include "lalr.h"
32#include "print_graph.h"
33#include "reader.h"
34#include "state.h"
35#include "symtab.h"
36
37
38/*----------------------------.
39| Construct the node labels.  |
40`----------------------------*/
41
42/* Print the lhs of a rule in such a manner that there is no vertical
43   repetition, like in *.output files. */
44
45static void
46print_lhs (struct obstack *oout, rule *previous_rule, rule *r)
47{
48  if (previous_rule && STREQ (previous_rule->lhs->tag, r->lhs->tag))
49    {
50      int i;
51      for (i = 0; i < strlen (r->lhs->tag); ++i)
52        obstack_1grow (oout, ' ');
53      obstack_1grow (oout, '|');
54    }
55  else
56    {
57      obstack_sgrow (oout, escape (r->lhs->tag));
58      obstack_1grow (oout, ':');
59    }
60}
61
62static void
63print_core (struct obstack *oout, state *s)
64{
65  item_number *sitems = s->items;
66  rule *previous_rule = NULL;
67  size_t i;
68  size_t snritems = s->nitems;
69
70  /* Output all the items of a state, not only its kernel.  */
71  if (report_flag & report_itemsets)
72    {
73      closure (sitems, snritems);
74      sitems = itemset;
75      snritems = nitemset;
76    }
77
78  obstack_printf (oout, _("State %d"), s->number);
79  obstack_sgrow (oout, "\\n\\l");
80  for (i = 0; i < snritems; i++)
81    {
82      item_number *sp;
83      item_number *sp1;
84      rule_number r;
85
86      sp1 = sp = ritem + sitems[i];
87
88      while (*sp >= 0)
89        sp++;
90
91      r = item_number_as_rule_number (*sp);
92
93      obstack_printf (oout, "%3d ", r);
94      print_lhs (oout, previous_rule, &rules[r]);
95      previous_rule = &rules[r];
96
97      for (sp = rules[r].rhs; sp < sp1; sp++)
98        obstack_printf (oout, " %s", escape (symbols[*sp]->tag));
99
100      obstack_sgrow (oout, " .");
101
102      for (/* Nothing */; *sp >= 0; ++sp)
103        obstack_printf (oout, " %s", escape (symbols[*sp]->tag));
104
105      /* Experimental feature: display the lookahead tokens. */
106      if (report_flag & report_lookahead_tokens
107          && item_number_is_rule_number (*sp1))
108        {
109          /* Find the reduction we are handling.  */
110          reductions *reds = s->reductions;
111          int redno = state_reduction_find (s, &rules[r]);
112
113          /* Print them if there are.  */
114          if (reds->lookahead_tokens && redno != -1)
115            {
116              bitset_iterator biter;
117              int k;
118              char const *sep = "";
119              obstack_sgrow (oout, "  [");
120              BITSET_FOR_EACH (biter, reds->lookahead_tokens[redno], k, 0)
121                {
122                  obstack_sgrow (oout, sep);
123                  obstack_sgrow (oout, escape (symbols[k]->tag));
124                  sep = ", ";
125                }
126              obstack_1grow (oout, ']');
127            }
128        }
129      obstack_sgrow (oout, "\\l");
130    }
131}
132
133
134/*---------------------------------------------------------------.
135| Output in graph_obstack edges specifications in incidence with |
136| current node.                                                  |
137`---------------------------------------------------------------*/
138
139static void
140print_actions (state const *s, FILE *fgraph)
141{
142  transitions const *trans = s->transitions;
143  int i;
144
145  if (!trans->num && !s->reductions)
146    return;
147
148  for (i = 0; i < trans->num; i++)
149    if (!TRANSITION_IS_DISABLED (trans, i))
150      {
151	state *s1 = trans->states[i];
152	symbol_number sym = s1->accessing_symbol;
153
154	/* Shifts are solid, gotos are dashed, and error is dotted.  */
155	char const *style =
156	  (TRANSITION_IS_ERROR (trans, i) ? "dotted"
157	   : TRANSITION_IS_SHIFT (trans, i) ? "solid"
158	   : "dashed");
159
160	if (TRANSITION_IS_ERROR (trans, i)
161	    && strcmp (symbols[sym]->tag, "error") != 0)
162	  abort ();
163	output_edge (s->number, s1->number,
164		     TRANSITION_IS_ERROR (trans, i) ? NULL : symbols[sym]->tag,
165		     style, fgraph);
166      }
167  /* Display reductions. */
168  output_red (s, s->reductions, fgraph);
169}
170
171
172/*-------------------------------------------------------------.
173| Output in FGRAPH the current node specifications and exiting |
174| edges.                                                       |
175`-------------------------------------------------------------*/
176
177static void
178print_state (state *s, FILE *fgraph)
179{
180  struct obstack node_obstack;
181
182  /* A node's label contains its items.  */
183  obstack_init (&node_obstack);
184  print_core (&node_obstack, s);
185  obstack_1grow (&node_obstack, '\0');
186  output_node (s->number, obstack_finish (&node_obstack), fgraph);
187  obstack_free (&node_obstack, 0);
188
189  /* Output the edges.  */
190  print_actions (s, fgraph);
191}
192
193
194void
195print_graph (void)
196{
197  state_number i;
198  FILE *fgraph = xfopen (spec_graph_file, "w");
199  start_graph (fgraph);
200
201  /* Output nodes and edges. */
202  new_closure (nritems);
203  for (i = 0; i < nstates; i++)
204    print_state (states[i], fgraph);
205  free_closure ();
206
207  finish_graph (fgraph);
208  xfclose (fgraph);
209}
210