一種優(yōu)化GCC抽象語法樹的方法

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

【關鍵詞】抽象語法樹 結(jié)點優(yōu)化 結(jié)點冗余

1 引言

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

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

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

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

（1）標識符結(jié)點（identifiers）；

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

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

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

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

（6）語句結(jié)點（statements）；

（7）表達式結(jié)點（expressions）。

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

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

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

3.1 優(yōu)化目標

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

3.2 優(yōu)化思想

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

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

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

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

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

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

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

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

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

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

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

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

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

對AST遍歷和操作十分方便，所以對AST的訪問和操作分離成遍歷器和動作器，將遍歷算法和針對各個結(jié)點的操作分離出來。

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

3.4 算法的詳細描述

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

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

算法過程：

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

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

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

（1）對gcc_astTXT格式化，使描述同一結(jié)點的標記簽和標記值在同一行上

（2）fin.open（"*.tu"）；/*打開一個AST文件*/ fout.open（"node.txt"）；/*將有用結(jié)點編號寫入node.txt文件*/

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

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

（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）存儲在數(shù)組arry中；

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

fout.open（"sub_node.txt"）

（16）while（fin>>data） do /*取一個有用結(jié)點編號*/

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

（18）for k=1 to n do

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

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

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

num_sub++；

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

（23）while_end；

（24）fin.close（）；

fout.close（）；

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

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

3.5 算法復雜性分析

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

（2）算法占用的空間主要是一個字符串數(shù)組。

4 實驗分析

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

5 結(jié)束語

本文提出的方法達到了很好的效果并且具有較低的時間復雜度與空間復雜度。作為改善相似度計算的重要一步，取得了良好的效果。再進一步處理，可以非常方便地應用于對程序分析及其他領域。

參考文獻

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

[2]劉文偉，劉堅.一個重建GCC抽象語法樹的方法[J].計算機工程與應用，2004（18）：125-128.

[3]石峰，劉堅.一種解析GCC抽象語法樹的方法[J].計算機應用，2004，24（03）：115-116.

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

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

作者簡介

趙彥博（1980-），男，內(nèi)蒙古鄂爾多斯市人。碩士學位。工程師。主要研究方向為電力系統(tǒng)技術研究，數(shù)據(jù)挖掘。

作者單位

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

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