面向語句分值的C程序靜態(tài)評分方法

舒新峰，賈敬霞，何孝敏，付穩(wěn)穩(wěn)

(西安郵電大學 計算機學院，陜西 西安 710121)

0 引 言

隨著互聯(lián)網(wǎng)技術在“C程序設計”教學過程中的應用，一些高校引入C程序在線考試系統(tǒng)實現(xiàn)自動閱卷[1-3]，而現(xiàn)有的考試系統(tǒng)主要采用動態(tài)評測和靜態(tài)分析兩類技術。動態(tài)評測通過編譯運行待判定程序并輸入測試用例集，根據(jù)程序輸出結果與預期結果是否一致來評分[4-6]。當程序存在語法錯誤而無法運行時，此類系統(tǒng)會給予0分成績，評分結果較為粗糙，不符合實際教學需求。

靜態(tài)分析方法通過分析待判定程序的結構及語義特征獲取評分結果，主要分為兩種。一種通過統(tǒng)計程序代碼行數(shù)、函數(shù)、循環(huán)結構等程序屬性特征的數(shù)量給出評分[7]，但因沒有考慮程序語義而導致評分結果比較粗糙。另一種將學生程序和答案程序轉化為中間形式，如控制流圖[8,9]、抽象語法樹[10,11]、系統(tǒng)依賴圖[12,13]等，然后比較兩者的相似度進行評分，但現(xiàn)有的中間表示形式不能準確表達程序結構及語句依賴關系，降低了評分的準確性。

針對上述問題，本文提出面向語句分值的C程序靜態(tài)評分方法，通過在答案程序中標注描述評分細則的語句分值，引入能夠準確描述語句控制、數(shù)據(jù)依賴關系的程序語句依賴圖作為中間表示結構。評分過程如圖1所示，首先對待判定C程序進行標準化，消除表達多樣性問題，具體策略見參考文獻[10]；其次構造帶有語句分值的程序語句依賴圖；最后匹配待判定程序和答案程序間路徑片段集合實現(xiàn)程序評分。

圖1 靜態(tài)評分過程

1 答案程序中語句分值的設置

為支持命題教師準確描述評分細則，根據(jù)知識點、語句的重要性對答案程序中的語句片段設置不同分值，即對答案程序中的單行、多行語句設定不同注釋方式來描述考察的知識點及分值權重。當一個分值表示多行語句時，在這些語句的第一條源碼后面標注/*ktype_symbol- -score*/表示分值的開始，最后一條語句標注/*ktype_symbol*/表示該分值所表示語句范圍結束；而分值表示一條語句時，則在這條語句后標注/*- -score*/表示；此外用/*sum- -score*/表示整個答案程序的分值。其中ktype_symbol表示知識點符號，具體取值見表1，score為分值。例如，“求π值問題”答案程序中語句分值的標注情況如圖2所示。

圖2 “求π值問題”的答案程序

2 程序語句依賴圖

針對現(xiàn)有的評分方法不能精確表示程序語句間執(zhí)行次序及依賴關系、選擇/循環(huán)的語法結構，對系統(tǒng)依賴圖[12,13]進行改進，引入了程序語句依賴圖(program statement dependency graph，PSDG)來描述待判定程序的語法結構。

2.1 程序語句依賴圖定義

PSDG基本策略是將C程序遞歸描述為復合語句的集合，每個復合語句由復合語句名稱和復合語句體構成，復合語句體為語句及其數(shù)據(jù)/控制依賴關系構成的有向圖，圖3為PSDG的結構。第一層為函數(shù)復合語句，復合語句名稱(圓形頂點)為函數(shù)名，復合語句體為函數(shù)體語句(方形頂點)構成的有向圖，圖中的弧表示語句stmt_i必優(yōu)先于語句stmt_k執(zhí)行，即后者的執(zhí)行對前者的計算結果存在依賴關系；語句stmt_k和stmt_t之間沒有弧直接或者間接相連，表示其執(zhí)行次序上無先后約束。特別地，當復合語句體中包含if或while語句時，如函數(shù)Fun_1中的if語句，其復合語句名稱為Yes/No,而Yes分支和No分支也分別遞歸描述為復合語句(while語句結構無No分支)。

圖3 程序語句依賴

