以计算思维能力培养为导向的“编译原理”教学改革探索

谌志群，王荣波，黄孝喜

（杭州电子科技大学 计算机学院，浙江 杭州 310018）

0 引言

“能力导向”是本科教育的基本追求，有利于培养学生的可持续发展能力。 “能力导向”教学与“知识导向”教学并不矛盾，两者是相辅相成的关系：以知识为载体，通过对知识的学习，掌握恰当的问题求解思想和方法，培养学生的（专业）能力；能力的增强，反过来会促进学生学习、掌握甚至发现更多的知识。所以，先进的教育倡导研究型“教”与“学”，尊崇的是“能力导向”[1]。

计算思维能力是计算机类专业人才4 大专业基本能力之一 （另外3 个是算法设计与分析能力、程序设计与实现能力、系统能力）[2]。 计算思维是美国卡内基·梅隆大学计算机科学系主任周以真（Jeannette M. Wing）教授提出的。 2006 年 3 月，周教授在美国计算机权威期刊 《Communications of the ACM》上给出了计算思维（Computational Thinking）的定义：计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。

过去几十年来，尽管我国在计算机专业教育上取得了很大的成绩，培养出了数量众多胜任工作的毕业生，计算思维的诸要素也或多或少渗透在培养方案和课程大纲中，但执行的情况还不够理想[3]。不仅不同的学校在计算思维能力培养效果上差别大，而且计算思维能力培养的水平整体看还不够高，学生对于计算思维要素掌握的程度还不够深。 对此，我们需要更主动地采取有效措施， 从思想观念、教学内容、教学方法等方面入手，进一步强化对学生开展计算思维能力的培养。

“编译原理”作为计算机专业的核心基础课程，它所涉及的大量知识都是计算思维的恰当诠释和生动案例[4]。 将计算思维培养与“编译原理”教学相结合，不仅可以从计算思维的角度重新审视和组织“编译原理”的课堂教学，而且可以加强对学生计算思维能力的培养，使学生能够更好地应用计算思维来解决实际问题。

1 教学改革思路与目标

计算的根本是抽象和自动化。用计算机解决问题，首先要对问题进行抽象和形式化描述，然后将问题求解方法算法化， 最后用编程语言实现算法。要有效解决问题，算法的复杂度还必须在可承受的范围内[5]。 这是用计算思维解决实际问题的基本思路。 如何有效地将计算思维融入、渗透到课程的实际教学中，提高学生运用计算思维进行问题的抽象和分解能力，一直以来都是计算机教育界极为关心的热点问题，也是一个巨大的挑战。

“编译原理”由于基础概念繁杂、理论性内容比重大、抽象程度高等特点，被师生们普遍反映是一门难教又难学的课程。学生在学习过程中经常感到内容抽象、算法复杂、难于理解。 另外，学生普遍认为“编译原理”不实用，导致缺乏学习热情，失去积极性和主动性。如果从计算思维的角度来重新审视“编译原理”这门课程，我们发现“编译原理”是训练学生计算思维、培养学生计算机专业素质、提高学生系统能力的良好载体。教师在教学过程中利用计算思维来重新梳理和组织“编译原理”的教学内容，可以在一定程度上克服当前“编译原理”教学中存在的问题，提高实际的“教”“学”水平。

以计算思维能力培养为导向，对“编译原理”课程教学进行改革探索，可达到如下教学目标：

（1）培养学生对问题进行抽象的能力。 在计算机科学中，抽象化就是在解决问题时隐藏实现细节以减少问题的复杂度，使人们专注重要的、本质的部分来把握事物本质、发现事物的内在规律。

（2）培养学生对问题进行形式化描述的能力。形式化方法就是发现逻辑规律、 定义逻辑规则、完善理论体系，进而对问题进行数学建模的过程。

（3）培养学生设计算法求解实际问题的能力。设计复杂度合理的算法是解决实际问题的可行途径， 算法设计是将计算思维的成果实物化的过程，也是将理论成果应用于具体技术的实践过程。

（4）培养学生采用递归与迭代解决实际问题的能力。递归与迭代是解决复杂工程问题的强有力的方法。 递归与迭代在程序编译过程中应用非常广泛，通过对实际案例的剖析，可培养学生解决复杂问题的能力。

以计算思维能力培养为导向的 “编译原理”教学改革实践的基本流程如图1 所示。

图1 “编译原理”教学改革实践基本流程Figure 1 Basic process of teaching reform practice for “Compilation Principle”

2 教学改革方案分析与内容设计

2.1 “编译原理”中的计算思维分析

计算思维中包含的计算特点是采用计算机科学的基本概念来求解问题、设计系统和理解人类行为，涵盖了计算机科学一系列的思维方法。例如，经过数据仿真、嵌入实验、等价转化、合理约简等步骤，把一个抽象复杂的问题解释成简单易懂、易解决的问题；通过分解和抽象解决复杂的任务；选择恰当的表示方式表述问题或者对问题进行建模，进而把问题简化处理；通过纠错、冗余、容错等方法预防、检测或者以最差的情况恢复系统；在空间与时间、存储容量与处理能力等方面进行平衡；进行递归转化等。以上计算思维方法都可以在“编译原理”的很多理论和相关技术中得以体现，并且很多编译成果也利用了计算思维的核心。 例如，抽象和自动化就是编译理论和方法产生的基础；编译中介绍的词法、语法分析，属性文法和优化等内容，都体现了从实际问题中抽象出共性，并且运用科学思维方法求解问题的思想。 其中，词法分析主要涉及形式化、转化、约简的方法；语法分析主要涉及形式化、递归、分解的方法； 语义分析与中间代码生成主要涉及形式化、嵌入、分解的方法；代码优化主要涉及约简、分解、仿真的方法；目标代码生成主要涉及仿真、容错的方法。 求解的成果建立在经典理论的基础上，并应用到具体的实际问题中，进一步推动了编译相关技术的进步。 因此，“编译原理”课程处处渗透计算的特征，在理论和技术上都体现了计算思维。

