从我高三听说“公开课”开始，我就觉得这个东西一定会有前途。那时候他们还叫Open Course Wave，公开课的形式还都是课程笔记和清晰度超低的课堂视频。当时我看完了流行的《哲学：死亡》和《聆听音乐》，哈佛的《公正》和《幸福》都只看了一点点。另外还囤下了 好几套课程，一直拖到现在都没有接着看。可惜当时没有抓紧时间上《Algorithm》和C语言的课程，要不然上大学的时候也不会那么智商捉急了。

课程名两边用什么标点符号都觉得不对劲，我就用书名号了。

回到正题。大三上编译原理的时候我一直都在忙其他事情——ACM，GRE，莫名其妙的项目，实习，以及无聊的单机版Dota。跟随机房里诸位大牛的脚步，我开始了《Compiler》课程的学习。当时觉得自己自制力不行，没敢跟着老师的脚步上，而是选择了自助模式。看视频做作业，学习过程断断续续，前后持续了近一年。

课程设置非常不错，课堂上讲解的内容也比较简单，基本被我们大HIT课程覆盖。虽然我大HIT讲的我基本没听懂——也有可能是我总在上课的时候睡觉。视频讲得比较浅，但是很详细，有许多step-by-step的例子，例如模拟自动机和算法的运行等等。我之前一直对我们教材龙书的难度深表不满：许多涉及实现细节的代码和算法，跟原理混在一起，真的很难懂很难懂。我也不知道该怎么讲才能讲简单讲清楚。但是我想Alex Aiken教授的这门《Compiler》真的做到了易懂：整个编译器地框架和结构讲得非常清晰，具体算法和原理也都有介绍。教授涉猎很多，跟着教授上课不会担心他漏掉什么东西没有讲。编译器的实现主要体现在作业里，需要自己下一番功夫才能做好。小课堂大作业，我最喜欢的模式。所以我这篇博客会一直说作业怎么样怎么样怎么样。

下面就来了。

整个课程的作业加在一起就是设计一个编译器。它首先提供了一个完整版的编译器作为标准。这个编译器的框架搭得好，比较容易扩展；模块化也做得非常好，编译的每个步骤对应一个模块，模块之间接口简单明确，依赖很轻。这样一来一个模块可以单独拆出来交给学生实现，其他模块都用标准版的，易于调试和查错。框架屏蔽了许多细节，在前两个作业中基本不需要关心底层实现。唯一的缺点是框架提供的utility不太好用，需要自己实现正序的单链表。在编译的时候保持方法和成员的顺序是一个非常好的特性，所以我们需要不改变顺序的单链表。

作业中编译器的源语言是Cool语言。Cool是一种完美的教学语言。没有指针没有数组，一切都是对象，有继承和多态，多了很多十分有意思的细节；自创了type-case语句，非常有用而且实现非常有趣的语句。编译器的目标语言是MIPS汇编，比X86概念更少更容易入门。

四次作业的感受

可以毫不夸张地说，作业是这门课程里最实用最有价值的部分。我的绝大部分时间都花在了作业上，而且我觉得这个时间花得十分值得。

PA2词法分析。总体来说比较简单。部分原因是，与后来的三个作业相比，这个作业要解决的问题本身比较简单。作业使用的工具flex对这个问题做了非常好的抽象，我们只需要用正则表达式描述识别token的规则就行了。当然，并不是所有编程语言的语法规则都可以用正则语言来描述（貌似大部分都不能用正则语言完整描述）。比如Cool语言允许嵌套注释，在处理的过程中就必须记录一下当前注释嵌套的层数，才能正确配对注释开始和结束。这个作业的用意不在于考量大家使用正则表达式的能力，所以Cool的语法有很多明显的简化，避开了大部分难点。时间太久了难点都记不得了，在这里就不列出了。做这个作业的时候可以试图简单扩展一下作业里规定的Cool的语法，相当有意思。

PA3语法分析。相对于PA2的简单直白，PA3就相当抽象了。PA3用到的工具是Bison，比flex复杂了很多。阅读Bison的说明书花了我三四天的时间（根据G+ Post的记录）。加上课程提供的各种基础库（AST等等）是从这次作业开始引入的，使得这次作业的阅读量和理解量非常大。作业本身的难度一般，完成一个上下文无关文法，规定操作符的结合性等等。我当时的时间主要花费在处理／抽象各种空和非空的列表上了。其实只要文档读得细，应该很顺利就能做完并且拿到满分——我的意思是在打分器的帮助下。我试图阅读Bison编译出来的C语言程序，失败了；有时间要了解下Bison的算法。

这里必须表扬一下Compiler课程各个作业中的打分脚本。本质上就是集合了无数test case的一个库，颇有Online Judge风格。要把这个库里的每一个case都处理好是非常不容易的。在这四个作业中，我第一次提交的版本基本都在十分以下——满分是50-80。但是经过无数次的修改和刷分，最后拿到满分也不是特别困难。 我觉得这种做法是对批作业模式的一种改进。尤其是在作业十分复杂的情况下，助教基本不可能理解每个学生的代码，注意到作业里的每个细节，也就没办法高效地评分。这个脚本对学生也特别有用。它大大缩短了学生得到作业反馈的时间，对自学帮助很大。这个方法和助教答疑结合使用，应该会有非常好的效果。当然这一切都建立在一个前提上：评分脚本一定要做得非常用心，包含足够多的case使得它不容易被针对。

