一種基于程序切片的C語言程序評測方法

李欣潼

?

一種基于程序切片的C語言程序評測方法

李欣潼

（哈爾濱市第三高級中學校，黑龍江 哈爾濱 150001）

由于程序量大，當前針對學生編寫程序的評測一般采用判斷其輸出結果的正誤進行判定。這種評測方法機械，導致學生編程關注點偏頗，影響一些初學者的學習熱情。本文首先研究了程序切片技術的概念、分類及原理等內容，然后在構建了程序依賴圖以及擴展后的系統依賴圖基礎上，設計了靜態程序切片的算法，進而實現了依據不同的切片準則的程序切片。最后通過對標準程序及學生程序的切片模塊的比較，在降低了程序的復雜度后完成了對學生程序的評測，通過實例證明了方法的有效，為初學者程序的評測提供了較客觀的評測方法。

程序切片；系統依賴圖；靜態切片；程序評測

0 引言

C語言作為中學生信息競賽的官方語言，以及許多高等學校計算機及相關專業學生入門必修課，它在學生學習經歷中起著至關重要的作用。初學伊始課程的考核方式影響著學生學習的動力和熱情，但由于C語言程序的靈活性，即使同樣的問題，不同人編寫的程序也會有比較大的差異，這樣導致通過自動的語義和程序結構的評判方式困難，而人為評判的工作量又很大。現階段針對學生的程序評測方法大多是依據輸出結果評測，因此結果只有正確和錯誤之分。對于參加競賽的學生來說，針對其邏輯思想和思維的嚴密以及動手實踐能力方面的考核是主要的考核內容，所以這種方式作為競賽的結果評測比較適宜，但是作為學生課程學習的評測并不很恰當，特別是對于初學計算機編程的同學。初學者學習編程首先應該重視的是學生的邏輯思維能力，但在學生代碼只有少數錯誤而最后答案不正確時，如果通過評測系統判為零分，對學生也不很公正，更可能打擊學生的學習積極性[1-2]。

程序切片是一種分析和理解程序的技術，它通過分析程序的數據流和控制結構依賴情況對源程序進行分解，生成多個小片段，通過對片段的分析和處理實現對整個程序的理解和評測。此項技術最早由Marker Wister在其博士論文中最早提出[3]。本文以初學者的C語言程序為對象，按照程序切片的算法及實現為主要內容研究設計了一種前向靜態切片的方法，并據此針對C語言初學者編寫程序的語義完成了評測。

1 程序切片原理及流程

1.1 切片基本原理及分類

程序切片是指將一個程序中用戶所感興趣的所有代碼都抽取出來形成的嶄新程序的方法，這些代碼根據確定的興趣點進行選取，因此能夠間接或直接地影響到這個興趣點處變量的值。程序切片用符號表示的定義為二元組(,)，即影響變量在程序P中某一點狀態的所有語句和謂詞的集合。程序切片實際上是得到了程序P的一個有效子集，而省略了其他不相關代碼。

切片方式不同程序切片分為不同的種類[4]。根據切片方向的不同，可以分為前向切片和后向切片。如果程序切片是由程序P中受到某個興趣點處變量的值影響的所有控制語句組成的集合，那么稱為前向切片；相反的，若程序切片是由程序P中能夠影響到某個興趣點處變量的值的所有控制語句組成的集合則稱為后向切片。由定義可知，前向切片是由興趣點處語句之后的語句組成的集合，后向切片得到的代碼是由興趣點處語句之前的語句組成的集合。

按照對數據流和程序流的分析方法不同分為靜態切片和動態切片。如果切片是程序P中影響了興趣點的定義或使用的變量值的語句和謂詞構成的集合則是靜態后向切片；而如果程序P中選出的是受興趣點變量的值影響的所有語句和謂詞組成的集合，則稱為靜態前向切片[5]。前向計算的動態程序切片方法是根據興趣點直接動態依賴節點計算興趣點的切片；后向分析的動態程序切片方法通過回溯動態依賴關系找到興趣點的直接和間接依賴節點集合生成興趣點切片[6]。靜態切片一般用于程序理解與軟件維護方面，動態切片用在程序調試和測試方面。

