一種優化GCC抽象語法樹的方法

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

【關鍵詞】抽象語法樹 結點優化 結點冗余

1 引言

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

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

2 AST結構

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

（1）標識符結點（identifiers）；

（2）類型結點（types）；

（3）聲明結點（declarations）；

（4）函數結點（functions）；

（5）范圍結點（scope）；

（6）語句結點（statements）；

（7）表達式結點（expressions）。

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

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

3 抽象語法樹優化方法

3.1 優化目標

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

3.2 優化思想

確定AST中的結點是否為有用結點，主要經過以下兩個步驟：

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

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

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

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

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

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

經過這一步，可以消除AST文本中的固有冗余和系統冗余。

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

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

經過上述兩個優化步驟，得到了冗余消除后的抽象語法樹文本。經過優化的抽象語法樹，結點的數目減少很多，而且結構簡單，便于分析抽象語法樹。

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

3.3 AST結點遍歷方法

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

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

3.4 算法的詳細描述

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

輸出：規范化的抽象語法樹文本

算法過程：

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

int num_node；/* 計數器，記錄優化后有多少個有用結點*/

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

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

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

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

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

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

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

fout.open（"sub_node.txt"）

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

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

（18）for k=1 to n do

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

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

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

num_sub++；

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

（23）while_end；

（24）fin.close（）；

fout.close（）；

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

（26）算法結束。

3.5 算法復雜性分析

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

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

4 實驗分析

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

5 結束語

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

參考文獻

[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++源程序結構的分析[J].計算機工程與應用，2006（23）：97-100.

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

作者簡介

趙彥博（1980-），男，內蒙古鄂爾多斯市人。碩士學位。工程師。主要研究方向為電力系統技術研究，數據挖掘。

作者單位

1.呼和浩特供電局 內蒙古自治區呼和浩特市 010050

2.包頭市公安消防支隊 內蒙古自治區包頭市 014030