105436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* Output Graphviz specification of a state machine generated by Bison. 205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 305436638acc7c010349a69c3395f1a57c642dc62Ying Wang Copyright (C) 2006-2007, 2009-2012 Free Software Foundation, Inc. 405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 505436638acc7c010349a69c3395f1a57c642dc62Ying Wang This file is part of Bison, the GNU Compiler Compiler. 605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 705436638acc7c010349a69c3395f1a57c642dc62Ying Wang This program is free software: you can redistribute it and/or modify 805436638acc7c010349a69c3395f1a57c642dc62Ying Wang it under the terms of the GNU General Public License as published by 905436638acc7c010349a69c3395f1a57c642dc62Ying Wang the Free Software Foundation, either version 3 of the License, or 1005436638acc7c010349a69c3395f1a57c642dc62Ying Wang (at your option) any later version. 1105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 1205436638acc7c010349a69c3395f1a57c642dc62Ying Wang This program is distributed in the hope that it will be useful, 1305436638acc7c010349a69c3395f1a57c642dc62Ying Wang but WITHOUT ANY WARRANTY; without even the implied warranty of 1405436638acc7c010349a69c3395f1a57c642dc62Ying Wang MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1505436638acc7c010349a69c3395f1a57c642dc62Ying Wang GNU General Public License for more details. 1605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 1705436638acc7c010349a69c3395f1a57c642dc62Ying Wang You should have received a copy of the GNU General Public License 1805436638acc7c010349a69c3395f1a57c642dc62Ying Wang along with this program. If not, see <http://www.gnu.org/licenses/>. */ 1905436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2005436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* Written by Paul Eggert and Satya Kiran Popuri. */ 2105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2205436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include <config.h> 2305436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "system.h" 2405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2505436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include <quotearg.h> 2605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2705436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "files.h" 2805436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "gram.h" 2905436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "graphviz.h" 3005436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "tables.h" 3105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 3205436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* Return an unambiguous printable representation for NAME, suitable 3305436638acc7c010349a69c3395f1a57c642dc62Ying Wang for C strings. Use slot 2 since the user may use slots 0 and 1. */ 3405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 3505436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic char * 3605436638acc7c010349a69c3395f1a57c642dc62Ying Wangquote (char const *name) 3705436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 3805436638acc7c010349a69c3395f1a57c642dc62Ying Wang return quotearg_n_style (2, c_quoting_style, name); 3905436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 4005436638acc7c010349a69c3395f1a57c642dc62Ying Wang 4105436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid 4205436638acc7c010349a69c3395f1a57c642dc62Ying Wangstart_graph (FILE *fout) 4305436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 4405436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (fout, 4505436638acc7c010349a69c3395f1a57c642dc62Ying Wang _("// Generated by %s.\n" 4605436638acc7c010349a69c3395f1a57c642dc62Ying Wang "// Report bugs to <%s>.\n" 4705436638acc7c010349a69c3395f1a57c642dc62Ying Wang "// Home page: <%s>.\n" 4805436638acc7c010349a69c3395f1a57c642dc62Ying Wang "\n"), 4905436638acc7c010349a69c3395f1a57c642dc62Ying Wang PACKAGE_STRING, 5005436638acc7c010349a69c3395f1a57c642dc62Ying Wang PACKAGE_BUGREPORT, 5105436638acc7c010349a69c3395f1a57c642dc62Ying Wang PACKAGE_URL); 5205436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (fout, 5305436638acc7c010349a69c3395f1a57c642dc62Ying Wang "digraph %s\n" 5405436638acc7c010349a69c3395f1a57c642dc62Ying Wang "{\n", 5505436638acc7c010349a69c3395f1a57c642dc62Ying Wang quote (grammar_file)); 5605436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (fout, 5705436638acc7c010349a69c3395f1a57c642dc62Ying Wang " node [fontname = courier, shape = box, colorscheme = paired6]\n" 5805436638acc7c010349a69c3395f1a57c642dc62Ying Wang " edge [fontname = courier]\n" 5905436638acc7c010349a69c3395f1a57c642dc62Ying Wang "\n"); 6005436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 6105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 6205436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid 6305436638acc7c010349a69c3395f1a57c642dc62Ying Wangoutput_node (int id, char const *label, FILE *fout) 6405436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 6505436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (fout, " %d [label=\"%s\"]\n", id, label); 6605436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 6705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 6805436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid 6905436638acc7c010349a69c3395f1a57c642dc62Ying Wangoutput_edge (int source, int destination, char const *label, 7005436638acc7c010349a69c3395f1a57c642dc62Ying Wang char const *style, FILE *fout) 7105436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 7205436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (fout, " %d -> %d [style=%s", source, destination, style); 7305436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (label) 7405436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (fout, " label=%s", quote (label)); 7505436638acc7c010349a69c3395f1a57c642dc62Ying Wang fputs ("]\n", fout); 7605436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 7705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 7805436638acc7c010349a69c3395f1a57c642dc62Ying Wangchar const * 7905436638acc7c010349a69c3395f1a57c642dc62Ying Wangescape (char const *name) 8005436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 8105436638acc7c010349a69c3395f1a57c642dc62Ying Wang char *q = quote (name); 8205436638acc7c010349a69c3395f1a57c642dc62Ying Wang q[strlen (q) - 1] = '\0'; 8305436638acc7c010349a69c3395f1a57c642dc62Ying Wang return q + 1; 8405436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 8505436638acc7c010349a69c3395f1a57c642dc62Ying Wang 8605436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic void 8705436638acc7c010349a69c3395f1a57c642dc62Ying Wangno_reduce_bitset_init (state const *s, bitset *no_reduce_set) 8805436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 8905436638acc7c010349a69c3395f1a57c642dc62Ying Wang int n; 9005436638acc7c010349a69c3395f1a57c642dc62Ying Wang *no_reduce_set = bitset_create (ntokens, BITSET_FIXED); 9105436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_zero (*no_reduce_set); 9205436638acc7c010349a69c3395f1a57c642dc62Ying Wang FOR_EACH_SHIFT (s->transitions, n) 9305436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_set (*no_reduce_set, TRANSITION_SYMBOL (s->transitions, n)); 9405436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (n = 0; n < s->errs->num; ++n) 9505436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (s->errs->symbols[n]) 9605436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_set (*no_reduce_set, s->errs->symbols[n]->number); 9705436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 9805436638acc7c010349a69c3395f1a57c642dc62Ying Wang 9905436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic void 10005436638acc7c010349a69c3395f1a57c642dc62Ying Wangconclude_red (struct obstack *out, int source, rule_number ruleno, 10105436638acc7c010349a69c3395f1a57c642dc62Ying Wang bool enabled, bool first, FILE *fout) 10205436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 10305436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* If no lookahead tokens were valid transitions, this reduction is 10405436638acc7c010349a69c3395f1a57c642dc62Ying Wang actually hidden, so cancel everything. */ 10505436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (first) 10605436638acc7c010349a69c3395f1a57c642dc62Ying Wang (void) obstack_finish0 (out); 10705436638acc7c010349a69c3395f1a57c642dc62Ying Wang else 10805436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 10905436638acc7c010349a69c3395f1a57c642dc62Ying Wang char const *ed = enabled ? "" : "d"; 11005436638acc7c010349a69c3395f1a57c642dc62Ying Wang char const *color = enabled ? ruleno ? "3" : "1" : "5"; 11105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 11205436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* First, build the edge's head. The name of reduction nodes is "nRm", 11305436638acc7c010349a69c3395f1a57c642dc62Ying Wang with n the source state and m the rule number. This is because we 11405436638acc7c010349a69c3395f1a57c642dc62Ying Wang don't want all the reductions bearing a same rule number to point to 11505436638acc7c010349a69c3395f1a57c642dc62Ying Wang the same state, since that is not the desired format. */ 11605436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (fout, " %1$d -> \"%1$dR%2$d%3$s\" [", 11705436638acc7c010349a69c3395f1a57c642dc62Ying Wang source, ruleno, ed); 11805436638acc7c010349a69c3395f1a57c642dc62Ying Wang 11905436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* (The lookahead tokens have been added to the beginning of the 12005436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack, in the caller function.) */ 12105436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (! obstack_empty_p (out)) 12205436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 12305436638acc7c010349a69c3395f1a57c642dc62Ying Wang char *label = obstack_finish0 (out); 12405436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (fout, "label=\"[%s]\", ", label); 12505436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_free (out, label); 12605436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 12705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 12805436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Then, the edge's tail. */ 12905436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (fout, "style=solid]\n"); 13005436638acc7c010349a69c3395f1a57c642dc62Ying Wang 13105436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Build the associated diamond representation of the target rule. */ 13205436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (fout, " \"%dR%d%s\" [label=\"", 13305436638acc7c010349a69c3395f1a57c642dc62Ying Wang source, ruleno, ed); 13405436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (ruleno) 13505436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (fout, "R%d", ruleno); 13605436638acc7c010349a69c3395f1a57c642dc62Ying Wang else 13705436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (fout, "Acc"); 13805436638acc7c010349a69c3395f1a57c642dc62Ying Wang 13905436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (fout, "\", fillcolor=%s, shape=diamond, style=filled]\n", 14005436638acc7c010349a69c3395f1a57c642dc62Ying Wang color); 14105436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 14205436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 14305436638acc7c010349a69c3395f1a57c642dc62Ying Wang 14405436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic bool 14505436638acc7c010349a69c3395f1a57c642dc62Ying Wangprint_token (struct obstack *out, bool first, char const *tok) 14605436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 14705436638acc7c010349a69c3395f1a57c642dc62Ying Wang char const *q = escape (tok); 14805436638acc7c010349a69c3395f1a57c642dc62Ying Wang 14905436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (! first) 15005436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_sgrow (out, ", "); 15105436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_sgrow (out, q); 15205436638acc7c010349a69c3395f1a57c642dc62Ying Wang return false; 15305436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 15405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 15505436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid 15605436638acc7c010349a69c3395f1a57c642dc62Ying Wangoutput_red (state const *s, reductions const *reds, FILE *fout) 15705436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 15805436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset no_reduce_set; 15905436638acc7c010349a69c3395f1a57c642dc62Ying Wang int j; 16005436638acc7c010349a69c3395f1a57c642dc62Ying Wang int source = s->number; 16105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 16205436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Two obstacks are needed: one for the enabled reductions, and one 16305436638acc7c010349a69c3395f1a57c642dc62Ying Wang for the disabled reductions, because in the end we want two 16405436638acc7c010349a69c3395f1a57c642dc62Ying Wang separate edges, even though in most cases only one will actually 16505436638acc7c010349a69c3395f1a57c642dc62Ying Wang be printed. */ 16605436638acc7c010349a69c3395f1a57c642dc62Ying Wang struct obstack dout; 16705436638acc7c010349a69c3395f1a57c642dc62Ying Wang struct obstack eout; 16805436638acc7c010349a69c3395f1a57c642dc62Ying Wang 16905436638acc7c010349a69c3395f1a57c642dc62Ying Wang no_reduce_bitset_init (s, &no_reduce_set); 17005436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_init (&dout); 17105436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_init (&eout); 17205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 17305436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (j = 0; j < reds->num; ++j) 17405436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 17505436638acc7c010349a69c3395f1a57c642dc62Ying Wang bool defaulted = false; 17605436638acc7c010349a69c3395f1a57c642dc62Ying Wang bool firstd = true; 17705436638acc7c010349a69c3395f1a57c642dc62Ying Wang bool firste = true; 17805436638acc7c010349a69c3395f1a57c642dc62Ying Wang rule_number ruleno = reds->rules[j]->number; 17905436638acc7c010349a69c3395f1a57c642dc62Ying Wang rule *default_reduction = NULL; 18005436638acc7c010349a69c3395f1a57c642dc62Ying Wang 18105436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (yydefact[s->number] != 0) 18205436638acc7c010349a69c3395f1a57c642dc62Ying Wang default_reduction = &rules[yydefact[s->number] - 1]; 18305436638acc7c010349a69c3395f1a57c642dc62Ying Wang 18405436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Build the lookahead tokens lists, one for enabled transitions and one 18505436638acc7c010349a69c3395f1a57c642dc62Ying Wang for disabled transistions. */ 18605436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (default_reduction && default_reduction == reds->rules[j]) 18705436638acc7c010349a69c3395f1a57c642dc62Ying Wang defaulted = true; 18805436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (reds->lookahead_tokens) 18905436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 19005436638acc7c010349a69c3395f1a57c642dc62Ying Wang int i; 19105436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < ntokens; i++) 19205436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (bitset_test (reds->lookahead_tokens[j], i)) 19305436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 19405436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (bitset_test (no_reduce_set, i)) 19505436638acc7c010349a69c3395f1a57c642dc62Ying Wang firstd = print_token (&dout, firstd, symbols[i]->tag); 19605436638acc7c010349a69c3395f1a57c642dc62Ying Wang else 19705436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 19805436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (! defaulted) 19905436638acc7c010349a69c3395f1a57c642dc62Ying Wang firste = print_token (&eout, firste, symbols[i]->tag); 20005436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_set (no_reduce_set, i); 20105436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 20205436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 20305436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 20405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 20505436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Do the actual output. */ 20605436638acc7c010349a69c3395f1a57c642dc62Ying Wang conclude_red (&dout, source, ruleno, false, firstd, fout); 20705436638acc7c010349a69c3395f1a57c642dc62Ying Wang conclude_red (&eout, source, ruleno, true, firste && !defaulted, fout); 20805436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 20905436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_free (&dout, 0); 21005436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_free (&eout, 0); 21105436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_free (no_reduce_set); 21205436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 21305436638acc7c010349a69c3395f1a57c642dc62Ying Wang 21405436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid 21505436638acc7c010349a69c3395f1a57c642dc62Ying Wangfinish_graph (FILE *fout) 21605436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 21705436638acc7c010349a69c3395f1a57c642dc62Ying Wang fputs ("}\n", fout); 21805436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 219