最晚突发灵感,一口气写代码生成写到凌晨 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