程序設計題自動評分方法研究

馮秀梅 張永勝

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

關鍵詞：自動評分；程序設計；人工閱卷

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

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

4.2 動態測試與靜態分析相結合的自動評分

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

圖4 動態測試的自動評分

Fig.4 Automatic scoring of the dynamic test

圖5 靜態分析的自動評分

Fig.5 Automatic scoring of static analysis

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

圖6 動態測試與靜態分析相結合的自動評分

Fig.6 Automatic scoring combination of dynamic test

and static analysis

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

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

程序一

void fun（ ）

{

int...

for...

}

程序二

void fun（ ）

{

int...

if...

}

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

圖7 語法樹的子樹

Fig.7 The subtree of syntax tree

該方法在語法錯誤識別和知識點識別方面雖精確，評分結果也能反映學生的真實水平，雖只注重考查學生程序的內部語法結構。但該方法更人性化，只要考生寫出一部分功能語句，系統會給相對合理的分數，基本不會出現全部零分的情況，系統采用以下公式來計算評分的準確率GP：

其中，Tscore表示人工評分，Stscore表示給出的最后分數，Fullscore表示總分。

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

5 結論（Conclusion）

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

參考文獻（References）

[1] 趙曉靜.編程題自動閱卷系統的設計與實現[J].軟件工程師，

2014，17（9）：46-47.

[2] 王寧.編程題自動評分系統中結構體的研究與實現[D].哈爾

濱工業大學，2006.

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

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

[4] 佘石泉.編程題自動閱卷技術的研究與實現[D].中南大學，

2007.

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

分系統[J].實驗技術與管理，2010，27（10）：173-177.

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

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

[7] 陳媛媛.基于抽象語法樹的編程題自動評分系統的研究與應

用[D].大連海事大學，2011.

作者簡介：

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

張永勝（1962-），男，碩士，教授.研究領域：數據庫技術，網

絡信息安全.