一種面向數組C程序的靜態評分方法

舒新峰，何孝敏，郭芳瑤

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

C語言具備表達能力強、語法簡潔緊湊以及執行效率高等特點，已廣泛應用于操作系統和控制系統等各類底層軟件開發中，是高校信息類專業普遍開設的必修課程。為了提升學生C語言編程能力，許多高校在C語言程序設計課程教學中打破傳統的紙質作業和試卷的考核方式，引入“程序自動判定系統”對學生的作業和試卷進行計算機自動判定，通過考核手段改革引導學生強化C語言編寫程序能力訓練，并取得了良好的教學效果。數組是C語言廣泛使用的一種數據類型，操作數組的方法和程序表達方式的多樣性，給程序自動評分帶來了困難。

棧返回地址保護[1-2]、數據追蹤和插入檢測代碼[3]等動態評分方法可以應用于含有數組的C程序評分，但評測結果單一，只有0分或滿分，不能很好地滿足教學需要。靜態評分方法主要是將源程序轉化為系統依賴圖[4]、控制流[5]和抽象語法樹[6](Abstract Syntax Tree,AST)等中間表示形式，然后通過樹或圖的匹配算法[7]計算語句相似度進行評分。該方法雖然考慮了程序結構，但現有的中間表示形式不能準確表達程序語義及語句依賴關系，若數組空間大小不同或計算數組下標方式不同，則會導致誤判，降低了評分的準確性。文獻[8]將數組越界問題轉化為下標變量取值的范圍分析問題，利用抽象解釋技術[9]進行數組越界的判定，但該方法對循環語句中數組的檢測結果精度較低。

針對上述問題，擬提出一種面向數組C程序的靜態評分方法。首先，對待判定程序進行預處理，構造抽象語法樹，通過標準化算法消除程序的多樣性，獲取數組和變量的信息。其次，引入程序語句依賴圖[10](Program Statement Dependency Graph，PSDG)描述語句之間的依賴關系。然后，對學生編寫程序和答案程序的PSDG進行相似度匹配，通過數組下標訪問檢測和表達式等價識別方法修正誤判結點。最后，根據相似結點所占比例計算程序分值。

1 程序預處理

AST是程序的一種中間表示形式，可以準確表達程序的語法結構，存儲效率高，能方便地對其進行遍歷和操作[11]。對待判定程序進行預處理，首先將待判定程序轉化為AST，然后從AST中提取變量信息，便于后續使用，最后對程序進行標準化處理，消除因C程序表達多樣性對評分結果帶來的不利影響。

1.1 變量信息提取

通過GNU編譯套件(GNU Compiler Collection，GCC)將待判定程序轉化為AST。提取變量信息時，先定義好存儲變量信息的數據結構，其形式化定義如圖1所示。分別保存數組類型的變量Arr和其他類型的變量Var，vRange表示變量的取值范圍，size表示數組的空間大小，pSet表示引用數組的指針變量，其中包括指針變量p_id和表示數組下標的變量var_id。

圖1 變量存儲結構的形式化定義

提取變量及數組信息的算法步驟如下。

步驟1新建arrList和varList兩個表，分別用來存儲數組變量和其他變量的信息。

步驟2遍歷抽象語法樹，尋找函數的變量結點Attr，通過type對變量類型進行判斷：若為數組類型，則需記錄數組名arrName和空間大小size；若為其他類型的變量，則記錄變量的名稱name和初始值value。

步驟3將數組變量信息添加到arrList中，將其他變量信息添加到varList中，其中vRange的值為value。

1.2 數組標準化

C程序中可以通過下標或指針引用一個數組元素，當指針變量引用數組時，該指針就獲得了數組中某個元素的地址。雖然指針在程序中運行速度快，占用內存小，但在靜態分析程序時無法直接確定指針指向數組中的具體位置，因此需要將指針對數組的操作標準化為數組下標的形式。

令arr表示任意n(n≥1)維數組，p表示指向n維數組的指針變量，ei(1≤i≤n)為任意整數表達式，數組標準化算法具體步驟如下，其他語句的標準化方法可參照文獻[12]。

步驟1遍歷待判定程序的AST，對于形如p=& arr[e1]...[en]的語句，將指針變量p的id添加到數組arr的指針變量表pSet的p_id中，并定義n個新下標變量index_1，...，index_n，初始值分別為e1，...，en，將這些下標變量的信息存儲到變量表中，并將對應的id存入數組arr中pSet的var_id中。形如p=arr的語句做類似處理，區別在于所有下標變量初始值為0。

步驟2形如

