程序設(shè)計題自動評分方法研究

馮秀梅 張永勝

摘 要：目前在計算機考試自動評分系統(tǒng)中，最能反映考生水平的程序設(shè)計類問題缺少有效的解決方法。本文通過分析常見自動評分過程，將評分方法進行分類，剖析了閱卷中的關(guān)鍵編譯技術(shù)對評分準(zhǔn)確率的影響，針對動態(tài)測試與靜態(tài)分析相結(jié)合的自動評分方法和基于程序理解的綜合型自動評分方法的算法策略及評分步驟，給出在算法和編譯運行方面提高評分效果的解決途徑。

關(guān)鍵詞：自動評分；程序設(shè)計；人工閱卷

中圖分類號：TP312 文獻標(biāo)識碼：A

1 引言（Introduction）

目前，程序設(shè)計語言的上機測試和自動評分已經(jīng)成為教育教學(xué)領(lǐng)域的研究熱點。但現(xiàn)有編程語言測試系統(tǒng)的自動評分大都是客觀型測試，但對能體現(xiàn)考生水平和能力的程序題缺少有效的解決方案[1]。程序語言設(shè)計課程的考試題大多由教師批改。若用計算機實現(xiàn)自動閱卷和評分，不僅能把改卷老師從大批量的閱卷工作中解放，確?？陀^公正，還能提供有效快速的反饋，促進學(xué)生學(xué)習(xí)和程序設(shè)計能力。該方法對于實現(xiàn)上機在線考試，特別計算機遠程輔助教學(xué)方面有重要的推廣意義，這種理論和實踐都很強的自動評分方法，和軟件工程試驗、人工智能、程序理解等其他技術(shù)聯(lián)系密切，尚有許多專業(yè)難題要攻克，具有很高的研究價值和發(fā)展前景。

2 自動評分的過程（The process of automatic scoring）

程序設(shè)計題的自動評分對系統(tǒng)來說是在特定范圍內(nèi)的，系統(tǒng)不需理解所有自然語言，只要理解標(biāo)準(zhǔn)答案即可。運用特別的方法把標(biāo)準(zhǔn)答案轉(zhuǎn)化成能理解的模式，同時把考生的程序也根據(jù)某種特定的規(guī)則轉(zhuǎn)化成計算機能理解的模式，最后與標(biāo)準(zhǔn)答案進行匹配給予評分結(jié)果。在此之中的關(guān)鍵性問題是，要把規(guī)則轉(zhuǎn)化為讓計算機理解的一個知識庫。

本文對目前常用的程序設(shè)計題自動評分方法進行研究，依據(jù)其評分思路，將其分為程序分析比較法和綜合型方法兩類，分別進行具體論述。

3 程序分析比較法（Analysis and comparison

methods）

程序分析比較法即源程序分析比較法，系統(tǒng)對考生源程序分析與比較，通過一定的方法實現(xiàn)對源程序語句語義、字符串等與模板程序進行相似度匹配得出評分結(jié)果。

3.1 基于語義相似度的評分

該方法將程序的某些標(biāo)準(zhǔn)化規(guī)則，如算術(shù)運算和布爾運算進行創(chuàng)新和完善，在文獻[2]提出的評分方法模型基礎(chǔ)上采用數(shù)組分析和函數(shù)調(diào)用等一些改進方法，根據(jù)語義相似度來匹配學(xué)生程序與模板。該方法的基本思想如下：

（1）制定模板程序，將模板作為判斷程序是否正確的標(biāo)準(zhǔn)。

（2）答案中一個語義與考生編寫的程序的語義對等，則判斷該程序語義是正確的。

（3）程序用SDG表示，若兩個SDG等價，則有等價的語義。

（4）語義等價轉(zhuǎn)換即為采用系統(tǒng)依賴圖標(biāo)準(zhǔn)化語義等價程序，無論程序用何種方法，只要程序結(jié)果不變，就判定該轉(zhuǎn)換是等價的[2]。

