1 /* Output Graphviz specification of a state machine generated by Bison.
3 Copyright (C) 2006-2007, 2009-2015, 2018-2020 Free Software
6 This file is part of Bison, the GNU Compiler Compiler.
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.
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.
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/>. */
21 /* Written by Paul Eggert and Satya Kiran Popuri. */
33 /* Return an unambiguous printable representation for NAME, suitable
34 for C strings. Use slot 2 since the user may use slots 0 and 1. */
37 quote (char const *name
)
39 return quotearg_n_style (2, c_quoting_style
, name
);
43 start_graph (FILE *fout
)
46 _("// Generated by %s.\n"
47 "// Report bugs to <%s>.\n"
48 "// Home page: <%s>.\n"
56 quote (grammar_file
));
58 " node [fontname = courier, shape = box, colorscheme = paired6]\n"
59 " edge [fontname = courier]\n"
64 output_node (int id
, char const *label
, FILE *fout
)
66 fprintf (fout
, " %d [label=\"%s\"]\n", id
, label
);
70 output_edge (int source
, int destination
, char const *label
,
71 char const *style
, FILE *fout
)
73 fprintf (fout
, " %d -> %d [style=%s", source
, destination
, style
);
76 fputs (" label=\"", fout
);
77 for (const char *cp
= label
; *cp
; ++cp
)
80 case '"': fputs ("\\\"", fout
); break;
81 case '\\': fputs ("\\\\", fout
); break;
82 default: fputc (*cp
, fout
); break;
90 no_reduce_bitset_init (state
const *s
, bitset
*no_reduce_set
)
92 *no_reduce_set
= bitset_create (ntokens
, BITSET_FIXED
);
93 bitset_zero (*no_reduce_set
);
96 FOR_EACH_SHIFT (s
->transitions
, n
)
97 bitset_set (*no_reduce_set
, TRANSITION_SYMBOL (s
->transitions
, n
));
99 for (int n
= 0; n
< s
->errs
->num
; ++n
)
100 if (s
->errs
->symbols
[n
])
101 bitset_set (*no_reduce_set
, s
->errs
->symbols
[n
]->content
->number
);
105 conclude_red (struct obstack
*out
, int source
, rule_number ruleno
,
106 bool enabled
, bool first
, FILE *fout
)
108 /* If no lookahead tokens were valid transitions, this reduction is
109 actually hidden, so cancel everything. */
111 (void) obstack_finish0 (out
);
114 char const *ed
= enabled
? "" : "d";
115 char const *color
= enabled
? ruleno
? "3" : "1" : "5";
117 /* First, build the edge's head. The name of reduction nodes is "nRm",
118 with n the source state and m the rule number. This is because we
119 don't want all the reductions bearing a same rule number to point to
120 the same state, since that is not the desired format. */
121 fprintf (fout
, " %d -> \"%dR%d%s\" [",
122 source
, source
, ruleno
, ed
);
124 /* (The lookahead tokens have been added to the beginning of the
125 obstack, in the caller function.) */
126 if (! obstack_empty_p (out
))
128 char *label
= obstack_finish0 (out
);
129 fprintf (fout
, "label=\"[%s]\", ", label
);
130 obstack_free (out
, label
);
133 /* Then, the edge's tail. */
134 fprintf (fout
, "style=solid]\n");
136 /* Build the associated diamond representation of the target rule. */
137 fprintf (fout
, " \"%dR%d%s\" [label=\"",
140 fprintf (fout
, "R%d", ruleno
);
142 fprintf (fout
, "Acc");
144 fprintf (fout
, "\", fillcolor=%s, shape=diamond, style=filled]\n",
150 print_token (struct obstack
*out
, bool first
, char const *tok
)
153 obstack_sgrow (out
, ", ");
154 obstack_backslash (out
, tok
);
159 output_red (state
const *s
, reductions
const *reds
, FILE *fout
)
161 bitset no_reduce_set
;
162 no_reduce_bitset_init (s
, &no_reduce_set
);
164 rule
*default_reduction
165 = yydefact
[s
->number
] ? &rules
[yydefact
[s
->number
] - 1] : NULL
;
167 /* Two obstacks are needed: one for the enabled reductions, and one
168 for the disabled reductions, because in the end we want two
169 separate edges, even though in most cases only one will actually
173 obstack_init (&dout
);
174 obstack_init (&eout
);
176 const int source
= s
->number
;
177 for (int j
= 0; j
< reds
->num
; ++j
)
179 bool defaulted
= default_reduction
&& default_reduction
== reds
->rules
[j
];
181 /* Build the lookahead tokens lists, one for enabled transitions
182 and one for disabled transitions. */
185 rule_number ruleno
= reds
->rules
[j
]->number
;
187 if (reds
->lookaheads
)
188 for (int i
= 0; i
< ntokens
; i
++)
189 if (bitset_test (reds
->lookaheads
[j
], i
))
191 if (bitset_test (no_reduce_set
, i
))
192 firstd
= print_token (&dout
, firstd
, symbols
[i
]->tag
);
196 firste
= print_token (&eout
, firste
, symbols
[i
]->tag
);
197 bitset_set (no_reduce_set
, i
);
201 /* Do the actual output. */
202 conclude_red (&dout
, source
, ruleno
, false, firstd
, fout
);
203 conclude_red (&eout
, source
, ruleno
, true, firste
&& !defaulted
, fout
);
205 obstack_free (&dout
, 0);
206 obstack_free (&eout
, 0);
207 bitset_free (no_reduce_set
);
211 finish_graph (FILE *fout
)