GCC抽象语法树的解析及控制依赖子图的建立方法研究

论文摘要

在程序设计语言考试中,编程题自动评分是一项具有实用价值的应用,它是实现在线考试功能的一个关键技术,由于它涉及到多方面的理论和知识,因而成为一个难点。目前,还有一些技术问题需要解决。一是无法对有语法错误的程序进行自动评分;二是分析规模较大程序能力较弱。针对这两个问题,在深入研究已出现的评分模型和现有评分系统的基础上,通过引入当前功能比较强大的编译器GCC(GNU C complier)改善现有系统前端的方式来解决以上两个问题。本文首先对GCC的输出——文本抽象语法树做了详细的研究并提出了GCC抽象语法树解析的定义和与之相关的定义,这一部分是本文的理论基础;其次,在深入研究了几种常见的静态编程题自动评分模型的基础上,提出了基于GCC的C程序自动评分模型;再次,提出了消除文本抽象语法树中冗余信息的算法并给出了算法复杂性分析,实验结果证明该算法取得了提高了GCC抽象语法树解析的时空效率。最后提出了将文本抽象语法树转化为邻接表形式的抽象语法树的算法和控制依赖子图的构建算法,较好完成了系统前端的构建。实验部分的目标是将新前端和原系统的后端连接形成一个新系统,本文给出了连接过程的总体流程和阶段性的结果,然后针对若干实验程序给出了新前端产生的控制依赖子图,实验证明新前端具有良好的适用性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题来源、研究背景和意义
• 1.2 国内外研究现状
• 1.3 本文的主要研究内容和章节安排
• 第2章 GCC 文本抽象语法树
• 2.1 GCC 及其工作流程
• 2.2 文本抽象语法树的结构特性
• 2.2.1 GCC 语法分析输出—抽象语法树
• 2.2.2 文本抽象语法树中的结点
• 2.2.3 重要字段说明
• 2.2.4 文本抽象语法树的结构特性
• 2.2.5 文本抽象语法树解析的含义
• 2.2.6 抽象语法树相关定义及补充
• 2.3 本章小结
• 第3章 GCC 文本抽象语法树的解析及控制依赖子图的生成
• 3.1 基于GCC 的C 程序自动评分模型
• 3.2 GCC 文本抽象语法树中冗余信息消除算法
• 3.2.1 消除冗余的原因
• 3.2.2 算法的基本思想
• 3.2.3 算法的详细描述
• 3.2.4 算法的复杂度分析
• 3.2.5 实验分析
• 3.3 邻接表形式的抽象语法树的建立算法及实现
• 3.3.1 编号映射
• 3.3.2 消除字段冗余
• 3.3.3 存储结构设计
• 3.3.4 算法的基本思想与详细描述
• 3.3.5 算法的复杂度分析
• 3.3.6 实验分析
• 3.4 程序的中间表示——系统依赖图
• 3.5 控制依赖子图的生成算法及实现
• 3.5.1 算法的基本思想
• 3.5.2 算法的详细描述
• 3.5.3 算法复杂性分析
• 3.5.4 实验分析
• 3.5.5 完成对整个程序控制依赖子图的构建
• 3.6 系统依赖图的构建算法及实现
• 3.6.1 建立系统依赖图的一般步骤
• 3.6.2 求到达-定值信息
• 3.6.3 REF 集合和DEF 集合
• 3.6.4 求GEN 集合和KILL 集合
• 3.6.5 求IN 集合和OUT 集合
• 3.6.6 建立数据流边
• 3.6.7 实验分析
• 3.7 本章小结
• 第4章 系统测试与分析
• 4.1 新旧系统的连接
• 4.2 实验数据
• 4.3 对新前端进行测试
• 4.4 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