“编译系统设计”课有一个作业是做一个某语言的 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 渲染成这个样子（点击查看原始大小的图片）：

我这里用了一种很不 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;
}

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

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

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

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