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

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

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

中圖分類號：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

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

1 正則表達式算法

1.1 正則表達式概念及可行性

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

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

1.2 程序度量算法模型

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

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

2）通過掃描被測程序的程序體抽取出被測程序的主體邏輯序列

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

模型如圖2所示：

2 算法實現(xiàn)

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

在使用正則表達式進行度量匹配之前，首先需要對被測程序進行語法與句法的分析，在保證被測程序語法與句法合理的前提下對程序主體進行抽取邏輯序列與標準邏輯序列進行對比，即：語義分析。

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

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

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

2.2 算法描述

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

2.3 算法分析

1）被測程序邏輯序列的生成

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

2）被測程序與標準程序邏輯序列的對比

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

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

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

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

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

3 結(jié)束語

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

參考文獻：

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

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

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

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

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

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

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

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

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

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

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

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

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

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