完成中间代码生成

最晚突发灵感，一口气写代码生成写到凌晨 5 点。睡了一觉，逃了一天课，下午又接着写，终于完成了这个 "Simple Compiler"。说实话，写这个编译器花的时间最多的不在代码生成，但确实感到代码生成的技术含量是最高的，也难怪每一本讲编译的书在代码生成上的章节是最长的。想想 2 个月前的暑假时还认为写编译器是一项不可能在短时间完成的任务，而现在基本上对编译器的流程有了一个大致的了解和实践，真的还是应了那句老话：“没有什么是学不会的。”

这个编译器，词法分析方面主要参照了《编译原理与实践》(Compiler Construction Principles and Practice) 里的那个 TINY Compiler 处理方法和技巧，构造 DFA，分状态处理输入字符。语法分析就是纯正的 LL(1)。

语义分析和中间代码生成这个阶段就不像前两个阶段那样有一个公式可以套。可以说，每个语言都有不同的、属于自己的分析方法，所以这个部分我更多的参照了教科书里面的方法。虽然说先根据语法分析的结果生成语法树，再根据语法树生成代码会简单一些，但这样会增加代码，降低效率，而且在某些情况下不适用，同时因为我的语法分析是 LL(1)，所以我还是选择在不改变语法的情况下直接在语法分析中间添加语义分析的代码。

具体技术上，主要是使用“回填”技术。为了解决如何延后修改已经生成的代码的问题，我设立了一个四元式的数组，把生成的中间代码写进去，在 backpatch 函数中修改相应四元式。在分析完了所有程序后，用 emit 函数将四元式输出到控制台上。

其实，虽然感觉在实际编写代码上的时间并不是很多，但平时一直都在看关于编译的书，也正是有这些积累，才能够有比较清晰的思路来完成它。还要感谢那些前辈们宝贵的智慧和经验，没有他们，编译还是 Mission Impossible。

《编译原理》，Compilers: Principles, Techniques, and Tools，龙书
《编译原理与实践》，Compiler Construction Principles and Practice
《可变目标C编译器——设计与实现》，A Retargetable C Compiler: Design and Implementation，lcc
《编译器构造：C语言描述》，Crafting a compiler with C

初识编译器设计

最近终于开始自己动手写编译器了。老师给了一个名为 SIMPLE 的语言，叫我们写一个词法分析和语法分析。我是用 C++ 写的，刚刚把语法分析做出来了，总的来说还是有点心得的。

词法方面更多的还是参照了《编译原理与实践 (Compiler Construction Principles and Practice, Kenneth C. Louden) 》的 TINY Compiler，原因主要还是因为对编译器不熟，现在有比较成熟的方法，先拿来再说。分析的方法还是先在纸上构造出相应的 DFA，然后用一个 switch 语句选择各种状态分别处理。实际编写的时候，还是发现了很多和 TINY 不同的地方，所以自己也在他的基础上进行了修改。

我们的 SIMPLE 语言比 TINY 要复杂很多（Simple > Tiny ?），所以语法分析方面，相应的函数也多了很多。语言是符合 LL(1) 文法的，所以用的还是递归下降分析法（后来发现，其实还是有一个表达式不符合 LL(1)，不过找到了解决办法）。因为有一个非终结符的两个候选式的 First 集合有交集，所以一时想不到该怎么去选择候选式。后来发现，可以用以下办法解决这个问题：将两个候选式 First 集合的交集抽出来，如果一个候选式可以推出另一个候选式（前者比后者大），那么在遇到交集里的终结符时，选择大的候选式。其他的非交集部分则选择各自候选式。举个例子：

abc → id | | id relation id | arith_exp relation arith_exp

arith_exp 是算术表达式，可以是 id + id，也可以是 id，还可以是 id + num，等等。可以看出，由于 arith_exp 和 id 的 First 集合具有交集 id，如果当前符号是 id，则不知道应该选择哪一个候选式。因为 arith_exp 可以推出 id，所以我把上式改成了

abc → arith_exp [relation arith_exp]

因为如果满足了 id，则一定满足 arith_exp，反之如果满足 arith_exp，不一定满足 id。事实上，上面的例子只是一个简化了的表达式，实际中还要考虑一些其他因素，不过总的思路就是这样了。当然，最好的方法还是仔细的设计标准的 LL(1) 文法，这也算是一点教训吧。