基于正則表達(dá)式度量算法的智能評(píng)分設(shè)計(jì)

許文俊+朱盼雨+張學(xué)生+石虎

摘要：針對(duì)程序的智能評(píng)分問(wèn)題進(jìn)行研究，采用編譯技術(shù)中詞法與語(yǔ)法分析技術(shù)分析被測(cè)程序的語(yǔ)法與和語(yǔ)義和使用正則表達(dá)式度量算法抽取程序的邏輯序列，程序經(jīng)過(guò)語(yǔ)法及詞法分析和數(shù)據(jù)驗(yàn)證后，在與程序樣例的邏輯序列循環(huán)掃描對(duì)比、匹配的過(guò)程中，記錄得分點(diǎn)主要信息，從而實(shí)現(xiàn)對(duì)程序的智能評(píng)分，評(píng)分結(jié)果更加準(zhǔn)確、合理。

關(guān)鍵詞：正則表達(dá)式度量；過(guò)濾；語(yǔ)法分析；語(yǔ)義分析

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

隨著計(jì)算機(jī)技術(shù)的高速發(fā)展，使用程序設(shè)計(jì)語(yǔ)言設(shè)計(jì)出高效、可靠、實(shí)用的軟件則是計(jì)算機(jī)發(fā)展的必經(jīng)之路，所以，對(duì)于程序設(shè)計(jì)語(yǔ)言的學(xué)習(xí)與教學(xué)則顯得尤為重要。在傳統(tǒng)的程序設(shè)計(jì)語(yǔ)言教學(xué)中，對(duì)于編程題的考核十分復(fù)雜繁瑣，不能真實(shí)地反應(yīng)編程人員的真實(shí)編程能力，單純依靠傳統(tǒng)的紙質(zhì)試卷，不僅效率低，而且浪費(fèi)了大量的時(shí)間。由于程序代碼的復(fù)雜性，人工閱卷的評(píng)分的效率非常低，。因此，開(kāi)發(fā)出用于教學(xué)所使用的智能評(píng)分系統(tǒng)能有效簡(jiǎn)化傳統(tǒng)的評(píng)分過(guò)程，消除人工評(píng)分的主觀性給公正評(píng)分帶來(lái)的片面的影響。隨著越來(lái)越多智能的算法的發(fā)展，智能系統(tǒng)得到蓬勃的發(fā)展。尤其是在智能評(píng)分領(lǐng)域，建立在數(shù)據(jù)庫(kù)基礎(chǔ)上的代碼相似度判斷算法缺乏普遍的適應(yīng)性，難以適應(yīng)復(fù)雜的java程序，尤其是對(duì)于嵌套層次較深的程序，分析起來(lái)十分復(fù)雜，算法難以適用。對(duì)于實(shí)際程序設(shè)計(jì)語(yǔ)言教學(xué)中復(fù)雜的程序，基于正則式度量的算法能夠滿足系統(tǒng)對(duì)效率的高要求以及高效性。該算法能夠從答題者的角度去分析程序思路，對(duì)題目的評(píng)分不僅僅局限于結(jié)果的正確與否，及時(shí)結(jié)果錯(cuò)誤，該算法仍然可以根據(jù)程序中的得分點(diǎn)給出相應(yīng)的分?jǐn)?shù)，真實(shí)模擬了從程序執(zhí)行角度去評(píng)審程序的情況。本文分析了基于正則表達(dá)式度量算法的實(shí)現(xiàn)方式以及流程，歸納出該算法的特性，彌補(bǔ)了傳統(tǒng)評(píng)分算法的局限性以及不公正性，在傳統(tǒng)的基礎(chǔ)上改善了算法的時(shí)間復(fù)雜度、成功度。在算法中，提出對(duì)未通過(guò)前期詞法與語(yǔ)法分析以及為通過(guò)數(shù)據(jù)驗(yàn)證的程序采用正則表達(dá)式對(duì)程序的得分點(diǎn)進(jìn)行判斷，根據(jù)程序的邏輯思維角度去分析程序，使得評(píng)分結(jié)果更加準(zhǔn)確、合理。

