基于线索抽象语法树的程序依赖图自动生成算法

基于线索抽象语法树的程序依赖图自动生成算法 Threaded Abstract Syntax Tree Based Generation Algorithm of Program Dependence Graph 易世界 YI Shijie 1 first-author 陈群辉 CHEN Qunhui 1 吕珊珊 L Shanshan 1 汤梦姿 TANG Mengzi 1 刘进 LIU Jin 1 黄勃 HUANG Bo 2 3 武汉大学软件工程国家重点实验室 武汉大学软件工程国家重点实验室 State Key Laboratory of Software Engineering,Wuhan University State Key Laboratory of Software Engineering,Wuhan University 武汉大学计算机学院 武汉大学计算机学院 School of Computer,Wuhan University School of Computer,Wuhan University 武汉大学深圳研究院 武汉大学深圳研究院 Shenzhen Research Institute,Wuhan University Shenzhen Research Institute,Wuhan University 提出了一种基于线索抽象语法树的程序依赖图自动生成算法,将代码的抽象语法树自动转换成为DOT语言表征的标准程序依赖图.该算法一方面通过在抽象语法树上自动标注表示程序语句流向的线索边,构建线索抽象语法树;另一方面将线索抽象语法树转换为标准程序依赖图.实验结果表明:中间模型线索抽象语法树的建立,可以减少转换过程中遍历树的次数,有效降低自动生成程序依赖图的时间复杂度. This paper presents a threaded abstract syntax tree based PDG（ program dependence graph） generation algorithm,automatically achieving the conversion from the abstract syntax tree（ AST） that is easy to get to the PDG with the form of DOT language. In the conversion process,to avoid the repeated traversal of the AST,this paper adds the thread edges that represent the possible flow of the program statements to the AST and constructs the threaded abstract syntax tree as a AST extension model,which reduces the time complexity of the algorithm. 程序依赖图 抽象语法树 线索边 自动生成 DOT语言 program dependence graph abstract syntax tree thread edge generation algorithm DOT language 10.14188/j.1671-8836.2015.02.002 TP311.11 国家自然科学基金（91118003,61003071）;深圳战略性新兴产业发展专项资金（JCYJ2012061613593612）资助项目;武汉大学2014年研究生自主科研项目（2014211020201） 2015-02-01 2021-03-31 2 61