基于K最近邻的C克隆代码重构方法

时间:2024-01-04 点赞:45096 浏览:87915 作者原创标记本站原创

本文是一篇代码论文范文,代码有关专升本毕业论文开题报告,关于基于K-最近邻的C克隆代码重构方法相关在职毕业论文范文。适合代码及过程及语句方面的的大学硕士和本科毕业论文以及代码相关开题报告范文和职称论文写作参考文献资料下载。

摘 要:在软件开发过程中,克隆代码已经成为引起软件缺陷的一个重要因素.针对现有的方法不能很好地处理内聚度低、功能交叉的克隆代码的问题,提出了一种基于K-最近邻的克隆代码重构方法.首先,对克隆代码进行静态分析,搜集控制依赖信息和数据流信息,再经过K-最近邻聚类方法,形成便于提取、功能独立的代码片段,然后对代码片段进行过程提取,使之成为一个独立的过程,并用过程调用替代原来的克隆代码.实验结果表明,该方法能够对克隆代码进行有效组织,并对功能独立的部分进行提取.

关 键 词:

中图分类号:TP311文献标识码:A文章编号:2095-2163(2011)01-0047-04

0引言

随着计算机软件的不断发展,研究人员提出了软件复用的概念.人们希望通过复用已有的高质量开发成果,避免重新开发可能引入的错误,提高软件的质量.当在开发过程中碰到一些熟悉问题的时候,编程人员就从已有的系统中寻找实现类似功能的代码,稍作修改,以满足需求,然后应用到当前系统中.随着时间的推移和系统功能的增加,拷贝-粘贴的方法很容易导致整个软件系统充斥着大量的克隆代码.

克隆代码在大多数情况下是有害的,增加了软件系统代码的长度,使得软件系统愈加复杂、难以维护,系统运行效率降低,并且给软件引入大量的程序缺陷.对克隆代码使用的重构技术主要是过程提取,就是将出现在源代码中的克隆代码提取为一个新的过程,这在一定程度上降低了克隆代码带来的危害.

过程提取这个概念最早出现在1977年,由BURSTALL和DARLINGTON首次提出[1].但是直到90年代初,才由GRISWOLD和NOTKIN第一次在其著作[2,3]中提出extract-function(过程提取)这个词.比较早的过程提取方法有LAKHOTIA提出的tuck[4]方法,该方法可以将连续的语句和不连续的语句提取成单独的过程.随后,KOMONDOOR和HORWITZ提出了语义保持的自动过程提取方法[5-6],来提取可能含有跳转语句的不连续的代码片段.HARMAN和BINKLEY针对自动过程提取方法又做了一些改进[7],减少了要提取的代码数量.但是上述方法都是注重将代码变换为连续一致的形式,计算复杂度较高,并且没有涉及到内聚度低、功能交叉的代码的处理.

为了处理内聚度低的代码,文献[8-9]在源代码级别上使用了聚类算法,选取可执行语句作为实体,根据实体的数据属性和控制属性计算相似度,将彼此关联的元素归类,但是文献中算法对语句之间的控制依赖考虑较少,导致聚类结果不准确,也没有将聚类算法应用到克隆代码的重构中.

针对上述方法中存在的不足,提出一种基于K-最近邻的克隆代码重构方法,结合控制依赖图和K-最近邻聚类算法,形成便于提取和功能独立的代码片段,然后基于抽象语法树,应用过程提取算法,将代码片段提取为一个新的过程.该方法能够有效改进程序结构,对克隆代码进行重构.

1基于K-最近邻的克隆代码重构算法

1.1基于K-最近邻的克隆代码重构模型

本文提出的克隆代码重构模型如图1所示.该模型的基本思路为:首先读入C克隆代码,接着进行词法分析和语法分析,在此基础上生成抽象语法树,然后建立程序依赖图,获得控制流信息和数据流信息.其次,采用控制依赖图和K-最近邻聚类算法相结合的方法分析代码,分离出便于提取、功能独立的代码片段.最后,调用基于抽象语法树的过程提取算法,解决参数相关问题,将代码片段提取为独立的过程,并用过程调用取代其在源代码中的位置.

1.2改进的基于控制依赖图的K-最近邻聚类算法

通过建立和分析程序的控制依赖图[10],可以求得代码语句的定值-引用变量信息.在此基础上,对代码执行聚类算法[8],将语句进行归类,可以提高提取、功能独立的代码片段的准确性.

基于这样一种思路,本文在文献[8-9]的基础上提出一种改进的基于控制依赖图的K-最近邻聚类算法.该聚类算法结合控制依赖图,查找、记录控制语句的作用域,重新调整语句之间的控制依赖关系,使得聚类结果更加准确;并且利用相似度矩阵和控制依赖关系,调整分类结果,使其可以作为过程提取算法的输入,支持克隆代码重构.改进的基于控制依赖图的K-最近邻算法如图2所示.

