李欣潼

?

一種基于程序切片的C語言程序評(píng)測(cè)方法

李欣潼

（哈爾濱市第三高級(jí)中學(xué)校，黑龍江 哈爾濱 150001）

由于程序量大，當(dāng)前針對(duì)學(xué)生編寫程序的評(píng)測(cè)一般采用判斷其輸出結(jié)果的正誤進(jìn)行判定。這種評(píng)測(cè)方法機(jī)械，導(dǎo)致學(xué)生編程關(guān)注點(diǎn)偏頗，影響一些初學(xué)者的學(xué)習(xí)熱情。本文首先研究了程序切片技術(shù)的概念、分類及原理等內(nèi)容，然后在構(gòu)建了程序依賴圖以及擴(kuò)展后的系統(tǒng)依賴圖基礎(chǔ)上，設(shè)計(jì)了靜態(tài)程序切片的算法，進(jìn)而實(shí)現(xiàn)了依據(jù)不同的切片準(zhǔn)則的程序切片。最后通過對(duì)標(biāo)準(zhǔn)程序及學(xué)生程序的切片模塊的比較，在降低了程序的復(fù)雜度后完成了對(duì)學(xué)生程序的評(píng)測(cè)，通過實(shí)例證明了方法的有效，為初學(xué)者程序的評(píng)測(cè)提供了較客觀的評(píng)測(cè)方法。

程序切片；系統(tǒng)依賴圖；靜態(tài)切片；程序評(píng)測(cè)

0 引言

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

程序切片是一種分析和理解程序的技術(shù)，它通過分析程序的數(shù)據(jù)流和控制結(jié)構(gòu)依賴情況對(duì)源程序進(jìn)行分解，生成多個(gè)小片段，通過對(duì)片段的分析和處理實(shí)現(xiàn)對(duì)整個(gè)程序的理解和評(píng)測(cè)。此項(xiàng)技術(shù)最早由Marker Wister在其博士論文中最早提出[3]。本文以初學(xué)者的C語言程序?yàn)閷?duì)象，按照程序切片的算法及實(shí)現(xiàn)為主要內(nèi)容研究設(shè)計(jì)了一種前向靜態(tài)切片的方法，并據(jù)此針對(duì)C語言初學(xué)者編寫程序的語義完成了評(píng)測(cè)。

1 程序切片原理及流程

1.1 切片基本原理及分類

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

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

按照對(duì)數(shù)據(jù)流和程序流的分析方法不同分為靜態(tài)切片和動(dòng)態(tài)切片。如果切片是程序P中影響了興趣點(diǎn)的定義或使用的變量值的語句和謂詞構(gòu)成的集合則是靜態(tài)后向切片；而如果程序P中選出的是受興趣點(diǎn)變量的值影響的所有語句和謂詞組成的集合，則稱為靜態(tài)前向切片[5]。前向計(jì)算的動(dòng)態(tài)程序切片方法是根據(jù)興趣點(diǎn)直接動(dòng)態(tài)依賴節(jié)點(diǎn)計(jì)算興趣點(diǎn)的切片；后向分析的動(dòng)態(tài)程序切片方法通過回溯動(dòng)態(tài)依賴關(guān)系找到興趣點(diǎn)的直接和間接依賴節(jié)點(diǎn)集合生成興趣點(diǎn)切片[6]。靜態(tài)切片一般用于程序理解與軟件維護(hù)方面，動(dòng)態(tài)切片用在程序調(diào)試和測(cè)試方面。

在靜態(tài)切片和動(dòng)態(tài)切片之間還有一種被稱為條件切片的一種切片技術(shù)。它是通過添加一個(gè)條件來擴(kuò)展傳統(tǒng)的靜態(tài)切片準(zhǔn)則，即在進(jìn)行切片時(shí)只有滿足所添加的條件才會(huì)取出來形成的切片，不滿足條件的則不予理會(huì)。從而當(dāng)某條件對(duì)應(yīng)著的程序中的初始狀態(tài)參與切片時(shí)，只有滿足那些條件的輸入才會(huì)提取出來形成切片。

其他還有過程內(nèi)切片和過程間切片，面向?qū)ο蟮那衅取?/p>

1.2 程序切片的基本準(zhǔn)則

