一种基于程序切片的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