c4编译器源码剖析

2015-03-15 fishedee 后端

1.概述

c4是500行代码实现一个c语言编译器，简单暴力，适合了解基础的编译器原理

2. 主流程

1
2
3
4
1.建立系统符号表
2.读取源代码
3.一次遍历源代码，同时进行词法分析，语法分析和中间代码生成。
4.执行中间代码

3. 中间代码

3.1. 基础

中间代码 操作 意义
LEA 2 将栈往上的2个位置变量加载到寄存器 加载本地变量
IMM 将代码区位置指定的代码加载到寄存器 加载到全局变量
JMP 2 将代码区跳转到2这个位置 跳转
JSR 2 将下一个代码区位置保存到栈顶，并将代码区跳转到2这个位置 跳转到子程序
BZ 2 如果全局变量为a，则跳转到下一个代码区域，否则跳转到2这个位置 零跳转
BNZ 2 如果全局变量不为a，则跳转到下一个代码区域，否则跳转到2这个位置 非零跳转
ENT 2 保存前一个程序的栈顶到当前栈上，并设置新栈顶，和局部变量区 开辟一个新的子程序
ADJ 2 栈调整，往前2个位置 栈跳转
LEV 栈回滚到当前程序的栈顶，然后恢复上一个程序的栈顶，再恢复上一个程序的代码区，最后恢复上一个程序的栈 子程序退出
LI 将寄存器的整数变量加载出来 加载整数
LC 将寄存器的字符变量加载出来 加载字符
SI 将栈顶指定位置的地址保存整数 保存整数
SC 将栈顶指定位置的地址保存字符 保存字符
PSH 将寄存器变量保存到栈上 保存栈
EXIT 将栈顶变量打印出来，作为返回值，并退出来 退出整个程序

3.2. 运算

1
2
OR,XOR,AND,EQ,NE,LT,GT,LE,GE,SHL,SHR,ADD,SUB,MUL,DIV,MOD
都是二元操作符，都是将栈顶变量取出来，然后与寄存器运算，再存回到寄存器

3.3. 系统调用

1
2
OPEN,READ,CLOS,PRTF,MALC,MSET,MCMP,
都是系统调用，将栈顶变量作为参数，逐一打印出来

3.4. 范例

3.4.1. 函数调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
函数调用前，先将参数逐个放入栈中
IMM  3,
PSH,
IMM  4,
PSH
然后执行JSR跳转到子程序
JSR -145211380
上述代码相当于调用函数
xxxx(4,3)
这时候栈的内容为：
[3,4,下一行代码的pc位置]

子程序执行完毕后，栈的内容为
[3,4]
重置堆栈位置，去掉参数
ADJ 2
这时栈的内容为
[]

3.4.2. 函数执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ENT  0
开始执行函数，函数的局部变量为0个，所以为ENT 0，这是栈的内容为
[3,4,下一行代码的pc位置,上一个程序的栈底]
LEA  3
LI
PSH
[3,4,下一行代码的pc位置,上一个程序的栈底,3]
LEA  2
LI
ADD
[3,4,下一行代码的pc位置,上一个程序的栈底,7]
将栈顶存入的两个参数运算放入到寄存器中
LEV
离开函数，恢复上一个程序的pc位置，以及栈底
[3,4]

3.5 总结

1
2
3
4
5
c4的中间代码是一个基于寄存器的vm。
其只有一个寄存器变量，为a
有一个栈存储区，当前栈顶位置为sp，每个函数有自己的栈底bp，存储区域为stack area
有一个代码区，当前执行代码位置为pc，存储区域为text area
有一个数据区，存储区域为data area

4. 符号表

4.1. 符号类型

1
2
3
4
enum {
  Num = 128, Fun, Sys, Glo, Loc, Id,
  Char, Else, Enum, If, Int, Return, Sizeof, While,
};

4.2. 符号表存放

1
2
3
4
5
6
7
8
9
10
int   *sym,     // symbol table (simple list of identifiers)
enum { Tk, Hash, Name, Class, Type, Val, HClass, HType, HVal, Idsz };
符号表是一个长数组，每个数组的元素为符号描述，元素长度为Idsz
每个符号元素包括的信息为：
Tk 符号类型，id类型，用来区分是否为关键字的
Hash 符号哈希
Name 符号名字
Class 变量类型，Num = 128（常数）Fun（函数）Sys（系统调用） Glo（全局变量） Loc（本地变量） Id
Type 变量数值类型，char,int,ptr,还是*char,*int,*ptr,还是**char,**int,**ptr
Val 变量的值，对应不同的数据类型有不同的值

4.3. 关键字符号表

1
2
Char, Else, Enum, If, Int, Return, Sizeof, While
以上Id在符号表上都是有特殊的Tk值

4.4. 系统调用符号表

1
2
open read close printf malloc memset memcmp exit
以上Id在符号表上的Class为Sys，Type为Int，Val为特殊值

4.5. 特殊符号表

1
2
void 的符号设置为和Char一样
main 的符号位置被记录

5.流程

5.1. 配置文件

1
识别配置文件中的-s -d参数

5.2. 配置vm环境

1
2
3
4
5
6
建立源代码区域
建立符号表区域

建立text area
建立data area
建立stack area

5.3. 初始化符号表

1
初始化关键字符号表，系统调用符号表，和特殊符号表

5.4. 读取源代码

1
将源代码文件整个写入到源代码区域。

5.5. 词法分析，语法分析与中间代码生成

1
c4的代码很简洁，一次遍历源代码，同时执行词法分析，语法分析，和中间代码生成

5.5.1. 词法分析

1
2
3
4
5
词法分析，在next()函数中实现。
每解析一个词语，就将
结果类型写入到tk变量，
变量值写入到ival变量
id类的变量还会顺道写入到符号表中

5.5.2. 语法分析

1
2
3
4
语法分析，在main，stmt,expr中都有实现。
其中main负责主流程的语法分析，包括全局变量定义，枚举体定义，函数定义
stmt负责分支循环语句的语法分析，包括if,while,return
expr负责运算符语句的语法分析，包括加减乘除赋值等等

5.5.3. 中间代码生成

1
2
3
4
c4是在语法分析的过程中生成中间代码的。
main中，碰到枚举体定义时，更新符号表。碰到全局变量定义时，加入data area和符号表。碰到函数定义时，生成ENT和LEV的中间代码
stmt中，碰到if，while,return，生成对应的BZ,BNZ,JMP的中间代码
expr中，根据不同的预算符，将变量计算，并将结果均写入到寄存器中。

5.6. 执行中间代码

1
2
3
在符号表中确定main函数的位置。
初始化退出代码，PSH和EXIT
根据text area，执行中间代码，不断更新stack area与data area

6.总结

1
2
3
4
c4的代码简洁，但较难懂，好多变量都是缩写。
功能齐全，满足编译器开发的，词法分析，语法分析，目标代码生成的三个基本步骤。
并实现了自举，可以自己编译自己。
./c4 c4.c c4.c hello.c。

相关文章