用 Graphviz 来做图的 Visualization

June 11, 2008 – 12:18 am

graphviz“编译系统设计”课有一个作业是做一个某语言的 parser ,生成一棵语法树,并用合适的方法把这棵语法树显示出来。我用 Graphviz 来做了 visualization 的部分。这是一个用来做图的 visualization 的很方便的工具,语法树作为一棵树,其实是一个有向无环图了,所以用这个来做其实也是很方便的。

其实作业主要分为两个部分:分析和 visualization 。“某语言”可以是自己定义的,我一开始想做 Scheme 的语法分析,不过后来想想还是算了,那个实在是太简单了,恐怕到时候助教不让过。题目要求用 YACC 或者递归下降的方式进行分析。YACC 我还不会用(暂时也没有要学的打算),所以我用 Treetop 来做 parser ,Treetop 是使用 PEG 进行分析的,其实和传统的递归下降是很像的了。

另一部分是 visualization ,其实应该直接在终端里以不同缩进的方式显示出来也是可以的,但是如果树比较大的画,看起来就不方便了。另一方面,要我自己去在一个 GUI 上手工“画”一棵树出来我肯定是不会同意的。而且不知道从什么时候开始,我已经对做传统的桌面 GUI 程序有一种逆反心理了。而既然 parser 选择了 Ruby 的 Treetop ,于是就理所当然地用 Ruby on Rails 做成一个 Web app 了。

我首先用 Treetop 把源代码分析成 sexp 的形式,这是一个类 C 的语法,下面是一个例子:

 
function gcd(int m, int n):int
{
    int r;
 
    r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}
 
function main():void
{
    int a;
    int b;
    print("input two integers:");
    a = read_int();
    b = read_int();
    printf("gcd of %d and %d is %d",
           a, b, gcd(a, b));
}

分析成如下的 sexp

[[:defun,
  [:symbol, "gcd"],
  [[[:symbol, "m"], [:type, "int"]], [[:symbol, "n"], [:type, "int"]]],
  [:type, "int"],
  [[:defvar, [:symbol, "r"], [:type, "int"]],
   [:assign,
    [:symbol, "r"],
    [:binary_expression, "%", [:symbol, "a"], [:symbol, "b"]]],
   [:while,
    [:binary_expression, "!=", [:symbol, "r"], [:number, 0]],
    [[:assign, [:symbol, "a"], [:symbol, "b"]],
     [:assign, [:symbol, "b"], [:symbol, "r"]],
     [:assign,
      [:symbol, "r"],
      [:binary_expression, "%", [:symbol, "a"], [:symbol, "b"]]]]],
   [:return, [:symbol, "b"]]]],
 [:defun,
  [:symbol, "main"],
  [],
  [:type, "void"],
  [[:defvar, [:symbol, "a"], [:type, "int"]],
   [:defvar, [:symbol, "b"], [:type, "int"]],
   [:funcall, [:symbol, "print"], [[:string, "input two integers:"]]],
   [:assign, [:symbol, "a"], [:funcall, [:symbol, "read_int"], []]],
   [:assign, [:symbol, "b"], [:funcall, [:symbol, "read_int"], []]],
   [:funcall,
    [:symbol, "printf"],
    [[:string, "gcd of %d and %d is %d"],
     [:symbol, "a"],
     [:symbol, "b"],
     [:funcall, [:symbol, "gcd"], [[:symbol, "a"], [:symbol, "b"]]]]]]]]

最后用 Graphviz 渲染成这个样子(点击查看原始大小的图片):


gcd_thumb.png