本文聚类算法选取程序语句作为聚类的实体对象,控制变量和数据变量作为实体的属性,以实体属性矩阵作为算法的输入,矩阵的行表示语句的行号,列表示实体相关的属性.

算法步骤如下:

(1)根据实体属性矩阵,计算两两实体之间的相似度,构建相似度矩阵;

(2)处理声明类型节点,初始化每个实体的类标签,类标签用来记录该实体在聚类过程中的分类情况;

(3)执行K-最近邻算法,对语句进行层次聚类.再遍历实体集合,对每个控制实体,结合控制依赖图,建立其与所有子结点的列表,形成控制实体集合;

(4)去掉每个聚类结果中相似度为零的分类;

(5)对于处于控制语句作用域中的语句,添加其控制节点,重建控制依赖;

(6)最后输出结果.

1.3基于抽象语法树的过程提取算法

代码经过聚类之后,形成了便于提取、功能独立的代码片段,可以将其提取为独立的过程.此时,主要需要解决待提

取的过程的参数相关问题,为此,本文在进行过程提取的同时,也加入了抽象语法树.当需要解决参数类型问题时,查找抽象语法树,获得需要的信息.过程提取的算法如图3所示.

具体涉及如下几个关键问题:

(1)提取变量的到达-定值信息

由于控制依赖图包含控制流信息,可通过控制依赖图获得节点之间的控制依赖关系,从而获得各个节点的到达――定值信息,因此可以在创建完成控制依赖子图后对其执行数据流分析,得到变量定值――引用信息[11].

(2)根据变量的定值――引用信息,确定变量类型

确定变量类型时,若是函数体中的声明变量,则遍历控制依赖图,找到声明语句,然后转到语法树,找到其对应的声明类型的语法树节点,根据语法规则,声明类型节点的最左孩子节点即为该变量的类型.若是函数参数列表中的变量,则首先根据函数定义得到变量所处位置信息,再遍历语法树,找到其对应的类型.


(3)确定要提取的过程的参数类型及个数

在将语句提取为新的过程时,需要确定新过程的参数类型.参数类型主要分为两类:传引用类型和传值类型.对定值(def)变量集合进行计算,去掉声明(del)集合中的变量,剩下的变量就是引用类型的参数,计算公式如下:

para(&)=Vars(def)-Vars(del)(1)

其中,para(&)表示引用类型参数的集合,Vars(def)表示定值变量的集合,Vars(del)表示声明变量的集合.

对引用集合(ref)中的变量经过处理作为传值类型,其计算公式如下:

para(v)=Vars(ref)-Vars(def)∪Vars(del)(2)

其中,para(v)表示传值类型参数的集合,Vars(ref)表示引用变量的集合.


para(&)和para(v)两个集合的元素个数即为新过程的参数个数.

此外,还要特别对待临时变量,此变量的定义和使用都在要提取的语句范围内.对于临时变量,不作为新过程的参数,直接放到新的过程体中.

(4)解决过程的返回值问题

在将代码提取为新的过程的时候,需要确定新过程是否有返回值.目前分为两种情况:新过程没有返回值和新过程有一个或多个返回值.如果新过程没有返回值,则直接将代码提取为新的过程.如果新过程有一个或多个返回值,统一采用传引用方式解决,将返回值以引用形式添加到新过程的参数列表.

采用数据流分析的方法来确定新过程是否有返回值.先计算标记语句后面语句的变量的信息,然后与标记语句的声明变量做对比,若二者有交集,则认为新的过程有返回值,计算公式如下:

returnvalues=Vars(del)-Vars(nbm)(3)

其中,returnvalues表示返回值集合,Vars(nbm)表示要提取的语句之后的变量集合.

(5)将代码提取为新的过程

在确定了新过程的参数和返回值之后,就可以将代码提取为新的过程了.这里,特别要注意的是新过程有返回值的情况.因为如果新过程有返回值,就可能要对标记语句节点进行分裂,使之成为两个声明语句,一条语句需要提取,一条语句不需要提取.例如对于标记声明语句intx,y=1,z;如果只有x是返回值涉及到的变量,则该语句需要分裂成两个节点:intx和inty=1,z.其中前者变为不需要提取的语句,作为新方法的引用参数;后者依然为需要提取的语句.

2实验结果与分析

为了验证以上算法,选取两组实验程序:第一组是文献[8]中使用的示例程序,第二组使用开源程序.

2.1文献中程序的实验

本文选取文献[8]中的代码来测试重构算法.文献中是java代码,聚类结果只给出树形表示形式,也没有给出重构方法.本文用C语言将其改写,示例代码如图4所示,其中有++符号的为待提取的克隆代码.

