分支语句重构算法的研究与应用

赵会群，孙雨

北方工业大学计算机学院，北京100144

分支语句重构算法的研究与应用

赵会群，孙雨

北方工业大学计算机学院，北京100144

CNKI网络出版：2017-04-14,http://kns.cnki.net/kcms/detail/11.2127.TP.20170414.1723.020.html

1 引言

软件产品的后期维护问题往往是由于软件自身的设计不当，然而，这种由软件产品质量引起的问题不仅会给用户带来经济损失，还会在诸如军事、医疗、航天、通信、交通等相关领域带来灾难性的后果。软件的安全性和可靠性就显得尤为重要，而要保证软件的正常运作，为人们提供最优质的服务，就需要对软件进行不断地维护与测试，这其中非常重要的一项工作就是软件重构[1]。

代码重构是对软件内部结构的一种调整[2]，目的是在不改变软件可观察行为的前提下，提高其可理解性，降低其修改成本[3]。面向结构分析需求的代码重构的基本思想是，通过对代码结构的分析与研究，确定对应的重构方法，以便对代码在结构上的识别与划分更加精准与高效。

关于重构的研究，前人已经做了大量的研究，在重构工具的设计与实现方面，由李龙[4]等实现了一个基于AADL架构的软件重构工具，软件架构的重构主要通过软件模态的迁移实现，运用生成的AADL模态的动态蓝图动态模拟目标软件系统的模态迁移过程，从而便于进行代码重构，最终实现该软件重构工具。在代码坏味的处理方面，高原[5]等人对代码坏味处理顺序的优先级进行了研究，选取具有代表性的10种代码坏味，从每种代码坏味的产生原因、症状，对软件的影响以及相应的处理这4个方面进行分析，考虑重构操作与相对应的代码坏味的关系，分析重构操作的先后顺序，最终得出代码坏味处理顺序的优先级。在代码的类提取方面，由Bavota[6]等对如何识别提炼类重构机会进行了研究，运用的方法是将结构和语义凝聚。他们利用结构和语义在方法之间的关系，提出了一个基于图理论的提取类重构方法，这个方法强调了语义和结构相结合措施的益处，也强调了该方法在软件开发环境中的潜在有用性。在代码的搬移函数方面，由Han[7]提出了一个自动化的方法来识别多个独立搬移函数重构候选点，并且可以同时应用以最大化提高软件的可维护性，此方法运用最高独立集的概念，确定多个重构操作可以同时被运用。运用实践证明该方法增强了重构识别过程的时效和效益，提高软件可维护性，与一次选择一个重构候选点的方法相比，需要较少的计算成本。在预测维护工作方面，由Yamashita[8]等研究了在多大程度上可以通过代码味道检测来预测维护问题，代码味道作为糟糕代码和不良设计的指示灯，很容易在软件维护和演化阶段引起一些问题。这项研究做了一个非常详细的调查，通过已知的现有的代码味道去预测维护阶段可能会出现的问题。最终从观察中得到的结论是代码味道只是维护难点的一个部分指示器，并不是占绝大部分或者全部责任。

本文所做的重构工作借鉴了以上相关工作的工作经验，从分析代码的坏味道开始，到提出具体的解决方案，到最后达到重构的效果[9]。

一般程序的伪代码中，会存在一系列的条件语句，而条件语句中又会嵌套条件语句，多重嵌套后导致程序逻辑结构复杂化，不利于分析程序的执行路径。在软件测试中，基本路径测试法是一种很常见的测试方法，它是一种白箱测试技术，基本路径测试方法允许测试用例设计者导出一个过程设计的逻辑复杂性测度，并使用该测度作为指南来定义执行路径的基本集。而要得到执行路径的基本集，首先要分析程序的执行路径[10]，这时清晰的程序逻辑结构就显得尤为重要。

