“编译原理”课程的教学内容选择的探讨

张 昱 陈意云 郭 宇 李兆鹏

摘要:本文根据国外“编译原理”教材的演化情况并结合笔者自己的教学和科研的经验,对国内“编译原理”的教学提出了普通高校本科、重点高校本科和研究生阶段三个不同层次的教学目标,并给出了这三个层次的教学内容的建议,供国内同行参考。

关键词:编译原理;编程语言;教学目标;教学内容

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

1引言

编程语言的“编译原理”是计算机专业一门非常有用的核心课程,又是一门需要较大投入的课程。怎样激发学生的学习热情,努力学好本课程?在正确的教学目标下选择适当的教学内容是非常重要的一环。基于笔者长期承担“编译原理”教学的体会,以及多年从事编程语言理论和实现技术研究的积累,本文阐述笔者对该问题的认识。

国外和国内分别从二十世纪六十和八十年代开始设置“编译原理”课程,几十年来,“编译原理”课程可以讲授的内容越来越多,从文献[1,2]这两本专著的内容看出。和第一版相比,第二版压缩了编译原理传统部分的内容,大量增加了新技术内容,书的厚度从接近800页猛增到超过1000页。第一版中被删除的部分包括:语法分析中的算符优先分析法,语法制导翻译中的递归计算方法、语法制导翻译的实现细节和语法制导定义的分析,最后两章的编译器自展和一些具体编译器的介绍。在静态检查一章介绍的类型系统和类型检查被分散和弱化到中间代码生成一章中。第二版中增加的内容包括:

(1) 堆管理和各种垃圾收集算法。

(2) 独立于机器的代码优化增加了数据流分析的理论基础,强调了在一个数据流分析的一般框架下解决各种具体数据流问题,能使读者对程序分析和代码优化有更深刻的认识。

(3) 依赖于机器的优化,包括现代处理器体系结构、指令调度、基本块调度、全局调度和软件流水等。

(4) 并行性和数据局部性优化,重点介绍在多处理器系统上,使用数组作为数据结构,并且以简单而有序模式访问这些数据的计算密集型程序的优化问题。

(5) 过程间的分析,包括调用图、上下文敏感分析和指针分析等。

国外另一本著名的专著是Appel的《Modern Compiler Implementation in C(3rd. Edition)》(还有Java语言描述和ML语言描述的版本)。全书21章,表明它涉及的内容广泛,比Aho第二版覆盖的范围还要广,包括了面向对象编程语言和函数式编程语言的实现方法。但是全书不到550页。因为Appel强调编译原理的学习离不开具体的实践,他精心设计了一个“学生项目编译器”的框架和模块接口,每章的结尾给出与该章内容相关的编译器模块的设计任务,要求学生逐步实现一个编译器。对相关的理论,该书的介绍都比较粗略;对相关算法,除了直接用代码表达的以外,大多数只通过例子表达思想。

从这两本教材可以看出国际教材的变化趋势是压缩仅和编译器前端有关的部分,增加独立于机器的优化和依赖于机器的优化等内容。

国内的编译原理教材基本上都是根据国外教材编写的,在跟踪过程中,总显得有些滞后。例如,国外2000年以后出版的教材已经不介绍算符优先分析法,而国内2004年和2005年出版的一些较有影响的教材仍然介绍算符优先分析法。在增加新内容方面,国内教材也相对落后,笔者力图克服这一缺点,在新近改版的教材(详见文献[5])中,加入了依赖于机器的优化内容。

真正从事主流编程语言编译器设计的虽然只是极少数一部分人,但是编译技术在计算机体系结构设计、提高软件开发效率与质量的工具开发等方面有着重要的应用,这是学习编译原理的主要理由。在编译原理所涉及的知识越来越多,而“编译原理”课程的课时数不足的情况下,如何选择编译原理的教学内容是一件值得探讨的事情。

2教学目标

笔者认为,虽然编译原理和技术对计算机专业的学生来说是重要的基础知识之一,但是对不同层次的高校,应该编写不同深度的教材,讲授不同的内容,以达到不同的教学目标。

可以将教学目标分成三个层次:普通高校本科的目标、重点高校本科的目标和研究生阶段的目标。下面概述的这些目标中,后者包括了前者,并且边界不是绝对的。

(1) 普通高校本科的目标是:通过编程语言实现技术的学习,提高学习编程语言及在程序开发中应用编程语言的能力,具体解释如下:

提高学习、理解和使用编程语言的能力;

提高程序排错的能力,即快速理解、定位和解决在程序开发与程序运行中碰到的问题的能力;

提高编写高质量代码的能力。

