基于最小子程序匹配的C語言自動(dòng)評分算法研究

朱林琴++劉新++張輝++李亭葳

摘 要：針對傳統(tǒng)的編程題自動(dòng)評分方法無法準(zhǔn)確衡量學(xué)生對知識(shí)點(diǎn)掌握程度的問題，提出了一種基于最小子程序匹配的C語言自動(dòng)評分算法。算法首先將程序做標(biāo)準(zhǔn)化處理，然后轉(zhuǎn)換為樹形子程序，再通過搜索檢測劃分更小粒度的子程序。再根據(jù)自動(dòng)評分算法完成對C語言程序的自動(dòng)評分。初步實(shí)驗(yàn)結(jié)果表明：自動(dòng)評分算法與普通的人工評分誤差相差不大，相較于傳統(tǒng)的自動(dòng)評分方法，其結(jié)果更能反映出學(xué)生的真實(shí)水平。

關(guān)鍵詞：自動(dòng)評分；子程序；樹；C語言

中圖分類號：TP311 文獻(xiàn)標(biāo)志碼：A 文章編號：1673-8454（2017）17-0026-04

引言

目前國內(nèi)外有許多程序設(shè)計(jì)在線測試系統(tǒng)[1]，這類線上測試系統(tǒng)對學(xué)生提交的代碼一般采取的評分方式主要分為兩大類：①動(dòng)態(tài)測試[2-8]，即對學(xué)生程序進(jìn)行編譯、運(yùn)行。當(dāng)編譯不通過、編譯過后運(yùn)行結(jié)果錯(cuò)誤、運(yùn)行時(shí)間超時(shí)情況出現(xiàn)時(shí)都判定提交程序無效，該方法快速、直接。②靜態(tài)評分方法[2][9-12]，靜態(tài)評分通過靜態(tài)分析學(xué)生源代碼與答案模板代碼，用抽象語法樹、系統(tǒng)依賴圖、程序依賴圖等中間表現(xiàn)形式，然后從中提取特征屬性值或度量值來進(jìn)行匹配再給出分值。

動(dòng)態(tài)評分是目前較多在線測試系統(tǒng)中用到的評分方法，其前提是程序能運(yùn)行成功，當(dāng)程序運(yùn)行結(jié)果不匹配，隨機(jī)測試用例結(jié)果等情況都以0分處理。所以對學(xué)生的考察存在片面性。國內(nèi)外學(xué)者在靜態(tài)評分的研究上有很多，有文獻(xiàn)表明通過計(jì)算控制流圖結(jié)點(diǎn)的相似度進(jìn)行編程題自動(dòng)評分，[13]還有文獻(xiàn)表明在考生程序生成語法樹后進(jìn)行遍歷使用Levenshtein算法完成編程題自動(dòng)評分。[14]靜態(tài)分析能在一定程度上得到學(xué)生程序與模板程序的相似度，從而生成學(xué)生得分。

但由于學(xué)生編寫的源代碼存在著多樣性，以及現(xiàn)有的技術(shù)對程序的理解度、語義分析的準(zhǔn)確度還不太高等原因，評分準(zhǔn)確性會(huì)受到影響。針對這些問題，本文提出了一種基于最小子程序匹配的自動(dòng)評分算法，首先根據(jù)自定義試用于匹配的子程序，對源代碼經(jīng)過詞法、語法分析，依據(jù)系統(tǒng)依賴圖將程序轉(zhuǎn)換為有序樹，該樹包含不同粒度的子程序，通過構(gòu)造樹時(shí)的關(guān)系規(guī)則將子程序圖切分為多個(gè)更小粒度的子程序集合，然后對學(xué)生子程序與模板子程序采取從小到大的遞歸式匹配方式，最后結(jié)合模板程序中標(biāo)記的權(quán)值為學(xué)生程序打分。此方法對學(xué)生是否掌握某語法知識(shí)或是結(jié)構(gòu)的使用有很好的效果。

一、基本子程序的定義

