基于关键词Trie树的GCC抽象语法树消除冗余算法  

Deduplication Algorithm of Abstract Syntax Tree in GCC Based on Trie Tree of Keywords

作　　者：韩磊 胡建鹏[1] HAN Lei;HU Jian-peng(School of Electronic and Electrical Engineering,Shanghai University of Engineering Science,Shanghai 201620,China)

机构地区：[1]上海工程技术大学电子电气工程学院,上海201620

出　　处：《计算机科学》2020年第9期47-51,共5页Computer Science

基　　金：国家自然科学基金项目(61802252);上海工程技术大学金课培育项目(DQY19004)。

摘　　要：GCC(GNU Compiler Collection)编译器编译C语言源程序所生成的抽象语法树文本中包含大量与源代码无关的冗余信息,若直接进行解析,会严重影响分析效率,降低分析精确度,同时会占用大量存储空间。针对此问题,提出一种基于关键词Trie树的GCC抽象语法树消除冗余算法,其根据包含抽象语法树文本有用信息节点的关键词建立Trie树,可实现对抽象语法树文本无用节点的过滤,从而达到优化编译的效果。相比传统KMP消除冗余算法,关键词Trie树算法可以有效避免去冗余过程中常量、变量等有用信息节点的丢失,确保数据的完整性;同时,关键词Trie树算法可以最大限度地减少重复前缀或后缀字符串的比较次数,节省了时空开销。挑选不同长度的C语言源码文件进行去冗余实验,测试该算法的性能,并将其与传统KMP算法进行对比。实验结果表明,所提算法的去冗效率和查准率均得到了极大的提高。The abstract syntax tree text generated by GCC compiler compiling C language source program contains a lot of redundant information independent of source code.If directly parsed,it will seriously affect the analysis efficiency,reduce the analysis accuracy,and occupy a large amount of storage space.Aiming at this problem,a GCC abstract syntax tree elimination redundancy algorithm based on the keyword Trie tree is proposed.The Trie tree is built according to the keywords containing the abstract syntax tree text useful information nodes,which can filter the useless node information of the syntax tree text,thus achieving optimized compilation results.Compared with the traditional KMP redundancy elimination algorithm,the keyword Trie tree algorithm can effectively avoid the loss of useful information nodes such as constants and variables in the process of redundancy removal and ensure the integrity of data.At the same time,the keyword Trie tree algorithm can minimize the comparison of repeated prefixes or suffix strings,saving time and space overhead.This paper selects different lengths of C language source files for de-redundancy experiments,tests the performance of the algorithm,and compares it with the traditional KMP algorithm.The experimental results show that the algorithm can greatly improve the redundancy efficiency and precision.

关 键 词：GCC 抽象语法树 关键词Trie树 优化编译 KMP 消除冗余 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]