根據(jù)上述策略，PSDG的形式化定義如圖4所示。PSDG 定義為復合語句集合ComStmtSet；每個復合語句ComStmt為一個有向圖，其中nameNode為復合語句名稱頂點，varRefSet、nodeSet、arcSet分別表示復合語句中的變量集、頂點集和弧集。nameNode中的name為復合語句名稱。頂點Node中的NodeType標識語句類型，取值type_Var、type_Expr、type_If、type_Loop、type_InOut、type_Return分別表示變量聲明、賦值、分支、循環(huán)、輸入/輸出、返回；expTree為語法子樹表示的語句內容；若Node為if/while語句時，Yes/No分支對應的復合語句存儲在subComStmtSet。變量VarRef的dataType和varName分別表示變量類型和名稱，而refNode表示最近一次引用變量的語句頂點。

圖4 PSDG的形式化定義

為了描述程序中包含的語句分值，給PSDG每個頂點設置flag、weight、gather、fchange屬性。其中flag表示語句分值所指的范圍，取值為1表示該頂點所代表的語句為分值的起始位置，為0表示語句為分值結束位置，其余頂點的flag值為2；weight表示分值的大小，在flag=1的頂點位置時weight值為score，否則為0；用gather表示分值所屬范圍，同屬于一個分值的頂點gather值相同；特別地，當一個分值所包含的語句范圍內另嵌套分值時，則用屬性fchange記錄分值間的嵌套關系。另外給每個為main的復合語句名稱頂點設置“sum”屬性用于記錄程序的總分。nameNode、Node中的pathSet存放下節(jié)評分過程中與該頂點相關的路徑片段集合。

2.2 程序語句依賴圖構造算法

根據(jù)PSDG的遞歸定義，PSDG的構造算法CreatePSDG如圖5所示。算法以C程序源代碼Source_Code作為入口參數(shù)，首先初始化圖G，遞歸遍歷Source_Code的每一個函數(shù)源代碼建立復合語句的有向圖，函數(shù)名為復合語句名稱頂點nameNode，函數(shù)體使用算法CreatComStmt構造為復合語句體子圖并將子圖添加到G中，算法結束后返回Source_Code的PSDG。

圖5 程序語句依賴圖構造算法

構造復合語句體子圖的算法CreatComStmt以復合語句體ComStmt_Code以及復合語句體子圖ComStmt作為入口參數(shù)，遞歸遍歷ComStmt_Code的每一條語句，根據(jù)語句類型及語句間的數(shù)據(jù)/控制依賴關系建立ComStmt。其構造過程如下所示：

(1)如果語句為變量聲明類型時，新建一個圖頂點node，將語句類型、內容存入node，使用AddNode函數(shù)將語句頂點添加到復合語句體子圖中，使用AddArc建立nameNode和語句間的弧連接，新建一個varRef，獲取該語句中的變量類型及名稱存入varRef中，并將node存入varRef的reFnode中作為最近一次使用node中所包含變量的頂點。最后將varRef加入到變量集varRefSet中。

(2)如果語句為變量賦值類型時，將語句存入新建的一個圖頂點node中，并將該頂點添加到ComStmt中。使用GetVarSet獲取語句中的變量集合varSet；遍歷varSet獲取每一個變量名varName，使用GetRefNode函數(shù)獲取varRefSet中最近一次使用varName的頂點，即refNode中的存放頂點，建立該頂點與node的弧連接。獲取node中被賦值的變量,并用node替換最近一次使用被賦值的變量的頂點即使用UpdateRefNode，將node存入varRefSet的reFnode中，實現(xiàn)varRefSet的更新。

(3)特別地，if/while結構需作為一個整體處理。將if條件表達式作為一個語句頂點node；遞歸建立if結構中Yes分支、No分支復合語句的子圖存入subComStmtSet。獲得子圖中使用的變量集合，在varRefSet中獲取最近一次使用變量集合的頂點，添加這些頂點與node的連接；獲取子圖中被更改的變量集合，用node替換最近一次使用這些變量的頂點，完后varSet更新。while結構采用同樣的方法處理。

(4)如果語句為輸入/輸出類型時，將語句存放在新建的圖頂點node中，獲取該語句中的變量，添加node與最近使用該變量的頂點間弧連接，并用node替換該變量的reFnode存放的結點。

(5)如果語句為返回類型，將語句存入新建的node中，獲取varRefSet的refond中所有頂點集合staNodeSet；建立node與staNodeSet中頂點的弧連接，然后用node替換staNodeSet中的頂點完后varRefSet更新。

