基于抽象语法树的编程题自动评分系统的研究与应用

摘要

近年来,随着在线考试系统的推广和流行,针对计算机自动评分技术的应用研究已迅速地发展并成熟起来。但是,目前大多数的在线考试系统,由于无法或不能很好地实现对主观题的评分,在试题选择方面进行了限制,只抽取一些客观题进行测试,而忽略了对主观题特别是能够真正测试学生编程能力的编程题的考查。因此,对编程题进行自动评分已成为目前自动评分领域的研究热点,具有理论和现实意义。
　　 目前,大多数的研究都将系统依赖图作为程序的中间表示形式,将考生程序和答案程序转换为这种中间形式,然后在此基础上进行评分。但由于抽象语法树较系统依赖图存储效率高、易于遍历和操作,且更适合表达式的语法结构,本文采用抽象语法树作为程序的中间表示,在此基础上对考生程序进行分析,并模拟人工评分的思路,提出了基于抽象语法树的编程题自动评分的解决方案。
　　 该方案在抽象语法树的基础上,运用本文给出的表达式和控制结构的标准化规则,对程序中的表达式和控制结构进行标准化,以消除代码的多样化,减少答案模板的数量。同时,本文运用基于结点权值的树编辑距离算法对经过标准化的考生程序和答案程序对应的抽象语法树进行表达式和控制结构的匹配,计算它们的相似度,以此作为考生程序最后得分的重要依据。此外,本文还结合编译原理中的词法分析和语法分析对考生程序进行词法和语法错误检测,并将其作为考生程序得分的依据之一。
　　 最后,对本方案进行了实验验证,通过将其应用于C语言考试系统的编程题模块中,验证了该方案的可行性和评分结果的合理性。

目录

文摘

英文文摘

第1章 绪论

1.1 课题的研究背景及意义

1.1.1 课题的研究背景

1.1.2 课题的研究意义

1.2 国内外研究现状

1.2.1 国外研究现状

1.2.2 国内研究现状

1.3 主要研究内容

1.4 论文的组织结构

第2章 课题相关的理论基础

2.1 编译原理的基础知识

2.1.1 文法定义

2.1.2 词法分析

2.1.3 语法分析

2.2 抽象语法树

2.2.1 抽象语法树

2.2.2 抽象语法树的遍历

2.3 程序代码相似度计算

2.3.1 基于属性计数的方法

2.3.2 基于结构度量的方法

2.4 字符串文本匹配算法

2.4.1 蛮力匹配算法

2.4.2 KMP算法

2.4.3 BM算法

2.5 树编辑距离算法

2.5.1 树编辑距离

2.5.2 树编辑距离算法

第3章 基于抽象语法树的评分方案及程序标准化

3.1 常用的编程题自动评分模型

3.1.1 基于语义相似度的评分模型

3.1.2 基于程序理解的评分模型

3.2 基于抽象语法树的编程题自动评分的解决方案

3.3 表达式的标准化

3.3.1 算术表达式标准化

3.3.2 逻辑表达式标准化

3.3.3 关系表达式标准化

3.4 控制结构的标准化

3.4.1 选择结构的标准化

3.4.2 循环结构的标准化

第4章 错误检测及基于结点权值的程序匹配

4.1 C语言程序错误类型

4.2 语法错误

4.2.1 司法分析阶段的错误检测

4.2.2 语法分析阶段的错误检测

4.3 应用树编辑距离进行树匹配

4.4 基于结点权值的树编辑距离算法

第5章 系统设计、实现与实验结果分析

5.1 系统设计

5.1.1 系统的体系结构

5.1.2 系统的功能模块设计

5.1.3 数据库设计

5.2 系统实现

5.2.1 用户登录模块的实现

5.2.2 试题信息维护模块的实现

5.2.3 编程题答题模块的实现

5.2.4 编程题评分模块的实现

5.3 实验及结果分析

第6章 总结与展望

6.1 总结

6.2 展望

参考文献

致谢