基于C0文法的编译器设计与开发
项目背景
大三时编译原理课程，报名参加了试点班。试点班就是不用参加平常的理论课和实验课，只需要用一学期的时间开发出一个编译器。但是一共三四十名学生报名参加了试点班，最后我的成绩是最高的。
在上编译原理这门课之前对编译器可以说是一无所知，所以一开始上手很困难。老师给了我们一本编译原理的书，就是号称编译原理三大圣经之一的龙书，然后给了我们一个编译原理的网课让我们自学。看了一段时间书和网课然后慢慢开始一点点上手实践。
项目流程
编译器开发主要分为四大块：词法分析、语法分析、中间代码生成和汇编代码生成。
- 词法分析主要是将源代码的字符串划分为token，每个token都包含了一个划分出来的词以及这个词的类型。
- 语法分析就是按照定义好的语法规则将词法分析生成的tokens转换成抽象语法树的过程。
- 中间代码生成式在语法分析的过程中，将语法树转换成四元组的形式，使用四元组主要是为了方便后续汇编代码生成。
- 汇编代码生成就是将四元组转化成对应的汇编代码，比如我采用的mips指令集。
项目难点
寄存器优化
不进行优化的方案就是，每次对变量进行操作的时候，都需要先将变量从内存读到寄存器，然后在寄存器上对变量进行操作，操作完成后再将变量写回寄存器，所以每次使用一个变量都会带来两次寄存器读写，这是很耗时间的，尤其是当对一个变量进行反复修改，就得不断的反复从内存读出写入。
所以最好的解决方案是，给每个变量都分配一个寄存器，等到程序结束的时候再一起写回。但是实际中寄存器的数量是很有限的，以mips指令集为例，一般只有32位寄存器，除去一些有特殊用处的能够使用的寄存器可能只有十几二十几个，而一段代码内部的变量可能有很多，所以没办法给每个变量都分配一个寄存器。
可以尽可能多的把寄存器分配给变量，但是当寄存器用完了而又来了新变量时，就必须做出一个抉择就是要把哪个旧的变量踢出寄存器。这个选择做的好坏非常影响编译器的性能。
当时对这方面的算法了解不多，所以采取了一个比较简单的算法，就是引用计数法。即每次使用一个变量都对将它的计数器加一，然后需要踢出变量的时候就优先踢出计数器次数最小的那个。这种方法再大多数情况下是有效的，但是有些极端情况比如寄存器震荡等。
后来慢慢接触到其它知识后，了解到这个问题其实跟很多其它问题类似，比如内存的页面置换等。有一些很好的算法，比如LRU等，这也是这个编译器后续可以继续优化的方向。
函数调用时的压栈和出栈设计
每个函数都在内存中对应着一段栈帧，栈帧由栈顶和栈底两个寄存器确定，mips里叫做sp和fp。
调用函数时，先将函数参数压栈压栈，再将返回地址压栈，再将栈底位置压栈，然后将栈底指向栈顶也就是当前位置，之后就是新函数的栈帧。
函数调用结束后，出栈的顺序跟入栈的顺序相反，先让栈顶指向栈底，意味着将该函数的栈帧取消，再将栈底移到它指向的值，即回到上一个栈底的位置，从而恢复上一个函数的栈帧，然后再将放回地址出栈，让指令寄存器回到返回地址处继续执行程序。
多重for循坏的线性化
通过mips的label和jump指令将for循环展开
后续的优化方向
- 增加一些功能，比如多维数组、结构体等。
- 改进寄存器优化算法，比如增加计数器衰减或者使用LRU算法等。