独立学院编译原理课程教学改革

沈岚岚

（桂林电子科技大学 信息科技学院，广西 桂林 541004）

0 引 言

编译原理是计算机专业的一门重要基础课，通过介绍和学习编译程序构造的一般原理和基本方法，培养学生的系统能力、程序设计和分析能力。独立学院是高校内部系院改造的二级单位，专业设置大多以工程应用为主，目的是使毕业生可以直接服务社会，同时比高职高专毕业生具有更深厚的专业理论基础，兼具学术性特色。独立学院的培养目标、教学对象、教学环境等都和传统高校有所区别，因此在教学上也应有自己的特色。

1 存在问题及分析

当前独立学院的编译原理课程教学大多照搬传统高校的形式，按照编译器的构造分成词法、语法、语义分析，中间代码生成、优化，目标代码的生成等几个章节，每个章节讲授相关方面的知识，从而进行理论和实践教学。编译系统是一个相当复杂的系统，编译原理课程的各个环节都包含了丰富的理论、大量的算法和实现的方法。独立学院受限于课时、学生基础等情况，在现有的教学体系之下，很难取得良好的教学效果，学生往往觉得这门课程理论繁多、算法抽象、实践困难，各个知识点也难以贯通。

从本质上说，编译器的构造是一个规模相当大的复杂算法问题，导致讲授其原理和技术的编译原理课程也具有复杂性，并造成了教学上的困难。复杂问题的求解往往采用“分治”的方法，即将复杂问题分解成规模较小的子问题，通过求解一个个子问题降低复杂度，并根据子问题之间的联系最终解决原本复杂的问题。编译原理的教学虽然也进行了一定的分解，但是这种分解是基于编译器的构造，而不是基于教学，子问题的规模仍然偏大，有必要根据教学规律进行进一步分解。

对问题进行有效分解的前提是对其有一个清晰的定义，编译原理课程教学并不是编译器的构造，其问题的表现形式是各个知识点。应该将教学内容分解成各个知识点，针对这些知识点进行教学方法的设计，以实现“各个击破、分而治之”。对于学科知识的定义，Denning提出了一种二维矩阵的方式，其“纵向”关系为各分支学科，“横向”关系反映的是学科所研究的基本内容[1]。董荣胜从认知规律出发，认为计算学科的所有知识点可以归入抽象、理论和设计3种形态中，提出将这3种形态作为二维表的“横向”关系[2]。认知规律是教学的基本规律之一，我们采用这种定义方式将编译原理课程各章节内容进行定义和教学设计，并以词法分析为例进行详细阐述。

2 基于抽象、理论和设计的知识定义和分解

抽象指的是对现实世界的认识，最初可能是感性而粗糙的，但能够通过理论的指导进行进化而不断趋于完美；理论是系统而完备的，其表现形式是定义、定理和证明等；设计是对知识的运用，是一个有效的装置或系统[2]。这三者之间的联系符合对事物从感性认识到理性认识，并用认识来指导实践的认知规律。

词法分析的任务是将待编译的源程序进行分解，使之成为如属性、值等的单词二元组，然后用计算机表示这样一个过程并自动执行，使它变成可计算的。在数学家哥德尔的研究中，可以给每个对象配上1个数，接下来的证明或计算过程就是对这些具有某种确定性质的符号的有穷序列所做的变换。根据这个理论，可以将单词的每一属性指定一个唯一的自然数进行表示，即使用哥德尔配数法来进行表示，后面的分析过程也就是将源程序的字符序列变成哥德尔数的序列。一般来说， 1个高级语言的源程序至少有5类单词（见表1）。

表1　单词属性和哥德尔数

进一步研究发现，关键字、运算符和界符是预先定义好的，其数量有限；此时可以省略单词的值，而为每一种符号定义1个哥德尔数，建立1个数据字典，以提高分析效率，由此产生了词法分析结果的最终表现形式。这个过程体现了经典理论和现实技术的结合，这样的例子在编译原理课程教学中还有许多，按照抽象、理论和设计来进行教学内容的分解能够降低问题的复杂度，可以更好地进行教学。基于这3种形态对词法分析教学内容的分解见表2。

Backus-Naur范式、正规式等是对词法组成和规则的形式化描述，状态转换图是按照规则识别字符串的工具。形式语言和自动机的相关理论可以指导词法规则和状态转换图的构造，并对它们进行优化，以便更有效的应用，并产生自动识别的算法。通过这些算法，可以编写出词法分析程序以及构造词法分析程序的自动工具。

通过表2的分解以及3种形态之间的联系，可以知道为什么学习这些知识、这些知识起什么作用，从而将各知识点贯穿起来。此外，不同形态有着各自的思维特点和认知方法，讲授抽象形态的知识时应尽可能使其形象化、具体化；理论形态的知识常用到推导、证明等方法，可以类比数学的教学方法；设计形态主要是针对实践能力的培养，可以通过工程训练的方法进行。通过这些原则可以对各个知识点进行针对性的教学，以实现“各个击破、分而治之”的教学目的。

