簡(jiǎn)化GNU編譯器套件抽象語法樹的算法研究

高峰　吳海濤

摘 要： 提出了一種消除抽象語法樹文本中冗余的方法，借助Knuth-Morris-Pratt（KMP）算法，設(shè)計(jì)核心算法，對(duì)抽象語法樹進(jìn)行簡(jiǎn)化，并選出幾個(gè)經(jīng)典的代碼片段進(jìn)行實(shí)驗(yàn)，對(duì)算法的性能做了相應(yīng)驗(yàn)證.實(shí)驗(yàn)結(jié)果表明，算法在消除冗余方面的簡(jiǎn)化率達(dá)到90%以上.

關(guān)鍵詞： 抽象語法樹； GNU編譯器套件（GCC）； Knuth-Morris-Pratt（KMP）算法； 重復(fù)代碼

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

Abstract： We propose a method to eliminate the redundancy in the text of abstract syntax tree.By using the Knuth-Morris-Pratt （KMP） algorithm，we design the core algorithm，simplify the abstract syntax tree，and select several classic code fragments to be tested.The experimental results show that the reduction rate of the algorithm is more than 90%.

Key words： abstract syntax tree； GNU compiler collection （GCC）； Knuth-Morris-Pratt（KMP） algorithm； duplicated code

0 引 言

GNU編譯器套件（GCC）生成的抽象語法樹包含了許多編譯操作的細(xì)節(jié)信息，如頭文件中的函數(shù)、常量等，增加源代碼分析的工作量.另外，抽象語法樹文件結(jié)點(diǎn)數(shù)目龐大，增加了內(nèi)存的消耗，降低了分析的效率，因此需要消除抽象語法樹文本中的冗余信息，過濾與源程序無關(guān)的結(jié)點(diǎn).

抽象語法樹相關(guān)文獻(xiàn)很多，Nilsson[1]利用抽象語法樹進(jìn)行代碼抄襲的檢測(cè).Srinuvasu等[2]基于抽象語法樹，重構(gòu)軟件模型圖.Okunday等[3]借助抽象語法樹，從模式匹配中確定圖像的相似性.李鑫等[4]提出了一種簡(jiǎn)化GCC抽象語法樹的算法，達(dá)到了簡(jiǎn)化抽象語法樹文本的目的.田冰川等[5]提出了一種新穎的算法來簡(jiǎn)化GCC抽象語法樹，通過將樹轉(zhuǎn)化成圖來進(jìn)行算法分析，從而達(dá)到簡(jiǎn)化的目的.

由上述文獻(xiàn)可以看出，抽象語法樹的使用很頻繁，而且應(yīng)用的領(lǐng)域也很廣泛，但是在利用抽象語法樹解析源代碼時(shí)，并沒有考慮到語法樹本身存在的冗余問題，使解析效率下降，還在一定程度上降低了結(jié)果的準(zhǔn)確性，所以簡(jiǎn)化抽象語法樹顯得十分必要.本文作者在文獻(xiàn)[1]算法的基礎(chǔ)上進(jìn)行改進(jìn)，設(shè)計(jì)一種更加簡(jiǎn)易高效的算法，來簡(jiǎn)化GCC抽象語法樹.

1 抽象語法樹文本簡(jiǎn)化算法

1.1 算法的基本思想

整個(gè)算法主要分為兩步：1） 使用深度優(yōu)先算法去遍歷樹中的結(jié)點(diǎn)；2） 使用KMP算法進(jìn)行結(jié)點(diǎn)名稱的字符串匹配.

將所有結(jié)點(diǎn)默認(rèn)設(shè)為unknownNode，根據(jù)來源（srcp）字段的值，依次對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行判斷，將所有結(jié)點(diǎn)分為三類：

1） 沒有srcp字段，該結(jié)點(diǎn)維持unknownNode；

2） 有srcp字段且srcp字段值為源文件名，該結(jié)點(diǎn)被標(biāo)示為usefulNode；

3） 有srcp字段且srcp字段值不是源文件名，該結(jié)點(diǎn)被標(biāo)示為uselessNode.

對(duì)所有的unknownNode（下面的子結(jié)點(diǎn)簡(jiǎn)寫為subNode）進(jìn)行轉(zhuǎn)化：

1） 如果父結(jié)點(diǎn)是usefulnode，則該節(jié)點(diǎn)被標(biāo)示為usefulNode；

2） 如果父結(jié)點(diǎn)是uselessNode，則該節(jié)點(diǎn)被標(biāo)示為uselessNode；

3） 直到unknownNode的個(gè)數(shù)為0.

最后，找回包含相關(guān)函數(shù)的結(jié)點(diǎn).

1.2 核心算法的詳細(xì)描述

算法過程如圖1所示.

1.3 算法復(fù)雜度分析

1.3.1 時(shí)間復(fù)雜度