2.3 語句分值在PSDG中表示

在獲得源程序Source_Code的程序語句依賴圖G后，遞歸遍歷Source_Code的每一個函數(shù)及函數(shù)中的每條語句code，在獲取語句分值s后，根據(jù)語句及G中頂點間的對應關系，將語句分值標注在表示code的頂點屬性中。此外在每個函數(shù)內部，一個語句分值會對應一個集合gather，不在任一語句分值區(qū)域的code歸為一個gather(需更改首尾句flag值)，這時一個函數(shù)劃分為若干個集合，多個函數(shù)形成多個集合。具體步驟如下所示：

(1)如果程序中包含s，即“/*sum- -score*/”,則將name為main頂點的屬性sum設置為score。

(2)如果s為“/*ktype_symbol- -score*/”，需將語句所對應頂點node的flag置1，weight的值為score，gather為當前所屬集合，fchange為當前所嵌套gather的集合。

(3)如果s為“/*ktype_symbol*/”，此時node為所屬分值的最后一行，故flag、weight為0，而gather、fchange保持不變。

(4)如果頂點node屬于語句分值范圍內，node的flag為2、weight為0，而gather、fchange保持不變。若s為“/*- -score*/”采用同樣的方法處理，但node的weight值需變?yōu)閟中的score。

(5)特別地，一些語句并不在“/*ktype_ symbol--score*/”和“/*ktype_symbol*/”范圍內，需變更gather、fchange的值，并將這些語句的gather、fchange保持一致，并設置這些語句頂點的flag值，令weight為0。

圖6給出圖2所描述題目的PSDG表示，而部分帶有分值的語句在PSDG中的表示見表2。

表2 語句分值在PSDG每個頂點中的表示

圖6 “求π的值”程序語句依賴

3 程序評分

在獲得標有語句分值的PSDG后，首先標準化程序語句依賴圖的標識符命名；其次依據(jù)語句分值的位置、程序中語句依賴關系將PSDG劃分為由路徑片段構成的集合；最后遍歷每個集合，依據(jù)待判定、答案程序間同集合路徑相匹配原則，計算待判定程序路徑片段的相似度，完成待判定程序評分。

3.1 劃分答案程序

3.1.1 答案程序路徑片段集合劃分

在獲得答案程序的PSDG后，依據(jù)PSDG中每個頂點的gather值及頂點間的偏序依賴關系劃分路徑片段集合，算法如圖7所示。具體說明如下：

圖7 劃分答案程序路徑片段集合算法

從起始頂點出發(fā)，遍歷PSDG的每個頂點，尋找其直接后繼頂點。若兩個頂點的gather值相同，則尋找直接后繼頂點的后繼頂點，直至直接后繼頂點gather值為另一個集合值(gather值不相等)，此時獲得從起始頂點出發(fā)的一條路徑片段；然后從起始頂點出發(fā)遍歷其余直接后繼頂點，獲取其余后繼頂點所在的路徑片段；這些路徑片段存儲在一個集合中。然后從未訪問頂點出發(fā)按照上述思路尋找其余集合，這樣PSDG就會被劃分為由路徑片段構成的集合。

3.1.2 計算答案程序中集合分值

答案程序中存在一個語句分值Wi包含另一個語句分值Wj的情況(被包含的分值Wj屬于Wi的一部分)，而在集合劃分時Wi并沒有包含Wj中的語句，因此需更改Wi的分值。即依據(jù)分值注釋間的嵌套關系，從最外層出發(fā)，用嵌套集合的分值減去所有直接被嵌套集合的分值，即父集合Wi的分值weight為其減去所有子集合Wj的分值后剩余的分值。其算法如圖8所示。

圖8 計算答案程序集合分值算法

在完成上步計算后，有些集合因教師未設置語句分值導致該類集合沒有分值，其計算方法如式(1)所示，其中題目總分為sum、已知分值的集合分值為score(共m個)、未給分值的集合數(shù)量Mnum、未給分值的集合分值為Nscore

(1)

3.2 待判定程序路徑片段集合劃分

由于答案程序中語句分值間存在嵌套關系，故需從答案程序被嵌套的路徑集合出發(fā)，依據(jù)待判定、答案程序的頂點間相似度標注待判定程序PSDG中每個頂點所屬集合值，直至每個頂點被訪問過一遍，然后按照上述方法從答案程序的嵌套集合出發(fā)標注剩余頂點的gather值，算法如圖9所示，其中Zhangshasha為頂點間相似度計算函數(shù)，具體算法見文獻[14]。

