趙會群，孫雨

北方工業(yè)大學計算機學院，北京100144

分支語句重構算法的研究與應用

趙會群，孫雨

北方工業(yè)大學計算機學院，北京100144

CNKI網(wǎng)絡出版：2017-04-14,http://kns.cnki.net/kcms/detail/11.2127.TP.20170414.1723.020.html

1 引言

軟件產(chǎn)品的后期維護問題往往是由于軟件自身的設計不當，然而，這種由軟件產(chǎn)品質量引起的問題不僅會給用戶帶來經(jīng)濟損失，還會在諸如軍事、醫(yī)療、航天、通信、交通等相關領域帶來災難性的后果。軟件的安全性和可靠性就顯得尤為重要，而要保證軟件的正常運作，為人們提供最優(yōu)質的服務，就需要對軟件進行不斷地維護與測試，這其中非常重要的一項工作就是軟件重構[1]。

代碼重構是對軟件內(nèi)部結構的一種調整[2]，目的是在不改變軟件可觀察行為的前提下，提高其可理解性，降低其修改成本[3]。面向結構分析需求的代碼重構的基本思想是，通過對代碼結構的分析與研究，確定對應的重構方法，以便對代碼在結構上的識別與劃分更加精準與高效。

關于重構的研究，前人已經(jīng)做了大量的研究，在重構工具的設計與實現(xiàn)方面，由李龍[4]等實現(xiàn)了一個基于AADL架構的軟件重構工具，軟件架構的重構主要通過軟件模態(tài)的遷移實現(xiàn)，運用生成的AADL模態(tài)的動態(tài)藍圖動態(tài)模擬目標軟件系統(tǒng)的模態(tài)遷移過程，從而便于進行代碼重構，最終實現(xiàn)該軟件重構工具。在代碼壞味的處理方面，高原[5]等人對代碼壞味處理順序的優(yōu)先級進行了研究，選取具有代表性的10種代碼壞味，從每種代碼壞味的產(chǎn)生原因、癥狀，對軟件的影響以及相應的處理這4個方面進行分析，考慮重構操作與相對應的代碼壞味的關系，分析重構操作的先后順序，最終得出代碼壞味處理順序的優(yōu)先級。在代碼的類提取方面，由Bavota[6]等對如何識別提煉類重構機會進行了研究，運用的方法是將結構和語義凝聚。他們利用結構和語義在方法之間的關系，提出了一個基于圖理論的提取類重構方法，這個方法強調了語義和結構相結合措施的益處，也強調了該方法在軟件開發(fā)環(huán)境中的潛在有用性。在代碼的搬移函數(shù)方面，由Han[7]提出了一個自動化的方法來識別多個獨立搬移函數(shù)重構候選點，并且可以同時應用以最大化提高軟件的可維護性，此方法運用最高獨立集的概念，確定多個重構操作可以同時被運用。運用實踐證明該方法增強了重構識別過程的時效和效益，提高軟件可維護性，與一次選擇一個重構候選點的方法相比，需要較少的計算成本。在預測維護工作方面，由Yamashita[8]等研究了在多大程度上可以通過代碼味道檢測來預測維護問題，代碼味道作為糟糕代碼和不良設計的指示燈，很容易在軟件維護和演化階段引起一些問題。這項研究做了一個非常詳細的調查，通過已知的現(xiàn)有的代碼味道去預測維護階段可能會出現(xiàn)的問題。最終從觀察中得到的結論是代碼味道只是維護難點的一個部分指示器，并不是占絕大部分或者全部責任。

本文所做的重構工作借鑒了以上相關工作的工作經(jīng)驗，從分析代碼的壞味道開始，到提出具體的解決方案，到最后達到重構的效果[9]。

一般程序的偽代碼中，會存在一系列的條件語句，而條件語句中又會嵌套條件語句，多重嵌套后導致程序邏輯結構復雜化，不利于分析程序的執(zhí)行路徑。在軟件測試中，基本路徑測試法是一種很常見的測試方法，它是一種白箱測試技術，基本路徑測試方法允許測試用例設計者導出一個過程設計的邏輯復雜性測度，并使用該測度作為指南來定義執(zhí)行路徑的基本集。而要得到執(zhí)行路徑的基本集，首先要分析程序的執(zhí)行路徑[10]，這時清晰的程序邏輯結構就顯得尤為重要。

