“编译原理”教学实践探究

摘要：教学需要“教”与“学”双方的密切配合。树立“学生为主体、教师为主导”的良好教学关系，是成功教学的关键。本文根据“编译原理”课程的特点，提出应用启发式教学的思想，提高学生在学习中的主体地位，多方面增强学生的学习兴趣。文章结合笔者17年的“编译原理”课程教学实践经验，总结了开展启发教学、提高教学质量的一些粗浅策略。

关键词：编译原理；文法；有穷自动机；下推自动机；启发教学；教学策略

教书育人是教师的天职。教学，顾名思义，包含“教”和“学”两个方面。教师需要“教”给学生知识和方法；而学生是学习的主体。我们要取得好的教学效果，首先要激发学生的学习兴趣。

良好的开端是成功的一半。开课伊始就让学生产生学习热情、学习兴趣是非常重要的。两千多年前，孔子曾说过：“知之者不如好之者，好之者不如乐之者。”意思是懂得它的人，不如爱好它的人；爱好它的人，又不如以它为乐的人。爱因斯坦也说过：“兴趣是最好的老师。”学生感兴趣了，教学就成功了一大半。

1.“编译原理”课程概述

“编译原理”课程是计算机科学专业的一门重要核心课程。计算机语言之所以能由单一的机器语言发展到今天的数千种高级语言，是因为有了编译技术。自从20世纪50年代早期第一个编译器出现以来，编译技术成为计算机科学中发展最迅速、最成熟的重要分支。自1966年设立图灵奖以来，程序设计语言、编译理论与方法方面的得奖成果约占总数的1/3。可见，程序语言及其编译的研究在计算机科学中始终处于非常重要的地位。

“编译”是将高级语言描述的程序转换成与之等价的低级语言表达的程序。在编译系统的设计与实现中，用到计算学科的很多基本原理、技术和方法。Alfred V Aho编写的编译教材作为编译课程方面的经典教材，被奉为“龙书”。他在该书第一章的第一句话提到：“编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机科学家的研究生涯中，本书中的原理和技术都会反复用到。”北京工业大学的蒋宗礼教授认为，编译课程是计算机专业最为恰当、有效的知识载体之一。

2.“编译原理”课程在整个课程体系中的地位和作用

从计算机应用的发展来看，编译技术在其中发挥着极其重要且不可替代的作用。正是在编译技术的支持下，程序设计才从以繁琐的低级语言为工具，发展到以接近自然语言和数学语言的高级程序设计语言为工具，软件开发也从模块化的软件开发方法发展到了面向对象的开发方法。编译技术的发展极大地提高了软件开发的效率，深刻地影响着软件开发方法的变革，推动着计算机应用不断地向社会的方方面面延伸。

编译程序作为符号处理系统，广泛应用到其他软件的设计中。

例如，编译在反病毒中的应用：对于高级文本语言类的文件（如网页类文件），应用编译技术的词法分析和语法分析原理，可准确快速地定位病毒代码，从而构造反病毒程序。编译在机器翻译系统和文本分类中的应用：机器翻译系统又称为语言翻译系统，输入是一种语言，输出是功能上等价的另外一种语言。例如，中文和日文的相互翻译。文本分类是把互联网上的海量信息进行分类，便于阅读。它们都离不开编译中的词法分析和语法分析技术。

“编译原理”课程含有基本问题求解的典型思路和方法，通过本课程的学习，使学生容易理解和掌握“问题、形式化描述、自动化（计算机化）”的解题思路，培养学生的形式化描述和抽象思维能力。继程序设计、数据结构与算法等课程后，该课程使学生从系统层面上对算法和程序进行再认识，提高学生对“程序设计语言”、“操作系统”、“计算机原理和体系结构”等课程知识的综合理解。

该课程理论的学习不应仅局限在构造高级程序设计语言编译器方面，还应把教学的重点放在培养专业素质、训练抽象思维的层面上。在编译课程的教学中，结合编译理论和技术中的经典案例，培养学生的计算思维。

例如，抽象计算思维方法运用自动机和形式语言文法的形式化工具，把词法分析和语法分析问题的本质抽象出来，从而可以发现解决该问题的自动化方法。自动化计算思维方法在计算机上实现抽象的结果，词法分析环节的有穷状态自动机、语法分析环节的LR分析法都是经典的编译方法，它们是在抽象的基础上对分析表进行处理的算法。编译器的自动生成工具的设计正是体现了自动化的思维方法。

3.启发式教学的设计及实施

