X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/cb9ec4fada480554cf47810fee736997d64e7427..0fe9720964da510a2b359af390a3053aace65f9f:/src/graphviz.c?ds=sidebyside diff --git a/src/graphviz.c b/src/graphviz.c index 0007f9e0..9da5f6e3 100644 --- a/src/graphviz.c +++ b/src/graphviz.c @@ -25,12 +25,14 @@ #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); @@ -51,12 +53,16 @@ start_graph (FILE *fout) "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 @@ -69,6 +75,142 @@ output_edge (int source, int destination, char const *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) + (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) {