Commit | Line | Data |
---|---|---|
35fe0834 | 1 | /* Output a graph of the generated parser, for Bison. |
16bb742f | 2 | |
401b73af JD |
3 | Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009 Free |
4 | Software Foundation, Inc. | |
ce4d5ce0 AD |
5 | |
6 | This file is part of Bison, the GNU Compiler Compiler. | |
7 | ||
f16b0819 | 8 | This program is free software: you can redistribute it and/or modify |
ce4d5ce0 | 9 | it under the terms of the GNU General Public License as published by |
f16b0819 PE |
10 | the Free Software Foundation, either version 3 of the License, or |
11 | (at your option) any later version. | |
ce4d5ce0 | 12 | |
f16b0819 | 13 | This program is distributed in the hope that it will be useful, |
ce4d5ce0 AD |
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 | |
f16b0819 | 19 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
ce4d5ce0 | 20 | |
2cec9080 | 21 | #include <config.h> |
ce4d5ce0 | 22 | #include "system.h" |
16bb742f | 23 | |
16bb742f PE |
24 | #include <quotearg.h> |
25 | ||
ce4d5ce0 | 26 | #include "LR0.h" |
16bb742f | 27 | #include "closure.h" |
ce4d5ce0 | 28 | #include "complain.h" |
16bb742f PE |
29 | #include "conflicts.h" |
30 | #include "files.h" | |
ce4d5ce0 | 31 | #include "getargs.h" |
16bb742f | 32 | #include "gram.h" |
35fe0834 | 33 | #include "graphviz.h" |
16bb742f | 34 | #include "lalr.h" |
ce4d5ce0 | 35 | #include "print_graph.h" |
16bb742f PE |
36 | #include "reader.h" |
37 | #include "state.h" | |
38 | #include "symtab.h" | |
ce4d5ce0 | 39 | |
8adfa272 | 40 | |
6b98e4b5 AD |
41 | /*----------------------------. |
42 | | Construct the node labels. | | |
43 | `----------------------------*/ | |
8adfa272 | 44 | |
ce4d5ce0 | 45 | static void |
16bb742f | 46 | print_core (struct obstack *oout, state *s) |
ce4d5ce0 | 47 | { |
f6fbd3da | 48 | size_t i; |
16bb742f | 49 | item_number *sitems = s->items; |
f6fbd3da | 50 | size_t snritems = s->nitems; |
22c2cbc0 | 51 | |
2e729273 | 52 | /* Output all the items of a state, not only its kernel. */ |
05811fd7 | 53 | if (report_flag & report_itemsets) |
30171f79 | 54 | { |
5123689b | 55 | closure (sitems, snritems); |
30171f79 | 56 | sitems = itemset; |
b09f4f48 | 57 | snritems = nitemset; |
30171f79 | 58 | } |
22c2cbc0 | 59 | |
35fe0834 | 60 | obstack_fgrow1 (oout, "%d", s->number); |
5123689b | 61 | for (i = 0; i < snritems; i++) |
ce4d5ce0 | 62 | { |
16bb742f PE |
63 | item_number *sp; |
64 | item_number *sp1; | |
65 | rule_number r; | |
c4b66126 | 66 | |
2e729273 | 67 | sp1 = sp = ritem + sitems[i]; |
ce4d5ce0 | 68 | |
75142d45 | 69 | while (*sp >= 0) |
ce4d5ce0 AD |
70 | sp++; |
71 | ||
16bb742f | 72 | r = item_number_as_rule_number (*sp); |
ce4d5ce0 | 73 | |
35fe0834 | 74 | obstack_fgrow1 (oout, "\n%s -> ", rules[r].lhs->tag); |
ce4d5ce0 | 75 | |
16bb742f | 76 | for (sp = rules[r].rhs; sp < sp1; sp++) |
97650f4e | 77 | obstack_fgrow1 (oout, "%s ", symbols[*sp]->tag); |
ce4d5ce0 | 78 | |
d4e7d3a1 | 79 | obstack_1grow (oout, '.'); |
22c2cbc0 | 80 | |
75142d45 | 81 | for (/* Nothing */; *sp >= 0; ++sp) |
97650f4e | 82 | obstack_fgrow1 (oout, " %s", symbols[*sp]->tag); |
d4e7d3a1 | 83 | |
742e4900 | 84 | /* Experimental feature: display the lookahead tokens. */ |
255a6b90 JD |
85 | if (report_flag & report_lookahead_tokens |
86 | && item_number_is_rule_number (*sp1)) | |
d4e7d3a1 | 87 | { |
cd08e51e | 88 | /* Find the reduction we are handling. */ |
16bb742f PE |
89 | reductions *reds = s->reductions; |
90 | int redno = state_reduction_find (s, &rules[r]); | |
613f5e1a | 91 | |
cd08e51e | 92 | /* Print them if there are. */ |
742e4900 | 93 | if (reds->lookahead_tokens && redno != -1) |
d4e7d3a1 | 94 | { |
cd08e51e AD |
95 | bitset_iterator biter; |
96 | int k; | |
d0829076 | 97 | char const *sep = ""; |
cd08e51e | 98 | obstack_sgrow (oout, "["); |
742e4900 | 99 | BITSET_FOR_EACH (biter, reds->lookahead_tokens[redno], k, 0) |
d0829076 PE |
100 | { |
101 | obstack_fgrow2 (oout, "%s%s", sep, symbols[k]->tag); | |
102 | sep = ", "; | |
103 | } | |
d4e7d3a1 AD |
104 | obstack_sgrow (oout, "]"); |
105 | } | |
106 | } | |
ce4d5ce0 | 107 | } |
ce4d5ce0 AD |
108 | } |
109 | ||
08a946e0 AD |
110 | |
111 | /*---------------------------------------------------------------. | |
112 | | Output in graph_obstack edges specifications in incidence with | | |
113 | | current node. | | |
114 | `---------------------------------------------------------------*/ | |
115 | ||
ce4d5ce0 | 116 | static void |
35fe0834 | 117 | print_actions (state const *s, FILE *fgraph) |
ce4d5ce0 AD |
118 | { |
119 | int i; | |
d954473d | 120 | |
35fe0834 | 121 | transitions const *trans = s->transitions; |
22c2cbc0 | 122 | |
35fe0834 | 123 | if (!trans->num && !s->reductions) |
5092aba5 | 124 | return; |
ce4d5ce0 | 125 | |
16bb742f PE |
126 | for (i = 0; i < trans->num; i++) |
127 | if (!TRANSITION_IS_DISABLED (trans, i)) | |
d954473d | 128 | { |
16bb742f PE |
129 | state *s1 = trans->states[i]; |
130 | symbol_number sym = s1->accessing_symbol; | |
d954473d | 131 | |
35fe0834 PE |
132 | /* Shifts are solid, gotos are dashed, and error is dotted. */ |
133 | char const *style = | |
134 | (TRANSITION_IS_ERROR (trans, i) ? "dotted" | |
135 | : TRANSITION_IS_SHIFT (trans, i) ? "solid" | |
136 | : "dashed"); | |
137 | ||
138 | if (TRANSITION_IS_ERROR (trans, i) | |
139 | && strcmp (symbols[sym]->tag, "error") != 0) | |
140 | abort (); | |
141 | output_edge (s->number, s1->number, | |
142 | TRANSITION_IS_ERROR (trans, i) ? NULL : symbols[sym]->tag, | |
143 | style, fgraph); | |
d954473d | 144 | } |
ce4d5ce0 AD |
145 | } |
146 | ||
08a946e0 AD |
147 | |
148 | /*-------------------------------------------------------------. | |
149 | | Output in FGRAPH the current node specifications and exiting | | |
150 | | edges. | | |
151 | `-------------------------------------------------------------*/ | |
152 | ||
ce4d5ce0 | 153 | static void |
35fe0834 | 154 | print_state (state *s, FILE *fgraph) |
ce4d5ce0 | 155 | { |
600cad3b | 156 | struct obstack node_obstack; |
ce4d5ce0 | 157 | |
35fe0834 | 158 | /* A node's label contains its items. */ |
600cad3b | 159 | obstack_init (&node_obstack); |
16bb742f | 160 | print_core (&node_obstack, s); |
08a946e0 | 161 | obstack_1grow (&node_obstack, '\0'); |
35fe0834 PE |
162 | output_node (s->number, obstack_finish (&node_obstack), fgraph); |
163 | obstack_free (&node_obstack, 0); | |
342b8b6e | 164 | |
08a946e0 | 165 | /* Output the edges. */ |
35fe0834 | 166 | print_actions (s, fgraph); |
ce4d5ce0 AD |
167 | } |
168 | \f | |
169 | ||
170 | void | |
171 | print_graph (void) | |
172 | { | |
16bb742f | 173 | state_number i; |
35fe0834 PE |
174 | FILE *fgraph = xfopen (spec_graph_file, "w"); |
175 | start_graph (fgraph); | |
ce4d5ce0 | 176 | |
08a946e0 | 177 | /* Output nodes and edges. */ |
9e7f6bbd | 178 | new_closure (nritems); |
ce4d5ce0 | 179 | for (i = 0; i < nstates; i++) |
35fe0834 | 180 | print_state (states[i], fgraph); |
2e729273 | 181 | free_closure (); |
ce4d5ce0 | 182 | |
35fe0834 | 183 | finish_graph (fgraph); |
342b8b6e | 184 | xfclose (fgraph); |
ce4d5ce0 | 185 | } |