在靜態切片和動態切片之間還有一種被稱為條件切片的一種切片技術。它是通過添加一個條件來擴展傳統的靜態切片準則，即在進行切片時只有滿足所添加的條件才會取出來形成的切片，不滿足條件的則不予理會。從而當某條件對應著的程序中的初始狀態參與切片時，只有滿足那些條件的輸入才會提取出來形成切片。

其他還有過程內切片和過程間切片，面向對象的切片等。

1.2 程序切片的基本準則

程切切片必須按照一定的切準則進行切片才有意義。對同一個程序進行切片，不同的切片準則對應著不同的程序切片結果。按照程序切片類型的不同，一般有靜態切片準則和動態切片準則之分。

（1）靜態切片準則

靜態切片準則一般被認為是一個二元組（,），其中表示程序中的某個關注點即興趣點，它是程序中的一條語句，表示程序中變量集合的一個子集。對于給定的靜態切片標準，靜態切片由可能影響興趣點處中變量的所有語句組成。同時程序的切片還可以是任何一個對處興趣點中變量具有與原程序相同影響的計算機程序。

（2）動態切片準則

相應地按照切片過程中考慮的不同條件或因素還有條件切片準則，它是一個四元組，即在動態切片的基礎上加入謂詞元，以及在此基礎上發展的考慮到程序中函數調用關系的五元組[7]及考慮函數調用的參數關系的六元組[8]。

本文面向C語言的初學者編寫的簡單程序的評測，以二元和三元組為原則實現切片。

2 程序切片算法

2.1 與算法相關的定義[9]

靜態切片算法有很多種，比如基于數據流的切片算法、基于信息流關系的算法、基于依賴圖的可達性算法、無定型切片算法、有條件切片算法等[3]。這些算法大致可以分成三類算法：基于數據流方程的切片算法，基于信息流關系的算法和基于依賴圖的圖形可達性算法。

這些算法涉及到如下幾個概念，定義如下：

定義2 如果程序中的某一語句設定為，那么就定義：

()={|為程序執行語句時，被語句引用的變量}

()={|為程序執行語句時，在語句中出現的定義性變量}

定義3 設某個程序中的兩條語句1、2，某一變量為。如果滿足以下的三個條件，那么就稱語句2關于數據流直接依賴于語句1，簡稱2數據依賴于1。

（1）變量在語句1中進行了定義，則∈()；

（2）語句2執行時引用了變量，則∈()；

（3）程序中之間存在一條執行路徑，且在此路徑上，其他語句未對變量重新進行定義。

定義4設某個程序中的兩條語句1、2，如果語句1執行的結果決定著語句2是否執行，也就是說，當程序執行到語句1時，由控制條件的取值確定是否執行語句2，那么就稱語句2控制依賴于語句1，簡稱2控制依賴于1。

2.2 基于數據流方程的切片算法

根據上述定義可以通過解決數據流和控制流方程來計算程序切片。即從待切片程序的（控制流圖）產生，使用迭代過程計算中每個節點相關變量的集合。節點和變量結合切片的相關變量集合可以通過算法3.1得到。見圖1。

算法3.1：（1）初始化所有節點的相關集合，均為空集合；（2）把變量集合V中的所有變量放入relevant(n);（relevant(n)就是每個節點n的數據流信息）（3）對n的直接前驅m的relevant(m)的定義如下:relevant(m)=relevant(n)-def(m); /*排除所有在m點的定義性變量*/if(relevant(n)∩def(m)≠?) /*如果在m點定義了n中的相關的變量*/{ relevant(m)=relevant(m)∪ref(m); /*包含進m點的引用性變量*/因為節點m定義了一個在節點n引用的相關變量，將節點m包含進切片內 }（4）在CFG中對m點的直接前驅重復操作（3），直到到達n的初始化集合或相關變量集合relevant(n)為空。

表1是針對源程序計算,的各相關集合。例中，∶；8∶1。切片節點集合為{1, 2, 6, 7, 8}。

基于數據流方程的算法最大的缺點就是必須為每個切片計算節點的相關集合，而這種數據信息不能被其他切片重用。

2.3 基于程序依賴圖的靜態切片技術

2.3.1 程序依賴圖