程切切片必須按照一定的切準(zhǔn)則進(jìn)行切片才有意義。對(duì)同一個(gè)程序進(jìn)行切片，不同的切片準(zhǔn)則對(duì)應(yīng)著不同的程序切片結(jié)果。按照程序切片類型的不同，一般有靜態(tài)切片準(zhǔn)則和動(dòng)態(tài)切片準(zhǔn)則之分。

（1）靜態(tài)切片準(zhǔn)則

靜態(tài)切片準(zhǔn)則一般被認(rèn)為是一個(gè)二元組（,），其中表示程序中的某個(gè)關(guān)注點(diǎn)即興趣點(diǎn)，它是程序中的一條語句，表示程序中變量集合的一個(gè)子集。對(duì)于給定的靜態(tài)切片標(biāo)準(zhǔn)，靜態(tài)切片由可能影響興趣點(diǎn)處中變量的所有語句組成。同時(shí)程序的切片還可以是任何一個(gè)對(duì)處興趣點(diǎn)中變量具有與原程序相同影響的計(jì)算機(jī)程序。

（2）動(dòng)態(tài)切片準(zhǔn)則

相應(yīng)地按照切片過程中考慮的不同條件或因素還有條件切片準(zhǔn)則，它是一個(gè)四元組，即在動(dòng)態(tài)切片的基礎(chǔ)上加入謂詞元，以及在此基礎(chǔ)上發(fā)展的考慮到程序中函數(shù)調(diào)用關(guān)系的五元組[7]及考慮函數(shù)調(diào)用的參數(shù)關(guān)系的六元組[8]。

本文面向C語言的初學(xué)者編寫的簡(jiǎn)單程序的評(píng)測(cè)，以二元和三元組為原則實(shí)現(xiàn)切片。

2 程序切片算法

2.1 與算法相關(guān)的定義[9]

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

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

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

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

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

定義3 設(shè)某個(gè)程序中的兩條語句1、2，某一變量為。如果滿足以下的三個(gè)條件，那么就稱語句2關(guān)于數(shù)據(jù)流直接依賴于語句1，簡(jiǎn)稱2數(shù)據(jù)依賴于1。

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

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

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

定義4設(shè)某個(gè)程序中的兩條語句1、2，如果語句1執(zhí)行的結(jié)果決定著語句2是否執(zhí)行，也就是說，當(dāng)程序執(zhí)行到語句1時(shí)，由控制條件的取值確定是否執(zhí)行語句2，那么就稱語句2控制依賴于語句1，簡(jiǎn)稱2控制依賴于1。

2.2 基于數(shù)據(jù)流方程的切片算法

根據(jù)上述定義可以通過解決數(shù)據(jù)流和控制流方程來計(jì)算程序切片。即從待切片程序的（控制流圖）產(chǎn)生，使用迭代過程計(jì)算中每個(gè)節(jié)點(diǎn)相關(guān)變量的集合。節(jié)點(diǎn)和變量結(jié)合切片的相關(guān)變量集合可以通過算法3.1得到。見圖1。

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

表1是針對(duì)源程序計(jì)算,的各相關(guān)集合。例中，∶；8∶1。切片節(jié)點(diǎn)集合為{1, 2, 6, 7, 8}。

基于數(shù)據(jù)流方程的算法最大的缺點(diǎn)就是必須為每個(gè)切片計(jì)算節(jié)點(diǎn)的相關(guān)集合，而這種數(shù)據(jù)信息不能被其他切片重用。

2.3 基于程序依賴圖的靜態(tài)切片技術(shù)

2.3.1 程序依賴圖

在程序中根據(jù)數(shù)據(jù)流和控制流的流向分別建立數(shù)據(jù)依賴子圖、控制依賴子圖，然后由兩者構(gòu)建程序依賴圖。控制流圖是程序依賴圖的重要組成部分，其中體現(xiàn)出程序中各種控制依賴關(guān)系和數(shù)據(jù)依賴關(guān)系，它是以語句或者語句塊作為圖中的節(jié)點(diǎn)，圖中的邊代表的是節(jié)點(diǎn)之間的控制流的流向。

表1 源程序p關(guān)于<8,a>各節(jié)點(diǎn)的relevant集合

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

