面向程序理解的系统依赖图构建算法  

Program comprehension oriented construction algorithm of system dependence graph

作　　者：王克朝[1,2] 王甜甜[1] 苏小红[1] 马培军[1] 童志祥[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001 [2]哈尔滨学院软件学院,哈尔滨150086

出　　处：《哈尔滨工业大学学报》2013年第1期78-84,共7页Journal of Harbin Institute of Technology

基　　金：国家自然科学基金资助项目(61202092;61173021);高等学校博士学科点专项科研基金资助项目(20112302120052);中央高校基本科研业务费专项资金资助项目(HIT.NSRIF.201178);黑龙江省高教学会"十二五"重点规划课题资助项目(HGJXH B1110957)

摘　　要：为降低程序理解中的程序标准化和程序匹配等复杂度,提出了面向程序理解的系统依赖图构建算法,将其划分为3个阶段:程序信息的提取、控制依赖子图的构建和数据依赖子图的构建.采取控制依赖和数据依赖分别求解,直接基于控制依赖子图分析数据流,无需额外的控制流图表示,并且可按需计算数据流,降低了算法复杂度;将选择语句和循环语句统一表示,并将表达式表示为抽象语法树,使之便于程序转换和分析.在编程题自动评分系统和程序识别中的应用中结果表明构建的系统依赖图为程序理解和分析提供了方便,降低了复杂度.To reduce the complexity of program comprehension such as program standardization and program matching,a program comprehension oriented construction algorithm of system dependence graph is proposed.This algorithm can be divided into three stages： program information extraction,control dependence sub-graph construction and data dependence sub-graph construction.Control dependency and data dependency are independently computed.Data flow is directly analyzed based on control dependent sub-graph without extra control flow graph,and computed on demand,which reduces the algorithm complexity.Selection statements and loop statements are uniformly represented,and expressions are represented as Abstract syntax trees,which can facilitate program transformation and analysis.The system dependence graph has been used in automatic grading system of student programs and program recognition.Application results show that it can facilitate program comprehension and analysis and reduce the complexity of program comprehension and analysis.

关 键 词：程序理解 系统依赖图 程序信息提取 控制依赖 数据依赖 

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