1 正則表達(dá)式算法

1.1 正則表達(dá)式概念及可行性

正則表達(dá)式就是用某種模式去匹配一類字符串的一個(gè)公式，是一些事先定義好的特定字符組成的字符串，并使用這組規(guī)定好的字符串去與想要操作的字符串進(jìn)行匹配、過(guò)濾。對(duì)于給定的字符串以及正則表達(dá)式，可以通過(guò)匹配去判斷字符串是否符合過(guò)濾邏輯。程序語(yǔ)言是由多條語(yǔ)句構(gòu)成的，那么一條語(yǔ)句就可以看作是一個(gè)字符串，所以，完整的程序可以看作是由多個(gè)字符串組成的字符串集合。因?yàn)檎齽t表達(dá)式能夠靈活、高效地對(duì)所要操作的字符串進(jìn)行匹配，具有全面匹配的特性，所以字符串常被用來(lái)對(duì)不同復(fù)雜程度的字符串集合進(jìn)行描述，用于檢測(cè)測(cè)試數(shù)據(jù)的正確性、有效性、提取子串等。故而正則表達(dá)式非常適合用于程序語(yǔ)言的描述。在使用正則表達(dá)式描述完整的程序時(shí)，定義程序語(yǔ)言中固定的語(yǔ)法單元十分重要。在定義中可以實(shí)現(xiàn)定義好某些字符的特殊含義。例如：D定義為數(shù)字的集合。

在定義常量時(shí)，例如小數(shù)：6.61829，可以表示為：Lit=D+＼.D+。“+”在正則表達(dá)式中表示對(duì)前一個(gè)字符的一次或多次匹配，而利用轉(zhuǎn)義字符“＼”可以通過(guò)“＼.”對(duì)“.”進(jìn)行匹配。所以，通過(guò)使用正則表達(dá)式強(qiáng)大的匹配功能，可以實(shí)現(xiàn)對(duì)復(fù)雜程序語(yǔ)句的完整描述，而且能準(zhǔn)確表達(dá)其邏輯意義。例如：對(duì)于if語(yǔ)句與while循環(huán)用正則表達(dá)式描述，如圖1所示：

1.2 程序度量算法模型

由于在系統(tǒng)中預(yù)存了程序題的邏輯序列，所以在評(píng)測(cè)過(guò)程中，通過(guò)以下步驟建立評(píng)測(cè)模型。

1）根據(jù)被測(cè)程序的要求，在系統(tǒng)中預(yù)存被測(cè)程序的邏輯序列

2）通過(guò)掃描被測(cè)程序的程序體抽取出被測(cè)程序的主體邏輯序列

3）將前兩步的邏輯序列進(jìn)行對(duì)比、匹配，在對(duì)比過(guò)程中，記錄關(guān)鍵字信息。

模型如圖2所示：

2 算法實(shí)現(xiàn)

2.1 被測(cè)程序的預(yù)處理

在使用正則表達(dá)式進(jìn)行度量匹配之前，首先需要對(duì)被測(cè)程序進(jìn)行語(yǔ)法與句法的分析，在保證被測(cè)程序語(yǔ)法與句法合理的前提下對(duì)程序主體進(jìn)行抽取邏輯序列與標(biāo)準(zhǔn)邏輯序列進(jìn)行對(duì)比，即：語(yǔ)義分析。

