简化GNU编译器套件抽象语法树的算法研究

高峰　吴海涛

摘 要： 提出了一种消除抽象语法树文本中冗余的方法，借助Knuth-Morris-Pratt（KMP）算法，设计核心算法，对抽象语法树进行简化，并选出几个经典的代码片段进行实验，对算法的性能做了相应验证.实验结果表明，算法在消除冗余方面的简化率达到90%以上.

关键词： 抽象语法树； GNU编译器套件（GCC）； Knuth-Morris-Pratt（KMP）算法； 重复代码

中图分类号： TP 311 文献标志码： A 文章编号： 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）生成的抽象语法树包含了许多编译操作的细节信息，如头文件中的函数、常量等，增加源代码分析的工作量.另外，抽象语法树文件结点数目庞大，增加了内存的消耗，降低了分析的效率，因此需要消除抽象语法树文本中的冗余信息，过滤与源程序无关的结点.

抽象语法树相关文献很多，Nilsson[1]利用抽象语法树进行代码抄袭的检测.Srinuvasu等[2]基于抽象语法树，重构软件模型图.Okunday等[3]借助抽象语法树，从模式匹配中确定图像的相似性.李鑫等[4]提出了一种简化GCC抽象语法树的算法，达到了简化抽象语法树文本的目的.田冰川等[5]提出了一种新颖的算法来简化GCC抽象语法树，通过将树转化成图来进行算法分析，从而达到简化的目的.

由上述文献可以看出，抽象语法树的使用很频繁，而且应用的领域也很广泛，但是在利用抽象语法树解析源代码时，并没有考虑到语法树本身存在的冗余问题，使解析效率下降，还在一定程度上降低了结果的准确性，所以简化抽象语法树显得十分必要.本文作者在文献[1]算法的基础上进行改进，设计一种更加简易高效的算法，来简化GCC抽象语法树.

1 抽象语法树文本简化算法

1.1 算法的基本思想

整个算法主要分为两步：1） 使用深度优先算法去遍历树中的结点；2） 使用KMP算法进行结点名称的字符串匹配.

将所有结点默认设为unknownNode，根据来源（srcp）字段的值，依次对每个结点进行判断，将所有结点分为三类：

1） 没有srcp字段，该结点维持unknownNode；

2） 有srcp字段且srcp字段值为源文件名，该结点被标示为usefulNode；

3） 有srcp字段且srcp字段值不是源文件名，该结点被标示为uselessNode.

对所有的unknownNode（下面的子结点简写为subNode）进行转化：

1） 如果父结点是usefulnode，則该节点被标示为usefulNode；

2） 如果父结点是uselessNode，则该节点被标示为uselessNode；

3） 直到unknownNode的个数为0.

最后，找回包含相关函数的结点.

1.2 核心算法的详细描述

算法过程如图1所示.

1.3 算法复杂度分析

1.3.1 时间复杂度

采用Knuth-Morris-Pratt（KMP）算法寻找子串“srcp”，由于每个结点的字符长度有限，假设结点字符长度小于M，结点总数为n，那么算法的时间复杂度为O（（4+M）× n）.转换unknownNode结点时，由于每个结点的字节点个数有限，不妨假设子节点个数小于P，算法的时间复杂度为O（P×n）.找回相关函数结点时，算法的时间复杂度为O（（P-1）×n）.因此，整个算法的时间复杂度为O（n）.

1.3.2 空间复杂度：

算法占用的空间主要是一个字符型数组及2个整型数组的存储空间.

2 实验分析

为了检测算法的实际性能，选取5段不同的C语言源代码对算法进行测试，分别统计简化前后抽象语法树文件中的节点数目，并进行对比，对比结果如表1所示.

由表1可以看出，化简后结点数比原程序的精简，5个程序中抽象语法树文本中的结点化简率都达到了90%以上，说明该算法较好地删除了冗余信息，为后续的语法树分析提供了便利.

输入：通过gcc-fdump-translation-unit参数所产生的原文件的抽象语法树文本（*.tu 文件）

输出：简化的抽象语法树文本（result.tu文件）.

char str[M][N] //用来存储.tu文件中所有结点

int substr[K][L] //存储结点的所有子节点编号

int flag[Q]=0 /*用整型数组存储结点的标识（0表示unkown，1表示useless，2表示useful），初始状态所有结点设为unkown*/

for 0<=i< n //假定抽象语法树文本中有n个结点

if str[i] 有srcp字段

if srcp字段的值！=源文件名 then flag[i]==1 //找出useless结点

else if srcp字段的值==源文件名 then flag[i]==2 //找出useful结点

//将unkown结点转化为useless or useful结点

for 0<=i

//将父结点是useful的subNode，全部标识为useful

if（flag[i]==2）

for 0<=j

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

//将父结点是useless的子节点，全部标识为useless

else if（flag[i]==1）

for 0<=j

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

//找回相应子节点

for 0<=i

if str[i]有相关字段

then

for 1<=j< sum

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

3 结束语

提出了一种简化GCC抽象语法树文本的改进算法，为GCC抽象语法树文本删除了冗余信息，进而为后续利用抽象语法树检测重复代码的分析工作提供了便利.

参考文献：

[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].计算机科学，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] 田冰川，孙珂，巢汉青.简化GCC抽象语法树的新型算法 [J].计算机科学，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.

（责任编辑：包震宇）