在程序中根據數據流和控制流的流向分別建立數據依賴子圖、控制依賴子圖，然后由兩者構建程序依賴圖。控制流圖是程序依賴圖的重要組成部分，其中體現出程序中各種控制依賴關系和數據依賴關系，它是以語句或者語句塊作為圖中的節點，圖中的邊代表的是節點之間的控制流的流向。

表1 源程序p關于<8,a>各節點的relevant集合

Tab.1 The relevant set of source program p about node of <8,a>

由定義3.5得出，在中節點之間必然存在兩種關系的有向邊：數據依賴和控制依賴。數據依賴主要描述的是程序中賦值語句的賦值等號左邊數據依賴于賦值等號右邊的關系，而控制依賴則描述的是關于循環語句、條件語句等語句塊對嵌套在其中的語句的控制關系。

構造程序依賴圖時，需要定義一個（入口）節點作為程序的開始，它和程序中的其它語句都是控制依賴的關系。

下面以程序3-1為例，然后構建出相應的程序依賴圖見圖2。

程序3-1：

程序3-1：1 int main(){2 int j=0;3 int av=0;4 while (j<10){5 if(j%2==0)6 av=j/2;7 else 8 av=j/2+1;9 j++; }10 printf(“%d”,av);11 return 0;}

圖3 程序3-1的程序依賴圖

2.3.2 系統依賴圖

在基礎上，中還增添了函數調用結點和參數傳遞結點，并用函數調用邊連結函數調用結點和被調用的函數入口結點，用傳遞依賴邊連結參數傳遞過程中具有依賴關系的結點。3.3.3節中說明系統依賴圖的構建。

2.3.3 兩階段圖可達性算法

在構建了程序依賴圖以及擴展后的系統依賴圖基礎上，將實現靜態程序切片的計算方法。該方法分2個階段：

階段1：依據程序中依賴關系，構建系統依 賴圖。

在此階段，對于包含多個子過程的程序，分別對每個子過程建立程序依賴圖，再根據程序調用構建整體系統依賴圖。

階段2：依據系統依賴圖及切片準則計算程序切片。

在這個階段中，遍歷系統依賴圖要采用兩階段圖可達性算法，具體步驟分2步：

（1）如果關于切片準則<，計算切片，則從興趣點語句處逆向遍歷控制依賴、數據依賴等邊，得出節點集合；

以程序3-2（見圖4）為例計算關于切片準則<8,>的靜態程序切片。首先構建系統依賴圖，見圖6。然后按照算3-2（見圖5）求解關于切片準則<8,>的切片程序，切片結果見程序3-3。程序中用*表示去除掉的代碼行，其他準則的切片類同。

