原文链接 http://woodrat.xyz/2017/04/09/%E4%BD%BF%E7%94%A8%20PLY%20%E4%B8%8E%20LLVM%20%E5%AE%9E%E7%8E%B0%E4%B8%80%E4%B8%AAC%E8%AF%AD%E8%A8%80%E5%AD%90%E9%9B%86%E7%9A%84%E7%BC%96%E8%AF%91%E5%99%A8/
注：以下为加速网络访问所做的原文缓存，经过重新格式化，可能存在格式方面的问题，或偶有遗漏信息，请以原文为准。
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)
8
在前端划分好基本块再生成代码就没有之前的问题了，不足的就是目前的划分代码不完善，生成的中间代码有冗余，也没有做死代码消除等优化。 不过不影响流程。
加上了目标文件生成功能，并且将后端编译为 .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\n", fuck());
return 0;
}
输出如下
$ python2 compiler.py tests/test3.ns fuck.o
$ clang main.c fuck.o -o main
$ ./main
11
目前为止还剩下 支持多种类型，支持 extern 声明(用以调用其他模块中的函数，如 glibc 中的函数)，支持 C 语言中的其他特性(数组、指针、结构体)， 以及支持预处理。
未完待续......