传统的条件语句形式都是以if-else关键词的形式出现的，还有特殊的if-else嵌套形式，多重的嵌套使得程序的逻辑结构复杂化，不够清晰易懂，测试时，会导致分析程序的执行路径花费更多的时间。据此，本文提出了一种对嵌套条件语句进行优化的自动化重构方法，依据重构理论知识中代码坏味的判定方法[11]，运用语法分析中的自下而上分析方法和归约思想[12]，将嵌套的条件语句转化为线性排列的条件语句，简化了程序的逻辑结构，提高了代码的可读性，也提高了路径分析的精度，应用于改进后的路径集生成工具可以得到更准确的结果，对提高测试效率有很大帮助。本文主要实现了一种代码自动化重构的工具，同时改进了另一个相关工具（路径集生成工具）中生成模型代数[13]表达式的算法（准确度较低），该重构工具的应用提高了路径集生成工具的效率。

接下来的第2章介绍了重构条件分支语句工具的实现过程；第3章介绍了改进的生成代数表达式算法；第4章介绍了实验结果与分析过程；最后进行了总结。

2 重构分支语句的实现方法

该方法是以编译原理中语法分析方法为基础，运用其中的归约思想，在不改变伪代码功能的基础上，实现if-else嵌套语句的变换，最终实现伪代码的重构。方法的大概过程如下所示：

步骤1准备源伪代码。

步骤2对伪代码进行提取，替换，收集关键行，运用关键词来侦测其所在的行，将else替换为if形式，再收集所有的if条件表达式。

步骤3运用编译原理中语法分析的自下而上分析方法，利用其中的归约思想，将if嵌套的代码块变换为单一if条件。

步骤4得到组合条件，最终可用于进行直接替换。

步骤5首先侦测出替换点，进行代码块的差异性分析，定位出需要替换的代码块位置，替换完毕进行相应的删减，除去已无关的行。

步骤6得到重构之后的伪代码。

2.1 生成组合条件

语法分析的方法——自下而上分析的原理是，从输入串开始，逐步进行“归约”，直到文法的开始符号，即从树末端开始，构造语法树。采用“移进-归约”思想进行自下而上分析，用一个寄存符号的先进后出栈，把输入符号一个一个地移入到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成（规约为）该生产式的左部符号。边输入单词符号（移进到栈里），边归约。过程中处理的核心问题是：识别可归约串。

在if-else重构的算法中运用了类似于归约的基本思想，在将if条件入栈的同时，把匹配else的出现作为识别到了可归约串，继而得到可替换的if组合条件。整个过程也是边输入、边做类似归约的操作。相关算法见算法1。

算法1生成组合条件算法getIfMap（）

输入：初步处理伪代码提取的关键行。

输出：组合条件。

while（关键行不为空）

2.2 重构嵌套语句

侦测替换点时，要进行代码块的差异性分析，首次遇到的单行if并不能作为替换点，首次遇到双层嵌套时，或者是三层嵌套，表示替换点已被侦测到，需要进行相应的替换与删减，最终得到重构代码，相关算法见算法2。

算法2重构if嵌套changeIfNest（）

输入：组合条件。

输出：重构后的伪代码。

钢-混凝土组合结构桥梁是指钢腹板或钢桁架组成的钢梁与混凝土面板通过抗剪连接件连接在一起的桥梁结构形式，这种结构可以让钢材和混凝土共同承受主梁的荷载.

while（原伪代码不为空）

if遇到相邻两行都包含if then取一个组合条件来替换，移除多余的if行；

if遇到相邻三行都包含if then继续取组合条件来替换，并移除多余if行；

if遇到单行if，而此时组合条件集不为空then直接进行替换；

endwhile

3 生成模型代数表达式算法的改进

重构之后的伪代码可以用于生成基本路径集的工具，该工具可生成用于测试的基本路径集。在生成基本路径集工具中，生成模型代数表达式的算法存在一定的不足。