(2) 重点高校本科的目标是:通过对与编程语言相关的理论和技术的学习,提高在软件工程中应用这些理论和技术的能力。和编程语言有关的理论和技术包括:

形式语言和自动机理论、语法制导的翻译技术、类型论和类型系统、数据流分析的理论基础等,可以选择一部分作为教学内容;

LR分析和语法制导翻译等技术,代码生成和代码优化中的一些重要算法。

(3) 研究生阶段的目标是:通过对与编程语言密切相关的、更宽泛的理论和技术的学习,提高在科研工作中应用相关理论和技术的能力。这些理论和技术列举如下:

依赖于机器的各种优化技术;

其它范型的编程语言的理论和实现技术;

程序分析的理论和技术;

并行编译理论和技术。

3教学内容的选择

本节探讨在三种不同教学目标下的教学内容。不管怎样选择教学内容,都要有恰当的课程实践作为课堂教学的非常重要的补充。笔者已另外行文专门介绍在课程实践方面的经验和体会,因此本文不再讨论课程实践。

3.1普通高校本科

根据前面提到的目标,笔者认为,教学内容应强调对编译原理和技术的宏观理解及全局把握,而不要把学生的注意力分散到一些枝节的算法上,如计算开始符号集合和后继符号集合的算法、回填技术等。另一方面,教学内容和习题要包括一些从实际碰到的问题中抽象出来的例题和习题,鼓励学生用所学的知识去分析和解决实际问题。笔者在这方面已经有所尝试(详见文献[6, 7]),教材中主要各章都有配合该章内容的C语言小程序作为例题或习题。

针对编译的各逻辑阶段,笔者建议的教学内容如下。

(1) 词法分析

正规式、不确定的有限自动机、确定的有限自动机及其最小化是主线;同时要有用C语言写的一个简单语言的词法分析器,并介绍词法分析器的生成器。

有限自动机是一种经常用得着的概念和工具,放在编译原理课程中介绍最为合适。词法分析器的生成器是上述主线的自然产物,由于它比较简单,让学生通过它来开始理解程序生成的概念和工具较为合适。

(2) 语法分析

上下文无关文法是必备的基础知识。LL(1)文法和递归下降分析方法比较直观,便于学生接受,应首先介绍,并伴有一个简单语言的递归下降分析程序作为例子。在介绍自下而上分析的一般概念和使用LR分析表进行移进归约分析后,直接介绍分析器的自动生成器,并介绍归约时的语义动作,为下面阶段语义工作的描述奠定基础。

算符优先分析法没有必要讲,因为编译器的语法分析已不再使用这种方法。LR分析方法固然很重要,但由于SLR(1)分析、规范LR(1)分析和向前看LR(1)分析的介绍需要占用较多课时,因此以不介绍这几种LR分析表的生成算法而直接介绍LR分析表的使用为好。

(3) 静态语义检查

概述静态语义检查包括哪些方面,然后重点放在类型检查上。类型系统在编程语言的设计中占据重要位置,可以先介绍一下类型系统在编程语言中的作用,然后用语义动作来表达类型检查算法。

(4) 运行时存储空间的组织和管理

这是最需要搞明白的部分。尤其在用C这样比较低级的语言时,掌握这部分内容对编写程序和程序排错都很有帮助。具体应该介绍局部存储分配策略(即一个活动记录中各类数据的组织),静态分配、栈式分配和堆式分配等三种全局存储分配策略,非局部名字的访问方式和各种参数传递方式的实现。

(5) 中间代码生成

主要介绍各种形式的中间语言,把赋值语句和各种控制流语句翻译成中间代码的语义动作。对于类型和变量声明语句,主要关注怎样按语言的作用域规则组织符号表。至于符号表中符号的插入和查找方法在数据结构课程中已经介绍过,没有必要在这里重复。

(6) 代码生成

选择一种采用简单的寄存器分配策略的代码生成算法加以介绍,让学生对代码生成有所了解即可。

(7) 代码优化

用实例来介绍各类优化,让学生明白编译器能完成哪些优化,而不要给学生介绍各种优化算法。这对编程有用处,例如,在可读性好的源代码和优化的源代码两者之间做选择时,若知道那些优化可以由优化编译完成,则宁可选择可读性好的代码。

(8) 编译系统和运行系统

通常,除了编译器外,还需要一些其它工具的帮助,才能得到可执行的目标程序,这些工具包括预处理器、汇编器和连接器等。这些工具都较简单和明显。了解这些工具有助于掌握从源程序到可执行目标程序的实际处理过程,这些知识对于参与大型软件系统的开发是很有用的。

