| 1 | /* Output a graph of the generated parser, for Bison. |
| 2 | |
| 3 | Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009 Free |
| 4 | Software 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 "system.h" |
| 23 | |
| 24 | #include <quotearg.h> |
| 25 | |
| 26 | #include "LR0.h" |
| 27 | #include "closure.h" |
| 28 | #include "complain.h" |
| 29 | #include "conflicts.h" |
| 30 | #include "files.h" |
| 31 | #include "getargs.h" |
| 32 | #include "gram.h" |
| 33 | #include "graphviz.h" |
| 34 | #include "lalr.h" |
| 35 | #include "print_graph.h" |
| 36 | #include "reader.h" |
| 37 | #include "state.h" |
| 38 | #include "symtab.h" |
| 39 | |
| 40 | |
| 41 | /*----------------------------. |
| 42 | | Construct the node labels. | |
| 43 | `----------------------------*/ |
| 44 | |
| 45 | static void |
| 46 | print_core (struct obstack *oout, state *s) |
| 47 | { |
| 48 | size_t i; |
| 49 | item_number *sitems = s->items; |
| 50 | size_t snritems = s->nitems; |
| 51 | |
| 52 | /* Output all the items of a state, not only its kernel. */ |
| 53 | if (report_flag & report_itemsets) |
| 54 | { |
| 55 | closure (sitems, snritems); |
| 56 | sitems = itemset; |
| 57 | snritems = nitemset; |
| 58 | } |
| 59 | |
| 60 | obstack_fgrow1 (oout, "%d", s->number); |
| 61 | for (i = 0; i < snritems; i++) |
| 62 | { |
| 63 | item_number *sp; |
| 64 | item_number *sp1; |
| 65 | rule_number r; |
| 66 | |
| 67 | sp1 = sp = ritem + sitems[i]; |
| 68 | |
| 69 | while (*sp >= 0) |
| 70 | sp++; |
| 71 | |
| 72 | r = item_number_as_rule_number (*sp); |
| 73 | |
| 74 | obstack_fgrow1 (oout, "\n%s -> ", rules[r].lhs->tag); |
| 75 | |
| 76 | for (sp = rules[r].rhs; sp < sp1; sp++) |
| 77 | obstack_fgrow1 (oout, "%s ", symbols[*sp]->tag); |
| 78 | |
| 79 | obstack_1grow (oout, '.'); |
| 80 | |
| 81 | for (/* Nothing */; *sp >= 0; ++sp) |
| 82 | obstack_fgrow1 (oout, " %s", symbols[*sp]->tag); |
| 83 | |
| 84 | /* Experimental feature: display the lookahead tokens. */ |
| 85 | if (report_flag & report_lookahead_tokens |
| 86 | && item_number_is_rule_number (*sp1)) |
| 87 | { |
| 88 | /* Find the reduction we are handling. */ |
| 89 | reductions *reds = s->reductions; |
| 90 | int redno = state_reduction_find (s, &rules[r]); |
| 91 | |
| 92 | /* Print them if there are. */ |
| 93 | if (reds->lookahead_tokens && redno != -1) |
| 94 | { |
| 95 | bitset_iterator biter; |
| 96 | int k; |
| 97 | char const *sep = ""; |
| 98 | obstack_sgrow (oout, "["); |
| 99 | BITSET_FOR_EACH (biter, reds->lookahead_tokens[redno], k, 0) |
| 100 | { |
| 101 | obstack_fgrow2 (oout, "%s%s", sep, symbols[k]->tag); |
| 102 | sep = ", "; |
| 103 | } |
| 104 | obstack_sgrow (oout, "]"); |
| 105 | } |
| 106 | } |
| 107 | } |
| 108 | } |
| 109 | |
| 110 | |
| 111 | /*---------------------------------------------------------------. |
| 112 | | Output in graph_obstack edges specifications in incidence with | |
| 113 | | current node. | |
| 114 | `---------------------------------------------------------------*/ |
| 115 | |
| 116 | static void |
| 117 | print_actions (state const *s, FILE *fgraph) |
| 118 | { |
| 119 | int i; |
| 120 | |
| 121 | transitions const *trans = s->transitions; |
| 122 | |
| 123 | if (!trans->num && !s->reductions) |
| 124 | return; |
| 125 | |
| 126 | for (i = 0; i < trans->num; i++) |
| 127 | if (!TRANSITION_IS_DISABLED (trans, i)) |
| 128 | { |
| 129 | state *s1 = trans->states[i]; |
| 130 | symbol_number sym = s1->accessing_symbol; |
| 131 | |
| 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); |
| 144 | } |
| 145 | } |
| 146 | |
| 147 | |
| 148 | /*-------------------------------------------------------------. |
| 149 | | Output in FGRAPH the current node specifications and exiting | |
| 150 | | edges. | |
| 151 | `-------------------------------------------------------------*/ |
| 152 | |
| 153 | static void |
| 154 | print_state (state *s, FILE *fgraph) |
| 155 | { |
| 156 | struct obstack node_obstack; |
| 157 | |
| 158 | /* A node's label contains its items. */ |
| 159 | obstack_init (&node_obstack); |
| 160 | print_core (&node_obstack, s); |
| 161 | obstack_1grow (&node_obstack, '\0'); |
| 162 | output_node (s->number, obstack_finish (&node_obstack), fgraph); |
| 163 | obstack_free (&node_obstack, 0); |
| 164 | |
| 165 | /* Output the edges. */ |
| 166 | print_actions (s, fgraph); |
| 167 | } |
| 168 | \f |
| 169 | |
| 170 | void |
| 171 | print_graph (void) |
| 172 | { |
| 173 | state_number i; |
| 174 | FILE *fgraph = xfopen (spec_graph_file, "w"); |
| 175 | start_graph (fgraph); |
| 176 | |
| 177 | /* Output nodes and edges. */ |
| 178 | new_closure (nritems); |
| 179 | for (i = 0; i < nstates; i++) |
| 180 | print_state (states[i], fgraph); |
| 181 | free_closure (); |
| 182 | |
| 183 | finish_graph (fgraph); |
| 184 | xfclose (fgraph); |
| 185 | } |