师者，传道授业解惑也。“传道”就是体会学生在想什么，能够启发、引诱学生提高兴趣；“解惑”并非简单地解答疑惑，好老师会帮助学生知道什么是“惑”，引导学生一步步地去探究，真正调动学生的学习兴趣，发挥个人的潜能，从而达到“解惑”的目的。

爱因斯坦曾经说过，一个人的成功不是解决问题，最重要的是提出问题。教师是教学的组织者和实施者，如何激励学生的学习积极性、帮助学生积极地获取知识和技能，使学生获得综合运用知识能力等，这些对教师来说更具挑战性。

在计算机学科中，“编译原理”是公认较难也是非常重要的一门专业课程。如形式语言、自动机理论、LR分析、语法制导翻译等理论，内容相对抽象。但若方法应用得当，也会化难为易，使学生非常轻松地掌握看似艰涩的编译原理和相关技术。

在教学中，教师要以人为本，把学生的潜能挖掘出来，同时培养学生还要因材施教，根据学生的能力给予不同的指导方式，充分发挥学生的潜力，这样才能使学生很快成长起来。

课堂教学是实现素质教育的主渠道。笔者在长期的教学实践中，习惯了从学生的角度出发，换位思考，回想自己学习新知识的困惑，设想学生初次接触编译这门课程，会有什么疑问，又会对什么特别感兴趣？如果一开始，就能从学生的关注点出发，一步步引领他们解开心中的疑惑，树立起学习的信心，而不是一味地照本宣科，让学生兴趣寡然，则后面的教学过程可能就是柳暗花明，得到事半功倍的效果。

开学第一课是至关重要的。学生借此认识教师并了解这门课程。教师通常在第一课上要概括介绍学习“编译原理”的目的，编译是“干什么用的？”“编译”就是将各种高级程序设计语言书写的源程序翻译成等价的目标程序（低级语言）的过程，因此编译程序就是一个语言转换器。换言之，有了编译程序，计算机就能“读懂”用户书写的高级语言程序。实际上，编译程序充当了一个“翻译者”的角色，在人和计算机之间架起了一座桥梁。有了编译器，用户不必关心或掌握计算机内部的繁琐细节（如指令系统、机器代码），只需要掌握某种高级语言（如C语言），就可以给计算机下达指令，让它为自己服务。

接着，教师可以引导学生思考。既然编译程序完成的是程序设计语言的翻译工作，那么它和我们生活中的哪些常识有共通之处呢？学生当然接触过自然语言的翻译，会联想到英汉对译。英译汉通常需要几个过程：识别单词、语法分析、理解含义、写出译文。与此类似，编译程序也要经过词法分析（识别单词）、语法分析、语义分析（理解含义）、目标代码生成，才能最终将源语言（source Language，SL）程序翻译成等价的目标语言（Object Language，OL）程序。此时，教师可以自然地引入编译程序的“T”型图描述，它非常形象地反映了编译程序的三个要素：源语言、目标语言、书写编译程序的语言。

既然编译程序要分析源语言，自然要了解语言的定义机制，从而自然地进入到文法的学习。文法是语言的定义装置，它可以用有穷的规则定义无穷的语言（使用递归规则就可定义无穷语言）。这时我们可以让学生浏览“编译原理”教材的目录，让学生发现全书实际上是按照编译程序的实现步骤设立所有章节的。首先是概述（了解编译的整体过程），接着介绍文法和语言（了解源程序是如何定义的），然后依次阐述编译的各个阶段：词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成。编译原理的学习过程中，会涉及许多看似抽象的概念和原理，其实，都是为“一个中心”（实现翻译）服务的。

在编译的学习过程中，引导学生把自己想象成设计者。例如学习词法分析时，怎样完成单词的识别？学生们经过思考后，会按照从左向右的扫描顺序，一一解读每个字符；如何分辨出不同的单词符号？寻找规律，发现不同单词，其开始符号各不相同；因此，按照开始符的不同，识别不同单词，拼写单词直到遇到非法符号即可终止。至此，引入有穷自动机（Finite Automata，FA）的定义，即词法分析程序的数学模型，并画出FA的状态转换图：一种非常直观的表达方式。学生们由于参与了这一过程，会感到兴趣盎然，很有成就感。与此同时，我们可以给出现实生活中的实例，如一个人带着一头狼、一棵白菜和一只山羊过桥，要求每次人只能带一样东西，如何保证在羊不被狼吃掉，而且白菜也不被羊吃掉的前提下全部过桥呢。抛出这个问题，让学生们试图应用有穷自动机来解决这一问题。模拟这一问题实现的有穷自动机如图1所示。（注：m代表人；g代表山羊；w代表狼；c代表白菜。）

