程序设计题自动评分方法研究

冯秀梅 张永胜

摘 要：目前在计算机考试自动评分系统中，最能反映考生水平的程序设计类问题缺少有效的解决方法。本文通过分析常见自动评分过程，将评分方法进行分类，剖析了阅卷中的关键编译技术对评分准确率的影响，针对动态测试与静态分析相结合的自动评分方法和基于程序理解的综合型自动评分方法的算法策略及评分步骤，给出在算法和编译运行方面提高评分效果的解决途径。

关键词：自动评分；程序设计；人工阅卷

中图分类号：TP312 文献标识码：A

1 引言（Introduction）

目前，程序设计语言的上机测试和自动评分已经成为教育教学领域的研究热点。但现有编程语言测试系统的自动评分大都是客观型测试，但对能体现考生水平和能力的程序题缺少有效的解决方案[1]。程序语言设计课程的考试题大多由教师批改。若用计算机实现自动阅卷和评分，不仅能把改卷老师从大批量的阅卷工作中解放，确保客观公正，还能提供有效快速的反馈，促进学生学习和程序设计能力。该方法对于实现上机在线考试，特别计算机远程辅助教学方面有重要的推广意义，这种理论和实践都很强的自动评分方法，和软件工程试验、人工智能、程序理解等其他技术联系密切，尚有许多专业难题要攻克，具有很高的研究价值和发展前景。

2 自动评分的过程（The process of automatic scoring）

程序设计题的自动评分对系统来说是在特定范围内的，系统不需理解所有自然语言，只要理解标准答案即可。运用特别的方法把标准答案转化成能理解的模式，同时把考生的程序也根据某种特定的规则转化成计算机能理解的模式，最后与标准答案进行匹配给予评分结果。在此之中的关键性问题是，要把规则转化为让计算机理解的一个知识库。

本文对目前常用的程序设计题自动评分方法进行研究，依据其评分思路，将其分为程序分析比较法和综合型方法两类，分别进行具体论述。

3 程序分析比较法（Analysis and comparison

methods）

程序分析比较法即源程序分析比较法，系统对考生源程序分析与比较，通过一定的方法实现对源程序语句语义、字符串等与模板程序进行相似度匹配得出评分结果。

3.1 基于语义相似度的评分

该方法将程序的某些标准化规则，如算术运算和布尔运算进行创新和完善，在文献[2]提出的评分方法模型基础上采用数组分析和函数调用等一些改进方法，根据语义相似度来匹配学生程序与模板。该方法的基本思想如下：

（1）制定模板程序，将模板作为判断程序是否正确的标准。

（2）答案中一个语义与考生编写的程序的语义对等，则判断该程序语义是正确的。

（3）程序用SDG表示，若两个SDG等价，则有等价的语义。

（4）语义等价转换即为采用系统依赖图标准化语义等价程序，无论程序用何种方法，只要程序结果不变，就判定该转换是等价的[2]。

该方法对语法和词法分析上较严格，尽管该模型已经能应用于实际，但是有需要完善及改进的地方，比如对结构体、指针和共同体等的处理就不是很理想。

3.2 基于字符串相似度算法的自动评分

程序中字符串的相似度就是指一个字符串与另一字符串的相似程度。这类算法有很多，文献[3]中采用编辑距离算法，编辑距离即从原字符串转换到目标字符串所满足的插入，删除和替换的数量的最小值。在系统中，运用黑盒测试法、字符串相似度与关键点匹配这三个层次进行评价，这三个层次的评分过程的流程如图1所示。

图1 字符串相似度方法的评分过程

Fig.1 The scoring process of string similarity method

该系统采用由小变大的评价粒度。字符串相似度从总体上给出评分结果，但关键的匹配方法是看所给程序题中得分点给分，与字符串相似度比较显得粒度较大。程序设计题经过三个层次的评测，全面地考察了学生对问题的理解与掌握程度，比仅使用单一的黑盒测试法更加客观、公平，比仅使用关键点匹配评价更加精细、全面。该系统已经在该校的计算中心进行多次实际应用，基本能够满足C语言程序设计要求，但需要对标准答案与关键点匹配方法等方面进一步的完善。

