董伟 张明刚 张津源

摘要：由于GCC抽象语法树包含许多有助于编译的细节信息，提出一种优化抽象语法树结构关系的方法，消除冗余结点。通过实验证明了算法的正确性和适用性。

关键词：抽象语法树；结点优化；结点冗余

Abstract: due to the GCC abstract syntax tree contains many help compiler details, and put forward a kind of optimization abstract syntax tree structure relation method, eliminate redundant nodes. Through the experiments prove the effectiveness and the validity of the algorithm.

Keywords: abstract syntax tree; Node optimization; Node redundancy

中图分类号：TP314文献标识码：A 文章编号：

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种：①标识符结点(identifiers)，②类型结点(types)，③声明结点(declarations)，④函数结点(functions)，⑤范围结点(scope)，⑥语句结点(statements)，⑦表达式结点(expressions)。

图1 AST结点结构

GCC的AST文件存储方式是首先对此AST上的每一个结点编号，然后每一个结点对应一条记录项，每个记录项以“@”开始，@后是该结点的索引。该结点包含的信息主要有变量的名字(name)、变量的类型(type)、该变量在属于哪一个函数(scpe)、源代码的文件名及在程序中的位置(srcp)等，其中@3584 称作结点编号,它是抽象语法树上区分该结点的唯一标志,也是访问该结点的索引。其后是结点标识符和结点标记的序列。结点标识符是该节点的名称,代表了该结点的含义, @3584 结点的结点标识符为var_decl。其余部分为结点标记的列表,每个结点标记形如:name : @3590。结点标记的列表记录了该结点连接到其他结点的所有分支,每个结点标记对应一个分支。结点标记由标记标签和标记值组成,标记值可以为空。标记标签是该分支的名称,标记值是该分支连接的目标。@3584结点的第一个结点标记是name : @3590 ,name 为标记标签, @3590为标记值,代表该结点第一个分支是name 分支,其指向目标为@3590 结点。

GCC 产生的抽象语法树文本规模庞大，不适合直接进行代码分析,所以需要先优化抽象语法树文本中的冗余信息，过滤跟源程序无关的结点。编译器的目的是将高级语言转化为汇编代码，故而, GCC 产生的抽象语法树文本中包含许多有助于编译的细节信息,例如由#include 命令产生的未被源程序用到的函数及结构,以及编译过程中产生的一些内部函数、类型声明、出错信息、常量等,这些信息属于无用信息，不利于代码分析。在数量上,一个七行代码的加法运算程序，能产生三千五百多条的抽象语法树文本，如果直接解析抽象语法树文本,最终产生的AST会占据整个内存，产生内存“泄漏”。

2抽象语法树优化方法

2.1优化目标

为了提高从GCC抽象语法树中提取静态信息的效率，优化的目标是消除抽象语法树中所有不能表达程序含义的信息，既消除抽象语法树文本中与程序无关的抽象语法树结点。

2.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文本优化过程中采用文件读写的方式，既只有当前解析的一个结点才会进入到内存，其他结点仍然存放在文件中。

2.3 AST结点遍历方法

对AST遍历和操作十分方便，所以对AST的访问和操作分离成遍历器和动作器,将遍历算法和针对各个结点的操作分离出来。

对于AST文本的访问和操作绝大部分是遍历操作，对GCC 产生的抽象语法树遍历是自顶向下深度优先遍历，在遍历的过程中记录所关注节点的标识符，并根据该结点的分支实现对结点的遍历。结点标记对应一个分支，在自上而下遍历的过程中，通过结点的标记值传递直接实现深度优先遍历；对一个分支遍历结束后，再对结点中下一个标记分支遍历，实现对结点标记的广度优先遍历。

2.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==文件名)

thenfout<

(7)if node.identifier==real_cst

thenfout<

(8)if node.identifier==parm_decl

thenfout<

(9)if node.identifier==nop_expr

thenfout<

(10) if node.identifier== modify_expr

thenfout<

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) 算法结束。

2.4算法复杂性分析

(1)算法耗时：令m = AST结点个数，在寻找有用结点上,算法的时间复杂度为O(m×n)；对每个有用结点为根的子结点的遍历,算法的时间复杂度为O(m2×n)；所以，算法的时间复杂度为O(m2×n)；

(2)算法占用的空间主要是一个字符串数组。

3实验分析

在Dev-C++_4.9.9.2环境中实现以上算法，实验结果如图2所示。从图2可以看出,总体上效果达到了预计的目标,较好地删除了AST文本中的冗余结点。图2和图3是冗余消除前的抽象语法树文本与冗余消除后的AST文本的一个对照,该文本是以计算10个整数和的平均值为例。

图2 优化后的AST文本

图3 优化前的AST文本

4结束语

本文提出的方法达到了很好的效果并且具有较低的时间复杂度与空间复杂度。作为改善程序代码相似度计算的重要一步，现已用到程序代码抄袭检测系统中，取得了良好的效果。再进一步处理，可以非常方便地应用于对程序分析及其他领域。

参考文献：

[1]李鑫，王甜甜，苏小红等.消除GCC抽象语法树文本中冗余信息的算法研究[J].计算机科学,2008,35(10):170-172..

[2]刘文伟,刘坚.一个重建GCC抽象语法树的方法[J].计算机工程与应用,2004,18:125-128.

[3]石峰,刘坚.一种解析GCC抽象语法树的方法[J].计算机应用,2004,24(3):115-116.

[4]王相懂,张毅坤.基于GCC抽象语法树对C++源程序结构的分析[J].计算机工程与应用,2006,23:97-100.

[5]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1997.

注：文章内所有公式及图表请以PDF形式查看。