compiler

一个用Python实现的MiniC语言(类似于C语言不过有一定精简)编译器. 输入为MiniC的代码, 输出为汇编语言.

beta2.2 版本,暂时修改了所有已发现错误.

数据类型支持int, unsigned int, short, unsigned short, char, unsigned char

支持指针

懒人版文档:

假如没有时间看详细文档, 这里是这个编译器如何使用的简单说明.

主程序为compiler.py, (compiler_alpha.py顾名思义是alpha版, 现在已经不能使用.)

输入为工作目录(windows下就是同目录)下的input.c,输入文件的对应目标语言为MiniC,简单来说是阉割版C语言,具体需要看yqs在群里上传的最新版文档.

编译器首先读入代码并格式化(包括去单行/多行注释, 加{}号, 去;号, 分行, 替换变量格式标识符,替换一元右结合运算符号), 格式化的结果输出为code1.txt

之后利用格式化过的代码进行翻译成汇编代码, 输出为code.asm. 中间检测到的错误会被抛出, 即error.txt记录了所有格式化过的错误代码行. 所以如果要定位错误行, 需要将 源代码 — 格式化后的代码 — 错误代码行 三者匹配.

闲人版:

本来编译器是应该用, 也是正路的育成方法是lex+yacc+生成机器码的. 虽然已经有了seulex, 但yacc不是自己的代码, 实在没法放心用. 也没有心看下去lex和yacc的使用规则, 于是就自下而上开始一步步用python实现.

首先, 看一下我们想要什么:

.stack

.data

.code

其中, .stack默认为空所以不用管; .data需要存放非寄存器数据; .code是程序代码.

而这次的编译器的目标语言是MiniC, 与C区别在于精简了大量功能并规定了一些格式. (这也是敢用python硬解的底子) 于是再看一下我们需要处理的语言是什么模样:

int a;
void delay(int i, int j) {
	int a[10];
	short s;
	char c;
	unsigned char uc;
	unsigned short us;
	unsigned int ui;
	char q;
	short w;
	int e;
	int *p;
	a[1] = 1000;
	while(c>0){ c=c - 1;}
	i = a[5] + 3;
}
int main(void)
{
	int i,j,k[3];
	int key;
	int *LED;
	key=0;
	LED = 0xfffffc60;
	while(1)
	{
		key=key+1;
		*LED=key;
		if(key>100) key=0;
		else if(key>10)key = 1;
		else key=key-3;

		delay(a+5, k[2]);
	}
}

大概就是这种样式. 重要的几点有: 全局变量定义在所有函数前, 定义和赋值必须分开. 另外支持(unsigned) int8,16,32. (这里比较坑的一点是最开始给的资料并没有这样说, 只要求支持int就好; 结果在群文件里上传了更新后的文件, 对于我这种从来不看群文件的就妥妥地坑掉了.)

在继续说明之前, 首先让我大致介绍下编译器的解析思路:

1. 全局变量, 毫无疑问是定义在.data区. 所以只要扫描提取出变量名并列在.data就好. 为了和之后函数里的变量名区分, 全局变量在汇编里的名称定义都是 "Void_ + 原本的变量名". 另外为了支持对齐, 假设不足32位的变量, 会被强制补齐至足够32位的个数.

2. 函数的局部变量, 与全局变量不同的是, 前10个使用最频繁的局部变量需要分配的是寄存器, 其它才会分配到.data区. 所以先要提取出函数形参和最开始定义的变量, 并扫描整个函数记录变量出现的次数, 选取前10个分配寄存器, 之后的分配到.data区. 这时出现了一个问题: 我如何让函数支持递归?

   寄存器内的函数, 只要push就好, 全局数据区的怎么办? 其实也是push就好. 为了支持递归, 我们定义了PUSHA和POPA函数(汇编语言), 编译器在发现要进入其它函数内部时, 首先生成PUSHA命令, 之后跳转到目标函数, 最后从目标函数跳回原位置并生成POPA命令. PUSHA命令的作用是, PUSH所有的该函数涉及到的变量至.stack区, 包括寄存器类型和.data区的变量. 寄存器类型只要不管用没用到全部PUSH就好, 但.data区的变量如何PUSH? 这就是我们的这次实现中最讨巧的地方: 首先在.data区的变量都是按照函数簇集的. 也就是不同函数的变量绝不可能交叉; 其次, 在每块函数所属的变量前, 我们都加了一个新的变量. 变量名为函数名, 类型为.word(即32位整形), 值为该函数之后所占.data区的字节(8位大小)个数. 比如:

   
   delay .word 44
   
   delay_a .word 0 0 0 0 0 0 0 0 0 0
   
   delay_b .byte 0 0 0 0
   
   

   有一个叫delay(void)的函数, 里面定义了一个 int a[10]; char b[3]; 的数组, 上面就是实际得到的效果. 注意虽然b[3]定义里长度是3, 但为了32位对齐, 实际会补足32位长度, 即4个.

   同时, 在生成PUSHA命令的时候, 编译器不仅仅输出PUSHA, 同时在后面空了1后, 输出这么一条注释: ##函数名. (函数名即为当前所在函数的函数名); POPA同理. 这样, 汇编器在识别出PUSHA/POPA之后, 读取后面的注释就可以知道当前所在函数的函数名, 同理也就知道了.data该函数的入口位置, 读取该位置的值就知道了该函数在.data里占用的大小, 继续向后读取该大小的32位数并push到栈里即可. 这样函数的递归就可以实现了.