生成模型代数表达式的过程如下，首先运用编译原理中关于基本块的划分原理，对伪代码进行标记划分。需要对伪代码进行逻辑结构的分析，判断基本语句的流程关系，所做的标记能够与相应的控制流图表示一致，该算法扫描该伪代码的结构与标记，生成模型代数表达式。而该表达式最终提取解析出来的各个子表达式所表示的路径与控制流图的路径完全相同，才是最终正确的结果。但先前的算法在此环节有部分功能的缺失，未能足够准确地生成预期的模型代数表达式。本章对该算法做出了改进，具体见算法3。

算法3改进的生成模型代数表达式算法

//读取经过基本快划分的伪代码ReadPseudo_Code（Path）

//构件结点的前驱后继关系表

GenerateSuccessorMap

//通过递归方法生成模型代数表达式

//递归出口，该结点不存在后继结点或结点出/现循环

此处添加一个变量，用来判断结点是否是目标值}

本次改进的两个函数分别是String generateSubExpression（Integer index）{}和boolean isLoop（Integer index，int i）{}。原来的算法在遇到循环条件的时候，无法实现结点的倒序遍历，且由于递归条件的不够完善，在生成的模型代数表达式中无法出现相同的子表达式。基于这样的两个问题，对两个函数进行了相应的扩展。通过后面的案例对比，可以看出本次算法改进的有效性，能够准确地生成代数模型表达式。

4 实验结果与分析

首先针对嵌套分支语句重构方法进行具体案例分析，验证该重构方法的有效性。之后应用于选取的另外四个案例当中，并运用于生成基本路径集的工具中，同时引入改进后的算法，得到了重构与改进前后的不同实验结果，通过统计、对比、分析、验证了重构方法的通用性及改进算法的有效性。

4.1 重构案例研究

案例：任意输入三边的值，判断三角形的类型。

伪代码如图1所示。

图1 初始伪代码

首先依据if，else关键词对伪代码进行扫描提取、替换、收集，得到用于生成组合条件的关键行。将关键行作为算法1的输入，得到的组合条件如图2所示。

图2 组合条件

然后将得到的组合条件作为算法2的输入，得到的重构后的伪代码如图3所示。

图3 重构后的伪代码

重构后的伪代码能够保持程序原有功能，同时实现了代码逻辑结构的调整，简化结构，增强程序的可读性，遵循了重构的基本概念要求。本次的重构方法为以后生成基本路径集提供了清晰的程序逻辑结构，容易建立语句之间的对应关系，便于进行基本块的标记划分，提高了效率，对之后生成测试路径集有很大帮助，同时说明该重构方法在生成测试基本路径集这一方面具有一定意义，即为测试工作提供了方便。

4.2 重构方法应用案例研究

案例：计算不超过100个数字的平均值，同时计算总和与有效数字个数。具体的程序伪代码如图4所示。

图4 待测路径的程序伪代码

（1）重构与改进之前

划分基本块后的程序流图，如图5所示。

图5 重构前程序流程图

生成的代数表达式：（与预期不一致）

预期的代数表达式：

基本路径：->>>

独立路径：->>>

（2）重构与改进之后

划分基本块之后的程序流程图如图6所示。

图6 重构后程序流程图

生成的代数表达式：（与预期一致）

预期的代数表达式：

基本路径：->>>

独立路径：->>>

在使用路径集生成工具之前，首先用重构方法对伪代码进行重构，然后再进行基本路径集的生成工作。由于改进算法之前生成的代数表达式与预期的不一致，在生成的过程中存在一些结点不可达的路径，即路径不完整。改进算法之后生成的代数表达式可以与期望的表达式完全一致，最终生成与程序流程图完全一致的基本路径集。

现补充介绍一个代码相对复杂的案例，充分证明重构工具和改进算法的有效性。

案例：NextDate是一个有三个变量（月份、日期和年）的函数。函数返回输入日期后面的那个日期。变量月份、日期和年都是整数值，并满足以下条件：c1：1≤日期≤31；c2：1≤月份≤12；c3：1840≤年≤2016。

