原文地址 实现一个C语言子集的玩具编译器

1

之前的项目里做了很多跟 DSL 有关的工作，加上某天在 HackerNews 上看到了how-i-wrote-a-self-hosting-c-compiler-in-40-days 这篇文章，于是又燃起了动手写个玩具编译器的想法。

回想起在学校的时候，曾经多次想尝试写一个编译器或者解释器，都因为水平不够都夭折了。

总结了一下过去的失败经验，一开始就想自己从头开始徒手写一个完整编译器的难度太高，首先在前端解析这里就会花费大量的精力， 很难坚持下去。 更何况作为一个 1096 的炮灰开发，根本挤不出这么多精力。 而且时间过去了这么久，当初学的理论知识也已经差不多忘光了。

于是索性决定前后端都用现成框架，只要最后能跑就行。毕竟写代码最重要的就是开心。

去 Github 上找了一个叫 PLY 的库，就是 Python 版的 lex 和 yacc， 后端毫无疑问的选择了 LLVM，毕竟大家用过都说好。

然后一想，反正都偷懒了，后端干脆也用 Python 写算了，以前看过一个叫 numba 的项目, 自己维护了一个叫 llvmlite 的 LLVM Python 绑定，看起来还不错。于是就拿 PLY 和 llvmlite 开始搞了。

以前在学校上编译原理课的时候写过一个玩具编译器前端 ，支持一种叫 TEST 的简易语言，当时没能把后端一起写完，现在只需要把前端改成 PLY 的形式，在加上代码生成就搞定了。

于是信心满满的写了一堆 TODO，想著星期天不加班的时候就可以搞定了。

2

花了几天把TEST语言的前端转成了 PLY 的形式，并且也把 AST 写好了，但是觉得有很多地方写的有问题。 请教了同事后，同事推荐了一个叫 pycparser 的基于 PLY 解析 C 语言的库, 花了几天时间研究了下，然后结合 language-implementation-patterns，重构了生成的 AST 类。 将原本递归调用每个 class 中的 Serialize 函数改为基于 Visitor 模式来调用，并添加了简单的语义检查。

动手写后端的时候发现， llvmlite 看起来很美好，但是和 LLVM 版本的是绑定的，而且很多地方缺少文档。 想起最近写引擎的经验，决定干脆前端用 PLY 解析出 AST 后序列化传给 C++， C++ 反序列化出 AST 后再调用 LLVM API 来生成代码。

之前的项目里用到过一个叫 structure.py 的序列化库，因为以后可能还需要用到，就选它来练练手，放弃了 pb 之类的框架。

3

中途过年回家玩了两个星期，花了几天时间重新找回了写代码的状态。

按照之前的计划开始写 C++ 读取序列化文件的模块，跟 Python 比起来写 C++ 真的太痛苦了。 虽然工作中也需要用到 C++，如果可以选的话我还是愿意用 Python，就算是 C 或者 Go 用起来都比 C++ 舒服很多。

周末的时间太少，调一个 C++ 的 bug 基本就过完一天了。进度有些缓慢。 不过，想清楚序列化不过是结构体套结构体而已，也不是那么复杂。

序列化 AST 的时候，一个需要注意的地方有几个:

• 需要单独写一个字元串表， 其他类里的字元串在序列化的时候都得转换成数字ID（在字元串中的索引）
• 每个结构体需要有一个固定位置的值来确定类型
• 如果是一个结构体中有一个数组类型的栏位，该栏位中填入的每个结构体都得带上一个栏位写明该结构的大小。
• 序列化与反序列化需要按照同样的位元组类型，如在 structure.py 中，< 符号表示按小端的位元组类型生成， C++ 载入时需要用到 GCC 的 __attribute__((packed)) 扩展。

4

参照 LLVM 的官方文档 Implementing a Language with LLVM， 实现了 TEST 语言的部分特性的代码生成（生成 LLVM IR）。但是只能通过 LLVM 的 dump API 列印，还不能跑。

TEST 语言是一个很简陋的仿 C 语言，大概长的像这样：

{
int i;
int abc;
read(abc);
for(i=1; i< 10; i = i+1)
{
abc = abc + 1;
}
write(abc);
}


只支持最基本的代码块、声明、赋值、循环语句（Control Flow），以及内置的两个函数(read, write)。 目前为止，我只实现了前3个功能，控制流和函数调用比较复杂，暂时没有实现。

转念一想，反正都写到这里了，不如按照 C 语言的语法多支持一些特性。 比如支持函数，函数调用，条件语句（if/else)等。

5

按照之前的计划前端支持了函数，if 语句， while 语句。

但是又遇到了几个新的问题：

