基于抽象語(yǔ)法樹的C克隆代碼重構(gòu)應(yīng)用與研究

辛艷艷　吳海濤

摘 要： 為了縮短軟件工程生命周期，引入組件、復(fù)制的概念，利用抽象語(yǔ)法樹（AST）將相同功能的代碼設(shè)計(jì)為一個(gè)函數(shù)，保留充足的接口參數(shù)，利用過程調(diào)用開發(fā)軟件程序，可以提高軟件開發(fā)效率.

關(guān)鍵詞： 抽象語(yǔ)法樹（AST）； 代碼重構(gòu)； 過程調(diào)用； 組件

中圖分類號(hào)： TP 312 文獻(xiàn)標(biāo)志碼： A 文章編號(hào)： 1000-5137（2018）04-0466-03

Abstract： In order to shorten the life cycle of software engineering，we usethe abstract syntax tree（AST） to design the same function of the code as a function according to the concept of components and reproduction.By keeping sufficient interface parameters，we can call the procedure to improve the efficiency of coding.

Key words：abstract syntax tree（AST）； code refactoring； procedure calling； component

0 引 言

軟件復(fù)用可以對(duì)高質(zhì)量的源代碼進(jìn)行重復(fù)利用，以減少程序設(shè)計(jì)工作量，降低重復(fù)性勞動(dòng)和誤差.但是，復(fù)用增加了代碼長(zhǎng)度，造成軟件系統(tǒng)架構(gòu)臃腫，運(yùn)行效率低，維護(hù)困難，于是研究人員提出了重構(gòu)技術(shù)[1].軟件重構(gòu)是一種提高程序開發(fā)的有效手段，可以在維持軟件功能正常運(yùn)轉(zhuǎn)的條件下改善軟件系統(tǒng)的程序組織結(jié)構(gòu)，可以有效清理代碼.劉陽(yáng)等[2]提出一種自動(dòng)檢測(cè)的代碼重構(gòu)技術(shù)，引入版本比較理念，可以自動(dòng)提取可重復(fù)利用的代碼，并將其設(shè)計(jì)為函數(shù).劉偉等[3]分析了人工重構(gòu)效率較低問題，提出一種以單例模式為導(dǎo)向的程序代碼自動(dòng)化重構(gòu)算法，將源代碼轉(zhuǎn)換為抽象語(yǔ)法樹（AST），創(chuàng)建一個(gè)實(shí)例類.胡志剛等[4]針對(duì)類型重構(gòu)，引入了一種簡(jiǎn)單的中間語(yǔ)言，并設(shè)計(jì)了一個(gè)寄存器抽象語(yǔ)法樹，采集程序基本類型和結(jié)構(gòu)體類型的約束信息，提出一種有效判斷二進(jìn)制代碼循環(huán)結(jié)構(gòu)和變量的方法，高效分析重構(gòu)數(shù)據(jù)類型.盧紅敏[5]提出一種重構(gòu)語(yǔ)義分析方法，引入后置條件作為重構(gòu)后程序語(yǔ)義的分析條件，能檢測(cè)出代碼異常的行為，利用不同重構(gòu)之間的關(guān)系及其關(guān)聯(lián)語(yǔ)義特征，發(fā)現(xiàn)重構(gòu)存在的錯(cuò)誤和缺陷，提高重構(gòu)準(zhǔn)確度.張重峰等[6]提出了一種自動(dòng)識(shí)別的重構(gòu)對(duì)象技術(shù)，利用程序切片構(gòu)造一種度量函數(shù)量化元素間的依賴程度，識(shí)別源代碼位置和從屬關(guān)系，提高重構(gòu)識(shí)別的效率.

由于程序重構(gòu)過程中實(shí)體的數(shù)據(jù)屬性、控制屬性較為相似，分類時(shí)沒有充分考慮語(yǔ)句之間的控制依賴，本文作者提出一種基于抽象語(yǔ)法樹的C克隆代碼重構(gòu)方法，將代碼端提取為一個(gè)新的函數(shù)，有效改善程序結(jié)構(gòu)，減少克隆代碼導(dǎo)致的錯(cuò)誤，提高重構(gòu)準(zhǔn)確度.

1 基于抽象語(yǔ)法樹的C克隆代碼重構(gòu)算法設(shè)計(jì)

為了提高代碼執(zhí)行效率，降低算法復(fù)雜度，利用抽象語(yǔ)法樹設(shè)計(jì)一個(gè)C克隆代碼重構(gòu)算法.算法執(zhí)行流程如下：首先針對(duì)C克隆代碼進(jìn)行程序編譯，其次對(duì)C克隆代碼進(jìn)行有效的詞法、語(yǔ)法分析，構(gòu)建一個(gè)抽象語(yǔ)法樹，并且建立一個(gè)程序控制依賴圖，以便準(zhǔn)確地獲取控制流信息、數(shù)據(jù)流信息.抽象語(yǔ)法樹使用控制依賴圖分析具體的程序代碼，將功能重復(fù)、完全獨(dú)立的C克隆代碼片段提取出來(lái)，進(jìn)行加工、整理和優(yōu)化，構(gòu)建一個(gè)傳遞參數(shù)的過程，最后，將過程調(diào)用的函數(shù)放回到C克隆代碼的位置.

算法執(zhí)行過程中，其關(guān)鍵步驟包括以下幾個(gè)方面.

1） 確定變量類型.變量類型確定時(shí)需要遍歷程序依賴圖，尋找聲明語(yǔ)句，然后通過抽象語(yǔ)法樹尋找對(duì)應(yīng)類型的語(yǔ)法樹節(jié)點(diǎn)，該節(jié)點(diǎn)的最左孩子節(jié)點(diǎn)即為變量的類型.采用深度遍歷、廣度遍歷相結(jié)合的模式，以便能夠快速地獲取變量類型，準(zhǔn)確地進(jìn)行函數(shù)過程重構(gòu).