重构前伪代码如图7，重构后伪代码如图8。

运用基本路径集生成工具扫描此案例的伪代码，生成基本路径集。

改进前结果如下：

独立路径：->>>

存在大量终点不可达现象。

改进后结果如下：

独立路径：->>>

所有路径均可达到终点。

4.3 案例对比分析

本文研究的是文献[6]提出的五个案例，对其进行重构与应用，也方便对重构算法与改进算法所产生的效果进行先后对比。五个案例分别为：

案例1输入a,b值，经过处理后输出相应的a,b值。

案例2计算不超过100个数字的平均值，同时计算总和与有效数字个数。

案例3任意输入三边的值，判断三角形的类型。

案例4通过一定的规则，计算佣金的问题。

案例5输入年月日，计算该日期后面的日期。

图7 重构前伪代码

图8 重构后伪代码

本次实验对每一个案例都进行了重构，将得到的结果重新进行基本块的划分，然后用改进工具生成每一个案例的基本路径集。为了数据的直观简洁，便于进行对比，将得到的数据统计在两张表格中进行分析。

具体的实验数据可见表1和表2。

表1 重构前案例集数据

表2 重构后案例集数据

表1和表2中列出了结点数量，基本路径数量，路径完整性。

前后的不同之处表现在两个方面：划分基本块所用时间的不同和路径长度完整性的不同。重构之前，由于嵌套语句的逻辑结构比较复杂，导致划分基本块要用更多的时间，自动化重构[14]之后，可以减短所用时间。重构之前得到的基本路径会有终点不可达的现象，即路径不完整，有失准确性，改进生成模型代数表达式的算法后，可以确保所有路径的完整性。

通过此案例集的实验结果可以验证本次伪代码重构及改进生成模型代数表达式算法的有效性。

5 结束语

本文所做的研究，以基于模型代数的基本路径集的自动生成工具为基础，该工具是一种求基本路径集的全新思路，能够较为有效地生成待测程序的基本路径。该工具通过扫描程序的伪代码，最终生成与该伪代码的流图中相对应的基本路径集，而在扫描伪代码的过程中，生成的代数表达式存在一定的不足，本文首先对伪代码进行重构，而后改进生成代数表达式的算法，最终使得该工具能够非常准确地生成待测程序的基本路径。

通过面向结构分析需求的代码重构之后，代码会具有更加清晰易懂的程序结构（可见4.1节重构案例研究），便于进行分析程序的执行路径，使得路径集生成工具的性能也得到提升。将本方法与技术运用在基于模型代数的基本路径集自动生成工具中，该工具对伪代码的识别有一定的规则要求，造成代数表达式的生成存在一定的不足，通过本次重构及算法的改进，能够解决以上的不足之处，提高了划分基本块的效率，更快地生成了准确的基本测试路径集。更加具体地体现了代码重构的重要意义，使重构能够更为广泛地应用到不良代码当中[15]，而不仅仅只是停留在理论层面，同时验证了该代码重构工具的有效性，而且对测试自动化有重要意义。这样的实践使得面向结构的重构的理论与应用彼此融会贯通，丰富了理论，扩展了应用范围。当然，在实验过程中，为了便于对比所选取的案例是较为简短的，该算法能否解决更大规模的案例有待进一步进行研究和解决。

[1] Fowler M.重构改善既有代码的设计[M].北京：人民邮电出版社，2013.

[2] 王忠杰，徐晓飞，战德臣.面向复用成本优化的构件重构方法[J].软件学报，2005，16（12）：2157-2165.

[3] 陈生庆，张立臣，陈广明.面向方面软件重构等价性形式化证明方法[J].计算机科学，2006，33（7）：257-261.

[4] 李龙，董云卫，覃杨森，等.基于AADL的软件重构工具设计与实现[J].计算机科学，2011，38（7）：121-125.

