修晓杰，唐红军

(杭州电子科技大学信息工程学院，浙江杭州310018)

0 引言

程序评测是指根据一定的标准对程序进行程序结构和语义上的分析，并反馈分析结果。Marker［1］是一个C语言的测评软件，它通过分析程序的结构和输出的结果来判定程序的准确性。其不足之处是不能发现程序在语义级别上的错误和与模板程序的差异，没能给出更多在程序理解上有利用价值的信息，此类工具还有 Generic Automated Marking Environment［2］，online assessment［3］，Online Judge［4］等等，但这些工具都不能满足程序自动评测的要求。程序切片是一种用于分解程序的程序分析技术，是通过对源程序中每个兴趣点分别进行技术切片来达到对程序的分析和理解［5］。本文在“C语言程序设计”课程基础上，提出一种基于切片的C语言程序评测方法，并系统实现。系统能够实时评测学生的程序，并给出具体的错误信息和错误位置，同时给出相应分数。

1 程序评测过程

对于学生提交的C语言程序，将从4部分进行评测:编译是否通过、运行结果是否正确、是否抄袭和与模板程序的相似度。其中编译是否通过在构造程序抽象语法树(AST，Abstract Syntax Tree)时完成;运行结果是否正确通过对测试数据运行结果自动测试实现;是否抄袭，采用对评测结果相同或分数相近的学生程序进行匹配性对比完成，通过对两棵生成AST树进行结点匹配，根据相似度给出判断;学生程序与模板程序相似度部分是C语言程序评测中的关键点，本文将着重阐述该部分。程序评测过程如图1所示:

图1 程序评测过程

2 程序标准化处理

学生程序作为一种主观类型的作业，存在着主观性的特点，同一作业程序有着不同的表达方式和语句顺序，不同的学生程序有着不同的编程风格和习惯，这就加深了对程序在语义级上进行自动评测的难度。因此，需要对学生程序进行标准化处理，使得学生程序与模板程序具有对等性比较的可能。学生程序的标准化处理过程主要包括3个主要部分:抽象语法树的生成、结构分析和等价转换。学生程序标准化处理过程如图2所示:

图2 程序标准化处理过程

程序的标准化处理是依据于程序存在保留语义的变化，即SPV(Semantics Preserving Variation)。它是指尽管学生程序在表达上与模板程序有着不同的地方，但如果它的语义与模板程序的语义是一致的，那么该学生程序就存在着保留语义的变化。对于这类学生程序经过标准化处理，消除学生程序与模板程序在表达上的差别，达到相匹配的目的。在程序解析时，应用现有的程序解析器，生成程序抽象语法树;在程序的结构分析过程中，对程序进行保留语义转换和规范处理;然后利用文献［6］的标准化转换规则进行等价转换，消除SPV(文献7中所列);最后，对转换后的程序重新生成抽象语法树。此部分，本文将不再详细赘述。

3 程序切片

程序切片大致可分为静态、有条件和动态切片，各种切片都有各自的优势与劣势。计算程序切片的方法主要有两种:根据数据流方程计算和根据依赖图关系计算［5］。本文将实现静态切片算法，通过构造程序依赖图，利用计算图的可达性算法计算程序切片。程序的函数内算法如图3所示。其中二元组〈n，V〉表示感兴趣的变量以及感兴趣的变量定义位置和使用位置。其中n表示程序P中的兴趣点(如某条语句);V代表程序P中在n点定义或使用的变量(或变量集合)。在上面的切片算法的基础上，再结合编译程序得到的抽象语法树，就可以对程序进行划分了，划分的依据是按变量进行，包括全局和局部，并严格按照语法树从上到下的顺序进行划分。程序划分算法如图4所示。

图3 程序函数内切片算法

图4 程序划分算法

4 程序比较与评测

对学生程序的评测，采用以下基本要求进行评测［7］:(1)程序是否编译通过，有没有警告;(2)程序的运行结果是否正确;(3)程序是否存在抄袭的可能;(4)程序与模板程序进行比较相似度，根据程序相似度进行评测。