p=*{...*[*(p+e1)+e2]+...}+en

的指針運算表達式，將其轉化為數組下標的運算形式

index_1=index_1+e1，...，index_n= index_n+en

步驟3形如

*{*[...(*(p+e1)+e2)+...]+en}

的表達式，將其替換為數組元素訪問的表達式

arr[index_1+e1] ...[index_n+en]

步驟4對于數組元素訪問表達式arr[e1]...[en]，將其每個不是整型變量的下標表達式ei替換為新的臨時變量ti，將ti加入變量表中，令ti=ei，并將原表達式替換為arr[t1]...[tn]。

以“冒泡排序”算法為例，源程序代碼如圖2所示。

圖2 “冒泡排序”算法源程序代碼

部分源程序轉換為標準化后的抽象語法樹結構如圖3所示。圖3中，arr表示數組類型，數組名為a，空間的大小為4。“p=a”表示指針變量p引用數組a，根據標準化規則定義了表示數組下標的變量index并賦初值為0。main函數循環結構中的單次表達式“i=0”被前提到循環之前，“*(p+i)”中首先定義臨時變量t，然后將指針變量運算p+i轉換為t= index+i，最后通過數組下標a[t]的方式訪問數組中的元素。

圖3 標準化后的部分程序語句的抽象語法樹

2 程序評分方法

AST能準確表示程序的結構，但無法精確表達程序語句間執行的依賴關系，為了解決該問題，引入PSDG描述待判定程序的結構。含有數組的C程序評分方法，首先，構建程序的PSDG[11]，將學生編寫程序和答案程序的PSDG進行匹配，劃分相似結點集合和不相似結點集合。其次，通過表達式等價識別的方法對PSDG匹配過程中產生的誤判結點進行消除，提高評分的準確性。最后，通過計算相似結點個數所占比例得到程序分值。

2.1 程序語句依賴圖匹配

圖匹配[13-14]的過程主要是圖相似度計算的問題，PSDG為有向圖，以待判定程序stuPSDG和答案程序teaPSDG的函數名結點main為起始點，通過圖同構算法[15]和樹的編輯距離算法進行結點間的匹配。PSDG匹配算法步驟如下。

步驟1消除變量名多樣性。首先，對程序中的變量按照類型進行劃分。其次，在程序語句依賴圖中，對學生編寫程序和答案程序按照變量類型進行結點間的匹配，若結點中所存儲語句的結構相同，則將兩個變量以二元組的形式加入集合varSet中，構成映射關系，表示這兩個變量可以相互替換。最后，將沒有映射關系的變量統一命名為unRecVar。

步驟2新建stuSet和teaSet兩個集合，分別以學生編寫程序和答案程序的函數名結點main作為起始點，找到對應的所有鄰點并分別添加到集合stuSet和teaSet中。

步驟3將stuSet中的每個結點與teaSet中的所有結點相匹配，執行步驟4。stuSet中的所有結點都匹配完成后，執行步驟5。

步驟4匹配結點類型nodeType，若不同，則結束步驟4，否則，將結點中的變量按照varSet中變量之間的映射關系替換為teaSet中的變量。通過樹的編輯距離算法對結點中的expTree進行匹配。若相似，則將兩個結點以二元組的形式添加到集合sameSet中，否則，結束步驟4。

步驟5分別以stuSet中的結點stuNode和與之匹配的teaSet中的結點teaNode為起始點，深度優先搜索獲取待匹配結點newstuNode和newteaNode，執行步驟4。若兩個結點不匹配，則回溯。

步驟6將stuPSDG 中與teaPSDG不匹配的結點添加到unsameSet中。

2.2 誤判修正

在PSDG的匹配過程中，若待判定程序和答案程序中部分語句語義相同，表示方式不同，則會造成結點誤判，導致評分結果有較大的誤差。例如，在“冒泡排序”算法中，若main函數調用sort函數時傳遞的第二個參數的值為3，則在sort函數中兩個循環語句的條件控制表達式就分別變為“i

為解決該問題，首先分別以待判定程序stuPSDG和答案程序teaPSDG中含有數組的表達式結點為起始點，通過回溯進行變量替換，最終替換后的語句為關于數組下標變量的表達式。然后引入區間計算[16]的方法對變量取值范圍進行運算，判斷數組下標的取值范圍是否超出數組空間大小，若未超出，則對含有數組下標變量的表達式進行等價識別，修正誤判結點。定義var為任意變量，Expr為任意表達式，誤判修正步驟如下。

