由于GCC抽象語(yǔ)法樹(shù)包含許多有助于編譯的細(xì)節(jié)信息，提出一種優(yōu)化抽象語(yǔ)法樹(shù)結(jié)構(gòu)關(guān)系的方法，消除冗余結(jié)點(diǎn)。通過(guò)實(shí)驗(yàn)證明了算法的正確性和適用性。

【關(guān)鍵詞】抽象語(yǔ)法樹(shù) 結(jié)點(diǎn)優(yōu)化 結(jié)點(diǎn)冗余

1 引言

GCC（GNU Compiler Collection）編譯器是美國(guó)自由軟件基金會(huì)（Free Software Foundation，F(xiàn)SF）開(kāi)發(fā)的編譯器，它能夠支持 C， C++， Objective-C， Fortran， Java 和 Ada 等程序設(shè)計(jì)語(yǔ)言，同時(shí)能夠運(yùn)行在 x86， x86-64， IA-64， PowerPC， SPARC 和 Alpha 等幾乎目前所有的硬件平臺(tái)上。由于GCC 開(kāi)放源代碼的特點(diǎn)， 對(duì)最新的C++標(biāo)準(zhǔn)（ ISO/IEC 1998） 的良好支持， 以及 GCC 編譯代碼的高效性，使其受到廣大程序員的認(rèn)可， 成為L(zhǎng)inux、Unix和Windows操作系統(tǒng)平臺(tái)上C/C++標(biāo)準(zhǔn)的編譯器。

抽象語(yǔ)法樹(shù)（Abstract syntax tree）是程序編譯階段的一種中間表示形式。作為一種良好的中間表示，AST比較直觀地表示出源程序的語(yǔ)法結(jié)構(gòu)，含有源程序結(jié)構(gòu)顯示所需的全部靜態(tài)信息，并具有較高的存儲(chǔ)效率。AST的結(jié)構(gòu)不依賴于源語(yǔ)言的文法，也就是語(yǔ)法分析階段所采用的上下文無(wú)關(guān)文法，因此，AST被許多編譯器選作程序的中間表示形式，用于編譯的語(yǔ)義分析階段。在AST 的基礎(chǔ)上，還可以進(jìn)行程序優(yōu)化，生成機(jī)器代碼，也可以生成控制流﹑數(shù)據(jù)流圖，而且在程序分析等其它領(lǐng)域也具有廣泛的應(yīng)用。

2 AST結(jié)構(gòu)

GCC 編譯器以源程序的過(guò)程為單位生成AST，而且包含整個(gè)編譯單元的完整表示。AST是GCC編譯器前端的中心數(shù)據(jù)結(jié)構(gòu)，比較直觀地表示出源程序的語(yǔ)法結(jié)構(gòu)，并含有源程序結(jié)構(gòu)顯示所需的全部靜態(tài)信息。從GCC編譯器3.0版本開(kāi)始，用編譯參數(shù)-fdump-translation-unit可以得到*.tu的以文本形式輸出的AST文件，其中*為源程序名，一個(gè)結(jié)點(diǎn)的AST結(jié)構(gòu)如圖1所示，一個(gè)AST文本由若干個(gè)這樣的結(jié)點(diǎn)組。AST的結(jié)點(diǎn)類型包括以下7種：

（1）標(biāo)識(shí)符結(jié)點(diǎn)（identifiers）；

（2）類型結(jié)點(diǎn)（types）；

（3）聲明結(jié)點(diǎn)（declarations）；

（4）函數(shù)結(jié)點(diǎn)（functions）；

（5）范圍結(jié)點(diǎn)（scope）；

（6）語(yǔ)句結(jié)點(diǎn)（statements）；

（7）表達(dá)式結(jié)點(diǎn)（expressions）。

