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

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

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

　　中图分类号：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 

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