“编译原理”综合应用型教学案例的设计

张妮 严迪新 陆卫忠

摘 要：针对“编译原理”课程教学中缺乏实践的问题，设计了一个实践强化的综合应用型教学案例。该案例以编译原理课程为中心，综合运用了多门计算机专业课程的相关知识，并具有相似性检测的功能，能对学生提交的程序设计类作业进行相似性检测，以发现学生作业的原创性。学生通过对给出知识点的组合和扩展，完成案例的设计和程序实现。弥补了课程教学中存在的不足，并具有一定的实用性。

关键词：编译原理；教学案例；相似性检测

中图分类号：G64文献标识码：A 文章编号：1673-9795（2014）04（A）-0000-00

Design of an Integrated Application-oriented Teaching Instance

in “Compiler Principle”

ZHANG Ni，YAN Di-xin，LU Wei-zhong

（School of Electronic and Information Engineering， USTS， Suzhou 215011）

Abstract： Facing to the practice problems of the lack of the "compiler principle" teaching，the paper designed an integrated application-oriented teaching instance . The instance make compiler principle course as center， and integrate using of the relations knowledge of other professional courses，and has a similar detection function which can detect similarity of the students project， and verify the originality of students project. The design and implementation of the instance are completed by different combinations and expansion of knowledge. The instance make up for the deficiencies in teaching process， and also has a certain practicality.

Key words： Compiling Principles； teaching instance； similarity detection

“卓越工程师教育培养计划”是教育部于2010年6月启动的为期10年（2010—2020年）的重大改革项目。该计划旨在培养一大批创新能力强、适应社会经济发展需要的高质量工程技术人才[1-3]。编译原理课程作为计算机专业卓越工程师培养计划中一门核心专业基础课程，在新形势下要求其教学过程必须以学生为中心，巩固理论知识，加强实践教学，注重学生创新意识的培养。

然而，由于编译原理课程教学内容不仅包含形式语言、有限自动机、正规文法、正规表达式和LL（1）分析法等理论知识，而且编译的每个阶段都包含大量的复杂算法，学生在学习过程中感到抽象和难以理解[4]。通过对国内各高等院校教学现状的调查，目前编译原理课程教学过程中存在编译教学难点较多[5]，实践环节缺少实际应用背景和以及未与其他课程进行有效的融合[6]等几个方面问题。为了达到“卓越计划”培养目标，必須对现有的教学方法和手段进行改革，探讨如何将编译原理课程的理论知识应用于实践或实际项目和如何加强编译原理课程与其他计算机课程之间的联系的问题，更好地将理论知识点贯穿融合到实践教学或实际项目中。

本文在“卓越计划项目”的资助下，将案例教学法[7，12，13]引入编译原理课程的教学过程中。通过选取恰当的理论知识点，结合数据结构、面向对象程序设计等计算机专业的相关课程，设计了一个能吸引学生兴趣，实践强化的综合应用型教学案例。

1 案例设计思想及意义

在计算机专业程序设计类课程的教学过程中，学生提交作业的形式是源程序的电子文档，这为有些同学拷贝和抄袭提供了便利，不仅影响学生对课程的掌握度，还影响了老师判分的公正性。程序相似性检测技术能够对学生提交的程序设计作业进行检测，验证学生作业的原创性，帮助教师在大量的学生作业中找出相似性较高，即存在抄袭嫌疑的作业对象[11]，也有利于发现学生的创新性成果。通常程序相似性检测过程由程序源代码预处理，源代码转化，相似性比较，结果检测四个阶段构成。

在设计案例时，我们用编译原理课程中词法分析和语法分析算法思想来完成代码相似性检测过程中的源代码预处理和源代码转化两个阶段，使用数据结构课程中学过的字符串比较算法（如最长公共子序列算法等）作为相似性检测算法，可以选择案例开发环境有Eclipse，VC6.0和VS2010等。

