基于正则表达式度量算法的智能评分设计

许文俊+朱盼雨+张学生+石虎

摘要：针对程序的智能评分问题进行研究，采用编译技术中词法与语法分析技术分析被测程序的语法与和语义和使用正则表达式度量算法抽取程序的逻辑序列，程序经过语法及词法分析和数据验证后，在与程序样例的逻辑序列循环扫描对比、匹配的过程中，记录得分点主要信息，从而实现对程序的智能评分，评分结果更加准确、合理。

关键词：正则表达式度量；过滤；语法分析；语义分析

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）35-0214-03

Design of Intelligent Scoring Based on Regular Expression Measurement

XU Wen-jun， ZHU Pan-yu， ZHANG Xue-sheng， SHI Hu

（Department of Computer Science and Technology， Hefei University， Hefei 230601，China）

Abstract： Aiming at the problem of intelligent scoring of program， the grammar and semantics of the program under test and the logic sequence of the program are extracted by using the regular expression measurement algorithm. The syntax and lexical analysis and data After verifying， the main information of scoring points is recorded and compared with the logical sequence of the program sample in the process of matching and matching， so that the intelligent score of the program can be achieved， and the result is more accurate and reasonable.

Key words： regular expression measure； filter； syntax analysis； semantic analysis

随着计算机技术的高速发展，使用程序设计语言设计出高效、可靠、实用的软件则是计算机发展的必经之路，所以，对于程序设计语言的学习与教学则显得尤为重要。在传统的程序设计语言教学中，对于编程题的考核十分复杂繁琐，不能真实地反应编程人员的真实编程能力，单纯依靠传统的纸质试卷，不仅效率低，而且浪费了大量的时间。由于程序代码的复杂性，人工阅卷的评分的效率非常低，。因此，开发出用于教学所使用的智能评分系统能有效简化传统的评分过程，消除人工评分的主观性给公正评分带来的片面的影响。随着越来越多智能的算法的发展，智能系统得到蓬勃的发展。尤其是在智能评分领域，建立在数据库基础上的代码相似度判断算法缺乏普遍的适应性，难以适应复杂的java程序，尤其是對于嵌套层次较深的程序，分析起来十分复杂，算法难以适用。对于实际程序设计语言教学中复杂的程序，基于正则式度量的算法能够满足系统对效率的高要求以及高效性。该算法能够从答题者的角度去分析程序思路，对题目的评分不仅仅局限于结果的正确与否，及时结果错误，该算法仍然可以根据程序中的得分点给出相应的分数，真实模拟了从程序执行角度去评审程序的情况。本文分析了基于正则表达式度量算法的实现方式以及流程，归纳出该算法的特性，弥补了传统评分算法的局限性以及不公正性，在传统的基础上改善了算法的时间复杂度、成功度。在算法中，提出对未通过前期词法与语法分析以及为通过数据验证的程序采用正则表达式对程序的得分点进行判断，根据程序的逻辑思维角度去分析程序，使得评分结果更加准确、合理。

1 正则表达式算法

1.1 正则表达式概念及可行性

正则表达式就是用某种模式去匹配一类字符串的一个公式，是一些事先定义好的特定字符组成的字符串，并使用这组规定好的字符串去与想要操作的字符串进行匹配、过滤。对于给定的字符串以及正则表达式，可以通过匹配去判断字符串是否符合过滤逻辑。程序语言是由多条语句构成的，那么一条语句就可以看作是一个字符串，所以，完整的程序可以看作是由多个字符串组成的字符串集合。因为正则表达式能够灵活、高效地对所要操作的字符串进行匹配，具有全面匹配的特性，所以字符串常被用来对不同复杂程度的字符串集合进行描述，用于检测测试数据的正确性、有效性、提取子串等。故而正则表达式非常适合用于程序语言的描述。在使用正则表达式描述完整的程序时，定义程序语言中固定的语法单元十分重要。在定义中可以实现定义好某些字符的特殊含义。例如：D定义为数字的集合。

在定义常量时，例如小数：6.61829，可以表示为：Lit=D+＼.D+。“+”在正则表达式中表示对前一个字符的一次或多次匹配，而利用转义字符“＼”可以通过“＼.”对“.”进行匹配。所以，通过使用正则表达式强大的匹配功能，可以实现对复杂程序语句的完整描述，而且能准确表达其逻辑意义。例如：对于if语句与while循环用正则表达式描述，如图1所示：

1.2 程序度量算法模型

由于在系统中预存了程序题的逻辑序列，所以在评测过程中，通过以下步骤建立评测模型。

1）根据被测程序的要求，在系统中预存被测程序的逻辑序列

2）通过扫描被测程序的程序体抽取出被测程序的主体逻辑序列

3）将前两步的逻辑序列进行对比、匹配，在对比过程中，记录关键字信息。

模型如图2所示：

2 算法实现

2.1 被测程序的预处理

在使用正则表达式进行度量匹配之前，首先需要对被测程序进行语法与句法的分析，在保证被测程序语法与句法合理的前提下对程序主体进行抽取逻辑序列与标准逻辑序列进行对比，即：语义分析。

