[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Graphiz (dot) output for Bison
From: |
Paul Eggert |
Subject: |
Re: Graphiz (dot) output for Bison |
Date: |
Thu, 12 Oct 2006 16:38:33 -0700 |
User-agent: |
Gnus/5.1008 (Gnus v5.10.8) Emacs/21.4 (gnu/linux) |
Satya <address@hidden> writes:
> Here is a bare bones implementation (mostly a weekend hack) of graphviz
> (dot) format output for Bison.
Thanks for doing that. I stripped it down even further, by removing
layout advice and the like. On my version of dotty, omitting layout
advice caused the output to be smaller and easier to read. If this is
ugly in some other environments, we can fix this later. Also, I
changed the attributes so that the graph is black-and-white rather
than color; this works better with my monochrome printer.
I installed the following patch. Thanks again for starting the ball
rolling on this.
2006-10-12 Paul Eggert <address@hidden>
* NEWS: The -g and --graph options now output graphs in Graphviz
DOT format, not VCG format.
* doc/bison.1: Likewise.
* doc/bison.texinfo (Understanding, Bison Options): Likewise.
* THANKS: Add Satya Kiran Popuri, who proposed the initial version
of this change in
<http://lists.gnu.org/archive/html/bison-patches/2006-09/msg00158.html>.
* TODO: Remove Graphviz entry.
* src/Makefile.am (bison_SOURCES): Add graphviz.c and graphviz.h;
remove vcg.c, vcg.h, vcg_defaults.h.
* src/vcg.c, src/vcg.h, src/vcg_defaults.h: Remove.
* src/graphviz.c, src/graphviz.h: New files.
* src/files.c (compute_output_file_names): Output .dot, not .vcg.
* src/files.h: Make comment more generic.
* src/main.c (main): Likewise.
* src/print_graph.h: Likewise.
* src/getargs.c (usage): Make usage description more generic.
* src/print_graph.c: Include graphviz.h rather than vcg.h.
(static_graph, fgraph): Remove. All uses changed to pass
arguments instead of sharing a static var.
(print_core, print_actions, print_state, print_graph):
Output graphviz format rather than VCG format.
* tests/.cvsignore: Remove *.vcg; add *.dot.
* tests/output.at: Expect *.dot files, not *.vcg files.
Index: NEWS
===================================================================
RCS file: /cvsroot/bison/bison/NEWS,v
retrieving revision 1.160
diff -u -r1.160 NEWS
--- NEWS 13 Sep 2006 19:42:04 -0000 1.160
+++ NEWS 12 Oct 2006 23:29:12 -0000
@@ -1,6 +1,11 @@
Bison News
----------
+Changes in version 2.3a+ (????-??-??):
+
+* The -g and --graph options now output graphs in Graphviz DOT format,
+ not VCG format.
+
Changes in version 2.3a, 2006-09-13:
* Instead of %union, you can define and use your own union type
Index: TODO
===================================================================
RCS file: /cvsroot/bison/bison/TODO,v
retrieving revision 1.97
diff -u -r1.97 TODO
--- TODO 10 Jun 2006 03:02:22 -0000 1.97
+++ TODO 12 Oct 2006 23:29:13 -0000
@@ -310,9 +310,8 @@
I was wondering what you think about adding YYACT_PROLOGUE/EPILOGUE
to bison. If you're interested, I'll work on a patch.
-* Move to Graphviz
-Well, VCG seems really dead. Move to Graphviz instead. Also, equip
-the parser with a means to create the (visual) parse tree.
+* Better graphics
+Equip the parser with a means to create the (visual) parse tree.
-----
Index: doc/bison.1
===================================================================
RCS file: /cvsroot/bison/bison/doc/bison.1,v
retrieving revision 1.12
diff -u -r1.12 bison.1
--- doc/bison.1 10 Jun 2006 03:02:23 -0000 1.12
+++ doc/bison.1 12 Oct 2006 23:29:13 -0000
@@ -164,11 +164,11 @@
.BI \-g
.br
.ns
-Output a VCG definition of the LALR(1) grammar automaton computed by
+Output a graph of the grammar automaton computed by
Bison. If the grammar file is
.BR foo.y
-, the VCG output file will be
-.BR foo.vcg .
+, the output file will be
+.BR foo.dot .
.TP
.BI \-\-graph= graph-file
The behavior of
Index: doc/bison.texinfo
===================================================================
RCS file: /cvsroot/bison/bison/doc/bison.texinfo,v
retrieving revision 1.205
diff -u -r1.205 bison.texinfo
--- doc/bison.texinfo 11 Sep 2006 18:56:58 -0000 1.205
+++ doc/bison.texinfo 12 Oct 2006 23:29:13 -0000
@@ -6374,8 +6374,7 @@
Bison parsers are @dfn{shift/reduce automata}. In some cases (much more
frequent than one would hope), looking at this automaton is required to
tune or simply fix a parser. Bison provides two different
-representation of it, either textually or graphically (as a @acronym{VCG}
-file).
+representation of it, either textually or graphically (as a DOT file).
The textual file is generated when the options @option{--report} or
@option{--verbose} are specified, see @xref{Invocation, , Invoking
@@ -7073,10 +7072,11 @@
described under the @samp{-v} and @samp{-d} options.
@item -g
-Output a @acronym{VCG} definition of the @acronym{LALR}(1) grammar
-automaton computed by Bison. If the grammar file is @file{foo.y}, the
address@hidden output file will
-be @file{foo.vcg}.
+Output a graphical representation of the @acronym{LALR}(1) grammar
+automaton computed by Bison, in @uref{http://www.graphviz.org/, Graphviz}
address@hidden://www.graphviz.org/doc/info/lang.html, @acronym{DOT}} format.
+If the grammar file is @file{foo.y}, the output file will
+be @file{foo.dot}.
@item address@hidden
The behavior of @var{--graph} is the same than @samp{-g}. The only
@@ -8931,9 +8931,9 @@
@c LocalWords: strncmp intval tindex lvalp locp llocp typealt YYBACKUP
@c LocalWords: YYEMPTY YYEOF YYRECOVERING yyclearin GE def UMINUS maybeword
@c LocalWords: Johnstone Shamsa Sadaf Hussain Tomita TR uref YYMAXDEPTH
address@hidden LocalWords: YYINITDEPTH stmnts ref stmnt initdcl maybeasm VCG
notype
address@hidden LocalWords: YYINITDEPTH stmnts ref stmnt initdcl maybeasm notype
@c LocalWords: hexflag STR exdent itemset asis DYYDEBUG YYFPRINTF args
address@hidden LocalWords: infile ypp yxx outfile itemx vcg tex leaderfill
address@hidden LocalWords: infile ypp yxx outfile itemx tex leaderfill
@c LocalWords: hbox hss hfill tt ly yyin fopen fclose ofirst gcc ll
@c LocalWords: yyrestart nbar yytext fst snd osplit ntwo strdup AST
@c LocalWords: YYSTACK DVI fdl printindex
--- THANKS.~1.69.~ 2006-10-12 15:30:01.000000000 -0700
+++ THANKS 2006-10-12 16:33:36.000000000 -0700
@@ -69,6 +69,7 @@ R Blake address@hidden
Raja R Harinath address@hidden
Richard Stallman address@hidden
Robert Anisko address@hidden
+Satya Kiran Popuri address@hidden
Shura address@hidden
Steve Murphy address@hidden
Tim Josling address@hidden
Index: src/Makefile.am
===================================================================
RCS file: /cvsroot/bison/bison/src/Makefile.am,v
retrieving revision 1.71
diff -u -r1.71 Makefile.am
--- src/Makefile.am 15 Sep 2006 18:59:40 -0000 1.71
+++ src/Makefile.am 12 Oct 2006 23:29:13 -0000
@@ -65,8 +65,7 @@
system.h \
tables.h tables.c \
uniqstr.c uniqstr.h \
- vcg.c vcg.h \
- vcg_defaults.h
+ graphviz.c graphviz.h
EXTRA_bison_SOURCES = scan-code.l scan-skel.l scan-gram.l
Index: src/graphviz.c
===================================================================
RCS file: src/graphviz.c
diff -N src/graphviz.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ src/graphviz.c 12 Oct 2006 23:29:13 -0000
@@ -0,0 +1,66 @@
+/* Output Graphviz specification of a state machine generated by Bison.
+
+ Copyright (C) 2006 Free Software Foundation, Inc.
+
+ This file is part of Bison, the GNU Compiler Compiler.
+
+ Bison is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+
+ Bison is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with Bison; see the file COPYING. If not, write to
+ the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ Boston, MA 02110-1301, USA. */
+
+/* Written by Paul Eggert and Satya Kiran Popuri. */
+
+#include <config.h>
+#include "system.h"
+
+#include <quotearg.h>
+
+#include "graphviz.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 *
+quote (char const *name)
+{
+ return quotearg_n_style (2, c_quoting_style, name);
+}
+
+void
+start_graph (FILE *fout)
+{
+ fputs ("digraph Automaton{\n", fout);
+}
+
+void
+output_node (int id, char const *label, FILE *fout)
+{
+ fprintf (fout, "%d[label=%s]\n", id, quote (label));
+}
+
+void
+output_edge (int source, int destination, char const *label,
+ char const *style, FILE *fout)
+{
+ fprintf (fout, "%d->%d[style=%s", source, destination, style);
+ if (label)
+ fprintf (fout, " label=%s", quote (label));
+ fputs ("]\n", fout);
+}
+
+void
+finish_graph (FILE *fout)
+{
+ fputs ("}\n", fout);
+}
Index: src/graphviz.h
===================================================================
RCS file: src/graphviz.h
diff -N src/graphviz.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ src/graphviz.h 12 Oct 2006 23:29:13 -0000
@@ -0,0 +1,7 @@
+#include <stdbool.h>
+
+void start_graph (FILE *fout);
+void output_node (int id, char const *label, FILE *fout);
+void output_edge (int source, int destination, char const *label,
+ char const *style, FILE *fout);
+void finish_graph (FILE *fout);
Index: src/files.c
===================================================================
RCS file: /cvsroot/bison/bison/src/files.c,v
retrieving revision 1.96
diff -u -r1.96 files.c
--- src/files.c 9 Jul 2006 03:44:51 -0000 1.96
+++ src/files.c 12 Oct 2006 23:29:13 -0000
@@ -323,7 +323,7 @@
if (graph_flag)
{
if (! spec_graph_file)
- spec_graph_file = concat2 (all_but_tab_ext, ".vcg");
+ spec_graph_file = concat2 (all_but_tab_ext, ".dot");
name[names++] = spec_graph_file;
}
Index: src/files.h
===================================================================
RCS file: /cvsroot/bison/bison/src/files.h,v
retrieving revision 1.40
diff -u -r1.40 files.h
--- src/files.h 2 Oct 2005 17:44:49 -0000 1.40
+++ src/files.h 12 Oct 2006 23:29:13 -0000
@@ -1,5 +1,7 @@
/* File names and variables for bison,
- Copyright (C) 1984, 1989, 2000, 2001, 2002 Free Software Foundation, Inc.
+
+ Copyright (C) 1984, 1989, 2000, 2001, 2002, 2006 Free Software
+ Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
@@ -38,7 +40,7 @@
/* --verbose. */
extern char const *spec_verbose_file;
-/* File name specified for the output VCG graph. */
+/* File name specified for the output graph. */
extern char const *spec_graph_file;
/* File name specified with --defines. */
Index: src/main.c
===================================================================
RCS file: /cvsroot/bison/bison/src/main.c,v
retrieving revision 1.89
diff -u -r1.89 main.c
--- src/main.c 15 Sep 2006 18:59:40 -0000 1.89
+++ src/main.c 12 Oct 2006 23:29:13 -0000
@@ -137,7 +137,7 @@
timevar_pop (TV_REPORT);
}
- /* Output the VCG graph. */
+ /* Output the graph. */
if (graph_flag)
{
timevar_push (TV_GRAPH);
Index: src/print_graph.h
===================================================================
RCS file: /cvsroot/bison/bison/src/print_graph.h,v
retrieving revision 1.4
diff -u -r1.4 print_graph.h
--- src/print_graph.h 14 May 2005 06:49:48 -0000 1.4
+++ src/print_graph.h 12 Oct 2006 23:29:13 -0000
@@ -1,5 +1,6 @@
-/* Output a VCG description on generated parser, for bison,
- Copyright 2000 Free Software Foundation, Inc.
+/* Output a graph of the generated parser, for Bison.
+
+ Copyright 2000, 2006 Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
Index: src/getargs.c
===================================================================
RCS file: /cvsroot/bison/bison/src/getargs.c,v
retrieving revision 1.80
diff -u -r1.80 getargs.c
--- src/getargs.c 20 Sep 2006 20:04:28 -0000 1.80
+++ src/getargs.c 12 Oct 2006 23:29:13 -0000
@@ -274,7 +274,7 @@
-v, --verbose same as `--report=state'\n\
-b, --file-prefix=PREFIX specify a PREFIX for output files\n\
-o, --output=FILE leave output to FILE\n\
- -g, --graph also produce a VCG description of the automaton\n\
+ -g, --graph also output a graph of the automaton\n\
\n\
"), stdout);
Index: src/print_graph.c
===================================================================
RCS file: /cvsroot/bison/bison/src/print_graph.c,v
retrieving revision 1.61
diff -u -r1.61 print_graph.c
--- src/print_graph.c 10 Jun 2006 03:02:23 -0000 1.61
+++ src/print_graph.c 12 Oct 2006 23:29:13 -0000
@@ -1,6 +1,7 @@
-/* Output a VCG description on generated parser, for Bison,
+/* Output a graph of the generated parser, for Bison.
- Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 Free Software
+ Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
@@ -31,15 +32,12 @@
#include "files.h"
#include "getargs.h"
#include "gram.h"
+#include "graphviz.h"
#include "lalr.h"
#include "print_graph.h"
#include "reader.h"
#include "state.h"
#include "symtab.h"
-#include "vcg.h"
-
-static graph static_graph;
-static FILE *fgraph = NULL;
/*----------------------------.
@@ -61,7 +59,7 @@
snritems = nritemset;
}
- obstack_fgrow1 (oout, "state %2d\n", s->number);
+ obstack_fgrow1 (oout, "%d", s->number);
for (i = 0; i < snritems; i++)
{
item_number *sp;
@@ -75,10 +73,7 @@
r = item_number_as_rule_number (*sp);
- if (i)
- obstack_1grow (oout, '\n');
- obstack_fgrow1 (oout, " %s -> ",
- rules[r].lhs->tag);
+ obstack_fgrow1 (oout, "\n%s -> ", rules[r].lhs->tag);
for (sp = rules[r].rhs; sp < sp1; sp++)
obstack_fgrow1 (oout, "%s ", symbols[*sp]->tag);
@@ -120,17 +115,13 @@
`---------------------------------------------------------------*/
static void
-print_actions (state *s, const char *node_name)
+print_actions (state const *s, FILE *fgraph)
{
int i;
- transitions *trans = s->transitions;
- reductions *reds = s->reductions;
-
- static char buff[10];
- edge e;
+ transitions const *trans = s->transitions;
- if (!trans->num && !reds)
+ if (!trans->num && !s->reductions)
return;
for (i = 0; i < trans->num; i++)
@@ -139,23 +130,18 @@
state *s1 = trans->states[i];
symbol_number sym = s1->accessing_symbol;
- new_edge (&e);
-
- if (s->number > s1->number)
- e.type = back_edge;
- open_edge (&e, fgraph);
- /* The edge source is the current node. */
- e.sourcename = node_name;
- sprintf (buff, "%d", s1->number);
- e.targetname = buff;
- /* Shifts are blue, gotos are green, and error is red. */
- if (TRANSITION_IS_ERROR (trans, i))
- e.color = red;
- else
- e.color = TRANSITION_IS_SHIFT (trans, i) ? blue : green;
- e.label = symbols[sym]->tag;
- output_edge (&e, fgraph);
- close_edge (fgraph);
+ /* Shifts are solid, gotos are dashed, and error is dotted. */
+ char const *style =
+ (TRANSITION_IS_ERROR (trans, i) ? "dotted"
+ : TRANSITION_IS_SHIFT (trans, i) ? "solid"
+ : "dashed");
+
+ if (TRANSITION_IS_ERROR (trans, i)
+ && strcmp (symbols[sym]->tag, "error") != 0)
+ abort ();
+ output_edge (s->number, s1->number,
+ TRANSITION_IS_ERROR (trans, i) ? NULL : symbols[sym]->tag,
+ style, fgraph);
}
}
@@ -166,29 +152,19 @@
`-------------------------------------------------------------*/
static void
-print_state (state *s)
+print_state (state *s, FILE *fgraph)
{
- static char name[10];
struct obstack node_obstack;
- node n;
- /* The labels of the nodes are their the items. */
+ /* A node's label contains its items. */
obstack_init (&node_obstack);
- new_node (&n);
- sprintf (name, "%d", s->number);
- n.title = name;
print_core (&node_obstack, s);
obstack_1grow (&node_obstack, '\0');
- n.label = obstack_finish (&node_obstack);
-
- open_node (fgraph);
- output_node (&n, fgraph);
- close_node (fgraph);
+ output_node (s->number, obstack_finish (&node_obstack), fgraph);
+ obstack_free (&node_obstack, 0);
/* Output the edges. */
- print_actions (s, name);
-
- obstack_free (&node_obstack, 0);
+ print_actions (s, fgraph);
}
@@ -196,32 +172,15 @@
print_graph (void)
{
state_number i;
-
- /* Output file. */
- fgraph = xfopen (spec_graph_file, "w");
-
- new_graph (&static_graph);
-
- static_graph.display_edge_labels = yes;
-
- static_graph.port_sharing = no;
- static_graph.finetuning = yes;
- static_graph.priority_phase = yes;
- static_graph.splines = yes;
-
- static_graph.crossing_weight = median;
-
- /* Output graph options. */
- open_graph (fgraph);
- output_graph (&static_graph, fgraph);
+ FILE *fgraph = xfopen (spec_graph_file, "w");
+ start_graph (fgraph);
/* Output nodes and edges. */
new_closure (nritems);
for (i = 0; i < nstates; i++)
- print_state (states[i]);
+ print_state (states[i], fgraph);
free_closure ();
- /* Close graph. */
- close_graph (&static_graph, fgraph);
+ finish_graph (fgraph);
xfclose (fgraph);
}
Index: tests/.cvsignore
===================================================================
RCS file: /cvsroot/bison/bison/tests/.cvsignore,v
retrieving revision 1.11
diff -u -r1.11 .cvsignore
--- tests/.cvsignore 14 Mar 2003 01:31:24 -0000 1.11
+++ tests/.cvsignore 12 Oct 2006 23:29:13 -0000
@@ -1,4 +1,5 @@
-*.output *.vcg
+*.dot
+*.output
atconfig
atlocal
autom4te.cache
Index: tests/output.at
===================================================================
RCS file: /cvsroot/bison/bison/tests/output.at,v
retrieving revision 1.10
diff -u -r1.10 output.at
--- tests/output.at 22 Jan 2006 07:38:49 -0000 1.10
+++ tests/output.at 12 Oct 2006 23:29:13 -0000
@@ -1,5 +1,5 @@
# Checking the output filenames. -*- Autotest -*-
-# Copyright (C) 2000, 2001, 2002, 2005 Free Software Foundation, Inc.
+# Copyright (C) 2000, 2001, 2002, 2005, 2006 Free Software Foundation, Inc.
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
@@ -53,7 +53,7 @@
AT_CHECK_OUTPUT([foo.y], [], [-dv -b bar],
[bar.output bar.tab.c bar.tab.h])
AT_CHECK_OUTPUT([foo.y], [], [-dv -g -o foo.c],
- [foo.c foo.h foo.output foo.vcg])
+ [foo.c foo.dot foo.h foo.output])
AT_CHECK_OUTPUT([foo.y], [%defines %verbose], [],
- Re: Graphiz (dot) output for Bison,
Paul Eggert <=