傳統(tǒng)的條件語句形式都是以if-else關鍵詞的形式出現(xiàn)的，還有特殊的if-else嵌套形式，多重的嵌套使得程序的邏輯結構復雜化，不夠清晰易懂，測試時，會導致分析程序的執(zhí)行路徑花費更多的時間。據(jù)此，本文提出了一種對嵌套條件語句進行優(yōu)化的自動化重構方法，依據(jù)重構理論知識中代碼壞味的判定方法[11]，運用語法分析中的自下而上分析方法和歸約思想[12]，將嵌套的條件語句轉化為線性排列的條件語句，簡化了程序的邏輯結構，提高了代碼的可讀性，也提高了路徑分析的精度，應用于改進后的路徑集生成工具可以得到更準確的結果，對提高測試效率有很大幫助。本文主要實現(xiàn)了一種代碼自動化重構的工具，同時改進了另一個相關工具（路徑集生成工具）中生成模型代數(shù)[13]表達式的算法（準確度較低），該重構工具的應用提高了路徑集生成工具的效率。

接下來的第2章介紹了重構條件分支語句工具的實現(xiàn)過程；第3章介紹了改進的生成代數(shù)表達式算法；第4章介紹了實驗結果與分析過程；最后進行了總結。

2 重構分支語句的實現(xiàn)方法

該方法是以編譯原理中語法分析方法為基礎，運用其中的歸約思想，在不改變偽代碼功能的基礎上，實現(xiàn)if-else嵌套語句的變換，最終實現(xiàn)偽代碼的重構。方法的大概過程如下所示：

步驟1準備源偽代碼。

步驟2對偽代碼進行提取，替換，收集關鍵行，運用關鍵詞來偵測其所在的行，將else替換為if形式，再收集所有的if條件表達式。

步驟3運用編譯原理中語法分析的自下而上分析方法，利用其中的歸約思想，將if嵌套的代碼塊變換為單一if條件。

步驟4得到組合條件，最終可用于進行直接替換。

步驟5首先偵測出替換點，進行代碼塊的差異性分析，定位出需要替換的代碼塊位置，替換完畢進行相應的刪減，除去已無關的行。

步驟6得到重構之后的偽代碼。

2.1 生成組合條件

語法分析的方法——自下而上分析的原理是，從輸入串開始，逐步進行“歸約”，直到文法的開始符號，即從樹末端開始，構造語法樹。采用“移進-歸約”思想進行自下而上分析，用一個寄存符號的先進后出棧，把輸入符號一個一個地移入到棧里，當棧頂形成某個產(chǎn)生式的候選式時，即把棧頂?shù)倪@一部分替換成（規(guī)約為）該生產(chǎn)式的左部符號。邊輸入單詞符號（移進到棧里），邊歸約。過程中處理的核心問題是：識別可歸約串。

在if-else重構的算法中運用了類似于歸約的基本思想，在將if條件入棧的同時，把匹配else的出現(xiàn)作為識別到了可歸約串，繼而得到可替換的if組合條件。整個過程也是邊輸入、邊做類似歸約的操作。相關算法見算法1。

算法1生成組合條件算法getIfMap（）

輸入：初步處理偽代碼提取的關鍵行。

輸出：組合條件。

while（關鍵行不為空）

2.2 重構嵌套語句

偵測替換點時，要進行代碼塊的差異性分析，首次遇到的單行if并不能作為替換點，首次遇到雙層嵌套時，或者是三層嵌套，表示替換點已被偵測到，需要進行相應的替換與刪減，最終得到重構代碼，相關算法見算法2。

算法2重構if嵌套changeIfNest（）

輸入：組合條件。

輸出：重構后的偽代碼。

鋼-混凝土組合結構橋梁是指鋼腹板或鋼桁架組成的鋼梁與混凝土面板通過抗剪連接件連接在一起的橋梁結構形式，這種結構可以讓鋼材和混凝土共同承受主梁的荷載.

while（原偽代碼不為空）

if遇到相鄰兩行都包含if then取一個組合條件來替換，移除多余的if行；

if遇到相鄰三行都包含if then繼續(xù)取組合條件來替換，并移除多余if行；

if遇到單行if，而此時組合條件集不為空then直接進行替換；

endwhile

3 生成模型代數(shù)表達式算法的改進

重構之后的偽代碼可以用于生成基本路徑集的工具，該工具可生成用于測試的基本路徑集。在生成基本路徑集工具中，生成模型代數(shù)表達式的算法存在一定的不足。

生成模型代數(shù)表達式的過程如下，首先運用編譯原理中關于基本塊的劃分原理，對偽代碼進行標記劃分。需要對偽代碼進行邏輯結構的分析，判斷基本語句的流程關系，所做的標記能夠與相應的控制流圖表示一致，該算法掃描該偽代碼的結構與標記，生成模型代數(shù)表達式。而該表達式最終提取解析出來的各個子表達式所表示的路徑與控制流圖的路徑完全相同，才是最終正確的結果。但先前的算法在此環(huán)節(jié)有部分功能的缺失，未能足夠準確地生成預期的模型代數(shù)表達式。本章對該算法做出了改進，具體見算法3。