該方法對語法和詞法分析上較嚴(yán)格，盡管該模型已經(jīng)能應(yīng)用于實際，但是有需要完善及改進的地方，比如對結(jié)構(gòu)體、指針和共同體等的處理就不是很理想。

3.2 基于字符串相似度算法的自動評分

程序中字符串的相似度就是指一個字符串與另一字符串的相似程度。這類算法有很多，文獻[3]中采用編輯距離算法，編輯距離即從原字符串轉(zhuǎn)換到目標(biāo)字符串所滿足的插入，刪除和替換的數(shù)量的最小值。在系統(tǒng)中，運用黑盒測試法、字符串相似度與關(guān)鍵點匹配這三個層次進行評價，這三個層次的評分過程的流程如圖1所示。

圖1 字符串相似度方法的評分過程

Fig.1 The scoring process of string similarity method

該系統(tǒng)采用由小變大的評價粒度。字符串相似度從總體上給出評分結(jié)果，但關(guān)鍵的匹配方法是看所給程序題中得分點給分，與字符串相似度比較顯得粒度較大。程序設(shè)計題經(jīng)過三個層次的評測，全面地考察了學(xué)生對問題的理解與掌握程度，比僅使用單一的黑盒測試法更加客觀、公平，比僅使用關(guān)鍵點匹配評價更加精細、全面。該系統(tǒng)已經(jīng)在該校的計算中心進行多次實際應(yīng)用，基本能夠滿足C語言程序設(shè)計要求，但需要對標(biāo)準(zhǔn)答案與關(guān)鍵點匹配方法等方面進一步的完善。

3.3 用正則表達式來描述得分點的自動評分

正則表達式實際上亦為匹配模式，它由一系列具有特定含義的字符串構(gòu)成，用來進行匹配和替換。該方法用分割程序語義的處理方法，也就是在評分過程中不是用程序與模板進行完全匹配，而是把模板程序拆分成若干個得分點，并用正則表達式描述，然后在考生程序中搜索與得分關(guān)鍵點類似的代碼段，進行直接匹配評分[4]。通常來說，一道程序設(shè)計題在評分時會有三種情況：一是能進行編譯運行且結(jié)果正確；二是能進行編譯運行但結(jié)果不正確；三是不能進行編譯運行，同時得不到結(jié)果。

對于以上三種進行分析應(yīng)用的方法和手段不全部相同，因此需要分別對這三種情況進行處理。圖2給出用正則表達式來描述得分點的自動評分。

圖2 用正則表達式評分

Fig.2 The scoring method of using regular expression

首先，若為第一種，只需分析程序的代碼是否可信即可；若為第二種，通過基于得分關(guān)鍵點的評分模型進行評分；若為第三種，從語法或詞法等判斷代碼是否出錯，因為語法和詞法也是程序設(shè)計題的一個評分基點，故先對學(xué)生程序的詞法和語法錯誤進行統(tǒng)計，然后結(jié)合其他得分基點算出學(xué)生總成績。

該方法與人工閱卷評測結(jié)果非常接近，可是正則表達式的模式在構(gòu)造時太嚴(yán)格，學(xué)生程序中的某些程序的詞法或語法錯誤而導(dǎo)致檢測失??；若正則表達式的模式過于寬松，則會產(chǎn)生歧義。故正則表達式中應(yīng)忽略一些常見語法錯誤，如把一些對語法的檢測字串改為可選項，如分號等，而把這些交給語法分析去完成。故該方法不僅考慮全面而且要精確，故該模型構(gòu)造的優(yōu)劣也同樣對系統(tǒng)評分的結(jié)果產(chǎn)生或大或小的影響。

4 綜合型方法（Comprehensive methods）

所謂綜合型方法是指該評分方法不只是用一種只針對程序結(jié)構(gòu)語義，語句、字符串等方面的分析來對學(xué)生編寫的程序與模板程序進行直接的匹配評分，而是采用這種比如動態(tài)分析與靜態(tài)測試、程序分析與樹核相似、基于程序理解的綜合型評分方法。

4.1 基于程序理解的綜合型自動評分

