- 2021.7.1 突发奇想 “建党 100 周年!写一个名为 CPC 的 C 编译器,为党庆生!”
- C代码 tokenize -> symbol table
- parse & generate -> VM instructions
- run VM & 执行生成好的 instructions
思路来自于著名的 C4,一个 500 行的可自举的 C 编译器.
我这个行数目测要超过 1000 行,anyway,just for fun.
最终,我只用了 700 行!GOODJOB!代码漂亮易读,哈哈。
最核心的代码其实是两个函数:
- run_vm : 执行指令,依赖 init_vm
- parse : 将 C 代码解析为指令,核心依赖 parse_fun/parse_stmt/parse_expr
整个实现原理已制作成B站视频
虚拟机的内存包含三块空间
- code // 存储指令(以及指令所需要的参数),pc 从 0 开始
- data // 存储全局变量和常量,从小到大
- stack // 栈空间,从大到小(由于这三块内存我们是分别存储的,所以stack并非一定要从大到小,只是习惯而已)
- pc // 代码计数器,也就是 code 区域的指针,每步都是执行 pc 所指向的指令
- sp // stack pointer, 栈指针
- bp // base pointer,上一个栈的指针
- ax // 通用寄存器,保存指令要用的数据,返回值也会保存在这里
指令集一共有 4 大类
- Save&Load:在寄存器和内存中间传递数据
- IMM, LEA, PUSH, LC, LI, SC, SI
- 四则运算、逻辑运算、位运算
- OR, XOR, AND, EQ, NE, LT, GT, LE, GE, SHL, SHR, ADD, SUB, MUL, DIV, MOD
- 跳转、函数调用
- JMP/JZ/JNZ, CALL/NVAR/RET/DARG
- //TODO: 有空再细讲一下函数调用
- Native CALL:虚拟机通过调用原生函数支持的一些指令(以方便处理动态内存、IO等问题,简化实现)
- OPEN, READ, CLOS, PRTF, MALC, FREE, MSET, MCMP, EXIT
Parse 最关键的就是要将 C 代码翻译成 VM 指令写入 code 空间(同时把全局变量和常量写入 data 空间)
在 VM 运行之前,stack 空间应该是空的,而 code 和 data 应该是写好不需要再修改了的
Parse 过程需要保存一些关键的临时数据,比如说我 Parse 过一个全局变量 x,后面我再遇到变量 x 的时候,
我需要准确的知道 x 的类型、内存地址,这样我才能正确的处理 x 相关的语句和表达式
这个保存 Parse 过程临时数据的地方就是:符号表(symbol_table)
- 符号表 & 关键字
- Token: 符号类型标识,默认是 Id,但是关键字和运算符都有自己的Id
- Hash: just hash,用于快速判断两个 Id 是否相同
- Name: just name, 符号的全名
- Class: 符号的类别:Num(枚举符号), Fun(函数), Sys(Native Call), Glo(全局变量), Loc(局部变量)
- Type: 符号所代表的变量或者函数的返回类型
- Value: 符号的值,不同类别的符号值的含义不同,例如:全局变量的值为地址,Loc的值为顺序(地址在stack中,可根据顺序计算)
- GClass, GType, GValue: 用于进入局部空间后,对同名全局符号的遮蔽时临时保存全局属性
- Parse 全局定义
全局定义一共有两种:变量、函数,由于枚举变量以 enum 开头有些特殊,我们也把它单拎出来处理- parse 枚举:这个很容易 enum [Id] {Id [= Num], Id ....};
- parse 变量:这个更容易 type[*] Id [,Id] ... ;
- parse 函数:这个麻烦些 type[*] Id (type Id [, type Id] ... ) { 这里面是函数内部,单独讲 }
- Parse 函数
- 处理传入参数
- 处理局部变量(遮蔽同名全局变量)
- 一条一条处理 parse 语句
- 恢复同名全局变量
- Parse 语句
- If 语句
JZ false point
true point: true stmts ...
JMP end point
false point: false stmts ...
end point- While 语句
loop point
while stmt
JZ end point
stmts...
JMP loop point- Return 语句
- 普通语句:直接当做表达式处理
- Parse 表达式
表达式 Parse 我在经典的「递归下降」(LL)和 C4 使用的「优先级爬山」(LALR)中犹豫了很久,最终使用简单的爬山法
优先级爬山处理的方式也很优雅:- 遇到第一个 operator 直接压栈
- 后续的 operator 与栈顶比较
- 优先级更高的话直接处理
- 优先级低的话则先处理栈中的 operator
- 直到所有 operator 都处理完