由定義3.5得出，在中節(jié)點(diǎn)之間必然存在兩種關(guān)系的有向邊：數(shù)據(jù)依賴和控制依賴。數(shù)據(jù)依賴主要描述的是程序中賦值語句的賦值等號(hào)左邊數(shù)據(jù)依賴于賦值等號(hào)右邊的關(guān)系，而控制依賴則描述的是關(guān)于循環(huán)語句、條件語句等語句塊對(duì)嵌套在其中的語句的控制關(guān)系。

構(gòu)造程序依賴圖時(shí)，需要定義一個(gè)（入口）節(jié)點(diǎn)作為程序的開始，它和程序中的其它語句都是控制依賴的關(guān)系。

下面以程序3-1為例，然后構(gòu)建出相應(yīng)的程序依賴圖見圖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 系統(tǒng)依賴圖

在基礎(chǔ)上，中還增添了函數(shù)調(diào)用結(jié)點(diǎn)和參數(shù)傳遞結(jié)點(diǎn)，并用函數(shù)調(diào)用邊連結(jié)函數(shù)調(diào)用結(jié)點(diǎn)和被調(diào)用的函數(shù)入口結(jié)點(diǎn)，用傳遞依賴邊連結(jié)參數(shù)傳遞過程中具有依賴關(guān)系的結(jié)點(diǎn)。3.3.3節(jié)中說明系統(tǒng)依賴圖的構(gòu)建。

2.3.3 兩階段圖可達(dá)性算法

在構(gòu)建了程序依賴圖以及擴(kuò)展后的系統(tǒng)依賴圖基礎(chǔ)上，將實(shí)現(xiàn)靜態(tài)程序切片的計(jì)算方法。該方法分2個(gè)階段：

階段1：依據(jù)程序中依賴關(guān)系，構(gòu)建系統(tǒng)依 賴圖。

在此階段，對(duì)于包含多個(gè)子過程的程序，分別對(duì)每個(gè)子過程建立程序依賴圖，再根據(jù)程序調(diào)用構(gòu)建整體系統(tǒng)依賴圖。

階段2：依據(jù)系統(tǒng)依賴圖及切片準(zhǔn)則計(jì)算程序切片。

在這個(gè)階段中，遍歷系統(tǒng)依賴圖要采用兩階段圖可達(dá)性算法，具體步驟分2步：

（1）如果關(guān)于切片準(zhǔn)則<，計(jì)算切片，則從興趣點(diǎn)語句處逆向遍歷控制依賴、數(shù)據(jù)依賴等邊，得出節(jié)點(diǎn)集合；

以程序3-2（見圖4）為例計(jì)算關(guān)于切片準(zhǔn)則<8,>的靜態(tài)程序切片。首先構(gòu)建系統(tǒng)依賴圖，見圖6。然后按照算3-2（見圖5）求解關(guān)于切片準(zhǔn)則<8,>的切片程序，切片結(jié)果見程序3-3。程序中用*表示去除掉的代碼行，其他準(zhǔn)則的切片類同。

程序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）第一步從節(jié)點(diǎn)8出發(fā)，沿著控制依賴、call、parameter-in、summary邊進(jìn)行逆向遍歷，得到集合U1,U1={1, c, actual-out c}（2）U1中的每個(gè)u（）沿著各自的數(shù)據(jù)依賴、控制依賴、parameter-out、summary等邊進(jìn)行逆向遍歷，得到集合Vi。當(dāng)u=1時(shí)，記得到的節(jié)點(diǎn)集合為V0，則V0={entry}；當(dāng)u=c時(shí)，記得到的節(jié)點(diǎn)集合為V1，則V1={4,6}；當(dāng)u= actual-out c時(shí)，記得到的節(jié)點(diǎn)集合為V2，則V2={6,16}。={1,c,actual-out c,entry,4,6,16}（3）對(duì)每個(gè)u（）從u沿著控制依賴、數(shù)據(jù)依賴、parameter-out和summary等邊進(jìn)行逆向遍歷，得到節(jié)點(diǎn)Vi。同理可得：當(dāng)u=4時(shí)，記得到的節(jié)點(diǎn)集合為V3，則V3={1}；當(dāng)u=6時(shí)，記得到的節(jié)點(diǎn)集合為V4，則V4={1,a,b}；當(dāng)u= 16時(shí)，記得到的節(jié)點(diǎn)集合為V5，則V5={10,result}。U3={1,c, actual-out c, entry, 4, 6, 16, a, b, 10, result}。依此類推，得到U4，U5，…，Un，直到?jīng)]有得到新的節(jié)點(diǎn)為止。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 系統(tǒng)依賴圖