进一步引申，我们发现有穷自动机更是实时系统的一般建模工具，可以解决大量实际问题。所以，构造词法分析程序仅仅是有穷自动机的一个应用。掌握有穷自动机这种形式化描述工具，对于计算机学科的学生来说具有极其重要的意义，它可以提高学生计算思维的能力，让学生了解计算机解决问题的思路。

语法分析的学习也是难点。难点知识在高校计算机教育中，不仅对于学生是学习难点，对于教师也是讲授难点。教师应该对知识点特别熟悉，并能和相关应用案例联系起来。首先应该了解它与词法分析有何不同，为何不能延用有穷自动机来分析，而必须采用新的分析方法和技术。由于编程语言的嵌套性质，使得编程语言的语法描述通常要采用上下文无关文法（ComeXt Free Grammar，CFG），如描述左右括号配对的情形，用如下文法来描述。

G[S]：SSSI（S）|ε

这类文法描述的是2型语言，而有穷自动机仅能分析3型语言，即线性（一般为右线性）语言，没有记忆功能，即无法记住前面读了多少个“（”，当然也无法确定“（”与“）”是否匹配。教师可以提示学生：学过的何种数据结构具有记忆功能呢？有人可能会想起栈，其“后进先出”的特性使其具有一定的“记忆”能力。因此，语法分析的数学模型就是带有下推栈的有穷自动机，即下推自动机（Push Down Automata，PDA）。因此，下推自动机的引入，也是出于语法分析的需求，这是由于上下文无关文法CFG具有有别于3型文法的一个本质特征：自嵌入特性。

不论是用于“自上而下”分析的LL分析器，还是“自下而上”分析的LR分析器，都是下推自动机的特例，它们的不同之处在于：对栈的使用方式不同。因为一个是从文法的开始符号出发，一个是从给定的输入串出发开始分析的。

自动机理论可以用来描述系统行为。如：有穷自动机FA可以描述如（abc）*的语言。（abc）*的FA表示如图2所示。相应地，FA可用于刻画并发系统，在一个时间段内执行一系列操作，这些操作之间满足一定的先后顺序。

下推自动机PDA可以描述如anbn（n∈N）语言。相应地，PDA可刻画这样的系统：在一个时间段内执行一系列操作，这些操作之间不但满足一定的先后顺序，而且某两个不同操作的数量之间有匹配关系。PDA可看成带有下推栈的FA，但是不能用FA的状态转换图表示。

语法分析后，要完成语义分析。语义分析主要完成程序设计语言中上下文相关（敏感）成分的分析。如类型检查，标识符需要先定义再使用，函数的形参个数和实参个数应该一致等。学生很容易理解这些要求，虽然这些要求本来都是语法规定，但由于无法用上下文无关文法CFG来描述，才将它们纳入语义分析范畴。我们可借助符号表，采用语法制导翻译，完成语义分析和中间代码的生成。

只有清楚地认识编译程序各阶段的任务，学生才能在学习中保持浓厚的兴趣，积极思考解决问题的方法。如在语法分析中，有了自己的深入思考、探究后，学生对自上而下的LL分析方法以及自下而上的LR分析方法的提出，就会有更深刻的体会。课堂上先给出一定时间思考，怎么来分析？如果是自己来构造会怎么做？还差哪些条件？这样，有了主动的思考，工具的提出也顺理成章，而不是生硬地抛出一个个抽象的原理和概念。

4.结语

启发式教学是充分调动学生学习兴趣、学习潜能和学习积极性的一种重要教学方式。文章根据笔者十余年的“编译原理”教学实践及体会，提出实施启发式教学的一种有益尝试，即抓住主要脉络（一条主线），顺藤摸瓜，将编译的所有概念、原理、技术和方法都串在这条线上。学到哪儿，首先抓住当前要解决的问题，然后找方法，最后在实践中（课程设计）加以应用。所有学习的内容，都是围绕着编译程序的翻译工作这样一个中心任务，来分析应该使用哪些工具才能完成相应的词法分析（有穷自动机）、语法分析（下推自动机）、语义分析和目标代码生成。这样，学生在学习过程中思维清楚、目的性强，容易产生兴奋点，自主学习的效果非常好。

“教”与“学”需要双方密切配合。教师应该关注“教什么”和“怎么教”，即关注课程的基本内容、重点、难点是什么，将培养学生什么样的能力，用哪种教学手段教学比较恰当。在课堂教学中，以学生为主体、教师为主导，教师和学生建立良好的教学关系，师生互动，教学相长，不但给学生提供更多有益的指导，也促进了教师自身素质的提高。教师还应及时把握本学科的最新发展动向，更好地服务于教学。