GCC的AST文件存儲(chǔ)方式是首先對(duì)此AST上的每一個(gè)結(jié)點(diǎn)編號(hào)，然后每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)一條記錄項(xiàng)，每個(gè)記錄項(xiàng)以“@”開(kāi)始，@后是該結(jié)點(diǎn)的索引。該結(jié)點(diǎn)包含的信息主要有變量的名字（name）、變量的類型（type）、該變量在屬于哪一個(gè)函數(shù)（scpe）、源代碼的文件名及在程序中的位置（srcp）等，其中@3584 稱作結(jié)點(diǎn)編號(hào)，它是抽象語(yǔ)法樹(shù)上區(qū)分該結(jié)點(diǎn)的唯一標(biāo)志，也是訪問(wèn)該結(jié)點(diǎn)的索引。其后是結(jié)點(diǎn)標(biāo)識(shí)符和結(jié)點(diǎn)標(biāo)記的序列。結(jié)點(diǎn)標(biāo)識(shí)符是該節(jié)點(diǎn)的名稱，代表了該結(jié)點(diǎn)的含義， @3584 結(jié)點(diǎn)的結(jié)點(diǎn)標(biāo)識(shí)符為var_decl。其余部分為結(jié)點(diǎn)標(biāo)記的列表，每個(gè)結(jié)點(diǎn)標(biāo)記形如：name ： @3590。結(jié)點(diǎn)標(biāo)記的列表記錄了該結(jié)點(diǎn)連接到其他結(jié)點(diǎn)的所有分支，每個(gè)結(jié)點(diǎn)標(biāo)記對(duì)應(yīng)一個(gè)分支。結(jié)點(diǎn)標(biāo)記由標(biāo)記標(biāo)簽和標(biāo)記值組成，標(biāo)記值可以為空。標(biāo)記標(biāo)簽是該分支的名稱，標(biāo)記值是該分支連接的目標(biāo)。@3584結(jié)點(diǎn)的第一個(gè)結(jié)點(diǎn)標(biāo)記是name ： @3590 ，name 為標(biāo)記標(biāo)簽， @3590為標(biāo)記值，代表該結(jié)點(diǎn)第一個(gè)分支是name 分支，其指向目標(biāo)為@3590 結(jié)點(diǎn)。

GCC 產(chǎn)生的抽象語(yǔ)法樹(shù)文本規(guī)模龐大，不適合直接進(jìn)行代碼分析，所以需要先優(yōu)化抽象語(yǔ)法樹(shù)文本中的冗余信息，過(guò)濾跟源程序無(wú)關(guān)的結(jié)點(diǎn)。編譯器的目的是將高級(jí)語(yǔ)言轉(zhuǎn)化為匯編代碼，故而， GCC 產(chǎn)生的抽象語(yǔ)法樹(shù)文本中包含許多有助于編譯的細(xì)節(jié)信息，例如由#include 命令產(chǎn)生的未被源程序用到的函數(shù)及結(jié)構(gòu)，以及編譯過(guò)程中產(chǎn)生的一些內(nèi)部函數(shù)、類型聲明、出錯(cuò)信息、常量等，這些信息屬于無(wú)用信息，不利于代碼分析。在數(shù)量上，一個(gè)七行代碼的加法運(yùn)算程序，能產(chǎn)生三千五百多條的抽象語(yǔ)法樹(shù)文本，如果直接解析抽象語(yǔ)法樹(shù)文本，最終產(chǎn)生的AST會(huì)占據(jù)整個(gè)內(nèi)存，產(chǎn)生內(nèi)存“泄漏”。

3 抽象語(yǔ)法樹(shù)優(yōu)化方法

3.1 優(yōu)化目標(biāo)

為了提高從GCC抽象語(yǔ)法樹(shù)中提取靜態(tài)信息的效率，優(yōu)化的目標(biāo)是消除抽象語(yǔ)法樹(shù)中所有不能表達(dá)程序含義的信息，既消除抽象語(yǔ)法樹(shù)文本中與程序無(wú)關(guān)的抽象語(yǔ)法樹(shù)結(jié)點(diǎn)。

3.2 優(yōu)化思想

確定AST中的結(jié)點(diǎn)是否為有用結(jié)點(diǎn)，主要經(jīng)過(guò)以下兩個(gè)步驟：

Step1 對(duì)AST文本遍歷，選擇含有源程序含義的有用結(jié)點(diǎn)：

（1）if node.identifier==var_decl，then if srcp==文件名，該結(jié)點(diǎn)為有用結(jié)點(diǎn)。

（2）if node.identifier==real_cst，該結(jié)點(diǎn)為有用結(jié)點(diǎn)；

（3）if node.identifier==parm_decl，該結(jié)點(diǎn)為有用結(jié)點(diǎn)；

（4）if node.identifier==nop_expr，該結(jié)點(diǎn)為有用結(jié)點(diǎn)；

（5）if node.identifier== modify_expr，該結(jié)點(diǎn)為有用結(jié)點(diǎn)；

經(jīng)過(guò)這一步，可以消除AST文本中的固有冗余和系統(tǒng)冗余。

Step2由上一步得到的有用結(jié)點(diǎn)的孩子節(jié)點(diǎn)也是有用結(jié)點(diǎn)，所以對(duì)孩子節(jié)點(diǎn)遍歷將其確定為有用結(jié)點(diǎn)。