子程序[15]是能被其他程序調(diào)用、在實(shí)現(xiàn)某種功能后能自動(dòng)返回到調(diào)用程序的程序。其最后一條指令一定是返回指令，故能保證重新返回到調(diào)用它的程序中去。也可調(diào)用其他子程序，甚至可自身調(diào)用。為了適用于本文算法對子程序做了重新描述，子程序是能實(shí)現(xiàn)某一功能的基本語句的集合，可以嵌套、組合，沒有返回值。在這里將一個(gè)語句塊看作一個(gè)子程序。

為了能考察學(xué)生程序中是否實(shí)現(xiàn)了某些基本的功能，首先將學(xué)生程序與模板程序分解為基本的子程序，然后依靠系統(tǒng)依賴圖的數(shù)據(jù)依賴找出子程序之間的關(guān)系，每個(gè)子程序的中間表示都是一棵具有語義信息的子樹。最后對子樹進(jìn)行匹配。分析文中處理的C語言特性，劃分組成子程序的基本單元，具體形式有：聲明語句、庫函數(shù)調(diào)用語句、賦值語句、選擇分支語句、循環(huán)語句、返回語句、跳出語句。上述基本語句單位通過并列、嵌套、順序三種關(guān)系組成功能復(fù)雜的子程序。

二、基于有序樹的程序中間表示

答案模板程序和學(xué)生程序在經(jīng)過詞法分析和語法分析時(shí)，利用標(biāo)準(zhǔn)化規(guī)則在不改變語義的情況下消除語句的多樣性，同時(shí)獲得由多個(gè)不同粒度的子程序，且子程序之間通過數(shù)據(jù)流的依賴相互聯(lián)系。實(shí)現(xiàn)排序的源代碼如下所示：

#include ①

int main（）{

int i，j，temp，a[10]；

for（i=0；i<10；i++）

scanf （"%d，"，&a[i]）；

for（j=0；j<=9；j++） {

for （i=0；i<10-j；i++）

if （a[i]>a[i+1]）{

temp=a[i]；

a[i]=a[i+1]；

a[i+1]=temp；

}

}

for（i=1；i<10；i++）

printf（"%d，"，a[i] ）；

return 0；

}

（1）語句①依據(jù)標(biāo)準(zhǔn)化規(guī)則處理分為以下形式：

int I；int j；int temp；int a[0]

（2）依據(jù)數(shù)據(jù)流劃分出如下子程序用有序樹表示，以下根據(jù)粒度的大小進(jìn)行排序，粒度越大的子程序中組合、嵌套的其他子程序越多，從粒度大到粒度小的子程序如圖1、2、3所示：

由于篇幅限制僅展示3幅子程序有序樹圖。圖1是最小子程序。從圖1到圖2再到圖3的轉(zhuǎn)變過程可以很明顯地看出更小粒度的子程序是根據(jù)有序樹中右子樹種切分出來的，同時(shí)右子樹的子程序的第一個(gè)結(jié)點(diǎn)與其父親結(jié)點(diǎn)是嵌套關(guān)系，而左子樹是依據(jù)程序運(yùn)行子程序的順序關(guān)系連接得出的。

本例中沒有出現(xiàn)多選擇分支，鑒于并列代碼的特殊性，在此規(guī)定，當(dāng)檢測到子程序是分支語句時(shí)，構(gòu)造樹型圖時(shí)該結(jié)點(diǎn)下的子程序從左至右，最左邊為左子樹與上面描述一致，除了該左子樹其他均為右子樹。即一個(gè)父結(jié)點(diǎn)有多個(gè)子結(jié)點(diǎn)時(shí)，最左的子結(jié)點(diǎn)與父結(jié)點(diǎn)為順序關(guān)系，其他結(jié)點(diǎn)與父結(jié)點(diǎn)為嵌套關(guān)系，且這部分的結(jié)點(diǎn)之間是并列關(guān)系。由于該父結(jié)點(diǎn)下的子結(jié)點(diǎn)不滿足有序樹的定義，在有大于兩個(gè)子結(jié)點(diǎn)的情況下，也就是存在并列關(guān)系的節(jié)點(diǎn)時(shí)，子結(jié)點(diǎn)之間是無序的。也就是說本文中用于構(gòu)造子程序有序樹不是真正意義上的有序樹。

三、最小子程序匹配評分算法

1.子程序分塊預(yù)處理