程序理解即為先對源程序分析，并對源程序概括、推理來獲取內(nèi)容的方法過程。該方法把人為閱卷的某些思維過程與程序理解的策略緊密結(jié)合，并將模板程序與考生程序比較，然后對考生程序評分[5]。其主要評分方法過程如下：

（1）把程序代碼用系統(tǒng)依賴圖（SDG）來表示。

（2）標(biāo)準(zhǔn)化處理轉(zhuǎn)換成SDG，來去除程序多樣化[6]。

（3）匹配考生源程序和模板程序得出評分——從程序的規(guī)模、結(jié)構(gòu)及深度等幾方面入手。

該方法是運用程序的層次構(gòu)造分析，并對程序進行的逆向分析獲得程序的結(jié)構(gòu)內(nèi)容，然后把這些信息用圖形化形式表示出來，盡管程序的內(nèi)部結(jié)構(gòu)及邏輯關(guān)系便于理解，但重點在于對程序結(jié)構(gòu)的理解方面，不能做到用正確的邏輯關(guān)系來檢查程序。

蘇小紅等[5]在程序理解基礎(chǔ)上使用面向綜合能力的程序設(shè)計題自動評分方法，評分策略： 一是根據(jù)程序語義評分； 二是通過得分關(guān)鍵語句查找評分；三是使用動態(tài)測試評分。該方法的評分流程如圖3所示。

圖3 基于程序理解的自動評分方法

Fig.3 Automatic scoring method based on program

understanding

以上三個方法因都有優(yōu)缺點，將三個層次互相配合，互相補充，能更全面地計算出句子之間的相似度，對考生代碼正確、迅速地評分。但應(yīng)用于該系統(tǒng)時，在題目的錄入存在一些較為不人性化問題，可適當(dāng)增加部分刪除、修改的功能，使系統(tǒng)更加智能化；而且對參考答案模板的要求較高，提取模板技術(shù)有待完善與改進。

4.2 動態(tài)測試與靜態(tài)分析相結(jié)合的自動評分

動態(tài)測試的評分方法是把源程序編譯為可執(zhí)行文件，用預(yù)先定義的測試數(shù)據(jù)集中的數(shù)據(jù)作為輸入來測試，將結(jié)果與期望結(jié)果比較，參考對比結(jié)果給出具體分?jǐn)?shù)。評分過程如圖4所示。源程序靜態(tài)分析評分是把程序與模板的源代碼分析對比，評定學(xué)生成績。評分過程如圖5所示。

圖4 動態(tài)測試的自動評分

Fig.4 Automatic scoring of the dynamic test

圖5 靜態(tài)分析的自動評分

Fig.5 Automatic scoring of static analysis

兩種方法各有優(yōu)缺點，若兩者結(jié)合，可使評分準(zhǔn)確性很大有提升，后者能完成有用模板提取方法，使模板能提高基于靜態(tài)分析的評分準(zhǔn)確性。通過基于動態(tài)測試的評分方法的研究，在語義相似度的基礎(chǔ)上采用動態(tài)測試與靜態(tài)分析相結(jié)合的自動評分方法。該方法刪掉冗余的限制，改變評分策略，增加模板提取部分，更適用普通考生在線考試。如圖6所示的方法用于實際的上機考試，經(jīng)考試數(shù)據(jù)分析，該方法不僅能提高模型評分的準(zhǔn)確性，還能降低原有模型對模板庫的依賴程度，這為提升評分準(zhǔn)確性提供有效方法。由于編程題自動評分的課題研究存在很大難度，涉及諸多知識，還有許多技術(shù)亟待解決，該方法不可能完全解決所有問題，故在模板提取方法等方面還需進一步改進。

圖6 動態(tài)測試與靜態(tài)分析相結(jié)合的自動評分

Fig.6 Automatic scoring combination of dynamic test

and static analysis

4.3 程序分析與樹核相似算法相結(jié)合的自動評分