圖9 劃分待判定程序路徑片段集合

首先將待判定程序每個頂點與答案程序路徑集合中每個路徑片段的起始頂點對比，若兩個頂點相似度為1，則兩個頂點屬性gather值相同，此時該頂點為待判定程序PSDG某一集合內路徑起始頂點；遍歷該頂點的直接后繼頂點，對比直接后繼頂點與上述答案程序相應路徑片段中的結束頂點(無后繼頂點)直至相似度為1，此時獲取的頂點為待判定程序路徑的結束頂點，此時一條路徑片段形成(過程中設置兩個頂點屬性gather值相同)，否則繼續(xù)對比該后繼頂點的直接后繼頂點直至該頂點為PSDG結束頂點(即無后繼頂點的頂點)，也沒有找到相似度為1的頂點，則該條路徑放棄。

此時繼續(xù)對比頂點的其余直接后繼頂點劃分路徑片段，形成集合中的其余路徑片段，直至每個頂點都被訪問過，此時待判定程序的第一個路徑片段集合尋找完畢；然后從未被訪問的頂點出發(fā)按照上述思路尋找其余路徑片段集合。上述步驟形成的所有集合為待判定程序PSDG的路徑片段集合。

3.3 總成績

(1)路徑相似度及頂點分值計算：一條路徑上所有頂點的相似度之和與該條路徑上頂點數(shù)量的比值為路徑的相似度。特別地，若待判定程序的一個頂點i與答案程序的頂點j匹配時，頂點間相似度為Psimilar，且j有分值score，此時需用式(2)計算i的分值Pscore，否則不單獨計算頂點分值

Pscore=Psimilar*score

(2)

(2)匹配路徑/集合：答案程序S與待判定程序路徑片段集合T對比時，采用同集合(集合名相同)路徑相匹配的策略選擇待匹配的路徑，而集合中路徑匹配時則采用KM算法[15]找到每條路徑的匹配路徑。

集合M的一條路徑Mi與T中路徑相匹配時，先找到使Mi有相似度最大的路徑Tj(相似度為maxij)，然后對比M中每條路徑與Tj的路徑匹配結果，若存在使Tj相似度最大的路徑Mk則比較maxij和maxkj的大小，若maxij≥maxkj則將Tj作為Mi的匹配路徑，否則Tj不作為Mi的匹配路徑并繼續(xù)尋找使Mi有相似度次N大的路徑Tn直至滿足maxin≥maxnn，此時將Tn作為Mi的匹配路徑。按照上述算法遞歸尋找M和T中路徑的匹配對直至M或T中的每條路徑都找到匹配路徑，同時匹配對的頂點相似度作為待判定答案的頂點相似度。

(3)待判定集合分值計算：在獲取待判定程序每個集合內路徑的匹配路徑后，運用式(3)計算每個集合的分值Gscore，其中每個頂點的相似度為Psimilar、Num為一個集合內總的頂點數(shù)量、Tscore為答案程序中匹配集合的分值

(3)

若集合內一些頂點已獲得分值，需通過式(4)計算該集合的分值：即已知頂點的分值和與未知頂點分數(shù)之和相加即為集合分值Gscore

(4)

其中，n代表已獲得分值的頂點總數(shù)，m代表未獲得分值的頂點總數(shù)、頂點的相似度為Psimilar、答案程序中集合和頂點的分值分別為Tscore和TPscore。

4 實 驗

從2017屆本校200位大一學生C語言課程的課后作業(yè)中，選取5道編程題作為檢測本文方法的實驗題目。編程題目1～5分別為“求π的值”、“猴子吃桃問題”、“求1！+2！+…100！”、“求圓環(huán)的面積”和“漢諾塔問題”，每題滿分均為25分，其中題目1考察的知識點為函數(shù)、表達式、循環(huán)結構，題目2考察的知識點為函數(shù)、循環(huán)結構，題目3考察的知識點為函數(shù)、表達式、循環(huán)結構，題目4考察的知識點為函數(shù)、輸入、輸出結構，題目5考察的知識點為函數(shù)、選擇結構。題目1的答案程序賦予表達式和循環(huán)結構知識點權重分別為8分和14分；題目2、題目3每個語句平分題目分值；題目4賦予函數(shù)、輸入/輸出知識點權重分別為15分、5分；題目5賦予函數(shù)、選擇結構知識點權重分別為10分、13分。