根據(jù)AST建立的鄰接矩陣，對(duì)有用結(jié)點(diǎn)中的標(biāo)記簽遍歷，遍歷的過(guò)程是一個(gè)類似于圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。根據(jù)結(jié)點(diǎn)遍歷，可以找出抽象語(yǔ)法樹(shù)中表達(dá)諸如源代碼的文件名、函數(shù)名、函數(shù)類型、函數(shù)的參數(shù)及參數(shù)類型、變量名、變量類型的結(jié)點(diǎn)。

經(jīng)過(guò)上述兩個(gè)優(yōu)化步驟，得到了冗余消除后的抽象語(yǔ)法樹(shù)文本。經(jīng)過(guò)優(yōu)化的抽象語(yǔ)法樹(shù)，結(jié)點(diǎn)的數(shù)目減少很多，而且結(jié)構(gòu)簡(jiǎn)單，便于分析抽象語(yǔ)法樹(shù)。

如果直接在內(nèi)存中解析抽象語(yǔ)法樹(shù)文本，最終產(chǎn)生的AST會(huì)占據(jù)整個(gè)內(nèi)存，為了防止產(chǎn)生內(nèi)存“泄漏”，所以對(duì)AST文本優(yōu)化過(guò)程中采用文件讀寫的方式，既只有當(dāng)前解析的一個(gè)結(jié)點(diǎn)才會(huì)進(jìn)入到內(nèi)存，其他結(jié)點(diǎn)仍然存放在文件中。

3.3 AST結(jié)點(diǎn)遍歷方法

對(duì)AST遍歷和操作十分方便，所以對(duì)AST的訪問(wèn)和操作分離成遍歷器和動(dòng)作器，將遍歷算法和針對(duì)各個(gè)結(jié)點(diǎn)的操作分離出來(lái)。

對(duì)于AST文本的訪問(wèn)和操作絕大部分是遍歷操作，對(duì)GCC 產(chǎn)生的抽象語(yǔ)法樹(shù)遍歷是自頂向下深度優(yōu)先遍歷，在遍歷的過(guò)程中記錄所關(guān)注節(jié)點(diǎn)的標(biāo)識(shí)符，并根據(jù)該結(jié)點(diǎn)的分支實(shí)現(xiàn)對(duì)結(jié)點(diǎn)的遍歷。結(jié)點(diǎn)標(biāo)記對(duì)應(yīng)一個(gè)分支，在自上而下遍歷的過(guò)程中，通過(guò)結(jié)點(diǎn)的標(biāo)記值傳遞直接實(shí)現(xiàn)深度優(yōu)先遍歷；對(duì)一個(gè)分支遍歷結(jié)束后，再對(duì)結(jié)點(diǎn)中下一個(gè)標(biāo)記分支遍歷，實(shí)現(xiàn)對(duì)結(jié)點(diǎn)標(biāo)記的廣度優(yōu)先遍歷。

3.4 算法的詳細(xì)描述

輸入：GCC產(chǎn)生的抽象語(yǔ)法樹(shù)文本（*.tu文件）

輸出：規(guī)范化的抽象語(yǔ)法樹(shù)文本

算法過(guò)程：

聲明：int num；/* 計(jì)數(shù)器，記錄該AST文本有多少個(gè)結(jié)點(diǎn)*/

int num_node；/* 計(jì)數(shù)器，記錄優(yōu)化后有多少個(gè)有用結(jié)點(diǎn)*/

int num_sub；/* 計(jì)數(shù)器，記錄遍歷時(shí)得到有多少個(gè)葉子*/

（1）對(duì)gcc_astTXT格式化，使描述同一結(jié)點(diǎn)的標(biāo)記簽和標(biāo)記值在同一行上

（2）fin.open（"*.tu"）；/*打開(kāi)一個(gè)AST文件*/ fout.open（"node.txt"）；/*將有用結(jié)點(diǎn)編號(hào)寫入node.txt文件*/

fout_adj.open（"ast_adjacency_matrix.txt"）；/*將AST文本中所有的結(jié)點(diǎn)寫入該文件中，建立鄰接矩陣*/

（3）while（node） do /*取一個(gè)結(jié)點(diǎn)，node為AST文本中的一個(gè)結(jié)點(diǎn)*/

（4）num++；

（5）fout_adj<

（6）if （node.identifier==var_decl&& node.srcp==文件名）

then fout<

（7）if node.identifier==real_cst

then fout<

（8）if node.identifier==parm_decl

then fout<

（9）if node.identifier==nop_expr

then fout<

（10）if node.identifier== modify_expr

then fout<

num_node++；

（11）while_end；

（12）fin.close（）；

fout.close（）；

