论文部分内容阅读
近年来,在线学习环境日益普及,逐渐作为一个常见手段应用在大学生程序设计教学中,但已有的在线编程系统只能判别提交程序的正误,不能给出错误原因并进行修正。因此,本文针对高校设立的Java程序设计课程的代码,研究了自动程序修复在学生程序中的应用。不同于工业界的缺陷程序具有近似正确、补丁小及大部分测试用例可通过等特点,含有缺陷的学生程序具有错误密度大、缺少关键语句等特点。工业界方法通过对比测试用例通过情况实现修复功能,但学生程序可能一个测试用例也不能通过,因此工业界方法并不适用于修复学生程序。学生程序代码规模较小,同一个题目作答人数多,可以采用提供模板的方法进行修复,从正确的学生程序中挖掘模板,使模板程序更具有多样性。但一个程序设计问题会存在多种解决方案,学生给出的答案在实现算法、正确性以及语法使用上都有可能存在差异,选择不同的模板程序作为示例程序,会直接影响缺陷程序修复的正确性和修复率。本课题使用了从在线编程系统中收集的大量正确的模板程序,这些数据中蕴含着“编程智慧”,可以为自动程序修复提供丰富的信息。针对上述问题,本文完成了以下工作:本文提出了模板程序的挖掘方法,解决了从大量实现相同功能的程序中挖掘模板的问题。首先利用程序的上下文信息对代码的多样性进行区分,区别出功能等价的程序是语法形式不同还是实现方式不同,然后使用聚类方法构建出模板程序集。最后在从赛码网上收集的程序进行了评估,评估表明实现93.4%的准确率。本文提出了动态执行和上下文分析相结合的变量映射的方法,解决了缺陷程序和示例程序中等价变量的问题。该方法不仅考虑了程序动态执行时变量的值序列,而且还考虑了变量的上下文信息,使变量的匹配更准确,从而提高程序的修复率。实验评估表明该方法比原方法的正确率提高了53.5%,达到了93.7%。本文提出了改进的遗传编程算法,解决了交叉策略不够灵活、选择进化的变异体过于相同和搜索空间爆炸的问题,使得生成的变异体的质量较高且更具有多样性,同时也加快了算法的收敛速度,最大可能性的选择通过不同测试用例的变异体。本文与原方法进行了比较,评估表明,改进后的方法从适应度和执行时间上都有提高,单一错误修复中,平均适应度达到了94.5%,执行时间为8.9秒。