1 /* Output Graphviz specification of a state machine generated by Bison. 2 3 Copyright (C) 2006-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 /* Written by Paul Eggert and Satya Kiran Popuri. */ 21 22 #include <config.h> 23 #include "system.h" 24 25 #include <quotearg.h> 26 27 #include "files.h" 28 #include "gram.h" 29 #include "graphviz.h" 30 #include "tables.h" 31 32 /* Return an unambiguous printable representation for NAME, suitable 33 for C strings. Use slot 2 since the user may use slots 0 and 1. */ 34 35 static char * 36 quote (char const *name) 37 { 38 return quotearg_n_style (2, c_quoting_style, name); 39 } 40 41 void 42 start_graph (FILE *fout) 43 { 44 fprintf (fout, 45 _("// Generated by %s.\n" 46 "// Report bugs to <%s>.\n" 47 "// Home page: <%s>.\n" 48 "\n"), 49 PACKAGE_STRING, 50 PACKAGE_BUGREPORT, 51 PACKAGE_URL); 52 fprintf (fout, 53 "digraph %s\n" 54 "{\n", 55 quote (grammar_file)); 56 fprintf (fout, 57 " node [fontname = courier, shape = box, colorscheme = paired6]\n" 58 " edge [fontname = courier]\n" 59 "\n"); 60 } 61 62 void 63 output_node (int id, char const *label, FILE *fout) 64 { 65 fprintf (fout, " %d [label=\"%s\"]\n", id, label); 66 } 67 68 void 69 output_edge (int source, int destination, char const *label, 70 char const *style, FILE *fout) 71 { 72 fprintf (fout, " %d -> %d [style=%s", source, destination, style); 73 if (label) 74 fprintf (fout, " label=%s", quote (label)); 75 fputs ("]\n", fout); 76 } 77 78 char const * 79 escape (char const *name) 80 { 81 char *q = quote (name); 82 q[strlen (q) - 1] = '\0'; 83 return q + 1; 84 } 85 86 static void 87 no_reduce_bitset_init (state const *s, bitset *no_reduce_set) 88 { 89 int n; 90 *no_reduce_set = bitset_create (ntokens, BITSET_FIXED); 91 bitset_zero (*no_reduce_set); 92 FOR_EACH_SHIFT (s->transitions, n) 93 bitset_set (*no_reduce_set, TRANSITION_SYMBOL (s->transitions, n)); 94 for (n = 0; n < s->errs->num; ++n) 95 if (s->errs->symbols[n]) 96 bitset_set (*no_reduce_set, s->errs->symbols[n]->number); 97 } 98 99 static void 100 conclude_red (struct obstack *out, int source, rule_number ruleno, 101 bool enabled, bool first, FILE *fout) 102 { 103 /* If no lookahead tokens were valid transitions, this reduction is 104 actually hidden, so cancel everything. */ 105 if (first) 106 (void) obstack_finish0 (out); 107 else 108 { 109 char const *ed = enabled ? "" : "d"; 110 char const *color = enabled ? ruleno ? "3" : "1" : "5"; 111 112 /* First, build the edge's head. The name of reduction nodes is "nRm", 113 with n the source state and m the rule number. This is because we 114 don't want all the reductions bearing a same rule number to point to 115 the same state, since that is not the desired format. */ 116 fprintf (fout, " %1$d -> \"%1$dR%2$d%3$s\" [", 117 source, ruleno, ed); 118 119 /* (The lookahead tokens have been added to the beginning of the 120 obstack, in the caller function.) */ 121 if (! obstack_empty_p (out)) 122 { 123 char *label = obstack_finish0 (out); 124 fprintf (fout, "label=\"[%s]\", ", label); 125 obstack_free (out, label); 126 } 127 128 /* Then, the edge's tail. */ 129 fprintf (fout, "style=solid]\n"); 130 131 /* Build the associated diamond representation of the target rule. */ 132 fprintf (fout, " \"%dR%d%s\" [label=\"", 133 source, ruleno, ed); 134 if (ruleno) 135 fprintf (fout, "R%d", ruleno); 136 else 137 fprintf (fout, "Acc"); 138 139 fprintf (fout, "\", fillcolor=%s, shape=diamond, style=filled]\n", 140 color); 141 } 142 } 143 144 static bool 145 print_token (struct obstack *out, bool first, char const *tok) 146 { 147 char const *q = escape (tok); 148 149 if (! first) 150 obstack_sgrow (out, ", "); 151 obstack_sgrow (out, q); 152 return false; 153 } 154 155 void 156 output_red (state const *s, reductions const *reds, FILE *fout) 157 { 158 bitset no_reduce_set; 159 int j; 160 int source = s->number; 161 162 /* Two obstacks are needed: one for the enabled reductions, and one 163 for the disabled reductions, because in the end we want two 164 separate edges, even though in most cases only one will actually 165 be printed. */ 166 struct obstack dout; 167 struct obstack eout; 168 169 no_reduce_bitset_init (s, &no_reduce_set); 170 obstack_init (&dout); 171 obstack_init (&eout); 172 173 for (j = 0; j < reds->num; ++j) 174 { 175 bool defaulted = false; 176 bool firstd = true; 177 bool firste = true; 178 rule_number ruleno = reds->rules[j]->number; 179 rule *default_reduction = NULL; 180 181 if (yydefact[s->number] != 0) 182 default_reduction = &rules[yydefact[s->number] - 1]; 183 184 /* Build the lookahead tokens lists, one for enabled transitions and one 185 for disabled transistions. */ 186 if (default_reduction && default_reduction == reds->rules[j]) 187 defaulted = true; 188 if (reds->lookahead_tokens) 189 { 190 int i; 191 for (i = 0; i < ntokens; i++) 192 if (bitset_test (reds->lookahead_tokens[j], i)) 193 { 194 if (bitset_test (no_reduce_set, i)) 195 firstd = print_token (&dout, firstd, symbols[i]->tag); 196 else 197 { 198 if (! defaulted) 199 firste = print_token (&eout, firste, symbols[i]->tag); 200 bitset_set (no_reduce_set, i); 201 } 202 } 203 } 204 205 /* Do the actual output. */ 206 conclude_red (&dout, source, ruleno, false, firstd, fout); 207 conclude_red (&eout, source, ruleno, true, firste && !defaulted, fout); 208 } 209 obstack_free (&dout, 0); 210 obstack_free (&eout, 0); 211 bitset_free (no_reduce_set); 212 } 213 214 void 215 finish_graph (FILE *fout) 216 { 217 fputs ("}\n", fout); 218 } 219