3.3 用正则表达式来描述得分点的自动评分

正则表达式实际上亦为匹配模式，它由一系列具有特定含义的字符串构成，用来进行匹配和替换。该方法用分割程序语义的处理方法，也就是在评分过程中不是用程序与模板进行完全匹配，而是把模板程序拆分成若干个得分点，并用正则表达式描述，然后在考生程序中搜索与得分关键点类似的代码段，进行直接匹配评分[4]。通常来说，一道程序设计题在评分时会有三种情况：一是能进行编译运行且结果正确；二是能进行编译运行但结果不正确；三是不能进行编译运行，同时得不到结果。

对于以上三种进行分析应用的方法和手段不全部相同，因此需要分别对这三种情况进行处理。图2给出用正则表达式来描述得分点的自动评分。

图2 用正则表达式评分

Fig.2 The scoring method of using regular expression

首先，若为第一种，只需分析程序的代码是否可信即可；若为第二种，通过基于得分关键点的评分模型进行评分；若为第三种，从语法或词法等判断代码是否出错，因为语法和词法也是程序设计题的一个评分基点，故先对学生程序的词法和语法错误进行统计，然后结合其他得分基点算出学生总成绩。

该方法与人工阅卷评测结果非常接近，可是正则表达式的模式在构造时太严格，学生程序中的某些程序的词法或语法错误而导致检测失败；若正则表达式的模式过于宽松，则会产生歧义。故正则表达式中应忽略一些常见语法错误，如把一些对语法的检测字串改为可选项，如分号等，而把这些交给语法分析去完成。故该方法不仅考虑全面而且要精确，故该模型构造的优劣也同样对系统评分的结果产生或大或小的影响。

4 综合型方法（Comprehensive methods）

所谓综合型方法是指该评分方法不只是用一种只针对程序结构语义，语句、字符串等方面的分析来对学生编写的程序与模板程序进行直接的匹配评分，而是采用这种比如动态分析与静态测试、程序分析与树核相似、基于程序理解的综合型评分方法。

4.1 基于程序理解的综合型自动评分

程序理解即为先对源程序分析，并对源程序概括、推理来获取内容的方法过程。该方法把人为阅卷的某些思维过程与程序理解的策略紧密结合，并将模板程序与考生程序比较，然后对考生程序评分[5]。其主要评分方法过程如下：

（1）把程序代码用系统依赖图（SDG）来表示。

（2）标准化处理转换成SDG，来去除程序多样化[6]。

（3）匹配考生源程序和模板程序得出评分——从程序的规模、结构及深度等几方面入手。

该方法是运用程序的层次构造分析，并对程序进行的逆向分析获得程序的结构内容，然后把这些信息用图形化形式表示出来，尽管程序的内部结构及逻辑关系便于理解，但重点在于对程序结构的理解方面，不能做到用正确的逻辑关系来检查程序。

苏小红等[5]在程序理解基础上使用面向综合能力的程序设计题自动评分方法，评分策略： 一是根据程序语义评分； 二是通过得分关键语句查找评分；三是使用动态测试评分。该方法的评分流程如图3所示。

图3 基于程序理解的自动评分方法

Fig.3 Automatic scoring method based on program

understanding

以上三个方法因都有优缺点，将三个层次互相配合，互相补充，能更全面地计算出句子之间的相似度，对考生代码正确、迅速地评分。但应用于该系统时，在题目的录入存在一些较为不人性化问题，可适当增加部分删除、修改的功能，使系统更加智能化；而且对参考答案模板的要求较高，提取模板技术有待完善与改进。

4.2 动态测试与静态分析相结合的自动评分

动态测试的评分方法是把源程序编译为可执行文件，用预先定义的测试数据集中的数据作为输入来测试，将结果与期望结果比较，参考对比结果给出具体分数。评分过程如图4所示。源程序静态分析评分是把程序与模板的源代码分析对比，评定学生成绩。评分过程如图5所示。

图4 动态测试的自动评分

Fig.4 Automatic scoring of the dynamic test

图5 静态分析的自动评分

Fig.5 Automatic scoring of static analysis

