程序流程图结构分析与识别技术的研究与实现

论文摘要

随着嵌入式领域中模型驱动开发技术的日益成熟和广泛应用，工程的开发效率及自动化程度被高度重视。其中代码自动生成技术将开发人员从繁琐的代码实现中解放出来使其最大程度的关注系统逻辑的设计，从而保证了系统设计的合理性、高效性和鲁棒性。针对程序流程图模型的代码自动生成技术，其难点在于流程图的结构分析与识别。本文基于结构化程序设计思想的原则，充分考虑流程图中半结构化和非结构化元素的特征，设计并实现了标准程序流程图的结构分析与识别算法。结构化流程图中基本控制结构之间形成了复杂的组合与嵌套关系。结合上下文结构信息，算法运用图论知识准确识别各个循环结构及分支结构，同时在条件判断结点识别算法中判断循环结构的类型。通过遍历循环结构寻找控制流的改变，算法识别出流程图中有continue、break和return含义的半结构化元素。针对非结构化流程图，本文提出了结构化验证规则，验证算法依此辨别出流程图中有GOTO含义的非结构化元素。本文参与实现的流程图代码自动生成工具经大量测试用例验证，能够正确识别流程图的结构组成和非结构化元素并生成含有半结构化语句的C程序代码。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 国内外研究现状
• 1.3 论文研究问题
• 1.4 本文研究工作
• 1.5 本文的组织结构
• 第二章 流程图代码自动生成相关技术
• 2.1 结构化程序设计
• 2.2 结构化程序流程图
• 2.2.1 程序流程图
• 2.2.2 结构化程序流程图
• 2.3 半结构化程序流程图
• 2.4 本章小结
• 第三章 程序流程图的结构分析与识别
• 3.1 循环结构的识别
• 3.1.1 流程图中循环结构的特征
• 3.1.2 流程图中的强连通分量
• 3.1.3 强连通分量的计算
• 3.1.4 强连通分量环路的消除
• 3.2 循环结构的类型判定
• 3.2.1 循环结构的条件判断结点
• 3.2.2 条件判断结点的真假分支
• 3.2.3 多个非根判断结点的区分
• 3.2.4 多个条件判断结点中 while 的确定
• 3.2.5 循环结构判定算法
• 3.2.6 强连通分量的环路消除算法
• 3.3 分支结构的识别
• 3.4 半结构化流程图元素的识别
• 3.4.1 continue 流程线的识别
• 3.4.2 break 和 return 流程线的识别
• 3.4.3 半结构化流程图元素的结构转化
• 3.5 本章小结
• 第四章 流程图的结构化验证及线性化处理
• 4.1 流程图的结构化验证
• 4.1.1 基本验证
• 4.1.2 控制结构之间的关系验证
• 4.2 流程图的线性化
• 4.2.1 循环结构的线性化
• 4.2.2 分支结构的线性化
• 4.3 本章小结
• 第五章 流程图结构分析与识别的实现
• 5.1 相关数据结构设计
• 5.1.1 流程图
• 5.1.2 循环结构强连通图
• 5.2 流程图结构分析与识别的实现
• 5.2.1 分析与识别的递归框架
• 5.2.2 非结构化错误处理
• 5.2.3 算法复杂度分析
• 5.3 流程图的代码自动生成实验
• 5.3.1 实验选取
• 5.3.2 实验结果
• 5.4 本章小结
• 第六章 结论与展望
• 6.1 本文工作总结
• 6.2 工作展望
• 致谢
• 参考文献
• 作者在读期间的研究成果