对编译原理课程教学中计算思维培养的探讨

王 挺 李梦君 周会平

摘要:本文首先回顾了编译知识在计算机学科中的地位和作用,分析了“编译原理”课程在理论性和技术性上的特点,然后结合计算思维概念分析了计算思维在编译理论和技术发展中的作用,并结合编译课程教学中的知识点,探讨了在教学中如何结合具体案例培养计算思维。

关键词:编译原理;计算思维;课程改革

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

1编译知识在计算机学科中的作用

自从20世纪50年代中期诞生世界上第一个高级语言编译器——Fortran语言编译器以来,编译技术不断进步,已经成为计算机科学中发展最迅速、最成熟的一个重要分支。自1966年以来的所有55位图灵奖获奖者中,有近1/3的科学家是因为在程序设计语言和编译方面的成就而获得该项奖励,可见程序设计语言和编译的发展集中体现了计算机科学发展的重要成果与精华。计算机应用能发展到今天,编译技术的发展有着极其重要的、不可替代的作用。

五十多年以来,随着编译技术的发展,有关编译原理和技术的内容被逐步引入到了计算机专业本科教学中。从早期各阶段ACM和IEEE的计算机专业教学计划,到近年ACM和IEEE联合制定的CC 2005,再到我国教育部高等学校计算机科学与技术教学指导委员会2006年编制的《高等学校计算机科学与技术专业发展战略研究报告暨专业规范(试行)》,直至最新的ACM和IEEE联合制定的CS2008,都把有关编译原理和技术的知识作为重要教学内容列入。目前,我们编译原理课程的教学内容覆盖了CS2008体系中程序设计语言领域、算法和复杂性等领域的多个知识单元。

2编译原理课程的理论性和技术性特点

编译程序的构造原理和技术可以说是计算机科学技术中理论和实践相结合的最好典范。在许多课程的教学中,经典理论和先进技术之间的联系往往缺乏具体而形象的例证,而“编译原理”课程在这方面具有得天独厚的优势。形式语言和自动机理论为编译程序的设计提供了坚实的理论基础,正是在科学理论的保证下,才形成了一系列先进的编译程序设计方法和工具,使得编译程序的构造具有很高的系统性和自动化程度。例如,正是有了有限自动机的经典理论,才有了LEX这样的高度自动化的词法分析器的自动产生器;正是有了Knuth提出的LR分析方法,才有了YACC这样的高效的语法分析器产生器,将程序员从繁琐的代码编写中解放出来。编译课程的教学既要强调经典理论在计算机科学中的重要作用,又要注重介绍利用这些基础理论来设计和构造编译程序各模块的先进方法及工具,可以具体形象地说明经典理论与先进技术的关系。理论和实践相结合是“编译原理”课程的鲜明特色。

“编译原理”课程特别强调运用理论知识进行实践的能力和素质,以突出计算机专业人才培养的特色。“编译原理”是每个优秀的计算机专业人员必修的一门课程。通过编译程序这一具体的案例,学生可以综合理解和运用计算机的程序语言、操作系统和体系结构等各种软硬件知识,形成计算机专业人才特有的系统的专业知识结构。在系统学习编译的理论和技术的过程中,学生一方面对科学理论的基础作用有了充分的认识,提高了学习经典理论的兴趣,形成了较高的理论素养;另一方面,通过课程综合性的实践,分析或改进简单或复杂、原型级或产品级的各种编译程序或工具,也可以提高灵活运用理论知识、设计较大规模的软件来解决实际问题的能力。在课程的学习和实践中,学生可以深刻体会到理论学习的意义和动手实践的乐趣。

有许多人认为,如果今后不从事编译器的开发,编译知识就显得并不重要了——事实上并非如此。编译课程鲜明的理论性和技术性特点,使得这些知识对于计算机专业人员来说具有重要作用,甚至可以说是计算机专业人才区别于一般计算机人员的重要知识结构。对于将来从事编译系统设计工作的学生来说,编译课程的学习当然可以使他们掌握和理解编译系统的结构、工作流程以及编译程序各组成部分的设计原理和实现技术,获得分析、设计、实现和维护编译系统的初步能力,打下坚实的能力和知识基础;而对于那些将来不从事编译器研制的学生来说,编译课程的教学对于提高他们对计算机系统总体认识也具有重要的意义。通过学习编译的理论和方法,学生可以提高对程序设计语言的设计与实现等知识的综合理解,而这些知识对于准确掌握程序设计语言,学习新的编程范型,理解程序,开发出正确的软件都是不可缺少的基础。图灵奖获得者Perlis教授的名言“To understand a program you must become both the machine and the program”就精辟地说明了这一点。此外,编译课程介绍的经典语言分析方法和工具,对于一些实用的工具和软件,如自然语言理解、网络信息处理、网络协议的分析与实现等领域的软件或工具的研制,都是很好的基础。更为重要的是,编译课程中介绍的一些经典的理论和方法,对于传授计算机科学研究的方法、训练学生的思维都是难得的生动案例。因此,不能把编译课程片面地理解成为一个介绍编译程序的课程,而应当把该课程的教学放在培养专业素质、训练思维的层面加以认识,特别是应当强调如何在编译的教学中培养学生的计算思维。

3计算思维及其在编译理论和技术发展中的作用

计算思维(Computational Thinking)是卡内基梅隆大学计算机科学系Jeannette M. Wing教授在2006年提出来的先进的教育理念,被认为是近十年来产生的最具有基础性、长期性的学术思想,并将成为21世纪计算机科学研究的热点。