示例里的克隆代码是一段功能交叉的代码,包含计算数组元素的平均值avg和数组元素所有项的乘积prod两项功能.首先使用基于控制依赖图的K-最近邻聚类算法,形成功能独立的代码,聚类结果如图5所示.代码分成两类,有++标记的语句计算平均值avg,没有标记的语句计算成绩prod.在文献[8]的聚类结果中,没有指明for的控制范围,本文结果中,for语句的控制范围直接到语句,因而更加精确.

然后,对克隆代码执行过程提取算法,将其提取为单独的过程,并用新的过程调用取代其在源代码中的位置,结果如图6所示.文献[8]中并没有给出重构方法;本文提出了过程提取算法,处理了过程提取中参数相关问题,给出了具体的重构方案.文献[6]中的过程提取方法没有涉及到功能交叉的代码的处理,本方法能够更准确地提取功能内聚的代码.

2.2开源代码的实验

本文选取若干开源软件的克隆代码来进行实验.克隆代码的检测使用CPBugdetector[12&

本文是一篇代码论文范文,代码有关专升本毕业论文开题报告,关于基于K-最近邻的C克隆代码重构方法相关在职毕业论文范文。适合代码及过程及语句方面的的大学硕士和本科毕业论文以及代码相关开题报告范文和职称论文写作参考文献资料下载。

#93;.实验结果如表1所示.其中,#find表示检测到的克隆代码组数,#suit表示适合重构的克隆代码组数,#cluster表示聚类准确的克隆代码组数,#extract表示成功提取的克隆代码组数.从表1中可以看出,本文方法对需要重构的绝大部分克隆代码都能进行正确的重构,但是对原子操作代码的处理还存在一些不足,因为原子操作可能会受到其他语句的影响不能够聚在一起.

相比于文献[8]的方法,本文方法结合控制依赖图,有效地处理了语句之间的控制依赖关系,并将聚类结果应用于克隆代码的重构中,能够处理更多的情况.分别用本文方法和文献[8]的方法对上述开源软件进行实验,结果如表2所示.其中,#control表示有嵌套控制克隆代码组数.从表2中可以看出,本文算法对控制依赖有更好的处理.例如对图7中来自libmemcached-0.26中的克隆代码,文献[8]中的方法将两个while聚在同一个类中,使第二个while脱离了for的控制,如图8所示.本文方法则能够保持图7所示的控制依赖.

3结束语

本文提出一种基于K-最近邻的克隆代码重构方法.该方法结合控制依赖图和K-最近邻聚类算法,形成功能独立、便于提取的代码,再使用过程提取算法,对克隆代码进行重构.与文献[6]方法相比,本文方法能够较好地提取内聚度低、功能交叉的克隆代码;与文献[8]方法相比,本文方法能够较好地处理程序语句的控制依赖关系,具有较高的聚类准确性.

相关论文

Ja语言与C语言代码运行效率的比较

本文是一篇计算机语言论文范文,计算机语言相关毕业论文格式范文,关于Ja语言与C语言代码运行效率的比较相关毕业论文参考文献格式范文。适合。

一种谱的Matlab与VHDL代码转换方法

本文是一篇模块论文范文,关于模块方面毕业论文格式,关于一种谱的Matlab与VHDL代码转换方法相关在职研究生毕业论文范文。适合模块及蝶形及参。

机械制图作业错误代码批改方法

本文是一篇机械制图论文范文,机械制图类有关在职毕业论文开题报告,关于机械制图作业错误代码批改方法相关专科毕业论文范文。适合机械制图及。

c语言毕业文致谢范例

为您写身体健康毕业论文和职称论文提供身体健康相关大学毕业论文范文,与c语言毕业文致谢范例相关论文范文,包括关于身体健康及公司实习及科。

财会毕业文提纲高等数学C

该文是参考文献专业参考文献论文范文,主要论述了参考文献相关本科毕业论文,与财会毕业文提纲高等数学C相关论文范文,适合参考文献及财务会。

过量维生素C的不良反应

这篇维生素论文范文属于参考文献免费优秀学术论文范文,关于维生素方面毕业论文开题报告,与过量维生素C的不良反应相关毕业论文参考文献。适。

非合作A/C应答***识别

本论文是一篇模式方面毕业论文格式范文,关于非合作A C应答解码识别相关硕士毕业论文范文。免费优秀的关于模式及脉冲及电子技术方面论文范文。

组织机构代码质量解决方法

本文是一篇数据库论文范文,数据库方面电大毕业论文,关于组织机构代码质量解决方法相关毕业论文范文。适合数据库及代码及组织机构方面的的大。