/* Output Graphviz specification of a state machine generated by Bison.
- Copyright (C) 2006-2007, 2009-2011 Free Software Foundation, Inc.
+ Copyright (C) 2006-2007, 2009-2012 Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
#include <quotearg.h>
#include "files.h"
+#include "gram.h"
#include "graphviz.h"
+#include "tables.h"
/* Return an unambiguous printable representation for NAME, suitable
for C strings. Use slot 2 since the user may use slots 0 and 1. */
-static char const *
+static char *
quote (char const *name)
{
return quotearg_n_style (2, c_quoting_style, name);
"digraph %s\n"
"{\n",
quote (grammar_file));
+ fprintf (fout,
+ " node [fontname = courier, shape = box, colorscheme = paired6]\n"
+ " edge [fontname = courier]\n"
+ "\n");
}
void
output_node (int id, char const *label, FILE *fout)
{
- fprintf (fout, " %d [label=%s]\n", id, quote (label));
+ fprintf (fout, " %d [label=\"%s\"]\n", id, label);
}
void
output_edge (int source, int destination, char const *label,
- char const *style, FILE *fout)
+ char const *style, FILE *fout)
{
fprintf (fout, " %d -> %d [style=%s", source, destination, style);
if (label)
fputs ("]\n", fout);
}
+char const *
+escape (char const *name)
+{
+ char *q = quote (name);
+ q[strlen (q) - 1] = '\0';
+ return q + 1;
+}
+
+static void
+no_reduce_bitset_init (state const *s, bitset *no_reduce_set)
+{
+ int n;
+ *no_reduce_set = bitset_create (ntokens, BITSET_FIXED);
+ bitset_zero (*no_reduce_set);
+ FOR_EACH_SHIFT (s->transitions, n)
+ bitset_set (*no_reduce_set, TRANSITION_SYMBOL (s->transitions, n));
+ for (n = 0; n < s->errs->num; ++n)
+ if (s->errs->symbols[n])
+ bitset_set (*no_reduce_set, s->errs->symbols[n]->number);
+}
+
+static void
+conclude_red (struct obstack *out, int source, rule_number ruleno,
+ bool enabled, bool first, FILE *fout)
+{
+ /* If no lookahead tokens were valid transitions, this reduction is
+ actually hidden, so cancel everything. */
+ if (first)
+ return (void) obstack_finish0 (out);
+ else
+ {
+ char const *ed = enabled ? "" : "d";
+ char const *color = enabled ? ruleno ? "3" : "1" : "5";
+
+ /* First, build the edge's head. The name of reduction nodes is "nRm",
+ with n the source state and m the rule number. This is because we
+ don't want all the reductions bearing a same rule number to point to
+ the same state, since that is not the desired format. */
+ fprintf (fout, " %1$d -> \"%1$dR%2$d%3$s\" [",
+ source, ruleno, ed);
+
+ /* (The lookahead tokens have been added to the beginning of the
+ obstack, in the caller function.) */
+ if (! obstack_empty_p (out))
+ {
+ char *label = obstack_finish0 (out);
+ fprintf (fout, "label=\"[%s]\", ", label);
+ obstack_free (out, label);
+ }
+
+ /* Then, the edge's tail. */
+ fprintf (fout, "style=solid]\n");
+
+ /* Build the associated diamond representation of the target rule. */
+ fprintf (fout, " \"%dR%d%s\" [label=\"",
+ source, ruleno, ed);
+ if (ruleno)
+ fprintf (fout, "R%d", ruleno);
+ else
+ fprintf (fout, "Acc");
+
+ fprintf (fout, "\", fillcolor=%s, shape=diamond, style=filled]\n",
+ color);
+ }
+}
+
+static bool
+print_token (struct obstack *out, bool first, char const *tok)
+{
+ char const *q = escape (tok);
+
+ if (! first)
+ obstack_sgrow (out, ", ");
+ obstack_sgrow (out, q);
+ return false;
+}
+
+void
+output_red (state const *s, reductions const *reds, FILE *fout)
+{
+ bitset no_reduce_set;
+ int j;
+ int source = s->number;
+
+ /* Two obstacks are needed: one for the enabled reductions, and one
+ for the disabled reductions, because in the end we want two
+ separate edges, even though in most cases only one will actually
+ be printed. */
+ struct obstack dout;
+ struct obstack eout;
+
+ no_reduce_bitset_init (s, &no_reduce_set);
+ obstack_init (&dout);
+ obstack_init (&eout);
+
+ for (j = 0; j < reds->num; ++j)
+ {
+ bool defaulted = false;
+ bool firstd = true;
+ bool firste = true;
+ rule_number ruleno = reds->rules[j]->number;
+ rule *default_reduction = NULL;
+
+ if (yydefact[s->number] != 0)
+ default_reduction = &rules[yydefact[s->number] - 1];
+
+ /* Build the lookahead tokens lists, one for enabled transitions and one
+ for disabled transistions. */
+ if (default_reduction && default_reduction == reds->rules[j])
+ defaulted = true;
+ if (reds->lookahead_tokens)
+ {
+ int i;
+ for (i = 0; i < ntokens; i++)
+ if (bitset_test (reds->lookahead_tokens[j], i))
+ {
+ if (bitset_test (no_reduce_set, i))
+ firstd = print_token (&dout, firstd, symbols[i]->tag);
+ else
+ {
+ if (! defaulted)
+ firste = print_token (&eout, firste, symbols[i]->tag);
+ bitset_set (no_reduce_set, i);
+ }
+ }
+ }
+
+ /* Do the actual output. */
+ conclude_red (&dout, source, ruleno, false, firstd, fout);
+ conclude_red (&eout, source, ruleno, true, firste && !defaulted, fout);
+ }
+ obstack_free (&dout, 0);
+ obstack_free (&eout, 0);
+ bitset_free (no_reduce_set);
+}
+
void
finish_graph (FILE *fout)
{
projects / bison.git / blobdiff