计算思维是运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为,它包括了一系列广泛的计算机科学的思维方法。Wing教授认为,计算思维不仅仅属于计算机科学家,它将和阅读、写作和算术一样,是21世纪每个人必须具备的基本技能。计算思维已经在其他学科中产生影响,而这种影响在不断拓展和深入。例如计算生物学、计算博弈理论、纳米计算和量子计算等新兴研究领域的发展正在深刻改变生物学、经济学、化学和物理学领域研究的思考方式。

典型的计算思维包括一系列广泛的计算机科学的思维方法:递归、抽象和分解、保护、冗余、容错、纠错和恢复,利用启发式推理来寻求解答,在不确定情况下的规划、学习和调度等。显然,这些计算思维方法都可以在许多编译理论和技术的发展中找到痕迹,很多编译成果正是运用计算思维的结晶。例如,抽象和自动化是计算思维的两个重要手段,也是编译理论和方法产生的基础。编译课程中介绍的语法知识描述、词法分析、语法分析、属性文法、乃至优化等知识点,都体现了面向具体应用、从实际问题中抽象出科学问题并运用科学的思维方法进行问题求解的思想,其成果根植于坚实的经典理论,并应用于实践,以推动技术的进步。因此,在编译课程的教学中,结合编译理论和技术中经典的案例培养学生的计算思维,是一条值得探索的途径。

4结合编译案例的计算思维培养

如何培养“计算思维”,是目前计算机教育界非常关心的问题。例如,在计算机专业的教学中,有些学校在专业核心课程中融入计算思维的培养;在非计算机专业的教学中,对计算机导论类或程序设计类的课程进行改革,针对学科交叉的需求,从教学内容和方法上进行改革,培养学生的计算思维。总体来说,计算思维的培养应该贯穿在大学教育的全过程,甚至在大学之前的教育中。计算思维对于计算机专业的人才培养提出了新的要求,我们必须在专业课程教学中结合计算思维的培养。

编译课程的知识体系完整,既有经典理论成果奠定的坚实基础,又有在实践中发挥巨大作用的先进技术,其中很多知识点都为计算思维提供了很好的诠释和生动的案例。下面,我们从抽象、自动化、递归、问题分解和权衡等典型计算思维方法出发,探讨结合编译案例培养计算思维的可能途径。

(1) 抽象

“抽象”是科学研究的重要手段,也是计算机科学研究的重要工具。在编译理论和技术的发展中,正是运用“抽象”这一有力工具,才获得了一系列的重要成果。例如有限自动机、形式文法等都是重要的抽象工具,有了这些工具,才能够把握词法分析和语法分析等问题的本质,发现其中规律,最终形成一系列的自动分析方法。

(2) 自动化

将抽象思维的结果在计算机上实现,是一个将计算思维成果物化的过程,也是将理论成果应用于技术的实践。有限自动机、预测分析程序、算符优先分析、LR分析等编译经典方法,都是在抽象的基础上将知识和控制分离(即分析表加控制程序),从而获得了经典的分析工具,而这种知识和控制的分离也为分析工具的自动产生提供了可能。自动化的思维方法不仅体现在编译程序本身的工作机制上,更体现在编译程序的生成工具的研究和设计上。

(3) 递归

许多编译中的问题都具有明显的递归特征。运用递归思维解决复杂的问题,通常是对问题进行逐步化简,最后得到了一个规模非常小、非常简单、更容易解决的类似问题,将该问题解决后,再逐层解决上一级问题,最后解决了较复杂的原始问题。编译中的递归下降分析是最直观的对递归思维的运用,此外,基于树遍历的属性计算、语法制导翻译都是典型的递归问题求解。

(4) 问题分解

程序设计中的“自顶向下、逐步求精”的思想就是一种典型的问题分解的计算思维方法。运用问题分解这种思维方法进行问题求解,首先须做出对问题本身的明确描述,并对问题解法做出全局性决策,把问题分解成相对独立的子问题,再以同样的方式对每个子问题进一步精确化,直到获得对问题的明确解答。在编译程序的设计中,通过引入中间语言,将编译程序划分成前端和后端,就是一种典型的分解问题的思路。

(5) 权衡

“编译原理”课程是一门理论性和技术性都非常强的课程。理论研究重在探寻问题求解的方法,而在编译程序的设计和实现过程中,对于理论成果的研究运用又需要在能力和运用中做出权衡。这方面一个典型的例子是,我们知道,虽然高级语言的大部机制都可以由上下文无关文法来描述,但是上下文无关文法不能完全刻画高级程序语言的所有规范,有些语言机制甚至存在二义性。但是上下文无关文法的分析是高效的,所以我们在编译程序设计中依然采取上下文无关文法来描述高级语言语法,但是在具体实现时,通过改造分析表消除冲突、符号表操作、语义检查等手段,去实现上下文无关文法分析所不能完成的功能——这正是在具体实践中结合具体问题进行权衡的结果。

5结束语

计算思维的培养不是哪一门课程的教学能解决的问题。对于计算机专业教育来说,应当关注在各专业课程中的计算思维的培养,强调对各种原理和方法进行提炼,从思维方法的高度培养学生,使学生能够应用计算思维解决问题。大学计算思维的教育应贯穿于整个大学教育,做到学习期间不断线。

参考文献:

[1] Jeannette M. Wing. Computational Thinking[J]. Communications of ACM, 2006,49(3):33-35.

[2] 何炎祥,伍春香. 计算机专业不需要编译原理课程吗?[J]. 计算机教育,2009(4):61-62,85.

[3] Alan J. Perlis. Epigram on Programming [J]. GPLAN Notices, 1982,17(9):7-13.

[4] Owen Astrachan, Susanne Hambrusch, Joan Peckham, et al. The Present and Future of Computational Thinking[C]. SIGCSE09, 2009,USA:549-550.