算法3改進的生成模型代數(shù)表達式算法

//讀取經(jīng)過基本快劃分的偽代碼ReadPseudo_Code（Path）

//構件結點的前驅后繼關系表

GenerateSuccessorMap

//通過遞歸方法生成模型代數(shù)表達式

//遞歸出口，該結點不存在后繼結點或結點出/現(xiàn)循環(huán)

此處添加一個變量，用來判斷結點是否是目標值}

本次改進的兩個函數(shù)分別是String generateSubExpression（Integer index）{}和boolean isLoop（Integer index，int i）{}。原來的算法在遇到循環(huán)條件的時候，無法實現(xiàn)結點的倒序遍歷，且由于遞歸條件的不夠完善，在生成的模型代數(shù)表達式中無法出現(xiàn)相同的子表達式?；谶@樣的兩個問題，對兩個函數(shù)進行了相應的擴展。通過后面的案例對比，可以看出本次算法改進的有效性，能夠準確地生成代數(shù)模型表達式。

4 實驗結果與分析

首先針對嵌套分支語句重構方法進行具體案例分析，驗證該重構方法的有效性。之后應用于選取的另外四個案例當中，并運用于生成基本路徑集的工具中，同時引入改進后的算法，得到了重構與改進前后的不同實驗結果，通過統(tǒng)計、對比、分析、驗證了重構方法的通用性及改進算法的有效性。

4.1 重構案例研究

案例：任意輸入三邊的值，判斷三角形的類型。

偽代碼如圖1所示。

圖1 初始偽代碼

首先依據(jù)if，else關鍵詞對偽代碼進行掃描提取、替換、收集，得到用于生成組合條件的關鍵行。將關鍵行作為算法1的輸入，得到的組合條件如圖2所示。

圖2 組合條件

然后將得到的組合條件作為算法2的輸入，得到的重構后的偽代碼如圖3所示。

圖3 重構后的偽代碼

重構后的偽代碼能夠保持程序原有功能，同時實現(xiàn)了代碼邏輯結構的調整，簡化結構，增強程序的可讀性，遵循了重構的基本概念要求。本次的重構方法為以后生成基本路徑集提供了清晰的程序邏輯結構，容易建立語句之間的對應關系，便于進行基本塊的標記劃分，提高了效率，對之后生成測試路徑集有很大幫助，同時說明該重構方法在生成測試基本路徑集這一方面具有一定意義，即為測試工作提供了方便。

4.2 重構方法應用案例研究

案例：計算不超過100個數(shù)字的平均值，同時計算總和與有效數(shù)字個數(shù)。具體的程序偽代碼如圖4所示。

圖4 待測路徑的程序偽代碼

（1）重構與改進之前

劃分基本塊后的程序流圖，如圖5所示。

圖5 重構前程序流程圖

生成的代數(shù)表達式：（與預期不一致）

預期的代數(shù)表達式：

基本路徑：->>>

獨立路徑：->>>

（2）重構與改進之后

劃分基本塊之后的程序流程圖如圖6所示。

圖6 重構后程序流程圖

生成的代數(shù)表達式：（與預期一致）

預期的代數(shù)表達式：

基本路徑：->>>

獨立路徑：->>>

在使用路徑集生成工具之前，首先用重構方法對偽代碼進行重構，然后再進行基本路徑集的生成工作。由于改進算法之前生成的代數(shù)表達式與預期的不一致，在生成的過程中存在一些結點不可達的路徑，即路徑不完整。改進算法之后生成的代數(shù)表達式可以與期望的表達式完全一致，最終生成與程序流程圖完全一致的基本路徑集。

現(xiàn)補充介紹一個代碼相對復雜的案例，充分證明重構工具和改進算法的有效性。

案例：NextDate是一個有三個變量（月份、日期和年）的函數(shù)。函數(shù)返回輸入日期后面的那個日期。變量月份、日期和年都是整數(shù)值，并滿足以下條件：c1：1≤日期≤31；c2：1≤月份≤12；c3：1840≤年≤2016。

重構前偽代碼如圖7，重構后偽代碼如圖8。

運用基本路徑集生成工具掃描此案例的偽代碼，生成基本路徑集。

改進前結果如下：

獨立路徑：->>>

存在大量終點不可達現(xiàn)象。

改進后結果如下：

獨立路徑：->>>

所有路徑均可達到終點。

4.3 案例對比分析

本文研究的是文獻[6]提出的五個案例，對其進行重構與應用，也方便對重構算法與改進算法所產(chǎn)生的效果進行先后對比。五個案例分別為：

案例1輸入a,b值，經(jīng)過處理后輸出相應的a,b值。

