Title: Teaching the Compilers Course

Author: Alfred V. Aho,

Department of Computer Science

Columbia University

Note: A piece of translation work for professor Lv.

Here I only post the Chinese version for archiving

编译程序课程的教学

阿尔弗雷德 V. 阿霍

哥伦比亚大学 计算机科学系

我一直很喜欢教编译程序课。编译程序设计是理论与实践的完美结合—它是系统编程领域第一批重大理论基础发展之一,而今应用于通常实践中。我坚信高德纳信条:“理论与实践并不互斥,而是紧密联系,相辅相成的。”【5】

在过去的五十年中,一些团体把传统的编译程序课程同计算机科学课程关联在一起【6】。本文着眼于,编译程序课程自其诞生开始如何回应这些团体。我根据四本编译程序书中的材料整勾画了这一演变过程。我曾参与这些书的编写,还把它们用在我过去三十年的编译程序课程中。【1-4】

许多最早的编译程序课程着重强调语法分析和语法制导的翻译理论。然而,人们很快意识到,拘泥于理论很难教好学生如何创建一个有用的编译程序。这一发现在我与贝尔实验室计算机科学研究中心的一些杰出的研究者交流后更加验证了其正确性。那里是我刚毕业时工作的地方。我在普林斯顿大学创建了标号语法和嵌套堆栈自动机作为我的博士论文,就在那开始了我的计算机科学理论家生涯。随着身边Unix,C和C++诞生的喜悦,我很快就获得了参与理论和实践在系统和编译程序中富有成果的协作的绝好机会。

许多早期出现在Unix的工具,如diff,grep和yacc是来自于计算机科学理论的算法的软件化身。我曾尝试实现一些自己在Unix上编写最初版本egrep和fgrep时发明的字符串-模式-匹配算法,后与布莱恩.克尼翰和彼得.温伯格合作开发AWK编程语言。通过这些经验,我明白,在实践中有效、正确地实现一种算法,同在理论上开发它需要相当的天赋。许多出现于Unix第一个版本的工具至今仍在使用,这就是对那些Unix先驱精湛技艺的有力证明。