步驟1遍歷sameSet，找到含有數組表達式的結點，分別在stuPSDG和teaPSDG中確定其位置，以該結點為起始點回溯，對于形如var=Exp的語句，將數組下標表達式中的非下標變量var替換為Exp的形式，并對常量表達式進行計算，將替換的結點添加到repSet中，直到函數名結點為止，替換后的表達式表示為stuExpr和teaExpr。若含有復合語句，則從最內層開始進行表達式的替換，直到最外層的名稱結點YES/NO為止。

步驟2確定取值范圍。首先從變量表varList中獲取結點中變量當前的取值范圍valueRange，然后通過區間運算的方法對stuExpr中下標變量的取值范圍進行計算并更新，最后通過步驟3判斷取值范圍是否合法。

步驟3在arrList中獲取當前數組的長度size，與下標的取值范圍vRange進行比較，若vRange未超過size，則執行步驟4，否則結束步驟3。

步驟4通過樹的編輯距離算法比較stuExpr和teaExpr兩者的相似度，若相同，表示stuExpr和teaExpr等價，執行步驟5，否則結束步驟4。

步驟5在unsameSet中查找是否存在repSet中的結點，若存在，則將其從unsameSet中刪除，再添加到sameSet中。

2.3 評分

學生編寫程序和答案程序通過程序語句依賴圖匹配算法進行匹配后，將學生編寫程序的PSDG中的結點劃分為相似結點集合sameSet和不相似結點集合unsameSet，通過表達式等價識別的方法對unsameSet中的誤判結點進行修正，最終，學生編寫程序得分由相似結點集合中的結點個數sameNodeNum除以答案程序的PSDG中的結點個數teaPSDGNum，再乘以總分值Score得出。

3 實驗

選取某高校2019屆300位本科生的3道C程序作業題目作為實驗對象，第一題為數組元素排序，第二題為環形打印二維數組，第三題為打印出所有的水仙花數，每道題目總分為10分，分別使用所提方法、北京大學程序在線評測系統(Peking University Online Judge，POJ)和基于AST的自動評分方法[13]計算學生編寫程序得分，并與人工評分結果進行對比，驗證所提方法的有效性。每道題目的平均分值如表1所示。

表1 不同方法對每道題目評分的平均分值

由表1可知，POJ需要編譯運行程序，學生編寫程序得分只有0分和10分兩種形式，平均分值與人工評分的結果相差較大。基于AST的自動評分方法能夠表達程序的語法結構，通過計算學生編寫程序和答案程序的抽象語法樹相似度進行評分，該方法在對不含有數組的程序評分時，評分結果與人工評分結果接近，但在對含有數組的程序進行評分時，評分結果與人工評分結果誤差較大。所提方法首先通過PSDG精確表達了程序語句之間的依賴關系，然后通過區間運算和表達式等價識別的方法誤判結點進行了修正，提高了評分的準確度，更接近人工評分結果。

以第二題為例，隨機抽取50位學生的試題評測結果，計算所提方法和基于AST的程序自動評分方法與人工評分結果的誤差率，計算表達式為

其中：E表示誤差率；S表示使用不同方法評測學生編寫程序的評分結果；T表示人工評分結果。評分誤差率分布如表2所示。

表2 評分誤差率分布對比

由表2可知，基于AST的評分方法的誤差率主要集中在5%～15%之間，該區間的人數占總人數72%，且存在評分結果誤差率為25%以上的試題，誤差較高。這是因為，首先，該評分方法主要是根據學生編寫程序和答案程序AST的相似度進行評分，沒有考慮到學生編寫程序中所定義的數組空間大小的不同及表達式的多樣性表示給程序評分帶來的問題。其次，沒有考慮到因程序語句順序不同給評分結果帶來的影響。所提方法的誤差率分布在0～25%之間，其中，誤差率在10%以上的試題數量占總試題數量的18%，通過查看該部分試題，發現主要是因為學生只編寫了部分關鍵程序，人工評分時會給與一定的分值，而所提方法依賴于程序語句依賴圖的匹配和數組下標訪問檢測的結果，沒有考慮程序語句分值的權重，導致評分結果與人工之間存在較大差異，82%的試題的誤差率在0～10%之間，接近人工評分結果。因此，所提方法與POJ和基于AST的程序評分方法相比，評分結果的準確度更高。

4 結語

面向數組C程序的靜態評分方法，通過對程序標準化處理，利用區間計算和表達式等價識別的方法將PSDG匹配過程中產生的誤判結點進行了修正，減小了程序表達的多樣性。實驗結果表明，與現有的評分方法相比，該方法的評測結果更加接近人工評分，能更好地滿足實際教學需要。