[5] 高原，刘辉，樊孝忠，等.代码坏味的处理顺序[J].软件学报，2012，23（8）：1965-1977.

[6] Bavota G，Lucia A D，Oliveto R.Identifying extract class refactoring opportunities using structural and semantic cohesion measures[J].Journal of Systems and Software，2011，84（3）：397-414.

[7] Han A R，Bae D H，Cha S.An efficient approach to identify multiple and independent move method refactoring candidates[J].Information and Software Technology，2015，59（C）：53-66.

[8] Yamashita A，Moonen L.To what extent can maintenance problems be predicted by code smell detection?-An empirical study[J].Information and Software Technology，2013，55（12）：2223-2242.

[9] Liu Hui，Liu Yang，Xue Guo.Case study on software refactoring tactics[J].IET Software，2014，8（1）：1-11.

[10] 孙晶，张学娜.面向测试和模型检测需求的程序建模技术研究[J].计算机应用研究，2015（9）：2693-2696.

[11] Hermans F，Pinzger M，Deursen A V.Detecting and refactoring code smells in spreadsheet formulas[J].Empir Software Engineering，2015，20（2）：549-575.

[12] 陈火旺，刘春林.程序设计语言编译原理[M].3版.北京：国防工业出版社，2006.

[13] 赵会群，卢飞.基于模型代数的基本路径集的自动生成[J].计算机科学，2017，44（4）：114-117.

[14] 陈林，徐宝文，钱巨，等.一种基于类型传播分析的泛型实例重构方法[J].软件学报，2009，20（10）：2617-2627.

[15] Distante D，Garrido A，Camelier-Carvajal J.Business processes refactoring to improve usability in E-commerce applications[J].Electronic Commerce Research，2014，14（4）：497-529.

ZHAO Huiqun,SUN Yu.Research and application of refactoring algorithm of branch statements.Computer Engineering andApplications,2018,54（6）：30-36.

ZHAO Huiqun,SUN Yu

College of Computer Science,North China University of Technology,Beijing 100144,China

Due to the multiple nested of conditional branch statements,logic structure of the code is not clear and the code is difficult to read,the efficiency of dividing basic block is reduced when generating basic path set.On this basis,a method is proposed for automatic code refactoring.It uses bottom-up analysis and reduction,following compiler syntax analysis method,can realize automatic adjustment to the nested if-else conditional statement,and is more clearer to the structure of code,the code will be more suitable for the tool of generating basic path set.This method improves the efficiency of the tool of generating basic path set.For the tool of generating basic path set based on the model algebraic,it improves the algorithm of generating model algebraic expressions,and can generate basic path set accurately.Finally,through the comparison of the experiment,it verifies the effectiveness of the refactoring and the improved algorithm.

multiple nested;automated refactoring;bottom-up analysis;reduction;model algebraic expression

由于条件分支语句的多重嵌套，导致代码的逻辑结构不清晰，可读性差，降低了生成基本路径集时划分基本块的效率。据此，提出一种代码自动化重构方法，该方法运用编译原理中语法分析的自下而上分析方法和归约思想，能够对嵌套的if-else条件语句实现自动化调整，实现代码结构的清晰化，更适用于生成基本路径集的工具，该方法提高了生成基本路径集的效率。而对于基于模型代数的基本路径集生成工具，改进了生成模型代数表达式的算法，并且能够准确地生成基本路径集。最后通过实验对案例进行对比，验证了重构方法及改进算法的有效性。

多重嵌套；自动化重构；自下而上分析；归约；模型代数表达式

2016-10-13

2017-01-16

1002-8331（2018）06-0030-07

A

TP312

10.3778/j.issn.1002-8331.1610-0151

国家自然科学基金（No.61070030，No.61370051）。

赵会群（1960—），男，博士，教授，研究领域为软件体系结构，软件测试；孙雨（1989—），女，硕士研究生，研究领域为软件重构，E-mail：sunyu7412@163.com。