基于先修课程实践项目的编译原理教学方案

李志敏，黄兰英，叶从欢，熊曾刚

（湖北工程学院 计算机与信息科学学院，湖北 孝感 432100）

摘 要：借鉴CDIO工程教育理念，提出基于先修课程实践项目的编译原理教学方案。通过将编译程序各阶段分解成子任务，对应先修课程相关知识点，设计编译原理先修课程的实践项目。阐述如何引导学生进行自主研究性学习，以改善编译原理课程的教学效果。

教育期刊网 http://www.jyqkw.com
关键词 ：编译原理；先修课程；实践项目；CDIO工程教育理念

基金项目：湖北省高等学校教学改革研究项目“基于CDIO工程教育理念的编译原理课程教学改革”（2012367）。

第一作者简介：李志敏，男，副教授，研究方向为计算机软件与理论，2218538304@qq.com。

l 编译原理课程简介

编译程序是重要的计算机系统软件，它的设计和实现综合应用了高级语言程序设计、计算机体系结构、形式语言与自动机理论、算法设计与分析、软件工程等知识。编译原理课程建立在高级语言或汇编语言的基础上，运用编译理论和技术来解决高级语言在机器上运行的实际问题[1]。

编译原理的先修课程主要是高级语言程序设计、汇编语言程序设计、离散数学、数据结构与算法、操作系统等。编译原理主要介绍编译器实现过程中的词法分析、语法分析、语义分析、中间代码生成、目标代码生成、代码优化等各阶段的核心算法，涉及形式语言与自动机等抽象概念，需要学生熟练掌握高级语言、数据结构、操作系统、软件工程、汇编语言等课程的知识。精通高级语言及底层寄存器分配、内存管理等方面的内容。编译原理课程在理论、技术、方法上为学生提供了系统而有效的训练，有利于提高学生的计算机应用和系统开发能力。编译理论中的形式化理论与技术不仅应用于编译器设计，而且广泛应用于人工智能、自然语言处理、网络信息处理、多媒体技术及数据库等领域。该课程的学习对于今后很多领域，如计算机软件技术、计算机系统结构、人工智能系统的机器学习、并行处理技术等领域的理论研究具有深远的意义。

2 基于先修课程教学方案的提出

由于编译原理课程概念繁多、理论抽象、逻辑严密，广泛而且深入地应用其他先修课程的知识。现行教材以编译器各个阶段的设计和实现为主，理论和实践的起点都比较高，割裂了先修课程与编译原理的内在联系。学生普遍感觉不知从哪里找到学习的突破口，再加上从事编译器设计工作的学生数量极少，绝大多数学生学习动力不足。

为提高编译原理教学质量，借鉴CDIO工程教育模式的理念，提出基于先修课程实践项目的编译原理教学方案，如图1所示。

CDIO模式倡导学生开展基于问题的学习、基于项目的学习、基于案例的学习等多种自主研究性学习方法，加强学生实践创新能力训练[2-6]。

由于编译原理课程是一门理论性和实践性都很强的课程，通过实践项目驱动，可以引导学生带着问题，进行自主研究性学习，从而真正掌握编译技术及其在各个领域中的应用。

如图1所示，教师将编译程序各阶段分解成子任务，找出他们相关联的先修课程实践项目。在实验前，教师提供编译程序框架平台和先修课程实践项目，让学生借鉴和分阶段设计编译程序，在编译程序框架平台上，整合集成前端和后端程序，构造出完整的编译程序平台。

3 先修课程实践项目的设计

在教学中，以PL/0编译程序为教学模型。PL/0是Pascal语言的子集，具备一般高级语言的典型特点。PL/0编译程序包含了高级语言程序实现的基本组织、技术和步骤。为降低编译程序设计的难度，针对编译每个阶段，结合C语言程序设计和数据结构课程，可以设计若干相关先修课程实践项目[7]。

3.1 PL/0编译程序的词法分析