两种方法各有优缺点，若两者结合，可使评分准确性很大有提升，后者能完成有用模板提取方法，使模板能提高基于静态分析的评分准确性。通过基于动态测试的评分方法的研究，在语义相似度的基础上采用动态测试与静态分析相结合的自动评分方法。该方法删掉冗余的限制，改变评分策略，增加模板提取部分，更适用普通考生在线考试。如图6所示的方法用于实际的上机考试，经考试数据分析，该方法不仅能提高模型评分的准确性，还能降低原有模型对模板库的依赖程度，这为提升评分准确性提供有效方法。由于编程题自动评分的课题研究存在很大难度，涉及诸多知识，还有许多技术亟待解决，该方法不可能完全解决所有问题，故在模板提取方法等方面还需进一步改进。

图6 动态测试与静态分析相结合的自动评分

Fig.6 Automatic scoring combination of dynamic test

and static analysis

4.3 程序分析与树核相似算法相结合的自动评分

程序分析与树核相似算法相结合的自动评分方法，实质上亦是一种动态测试与静态分析结合过程。但不同的是，采用抽象语法树（Abstract Syntax Tree 简称AST）这种中间表示描述考生程序语法结构信息，然后用树核的相似度算法计算程序的结构相似度[7]。即对源程序结构深度分析，把句子表示成树形结构（通过抽象语法树来得到）。使用语法树的优点使树形结构便于匹配。用树核算法计算两个程序相似度，如下举一个简单例子来说明。

程序一

void fun（ ）

{

int...

for...

}

程序二

void fun（ ）

{

int...

if...

}

它们的树形结构如图7所示。语法树的5棵子树只有1个子树是相同的，故两程序的结构相似度为1。使用树形结构来表示程序题的嵌套结构是最直观的方法，更能体现结构信息。

图7 语法树的子树

Fig.7 The subtree of syntax tree

该方法在语法错误识别和知识点识别方面虽精确，评分结果也能反映学生的真实水平，虽只注重考查学生程序的内部语法结构。但该方法更人性化，只要考生写出一部分功能语句，系统会给相对合理的分数，基本不会出现全部零分的情况，系统采用以下公式来计算评分的准确率GP：

其中，Tscore表示人工评分，Stscore表示给出的最后分数，Fullscore表示总分。

该方法在实际应用中接近人工阅卷，但有些功能不够完善，如对复杂的程序表达式的处理不完整；同时对模板要求较高，若不提供丰富的模板，会降低评分结果准确率。

5 结论（Conclusion）

本文对程序设计题自动评分方法进行了分类，分析了自动阅卷基本原理、算法步骤和关键技术。程序分析比较法的自动评分虽然准确率相对较高，但在模板提取的技术上有待改进；基于程序理解的综合型评分方法在评分思路上更符合人们的思维习惯，但在程序题的录入编辑技术上有待改进；程序设计题的自动评分是对理论和实践要求较高的问题，要使评分结果更接近人工阅卷，还需在各个方面加强研究。只有将程序设计题自动评分技术理论与实践相结合，并不断发展与改进，才能更好地应用于各类大型计算机考试的自动评分阅卷工作中。

参考文献（References）

[1] 赵晓静.编程题自动阅卷系统的设计与实现[J].软件工程师，

2014，17（9）：46-47.

[2] 王宁.编程题自动评分系统中结构体的研究与实现[D].哈尔

滨工业大学，2006.

[3] 杜利峰，牛永洁.字符串相似度在自动评分系统中的应用[J].

电子设计工程，2011，19（7）：42-44.

[4] 佘石泉.编程题自动阅卷技术的研究与实现[D].中南大学，

2007.

[5] 苏小红，等.面向综合实践能力考核的C语言编程考试自动评

分系统[J].实验技术与管理，2010，27（10）：173-177.

[6] 李必信，等.一种分析和理解程序的方法-程序切片[J].计算机

研究与发展，2000，37（3）：284-289.

[7] 陈媛媛.基于抽象语法树的编程题自动评分系统的研究与应

用[D].大连海事大学，2011.

作者简介：

冯秀梅（1990-），女，研究生.研究领域：软件工程.

张永胜（1962-），男，硕士，教授.研究领域：数据库技术，网

络信息安全.