1 /* Output a graph of the generated parser, for Bison.
2
3 Copyright (C) 2001-2007, 2009-2015, 2018-2021 Free Software
4 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 <https://www.gnu.org/licenses/>. */
20
21 #include <config.h>
22 #include "print-graph.h"
23
24 #include "system.h"
25
26 #include "closure.h"
27 #include "complain.h"
28 #include "conflicts.h"
29 #include "files.h"
30 #include "getargs.h"
31 #include "gram.h"
32 #include "graphviz.h"
33 #include "lalr.h"
34 #include "lr0.h"
35 #include "reader.h"
36 #include "state.h"
37 #include "symtab.h"
38
39
40 /*----------------------------.
41 | Construct the node labels. |
42 `----------------------------*/
43
44 /* Print the lhs of a rule in such a manner that there is no vertical
45 repetition, like in *.output files. */
46
47 static void
print_core(struct obstack * oout,state * s)48 print_core (struct obstack *oout, state *s)
49 {
50 item_index const *sitems = s->items;
51 sym_content *previous_lhs = NULL;
52 size_t snritems = s->nitems;
53
54 /* Output all the items of a state, not just its kernel. */
55 if (report_flag & report_itemsets)
56 {
57 closure (sitems, snritems);
58 sitems = itemset;
59 snritems = nitemset;
60 }
61
62 obstack_printf (oout, _("State %d"), s->number);
63 obstack_sgrow (oout, "\\n\\l");
64 for (size_t i = 0; i < snritems; ++i)
65 {
66 item_number const *sp1 = ritem + sitems[i];
67 rule const *r = item_rule (sp1);
68
69 obstack_printf (oout, "%3d ", r->number);
70 if (previous_lhs && UNIQSTR_EQ (previous_lhs->symbol->tag,
71 r->lhs->symbol->tag))
72 obstack_printf (oout, "%*s| ",
73 (int) strlen (previous_lhs->symbol->tag), "");
74 else
75 {
76 obstack_backslash (oout, r->lhs->symbol->tag);
77 obstack_printf (oout, ": ");
78 }
79 previous_lhs = r->lhs;
80
81 for (item_number const *sp = r->rhs; sp < sp1; sp++)
82 {
83 obstack_backslash (oout, symbols[*sp]->tag);
84 obstack_1grow (oout, ' ');
85 }
86
87 obstack_sgrow (oout, "•");
88
89 if (0 <= *r->rhs)
90 for (item_number const *sp = sp1; 0 <= *sp; ++sp)
91 {
92 obstack_1grow (oout, ' ');
93 obstack_backslash (oout, symbols[*sp]->tag);
94 }
95 else
96 obstack_sgrow (oout, " %empty");
97
98 /* Experimental feature: display the lookahead tokens. */
99 if (report_flag & report_lookaheads
100 && item_number_is_rule_number (*sp1))
101 {
102 /* Find the reduction we are handling. */
103 reductions *reds = s->reductions;
104 int redno = state_reduction_find (s, r);
105
106 /* Print them if there are. */
107 if (reds->lookaheads && redno != -1)
108 {
109 bitset_iterator biter;
110 int k;
111 char const *sep = "";
112 obstack_sgrow (oout, " [");
113 BITSET_FOR_EACH (biter, reds->lookaheads[redno], k, 0)
114 {
115 obstack_sgrow (oout, sep);
116 obstack_backslash (oout, symbols[k]->tag);
117 sep = ", ";
118 }
119 obstack_1grow (oout, ']');
120 }
121 }
122 obstack_sgrow (oout, "\\l");
123 }
124 }
125
126
127 /*---------------------------------------------------------------.
128 | Output in graph_obstack edges specifications in incidence with |
129 | current node. |
130 `---------------------------------------------------------------*/
131
132 static void
print_actions(state const * s,FILE * fgraph)133 print_actions (state const *s, FILE *fgraph)
134 {
135 transitions const *trans = s->transitions;
136
137 if (!trans->num && !s->reductions)
138 return;
139
140 for (int i = 0; i < trans->num; i++)
141 if (!TRANSITION_IS_DISABLED (trans, i))
142 {
143 const state *s1 = trans->states[i];
144 const symbol_number sym = s1->accessing_symbol;
145
146 /* Shifts are solid, gotos are dashed, and error is dotted. */
147 char const *style =
148 (TRANSITION_IS_ERROR (trans, i) ? "dotted"
149 : TRANSITION_IS_SHIFT (trans, i) ? "solid"
150 : "dashed");
151
152 if (TRANSITION_IS_ERROR (trans, i)
153 && STRNEQ (symbols[sym]->tag, "error"))
154 abort ();
155 output_edge (s->number, s1->number,
156 TRANSITION_IS_ERROR (trans, i) ? NULL : symbols[sym]->tag,
157 style, fgraph);
158 }
159 /* Display reductions. */
160 output_red (s, s->reductions, fgraph);
161 }
162
163
164 /*-------------------------------------------------------------.
165 | Output in FGRAPH the current node specifications and exiting |
166 | edges. |
167 `-------------------------------------------------------------*/
168
169 static void
print_state(state * s,FILE * fgraph)170 print_state (state *s, FILE *fgraph)
171 {
172 struct obstack node_obstack;
173
174 /* A node's label contains its items. */
175 obstack_init (&node_obstack);
176 print_core (&node_obstack, s);
177 output_node (s->number, obstack_finish0 (&node_obstack), fgraph);
178 obstack_free (&node_obstack, 0);
179
180 /* Output the edges. */
181 print_actions (s, fgraph);
182 }
183
184
185 void
print_graph(void)186 print_graph (void)
187 {
188 FILE *fgraph = xfopen (spec_graph_file, "w");
189 start_graph (fgraph);
190
191 /* Output nodes and edges. */
192 for (int i = 0; i < nstates; i++)
193 print_state (states[i], fgraph);
194
195 finish_graph (fgraph);
196 xfclose (fgraph);
197 }
198