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

李欣潼

?

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

李欣潼

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

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

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

0 引言

C語(yǔ)言作為中學(xué)生信息競(jìng)賽的官方語(yǔ)言，以及許多高等學(xué)校計(jì)算機(jī)及相關(guān)專(zhuān)業(yè)學(xué)生入門(mén)必修課，它在學(xué)生學(xué)習(xí)經(jīng)歷中起著至關(guān)重要的作用。初學(xué)伊始課程的考核方式影響著學(xué)生學(xué)習(xí)的動(dòng)力和熱情，但由于C語(yǔ)言程序的靈活性，即使同樣的問(wèn)題，不同人編寫(xiě)的程序也會(huì)有比較大的差異，這樣導(dǎo)致通過(guò)自動(dòng)的語(yǔ)義和程序結(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é)生來(lái)說(shuō)，針對(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í)，如果通過(guò)評(píng)測(cè)系統(tǒng)判為零分，對(duì)學(xué)生也不很公正，更可能打擊學(xué)生的學(xué)習(xí)積極性[1-2]。

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

1 程序切片原理及流程

1.1 切片基本原理及分類(lèi)

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

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

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

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

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

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

程切切片必須按照一定的切準(zhǔn)則進(jìn)行切片才有意義。對(duì)同一個(gè)程序進(jìn)行切片，不同的切片準(zhǔn)則對(duì)應(yīng)著不同的程序切片結(jié)果。按照程序切片類(lèi)型的不同，一般有靜態(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)，它是程序中的一條語(yǔ)句，表示程序中變量集合的一個(gè)子集。對(duì)于給定的靜態(tài)切片標(biāo)準(zhǔn)，靜態(tài)切片由可能影響興趣點(diǎn)處中變量的所有語(yǔ)句組成。同時(shí)程序的切片還可以是任何一個(gè)對(duì)處興趣點(diǎn)中變量具有與原程序相同影響的計(jì)算機(jī)程序。

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

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

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

2 程序切片算法

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

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

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

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

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

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

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

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

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

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

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

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

根據(jù)上述定義可以通過(guò)解決數(shù)據(jù)流和控制流方程來(lái)計(jì)算程序切片。即從待切片程序的（控制流圖）產(chǎn)生，使用迭代過(guò)程計(jì)算中每個(gè)節(jié)點(diǎn)相關(guān)變量的集合。節(jié)點(diǎn)和變量結(jié)合切片的相關(guān)變量集合可以通過(guò)算法3.1得到。見(jiàn)圖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 基于程序依賴(lài)圖的靜態(tài)切片技術(shù)

2.3.1 程序依賴(lài)圖

在程序中根據(jù)數(shù)據(jù)流和控制流的流向分別建立數(shù)據(jù)依賴(lài)子圖、控制依賴(lài)子圖，然后由兩者構(gòu)建程序依賴(lài)圖。控制流圖是程序依賴(lài)圖的重要組成部分，其中體現(xiàn)出程序中各種控制依賴(lài)關(guān)系和數(shù)據(jù)依賴(lài)關(guān)系，它是以語(yǔ)句或者語(yǔ)句塊作為圖中的節(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ù)依賴(lài)和控制依賴(lài)。數(shù)據(jù)依賴(lài)主要描述的是程序中賦值語(yǔ)句的賦值等號(hào)左邊數(shù)據(jù)依賴(lài)于賦值等號(hào)右邊的關(guān)系，而控制依賴(lài)則描述的是關(guān)于循環(huán)語(yǔ)句、條件語(yǔ)句等語(yǔ)句塊對(duì)嵌套在其中的語(yǔ)句的控制關(guān)系。

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

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

2.3.2 系統(tǒng)依賴(lài)圖

在基礎(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)，用傳遞依賴(lài)邊連結(jié)參數(shù)傳遞過(guò)程中具有依賴(lài)關(guān)系的結(jié)點(diǎn)。3.3.3節(jié)中說(shuō)明系統(tǒng)依賴(lài)圖的構(gòu)建。

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

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

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

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

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

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

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

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

程序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ā)，沿著控制依賴(lài)、call、parameter-in、summary邊進(jìn)行逆向遍歷，得到集合U1,U1={1, c, actual-out c}（2）U1中的每個(gè)u（）沿著各自的數(shù)據(jù)依賴(lài)、控制依賴(lài)、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沿著控制依賴(lài)、數(shù)據(jù)依賴(lài)、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}。依此類(lèi)推，得到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)依賴(lài)圖

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

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

面向?qū)W生程序的評(píng)測(cè)主要包括（1）程序是否編譯通過(guò)，有沒(méi)有警告；（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)則為<,>，通過(guò)對(duì)程序的遍歷找出程序中定義變量的語(yǔ)句，通過(guò)對(duì)該語(yǔ)句和語(yǔ)句中定義的變量進(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í)行該過(guò)程沒(méi)有標(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í)，說(shuō)明學(xué)生程序的邏輯結(jié)構(gòu)沒(méi)有標(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)沒(méi)有標(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)了一種“分流”的思想。通過(guò)逐步的選擇來(lái)達(dá)到所要達(dá)到的目的，可以減少選擇次數(shù)。

其次，語(yǔ)言層次也能體現(xiàn)邏輯的完整性。對(duì)比學(xué)生程序的程序切片和標(biāo)準(zhǔn)程序的程序切片，如果相似性高則說(shuō)明邏輯更完整。例如表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è)語(yǔ)句與標(biāo)準(zhǔn)程序相同或相似。可以很明顯的看出學(xué)生程序切片中的三條語(yǔ)句體現(xiàn)的邏輯思想不如標(biāo)準(zhǔn)程序，所以語(yǔ)言層次上存在差異。

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

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

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

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

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

4 結(jié)論

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

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

[2] 汪友生. 電類(lèi)非計(jì)算機(jī)專(zhuān)業(yè)C語(yǔ)言程序設(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] 蘇小紅, 龔丹丹, 王甜甜, 馬培軍.一種新的過(guò)程間靜態(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語(yǔ)言程序評(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語(yǔ)言程序評(píng)測(cè)方法[J]. 軟件，2018，39（10）：105-110