此案例以编译原理课程为中心，结合了数据结构、面向对象程序设计等计算机专业的相关课程，实现了具有程序相似性检测功能的系统。大多数学生在理解和掌握案例中给出知识点的基础上，通过对其进行不同组合来完成案例的设计和程序实现，达到教学的基本要求，基础好的学生在掌握已给出案例的基础上选择更难的知识点来设计和实现案例，学到更多知识。使学生通过一个综合案例的设计和实现，巩固了多门课程的相关知识点，弥补了课程教学中缺乏实践的问题，加强计算机相关课程之间的横向联系，培养学生的学以致用的实践能力和创新能力。

2 案例相关的知识点

案例教学法的核心是案例的设计，案例设计应该与教学内容、教学进度相适宜，能恰当地融入相关的知识点。本案例的相关知识点有：与编译原理课程相关的基于程序设计语言的词法分析程序实现方法（手工方式）和基于LEX的词法分析程序实现方法（自动方式）；与数据结构课程相关的一些字符串比较算法，如最长公共子序列（LCS）算法，Halstead算法和RKR-GST算法等；以及有一定的面向对象编程基础，能使用JAVA，C++，C#等其中一种语言编写程序。学生在熟悉和掌握这些知识点的基础上进行案例的设计和实现。

2.1 词法分析程序的实现方法

词法分析程序的工作原理是，从左至右扫描源程序的字符串，按照词法规则（正则文法规则）识别出一个个正确的单词，并转换成该单词相应的二元式（种别码、属性值），以数组、链表或文本文件等形式保存，交给后续模块使用。通常构造词法分析程序有两种方法。第一种是手工方式，即根据识别语言单词的状态转换图，使用某种高级程序设计语言，如C、C++、JAVA等，直接编写词法分析程序。第二种是自动方式，即利用LEX工具自动生成词法分析程序。

2.1.1 基于程序设计语言的词法分析程序

设计的主要思想就是构造出目标语言单词符号的有穷自动机（DFA）。手工方式实现词法分析的程序的步骤分为四个阶段，第一，定义目标语言的可用符号表和构词规则，即目标语言单词的状态转换图；第二，依次读入源程序符号，对源程序进行单词切分和识别，直到源程序结束；第三，对正确的单词，按照它的种别以〈记号类别，属性值〉的形式保存在符号表（ 数组或链表）中；最后对不正确的单词，做出错误处理。

2.1.2 基于 LEX的词法分析程序

LEX是一个词法分析器[8]的自动生成系统，它的输入是一个文本文件，文件的扩展名习惯用.l表示，称之为LEX源文件，该文件包含了用户定义的正规表达式以及每个正规表达式相对应的处理动作。LEX的工作原理是将源程序中的正规式转换成相应的DFA，而相应的动作则插入到输出的词法分析器中适当的地方，控制流由该DFA的解释器掌握。对不同的源程序，这个解释器是相同的。LEX最常见的版本是Flex，可以免费得到。基于 LEX的词法分析程序设计思路：编写LEX源文件，按要求抽象出正规表达式，同时滤掉输入串中所有的空格、Tab、回车及注释，最终形成.l文件。最后使用Flex编译器生成词法分析程序。

2.2 字符串匹配算法

除了数據结构课程已经介绍的字符串匹配算法（KMP算法），本案例还可以使用其他的字符串匹配算法，如最长公共子序列（LCS）算法，Halstead算法和RKR-GST算法等。依据词法分析程序的输出结果（单词符号串），利用字符串匹配算法来度量两个标记串的相似度。本案例提供这些算法的实现思想和源代码，供学生参考和进一步改进。

2.2.1 最长公共子序列（LCS）算法

LCS（Longest Common Subsequence）算法[9]即求两个字符串的最长公共子序列算法。算法的主要思想是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长公共子序列的位置。其算法由求最长公共子序列的长度Length（l，j）和最长公共子序列LCS（A，B）两步构成。

2.2.2 Halstead算法