• 之前的声明和赋值是通过一个全局的符号表，遇到声明就创建符号，遇到赋值就将值插入符号表， 遇到使用符号时就从符号表中取出对应符号的值。但是这么做其实没有真正在运行时支持变数， 应该按照 LLVM 标准按使用 store/load 指令的方式来生产代码。
• 在 X86 32位下，函数调用的方式是通过 caller 将参数压栈， callee 去栈中对应位置取出参数。 在 64 位下，寄存器够用的情况会优先使用寄存器来传参。对应 LLVM 模型，也应该使用 store/load 指令。 介于之前没有支持，现在无法支持带参数的函数调用。
• TEST 语言中没有实现 return 语句，默认最外层就是一个代码块，我给最外层添加了一个匿名函数， 并且把代码块最后一条语句的返回的 Value 作为函数的返回值返回了。要支持函数就得支持 return 语句。

6

实现了函数定义，以及变数的支持，这两部分参考 LLVM 文档一步步搞就行，没有遇到过大的问题。 在添加 if 和 break continue 语句后，才发现之前的设计是直接从 AST 生成代码，没有考虑到基本快划分的问题。

于是想了一个比较 low 的方案。

在生成 While 语句时先将 Loop Start 和 Loop End 两个标签添加到一个结构体中，并压栈。 如果在 StatementList 中遇到 Break Continue 以及 Return 的时候停止后面的代码生成， 并按栈顶中的标签生成对应的跳转(Break 跳到 Loop End， Continue 跳到 Loop Start)。 解析完 While 后将结构体从栈中弹出。

因为 If 语句会生成 3 个标签(THEN ELSE ENDIF), 并且在 THEN 和 ELSE 中需要添加一个跳转语句 到 ENDIF ， 如果 THEN 和 ELSE 的 StatementList 中有 Break Continue 或 Retrun 则不生成这个跳转。

7

之前的临时方案问题比较多，于是重新在 Python 前端添加了划分基本块的功能，参考 https://en.wikipedia.org/wiki/Basic_block.

• 一个基本块只有一个 Entry Point，只能由其他某个地方的 jmp 指令跳转到本基本块
• 一个基本块只有一个 Exit Point， 意味著基本块中最后一条指令将跳转到其他某个基本块中， 并且中间不能有跳转指令（可以有 call 指令）
• 基本块中的指令按顺序从上往下执行
• 基本块中，两条指令之间不能有其他操作

需要将 AST 中 IF 和 While 节点替换成 比较，跳转、Labal 等节点。

原来的 Visitor class 是从 pycparser 中拿过来的，不支持访问父节点动态修改 AST 树。

class NodeVisitor(object): def visit(self, node):
method = visit_ + node.__class__.__name__
visitor = getattr(self, method, self.generic_visit)
return visitor(node)

def generic_visit(self, node): for c in node.children():
self.visit(c)

想了一个比较取巧的方法，因为 Visitor class 遍历整棵树时， 访问子节点之前肯定是先访问了父节点再调用 visit 函数的，所以只用在 visit 函数里加上一个 parent 参数， 在父节点调用 visit 函数时将本节点作为参数传入即可。

class SpecialVisitor(object): def visit(self, node, parent):
method = visit_ + node.__class__.__name__
visitor = getattr(self, method, self.generic_visit)
# deep first for c in node.children():
self.visit(c, node)
return visitor(node, parent)

def generic_visit(self, node, parent): for c in node.children():
self.visit(c, node)

在前端划分好基本块再生成代码就没有之前的问题了，不足的就是目前的划分代码不完善，生成的中间代码有冗余，也没有做死代码消除等优化。 不过不影响流程。

加上了目标文件生成功能，并且将后端编译为 .so 动态链接库， 在 Python 端由 ctypes 调用。

示例 test3.ns

int fuck() {
int i;
i = 1;
while(1) {
i = i + 1;
if (i > 10) {
break;
}
}
return i;
}


