原文地址 實現一個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 語言中的其他特性(數組、指針、結構體)， 以及支持預處理。

未完待續……

推薦閱讀：

相关文章