“编译原理”课程实验项目介绍

王生原 董 渊 张素琴

摘要:在“编译原理”课程的教学中,实验项目是十分关键的部分。Decaf/Mind项目是近几年清华大学计算机系本科生“编译原理”课程的主体实验项目,在该项目中,学生在实验框架基础上,针对一个简单面向对象语言的实现开展4～5个阶段的编程实验,对理解和巩固理论知识以及提高软件系统的开发能力有较大帮助。本文就Decaf/Mind项目的背景、内容以及实施情况进行简要介绍。

关键词:编译原理;课程实验;Decaf/Mind项目

中图分类号:G642 文献标识码:A

在清华大学计算机系本科生“编译原理”课程的教学中,Decaf/Mind课程实验项目从1998级开始,至现在的2007级,经历了10届学生。1998～2002年,该项目是选作的(但分值较高的),自2003级之后成为必做的课程实验项目。本文首先介绍Decaf/Mind项目的背景,然后根据目前的情况(2006～2007级),对该实验项目的内容以及实施情况进行简要介绍。

1Decaf/Mind项目的背景

2001年,我们引进了Stanford课程CS143(Compilers, http://www.stanford.edu/class/cs143/, CS143, Stanford University) 的课程实验框架(其原始框架由Julie Zelenski设计)。该实验框架设计实现一种简单面向对象语言Decaf的编译器,因此我们称之为Decaf项目。

Decaf是一种强类型的、单继承的简单面向对象语言,是一种较为流行的教学语言,曾经在Stanford、MIT、University of Tennessee、Brown、Texas A&M、Southern Adventist等多所大学的相关课程中使用。

在1998级本科生的“编译原理”课程(2001年秋季学期)中,我们首次采用了Decaf项目,并根据需要对实验框架进行了一定的调整,包括适应Windows平台、增加目标代码在X86的执行以及对源语言进行适当的改动等。比如在2002级,我们对该项目进行一定的简化之后,称之为TOOL项目。

从2003级的课程之后,我们对原始的Decaf项目实验框架进行了3次实质性改动。

在2003～2004级的Decaf项目中,我们将原先实验框架的开发语言由C++改为Java。

在计50班(2005级“姚”班)的“编译原理”课程中,我们参考了U.C.Berkeley课程CS164(Programming Languages and Compilers, http://inst.eecs.berkeley.edu/～cs164/archives. html, CS143, University of California at Berkeley)的COOL课程项目以及Cornell大学课程 CS412(Introduction to Compilers, http://www.cs.cornell.edu/ courses/cs412/2003sp/ CS412/413, Cornell University)中所采用的Iota项目,将实验框架由原来的单遍组织改为多遍组织,我们称之为Mind(Mind is not decaf)项目,并称源语言为Mind语言。

由于计50班的编译课程安排在Java程序设计课程之前,所以首次Mind项目的开发语言为C++。随后,在2005级其他班的课程中,我们又将开发语言由C++改回Java。

从2006级开始,实验框架没有发生大的变动,只是对其进行微调或进行适当简化。下面是对2006～2007级教学情况的介绍。

2课程实验项目的内容

Decaf/Mind项目的实验框架是设计实现Decaf/Mind语言的编译器,该编译器的工作原理如图1所示。

我们将实验分成如下5个阶段:

阶段1:词法和语法分析。借助Lex和Yacc实现词法和语法分析,一遍扫描后直接产生一种高级中间表示(实验指定的抽象语法树AST)。使用的Lex和Yacc版本分别为Flex(Jflex, http://jflex.de/)和BYACC/J(BYACC/J, http:// byaccj.sourceforge.net/)。原始的Decaf项目采用Yacc实现主要编译阶段,实验的3个阶段(词法、语法分析阶段,语义分析阶段,生成三地址中间代码阶段)是一个单遍的过程(注:从三地址码到MIPS汇编代码的翻译由实验框架给定,没有安排阶段实验)。对于这个单遍的实验框架,前几届学生感觉调试的难度较大,有一些语言特征难以实现,但它可以和理论课学习中语法制导翻译的部分相呼应。修改框架后,依赖于Yacc工具的部分大大简化,生成抽象语法树AST形式后,符号表的建立和静态语义的检查工作只需使用树遍历算法就可实现,这符合现实中编译系统的实际情况。这种框架不能与语法制导翻译的理论直接呼应,但可用于间接指导。

阶段2:语义分析。遍历抽象语法树构造符号表、实现静态语义检查(非上下文无关语法检查以及类型检查等),产生带标注的抽象语法树。在这一阶段中,我们把语义分析分为对抽象语法树AST的两趟扫描进行:第一趟扫描时建立符号表的信息,并检测符号声明冲突以及跟声明有关的符号引用问题(例如A继承于B,但是B没有定义的情况);第二趟扫描时检查所有的语句以及表达式的参数数据类型。通过这一阶段的实验工作,学生可以熟练掌握Visitor设计模式的使用。

阶段3:中间代码生成。将带标注的抽象语法树(decorated AST)所表示的输入程序翻译成适合后期处理的另一种中间表示方式,即三地址码TAC,并在合适的地方加入诸如检查数组访问越界、数组大小非法等运行时错误的内容。通过一阶段的实验工作,学生可以掌握常见语言成分的中间代码翻译方法,并且可以对过程调用约定、面向对象机制的实现方法、存储布局等内容有切实的了解。

阶段4:中间代码优化。根据教学计划,目前的实验框架只要求基于TAC实现一些简单的数据流分析,没有包含中间代码优化算法的内容。在2005～2007级的实验中,只要求学生实现活跃变量分析,既包括以基本块为单位的分析,也包括以基本块内单个语句为单位的分析。

阶段5:目标代码生成。实验框架包括汇编指令选择、寄存器分配和栈帧管理,实验内容可以设计为对这些部分进行改进。考虑到学生负担问题,目前我们没有安排这一阶段的实验任务。

完成这些阶段后,即可产生适合实际MIPS机器的汇编代码,可以利用由美国Wisconsin大学所开发的MIPS R2000/R3000模拟器SPIM(MIPS SPIM, University of Wisconsin-Madison, http://pages.cs.wisc.edu/～larus/spim.html) 来运行这些汇编代码。

3课程实验项目的实施

Decaf/Mind项目一般在“编译原理”课程学期的第4或第5周开始,历时8周(遇特殊情况顺延),共4个阶段,各阶段2周。为鼓励学生积极进取,学生可以对实验工作自行扩展,自行扩展部分在第4阶段截止日的随后两周内完成提交。

2006级每一阶段的满分成绩为10分,实验成绩满分40分。2007级实验成绩满分35分,各阶段的分布情况是:第1～3阶段为9分,第4阶段为8分。自行扩展部分在4个阶段的评分完成后统一评分,最高5分,将直接加入总评成绩。

各阶段评分的依据包括程序部分和实验报告部分。程序部分主要看输出结果与标准输出的一致程度,占每阶段成绩的80%;报告部分主要看对提交的作业报告的描述,例如是否清楚说明了自己的工作内容等。每阶段截止提交2周后,该阶段成绩将被公布。如有抄袭,将取消阶段成绩,并给予警告。每名学生共有2天的晚交额度,每超过1天在总成绩中扣2分,公布评阅结果时会同时提醒每名学生剩下的晚交额度。

对自行扩展部分的评价是综合考虑创新性、实用性、合理性、难度、工作量等因素进行的。我们要求该部分选题一定是在已有实验框架基础上进行的有意义的改进工作,通常需要与教师或助教沟通后方可确定选题。教师可以对该部分的选题进行必要的引导,以避免一些意义不大的重复性工作。比如引导学生开展如下选题:函数式风格语句的实现、例外处理支持、垃圾回收机制、新的代码生成机制(必要时增加新的低级表示)、有意义的优化算法(必要时增加新的中间表示)的实现等。

4结语

本文简要介绍了清华大学计算机系本科生“编译原理”课程Decaf/Mind课程实验项目的基本情况,包括该项目的背景、内容以及实施情况。

Decaf/Mind课程实验项目实施以来受到计算机系学生的重视。对大多数学生而言,这个实验项目是入学以来遇到的第一个有一定规模的完整的程序设计项目(“编译原理”课在大三上开设),又由于本课程在计算机系课程体系中具有重要地位,加之项目本身的魅力,学生兴致较高,综合能力有明显提高。

“编译原理”课程实验项目的设计和实施是一项较为复杂的系统工程,期待国内同仁对本文所介绍的实验项目提出宝贵的意见。

致谢:Decaf/Mind课程实验项目经过多届学生的实践日趋成熟。我们要特别感谢杨俊峰(Stanford助教)、张迎辉(1999～2000级助教)、毛雁华(2000～2001级助教)、刘天淼(2001级助教)、唐硕(2002级助教)、梁英毅(2003～2005级助教)、张铎(2005～2007级助教)、蒋波等学生的倾情奉献。还有许多老师和学生对该项目作出了贡献,但由于失去统计,没能一一列出他们的名字,这里一并表达感谢。

Introduction to the Course Lab-Project for Principles and Practice of Compiler Construction

WANG Sheng-yuan, DONG Yuan, ZHANG Su-qin

(Department of Computer Science and Technology, Tsinghua University, Beijing 100084,China)

Abstract: The lab-project is very important in the course Principles and Practice of Compiler Construction. The Decaf/Mind project is the major lab-project of this course for the undergraduates in Department of Computer Science and Technology inTsinghua University. In the project, students will come through 4～5 phases of coding experience to implement a simple object-oriented language on the basis of the project framework. The project is helpful for both the theoretical study and the practical training in developing software system. The background, content and arrangement of the Decaf/Mind project are briefly introduced in the paper.

Key words: principles and practice of compiler construction; course lab-project; Decaf/Mind project