（13）int *arry=new int[num]；

（14）將鄰接矩陣（arryast_adjacency_matrix.txt）存儲(chǔ)在數(shù)組arry中；

（15）fin.open（"node.txt"）；

fout.open（"sub_node.txt"）

（16）while（fin>>data） do /*取一個(gè)有用結(jié)點(diǎn)編號(hào)*/

（17）查找data在鄰接矩陣中的位置；

（18）for k=1 to n do

（19）依次對(duì)k個(gè)標(biāo)記簽進(jìn)行遍歷；/*類似圖的廣度優(yōu)先遍歷，n為該結(jié)點(diǎn)中含有n個(gè)標(biāo)記簽，標(biāo)記簽所指向的結(jié)點(diǎn)也是有用結(jié)點(diǎn)，對(duì)標(biāo)記簽也進(jìn)行遍歷*/

（20）根據(jù)第k個(gè)標(biāo)記簽的值進(jìn)行深度遍歷，直到找到葉子結(jié)點(diǎn)；/*遍歷類似圖的深度優(yōu)先遍歷，所有的遍歷都在鄰接矩陣中進(jìn)行*/

（21）將遍歷得到的葉子結(jié)點(diǎn)編號(hào)寫入sub_node.txt文件中；

num_sub++；

（22）結(jié)點(diǎn)編號(hào)映射；//編號(hào)映射存放到”info.txt”文件中

（23）while_end；

（24）fin.close（）；

fout.close（）；

（25）delete[] arry； /*釋放存儲(chǔ)單元*/

（26）算法結(jié)束。

3.5 算法復(fù)雜性分析

（1）算法耗時(shí)：令m = AST結(jié)點(diǎn)個(gè)數(shù)，在尋找有用結(jié)點(diǎn)上，算法的時(shí)間復(fù)雜度為O（m×n）；對(duì)每個(gè)有用結(jié)點(diǎn)為根的子結(jié)點(diǎn)的遍歷，算法的時(shí)間復(fù)雜度為O（m2×n）；所以，算法的時(shí)間復(fù)雜度為O（m2×n）；

（2）算法占用的空間主要是一個(gè)字符串?dāng)?shù)組。

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

在Dev-C++_4.9.9.2環(huán)境中實(shí)現(xiàn)以上算法，實(shí)驗(yàn)結(jié)果如圖2所示。從圖2可以看出，總體上效果達(dá)到了預(yù)計(jì)的目標(biāo)，較好地刪除了AST文本中的冗余結(jié)點(diǎn)。圖2和圖3是冗余消除前的抽象語(yǔ)法樹(shù)文本與冗余消除后的AST文本的一個(gè)對(duì)照，該文本是以計(jì)算10個(gè)整數(shù)和的平均值為例。

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

本文提出的方法達(dá)到了很好的效果并且具有較低的時(shí)間復(fù)雜度與空間復(fù)雜度。作為改善相似度計(jì)算的重要一步，取得了良好的效果。再進(jìn)一步處理，可以非常方便地應(yīng)用于對(duì)程序分析及其他領(lǐng)域。

參考文獻(xiàn)

[1]GCC Command Options.Available[OL].http：//gcc.gnu.org/onlinedocs/gcc-3.0.4/gcc.html，2017-2-1.

[2]劉文偉，劉堅(jiān).一個(gè)重建GCC抽象語(yǔ)法樹(shù)的方法[J].計(jì)算機(jī)工程與應(yīng)用，2004（18）：125-128.

[3]石峰，劉堅(jiān).一種解析GCC抽象語(yǔ)法樹(shù)的方法[J].計(jì)算機(jī)應(yīng)用，2004，24（03）：115-116.

[4]王相懂，張毅坤.基于GCC抽象語(yǔ)法樹(shù)對(duì)C++源程序結(jié)構(gòu)的分析[J].計(jì)算機(jī)工程與應(yīng)用，2006（23）：97-100.

[5]趙彥博.基于抽象語(yǔ)法樹(shù)的程序代碼抄襲檢測(cè)技術(shù)研究[D].內(nèi)蒙古師范大學(xué)，2010：16-19.

作者簡(jiǎn)介

趙彥博（1980-），男，內(nèi)蒙古鄂爾多斯市人。碩士學(xué)位。工程師。主要研究方向?yàn)殡娏ο到y(tǒng)技術(shù)研究，數(shù)據(jù)挖掘。

作者單位

1.呼和浩特供電局 內(nèi)蒙古自治區(qū)呼和浩特市 010050

2.包頭市公安消防支隊(duì) 內(nèi)蒙古自治區(qū)包頭市 014030