（1）识别保留字和标识符。设有一张保留字表。对每个字母开头的字符串（包含若干字母和数字），都要查找保留字表。若查找到则为保留字，将对应的类别放在sym中，否则标记为用户定义的标识符。标识符将ident放在sym中，标识符本身的值放在id中。

（2）拼数和拼复合词。当所取单词是数字时，将数的类别number放在sym中，数值本身的值存放在num中。对两个字符组成的复合词算符，识别后将类别送sym中。

（3）识别单字符单词。识别单一运算符和界限符。

（4）滤空格。空格是程序不可缺少的界限符，但在语法分析中无用，必须滤掉[8]。

依据以上词法分析的任务，教学过程中设计如下先修课程实验项目：

实验1：字符类型统计。编写程序，在终端用键盘输入字符串，用符号#表示输入结束。统计输入的字符串中空格符、制表符、换行符的个数，并显示统计结果。

实验2：判断程序中begin和end是否匹配，并统计匹配次数。程序存放在txt文件中或用键盘直接输入。

实验3（农夫过河问题）：本实验项目用于自动机状态转换和单词识别的实现。

实验4：设计PL/0源程序扫描器，去除空格和注释及其他无关字符后得到单词的集合。

实验5：用自动机识别无符号数；要求能够识别整数，带小数的无符号数以及带指数形式的无符号数。

实验6：设计识别教育期刊网 http://www.jyqkw.com
关键词 、标识符等类型单词的程序。

3.2 PL/0编译程序的语法分析和语义分析

PL/0语法分析同时也根据程序的语义生成相应的代码，并提供了出错处理的机制。本阶段一般采用自上而下的递归下降子程序法。

语法分析从读入第一个单词进行分析作为初始符号的非终结符“程序”，也就是从非终结符“程序”对应状态转换图的初始状态出发开始分析。假设当前单词是a，分析器处于状态p，若读入单词a后转换到状态q，则分析器进入状态q。再读取下一个单词继续分析。如果当前单词是非终结符A，分析器处于状态p，若读入A后转换到状态q，则分析器调用A对应的处理子程序，分析完后，分析器进入状态q。如果当前单词是终结符，则判断当前读入的单词是否与状态转换图的终结符匹配。若匹配，则执行相应的语义分析程序（即翻译程序）。并且继续读取下一个单词进行分析。如果遇到分支点时，将对分支点上的多个符号逐个分析，若都不匹配时出错[9]。

依据以上语法和语义分析的任务，教学过程中设计如下实验项目，主要体现栈结构和递归的应用。

实验7（数字翻译器）：输入一个正整数N，输出它的英文表达。例如：输入1，输出one。输入12，输出twelve。输入135，输出one hundred thirty five。

实验8（魔王语言翻译）：有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是按照两种形式的规则由人的语言逐步抽象上去的：

（1）α→ β1β2……βm

（2）（θδ1δ2……δn)→θδnθδn-1……θδ1θ

在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。

（1）B → tAdA

（2）A → sae

该实验项目通过一组语法规则，将含有非终结符的单词序列变为句子。

实验9（表达式求值）：从键盘输入中缀表达式，含+，-，*，/以及圆括号“（”和“）”。先将其转换为后缀表达式，然后再利用后缀表达式求值。

3.3 PL/0编译程序的错误处理

发现语法错误时，对于容易校正的错误，例如缺失逗号或分号的错误，则指出出错位置，并补上逗号或分号。对于难以校正的错误，跳过一些单词符号，直到读入一个能使编译程序恢复正常语法分析工作的单词为止。

发现语义错误时，只给出错误信息和出错位置，编译工作继续进行。

对运行错误，例如溢出越界等，只能在运行时给出错误信息，PL/0编译程序无法给出源程序的错误位置。

依据以上PL/0编译程序错误处理任务，教学过程中设计如下先修课程实验项目：

实验10（表达式求值）：从文本文件input.txt中读取若干中缀表达式，中缀表达式之间用“；”隔开。转换为后缀表达式存放在临时temp.txt中，然后从temp.txt读取后缀表达式，完成计算，将计算结果存在input.txt中。要求能进行错误处理。

3.4 PL/0编译程序中符号表的设计与实现