运用正则表达式度量算法的前提是被测程序能够正常运行，不存在语法与句法的错误，所以要通过编译器提供的编译功能对被测源程序进行语法与句法的分析，主要运用编译原理方面的知识进行分析。分析的过程中，要对源程序的错误进行统计并记录，这更有利于为后续的评分提供评判依据以及分析教学策略。

在顺利通过编译的前提下，确立程序的逻辑性是否正确由数据验证来实现，即：采用输入输出数据去验证而不是简单的答案对比，可以有效避免学生投机取巧直接输出答案。

被测程序经过语法及词法分析和数据验证后，使用本算法对被测程序进行逻辑序列的抽取及循环扫描比对，从而智能的根据程序主体对得分点进行评测，结合前预处理操作，显著提高了本算法设计的智能化程度。

2.2 算法描述

用流程图描述基于正则表达式度量的算法如图3所示：

2.3 算法分析

1）被测程序逻辑序列的生成

扫描被测程序，根据程序中的关键字把被测程序的逻辑序列抽取出来，如果在序列中已经存在“循环”关键字，再次循环则修改为“循环1”，即是在前一个关键字的数字上加1，没有数字则默认为0。

2）被测程序与标准程序逻辑序列的对比

通过系统预存的逻辑序列与分析被测程序得到的逻辑序列进行对比。在对比的过程中，如果系统中预存逻辑序列与被测程序的逻辑序列中的某项相同，则记录其关键字信息（为后续判断该段代码是否符合题目要求得分点提供条件），如果不相同，则不做处理，知道预存的逻辑序列与被测程序的逻辑序列对比完毕。处理过程的伪代码如下：

根据关键字匹配与语法、句法分析可以得到程序体的逻辑序列为：

定义数组->定义变量->循环1->判断->交换。

根据以上得到的逻辑序列，对比结果所得到的关键字是{定义数组，循环，判断，交换}。然后根据关键字信息获取正则表达式集合中对应的得分点信息形成正则式集合，利用这些正则式集合扫描被测程序，扫描过程中如果出现满足正则式集合中的字符串，则判断该得分点正确，并记录相应的分数。对于上述程序，可在定义数组、判断、交换三个方面时设立相应的得分点，并根据扫描过程是否满足正则表达式条件字符串得到相应的分数。

算法过程中的程序扫描通过java语言中的正则表达式包“java.util.regex”中提供的模式类（Pattern）以及匹配器类（Matcher）实现，扫描过程中如果出现非法扫描模式，扫描程序会中断并报告异常情况。所以，通过使用java中提供的类可以使正则表达式的扫描变得简单、高效。

3 结束语

本文采用正则表达式度量的算法来实现智能的对程序进行评分，改善了传统评分系统中的局限性。基于正則表达式的程序度量算法及评分模型的建立为该评分系统的实际运用提供了实现的基础。本算法采用正则表达式作为评判基础，使得评分过程可以根据关键点评分，而不是简单的根据程序主体和结果判分，使得运用本算法的系统的自动评分更接近阅卷效果，从而可以提高评测的准确性和客观性。

参考文献：

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

[2] 布辉， 刘冉. 面向实践能力考核的程序题自动评分方法研究[J]. 电脑知识与技术， 2012（19）.

[3] 王亚宁， 何英， 俞锐刚， 等. 程序设计考试系统自动评分策略的研究与实践[J]. 昆明学院学报， 2011（06）.

[4] 韩家宝. 图数据搜索引擎Trinity中正则表达式匹配子系统的设计与实现[D]. 哈尔滨： 哈尔滨工业大学， 2015.

[5] 苏小红， 王宇颖， 王甜甜， 等. 面向综合实践能力考核的C语言编程考试自动评分系统[J]. 实验技术与管理， 2010（10）.

[6] 王力洪. 基于关键字和序列匹配的自动评分算法的研究[J]. 福建电脑， 2015（12）.

[7] 陈伟民. 基于CUDA的正则表达式匹配系统的设计与实现[D]. 湖北： 华中科技大学， 2011.

[8] 姜英杰. 支持正则表达式的文本匹配优化算法[D]. 沈阳： 东北大学， 2012.

[9] 刘鹏.面向存储的正则表达式匹配算法研究[D]. 河南： 解放军信息工程大学， 2010.

[10] 程璐.基于遗传算法的正则表达式规则分组优化[D]. 深圳： 深圳大学， 2015.

[11] 张大方， 张洁坤， 黄昆. 一种基于智能有限自动机的正则表达式匹配算法[J]. 电子学报， 2012（8）.

[12] 邵翔宇. 正则表达式匹配存储优化技术研究[D]. 河南： 解放军信息工程大学， 2015.

[13] 殷珍珍. 基于正则表达式的多模式匹配算法研究[D]. 杭州： 杭州电子科技大学， 2012.

[14] 邱涛. 基于反向因子的正则表达式匹配及其优化方法[D]. 沈阳： 东北大学， 2013.