程序3-2：1 main(){1 int a=1;2 int b=2;3 int c;4 int d;5 c=avg(a,b);6 d=add(a,b);7 printf(“%d”,c);8 printf(“%d”,d); }9 int avg(int x,int y){10 int result;11 if(x==y)12 result=(x+y)/2;13 else14 result=x;15 return result; }16 int add(int m,int n){17 int sum=0;18 if(m!=n)19 sum=m+n;20 else21 sum=2*m;22 return sum; }程序3-3：1 main(){1 int a=1;2 int b=2;3 int c;4 int d;5 c=avg(a,b);6 *******7 printf(“%d”,c);8 *******9 int avg(int x,int y){10 int result;11 if(x==y)12 result=(x+y)/2;13 else14 result=x;15 return result;}16 ******17 ******18 ******19 ******20 ******21 ******22 ******

算法3-2：（1）第一步從節點8出發，沿著控制依賴、call、parameter-in、summary邊進行逆向遍歷，得到集合U1,U1={1, c, actual-out c}（2）U1中的每個u（）沿著各自的數據依賴、控制依賴、parameter-out、summary等邊進行逆向遍歷，得到集合Vi。當u=1時，記得到的節點集合為V0，則V0={entry}；當u=c時，記得到的節點集合為V1，則V1={4,6}；當u= actual-out c時，記得到的節點集合為V2，則V2={6,16}。={1,c,actual-out c,entry,4,6,16}（3）對每個u（）從u沿著控制依賴、數據依賴、parameter-out和summary等邊進行逆向遍歷，得到節點Vi。同理可得：當u=4時，記得到的節點集合為V3，則V3={1}；當u=6時，記得到的節點集合為V4，則V4={1,a,b}；當u= 16時，記得到的節點集合為V5，則V5={10,result}。U3={1,c, actual-out c, entry, 4, 6, 16, a, b, 10, result}。依此類推，得到U4，U5，…，Un，直到沒有得到新的節點為止。V={8, entry, c, actual-out c, 1, 4, 6, 16, a, b, 10, result, 2, 3, 11, 13, 15, 12, 14, x, y, formal-in x, formal-in y, actual-in a, actual-in b}

圖6 系統依賴圖

3 評測系統的實現

對學生程序的評測一直以來是只針對結果的對錯來評判程序。但一個程序的正誤關鍵是它的邏輯結構即算法[10]-[11]，僅通過程序運行的結果來評測程序的對錯對初學者來說容易使學生學習的關注點偏頗，機械的結果評判也會打擊學生的學習積極性[12]。本文研究設計在確定待測程序的標準化程序后，通過切片程序的比較來實現以邏輯結構為決定性因素的評測系統。

面向學生程序的評測主要包括（1）程序是否編譯通過，有沒有警告；（2）程序的運行結果是否正確；（3）程序是否存在抄襲的可能；（4）程序與模板程序進行比較相似度，根據程序相似度進行評測[13]等幾個個方面。本文在構建了源程序的切片程序基礎上，利用Codeblocks13.1完成了學生程序的評測。系統面對初學者的程序采用靜態前向的切片算法，切片準則為<,>，通過對程序的遍歷找出程序中定義變量的語句，通過對該語句和語句中定義的變量進行切片。然后將學生不同準則的切片程序與相應的標準化程序的切片進行比較，實現對學生程序邏輯結構的評測。

初學者的程序大多比較簡單，一般均由比較簡單的幾個循環或選擇結構構成，邏輯結構的差異主要體現在循環結構和分支結構[14]，所以對學生程序進行評判的標準是在循環結構和分支結構方面的比較，評判標準如下：

（1）在一般情況下，當要執行一系列重復性步驟時，用循環結構或循環結構的嵌套要優于用分支結構和順序結構。所以，當學生程序的程序切片的循環結構少于標準程序的程序切片時，證明學生程序在執行該過程沒有標準程序邏輯好，需要改進。

（2）當標準程序的程序切片運用有限個并列的循環結構，而相應的學生程序的程序切片卻用嵌套的循環結構達成目的時，說明學生程序的邏輯結構沒有標準程序邏輯好，需要改進。

（3）當標準程序的程序切片運用有限個嵌套的循環結構，而學生程序的程序切片卻用多余標準程序所含有的循環結構個數，且嵌套的層數低于標準程序的程序切片。那么，學生程序的邏輯結構沒有標準程序邏輯好，需要改進。例如，一個嵌套三層循環結構的程序切片要優于四個嵌套兩層循環結構的程序切片。

（4）分支結構的嵌套在邏輯上要優于分支結構的羅列。因為分支結構的嵌套體現了一種“分流”的思想。通過逐步的選擇來達到所要達到的目的，可以減少選擇次數。

其次，語言層次也能體現邏輯的完整性。對比學生程序的程序切片和標準程序的程序切片，如果相似性高則說明邏輯更完整。例如表2是標準化程序的切片結果與學生程序切片結果的比較。

表2 對程序進行切片后結果

Tab.2 Result of program slicing

該程序切片是為了輸出一列三位數的個、十、百位的數字，雖然兩個切片都是達到了相同的目的且都為一個for循環結構，但是學生切片只有一個語句與標準程序相同或相似。可以很明顯的看出學生程序切片中的三條語句體現的邏輯思想不如標準程序，所以語言層次上存在差異。

根據邏輯結構層次與語言層次的重要性不同，評測程序時，邏輯結構占百分之七十的分數，語句層次占百分之三十，滿分一百分。但是當語句相似度高時，學生程序可能有很多無用語句或不必要的語句，所以還應該把語句是否簡潔作為一項評測標準，即：語句層次中語句相似度占25%，語句的簡潔性（本文根據切片的行數判斷）占5%。

系統執行時首先讀取標準化程序并對其進行切片，見圖7，然后再讀取學生程序并對其進行切片見圖8，最后通過評測輸出評測結果見圖9。

圖7 讀取標準化程序并完成切片

圖8 讀取學生程序并完成切片

圖9 評測結果

4 結論

本文在研究了程序切片的概念分類基礎上，重點研究了程序切片的算法，通過構建程序依賴圖和系統依賴圖，進而實現程序的切片。在學生初學編程時，代碼量少，邏輯結構比較簡單的情況下，通過前向靜態的程序切片方法完成源程序的切片。在分別對標準化程序和學生程序切片后，將切片程序形成代碼塊，通過代碼塊之間的邏輯結構及邏輯結構的語言層次進行對比，得到了評測結果，也可以是學生根據結果及參考標準化程序找出差距改進自己的程序。本文面向初學C語言的學生程序的評測過程和方法做了實驗探索，但對C語言程序詞法、語法分析過程還欠缺完整性，對前導文件名、預處理符號以及程序注釋文字等處理沒考慮進去；雖然采用模塊化處理對程序進行切片，但將語句及函數之間的依賴忽略了，這些都將是今后學習需要解決的問題。

[1] 施鍵蘭, 黃文秀. 程序設計類課程中的教改研究[J]. 軟件, 2016, 37(3): 34-35.

[2] 汪友生. 電類非計算機專業C語言程序設計實驗教學研究[J]. 軟件, 2018, 39(3): 99-101.

[3] 李必信, 鄭國梁, 王云峰, 李宣東.一種分析和理解程序的方法——程序切片. 計算機研究與發展[J]vol(37), 2000, 3: 284-291.

[4] 張新杰.程序切片技術研究及切片方案設計.[D]電子科技大學碩士論文. 2017.

[5] 張勇翔, 李必信, 鄭國梁.程序切片技術的研究與應用[J]. 計算機科學vol(27), 2000, 1: 31-35.

[6] 張龍杰, 謝曉方, 袁勝智.一種改進的靜態程序切片算法[J].計算機應用. vol(29), 2009, 3: 705-711.

[7] 王興亞, 姜淑娟, 鞠小林, 邵浩然.一種基于前向計算的動態程序切片方法.計算機科學[J]. vol(41). 2014, 1: 250-253.

[8] 蘇小紅, 龔丹丹, 王甜甜, 馬培軍.一種新的過程間靜態切片快速算法. 哈爾濱工業大學學報[J]. vol(47), 2015, 5: 26-31.

[9] 張軍, 劉鋒, 馬竹娟, 朱二周.改進型程序切片方法的測試需求約簡技術研究.傳感器與微系統[J]. vol.(36). 2017, 9: 17-21, 24.

[10] 王云. 《軟件測試》課程教學探索與思考[J]. 軟件, 2015, 36(7): 129-131.

[11] 張新杰.程序切片技術研究及切片方案設計.電子科技大學[D], 2017: 18-20.

[12] 吳成慶, 孫玉濤. 學生在線考試系統軟件測試[J]. 軟件, 2015, 36(6): 26-30.

[13] 修曉杰, 唐紅軍.C語言程序評測方法研究.杭州電子科技大學學報[J]. vol(32). 2012, 6: 57-60.

[14] 焦華. 基礎編程的思考方法[J]. 軟件, 2018, 39(3): 57-62.

An Method for C-Language Program Assessment Bease on Program Slicing

LI Xin-tong

(Harbin No.3 senior middle school, Heilongjiang Province, Harbin 150001)

The evaluation of students' programs are generally based on their output at present because of the large amount of program..This method of evaluation is unreliable, which leads students to be biased in program studying and loss their confidence for some beginners. In this paper, the concept, classification and principle of program slicing are studied. Then, the algorithm of static program slicing is designed based on the program dependency graph and the extended system dependency graph, so the program slicing is realized take advantage of different slicing criteria. The method has reduced the complexity in assessment of student’s program by decomposing. It provides a more reliable way to grade the beginners' program.

Program slicing; System dependence graphic; Static slicing; Program assessment

TP311

A

10.3969/j.issn.1003-6970.2018.10.021

李欣潼(2001-)，女，主要研究方向：程序設計及方法。

李欣潼. 一種基于程序切片的C語言程序評測方法[J]. 軟件，2018，39（10）：105-110