Dog-comp

Abstract

文章介绍一个编译器的实现流程。源语言选用MiniJava. MiniJava是一个面向对象语言，支持继承，对象创建等面向对象的特性。具体语法参考Tiger book 附录。
Dog-comp是一个用golang实现的minijava编译器，目前可以将minijava翻译成c。dog-comp包括前端的lexer，parser，type-checking，codegen，后端还有基于minijava-AST的优化，基于控制流图的优化。为了满足minijava面向对象的特性，Dog-comp还带有一个runtime，实现了一个垃圾收集器。Dog-comp可以作为学习编译器和语言优化的一个小工具。

lexer

虽然目前已经有了词法分析器的生成器，但是Dog-comp使用了转移图(TDA)算法手工实现lexer。

parser

Dog-comp的parser使用LL(1)。在Exp与Stm的处理上进行了文法改写，避免了二义性。

elaborator

编译器是一个典型的现行结构，类型检查的输入就是parser的输出，也就是源语言的Ast。

codegen

在代码生成的环节，将源语言的Ast翻译成了C语言的Ast，时候将C-Ast进行打印，实际上就完成了翻译。但是，这里有几个地方需要注意。将一个面向对象的语言翻译成C这样的语言，我们需要在中间做一些变换，这些变换实际上也就是面向对象语言的实现技术。

什么是对象？

这里要说对象到底是什么。对象里面可以有数据，还可以有函数，所以我们可以说对象是数据和操作这些数据的函数的集合。换到C语言里面，对象不能仅仅用一个structure表示，这里也就出现了虚函数表的概念。我们可以将数据和一个函数表组合成一个structure，这个structure其实就是java的对象。

Flattening

所谓的平坦化，就是将java的Class全部消除。显然，在C里面，所有的函数都是平坦的。

垃圾收集器

编译生成的C文件和runtime.c一起编译成可执行文件，使得c带有垃圾收集的功能。为了支持垃圾收集，必须在c的structure里面在加入一些字段，用于GC记录对象的状态。比如需要记录这个对象中那些字段是引用，这个对象是普通对象还是数组对象等等。

优化！

Dog-comp在源码Ast级别上做了4个优化。

• 死类删除

• 死代码删除

• 代数化简

• 常量折叠

DeadClass Elimination

如上图所示，class Fac是一个根本没有被用到的类，经过死类删除之后，Fac被干掉了。

DeadCode Elimination

上图的程序包含着死代码。显然，if的else分支是不可能执行的，最后一个while也没有执行的可能。所以经过死代码删除，这两段代码会直接消失。

这里有一个问题需要注意，while(true){}和while(false){}是否应该同样对待呢？while(false)显然是死代码，但是while(true)是否应该被删除呢？答案是否定。

AlgSimp

代数化简主要是针对运算，比如i=ab0*(a+2)/m),右侧的表达式可以直接优化为0.

ConstFold

常量折叠是在编译期把常量上的运算做完。

上图的代码中有很多可以优化的地方。执行完常量折叠之后代码如下图。

这里可以观察到，进行完常量折叠之后，实际上有产生的死代码，程序可以继续优化。所以这4个优化不停循环的作，直到达到不动点为止。

CFG

控制流图是一种方便优化的中间表示。如下图就是LinkedList.java中Equal函数的控制流图。

可以使用

dog-comp/$ ./dog-comp ../test/LinkedList.java -visualize svg 生成。