在對編程題自動(dòng)評分的研究中存在的一個(gè)難點(diǎn)就是C語言程序設(shè)計(jì)的多樣性，為了更多更精確地讓學(xué)生程序匹配到答案模板，都會(huì)在之前對語句做語義等價(jià)轉(zhuǎn)換，轉(zhuǎn)換規(guī)則如下所示：

（1）拆分復(fù)合語句

將復(fù)合語句被拆分為等價(jià)的語句序列，有運(yùn)算表達(dá)式的拆分、函數(shù)嵌套調(diào)用的拆分、聲明語句的拆分等等，讓語句化到最簡表達(dá)形式。

（2）統(tǒng)一循環(huán)結(jié)構(gòu)表示

在循環(huán)結(jié)構(gòu)中for、while和do...while之間有差別，為消除其多樣性將統(tǒng)一進(jìn)行如下處理：將for語句轉(zhuǎn)換為while語句的表達(dá)形式，提取for語句中的表達(dá)式1到循環(huán)體外，將表達(dá)式3寫入循環(huán)體內(nèi)。do...while循環(huán)要比其他循環(huán)多執(zhí)行一次，因此將循環(huán)體提取出來作為一個(gè)塊，然后將其轉(zhuǎn)換為while循環(huán)。以上操作的處理可以讓數(shù)據(jù)依賴和控制依賴更加明確清晰。

2.劃分最小粒度子程序

模板程序與生產(chǎn)程序經(jīng)過轉(zhuǎn)換得到標(biāo)準(zhǔn)子程序后，經(jīng)過下一步驟將最大粒度子程序劃分為逐一遞減子程序：

（1）從根結(jié)點(diǎn)出發(fā)向左子樹進(jìn)行深度遍歷，斷開具有右子樹的結(jié)點(diǎn)的父連接與左子樹連接，得到“最大粒度-1”的多個(gè)子程序。

（2）保存每次切分出的不同粒度的子程序，并重復(fù)步驟1的切分方式，直到切分出的子樹種結(jié)點(diǎn)沒有右子樹為止。

根據(jù)文中給出的排序源碼可以得到子程序集合PArray[n]= {pList1，pList2，...，pListn}，PArray是一個(gè)一維數(shù)組，按順序調(diào)用pListn，pListn是一個(gè)集合，存儲(chǔ)最大粒度子程序及該粒度下包含的層級遞減的細(xì)小粒度。以上面源碼為例存儲(chǔ)結(jié)構(gòu)如圖4所示：

3.子程序匹配

子程序之間匹配從最小粒度出發(fā)，匹配子程序的數(shù)據(jù)變量數(shù)據(jù)流依賴類型以及組成子程序的基本單元類型，以匹配圖1為例，源程序中有三個(gè)變量作交換，變量temp是流依賴，作用兩個(gè)賦值語句；變量a[i]是反依賴，作用兩個(gè)賦值語句；變量a[i+1]是反依賴，作用兩個(gè)賦值語句。當(dāng)學(xué)生代碼子程序中能匹配以上信息就算匹配成功。匹配后的子程序?qū)⒉粫?huì)進(jìn)入下一個(gè)更大粒度的子程序匹配。以匹配圖2為例，在匹配圖4中子程序的時(shí)候不再匹配圖2中連接的圖4中的子程序。

4.子程序匹配的自動(dòng)評分算法

基于子程序匹配的自動(dòng)評分算法的基本思想是：從最小粒度的子程序開始匹配，當(dāng)學(xué)生子程序滿足模板子程序中變量的數(shù)據(jù)依賴關(guān)系和控制依賴關(guān)系時(shí)則判定為正確，并記錄該子程序在整個(gè)程序中所占的分?jǐn)?shù)權(quán)值，之后根據(jù)匹配到的該最小粒度子程序結(jié)點(diǎn)搜索下一個(gè)父親結(jié)點(diǎn)，由此往上遞推，直到匹配完模板程序中由順序關(guān)系組成的最大粒度子程序。結(jié)合圖4所示的數(shù)據(jù)存儲(chǔ)表描述具體算法步驟如下所示：