表2　词法分析的知识分解

3 “词法分析”的教学设计与实现

在编译原理课程的教学中，算法理解能力和实践能力的培养往往是教学的重点和难点，它们分别属于抽象和设计形态的内容。针对2种形态的特点，我们给出了具体的教学设计和实现方式。

3.1 词法分析中算法的讲授

词法分析在实现过程中产生了很多算法，这些算法具有抽象化和自动化的特点。传统教学方式中，对算法的表示常使用伪代码的形式，文本化的表示方式较难引起学习者的兴趣，而且学生需要自行想象运行结果，不够直观；直接给出源代码虽然能够直观地看到算法的运行，但涉及众多语法知识和实现技术，分散了对算法本身的关注，实现起来也比较困难，所以这些教学方式往往以教授为主，配合板书、PPT，很少使用其他教学工具。

可视化编程工具Raptor[3]提供了一种基于流程图的程序开发环境，使用Raptor编写的NFA确定化算法的主要程序如图1所示。在图1中，定义二维矩阵nfa和dfa分别表示输入和输出，基于哥德尔数的理论，有限自动机的状态以及输入的符号都可以转化成自然数，因此，使用二维矩阵的行下标表示状态，列下标表示输入字符，将有限自动机由图形转化成了邻接矩阵。

Raptor提供了一种直观的算法表达框架，使用了类似流程图的语言来进行程序编写，这种可视化的算法表示形式更能引起学生的注意，执行过程又可以使学生直观地感受算法的所有运行步骤，观察到所有变量当前的内容，运行结果也能够直接验证算法的有效性。

3.2 词法分析器的编写

词法分析器的编写属于设计形态的知识，运用对现实世界的认识来进行实践，开发一个系统或装置。在词法分析中，就是进行词法分析器的编写，编写的前提是要具备一定的先期知识，手工构造词法分析器需要先画出最简DFA，而用自动工具进行生成只需写出正规式即可。

实践能力可以通过反复训练进行培养并逐步提高，分任务的词法分析器实践方案见表3。

表3　词法分析实验任务要求

图1　NFA确定化的Raptor程序

从任务①到任务④难度逐级递增，并给出每级任务所需的思维能力。在教学中，教师可以详细讲解任务①的实现方法，甚至可以视情况给出部分或全部源代码供学生进行仿写；任务②是对任务①的改进，首先需要学生自己进行浮点数的表示，再参照任务①的方法进行浮点数的识别，还可以增加一些新的运算；任务③则需要识别出标识符和关键字，让学生自己设计标识符规则和所用到的关键字，其中标识符的识别方法类似于浮点数的识别，关键字的识别方法类似于运算符的识别。这3个任务已基本包括高级语言中所有种类的单词符号的识别方式，以此为基础，可以尝试选择一种高级语言让学生进行词法分析。任务④是补充知识，旨在开阔视野，可作为课后作业，要求学生翻阅资料，进行需求分析并予以实现。让学生在实践中体会到编译器构造时产生理论技术的宝贵性，该技术不只应用于产生一个编译器，还可应用于许多领域。

通过不断深入迭代的任务体系，使学生在完成每级任务时产生“过关”的成就感，而下一任务的出现又对其提出了新挑战，促使学生不断地去学习、探索，使学生针对同一问题能够得到反复的、大量的训练，从而实现思维能力的锻炼和实践能力的提高。

4 结 论

随着科学技术的发展，并行编译、动态编译等在多核系统、单片机、信息安全领域等方面的作用越来越大，编译原理课程的作用也越来越重要。不同于传统高校教学，独立学院的编译原理课程教学应有自己的特点。我们将编译原理课程教学视为一个对复杂问题的求解过程，运用“分治”法将其分解并各个击破，可以实现较好的教学效果。

参考文献：

[1]Denning P J, Comer D E, Gries D, et al. Computing as a discipline[J]. Commuications of the ACM, 1989, 32(1): 63-70.

[2]董荣胜. 计算机科学导论: 思想与方法[M]. 3版. 北京: 高等教育出版社, 2015: 53-62.

[3]董荣胜. 计算机思维结构[M]. 北京: 人民邮电出版社, 2017: 34-56.

[4]程向前, 周梦远. 基于RAPTOR的可视化计算案例教程[M]. 北京: 清华大学出版社, 2014: 1-27.

[5]前桥和弥. 自制编程语言[M]. 北京: 人民邮电出版社. 2013: 17-41.

[6]王峰, 张浩军. 编译原理课程教学中的词法分析及其应用[J]. 计算机教育, 2013(9): 19-23.