Halstead算法[10]以源代码中出现的操作符和操作数为计数对象，以它们的出现次数作为计数目标来测算程序容量和工作量。其基本原理是：统计每个程序段中用到的操作符和操作数，最终生成一个特征向量。操作符包括所使用编程语言的关键字、运算符和标准库名称。操作数是指程序段中所有由用户自己定义的符号串。系统为每个待检测相似性的源代码生成一个特征向量之后，再计算每两个向量之间的欧几里德距离，若两个程序段的特征向量之间的距离很小，就可以认为这两段程序很相似。

2.2.3 RKR-GST算法

RKR-GST （Running Karp Rabin Greedy String Tiling）是一种贪婪式字符串匹配算法[14]，循环求取两个标记串中未被匹配部分的最大公共子串，并根据相应公式求出两个字符串的相似度。对源程序代码进行相似性检测的过程通常可分为两个阶段：第一阶段，对源程序进行词法分析或语法分析，剔除与程序结构无关的表面元素，产生标准化输出。第二阶段，采用字符串匹配技术两两比较各程序的标准化输出，进行相似度度量，求出其相似度。

3 案例设计与实现

本案例要求学生选择一种熟悉的开发平台（VC 6.0，Eclipse，VS 2010等），依照第二节中给出的基本知识点（学生需提前查阅相关资料，做好预习），通过对知识点的不同组合和扩展，如基于程序设计语言的词法分析程序+ LCS算法，基于 LEX的词法分析程序+RKR-GST算法和基于程序设计语言的词法分析程序+RKR-GST算法等，设计具有程序相似性检测功能的系统，然后编程实现综合教学案例系统。

在此，将以采用基于 LEX的词法分析程序（自动方式）来完成代码预处理及转换，使用RKR-GST算法进行代码相似性检测为例，给出设计和实现程序相似性检测系统的过程。在学生设计和实现本案例前，教师先演示这个已事先设计好的案例供学生参考，让学生对案例实现过程有一个直观的认识。本次设计具体分为代码预处理及转换、将源代码转化为标记串、RKR-GST算法实现及结果分析四个阶段。

3.1代码预处理及转换阶段

在理解有穷自动机知识点的基础上，结合第二节中给出的设计思想，设计了LEX源文件——LexScanning.l，其中自定义了一些词法规则、getToken（）以及printToken（）等函数，实现了词法分析功能，同时滤掉了用户源程序中所有的空格、Tab、回车及注释。如图1所示。之后使用Flex编译器将LexScanning.l文件编译生成名为CiFa.exe词法分析程序。

图1 LexScanning.l文件

3.2将源代码转化为标记串

在主程序中运行时，通过创建一个线程来调用CiFa.exe文件，进行词法分析，将用户源代码转化为标记串。

3.2.1参数设置

STARTUPINFO si；

memset（&si，0，sizeof（STARTUPINFO））；

si.cb=sizeof（STARTUPINFO）；

si.dwFlags=STARTF_USESHOWWINDOW；

si.wShowWindow = SW_HIDE；

PROCESS_INFORMATION pi；

3.2.2 创建线程

CString cmd = _T（"CiFa.exe "）+m_file_path_1；

if（CreateProcess（_T（"CiFa.exe"），（LPTSTR）（LPCTSTR）cmd，NULL，NULL，FALSE，0，NULL，NULL，&si，π））

{ WaitForSingleObject（pi.hProcess，INFINITE）；

CFile file（_T（"C：＼＼temp.txt"），CFile：：modeRead）；

……

dwFileLen=file.GetLength（）；

pBuf=new CHAR[dwFileLen+1]；

pBuf[dwFileLen]=0；

…… }

3.3 RKR-GST算法

两个程序段之间的相似性即为它们对应的标记串之间的相似性。可将每个标记串看成由若干个子串组成，那么两个标记串中相同的子串就是它们的公共子串，其相似性可用所有公共子串在整个串中所占的百分比表示。公式如下[14]：

其中： | A |、|B |为token串A、B的长度。match（i，j，length ） ： 在 A 中起始位置为i，在B中起始位置为j， 长度为n 的子串。Matches为公共子串集合。