運(yùn)用正則表達(dá)式度量算法的前提是被測(cè)程序能夠正常運(yùn)行，不存在語(yǔ)法與句法的錯(cuò)誤，所以要通過(guò)編譯器提供的編譯功能對(duì)被測(cè)源程序進(jìn)行語(yǔ)法與句法的分析，主要運(yùn)用編譯原理方面的知識(shí)進(jìn)行分析。分析的過(guò)程中，要對(duì)源程序的錯(cuò)誤進(jìn)行統(tǒng)計(jì)并記錄，這更有利于為后續(xù)的評(píng)分提供評(píng)判依據(jù)以及分析教學(xué)策略。

在順利通過(guò)編譯的前提下，確立程序的邏輯性是否正確由數(shù)據(jù)驗(yàn)證來(lái)實(shí)現(xiàn)，即：采用輸入輸出數(shù)據(jù)去驗(yàn)證而不是簡(jiǎn)單的答案對(duì)比，可以有效避免學(xué)生投機(jī)取巧直接輸出答案。

被測(cè)程序經(jīng)過(guò)語(yǔ)法及詞法分析和數(shù)據(jù)驗(yàn)證后，使用本算法對(duì)被測(cè)程序進(jìn)行邏輯序列的抽取及循環(huán)掃描比對(duì)，從而智能的根據(jù)程序主體對(duì)得分點(diǎn)進(jìn)行評(píng)測(cè)，結(jié)合前預(yù)處理操作，顯著提高了本算法設(shè)計(jì)的智能化程度。

2.2 算法描述

用流程圖描述基于正則表達(dá)式度量的算法如圖3所示：

2.3 算法分析

1）被測(cè)程序邏輯序列的生成

掃描被測(cè)程序，根據(jù)程序中的關(guān)鍵字把被測(cè)程序的邏輯序列抽取出來(lái)，如果在序列中已經(jīng)存在“循環(huán)”關(guān)鍵字，再次循環(huán)則修改為“循環(huán)1”，即是在前一個(gè)關(guān)鍵字的數(shù)字上加1，沒(méi)有數(shù)字則默認(rèn)為0。

2）被測(cè)程序與標(biāo)準(zhǔn)程序邏輯序列的對(duì)比

通過(guò)系統(tǒng)預(yù)存的邏輯序列與分析被測(cè)程序得到的邏輯序列進(jìn)行對(duì)比。在對(duì)比的過(guò)程中，如果系統(tǒng)中預(yù)存邏輯序列與被測(cè)程序的邏輯序列中的某項(xiàng)相同，則記錄其關(guān)鍵字信息（為后續(xù)判斷該段代碼是否符合題目要求得分點(diǎn)提供條件），如果不相同，則不做處理，知道預(yù)存的邏輯序列與被測(cè)程序的邏輯序列對(duì)比完畢。處理過(guò)程的偽代碼如下：

根據(jù)關(guān)鍵字匹配與語(yǔ)法、句法分析可以得到程序體的邏輯序列為：

定義數(shù)組->定義變量->循環(huán)1->判斷->交換。

根據(jù)以上得到的邏輯序列，對(duì)比結(jié)果所得到的關(guān)鍵字是{定義數(shù)組，循環(huán)，判斷，交換}。然后根據(jù)關(guān)鍵字信息獲取正則表達(dá)式集合中對(duì)應(yīng)的得分點(diǎn)信息形成正則式集合，利用這些正則式集合掃描被測(cè)程序，掃描過(guò)程中如果出現(xiàn)滿足正則式集合中的字符串，則判斷該得分點(diǎn)正確，并記錄相應(yīng)的分?jǐn)?shù)。對(duì)于上述程序，可在定義數(shù)組、判斷、交換三個(gè)方面時(shí)設(shè)立相應(yīng)的得分點(diǎn)，并根據(jù)掃描過(guò)程是否滿足正則表達(dá)式條件字符串得到相應(yīng)的分?jǐn)?shù)。

算法過(guò)程中的程序掃描通過(guò)java語(yǔ)言中的正則表達(dá)式包“java.util.regex”中提供的模式類（Pattern）以及匹配器類（Matcher）實(shí)現(xiàn)，掃描過(guò)程中如果出現(xiàn)非法掃描模式，掃描程序會(huì)中斷并報(bào)告異常情況。所以，通過(guò)使用java中提供的類可以使正則表達(dá)式的掃描變得簡(jiǎn)單、高效。

