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 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 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 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 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 195 void 196 print_graph (void) 197 { 198 state_number i; 199 FILE *fgraph = xfopen (spec_graph_file, "w"); 200 start_graph (fgraph); 201 202 /* Output nodes and edges. */ 203 new_closure (nritems); 204 for (i = 0; i < nstates; i++) 205 print_state (states[i], fgraph); 206 free_closure (); 207 208 finish_graph (fgraph); 209 xfclose (fgraph); 210 } 211
