论文部分内容阅读
摘 要：针对传统的编程题自动评分方法无法准确衡量学生对知识点掌握程度的问题，提出了一种基于最小子程序匹配的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的转变过程可以很明显地看出更小粒度的子程序是根据有序树中右子树种切分出来的，同时右子树的子程序的第一个结点与其父亲结点是嵌套关系，而左子树是依据程序运行子程序的顺序关系连接得出的。
本例中没有出现多选择分支，鉴于并列代码的特殊性，在此规定，当检测到子程序是分支语句时，构造树型图时该结点下的子程序从左至右，最左边为左子树与上面描述一致，除了该左子树其他均为右子树。即一个父结点有多个子结点时，最左的子結点与父结点为顺序关系，其他结点与父结点为嵌套关系，且这部分的结点之间是并列关系。由于该父结点下的子结点不满足有序树的定义，在有大于两个子结点的情况下，也就是存在并列关系的节点时，子结点之间是无序的。也就是说本文中用于构造子程序有序树不是真正意义上的有序树。
三、最小子程序匹配评分算法
关键词：自动评分；子程序；树；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的转变过程可以很明显地看出更小粒度的子程序是根据有序树中右子树种切分出来的，同时右子树的子程序的第一个结点与其父亲结点是嵌套关系，而左子树是依据程序运行子程序的顺序关系连接得出的。
本例中没有出现多选择分支，鉴于并列代码的特殊性，在此规定，当检测到子程序是分支语句时，构造树型图时该结点下的子程序从左至右，最左边为左子树与上面描述一致，除了该左子树其他均为右子树。即一个父结点有多个子结点时，最左的子結点与父结点为顺序关系，其他结点与父结点为嵌套关系，且这部分的结点之间是并列关系。由于该父结点下的子结点不满足有序树的定义，在有大于两个子结点的情况下，也就是存在并列关系的节点时，子结点之间是无序的。也就是说本文中用于构造子程序有序树不是真正意义上的有序树。
三、最小子程序匹配评分算法