第一步：取帶權(quán)模板子程序數(shù)組集合TPArray[n]={tpList1，tpList2...tpListn}，學(xué)生子程序數(shù)組集合SArray[m]={spList1，spList2...spListm}。y表示tpListn中子程序個(gè)數(shù)，z表示spListm子程序個(gè)數(shù)。設(shè)變量i=0、變量j=0、變量t=0、變量z=0，二維數(shù)組記錄匹配帶權(quán)子程序tempSimPArray[n][max]，max為tpListn中的最大長度。一維數(shù)組score存儲(chǔ)最大匹配到的子程序權(quán)值。

第二步：匹配spListj[i]與tpListt[z]數(shù)據(jù)的控制依賴：

（1）匹配成功i++，z++，將tpListt[z]存入tempSimPArray[t][z]，當(dāng)zm||i>n與t

（2）當(dāng)匹配不成功且tn時(shí)執(zhí)行第三步。

第三步：累計(jì)tempSimPArray中每一行中匹配到的子程序權(quán)值，取最大權(quán)值存入score。j++，當(dāng)jm，執(zhí)行第四步。

第四步：累加score中權(quán)值，輸出。

四、程序評分實(shí)現(xiàn)及實(shí)驗(yàn)結(jié)果分析

通?？疾鞂W(xué)生編程題的本意是檢測學(xué)生是否掌握了某些知識(shí)點(diǎn)，所以與知識(shí)點(diǎn)相關(guān)的代碼的得分權(quán)重要比其他代碼要大一些。實(shí)驗(yàn)中在沒有對模板程序做知識(shí)點(diǎn)標(biāo)記的情況下子程序的權(quán)值取總分均值。通過累計(jì)匹配到的子程序所帶權(quán)值，計(jì)算出學(xué)生的最終成績。

實(shí)驗(yàn)系統(tǒng)的流程如圖5所示：

為了檢測自動(dòng)評分的準(zhǔn)確率，實(shí)驗(yàn)選取5道編程題如表1所示，并取得50名學(xué)生提交的答案及教師提供的答題模板。

為了驗(yàn)證前文所述的自動(dòng)評分算法的性能，首先由多名教師嚴(yán)格按照評分標(biāo)準(zhǔn)給每個(gè)答題進(jìn)行打分，將其作為專業(yè)標(biāo)準(zhǔn)評分結(jié)果；然后隨機(jī)選取C語言程序設(shè)計(jì)課程的研究生助教給所有答案打分作為普通的人工評分；最后與我們的實(shí)驗(yàn)系統(tǒng)自動(dòng)評分結(jié)果進(jìn)行比較，以及用Levenshtein算法進(jìn)行自動(dòng)評分，評分詳情如表2所示。根據(jù)式1計(jì)算人工評分與自動(dòng)評分相對于標(biāo)準(zhǔn)評分的誤差率ER。

Erate=■×100%（1）

其中SScore為專業(yè)人士的標(biāo)準(zhǔn)評分，TestScore為普通助教人員的人工評分或文中的自動(dòng)評分，AllScore為總分。

在此次選取實(shí)驗(yàn)數(shù)據(jù)中模板數(shù)較多的題目編號1和編號3相對人工評分的誤差要比其他模板少的誤差率要小，說明了模板的數(shù)量在一定程度上對評分的精確度有影響。題目中涉及遞歸編程的題目2自動(dòng)評分誤差率最大，在后面的實(shí)驗(yàn)中需要在這個(gè)方面做改進(jìn)。從整體上來看與人工的誤差率是相對較小的。

五、結(jié)束語

基于最小子程序匹配的編程題自動(dòng)評分算法，是將人工評分的思維過程與考點(diǎn)結(jié)合起來，通過粒度小到粒度大的子程序的層級匹配能檢測出學(xué)生知識(shí)點(diǎn)的掌握程度。將程序劃分為不同粒度的子程序，由于子程序保存相關(guān)語義信息，在匹配過程中能提高準(zhǔn)確性。并且克服了程序?qū)崿F(xiàn)多樣性，語法、語義分析復(fù)雜度高等問題。其實(shí)驗(yàn)結(jié)果表明自動(dòng)評分與專業(yè)評分比較是存在誤差的，但與普通人工相比誤差控制的范圍是不大的，與Levenshtein算法相比總體上要優(yōu)于該算法。并且程序?qū)崿F(xiàn)思路清晰。在實(shí)驗(yàn)過程中會(huì)得到更多的模板程序，因此在后續(xù)的匹配中準(zhǔn)確率也將會(huì)有所提高。