程序分析與樹核相似算法相結(jié)合的自動評分方法，實質(zhì)上亦是一種動態(tài)測試與靜態(tài)分析結(jié)合過程。但不同的是，采用抽象語法樹（Abstract Syntax Tree 簡稱AST）這種中間表示描述考生程序語法結(jié)構(gòu)信息，然后用樹核的相似度算法計算程序的結(jié)構(gòu)相似度[7]。即對源程序結(jié)構(gòu)深度分析，把句子表示成樹形結(jié)構(gòu)（通過抽象語法樹來得到）。使用語法樹的優(yōu)點使樹形結(jié)構(gòu)便于匹配。用樹核算法計算兩個程序相似度，如下舉一個簡單例子來說明。

程序一

void fun（ ）

{

int...

for...

}

程序二

void fun（ ）

{

int...

if...

}

它們的樹形結(jié)構(gòu)如圖7所示。語法樹的5棵子樹只有1個子樹是相同的，故兩程序的結(jié)構(gòu)相似度為1。使用樹形結(jié)構(gòu)來表示程序題的嵌套結(jié)構(gòu)是最直觀的方法，更能體現(xiàn)結(jié)構(gòu)信息。

圖7 語法樹的子樹

Fig.7 The subtree of syntax tree

該方法在語法錯誤識別和知識點識別方面雖精確，評分結(jié)果也能反映學(xué)生的真實水平，雖只注重考查學(xué)生程序的內(nèi)部語法結(jié)構(gòu)。但該方法更人性化，只要考生寫出一部分功能語句，系統(tǒng)會給相對合理的分?jǐn)?shù)，基本不會出現(xiàn)全部零分的情況，系統(tǒng)采用以下公式來計算評分的準(zhǔn)確率GP：

其中，Tscore表示人工評分，Stscore表示給出的最后分?jǐn)?shù)，F(xiàn)ullscore表示總分。

該方法在實際應(yīng)用中接近人工閱卷，但有些功能不夠完善，如對復(fù)雜的程序表達式的處理不完整；同時對模板要求較高，若不提供豐富的模板，會降低評分結(jié)果準(zhǔn)確率。

5 結(jié)論（Conclusion）

本文對程序設(shè)計題自動評分方法進行了分類，分析了自動閱卷基本原理、算法步驟和關(guān)鍵技術(shù)。程序分析比較法的自動評分雖然準(zhǔn)確率相對較高，但在模板提取的技術(shù)上有待改進；基于程序理解的綜合型評分方法在評分思路上更符合人們的思維習(xí)慣，但在程序題的錄入編輯技術(shù)上有待改進；程序設(shè)計題的自動評分是對理論和實踐要求較高的問題，要使評分結(jié)果更接近人工閱卷，還需在各個方面加強研究。只有將程序設(shè)計題自動評分技術(shù)理論與實踐相結(jié)合，并不斷發(fā)展與改進，才能更好地應(yīng)用于各類大型計算機考試的自動評分閱卷工作中。

參考文獻（References）

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

2014，17（9）：46-47.

[2] 王寧.編程題自動評分系統(tǒng)中結(jié)構(gòu)體的研究與實現(xiàn)[D].哈爾

濱工業(yè)大學(xué)，2006.

[3] 杜利峰，牛永潔.字符串相似度在自動評分系統(tǒng)中的應(yīng)用[J].

電子設(shè)計工程，2011，19（7）：42-44.

[4] 佘石泉.編程題自動閱卷技術(shù)的研究與實現(xiàn)[D].中南大學(xué)，

2007.

[5] 蘇小紅，等.面向綜合實踐能力考核的C語言編程考試自動評

分系統(tǒng)[J].實驗技術(shù)與管理，2010，27（10）：173-177.

[6] 李必信，等.一種分析和理解程序的方法-程序切片[J].計算機

研究與發(fā)展，2000，37（3）：284-289.

[7] 陳媛媛.基于抽象語法樹的編程題自動評分系統(tǒng)的研究與應(yīng)

用[D].大連海事大學(xué)，2011.

作者簡介：

馮秀梅（1990-），女，研究生.研究領(lǐng)域：軟件工程.

張永勝（1962-），男，碩士，教授.研究領(lǐng)域：數(shù)據(jù)庫技術(shù)，網(wǎng)

絡(luò)信息安全.