2） 確定待提取過程的參數(shù)類型及個(gè)數(shù).將克隆代碼重塑為一個(gè)新的函數(shù)過程，需要確定其參數(shù)類型及個(gè)數(shù).為了便于分析，將變量劃分為聲明類型的變量、使用類型的變量及定值類型的變量，分別將它們放置到3個(gè)集合中.

3） 解決過程的返回值問題.如果新函數(shù)過程沒有返回值，則直接將代碼提取為一個(gè)新的函數(shù)過程；如果存在一個(gè)或多個(gè)返回值，則將返回值以引用形式添加到新函數(shù)過程的參數(shù)列表.采用分析數(shù)據(jù)流的方法確定新函數(shù)過程是否存在返回值，先計(jì)算標(biāo)記后續(xù)語(yǔ)句的變量信息，與標(biāo)記語(yǔ)句的聲明變量作對(duì)比，如果二者存在交集，則認(rèn)為新的過程存在返回值，返回值即是交集的元素.

2 應(yīng)用實(shí)例分析

為了驗(yàn)證所提算法的有效性，對(duì)一個(gè)開源軟件中的C克隆代碼進(jìn)行實(shí)驗(yàn)，并且使用工具CPBugdetector檢測(cè)源代碼.將所提算法的有效性與重構(gòu)語(yǔ)義分析算法[5]及基于C克隆代碼重構(gòu)算法進(jìn)行對(duì)比，算法執(zhí)行結(jié)果如表1所示.

由表1可知，所提算法精確度較高，尤其是在SDL-1.2.14程序中的克隆代碼提取時(shí)，所提算法的精確度比重構(gòu)語(yǔ)義分析算法的提高35個(gè)百分點(diǎn)，比C克隆代碼重構(gòu)算法的提高45個(gè)百分點(diǎn).

3 結(jié)束語(yǔ)

提出了基于抽象語(yǔ)法樹重構(gòu)算法，該算法可以重構(gòu)大部分的克隆代碼，增加了克隆代碼的標(biāo)識(shí)位，將相關(guān)的變量信息保存在程序關(guān)聯(lián)值中，關(guān)聯(lián)變量的定制和返回值，增強(qiáng)信息交互性.但是在原子操作代碼進(jìn)行處理時(shí)還存在一些不足，主要原因是原子操作語(yǔ)句之間缺乏保護(hù)措施.因此，未來(lái)可以對(duì)這些操作進(jìn)行改進(jìn)，比如引入多臺(tái)機(jī)制、切片度量等識(shí)別重構(gòu)代碼，提高算法的準(zhǔn)確度.

參考文獻(xiàn)：

[1] 馬金鑫，李舟軍，忽朝儉，等.一種重構(gòu)二進(jìn)制代碼中類型抽象的方法 [J].計(jì)算機(jī)研究與發(fā)展，2013，50（11）：2418-2428.

Ma J X，Li Z J，Hu C J，et al.A reconstruction method of type abstraction in binary code [J].Journal of Computer Research and Development，2013，50（11）：2418-2428.

[2] 劉陽(yáng)，劉秋榮，劉輝.函數(shù)抽取重構(gòu)的自動(dòng)檢測(cè)方法 [J].計(jì)算機(jī)科學(xué)，2015，42（12）：105-107.

Liu Y，Liu Q R，Liu H.Automated detection of extract method refactorings[J].Computer Science，2015，42（12）：105-107.

[3] 劉偉，胡志剛，劉宏韜.單例模式導(dǎo)向的源代碼自動(dòng)重構(gòu)研究 [J].小型微型計(jì)算機(jī)系統(tǒng)，2014（12）：2664-2669.

Liu W，Hu Z G，Liu H T.Singleton pattern directed automatic refactoring for source code [J].Journal of Chinese Computer Systems，2014（12）：2664-2669.

[4] 胡志剛，劉偉，劉宏韜.基于抽象語(yǔ)法樹和多態(tài)機(jī)制的復(fù)雜條件語(yǔ)句自動(dòng)重構(gòu)研究 [J].電子科技大學(xué)學(xué)報(bào)，2014（5）：736-741.

Hu Zhigang，Liu Wei，Liu Hongtao.Automatic refactoring for complex conditional statements based on abstract syntax tree and polymorphism [J].Journal of University of Electronic Science and Technology of China，2014（5）：736-741.

[5] 盧紅敏，郭晶，陳林，等.一種新的重構(gòu)語(yǔ)義分析方法及其應(yīng)用 [J].小型微型計(jì)算機(jī)系統(tǒng)，2012，33（11）：2372-2374.

Lu H M，Guo J，Chen L，et al.Novel refactoring semantic analysis model and its application [J].Journal of Chinese Computer Systems，2012，33（11）：2372-2374.

[6] 張重峰，李必信，孫小兵，等.基于切片度量的重構(gòu)對(duì)象識(shí)別 [J].東南大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，40（2）：275-281.

Zhang C F，Li B X，Sun X B，et al.Slice-based metrics for identifying refactoring [J].Journal of southeast University （natural science edition），2010，40（2）：275-281.

[7] Moret J M，Duval B P，Le H B，et al.Tokamak equilibrium reconstruction code LIUQE and its real time implementation [J].Fusion Engineering & Design，2015，91：1-15.

[8] Lazar F M，Banias O.Clone detection algorithm based on the Abstract Syntax Tree approach [C].International Symposium on Applied Computational Intelligence and Informatics，Timisoara：IEEE，2014.

（責(zé)任編輯：包震宇）