3 結(jié)束語(yǔ)

本文采用正則表達(dá)式度量的算法來(lái)實(shí)現(xiàn)智能的對(duì)程序進(jìn)行評(píng)分，改善了傳統(tǒng)評(píng)分系統(tǒng)中的局限性?；谡齽t表達(dá)式的程序度量算法及評(píng)分模型的建立為該評(píng)分系統(tǒng)的實(shí)際運(yùn)用提供了實(shí)現(xiàn)的基礎(chǔ)。本算法采用正則表達(dá)式作為評(píng)判基礎(chǔ)，使得評(píng)分過(guò)程可以根據(jù)關(guān)鍵點(diǎn)評(píng)分，而不是簡(jiǎn)單的根據(jù)程序主體和結(jié)果判分，使得運(yùn)用本算法的系統(tǒng)的自動(dòng)評(píng)分更接近閱卷效果，從而可以提高評(píng)測(cè)的準(zhǔn)確性和客觀性。

參考文獻(xiàn)：

[1] 趙曉靜. 編程題自動(dòng)閱卷系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 軟件工程師， 2014（9）.

[2] 布輝， 劉冉. 面向?qū)嵺`能力考核的程序題自動(dòng)評(píng)分方法研究[J]. 電腦知識(shí)與技術(shù)， 2012（19）.

[3] 王亞寧， 何英， 俞銳剛， 等. 程序設(shè)計(jì)考試系統(tǒng)自動(dòng)評(píng)分策略的研究與實(shí)踐[J]. 昆明學(xué)院學(xué)報(bào)， 2011（06）.

[4] 韓家寶. 圖數(shù)據(jù)搜索引擎Trinity中正則表達(dá)式匹配子系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D]. 哈爾濱： 哈爾濱工業(yè)大學(xué)， 2015.

[5] 蘇小紅， 王宇穎， 王甜甜， 等. 面向綜合實(shí)踐能力考核的C語(yǔ)言編程考試自動(dòng)評(píng)分系統(tǒng)[J]. 實(shí)驗(yàn)技術(shù)與管理， 2010（10）.

[6] 王力洪. 基于關(guān)鍵字和序列匹配的自動(dòng)評(píng)分算法的研究[J]. 福建電腦， 2015（12）.

[7] 陳偉民. 基于CUDA的正則表達(dá)式匹配系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D]. 湖北： 華中科技大學(xué)， 2011.

[8] 姜英杰. 支持正則表達(dá)式的文本匹配優(yōu)化算法[D]. 沈陽(yáng)： 東北大學(xué)， 2012.

[9] 劉鵬.面向存儲(chǔ)的正則表達(dá)式匹配算法研究[D]. 河南： 解放軍信息工程大學(xué)， 2010.

[10] 程璐.基于遺傳算法的正則表達(dá)式規(guī)則分組優(yōu)化[D]. 深圳： 深圳大學(xué)， 2015.

[11] 張大方， 張潔坤， 黃昆. 一種基于智能有限自動(dòng)機(jī)的正則表達(dá)式匹配算法[J]. 電子學(xué)報(bào)， 2012（8）.

[12] 邵翔宇. 正則表達(dá)式匹配存儲(chǔ)優(yōu)化技術(shù)研究[D]. 河南： 解放軍信息工程大學(xué)， 2015.

[13] 殷珍珍. 基于正則表達(dá)式的多模式匹配算法研究[D]. 杭州： 杭州電子科技大學(xué)， 2012.

[14] 邱濤. 基于反向因子的正則表達(dá)式匹配及其優(yōu)化方法[D]. 沈陽(yáng)： 東北大學(xué)， 2013.