基于后缀树的程序理解Plan自动提取  

Automatic extraction of software plans for program comprehension based on suffix trees

作　　者：陈华[1] 陈纯[1] 唐文彬[2] 钱剑飞[3] 刘康苗[1] 

机构地区：[1]浙江大学计算机科学与技术学院,浙江杭州310027 [2]中国计量学院信息分院,浙江杭州310018 [3]上海理工大学计算机工程学院,上海200093

出　　处：《浙江大学学报（工学版）》2008年第8期1340-1344,共5页Journal of Zhejiang University：Engineering Science

基　　金：国家自然科学基金资助项目(60573176);国家“973”重点基础研究发展规划资助项目(2007CB310900);浙江省重大科技专项资助项目(2006C11208)

摘　　要：为辅助维护用于程序理解的代码片段模版(Plan)库,提出了基于后缀树的Plan自动提取方法.通过词法/语法分析将源代码转换成Token串,然后对Token串生成后缀树,遍历后缀树得到候选代码Plan集,过滤后生成更小、更准确的Plan集.采用动态模式匹配合并合适的Plan和给Plan命名,最后生成可用于程序理解的Plan.由于后缀树的线性增长特性,该方法可以应用于大规模软件的程序理解.将方法应用于多个不同规模的软件,测试结果表明,该方法可以从源码中提取有效的Plan.A method of automatic plan extraction based on suffix trees was proposed to support the maintenance of software plan repositories for program comprehension, which are maintained by domain and computer science experts manually. The source codes were transformed into token strings after lexical and syntax analysis. The output token strings were used to construct a suffix tree, by traveling through which, a set of candidates of software plans was obtained. Filters were applied to the set to obtain a much smaller set. A dynamic pattern matching algorithm was finally applied to the set to merge suitable candidate plans and name them. The time and space requirements are linear to the size of nodes in suffix trees. The method can be applied to large scale software. Test results of applying the method to some software with different sizes show that it can extract valid plans from source code.

关 键 词：程序理解 后缀树 软件维护 软件工程 

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