3 評(píng)測(cè)系統(tǒng)的實(shí)現(xiàn)

對(duì)學(xué)生程序的評(píng)測(cè)一直以來是只針對(duì)結(jié)果的對(duì)錯(cuò)來評(píng)判程序。但一個(gè)程序的正誤關(guān)鍵是它的邏輯結(jié)構(gòu)即算法[10]-[11]，僅通過程序運(yùn)行的結(jié)果來評(píng)測(cè)程序的對(duì)錯(cuò)對(duì)初學(xué)者來說容易使學(xué)生學(xué)習(xí)的關(guān)注點(diǎn)偏頗，機(jī)械的結(jié)果評(píng)判也會(huì)打擊學(xué)生的學(xué)習(xí)積極性[12]。本文研究設(shè)計(jì)在確定待測(cè)程序的標(biāo)準(zhǔn)化程序后，通過切片程序的比較來實(shí)現(xiàn)以邏輯結(jié)構(gòu)為決定性因素的評(píng)測(cè)系統(tǒng)。

面向?qū)W生程序的評(píng)測(cè)主要包括（1）程序是否編譯通過，有沒有警告；（2）程序的運(yùn)行結(jié)果是否正確；（3）程序是否存在抄襲的可能；（4）程序與模板程序進(jìn)行比較相似度，根據(jù)程序相似度進(jìn)行評(píng)測(cè)[13]等幾個(gè)個(gè)方面。本文在構(gòu)建了源程序的切片程序基礎(chǔ)上，利用Codeblocks13.1完成了學(xué)生程序的評(píng)測(cè)。系統(tǒng)面對(duì)初學(xué)者的程序采用靜態(tài)前向的切片算法，切片準(zhǔn)則為<,>，通過對(duì)程序的遍歷找出程序中定義變量的語句，通過對(duì)該語句和語句中定義的變量進(jìn)行切片。然后將學(xué)生不同準(zhǔn)則的切片程序與相應(yīng)的標(biāo)準(zhǔn)化程序的切片進(jìn)行比較，實(shí)現(xiàn)對(duì)學(xué)生程序邏輯結(jié)構(gòu)的評(píng)測(cè)。

初學(xué)者的程序大多比較簡(jiǎn)單，一般均由比較簡(jiǎn)單的幾個(gè)循環(huán)或選擇結(jié)構(gòu)構(gòu)成，邏輯結(jié)構(gòu)的差異主要體現(xiàn)在循環(huán)結(jié)構(gòu)和分支結(jié)構(gòu)[14]，所以對(duì)學(xué)生程序進(jìn)行評(píng)判的標(biāo)準(zhǔn)是在循環(huán)結(jié)構(gòu)和分支結(jié)構(gòu)方面的比較，評(píng)判標(biāo)準(zhǔn)如下：

（1）在一般情況下，當(dāng)要執(zhí)行一系列重復(fù)性步驟時(shí)，用循環(huán)結(jié)構(gòu)或循環(huán)結(jié)構(gòu)的嵌套要優(yōu)于用分支結(jié)構(gòu)和順序結(jié)構(gòu)。所以，當(dāng)學(xué)生程序的程序切片的循環(huán)結(jié)構(gòu)少于標(biāo)準(zhǔn)程序的程序切片時(shí)，證明學(xué)生程序在執(zhí)行該過程沒有標(biāo)準(zhǔn)程序邏輯好，需要改進(jìn)。

（2）當(dāng)標(biāo)準(zhǔn)程序的程序切片運(yùn)用有限個(gè)并列的循環(huán)結(jié)構(gòu)，而相應(yīng)的學(xué)生程序的程序切片卻用嵌套的循環(huán)結(jié)構(gòu)達(dá)成目的時(shí)，說明學(xué)生程序的邏輯結(jié)構(gòu)沒有標(biāo)準(zhǔn)程序邏輯好，需要改進(jìn)。