2.2 教学改革方案中的内容设计

通过对“编译原理”课程知识框架的梳理，可提取计算思维与课程内容之间的结合点，这些结合点可归纳为4 类，如图2 所示。

图2 计算思维能力培养与课程内容结合点Figure 2 Combination of computational thinking ability training and course content

（1）提取问题抽象化与课程内容的结合点。 编译中的词法分析、语法分析以及优化等都是首先进行抽象化的过程， 是通过发现不同分析方法的规律，然后进行数学建模，直至最后自动分析的过程。以词法分析和语法分析为切入点，给出一个实际的小型语言系统的文法，通过课堂讲解，让学生建立起抽象符号与实际语义之间的联系，反复强调两者之间的对应关系， 最终使其专注于各种语法成分，把握分析对象的本质，忽略具体语言中各种语法成分的实现细节。

（2） 提取问题形式化描述与课程内容的结合点。编译中的形式语言理论部分，关于文法、语言以及各种范式的定义， 都是基于形式化的描述方法。通过这部分内容的学习和练习，可以大大提升学生的形式化描述能力。这部分内容密切结合各种语法分析中使用到的算法， 以 LL （1） 文法为例，求FIRST、FOLLOW 集的算法是以形式化的方式来描述的，未掌握形式化语言和形式化思维的学生理解起来非常吃力，更不用谈去实际应用。 在课堂讲解的过程中，先让学生接触大量的实例，观察FIRST、FOLLOW 集的构成， 引导学生总结各种符号的来源，最终靠自己的领悟形成对算法的形式化描述。通过这一方法， 学生可以领悟形式化思维和实际问题的联系， 使形式化的思维真正被学生所接受和理解。

（3）提取算法设计及算法复杂度与课程内容的结合点。 编译中自动生成工具LEX 和 YACC 的设计，就是在形式语言与自动机理论的前提下产生的高效词法和语法自动产生器。算法及算法复杂度不仅体现在编译程序本身的工作机制上， 更体现在编译程序的生成工具的研究和设计上。

（4） 提取递归与迭代思想与课程内容的结合点。编译中的自上而下语法分析中的递归下降分析程序、语法制导翻译中的递归下降翻译器的设计都是有关递归问题的典型代表。

算法设计部分、复杂度分析部分及递归迭代部分穿插在各算法的剖析中， 包括有限自动机的转换、DFA 化简、 递归下降语法分析方法、LR 语法分析算法、寄存器分配算法、代码生成算法等。

在教学过程中，除了系统讲授编译过程中涉及的主要理论、技术和算法，可留出一部分时间穿插介绍涉及计算思维能力培养的相关内容，即跳出课程知识框架，从更高层次上审视编译器的设计与实现，引导学生从中归纳总结通用问题求解的基本范式，以及在面对复杂工程问题时解决问题的基本思路与可行途径。

3 教学改革实施与效果评价

以杭州电子科技大学计算机学院计算机科学与技术专业“编译原理”教学为例。 课程组在2021学年第一学期期末考核时设计了一套计算思维能力试卷，并在泛雅网络教学平台上发布，要求选课学生完成。 试卷含3 种题型：判断题、单选题、简答题，各题型题量与内容见表1。

表1 计算思维能力考试题型与内容Table 1 Computational Thinking Ability Test Question Type and Content

考试共472 人参加，平均得分为76.9 分，成绩分布如图3 所示。这次考试的成绩作为期末成绩中课程思政得分的主要依据（占总成绩的5%），学生们比较重视，促使他们在学习过程中除了对编译课程具体知识点的掌握之外，也会同时思考编译器设计与实现中涉及到的理论、技术迁移到其他应用领域的可能，在提高专业素养和计算思维能力的同时也提高了他们通用问题的求解能力。

图3 计算思维能力考试成绩分布Figure 3 Distribution of Computational Thinking Ability Test Scores

在2021 学年第一学期的“编译原理”教学中，课程组两位主讲教师（A 教师、B 教师）采用新的教改方案，教学过程中注重强化对学生的计算思维能力的培养。另一位主讲教师（C 教师）采用原有的教学模式。为客观反映教改效果，比较了A 教师（4 个教学班）、B 教师（4 个教学班）与 C 教师（4 个教学班）之间客观题的测试得分数据。 具体数据见表2。 从表 2 可以看出，A 和 B 两位教师班级的得分率相对于C 教师来说有较大的优势。 课程组将在今后的教学过程中，根据反馈不断优化教改方案，如引入具体的工程案例，并从计算思维角度来剖析这些案例，将计算思维能力的培养落到实处。

表2 计算思维能力考试得分率比较Table 2 Scoring rate comparison of Computational Thinking Ability Test

4 结语

本文提出以计算思维能力培养为导向的“编译原理”课程教学模式，围绕编译程序逻辑结构的各个部分，将计算思维的主要培养目标融合贯穿其中，有利于提高学生解决复杂工程问题的能力。 该教学模式将计算思维能力分解为问题抽象能力、问题形式化描述能力、算法设计能力、递归与迭代能力，并落实到“编译原理”课程教学中，有利于提高学生的计算机专业素养和达成计算机专业对学生的能力培养目标。 提出的计算思维能力培养可推动学生从具备“实例计算（解决单一具体问题）”能力跨越到具备“类计算（完成一类问题系统求解）”能力，有利于培养学生的可持续发展能力。 教改方案实施后的评价结果初步展示了该教学模式的优越性。