早期和现代的编译程序具有戏剧性的差别。早期的编译程序通常用低级语言如汇编语言或C编写,只需几千行的代码就能实现;现代的编译程序由多种语言编写(C,C++,C#,F#,Java和OCAML是现在流行的语言),往往长达几百万行代码。早期的编译程序常由个体创建;现代的编译程序是一个典型的大型软件工程项目,涉及多个编程团队,使用预建组件和已有的编译器构造框架。

在计算机科学,早期只有相对较少的编程语言;今天有数千种。早期只有相对较少的目标机器体系结构;今天我们仍在用过去的CISC和RISC结构,但同时有vector,VLIW,多核,以及许多其他折中的架构。语言和机器这一演化的结果,使得我们不可能在一个编译程序课程中涵盖现在商业编译软件中用到多样的算法和技术。

尽管源语言和目标机的种类繁多,我还是发现仍有可能开设一门让学生受益匪浅的编译程序课程。

这是我目前的编译程序课程已经发展到的。它依然涵盖了词汇分析、语法分析、语义分析、中间代码生成、运行环境、资源管理和目标代码生成—存在于每一个编译软件中的任务。这些任务的基本概念必要知晓,因为它们不仅适用于编译领域,如自然语言处理和程序检查。但是,在第一个编译软件课程中没有时间去覆盖—独立于机器和依赖机械—代码优化算法的各个深度。

为一个小编程语言实现一个编译程序一直是编译软件课程的一个标准组成部分。过去我曾制定学生编译软件的源和目标语言让他们来实现。虽然这有指导意义,但是我发现学生对实现别人的玩具语言并不感到兴奋。

学生们觉得以一个小团队来运作,定义自己的小语言,再为它建立一个编译器,这么做有无限的成就感。当看到以自己的语言编写的程序被编译、执行,他们的眼睛雪亮。从我个人的经验中发现,围绕这种项目适当量的软件工程进程可以让每一个学生团队在为期15周的学期内顺利设计并实现一个可用的编译软件。

以下是我用过的进程。小队须要按照下面的时间表在15周的课程期间完成下列任务,同时学习编译软件背后的理论与实践。

星期 任务
2 成立一支5人小队
4 仿照Java白皮书给提案语言写一份白皮书
8 参照Chapter1写一个教程 

模仿克尼翰和里奇的书《编程语言C》的附录A写一份参考手册

14 就该语言向同学做一个10分钟的演示
15 向教学人员提交该编译器的一个30分钟的演示
15 上交最终的项目报告

团队一旦形成,须选出一名项目经理、一名系统架构师、一名系统集成师、一名测试员和一名语言师。每个职位担负特定的团队职责:

  • 项目经理制定项目时间表,召集全队举行每周会议,记录项目日志,并确保项目成果按时递交。
  • 系统架构师确定编译器架构、模块和接口。
  • 系统集成师确定系统开发平台和工具,集成环境,及makefile以确保各个编译组件一同工作。
  • 测试员根据语言参考手册确定测试计划和测试套件。 随着编译软件的开发,为了确确保其符合语言规范,每个团队成员都将执行测试套件。
  • 语言师维护语言知识的完整性,并制定一个基线系统和过程以管理语言定义的变更。

我和助教们给予这些团队关于如何完成相关任务所需的建议。这种项目有诸多好处。学生们有机会通过设计他们自己的新语言来锻炼他们的创造力。他们能体会到为语言写数值命题和为软件系统写详细的说明所富有的挑战性。他们还会学到一些有价值的技能,如项目管理、团队协作和沟通(包括口头和书面上的)。这些技能适用于任何类型的项目,不只是写个编译软件。

该项目的最终报告包含以下章节:

1.  简介(团队撰写)

2.  语言教程(团队撰写)

3.  语言参考手册(团队撰写)

4.  项目计划(项目经理撰写)

5.  语言演化(语言师撰写)

6.  编译器架构(系统架构师撰写)

7.  开发环境(系统集成师撰写)

8.  测试计划和测试套件(由系统测试员开发)

9.  含经验教训的结论(团队撰写)

10.包含编译软件完整源列表的附录

学生根据他们在团队中所扮演的角色和他们各自所写的编译器的组成部分获得独立的分数。他们从语言白皮书、教程、参考手册、课堂报告和项目演示中获得团队分。

我给每一个团队安排助教指导他们,通常我自己会指导三、四个团队。斯蒂芬A爱德华兹教授和我在哥伦比亚大学每学期用这种项目教授编程语言和编译课程已超过五年。每个班通常有50到100名学生。我们总能被学生创造的语言的独创性和新颖性震惊。其中有量子计算机语言模拟、电脑游戏制作、音乐创作、远程共享会议服务创建和其它应用程序方面的创新。有些语言项目最终成为可发表的论文。

有几个因素使得这种编译程序课程成为可能。该课程有数据结构、算法、计算机科学理论和计算机系统作为前序课程。学生至少能熟练应用Java和C。许多担任项目经理的学生有在软件产业中编写软件的经验,且熟知如访问者模式的设计模式。编译程序构造软件如lex和yacc(或其它现今的同类软件),集成软件开发环境,和wikis推动分布式编译软件开发,使得学生既能独立又能合作完成其编译器组件。但可能最重要的是,编译器设计的理论和实践现在已经成熟到连那些正在上15周课程的初学者也能创建有趣的、可用的编译器。

在此课程中软件过程的重要性不可低估。我个人仔细检查了语言白皮书、教程和参考手册,确保编译器可以用几千行源代码就能实现。每名团员须至少编写四百到五百行这种代码,这样每个人都能粗略了解编写系统组成代码要做的工作。

实际上,各个团队按时递交一个可用的编译程序并不奇怪。我让他们发展自己的语言和编译软件,这样他们只需在期末上交一个可用的版本。另外,我要求学生在他们的语言参考手册中陈述他们打算实现多少内容,如果有额外的时间能实现什么。在最终的项目演示中,我要求每个团队执行两个程序:一个随机选自他们的语言参考手册,另一个事先未知的新程序由助教创建以测试他(她)团队的语言。

学生一致给予了这门课程高度的评价,还说他们学到了足够的编译理论和工具的知识,可以在一学期内创建自己的语言。他们频频提高项目管理、团队工作及如何进行口头和书面陈述这些所学的重要技能。当他们去参加就业面试,面试官普遍为他们的软件工程技能所折服。

总之,现代编译程序课程可以给学生提供一个绝好的机会锻炼他们的创造力,让他们亲身体验理论和实践的完美共生,提供一个体验良好软件工程实践的小型方案—可以大大提高所实现项目的稳健性,学习团队协作和沟通技能—随后可用于生活的方方面面。

参考文献

1.  A. V. Aho and J. D. Ullman, The Theory of Parsing, Translation, and Compiling, Volume I:

Parsing, Volume II: Translation. Prentice-Hall, 1972 and 1973.

2.  A. V. Aho and J. D. Ullman, Principles of Compiler Design. Addison Wesley, 1977.

3.  A. V. Aho, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools. Addison

Wesley, 1986.

4.  A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and

Tools, Second Edition. Pearson Addison Wesley, 2007.

5.  D. E. Knuth, Theory and Practice, Keynote address for the 11th

World Computer Congress

(Information Processing 89), San Francisco, 28 August 1989.

6.  W. M. Waite, The Compiler Course in Today’s Curriculum: Three Stategies. SIGCSE,

Houston, Texas, March 1-5, 2006, pp. 87-91

2011/01/16