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
45 static void
print_lhs(struct obstack * oout,rule * previous_rule,rule * r)46 print_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
62 static void
print_core(struct obstack * oout,state * s)63 print_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
139 static void
print_actions(state const * s,FILE * fgraph)140 print_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
177 static void
print_state(state * s,FILE * fgraph)178 print_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
194 void
print_graph(void)195 print_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