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

Program comprehension oriented construction algorithm of system dependence graph

摘要:

为降低程序理解中的程序标准化和程序匹配等复杂度,提出了面向程序理解的系统依赖图构建算法,将其划分为3个阶段:程序信息的提取、控制依赖子图的构建和数据依赖子图的构建．采取控制依赖和数据依赖分别求解,直接基于控制依赖子图分析数据流,无需额外的控制流图表示,并且可按需计算数据流,降低了算法复杂度;将选择语句和循环语句统一表示,并将表达式表示为抽象语法树,使之便于程序转换和分析．在编程题自动评分系统和程序识别中的应用中结果表明构建的系统依赖图为程序理解和分析提供了方便,降低了复杂度．

Abstract:

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.