PA4语义分析。这是整个作业里最难的部分。我花了整整十四天，每天从早到晚都在研究这个问题。很庆幸毕设选了个有把握的题目，这样才有时间专心做这些。PA4整体设计很重要。我是先实现了一个类的继承关系树，每个class都是这棵树的一个结点。建树的时候顺便完成了继承关系的检查，确保每个类都有父亲。树中允许某些类没有定义，将报错推迟到类型检查的部分，这样更加user-friendly。然后再遍历一遍收集结点深度和方法的信息。接着检查每个方法，成员和表达式。我第一次实现的类型检查非常严格，对错误几乎是零容忍。后来为了容错，推断了很多表达式的类型（例如加减法，一定是整数），检查到错误只报错而不退出，继续类型检查。因为我听说“遇到第一个错误就退出的编译器不是好编译器”。（因为不这么干拿不了满分。）

在检查类型的时候我遇到了SELF_TYPE和找到两个树结点的最近公共祖先两个问题。因为代码里已经有了很多trick和workaround，所以我不得不在class树结点外又包了一层Type类，专门用于处理这两个问题；又定义了Type和树结点的隐式转换，让以前的代码能继续使用。这样改来该去改得自己都晕了，最后终于过了所有的case。

在这个作业里，表（Table）是个非常重要的基础设施。从类名查询Type，查询方法和成员在不在某个类中，收集某个类的所有方法，都要用到表。我比较倾向于变量和类名要单独建表，实现会比较方便。但是整个框架应该是倾向于把所有标示符(identifier)都放在一个表里的。作业的框架提供了ScopeTable来解决这个问题。

还有一个问题是如何存储类的方法和成员的表。子类会继承父类的所有方法和成员，我们要不要在子类的方法表里再存储一遍父类的方法／成员呢？很直白的空间－时间的取舍。框架提供的ScopeTable非常好地解决了这个问题。ScopeTable被设计成一个可以包含另外一个ScopeTable作子表的表。对外层Table的修改不会影响内层的Table。虽然ScopeTable其实是用链表实现的，但是我相信肯定会有更高效的数据结构来解决这个问题。

PA5代码生成。在视频里介绍了有一个寄存器和一个栈来做计算的机器（忘了名字叫什么了不就是下推自动机么！）。这种机器比较容易用汇编语言实现，而且我们都知道功能跟图灵机是一样的。这次作业涉及到了许多新问题，例如寄存器分配和临时变量的分配。不会高级算法的（比如我）只好用直白的低效的算法来实现了。我在这个作业中使用了做HIT的编译原理课程设计的思路，即约定每个表达式都把返回值放在a0（或者某个其他寄存器）里，其他寄存器都当做临时变量来用，尽量不使用栈。当时我的课程设计确实没有做出来，因为我当时使用了一种非常复杂的方法实现了用栈保存结果，而且也没有把这种做法推广到所有计算上。

遗憾和吐槽

课程学完了还是有些许遗憾的。PA2里不清楚生成自动机的细节。PA3里没有实现报错的时候附加行号，而且一直也没有弄明白行号到底是怎么工作的。PA4设计有点冗余，多加了一个类；细节处理十分混乱；最近公共祖先用的是记下结点深度然后向上遍历的方法实现的。PA5没有实现GC，代码生成中有许多hack；依赖于栈，没有分配寄存器算法。以后有时间要完善一下，做一份标准答案出来。

对作业的不满也有一些。在抽象语法树（AST）中，attr和method基于一个共同的基类，给类型检查和代码生成造成了很多麻烦。我必须实现一个虚函数来判断一个结点是方法还是成员。但是我也没有想出更好的方法来实现AST，所以这只是个吐槽。 ScopeTable很强大但是也很弱。整个表只能查但是不能遍历，这让我非常不爽。因为代码生成很显然需要遍历所有的方法和成员，所以我必须在存储ScopeTable的同时自己实现一个链表存储所有的成员。同样的冗余发生在PA4和PA5中间，PA4中收集过的许多信息PA5要再收集一遍，代码重复而且效率低。

最后，作业框架不支持添加自己的源文件，导致我的单个源文件超过了2000行，各种代码堆在一起很难阅读。

要不要把这些吐槽总结一下，发给教授作为Feedback？

总结

作业虽然做完了但是很多概念都忘掉了。如果有时间，我还会努力完成完成剩下的Quiz和Assignment。

这门课程的一个“副作用”是改变了我对Java的看法。曾经我觉得Java是一门又慢又慢又慢的语言。但是从编译器的角度来看，Java还是很优秀的。它实现了好多C/CPP没有实现的高级特性，例如Reflection和运行时加载类。这给了我继续用Java干活的勇气让我在使用Java的时候感觉好了不少。另外我还听说经过仔细调教调校的Java虚拟机可以让Java代码的效率达到CPP的98%左右。我着实被震惊了。以后再也不黑Java了。

《Compiler》也给我了一个（自我感觉）非常好的入门指引，如果要进一步在这个领域里学习，我会重点关注以下几个方面：寄存器分配，临时变量分配，生成自动机语法，语法分析的算法，代码优化算法以及其他高级语言语法的实现。

写到这里，我再一次深深地感觉到了人和人的不同。我想要继续学习就只好自己去查书，寻求帮助和指导对我来说异常困难。大学里的研究生们同学呢？本以为公开课会给我们这些没考上大学的人一个逆袭的机会，现在才意识到，要逆袭，这才仅仅是一个开始。