其中，第4点是比较评测的关键。在相似度评测中，主要分两个层次进行比较，一是程序结构上的比较，另一个是语句层次上的比较。学生程序和模板程序在结构上都要先经过标准化处理，一般的语法结构的不同都会通过标准化处理，如循环如果使用了for语句，标准化处理后都将使用while语句。但如果使用这些结构的次数不同，标准化处理后还将有差异，对于这种情况，如果学生程序运行结果正确，则考虑将学生程序加入模板库。

语句层次上的比较，在这一层次上将通过对程序划分为等价成分后，在语义级上进行比较评测。在学生程序作业这类小模块的程序比较中，经过程序的规范化要求，以及各种标准化处理，学生程序与模板程序的近似度可以达到很高，甚至在语句上是完全一致的，很可能的不同之处是对变量的命名，但是只要在结构上大致相同的，变量类型相同，以及在整个程序结构上的位置大致相同(这可通过抽象语法树进行识别)，在这些前提条件下，通过对变量切片代码段进行命名替换后也就可以进行比较了。语句层次的比较算法如图5所示:

图5 程序的比较评测算法

5 实例分析

本文中的程序评测算法已经程序实现，并使用大量具体实例进行验证，证明算法是有效的。实例程序:编程求一维数组中最大值(数组有10个元素)，数组元素的值由用户输入。通过程序自动评测功能进行分析和测评，并定位学生程序存在的错误和给出相应提示信息。具体如图6所示。

图6 实验程序比较评测实例

从图6可见，模板程序与学生程序存在3个差异，其中区别2在标准化过程中得到处理。其它区别将在语句层次上的比较评测中检测出来，并给出差异描述和评测结果，如表1所示。

表1 程序差异描述

对于实验程序评测从三个方面综合评价:(1)编译情况:通过编译;(2)程序测试用例测试结果:不通过;(3)模板程序与学生程序相似度:82%。根据这三方面，给出学生程序的相应分数。给程序打分第一考虑测试用例测试是否通过，然后再看程序的相似度。这样，采用人工设置分数比例的方法，如测试用例通过可得满分60%的分数，若不通过则得40%的分数，而不管测试用例是否通过，程序结构比较近似度占满分的40%，由此，在上述的实验中，设定满分为100，则程序评测的结果为:总分 =100×40%+100×40% ×82% =73。对于目前使用的评测系统主要有两种，一种针对ACM竞赛的评测系统，该程序例子运行结果错误，得分0;另一种针对运行结果和格式两方面进行评测(如北京航空航天大学的自动评测系统)，得分由上述两种因素的百分比决定。

6 结束语

本文提出的基于程序切片技术的程序评测方法已经应用在“C语言程序设计”课程的学生程序评测中，实践证明该方法能有效评测出学生程序与模板程序的相似度，并给出出错的具体语句，为高校C语言教学的老师提供了有效帮助。本文提出的程序评测方法不仅适用于过C语言程序评测，同样适用于其它面向过程语言程序。

［1］ Ghosh M，Verma B，Nguyen A.An Automatic Assessment Marking and Plagiarism Detection［C］.Australia:First International Conference on Information Technology and Applications，2002:489-494.

［2］ Blumenstein，Michael，Green，et al.GAME:A Generic Automated Marking Environment for Programming Assessment［C］.Austrlia:International Conference on Information Technology，2004:212-216.

［3］ Fischer，Gregor，Von Gudenberg，et al.Improving the quality of programming education by online assessment［C］.Germany:ACM International Conference Proceeding Series，2006:208-211.

［4］ Brenda Cheang，Anay Kurnia，Andrew Limb，et al.On Automated Grading of Programming Assignments in an Academic Institution［J］.Computers＆ Education，2003，41(2):121-131.

［5］ Chen Duanzhi.Program slicing［C］.Guangzhou:2010 International Forum on Information Technology and Applications，2010:15-18.

［6］ 王欢.面向对象程序等价转换技术的研究与应用［D］.广州:广东工业大学，2008.

［7］ 陈楚明.基于切片的程序评测研究［D］.广州:广东工业大学，2009.