1 | /* Output a graph of the generated parser, for Bison. |
2 | |
3 | Copyright (C) 2001-2007, 2009-2015, 2018-2019 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 <http://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 |
48 | print_core (struct obstack *oout, state *s) |
49 | { |
50 | item_number 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 | obstack_printf (oout, "%s: " , escape (r->lhs->symbol->tag)); |
76 | previous_lhs = r->lhs; |
77 | |
78 | for (item_number const *sp = r->rhs; sp < sp1; sp++) |
79 | obstack_printf (oout, "%s " , escape (symbols[*sp]->tag)); |
80 | |
81 | obstack_1grow (oout, '.'); |
82 | |
83 | if (0 <= *r->rhs) |
84 | for (item_number const *sp = sp1; 0 <= *sp; ++sp) |
85 | obstack_printf (oout, " %s" , escape (symbols[*sp]->tag)); |
86 | else |
87 | obstack_printf (oout, " %%empty" ); |
88 | |
89 | /* Experimental feature: display the lookahead tokens. */ |
90 | if (report_flag & report_lookahead_tokens |
91 | && item_number_is_rule_number (*sp1)) |
92 | { |
93 | /* Find the reduction we are handling. */ |
94 | reductions *reds = s->reductions; |
95 | int redno = state_reduction_find (s, r); |
96 | |
97 | /* Print them if there are. */ |
98 | if (reds->lookahead_tokens && redno != -1) |
99 | { |
100 | bitset_iterator biter; |
101 | int k; |
102 | char const *sep = "" ; |
103 | obstack_sgrow (oout, " [" ); |
104 | BITSET_FOR_EACH (biter, reds->lookahead_tokens[redno], k, 0) |
105 | { |
106 | obstack_sgrow (oout, sep); |
107 | obstack_sgrow (oout, escape (symbols[k]->tag)); |
108 | sep = ", " ; |
109 | } |
110 | obstack_1grow (oout, ']'); |
111 | } |
112 | } |
113 | obstack_sgrow (oout, "\\l" ); |
114 | } |
115 | } |
116 | |
117 | |
118 | /*---------------------------------------------------------------. |
119 | | Output in graph_obstack edges specifications in incidence with | |
120 | | current node. | |
121 | `---------------------------------------------------------------*/ |
122 | |
123 | static void |
124 | print_actions (state const *s, FILE *fgraph) |
125 | { |
126 | transitions const *trans = s->transitions; |
127 | |
128 | if (!trans->num && !s->reductions) |
129 | return; |
130 | |
131 | for (int i = 0; i < trans->num; i++) |
132 | if (!TRANSITION_IS_DISABLED (trans, i)) |
133 | { |
134 | const state *s1 = trans->states[i]; |
135 | const symbol_number sym = s1->accessing_symbol; |
136 | |
137 | /* Shifts are solid, gotos are dashed, and error is dotted. */ |
138 | char const *style = |
139 | (TRANSITION_IS_ERROR (trans, i) ? "dotted" |
140 | : TRANSITION_IS_SHIFT (trans, i) ? "solid" |
141 | : "dashed" ); |
142 | |
143 | if (TRANSITION_IS_ERROR (trans, i) |
144 | && STRNEQ (symbols[sym]->tag, "error" )) |
145 | abort (); |
146 | output_edge (s->number, s1->number, |
147 | TRANSITION_IS_ERROR (trans, i) ? NULL : symbols[sym]->tag, |
148 | style, fgraph); |
149 | } |
150 | /* Display reductions. */ |
151 | output_red (s, s->reductions, fgraph); |
152 | } |
153 | |
154 | |
155 | /*-------------------------------------------------------------. |
156 | | Output in FGRAPH the current node specifications and exiting | |
157 | | edges. | |
158 | `-------------------------------------------------------------*/ |
159 | |
160 | static void |
161 | print_state (state *s, FILE *fgraph) |
162 | { |
163 | struct obstack node_obstack; |
164 | |
165 | /* A node's label contains its items. */ |
166 | obstack_init (&node_obstack); |
167 | print_core (&node_obstack, s); |
168 | output_node (s->number, obstack_finish0 (&node_obstack), fgraph); |
169 | obstack_free (&node_obstack, 0); |
170 | |
171 | /* Output the edges. */ |
172 | print_actions (s, fgraph); |
173 | } |
174 | |
175 | |
176 | void |
177 | print_graph (void) |
178 | { |
179 | FILE *fgraph = xfopen (spec_graph_file, "w" ); |
180 | start_graph (fgraph); |
181 | |
182 | /* Output nodes and edges. */ |
183 | for (int i = 0; i < nstates; i++) |
184 | print_state (states[i], fgraph); |
185 | |
186 | finish_graph (fgraph); |
187 | xfclose (fgraph); |
188 | } |
189 | |