從200位學生中隨機抽取50名學生提交的程序作為實驗對象，通過搜集運用動態(tài)評分、統(tǒng)計屬性特征的結構規(guī)模評分、使用LCS算法[16]獲得語句相似度的程序靜態(tài)評分、采用本文策略的自動評分、人工評分5種方式對5道實驗題目評分點及評分的結果進行對比，驗證本文方法的有效性。

首先以“求π的值”(圖2)為例，結合人工評分方式、結構評分策略，使用式(5)計算50個學生采用結構規(guī)模、LCS、自動評分方式，找到知識點、語句被準確評分的誤差率。該題考察知識點為1個函數(shù)、4個表達式、1個while結構，并設置4個標有語句分值的區(qū)域。其中SeR表示誤差率、Psum表示人工評分時統(tǒng)計的數(shù)量、Ssum代表某種評分方式統(tǒng)計結果。由于動態(tài)評分是通過程序的運行結果評分，所以這里不對其進行誤差率計算。誤差率計算結果見表3

表3 知識點及語句被準確評分的誤差率計算結果/%

SeR=(|Psum-Ssum|)/Psum*100%

(5)

由表3可知，基于LCS的靜態(tài)評分采用LCS算法，匹配語句間相似度來判斷知識點正確性，因此會產(chǎn)生較高誤差率；結構規(guī)模評分則是考慮整個程序中包含的知識點數(shù)量與題目考查知識點的差距，該方法會計算注釋區(qū)域之外的知識點數(shù)量，且其并不考慮語句的內容，因此存在誤差；而自動評分是在語句分值范圍內獲取知識點，通過匹配路徑片段相似度獲取評分，所以其總體誤差率要優(yōu)于其它兩種評分方式。

其次，采用式(6)計算4種評分結果與人工評分之間的誤差率，結果見表4。其中ER表示評分的誤差率、Pscore表示人工評分結果、Sscore代表某種評分方式獲得的結果

表4 各種方式的評分結果對比/%

ER=(|Pscore-Score|)/Pscore*100%

(6)

由表4可知：LCS評分和自動評分誤差率接近，但該方法評分時采用LCS算法計算語句相似度，且沒有按照教師標注的語句分值進行評分，故其整體誤差率高于自動評分；而結構規(guī)模評分由于沒有考慮待判定程序的語句內容是否符合答案程序，使得誤差率高于自動評分；動態(tài)評分因其在待判定程序編寫錯誤，導致不能運行時會給予0分，故其誤差率高于自動評分。另外，在題目編號為2、3，設置語句平分答案程序分值時，自動評分和其余3種評分誤差率存在較小差距；題目編號為1、4、5，設置語句不同分值權重時，自動評分和其余3種評分誤差率存在的差距總體變大，故本文依據(jù)答案程序中設置的語句分值及PSDG實現(xiàn)的評分方法相比于其它方法明顯提升了評分準確度，更接近人工評分結果。

另外，通過實驗結果可以看到本文方法的評測結果和人工評測之間還存在一些差異。為尋找原因，對學生提交的程序進行了進一步檢查分析，發(fā)現(xiàn)凡是人工評判正確解答得滿分的程序，本文方法也為滿分；而對于存在一些錯誤的程序，本文方法評測結果和人工方法部分結果存在1-2分內的差異。究其原因，主要是當人工評測存在主觀性因素，當評分規(guī)則粒度較粗時評分尺度不是完全一致，另外對于多處類似細微錯誤按同一個錯誤扣分，而本文算法則是按照評分規(guī)則固定計算。

5 結束語

針對現(xiàn)有C程序靜態(tài)評分方法存在的缺陷，本文提出一種面向語句分值的C程序靜態(tài)評分方法，通過運用程序語句依賴圖描述源程序及程序中教師標注的語句分值，根據(jù)語句間的依賴關系和語句分值將答案及待判定程序劃分為路徑片段集合，對比兩者集合相似度完成待判定程序評分，評測結果接近人工評分，能更好滿足實際教學需要。但本文方法會受到答案程序的影響，當學生采用答案程序中不包含的正確解題思路時，不能夠正確識別和評分；另外，人工評分時對于程序中的多處類似錯誤一般僅扣除一次分值，而本文方法按實際出現(xiàn)次數(shù)進行扣分。這些問題需要在未來的研究中進行解決。