Re: Graphiz (dot) output for Bison

[Paul Eggert]

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],      [],