案例中设计了函数void Greedy_String_Tiling （tile_type *tiles， char *A， char *B， unsigned MML） 循环求取两个标记串中未被匹配部分的最大公共子串，并根据公式求出两个token串A、B的相似度。其中参数 *tiles存放求出的所有最长公共子串，*A和*B分别来存放字符串A和字符串B，MML给出公共子串应达到的最小长度。

4 系统的测试及结果分析

准备了三个C语言源程序作为测试用例，其中测试用例一（test1.c）和测试用例二（test2.c）有少数变量名不一样和源程序的组织结构稍有差别之外，其他的内容几乎一样。测试用例三（test3.c）与测试用例一和测试用例二在内容和结构上则完全不一样。

4.1 test1.c与test2.c的比较

运行程序，点击“浏览”按钮选择要比较的两个源程序文件test1.c和test2.c，点击“词法分析”按钮输出test1.c和test2.c经词法分析后的结果，如图2所示。

图2 词法分析结果

接下来，设置相似阈值为5之后，点击“比较”按钮，则进行两个源程序的相似性比较，比较的结果如图3所示。两个文件的相似度为91.089112%，结果符合我们的预想。

图3 相似性检测结果

4.2 test1.c与test3.c的比较图4给出了test1.c和test3.c的相似性检测结果，过程与上面相类似。相似度为13.265306%，符合我们的预期。

图4 相似性检测结果

5 结语

本文给出了笔者在编译原理教学过程中使用的一个案例。该案例以编译原理课程为中心，结合数据結构、面向对象程序设计等计算机核心专业课程，将几门课程的知识点联系在一起，突出“编译原理”课程的实用性。学生在实现综合案例之前，教师通过对已实现案例的演示，让学生有对实验过程及要求有了直观的了解，促使学生设计实现出更好的具有程序的相似性检测功能系统，巩固编译原理和数据结构等课程相关的知识点，激发学习兴趣，提高学生的学习质量和效率。今后的教学研究中，我们将对该案例进行扩展，使之能分析如.net等高级语言编写的源程序代码，增加一些新的知识点，进而可供高年级学生在课程设计中使用。

参考文献

[1] 林健.面向卓越工程师培养的研究性学习[J]. 高等工程教育研究，2011，（6）：5-15.

[2] 徐世军，范伟，黄贤英.面向卓越工程师培养的专业课程教学实践. 计算机教育.2013（13） 22-25.

[3] 李锋，夏小玲.计算机软件工程专业卓越计划实践教学. 计算机教育.2013（13） 18-21.

[4] 李冬梅，施海虎."编译原理"课程的教学研究与探索. 计算机教育.2008（08）：10-12.

[5] 张昱，陈意云，郑启龙. 编译原理课程的教学方法和教材建设[J]. 中国大学教学，2005，（7）：61-62.

[6] 计卫星，陈英等.简析计算机专业知识在编译课程教学中的渗透与融合.计算机教育. 2010（03）：23-25.

[7] 秦艳琳，吴晓平.“信息安全数学基础” 案例教学[J].计算机教育，2010（01）：141-144.

[8] 陈火旺，刘春林，谭庆平等. 程序设计语言编译原理[M].北京：国防工业出版社，2000.

[9] 于海英.字符串相似度度量中LCS和GST算法比较[J].电子科技，2011（3）：101-103.

[10] Halstead， Howard M. Elements of Software Science[Z].Elsevier，1977.

[11] 张莉，周祖林.代码相似性检测在程序设计教学中的应用.计算机教育.2009（13）：116-118.

[12] 张月琴，孙冰.案例教学法在“大学信息技术”课程中的应用研究[J].中国电力教育，2012，（25）：63-64.

[13] 范岩.案例教学法在计算机教学中的应用[J].科技信息，2008，（8）：35.

[14] Lutz Prechelt ， Guido Malpohl， and Michael Phlippsen. JPlag：Finding plagiarisms among a set of programs. Technical Report 2000-1， Fakult?t für Informatik， Universit?t Karlsruhe ， Germany， March 2000.