PL/0编译程序中符号表采用单表组织，所有嵌套的作用域共用一个全局符号表。为处理方便，符号表设计为栈结构。对符号表的维护主要有3种操作：登录、查询、删除。

依据以上PL/0编译程序符号表的设计与实现思路，教学过程中设计如下先修课程实验项目，熟悉查找算法和栈的基本操作和应用：

实验11（二叉树的基本操作）：将词法分析得到的记录以二叉树的结构存储并给出查找、删除算法。

实验12（Hash表的基本操作）：将词法分析得到的记录进行散列存储。

实验13（停车场管理）：设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等待，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。

3.5 PL/0程序运行时存储组织与管理

在编译阶段进行的存储空间分配工作称为静态存储分配。在运行阶段进行的存储空间分配工作称为动态存储分配。PL/0采用栈式存储分配方法。依据以上存储组织与管理的任务，教学过程中设计如下实验项目，主要体现栈结构的应用：

实验14（N阶Hanoi塔问题）：要求学生以N=3为例，显示执行过程中递归工作栈状态的变化情况。执行过程包括从主函数进入递归函数到退出递归函数返回主函数。

3.6 PL/0编译程序完整设计

完整的编译程序设计较为复杂，为了让学生熟悉编译程序各个阶段，先要求学生改编实验10（表达式求值），作为编译器设计的预备实验。

实验15（简单的表达式翻译器）：给出C语言编写的翻译器，它将用分号隔开的若干个中缀表达式序列翻译成后缀表达式序列。表达式由数字、标识符、操作符（+，-，*，/，div，mod）构成。要求翻译器包括词法分析、语法和语义分析、符号表、出错处理等编译程序模块[10]。

4 结 语

通过对2012—2014年计算机科学与技术专业3届学生观察分析，绝大多数学生对该课程的重要性有比较清楚的认识，对课程的重视程度普遍提高，能保持浓厚的学习兴趣。80%学生能完成词法分析程序、语法分析程序、中间代码生成等基础实验模块。半数学生可以独立完成编译器设计工作流程。其余学生在教师的指导下，也能顺利完成。

实践表明，通过先修课程的实验项目，将难懂的编译原理与学生已有的基础知识与技能相结合，起到降低编译程序设计门槛的效果。同时进一步巩固先修课程的理论和方法，使学生找到学习编译原理的切入点和兴趣点，提高了实际动手能力，增强了编译原理课程教学实效。

教育期刊网 http://www.jyqkw.com
参考文献：

[1] 王改芳, 龚君芳, 李圣文, 等. 编译原理课程实践教学改革探索[J]. 实验技术与管理, 2009(12): 130-131.

[2] 张彦春, 王孟钧. 基于课程的教学质量保证体系构建与运行[J]. 中国大学教学, 2012(8): 73-75.

[3] 何炎祥, 伍春香. 现代教学理论指导下的“编译原理”教学综合改革[J]. 计算机教育, 2010(1): 46-49.

[4] 罗高涌, 张瑾. 基于CDIO 模式校企合作办学工程应用型人才培养模式研究[J]. 高教探索, 2011(5): 71-75．

[5] 查建中. 工程教育改革战略“CDIO”与产学合作和国际化[J]. 中国大学教学, 2008(5): 16-19.

[6] 陈艳, 魏星, 李志梅. CDIO工学教学模式在数据库应用技术教学中的应用[J]. 教育探索, 2013(3): 136-137 .

[7] 蒋宗礼, 姜守旭. 形式语言与自动机理论[M]. 2版. 北京: 清华大学出版社, 2013: 269-276.

[8] 张素琴, 吕映芝. 编译原理 [M]. 北京: 清华大学出版社, 2005: 13-27.

[9] 陈应明, 马俊杰, 张怀庆. 编译原理[M]. 北京: 冶金工业出版社, 2004: 13-43.

[10] 严蔚敏, 吴伟民, 米宁. 数据结构题集(C语言版)[M]. 北京: 清华大学出版社, 2006: 72-165.

（编辑：赵 廓）