我这里用了一种很不 OO 的做法:就是把语法树表达为平凡的 list + symbol 的 sexp 的形式。封装得更好的形式应该是产生出一棵由各种对象节点构成的语法树,每个节点都能把自己渲染出来。但是实际上哪种做法更好还有待讨论,而且这作为一种 ad hoc 的方式,对于快速完成作业来说是非常有帮助的。 :p 我还有一点偷懒没有做的地方就是让生成出来的图片不要变得太宽,我不确信 Graphviz 是否提供了这样的控制,不过我想如果要做的话,即使 Graphviz 本身没有提供支持,其实也是可以通过一些 workaround 来实现的,比如添加一些隐藏的(白色或者透明)的边来影响树的形状等,但是这样也许会比较麻烦了。

用 Graphviz 来画图最方便的就是用使用它提供的 dot 语言了。例如,这样一段代码:

digraph  G  {
    main  [shape=box];      /*  this  is  a  comment  */
    main  ->  parse  [weight=8];
    parse  ->  execute;
    main  ->  init  [style=dotted];
    main  ->  cleanup;
    execute  ->  {  make_string;  printf}
    init  ->  make_string;
    edge  [color=red];      //  so  is  this
    main  ->  printf  [style=bold,label="100  times"];
    make_string  [label="make  a\nstring"];
    node  [shape=box,style=filled,color=".7  .3  1.0"];
    execute  ->  compare;
}

就可以画出下面这样一幅图:

dot_lang.png

Graphviz 也有各种语言的接口,我在 Debian 上也找到一个 libgv-ruby ,不过由于我要 deploy rails 的那个 server 是 Arch Linux ,没有这个包,所以我还是决定使用直接通过 sexp 生成 dot 文件再调用 dot 命令生成图片的方式。实践证明作为一个课程作业足够了。 :)

如果要做更华丽的 visualization 的话,还有一个工具就是 Ubigraph,可以做出很炫的 3D 动画来,比如它主页上的这个 demo

ps: Ubigraph 的主页也是用 blueprint 做的(一下子就能看出来 :p ),想起来前几天和 blueprint 相关的那次惊魂,现在还有些后怕呢,呵呵!

  1. 6 Responses to “用 Graphviz 来做图的 Visualization”

  2. Graphviz在节点少的时候生成的图很不错。多了以后就没法看了(会生成一张特别宽扁的图)。觉得它在节点的安排上如果能多提供一些选项就好了。

    By yawl on Jun 11, 2008

  3. @yawl,
    看样子是没有这样的选项了。不过我想可以在某一个叶节点添加一个隐藏的边指向另一棵子树的根节点,把它强行拉下来。不过这种做法我也没有试过,应该是非常不具有可移植性而且很容易出问题又不好维护的了。 :p

    By pluskid on Jun 11, 2008

  4. Graphviz 的布局控制还是太不灵活了点,节点和边较多的非树状图里经常会出现很不舒服的重叠和交叉。不过对于简单的图确实非常方便。

    By Rhythm on Jun 11, 2008

  5. @Rhythm,
    是它的算法不好吗?不知道这方面的工具还有没有其他更好用的了?

    By pluskid on Jun 11, 2008

  6. 我上编译的时候,老师给了我们一个tcl/tk的脚本
    把语法树搞成lisp那样,不要有换行
    (e (e (t (f (ID x )))) (PLUS + ) (t (t (f (ID y ))) (TIMES * ) (f (LPAREN \( ) (e (t (f (ID z )))) (RPAREN \) ))))

    然后用那个脚本,就输出语法树了
    样子么也就是那样,也不丑,不过没有Graphviz华丽
    优点就是图是画在窗口上的,太宽的话有scroll bar

    这里也不能帖图,要看效果的话来我这里吧

    那个脚本在这里
    http://www.cs.sfu.ca/~anoop/distrib/viewtree

    By Chunhao on Jun 14, 2008

  7. @Chunhao,
    呵呵~这个倒是不错,让学生 focus 到主要的部分,国内和国外的教学方法果然是有差距啊。不过我觉得即使自己用那个脚本,在机房那种机器上,也不会有 TCL/Tk 预先装好的吧? :(

    By pluskid on Jun 14, 2008

Post a Comment