3. 之后就是.code区的实际命令了. 赋值之类思路很简单, 关键是while 循环和if else条件控制. 这里, 编译器和汇编器做了一个约定: 编译器中绝不出现实际地址, 全部由标号Label代替. 在这里, while循环比较简单, 只要在while语句开始时加一个while_begin_number的Label, 最后加一个j while_begin_number的跳转语句和一个while_end_number 的结束Label, 内部开头加一个判断跳转语句即可. 但if else循环相当不好写. 大致的处理步骤如下:

   1. 首先, 不一定有{}号把if-else的语句括起来, 需要你自行处理. 所以第一步就是规则化, 把所有的if else语句变成if() {} else{ if-else }的形式, 这实际变成了一个递归的问题.
   2. 递归地生成Label. 这里我无法用语言去描述代码. 总之是根据第一步生成好了的左右{}号来生成Label, 较1.而言应该说是简单多了.

这样编译器的约定大致说完了, 开始说具体的流程.

1300行之前的代码都是各种定义和函数, 1300行之后才是main函数体. 其实应该用一个__main__函数的, 不过当时还没有意识到那种代码风格.

1. 首先, 读入数据并处理注释并分行. 单行注释直接在读入每行时消除. 但之后我犯了一个极其愚蠢的错误, 而且这个错误几乎无法修正: 我为了支持多行注释/* xxx */, 采用了一个蠢办法: 将所有读入行合成一整行, 之后扫描寻找/*子串, 找到后继续向后寻找*/子串. 这种方法虽然可行, 但却严重破坏了代码的行号信息, 以至于在之后的错误定位上越改越乱. 姑且, 现在错误定位是这样实现的: 存了一份原始的代码, 之后在代码处理过程中发现错误的时候, 直接将错误行抛出, 最后对所有抛出的代码行, 查找其在原始代码中的位置. 愚蠢的方法, 但别无选择了.

   关于分行, 是以 ; 号和 \n来分行, 并删除;号. 即, 这之后的数据, 只有两种形式: 具体的C代码, 比如运算, 函数等, 否则就是 {或} 号. 这也是规则化的一部分.

2. 类型名替换. 这是我之前提到过的被时间差坑掉的事: 后序更新的MiniC手册要求增加对各种int类型的支持, 然而初始alpha版代码只支持了int. 在beta版中, 为了便利的处理不同类型, 将原本的名称 char, short, int 统一替换为swift语言风格的int08, int16, int32. 并根据是否为unsigned类型而添加u和s. 最后类型会被编译器替换为['sint08','sint16','sint32','uint08','uint16','uint32']这个6种格式. 当然这些都是编译器做的, 对用户透明. 用户写的时候仍然是标准C风格的定义即可. 另外, 关于指针类型, 直接按照*作为一种右结合的运算, 数据本身作为sint32处理. 同时为了不与乘运算混淆, 所有的指针运算符号* 都被替换为了 $号; 作为单元运算符的负号 - 也被替换为了 `号(以便和二元运算符减号区分).

3. 之后是代码分块. 包括最开始的全局变量块, 和之后函数块(包括最后的main函数). 定义了function类, 类的初始化参数为类的全部代码行, 初始化时函数抽取出函数头, 参数列表和实际代码等数据. 至此输入和初始化完毕, 接下来是输出.

4. 首先输出的是.data区数据, 包括全局变量和函数的临时变量. 全局变量的处理如之前所述, 为方便识别全体在.data区加上了前缀 Void_ . 函数的临时变量同样如之前所述, 不过需要注意的是如果是数组类型则必定放在.data区, 无论数组大小是多大. 另外函数的形参同样是它自己'定义的'参数, 所以不能落下.

5. 因为每个函数的代码块其实是无关的, 所以接下来就是依序输出每个函数的代码块. 除非是遇到{号, 否则行与行之间也是无关的, 依次输出每行生成的汇编码. 如果遇到{或}号, 需考虑之前while或if等来生成Label以供之后跳转.

   这里需要额外注意的是函数的调用, 处理之前提到的生成规则, 另外非常麻烦的便是给函数的形参赋值. 需按序判断类型并赋值.

6. 以上对每条语句的处理, 最后都可以化简为两种运算: 单元运算或二元运算. 单元运算包括 非, 负, 否, 指针; 其它运算,包括赋值运算都归为2元运算. 所以通过两个函数来处理即可. 不过因为涉及不同位数和unsigned类型, 里面同样有各种坑, 比如一个未越界但满32位的uint32 减一个未越界的sint32. 这时候因为要把uint转为sint来处理, 所以会造成越界, 所以必须仍然按照uint判断并计算, 最后转为sint