采用Knuth-Morris-Pratt（KMP）算法尋找子串“srcp”，由于每個(gè)結(jié)點(diǎn)的字符長(zhǎng)度有限，假設(shè)結(jié)點(diǎn)字符長(zhǎng)度小于M，結(jié)點(diǎn)總數(shù)為n，那么算法的時(shí)間復(fù)雜度為O（（4+M）× n）.轉(zhuǎn)換unknownNode結(jié)點(diǎn)時(shí)，由于每個(gè)結(jié)點(diǎn)的字節(jié)點(diǎn)個(gè)數(shù)有限，不妨假設(shè)子節(jié)點(diǎn)個(gè)數(shù)小于P，算法的時(shí)間復(fù)雜度為O（P×n）.找回相關(guān)函數(shù)結(jié)點(diǎn)時(shí)，算法的時(shí)間復(fù)雜度為O（（P-1）×n）.因此，整個(gè)算法的時(shí)間復(fù)雜度為O（n）.

1.3.2 空間復(fù)雜度：

算法占用的空間主要是一個(gè)字符型數(shù)組及2個(gè)整型數(shù)組的存儲(chǔ)空間.

2 實(shí)驗(yàn)分析

為了檢測(cè)算法的實(shí)際性能，選取5段不同的C語言源代碼對(duì)算法進(jìn)行測(cè)試，分別統(tǒng)計(jì)簡(jiǎn)化前后抽象語法樹文件中的節(jié)點(diǎn)數(shù)目，并進(jìn)行對(duì)比，對(duì)比結(jié)果如表1所示.

由表1可以看出，化簡(jiǎn)后結(jié)點(diǎn)數(shù)比原程序的精簡(jiǎn)，5個(gè)程序中抽象語法樹文本中的結(jié)點(diǎn)化簡(jiǎn)率都達(dá)到了90%以上，說明該算法較好地刪除了冗余信息，為后續(xù)的語法樹分析提供了便利.

輸入：通過gcc-fdump-translation-unit參數(shù)所產(chǎn)生的原文件的抽象語法樹文本（*.tu 文件）

輸出：簡(jiǎn)化的抽象語法樹文本（result.tu文件）.

char str[M][N] //用來存儲(chǔ).tu文件中所有結(jié)點(diǎn)

int substr[K][L] //存儲(chǔ)結(jié)點(diǎn)的所有子節(jié)點(diǎn)編號(hào)

int flag[Q]=0 /*用整型數(shù)組存儲(chǔ)結(jié)點(diǎn)的標(biāo)識(shí)（0表示unkown，1表示useless，2表示useful），初始狀態(tài)所有結(jié)點(diǎn)設(shè)為unkown*/

for 0<=i< n //假定抽象語法樹文本中有n個(gè)結(jié)點(diǎn)

if str[i] 有srcp字段

if srcp字段的值！=源文件名 then flag[i]==1 //找出useless結(jié)點(diǎn)

else if srcp字段的值==源文件名 then flag[i]==2 //找出useful結(jié)點(diǎn)

//將unkown結(jié)點(diǎn)轉(zhuǎn)化為useless or useful結(jié)點(diǎn)

for 0<=i

//將父結(jié)點(diǎn)是useful的subNode，全部標(biāo)識(shí)為useful

if（flag[i]==2）

for 0<=j

if flag[substr[i][j]]==0 then flag[substr[i][j]]==2

//將父結(jié)點(diǎn)是useless的子節(jié)點(diǎn)，全部標(biāo)識(shí)為useless

else if（flag[i]==1）

for 0<=j

if flag[substr[i][j]]==0 then flag[substr[i][j]]==1

//找回相應(yīng)子節(jié)點(diǎn)

for 0<=i

if str[i]有相關(guān)字段

then

for 1<=j< sum

flag[substr[i][j]]==2

3 結(jié)束語

提出了一種簡(jiǎn)化GCC抽象語法樹文本的改進(jìn)算法，為GCC抽象語法樹文本刪除了冗余信息，進(jìn)而為后續(xù)利用抽象語法樹檢測(cè)重復(fù)代碼的分析工作提供了便利.

參考文獻(xiàn)：

[1] Nilsson E.Abstract syntax tree analysis for plagiarism detection [D].Linkping：Linkping University，2012.

[2] Srinuvasu A，Padmaja P.Construction of software model graph and analyzing object-oriented program（C#） using abstract syntax tree method [J].2015，6（4）：3288-3293.

[3] Okundaye B，Ewert S，Sanders I.Determining image similarity from pattern matching of abstract syntax trees of tree picture grammars [C].Twenty-Fourth Annual Symposium of the Pattern Recognition Association of South Africa.Johannesburg：CSIR，2013.

[4] 李鑫，王甜甜，蘇小紅，等.消除GCC抽象語法樹文本中冗余信息的算法研究 [J].計(jì)算機(jī)科學(xué)，2008，35（10）：170-172.

Li X，Wang T T，Su X H，et al.Research on eliminating redundancies of GCC AST text [J].Computer Science，2008，35（10）：170-172.

[5] 田冰川，孫珂，巢漢青.簡(jiǎn)化GCC抽象語法樹的新型算法 [J].計(jì)算機(jī)科學(xué)，2015，42（6A）：516-518.

Tian B C，Sun K，Chao H Q.New algorithm of simplying GCC syntax tree [J].Computer Science，2015，42（6A）：516-518.

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