案例2計算不超過100個數(shù)字的平均值，同時計算總和與有效數(shù)字個數(shù)。

案例3任意輸入三邊的值，判斷三角形的類型。

案例4通過一定的規(guī)則，計算傭金的問題。

案例5輸入年月日，計算該日期后面的日期。

圖7 重構前偽代碼

圖8 重構后偽代碼

本次實驗對每一個案例都進行了重構，將得到的結果重新進行基本塊的劃分，然后用改進工具生成每一個案例的基本路徑集。為了數(shù)據(jù)的直觀簡潔，便于進行對比，將得到的數(shù)據(jù)統(tǒng)計在兩張表格中進行分析。

具體的實驗數(shù)據(jù)可見表1和表2。

表1 重構前案例集數(shù)據(jù)

表2 重構后案例集數(shù)據(jù)

表1和表2中列出了結點數(shù)量，基本路徑數(shù)量，路徑完整性。

前后的不同之處表現(xiàn)在兩個方面：劃分基本塊所用時間的不同和路徑長度完整性的不同。重構之前，由于嵌套語句的邏輯結構比較復雜，導致劃分基本塊要用更多的時間，自動化重構[14]之后，可以減短所用時間。重構之前得到的基本路徑會有終點不可達的現(xiàn)象，即路徑不完整，有失準確性，改進生成模型代數(shù)表達式的算法后，可以確保所有路徑的完整性。

通過此案例集的實驗結果可以驗證本次偽代碼重構及改進生成模型代數(shù)表達式算法的有效性。

5 結束語

本文所做的研究，以基于模型代數(shù)的基本路徑集的自動生成工具為基礎，該工具是一種求基本路徑集的全新思路，能夠較為有效地生成待測程序的基本路徑。該工具通過掃描程序的偽代碼，最終生成與該偽代碼的流圖中相對應的基本路徑集，而在掃描偽代碼的過程中，生成的代數(shù)表達式存在一定的不足，本文首先對偽代碼進行重構，而后改進生成代數(shù)表達式的算法，最終使得該工具能夠非常準確地生成待測程序的基本路徑。

通過面向結構分析需求的代碼重構之后，代碼會具有更加清晰易懂的程序結構（可見4.1節(jié)重構案例研究），便于進行分析程序的執(zhí)行路徑，使得路徑集生成工具的性能也得到提升。將本方法與技術運用在基于模型代數(shù)的基本路徑集自動生成工具中，該工具對偽代碼的識別有一定的規(guī)則要求，造成代數(shù)表達式的生成存在一定的不足，通過本次重構及算法的改進，能夠解決以上的不足之處，提高了劃分基本塊的效率，更快地生成了準確的基本測試路徑集。更加具體地體現(xiàn)了代碼重構的重要意義，使重構能夠更為廣泛地應用到不良代碼當中[15]，而不僅僅只是停留在理論層面，同時驗證了該代碼重構工具的有效性，而且對測試自動化有重要意義。這樣的實踐使得面向結構的重構的理論與應用彼此融會貫通，豐富了理論，擴展了應用范圍。當然，在實驗過程中，為了便于對比所選取的案例是較為簡短的，該算法能否解決更大規(guī)模的案例有待進一步進行研究和解決。

[1] Fowler M.重構改善既有代碼的設計[M].北京：人民郵電出版社，2013.

[2] 王忠杰，徐曉飛，戰(zhàn)德臣.面向復用成本優(yōu)化的構件重構方法[J].軟件學報，2005，16（12）：2157-2165.

[3] 陳生慶，張立臣，陳廣明.面向方面軟件重構等價性形式化證明方法[J].計算機科學，2006，33（7）：257-261.

[4] 李龍，董云衛(wèi)，覃楊森，等.基于AADL的軟件重構工具設計與實現(xiàn)[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版.北京：國防工業(yè)出版社，2006.

[13] 趙會群，盧飛.基于模型代數(shù)的基本路徑集的自動生成[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

由于條件分支語句的多重嵌套，導致代碼的邏輯結構不清晰，可讀性差，降低了生成基本路徑集時劃分基本塊的效率。據(jù)此，提出一種代碼自動化重構方法，該方法運用編譯原理中語法分析的自下而上分析方法和歸約思想，能夠對嵌套的if-else條件語句實現(xiàn)自動化調整，實現(xiàn)代碼結構的清晰化，更適用于生成基本路徑集的工具，該方法提高了生成基本路徑集的效率。而對于基于模型代數(shù)的基本路徑集生成工具，改進了生成模型代數(shù)表達式的算法，并且能夠準確地生成基本路徑集。最后通過實驗對案例進行對比，驗證了重構方法及改進算法的有效性。

多重嵌套；自動化重構；自下而上分析；歸約；模型代數(shù)表達式

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。