调用 clang -Xclang -ast-dump -fsyntax-only 解析出的 AST 如下
TranslationUnitDecl 0x22d3880 <<invalid sloc>> <invalid sloc>
|-TypedefDecl 0x22d3dc8 <<invalid sloc>> <invalid sloc> implicit __int128_t __int128
| `-BuiltinType 0x22d3af0 __int128
|-TypedefDecl 0x22d3e28 <<invalid sloc>> <invalid sloc> implicit __uint128_t unsigned __int128
| `-BuiltinType 0x22d3b10 unsigned __int128
|-TypedefDecl 0x22d40e8 <<invalid sloc>> <invalid sloc> implicit __NSConstantString struct __NSConstantString_tag
| `-RecordType 0x22d3f00 struct __NSConstantString_tag
| `-Record 0x22d3e78 __NSConstantString_tag
|-TypedefDecl 0x22d4178 <<invalid sloc>> <invalid sloc> implicit __builtin_ms_va_list char *
| `-PointerType 0x22d4140 char *
| `-BuiltinType 0x22d3910 char
|-TypedefDecl 0x22d4428 <<invalid sloc>> <invalid sloc> implicit __builtin_va_list struct __va_list_tag [1]
| `-ConstantArrayType 0x22d43d0 struct __va_list_tag [1] 1
| `-RecordType 0x22d4250 struct __va_list_tag
| `-Record 0x22d41c8 __va_list_tag
`-FunctionDecl 0x22d44c8 <tmp.c:1:1, line:12:1> line:1:5 fuck int ()
`-CompoundStmt 0x232b4e8 <line:2:1, line:12:1>
|-DeclStmt 0x232b1e0 <line:3:2, col:7>
| `-VarDecl 0x232b180 <col:2, col:6> col:6 used i int
|-BinaryOperator 0x232b240 <line:4:2, col:6> int =
| |-DeclRefExpr 0x232b1f8 <col:2> int lvalue Var 0x232b180 i int
| `-IntegerLiteral 0x232b220 <col:6> int 1
|-WhileStmt 0x232b470 <line:5:2, line:10:5>
| |-<<<NULL>>>
| |-IntegerLiteral 0x232b268 <line:5:8> int 1
| `-CompoundStmt 0x232b448 <col:11, line:10:5>
| |-BinaryOperator 0x232b338 <line:6:9, col:17> int =
| | |-DeclRefExpr 0x232b288 <col:9> int lvalue Var 0x232b180 i int
| | `-BinaryOperator 0x232b310 <col:13, col:17> int +
| | |-ImplicitCastExpr 0x232b2f8 <col:13> int <LValueToRValue>
| | | `-DeclRefExpr 0x232b2b0 <col:13> int lvalue Var 0x232b180 i int
| | `-IntegerLiteral 0x232b2d8 <col:17> int 1
| `-IfStmt 0x232b410 <line:7:3, line:9:6>
| |-<<<NULL>>>
| |-<<<NULL>>>
| |-BinaryOperator 0x232b3c0 <line:7:7, col:11> int >
| | |-ImplicitCastExpr 0x232b3a8 <col:7> int <LValueToRValue>
| | | `-DeclRefExpr 0x232b360 <col:7> int lvalue Var 0x232b180 i int
| | `-IntegerLiteral 0x232b388 <col:11> int 10
| |-CompoundStmt 0x232b3f0 <col:15, line:9:6>
| | `-BreakStmt 0x232b3e8 <line:8:7>
| `-<<<NULL>>>
`-ReturnStmt 0x232b4d0 <line:11:2, col:9>
`-ImplicitCastExpr 0x232b4b8 <col:9> int <LValueToRValue>
`-DeclRefExpr 0x232b490 <col:9> int lvalue Var 0x232b180 i int

PLY 前端生成的 AST 如下

AST:
FuncList:
Function: return_type=int
MethodSymbol: name=fuck
DeclarationList:
CodeBlock:
DeclarationList:
Declaration: _type=int
VariableSymbol: name=i
StmtList:
AssignmentStmt:
AssignmentExpr:
VariableSymbol: name=i
Const: val=1
WhileStmt:
Const: val=1
StmtList:
AssignmentStmt:
AssignmentExpr:
VariableSymbol: name=i
BinaryOp: op=+
VariableSymbol: name=i
Const: val=1
IfStmt:
BinaryOp: op=>
VariableSymbol: name=i
Const: val=10
StmtList:
BreakStmt:
ReturnStmt:
VariableSymbol: name=i

生成的 LLVM IR 如下

define i32 @fuck() {
entry:
%i = alloca i32
store i32 1, i32* %i
br i1 true, label %L4, label %L5

L4: ; preds = %L3, %entry %i1 = load i32, i32* %i %addtmp = add i32 %i1, 1
store i32 %addtmp, i32* %i %i2 = load i32, i32* %i %cmptmp = icmp ugt i32 %i2, 10 %0 = zext i1 %cmptmp to i32
%1 = icmp ne i32 %0, 0
br i1 %1, label %L1, label %L2

L1: ; preds = %L4
br label %L5

L2: ; preds = %L4
br label %L3

L3: ; preds = %L2
br i1 true, label %L4, label %L5

L5: ; preds = %L3, %L1, %entry %i3 = load i32, i32* %i
ret i32 %i3
}

将生成的目标文件与 main.c 一起编译

main.c

#include <stdio.h> extern int fuck(void);

int main() {
printf("%d
", fuck());
return 0;
}

输出如下
$ python2 compiler.py tests/test3.ns fuck.o
$ clang main.c fuck.o -o main
$ ./main
11

目前为止还剩下 支持多种类型，支持 extern 声明(用以调用其他模块中的函数，如 glibc 中的函数)，支持 C 语言中的其他特性(数组、指针、结构体)， 以及支持预处理。

未完待续……

推荐阅读：

相关文章