（3）當(dāng)標(biāo)準(zhǔn)程序的程序切片運(yùn)用有限個(gè)嵌套的循環(huán)結(jié)構(gòu)，而學(xué)生程序的程序切片卻用多余標(biāo)準(zhǔn)程序所含有的循環(huán)結(jié)構(gòu)個(gè)數(shù)，且嵌套的層數(shù)低于標(biāo)準(zhǔn)程序的程序切片。那么，學(xué)生程序的邏輯結(jié)構(gòu)沒有標(biāo)準(zhǔn)程序邏輯好，需要改進(jìn)。例如，一個(gè)嵌套三層循環(huán)結(jié)構(gòu)的程序切片要優(yōu)于四個(gè)嵌套兩層循環(huán)結(jié)構(gòu)的程序切片。

（4）分支結(jié)構(gòu)的嵌套在邏輯上要優(yōu)于分支結(jié)構(gòu)的羅列。因?yàn)榉种ЫY(jié)構(gòu)的嵌套體現(xiàn)了一種“分流”的思想。通過逐步的選擇來達(dá)到所要達(dá)到的目的，可以減少選擇次數(shù)。

其次，語言層次也能體現(xiàn)邏輯的完整性。對(duì)比學(xué)生程序的程序切片和標(biāo)準(zhǔn)程序的程序切片，如果相似性高則說明邏輯更完整。例如表2是標(biāo)準(zhǔn)化程序的切片結(jié)果與學(xué)生程序切片結(jié)果的比較。

表2 對(duì)程序進(jìn)行切片后結(jié)果

Tab.2 Result of program slicing

該程序切片是為了輸出一列三位數(shù)的個(gè)、十、百位的數(shù)字，雖然兩個(gè)切片都是達(dá)到了相同的目的且都為一個(gè)for循環(huán)結(jié)構(gòu)，但是學(xué)生切片只有一個(gè)語句與標(biāo)準(zhǔn)程序相同或相似?？梢院苊黠@的看出學(xué)生程序切片中的三條語句體現(xiàn)的邏輯思想不如標(biāo)準(zhǔn)程序，所以語言層次上存在差異。

根據(jù)邏輯結(jié)構(gòu)層次與語言層次的重要性不同，評(píng)測(cè)程序時(shí)，邏輯結(jié)構(gòu)占百分之七十的分?jǐn)?shù)，語句層次占百分之三十，滿分一百分。但是當(dāng)語句相似度高時(shí)，學(xué)生程序可能有很多無用語句或不必要的語句，所以還應(yīng)該把語句是否簡(jiǎn)潔作為一項(xiàng)評(píng)測(cè)標(biāo)準(zhǔn)，即：語句層次中語句相似度占25%，語句的簡(jiǎn)潔性（本文根據(jù)切片的行數(shù)判斷）占5%。

系統(tǒng)執(zhí)行時(shí)首先讀取標(biāo)準(zhǔn)化程序并對(duì)其進(jìn)行切片，見圖7，然后再讀取學(xué)生程序并對(duì)其進(jìn)行切片見圖8，最后通過評(píng)測(cè)輸出評(píng)測(cè)結(jié)果見圖9。

圖7 讀取標(biāo)準(zhǔn)化程序并完成切片

圖8 讀取學(xué)生程序并完成切片

圖9 評(píng)測(cè)結(jié)果

4 結(jié)論

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

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

[2] 汪友生. 電類非計(jì)算機(jī)專業(yè)C語言程序設(shè)計(jì)實(shí)驗(yàn)教學(xué)研究[J]. 軟件, 2018, 39(3): 99-101.

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

[4] 張新杰.程序切片技術(shù)研究及切片方案設(shè)計(jì).[D]電子科技大學(xué)碩士論文. 2017.

[5] 張勇翔, 李必信, 鄭國(guó)梁.程序切片技術(shù)的研究與應(yīng)用[J]. 計(jì)算機(jī)科學(xué)vol(27), 2000, 1: 31-35.

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

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

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

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

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

[11] 張新杰.程序切片技術(shù)研究及切片方案設(shè)計(jì).電子科技大學(xué)[D], 2017: 18-20.

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

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

[14] 焦華. 基礎(chǔ)編程的思考方法[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-)，女，主要研究方向：程序設(shè)計(jì)及方法。

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