參考文獻(xiàn)：

[1]申田靜，陳俊.國內(nèi)在線考試系統(tǒng)研究綜述[J]. 中國教育技術(shù)裝備，2015（14）：19-22.

[2]李郴，史國峰.編程題綜合評分方法的研究[J]. 計(jì)算機(jī)與網(wǎng)絡(luò)，2016（6）：38-39.

[3]A. Drummond， Y. Lu， S. Chaudhuri， C. Jermaine， J. Warren and S. Rixner， "Learning to Grade Student Programs in a Massive Open Online Course，" 2014 IEEE International Conference on Data Mining， Shenzhen， 2014：785-790.

[4]R. Romli， S. Sulaiman and K. Z. Zamli， "Test data generation framework for Automatic Programming Assessment，" Software Engineering Conference （MySEC）， 2014 8th Malaysian， Langkawi，2014：84-89.

[5]Alamutka K M. A Survey of Automated Assessment Approaches for Programming Assignments[J].Computer Science Education， 2005， 15（2）：83-102.

[6]Pozenel M， Furst L， Mahnicc V. Introduction of the automated assessment of homework assignments in a university-level programming course[C].International Convention on Information and Communication Technology， Electronics and Microelectronics. IEEE， 2015：761-766.

[7]Cui B， Li J， Guo T， et al. Code Comparison System based on Abstract Syntax Tree[C].IEEE International Conference on Broadband Network and Multimedia Technology. IEEE， 2010：668-673.

[8]Rubio-S， Nchez M， Kinnunen P， et al. Student perception and usage of an automated programming assessment tool[J].Computers in Human Behavior， 2014，31（2）：453-460.

[9]Cui B， Li J， Guo T， et al. Code Comparison System based on Abstract Syntax Tree[C].IEEE International Conference on Broadband Network and Multimedia Technology. IEEE，2010：668-673.

[10]劉月霞，牛志堯，吳寧.面向大規(guī)模在線開放課程的編程題多特征綜合自動(dòng)評分方法[J].西安交通大學(xué)學(xué)報(bào)，2016（10）：64-70.

[11]王倩，蘇小紅，馬培軍.有語法錯(cuò)誤的編程題自動(dòng)評分方法研究——用局部語法分析和采分點(diǎn)匹配實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2010（17）：239-242.

[12]馬培軍，王甜甜，蘇小紅.基于程序理解的編程題自動(dòng)評分方法[J].計(jì)算機(jī)研究與發(fā)展，2009（7）：1136-1142.

[13]Vujo？觢evi■-Jani■i■ M， Nikoli■ M， To？觢i■ D， et al. Software verification and graph similarity for automated evaluation of students assignments[J].Information & Software Technology， 2012， 55（6）：1004-1016.

[14]劉天藍(lán).基于語義理解與運(yùn)行分析的程序題自動(dòng)評分算法研究[D].湖南師范大學(xué)，2013.

[15]徐寶文，張挺，陳振強(qiáng).遞歸子程序的依賴性分析及其應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào)，2001（11）：1178-1184.

[16]姜華，韓安琪，王美佳，王崢，吳雲(yún)玲.基于改進(jìn)編輯距離的字符串相似度求解算法[J].計(jì)算機(jī)工程，2014（1）：222-227.

[17]張有為，劉小春，汪永紅.程序段識(shí)別算法研究[J].計(jì)算機(jī)工程，2009（5）：72-100.

[18]李靜，高萬林，段晶潔等.編程題自動(dòng)評測系統(tǒng)的研究與設(shè)計(jì)[J].wisdom science and technology，2016（4）：11-16.

[19]Liu Y， Chai W， Li X， et al. Design and Implementation of Automatic Marking System for Programming Questions Based on Script Technique[C].2014 International Conference on Computer， Communications and Information Technology （CCIT 2014）. Atlantis Press， 2014.

[20]Liu X， Tao L， Zhou Y， et al. The Automatic Marking Method of SQL Script Based on Syntax Analysis and Levenshtein Distance[J].2014.

（編輯：王天鵬）endprint