这部分主要是让学生了解预处理、编译、汇编和连接这个流程,目标文件的格式,连接时的符号解析,静态库和动态库等。

3.2重点高校本科

粗略地说,普通高校本科计算机专业在软件方面主要培养软件编程人员,而重点高校本科培养高一个层次的软件设计和开发人员。因此需要学生掌握或了解和编程语言有关的理论以及和编程语言实现有关的重要算法。

(1) 形式语言和自动机理论

形式语言理论是用数学方法研究自然语言和人工语言(如编程语言)的语法的理论,它只研究语言的组成规则而不研究语言的含义。自动机理论是以研究离散数学系统的结构、功能以及两者之间关系为主要内容的数学理论。形式语言分层的四类文法和图灵机等某些自动机的对应(接受同样语言)是形式语言和自动机之间的重要联系。形式语言和自动机理论在编程语言的描述和编译、自然语言的理解和翻译以及语法制导的模式识别等方面有着广泛应用。若想给学生介绍一点形式语言和自动机理论,编译原理课程是最理想的场所。

(2)LR分析方法

LR分析方法是一种高效的、自下而上的语法分析技术,它能适用于一大类上下文无关文法的分析。LR分析方法被广泛采用,各种分析器的生成器几乎都是生成LR分析器。因此在全面介绍语法分析方法时,必须把LR分析方法当作重点来介绍。LR分析表的生成算法较复杂,因此还需把该算法当难点来讲解。只有能全面把握LR分析方法时,才能说比较好地掌握了语法分析方法。

(3) 语法制导翻译

语法制导的定义和语法制导的翻译方案是描述编程语言翻译的两种常用形式方法。它们描述严格并便于理解,因此大部分有一定深度的教材都用它们来描述静态语义检查和中间代码生成等。它们易于实现,所以编译器的生成器都要求编译器的设计者用这样的方法来表达识别出输入串中的语法构造时要执行的动作。通过对语法制导翻译的实现技术的学习,会对程序生成器有更多的理解,这在软件工程中是很有用处的。

(4) 类型论和类型系统

类型论是为了避免集合论悖论而建立起来的数学理论,主要研究集合的分层、分类方法。类型系统是一种依据程序短语语义值的种类来对程序短语进行分类的语法方法,它用来防止程序出现某些上下文有关的错误。在计算机科学的编程语言理论中,类型论提供了研究、设计和分析类型系统的形式基础。编程语言的设计现在都是以类型系统的设计为中心来展开的;掌握类型系统知识对学习编程语言有重要的指导作用。此外,类型系统在软件工程、软件安全、高性能编译器的实现和程序分析等领域都有深入的应用。

目前,国内编译原理的教材一般最多从类型系统的实现——类型检查算法来粗浅地介绍类型系统的知识,缺乏类型系统在编程语言中作用的全面介绍,缺乏对多态类型这样的非普通类型及其类型检查方法的介绍。

形式语言、语法制导翻译和类型系统知识的学习有助于提高学生的形式描述能力。

(5) 数据流分析的理论基础

国内介绍代码优化的编译原理教材,对各种数据流分析问题,分别给出数据流方程及其迭代求解算法,也谈及它们之间的联系,但是没有把它们作为一个整体来抽象地研究。文献[2]突出数据流分析的理论基础,强调在数据流分析的一个一般框架下解决各种具体数据流问题,使教材能站在更高层面上讨论代码优化,给学生一种洞察数据流分析本质的认识。

通过从半格定义开始的数据流分析一般框架的学习和理解,可以提高学生的数学抽象能力。

(6) 代码生成和代码优化的算法

简单的代码生成算法离实际的代码生成器相差太远。寄存器分配的图着色算法、树重写方式的指令选择方法、为表达式树产生最优代码的算法、动态规划的代码生成算法、使表达式的计算次数最小化的程序变换方法和程序流图中自然循环的识别算法等,不仅能让学生了解代码生成和代码优化的技术,而且能给学生算法设计方面的启迪。

随着嵌入式系统应用越来越广,自主设计嵌入式系统软硬件的机会越来越多,要求软件开发人员具备这部分知识的场合也不断出现。

3.3研究生阶段

在国内,就现阶段来看,虽然直接参与编译器的设计和开发的工程师还是很少,但是编译器的设计影响着计算机科学的一些其它领域,如针对计算机体系结构的优化、新计算机体系结构的设计、软件质量、软件安全、程序翻译和提高软件开发效率的工具等,这些领域的研究和开发工作都需要编译原理的知识。

研究生阶段学习编译原理的有关知识,主要是提高在科研和开发工作中应用相关理论和技术的能力。由于授课对象是本科毕业于不同学校的研究生,他们在编译原理方面的知识背景大不一样,因此可以挑选文献[5]中第3.2节和该节列举的部分理论和技术作为讲课内容。

