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
47static void
48print_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
123static void
124print_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
160static void
161print_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
176void
177print_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