0
0

Compiler学后

杨靖 发表于 2013年11月17日 19:40 | Hits: 1860

从我高三听说“公开课”开始,我就觉得这个东西一定会有前途。那时候他们还叫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》也给我了一个(自我感觉)非常好的入门指引,如果要进一步在这个领域里学习,我会重点关注以下几个方面:寄存器分配,临时变量分配,生成自动机语法,语法分析的算法,代码优化算法以及其他高级语言语法的实现。

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

原文链接: http://ditsing.com/blog/2013/11/17/compilerxue-hou/

0     0

评价列表(0)