(1) 依赖于机器的各种优化技术

计算机体系结构的迅速演化引起对新的编译器技术一种不知足的需要,几乎所有的高性能系统都在利用两种基本技术:并行化和内存分层。并行性可以在指令级和处理器级分别发掘;内存分层针对这样的基本局限:构造非常快的存储器或者非常大的存储器是可能的,但是构造不出既快又大的存储器。

所有现代微处理器都开拓指令级的并行。这种并行对程序员是隐蔽的,程序员理解为串行执行的指令序列,会被硬件动态地检查其中的相关性,并尽可能并行发射这些指令。编译器对此的配合作用是重新整理指令,使得指令级的并行更有效。

文献[2]有这些内容的较详细介绍。这部分内容也可以在计算机体系结构的相关课程中介绍。

(2) 其它范型的编程语言的理论和实现技术

对于不同范型的语言,主要是让学生了解其影响语言实现技术的重要语言特征,以及它们对实现技术的具体影响。

就面向对象编程语言来说,其信息封装虽是非常重要的特性;但对编译器来说,实现这些作用域规则是简单而明显的。因此重点是在另一个重要的语言特征——继承性及其实现上,实现中的关键数据结构是虚方法表。

理解函数式编程语言并不困难,重要的是理解其既允许高阶函数又支持函数嵌套声明给实现带来的影响。重要的是明白此时栈式存储分配不再适用,活动记录必须创建在堆上。实现中的一些重要概念是函数变量的闭包、垃圾收集、逃逸变量、惰性计算和换名调用等。

其它还有逻辑编程语言,例如Prolog语言,使用这类语言的人很少,无特别需要则不必介绍。

(3) 程序分析的理论和技术

程序分析指的是以程序为对象的静态(如编译时)预测技术,它们可用来预言程序运行时的动态布局或行为的一种安全(忠实于语义)且有效(所需时空少)的近似(因为一般而言不能期望精确的解答)。除了用于代码优化外,程序分析还用在程序理解、程序测试、程序安全性分析和程序重构等许多方面。

除了代码优化中提到的数据流分析外,常用的程序分析技术还有基于约束的分析、抽象解释、类型和结果系统、符号执行等。

国内已经有一些高校开设了专门的程序分析课程,相应教材(文献[8])也已经问世。

(4) 并行编译理论和技术

并行编译器是指处理并行编程语言或将串行编程语言的程序并行化的编译器。这样的编译器对程序员隐蔽了它发现程序并行性、把计算分布到多个处理器、极小化处理器之间的同步和通信的详情。并行化技术已经用于自动地把串行科学计算程序翻译成多处理器代码。

并行编译中采用的主要技术是依赖性分析和循环并行化等。这些内容已经被写入国内个别编译原理教材(文献[9])中。

参考文献:

[1]Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. Compilers: principles, techniques, and tools[M]. New York: Addison- Wesley, 1986.

[2]Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers: principles, techniques, and tools[M]. 2nd edition. New York: Addison-Wesley, 2007.

[3]Andrew W. Appel. Modern compiler implementation in C[M]. Cambridge, England: Cambridge University Press, 1998.

[4] 张素琴,吕映芝,蒋维杜,等. 编译原理[M]. 2版.北京:清华大学出版社,2005.

[5] 陈意云,张昱. 编译原理[M]. 2版.北京:高等教育出版社,2008.

[6] 张昱,陈意云. 编译原理课程实践改革探索[J]. 计算机教育,2008(8):2426.

[7] 陈意云,张昱. 编译原理习题精选与解析[M]. 北京:高等教育出版社,2005.

[8] 刘磊,张晶,单郸,等. 程序分析技术[M]. 北京:机械工业出版社,2005.

[9] 陈火旺,刘春林,谭庆平,等. 程序设计语言编译原理[M]. 3版.北京:电子工业出版社,2001.

Discuss on Teaching Content of Compiling Principles

ZHANG Yu, CHEN Yi-yun, Guo Yu, LI Zhao-peng

(School of Computer Science & Technology, University of Science & Technology of China, Hefei 230026,China)

Abstracts: By analysing the evolvement of foreign teaching materials on Compiling Principles and combining self- experience in teaching and scientific research, three levels of teaching goals on Compiling Principles are put forward, i.e. goals for undergraduates from common institutions of higher learning or from key institutions of higher learning, and goals for postgraduates. Moreover the teaching contents for those three levels are proposed for your information.

Key words: Compiling Principles; programming language; teaching goals; teaching content