基于过程驱动的“编译原理”课程实践教学研究
2016-09-25徐艳群
徐艳群，张 斌
（南阳理工学院 计算机与信息工程学院，河南 南阳 473004）
基于过程驱动的“编译原理”课程实践教学研究
徐艳群，张斌
（南阳理工学院 计算机与信息工程学院，河南南阳473004）
“编译原理”是计算机所有专业课程中最能锻炼学生计算思维能力的一门课程，也是计算机专业较难的一门课程，很多高校忽视编译原理的实践环节，导致学生对编译的学习断章取义，学了“编译原理”还是不明白编译的实际过程。为了解决学生在“编译原理”课程学习中存在的问题，笔者提出了基于过程驱动的“编译原理”实践教学模式，教学过程贯穿小型C语言编译器的词法分析、语法分析、目标代码生成等阶段，实现了对C语言部分语法的识别，课后组织学生进行编程实践，达到了教授该课程的预期效果。
项目驱动；C编译器；词法分析；语法分析
1 “编译原理”课程实践教学现状
“编译原理”这门课程是计算机专业一门比较难的课程，课理论性很强，实践性也很强，是一门很难出成果且很难上手实现编程的课程。很少有学生毕业后会从事编译器开发这样的工作。鉴于这种情况，目前很多应用型本科院校对编译原理这门课程不够重视：有的高校只讲理论不安排实践；有的高校即使有实践环节也只是对词法分析、语法分析、中间代码生成和代码优化等分别给一个简单程序让学生理解并实践。这导致学生只是局部理解编译，不能把握编译的整个过程，实际上编译的各个过程之间存在着紧密的联系，前一个阶段的输出是后一个阶段的输入，因而必须注重编译的过程。
高级语言的迅速发展对编译器的要求越来越高，而C语言在高级语言中占据的重要地位使人们对C语言编译器的发展格外关注。笔者在编译理论教学中，通过一个简单的C语言编译器和一个类伪代码（Pseudo-Code，PCODE）指令代码的解释器的设计与实现过程，帮助学生深入理解编译的过程。教学过程中贯穿小型C语言编译器的词法分析、语法分析、目标代码生成等阶段，实现了对C语言部分语法的识别，课后组织学生开展编程实践，改变以往枯燥的理论讲课过程，从而提高了学生的编程能力以及学生对多门课程的融会贯通能力等，学生的计算思维能力也得到了提升。具体环节按照先理论后实践的过程展开。
2 基于C语言编译器的课程实践设计思想
本文的主要目的是设计和实现一个简单的C语言的编译器和一个类PCODE指令代码的解释器。C语言编译器经过词法分析、语法分析后生成PCODE指令形式，调用类PCODE指令代码的解释器解释运行。具体设计过程如下。
（1）介绍如何设计和实现一个简单的C语言编译器时，文章提出了如何设计文法能够方便地编程，将复杂的词法、语法分析层次变得更加清晰。同时对文法采取动态的方法读入，只要写出文法就可以实现对输入串的分析、识别，而不必再去修改程序部分，使得此编译器更加灵活。
（2）语法分析部分采用“LR（1）”分析法，可以识别绝大多数的文法，克服了递归下降和LL（0）分析法对文法的“严格要求”，虽然实现“LR（1）”分析器的算法相对复杂，但它带来的方便是显而易见的。
（3）为了方便调试和提高代码的易读性，此编译器并没有生成汇编语言，而是生成了类PCODE指令形式。接着文章讨论了如何设计和实现一个部分功能的类PCODE指令代码解释器，从而可以执行上一步生成的中间代码。具体实现过程如图1所示。
图1 C语言编译器的实现过程
3 具体实施
3.1词法分析
词法分析是编译的第一个阶段，它的主要任务根据单词的构词规则是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以进行语法分析。词法分析其实也是语法分析的一部分，词法分析的描述完全可以归并到语法分析的描述中去，只不过词法规则更加简单一些。如果分离了可以使得编译程序的结构更加简洁、清晰和条理化，还可增加编译程序的可移植性等优点。词法分析程序的输出一般为二元式单词种别（单词自身的值）。
程序每次读出一个单词，然后获得对应的类型作为语法分析的输入部分，其流程如图2所示。经过词法分析后所有的字符都被加入到words中，最后用#作为结束符号。
图2 词法分析流程
3.2语法分析
语法分析是编译程序的核心部分。语法分析的作用是识别有词法分析给出的单词符号序列是否是给定的文法的正确句子。可以采用自顶向下的语法分析方法，也可以采用自底向上的语法分析方法。本文以自底向上的“LR（1）”分析方法为例。文法不仅可以精准地表达出来可以识别的输入串，同时还可以极大地方便编程的实现。
3.2.1语法分析用到的文法
下面是识别表达式的文法G：
为了简化语义分析时的判断，对表达式的文法而言，又引入了两个非终结符：乘除法句柄（md_opr_express）和加减法句柄（ps_opr_express），从而前文的产生式可以被表示为：
3.2.2求文法的First集
求First集的过程中将每一个终结符的First集存入到set
3.2.3“LR（1）”分析
“LR（1）”针对不同产生式上的非终极符，分别定义其超前搜索字符（Reducelookup），减少了移入/归约冲突。
（1）“LR（1）”项目集族的构造。由于构造的过程中同一个产生式的超前搜索字符不同或者原点位置不同，就说明不在同一种状态，所以对每个产生式再构造下面数据结构，就可以达到唯一的表示一个产生式的状态。
struct node｛
int key， //产生式的索引，可以唯一地表示出一个产生式int pos， //原点的位置
int First_index， //超前搜索字符的索引
｝eNode；
（2）“LR（1）”分析表的构造。“LR（1）”分析表包括两个部分，GOTO表和ACCTION表。“LR（1）”分析表的构造一般是在构造项目集簇的第（5）步生成的。
①Xi为终结符，获取Ji在队列中的位置，Ji_pos，则更新Action［pos］［ Xi］=Ji_pos 。
②Xi为非终结符，获取Ji在队列中的位置，则更新GOTO ［pos］［Xi］=Ji_pos。
③如果识别Xi后，发现Ji中有原点已经移到产生式右部最后一个文法符号的后面的产生式Pk，说明此项目有规约动作。更新Action［Ji_pos］［Pk的每一个超前搜索字符索引］为产生式Pk索引。
总的来说，每当识别一个文法符号（无论是终结符还是非终结符）都需要更新Action表或GOTO表的一个位置。每当有产生式的原点位置越过最后一个位置的时候，就可能要更新Action表的多个位置，根据“LR（1）”分析表就可以对C语言程序进行语法分析。
3.2.4目标代码的生成
在进行过语法分析后，多数编译器根据代码的语义将源程序生成另外一种内部表示形式，例如三元式或四元式。本文所讨论的方案并没有这一步骤，而是直接生成了类PCODE指令代码，然后通过类PCODE指令解释器解释类PCODE指令代码。
（1）类PCODE指令代码语言说明。类PCODE指令代码是一种假想栈式计算机的汇编语言，它不依赖于实际的计算机，其指令非常简单。指令格式如图3所示。
图3 指令格式
其中f代表功能码，l表示层差，a的含义不同指令有所区别，主要指令解释说明如下。
LIT0a将常数值取到栈顶，a为常数值。
LODla将变量值取到栈顶，a为偏移量，l为层差。
OPR00过程调用结束后，返回调用点并退栈。
OPR01栈顶元素取反。
OPR02次栈顶与栈顶相加，退两个栈元素，结果值进栈。
OPR03次栈顶减去栈顶，退两个栈元素，结果值进栈。
OPR04次栈顶乘以栈顶，退两个栈元素，结果值进栈。
OPR05次栈顶除以栈顶，退两个栈元素，结果值进栈。
（2）生成方法简述。对改写好的文法而言，每一个需要生成指令的规约动作都可以在语法分析的过程中被捕获到，根据规约的产生式不同，生成对应指令即可。如表1所示。
表1 表达式中间代码生成对应表
3.2.5类PCODE指令代码解释程序的设计和实现
当生成目标代码的过程中如果没有发现错误，就可以由编译程序调用解释程序对生成的类PCODE指令代码进行解释执行。解释执行的过程中，其数据空间为栈式计算机存储空间，遵循后进先出的规则，对每个过程被调用时才分配数据空间，当程序退出时，释放所分配的空间。
数据栈用一个vector来模拟，每当发现int指令的时候就开辟一个栈，每当遇到opr 0 0的时候就销毁一个栈。数据栈的数据类型为vector
图4 指令解释的流程
4 结语
经过过程驱动的“编译原理”实践教学过程的引入，学生对编译器的理解有了新的认识，学生能清楚编译的整个过程及过程之间的衔接，理解编译器的设计过程包括词法分析、语法分析、目标代码生成等，了解每个过程都有相应的算法，如词法分析用到自动机的确定化及最小化算法、语法分析的First集构造算法等，在具体编程过程中如何实现。在课堂教学过程中把对应的程序引入进来，讲完理论就接着讲具体实践，课下学生实际练习。通过近3年的统计，学校计算机专业学生期末成绩从平均分60多分提高到80分左右，学生算法理解及编程能力也不同程度有了提高，很多学生加入了国际大学生程序设计竞赛（Associationfor Computing Machinery International Collegiate Programming Contest，ACM）等计算机兴趣小组。虽然实现了函数的调用，但是函数递归调用过程中不能使用全局变量，同时指针、函数返回值、结构体等都没有实现对其处理，因而还需教师带领学生朝这些方面进一步努力，实现一个对C语言程序都能进行编译的C语言编译器，让学生掌握编译器的工作原理和编译器的设计与实现过程，激发学生的学习兴趣和动手实践的能力。
［1］王晓东.计算机算法设计与分析［M］.北京：电子工业出版社，2007.
［2］张素琴.编译原理［M］.北京：清华大学出版社，2003.
［3］THOMAS H C.算法导论［M］.陈克忠，译.北京：机械工业出版社，2006.
［4］张龙祥.UML与系统分析设计［M］.2版.北京：人民邮电出版社，2007.
Research on practice teaching of compiler principles course based on process driven
Xu Yanqun， Zhang Bin
（Computer and Information Engineering Department of Nanyang Institute of Technology， Nanyang 473004， China）
The course of compiler principles is very important in training computational thinking ability in all computer courses， it is also a kind of course more diffcult to learn. Many colleges ignore compiler principles practice process， which results in compile learning is not complete to students， who still don't fgure the actual process of compile. In order to solve the problem in studying “compiling principle”，the author puts forward practice teaching mode of “compiler principle”based on process driven， the teaching process applies a small C language compiler， including lexical analysis， syntax analysis， code generation phases， and achieved the recognition of C language partial syntax， organized student to take part in the practice of compiling， achieved the course effect by programming after class.
project driven； C compiler； lexical analysis； syntax analysis
徐艳群（1978— ），女，陕西韩城，硕士，讲师；研究方向：计算机应用。
