基于最小子程序匹配的C语言自动评分算法研究
2017-09-16朱林琴刘新张辉李亭葳
朱林琴++刘新++张辉++李亭葳
摘 要：针对传统的编程题自动评分方法无法准确衡量学生对知识点掌握程度的问题，提出了一种基于最小子程序匹配的C语言自动评分算法。算法首先将程序做标准化处理，然后转换为树形子程序，再通过搜索检测划分更小粒度的子程序。再根据自动评分算法完成对C语言程序的自动评分。初步实验结果表明：自动评分算法与普通的人工评分误差相差不大，相较于传统的自动评分方法，其结果更能反映出学生的真实水平。
关键词：自动评分；子程序；树；C语言
中图分类号：TP311 文献标志码：A 文章编号：1673-8454（2017）17-0026-04
引言
目前国内外有许多程序设计在线测试系统[1]，这类线上测试系统对学生提交的代码一般采取的评分方式主要分为两大类：①动态测试[2-8]，即对学生程序进行编译、运行。当编译不通过、编译过后运行结果错误、运行时间超时情况出现时都判定提交程序无效，该方法快速、直接。②静态评分方法[2][9-12]，静态评分通过静态分析学生源代码与答案模板代码，用抽象语法树、系统依赖图、程序依赖图等中间表现形式，然后从中提取特征属性值或度量值来进行匹配再给出分值。
动态评分是目前较多在线测试系统中用到的评分方法，其前提是程序能运行成功，当程序运行结果不匹配，随机测试用例结果等情况都以0分处理。所以对学生的考察存在片面性。国内外学者在静态评分的研究上有很多，有文献表明通过计算控制流图结点的相似度进行编程题自动评分，[13]还有文献表明在考生程序生成语法树后进行遍历使用Levenshtein算法完成编程题自动评分。[14]静态分析能在一定程度上得到学生程序与模板程序的相似度，从而生成学生得分。
但由于学生编写的源代码存在着多样性，以及现有的技术对程序的理解度、语义分析的准确度还不太高等原因，评分准确性会受到影响。针对这些问题，本文提出了一种基于最小子程序匹配的自动评分算法，首先根据自定义试用于匹配的子程序，对源代码经过词法、语法分析，依据系统依赖图将程序转换为有序树，该树包含不同粒度的子程序，通过构造树时的关系规则将子程序图切分为多个更小粒度的子程序集合，然后对学生子程序与模板子程序采取从小到大的递归式匹配方式，最后结合模板程序中标记的权值为学生程序打分。此方法对学生是否掌握某语法知识或是结构的使用有很好的效果。
一、基本子程序的定义
子程序[15]是能被其他程序调用、在实现某种功能后能自动返回到调用程序的程序。其最后一条指令一定是返回指令，故能保证重新返回到调用它的程序中去。也可调用其他子程序，甚至可自身调用。为了适用于本文算法对子程序做了重新描述，子程序是能实现某一功能的基本语句的集合，可以嵌套、组合，没有返回值。在这里将一个语句块看作一个子程序。
为了能考察学生程序中是否实现了某些基本的功能，首先将学生程序与模板程序分解为基本的子程序，然后依靠系统依赖图的数据依赖找出子程序之间的关系，每个子程序的中间表示都是一棵具有语义信息的子树。最后对子树进行匹配。分析文中处理的C语言特性，划分组成子程序的基本单元，具体形式有：声明语句、库函数调用语句、赋值语句、选择分支语句、循环语句、返回语句、跳出语句。上述基本语句单位通过并列、嵌套、顺序三种关系组成功能复杂的子程序。
二、基于有序树的程序中间表示
答案模板程序和学生程序在经过词法分析和语法分析时，利用标准化规则在不改变语义的情况下消除语句的多样性，同时获得由多个不同粒度的子程序，且子程序之间通过数据流的依赖相互联系。实现排序的源代码如下所示：
#include
int main（）{
int i，j，temp，a[10]；
for（i=0；i<10；i++）
scanf （"%d，"，&a[i]）；
for（j=0；j<=9；j++） {
for （i=0；i<10-j；i++）
if （a[i]>a[i+1]）{
temp=a[i]；
a[i]=a[i+1]；
a[i+1]=temp；
}
}
for（i=1；i<10；i++）
printf（"%d，"，a[i] ）；
return 0；
}
（1）语句①依据标准化规则处理分为以下形式：
int I；int j；int temp；int a[0]
（2）依据数据流划分出如下子程序用有序树表示，以下根据粒度的大小进行排序，粒度越大的子程序中组合、嵌套的其他子程序越多，从粒度大到粒度小的子程序如图1、2、3所示：
由于篇幅限制仅展示3幅子程序有序树图。图1是最小子程序。从图1到图2再到图3的转变过程可以很明显地看出更小粒度的子程序是根据有序树中右子树种切分出来的，同时右子树的子程序的第一个结点与其父亲结点是嵌套关系，而左子树是依据程序运行子程序的顺序关系连接得出的。
本例中没有出现多选择分支，鉴于并列代码的特殊性，在此规定，当检测到子程序是分支语句时，构造树型图时该结点下的子程序从左至右，最左边为左子树与上面描述一致，除了该左子树其他均为右子树。即一个父结点有多个子结点时，最左的子結点与父结点为顺序关系，其他结点与父结点为嵌套关系，且这部分的结点之间是并列关系。由于该父结点下的子结点不满足有序树的定义，在有大于两个子结点的情况下，也就是存在并列关系的节点时，子结点之间是无序的。也就是说本文中用于构造子程序有序树不是真正意义上的有序树。
三、最小子程序匹配评分算法
1.子程序分块预处理
在对编程题自动评分的研究中存在的一个难点就是C语言程序设计的多样性，为了更多更精确地让学生程序匹配到答案模板，都会在之前对语句做语义等价转换，转换规则如下所示：
（1）拆分复合语句
将复合语句被拆分为等价的语句序列，有运算表达式的拆分、函数嵌套调用的拆分、声明语句的拆分等等，让语句化到最简表达形式。
（2）统一循环结构表示
在循环结构中for、while和do...while之间有差别，为消除其多样性将统一进行如下处理：将for语句转换为while语句的表达形式，提取for语句中的表达式1到循环体外，将表达式3写入循环体内。do...while循环要比其他循环多执行一次，因此将循环体提取出来作为一个块，然后将其转换为while循环。以上操作的处理可以让数据依赖和控制依赖更加明确清晰。
2.划分最小粒度子程序
模板程序与生产程序经过转换得到标准子程序后，经过下一步骤将最大粒度子程序划分为逐一递减子程序：
（1）从根结点出发向左子树进行深度遍历，断开具有右子树的结点的父连接与左子树连接，得到“最大粒度-1”的多个子程序。
（2）保存每次切分出的不同粒度的子程序，并重复步骤1的切分方式，直到切分出的子树种结点没有右子树为止。
根据文中给出的排序源码可以得到子程序集合PArray[n]= {pList1，pList2，...，pListn}，PArray是一个一维数组，按顺序调用pListn，pListn是一个集合，存储最大粒度子程序及该粒度下包含的层级递减的细小粒度。以上面源码为例存储结构如图4所示：
3.子程序匹配
子程序之间匹配从最小粒度出发，匹配子程序的数据变量数据流依赖类型以及组成子程序的基本单元类型，以匹配图1为例，源程序中有三个变量作交换，变量temp是流依赖，作用两个赋值语句；变量a[i]是反依赖，作用两个赋值语句；变量a[i+1]是反依赖，作用两个赋值语句。当学生代码子程序中能匹配以上信息就算匹配成功。匹配后的子程序将不会进入下一个更大粒度的子程序匹配。以匹配图2为例，在匹配图4中子程序的时候不再匹配图2中连接的图4中的子程序。
4.子程序匹配的自动评分算法
基于子程序匹配的自动评分算法的基本思想是：从最小粒度的子程序开始匹配，当学生子程序满足模板子程序中变量的数据依赖关系和控制依赖关系时则判定为正确，并记录该子程序在整个程序中所占的分数权值，之后根据匹配到的该最小粒度子程序结点搜索下一个父亲结点，由此往上递推，直到匹配完模板程序中由顺序关系组成的最大粒度子程序。结合图4所示的数据存储表描述具体算法步骤如下所示：
第一步：取带权模板子程序数组集合TPArray[n]={tpList1，tpList2...tpListn}，学生子程序数组集合SArray[m]={spList1，spList2...spListm}。y表示tpListn中子程序个数，z表示spListm子程序个数。设变量i=0、变量j=0、变量t=0、变量z=0，二维数组记录匹配带权子程序tempSimPArray[n][max]，max为tpListn中的最大长度。一维数组score存儲最大匹配到的子程序权值。
第二步：匹配spListj[i]与tpListt[z]数据的控制依赖：
（1）匹配成功i++，z++，将tpListt[z]存入tempSimPArray[t][z]，当z （2）当匹配不成功且t 第三步：累计tempSimPArray中每一行中匹配到的子程序权值，取最大权值存入score。j++，当j 第四步：累加score中权值，输出。 四、程序评分实现及实验结果分析 通常考察学生编程题的本意是检测学生是否掌握了某些知识点，所以与知识点相关的代码的得分权重要比其他代码要大一些。实验中在没有对模板程序做知识点标记的情况下子程序的权值取总分均值。通过累计匹配到的子程序所带权值，计算出学生的最终成绩。 实验系统的流程如图5所示： 为了检测自动评分的准确率，实验选取5道编程题如表1所示，并取得50名学生提交的答案及教师提供的答题模板。 为了验证前文所述的自动评分算法的性能，首先由多名教师严格按照评分标准给每个答题进行打分，将其作为专业标准评分结果；然后随机选取C语言程序设计课程的研究生助教给所有答案打分作为普通的人工评分；最后与我们的实验系统自动评分结果进行比较，以及用Levenshtein算法进行自动评分，评分详情如表2所示。根据式1计算人工评分与自动评分相对于标准评分的误差率ER。 Erate=■×100%（1） 其中SScore为专业人士的标准评分，TestScore为普通助教人员的人工评分或文中的自动评分，AllScore为总分。 在此次选取实验数据中模板数较多的题目编号1和编号3相对人工评分的误差要比其他模板少的误差率要小，说明了模板的数量在一定程度上对评分的精确度有影响。题目中涉及递归编程的题目2自动评分误差率最大，在后面的实验中需要在这个方面做改进。从整体上来看与人工的误差率是相对较小的。 五、结束语 基于最小子程序匹配的编程题自动评分算法，是将人工评分的思维过程与考点结合起来，通过粒度小到粒度大的子程序的层级匹配能检测出学生知识点的掌握程度。将程序划分为不同粒度的子程序，由于子程序保存相关语义信息，在匹配过程中能提高准确性。并且克服了程序实现多样性，语法、语义分析复杂度高等问题。其实验结果表明自动评分与专业评分比较是存在误差的，但与普通人工相比误差控制的范围是不大的，与Levenshtein算法相比总体上要优于该算法。并且程序实现思路清晰。在实验过程中会得到更多的模板程序，因此在后续的匹配中准确率也将会有所提高。
参考文献：
[1]申田静，陈俊.国内在线考试系统研究综述[J]. 中国教育技术装备，2015（14）：19-22.
[2]李郴，史国峰.编程题综合评分方法的研究[J]. 计算机与网络，2016（6）：38-39.
[3]A. Drummond， Y. Lu， S. Chaudhuri， C. Jermaine， J. Warren and S. Rixner， "Learning to Grade Student Programs in a Massive Open Online Course，" 2014 IEEE International Conference on Data Mining， Shenzhen， 2014：785-790.
[4]R. Romli， S. Sulaiman and K. Z. Zamli， "Test data generation framework for Automatic Programming Assessment，" Software Engineering Conference （MySEC）， 2014 8th Malaysian， Langkawi，2014：84-89.
[5]Alamutka K M. A Survey of Automated Assessment Approaches for Programming Assignments[J].Computer Science Education， 2005， 15（2）：83-102.
[6]Pozenel M， Furst L， Mahnicc V. Introduction of the automated assessment of homework assignments in a university-level programming course[C].International Convention on Information and Communication Technology， Electronics and Microelectronics. IEEE， 2015：761-766.
[7]Cui B， Li J， Guo T， et al. Code Comparison System based on Abstract Syntax Tree[C].IEEE International Conference on Broadband Network and Multimedia Technology. IEEE， 2010：668-673.
[8]Rubio-S， Nchez M， Kinnunen P， et al. Student perception and usage of an automated programming assessment tool[J].Computers in Human Behavior， 2014，31（2）：453-460.
[9]Cui B， Li J， Guo T， et al. Code Comparison System based on Abstract Syntax Tree[C].IEEE International Conference on Broadband Network and Multimedia Technology. IEEE，2010：668-673.
[10]劉月霞，牛志尧，吴宁.面向大规模在线开放课程的编程题多特征综合自动评分方法[J].西安交通大学学报，2016（10）：64-70.
[11]王倩，苏小红，马培军.有语法错误的编程题自动评分方法研究——用局部语法分析和采分点匹配实现[J].计算机工程与应用，2010（17）：239-242.
[12]马培军，王甜甜，苏小红.基于程序理解的编程题自动评分方法[J].计算机研究与发展，2009（7）：1136-1142.
[13]Vujo？觢evi■-Jani■i■ M， Nikoli■ M， To？觢i■ D， et al. Software verification and graph similarity for automated evaluation of students assignments[J].Information & Software Technology， 2012， 55（6）：1004-1016.
[14]刘天蓝.基于语义理解与运行分析的程序题自动评分算法研究[D].湖南师范大学，2013.
[15]徐宝文，张挺，陈振强.递归子程序的依赖性分析及其应用[J].计算机学报，2001（11）：1178-1184.
[16]姜华，韩安琪，王美佳，王峥，吴雲玲.基于改进编辑距离的字符串相似度求解算法[J].计算机工程，2014（1）：222-227.
[17]张有为，刘小春，汪永红.程序段识别算法研究[J].计算机工程，2009（5）：72-100.
[18]李静，高万林，段晶洁等.编程题自动评测系统的研究与设计[J].wisdom science and technology，2016（4）：11-16.
[19]Liu Y， Chai W， Li X， et al. Design and Implementation of Automatic Marking System for Programming Questions Based on Script Technique[C].2014 International Conference on Computer， Communications and Information Technology （CCIT 2014）. Atlantis Press， 2014.
[20]Liu X， Tao L， Zhou Y， et al. The Automatic Marking Method of SQL Script Based on Syntax Analysis and Levenshtein Distance[J].2014.
（编辑：王天鹏）endprint
