（计算机科学与技术专业论文）基于抽象语法树的编程题自动评分系统的研究与应用.pdf

7 t h er e s e a r c ha n d a p p l i c a t i o no f a u t o m a t i cs c o r i n gs y s t e m b a s e do na b s t r a c ts y n t a xt r e e at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g b y c h e ny u a n y u a n ( c o m p u t e rs c i e n c ea n dt e c h n o l o g y ) t h e s i ss u p e r v i s o r ：p r o f e s s o rl iy a n h e n g m a y 2 0 1 1 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博硕士学位论文= = 基王垫筮适洼挝鲍缠猩题自麴透筮丕红数硒塞当廛旦= = 。 除论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体 已经公开发表或未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名：硇亟亟 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论 文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式 出版发行和提供信息服务。保密的论文在解密后遵守此规定。 不保密口( 请在以上方框内打“ ) 论文作者签名：硌皿渡导师签名：季够斫 日期：1 年7 月z 日 中文摘要 摘要 近年来，随着在线考试系统的推广和流行，针对计算机自动评分技术的应用 研究已迅速地发展并成熟起来。但是，目前大多数的在线考试系统，由于无法或 不能很好地实现对主观题的评分，在试题选择方面进行了限制，只抽取一些客观 题进行测试，而忽略了对主观题特别是能够真正测试学生编程能力的编程题的考 查。因此，对编程题进行自动评分已成为目前自动评分领域的研究热点，具有理 论和现实意义。 目前，大多数的研究都将系统依赖图作为程序的中间表示形式，将考生程序 和答案程序转换为这种中间形式，然后在此基础上进行评分。但由于抽象语法树 较系统依赖图存储效率高、易于遍历和操作，且更适合表达式的语法结构，本文 采用抽象语法树作为程序的中间表示，在此基础上对考生程序进行分析，并模拟 人工评分的思路，提出了基于抽象语法树的编程题自动评分的解决方案。 该方案在抽象语法树的基础上，运用本文给出的表达式和控制结构的标准化 规则，对程序中的表达式和控制结构进行标准化，以消除代码的多样化，减少答 案模板的数量。同时，本文运用基于结点权值的树编辑距离算法对经过标准化的 考生程序和答案程序对应的抽象语法树进行表达式和控制结构的匹配，计算它们 的相似度，以此作为考生程序最后得分的重要依据。此外，本文还结合编译原理 中的词法分析和语法分析对考生程序进行词法和语法错误检测，并将其作为考生 程序得分的依据之一。 最后，对本方案进行了实验验证，通过将其应用于c 语言考试系统的编程题 模块中，验证了该方案的可行性和评分结果的合理性。 关键词：自动评分；抽象语法树；表达式标准化；控制结构标准化；树编辑距离 英文摘要 a b s t r a c t i nr e c e n ty e a r s ，谢t 1 1t h ep r o m o t i o na n dp o p u l a r i t yo ft h eo n l i n ee x a m i n a t i o n s y s t e m ，t h ea p p l i e dr e s e a r c ha b o u ta u t o m a t i cs c o r i n gt e c h n o l o g yh a sr a p i d l yd e v e l o p e d a n db e c o m em a t u r e h o w e v e r , a tp r e s e n t ，m o s to ft h eo n l i n ee x a m i n a t i o ns y s t e m s ， w h i c ha r eu n a b l et og i v eag o o ds c o r eo nt h es u b j e c t i v ei t e m s ，c o n f i n e st h et y p e so f e x a m i n a t i o nq u e s t i o n si nt h eo b j e c t i v ei t e m s ，w h i l eo v e r l o o k i n gt h et e s to fs u b j e c t i v e i t e m sa n dp r o g r a m m i n gq u e s t i o ni np a r t i c u l a r , w h i c hc a nt r u l yr e f l e c ts t u d e n t s p r o g r a m m i n gs k i l l s t h e r e f o r e ，t h er e s e a r c ha b o u ta u t o m a t i cs c o r i n go np r o g r a m m i n g q u e s t i o nh a sb e c o m et h er e s e a r c hh o t s p o ti nt h ef i e l do fa u t o m a t i cs c o r i n g ，a n di t h a s t h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e c u r r e n t l y , i nt h em a j o r i t yo ft h es t u d y , r e s e a r c h e r ss e l e c tt h es y s t e md e p e n d e n c e g r a p ha st h ei n t e r m e d i a t er e p r e s e n t a t i o no ft h ep r o g r a m ，a n dt r a n s l a t et h es t u d e n t s p r o g r a ma n da n s w e rp r o g r a mi n t ot h i si n t e r m e d i a t ef o r m ，a n dt h e nt og r a d eo nt h i sb a s i s h o w e v e r , t h ea b s t r a c ts y n t a x t r e eh a sh i g h e r s t o r a g ee f f i c i e n c yt h a n t h es y s t e m d e p e n d e n c eg r a p h ，a n di t se a s i e rt ot r a v e r s ea n do p e r a t e ，a n dm o r es u i t a b l ef o rt h e r e p r e s e n t a t i o no fe x p r e s s i o n ，t h i sp a p e ru s e st h ea b s t r a c ts y n t a xt r e ea st h ei n t e r m e d i a t e r e p r e s e n t a t i o no ft h ep r o g r a m a n dt h i st h e s i sp u t sf o r w a r das o l u t i o nt oa u t o m a t i c s c o r i n gp r o g r a m m i n gq u e s t i o nb a s e do na b s t r a c ts y n t a xt r e e ，b yw h i c hw ea n a l y s i st h e s t u d e n t sp r o g r a mo nt h eb a s i so fa b s t r a c ts y n t a xt r e e ，a n ds i m u l a t et h ei d e ao fa r t i f i c i a l r a t i n g b a s e do nt h ea b s t r a c ts y n t a xt r e e ，t h i sm e t h o du s e st h es t a n d a r d i z e dr u l e so f e x p r e s s i o na n dc o n t r o ls t r u c t u r e s ，w h i c hh a s l a i dd o w ni nt h i st h e s i s ，s t a n d a r d i z e e x p r e s s i o n sa n dc o n t r o ls t r u c t u r e si nt h ep r o c e d u r e ，t oe l i m i n a t et h ed i v e r s i t yo ft h e c o d ea n dr e d u c et h en u m b e ro ft h ea n s w e rt e m p l a t e a tt h es a m et i m e ，t h i sp a p e ra p p l i e s t h et r e ee d i td i s t a n c ea l g o r i t h mb a s e do nn o d ew e i g h t st om a t c ht h ee x p r e s s i o na n d c o n t r o ls t r u c t u r ei nt h es t a n d a r d i z e da b s t r a c ts y n t a xt r e e so ft h es t u d e n t sp r o g r a ma n d t h ea n s w e rp r o g r a ma n dc a l c u l a t et h es i m i l a r i t yb e t w e e nt h es t u d e n t sp r o g r a ma n d t h ea n s w e rp r o g r a m i tu s e st h es i m i l a r i t yb e t w e e nt h et w op r o g r a m sa sa ni m p o r t a n t b a s i sf o rt h es t u d e n t s f i n a ls c o r e f u r t h e r m o r e ，t h i sp a p e rd e t e c t st h el e x i c a le r r o ra n d s y n t a xe r r o ro f t h es t u d e n t sp r o c e d u r eb yt h el e x i c a la n a l y s i sa n ds y n t a xa n a l y s i si nt h e 英文摘要 c o m p i l e rp r i n c i p l e ，w h i c hi sm a d e 嬲o n eo ft h eb a s e sf o rt h e s c o r eo ft h es t u d e n t s p r o g r a m f i n a l l y , t h es c o r i n gm e t h o dh a sb e e nv e r i f i e db y t h ee x p e r i m e n t t h ec o r r e c t n e s s a n df e a s i b i l i t yo ft h em e t h o di sv e r i f i e di nt h i se x p e r i m e n t ，w h i c hu s e st h i sm e t h o di n t h ep r o g r a m m i n g q u e s t i o nm o d u l eo f t h ecl a n g u a g ee x a m i n a t i o ns y s t e m k e yw o r d s ：a u t o m a t i cs c o r i n g ；a b s t r a c ts y n t a xt r e e ；e x p r e s s i o ns t a n d a r d i z a t i o n ； c o n t r o ls t r u c t u r es t a n d a r d i z a t i o n ；t r e ee d i td i s t a n c e ； 目录 目录 第1 章绪论1 1 1 课题的研究背景及意义1 1 1 1 课题的研究背景1 1 1 2 课题的研究意义2 1 2 国内外研究现状2 1 2 1 国外研究现状2 1 2 2 国内研究现状4 1 3 主要研究内容。5 1 4 论文的组织结构6 第2 章课题相关的理论基础8 2 1 编译原理的基础知识。8 2 1 1 文法定义8 2 1 2 词法分析9 2 1 3 语法分析9 2 2 抽象语法树1 0 2 2 1 抽象语法树1 0 2 2 2 抽象语法树的遍历1 2 2 3 程序代码相似度计算1 3 2 3 1 基于属性计数的方法1 3 2 3 2 基于结构度量的方法1 4 2 4 字符串文本匹配算法1 4 2 4 1 蛮力匹配算法1 4 2 4 2k m p 算法15 2 4 3b m 算法。1 5 2 5 树编辑距离算法1 6 2 5 1 树编辑距离1 6 2 5 2 树编辑距离算法17 第3 章基于抽象语法树的评分方案及程序标准化1 9 3 1 常用的编程题自动评分模型1 9 3 1 1 基于语义相似度的评分模型1 9 3 1 2 基于程序理解的评分模型1 9 目录 3 2 基于抽象语法树的编程题自动评分的解决方案2 0 3 3 表达式的标准化2 2 3 3 1 算术表达式标准化2 3 3 3 2 逻辑表达式标准化2 6 3 3 3 关系表达式标准化：2 8 3 4 控制结构的标准化2 8 3 4 1 选择结构的标准化2 9 3 4 2 循环结构的标准化一3 0 第4 章错误检测及基于结点权值的程序匹配3 3 4 1c 语言程序错误类型3 3 4 2 语法错误3 4 4 2 1 词法分析阶段的错误检测3 4 4 2 2 语法分析阶段的错误检测3 5 4 3 应用树编辑距离进行树匹配3 6 4 4 基于结点权值的树编辑距离算法3 8 第5 章系统设计、实现与实验结果分析4 2 5 1 系统设计4 2 5 1 1 系统的体系结构4 2 5 1 2 系统的功能模块设计4 3 5 1 3 数据库设计4 5 5 2 系统实现5 0 5 2 1 用户登录模块的实现5 0 5 2 2 试题信息维护模块的实现5 3 5 2 3 编程题答题模块的实现5 4 5 2 4 编程题评分模块的实现5 6 5 3 实验及结果分析6 0 第6 章总结与展望6 5 6 1 总结6 5 6 2 展望6 6 参考文献6 7 致 射7 1 基于抽象语法树的编程题自动评分系统的研究与应用 1 1 课题的研究背景及意义 第1 章绪论 1 1 1 课题的研究背景 在当今网络信息技术高速发展的时代，网络信息技术的应用极大地方便了人 们的生活和工作，同样，它也给学校教育带来了翻天覆地的变化，从多媒体教学 到远程网络教学，从传统化的纸质考试到在线考试系统，在很大程度上既方便了 大家的学习和工作，又节省了人力、物力和财力，同时还提高了工作效率。因此， 在很多高校，在线考试系统受到了师生的热烈欢迎，并且成为目前比较流行的考 试方式。 在线考试系统涉及到许多关键性的技术问题，比如：组卷策略、大规模的并 发访问和自动评分技术【l 】等，其中，自动评分技术能较大程度地节省劳动力、提高 效率，同时，也能方便学生快速地查看考试成绩。 在自动评分中，针对不同类型的试题，其相应的评分机制也不同，如：客观 题，只需要考生从已经拟定了的几个答案中辨认出正确答案即可，而无需考生自 己编写答案，不需要考生的主观考虑，因此对这类试题的评分简单且易于实现， 应用一般的“模式匹配”算法即可完成。而对于主观题的评分则不同，因为考生 所作的答案中掺杂有自己的主观因素或情感在里面，特别是程序设计类试题，其 中还包含有考生的算法设计，因此在评分中需要对考生所做答案的语义或者结构 等进行分析，其难度较大，实现起来比较复杂。 因此，目前国内的一些针对程序设计语言的考试系统，大多以客观题的考查 形式为主，如：判断题、选择题，也有一些系统实现了对编程题的考查和评分， 但结果还不尽如人意。例如：现有国家计算机等级考试上机考试( - - 级c 语言) 中的程序设计题，是直接根据结果文件的情况评分，如果结果正确给满分，否则， 给。分；而这不但不符合人工评分的思路，而且也是不合理的。为解决上述问题， 开展对编程题自动评分的研究也就应运而生。 第1 章绪论 1 1 2 课题的研究意义 本课题研究具有以下实际意义： ( 1 ) 节省人力、物力和财力，提高工作效率 传统的人士评分需要组织相关教师手动批改试卷，而且随着考生人数的增加， 这将大大增加教师的工作量，且效率较低。而自动评分的应用则减少了相关工作 量，将教师从繁重的手工批卷中解放出来，大大提高了工作效率，并且节省了资 源。 ( 2 ) 评分结果更具有客观性、公正性 在进行人工评分时，由于某些原因，可能会出现误判的情况，而且对于主观 试题的评分，可能会因掺杂有阅卷人的主观因素，而影响评分的客观性。自动评 分则会根据事先设定的评分标准及评分流程对考生答案进行客观公正的评分，避 免因人为原因导致的评分误差。 ( 3 ) 方便学生快速查看成绩，获得反馈信息 通过自动评分，考生可以及时地查看成绩，得到反馈信息，并根据此信息， 强化对某些知识点的学习运用，快速提高学生的编程能力。 同时，本课题来源于“计算机程序设计基础( c ) 考试方式的改革 中对于编程 题考试方式的改革这一校教改项目，因此，研究并实现一种针对编程题的自动评 分方案，以实现程序设计语言类考试的全过程自动化，是非常具有现实意义的。 1 2 国内外研究现状 1 2 1 国外研究现状 在2 0 世纪6 0 年代，国外就有一些专家和学者开展了对计算机自动评分的研 究，他们试图使用计算机对那些用自然语言书写的文章进行评分2 1 ，其中，最早实 现这一功能的是p r o j e c te s s a yg r a d e ( p e g ) 系统 3 1 ，它由e l l i sp a g e 于1 9 6 6 年开发， 他认为每个人的写作风格中都蕴含有其内在的特征，而这些内在特征可以被量化， 通过对这些特征进行量化并使其能在计算机内进行表示和计算，然后模仿人工评 分的过程对这些已量化的特征进行评分即可。 在随后几十年的研究与开发中，相继出现了一批针对不同领域的评分系统， 基于抽象语法树的编程题自动评分系统的研究与应用 它们中有一些已经投入实际应用，并且取得了很好的效果。 ( 1 ) l a t e n ts e m a n t i ca n a l y s i s ( l s a ) 该系统【4 5 】适合对大规模的文本进行相似度度量，它将每个文本看作一个空间 向量，通过计算各文本对应的向量之间的相似度来实现对待批改文本的评分。由 于系统运用的是类似信息检索技术中文档相似度的计算方法，所以该系统不适合 于对规模小、数据稀疏的文本进行评分。 ( 2 ) a u t o m a t e dt e x tm a r k c r ( a t m ) 该系统6 1 能分别对标准答案和学生答案进行分解，生成最小的可独立存在的概 念，分析比较概念间的依赖关系，然后通过对标准答案和学生答案二者的依赖关 系进行模式匹配，最后根据匹配情况进行评分。同时，系统提供的交互式语法分 析器和语义分析器，能建立一种对应自然语言的语义结构模型，真正实现基于语 义的自动评分。 ( 3 ) a u t o m a r k 该系统【刀是为解决开放性问题的自动评分而设计开发的，它将每个问题都视为 一个不同的领域，而文本中与该领域相关的概念即为该问题的正确答案。系统针 对不同问题设计不同的评分模式，并且对学生答案进行语法预处理和句子解析， 最后对经过处理后的学生答案和评分模式进行匹配，由匹配结果给出学生答案的 最后得分。 在进行主观题自动评分研究的同时，对程序自动评估技术的研究也慢慢地开 展起来。早在1 9 6 0 年，h o l l i n g s w o r t h 8 】就开发了一个针对穿孔卡片的汇编语言进 行自动评分的系统，同时他也是最早开始研究此类问题的领军人。随后，开始出 现了一些针对程序进行自动评分的系统。例如： ( 1 ) b o s s b o s s 系统【明是一个用于对网上提交的程序作业进行评分的系统，为防止系统 中某项功能出错时影响其他功能的正常运行，它将提交作业、评分和测试划分到 不同的服务器上。虽然该系统能够自动完成对作业的评估，并给出一个供教师参 考的考核参数，但最终的分数仍然需要人工参与决定，所以它是一个半自动化的 评分系统。 第1 章绪论 ( 2 ) a s a p a s a p 系统在程序提交后，为其选择一个合适的测试程序，然后针对源程序 运行该测试程序，最后根据测试结果进行评分。因为该系统需要动态运行源程序， 所以对存在问题而不能正常运行的源程序无法进行评价，因此，该评分结果是不 太合理的。 此外，还有许多针对不同程序设计语言的程序自动评分系统，如：w a g s 1 1 】、 c o u r s em a s t e r t l 2 1 和a n a l y s i s 1 3 1 等。但通过对这些系统进行研究，发现其采用的评分 方法大致可以分为两类【1 4 】：动态评分方法和静态评分方法。 ( 1 ) 动态评分 动态评分是指通过对源程序进行编译链接，选择一组特殊的数据对其进行测 试，然后根据其运行结果和答案提供的运行结果进行比较，最后根据两者之间的 比较结果来给出最后得分。但是由于学生程序常常存在一些词法或者语法错误， 而不能正常的编译运行，从而造成系统给出0 分的结果，这完全不符合人工评分 的思路，同时也是不合理的。因此将动态评分方法用于对学生程序进行评分是不 太合适的。 ( 2 ) 静态评分 静态评分方法是指不需要运行源程序，通过程序理解、语义分析或软件质量 度量等方法对源程序进行静态分析。运用软件质量度量的方法是根据程序中指定 的一些特征指标，如：模块长度、标识符长度、数据流和控制流等，综合起来对 源程序进行评分，但是该方法在对源代码进行分析时没有分析程序的语义；而运 用程序理解和语义分析的方法虽然更适合对编程题进行评分，但实现起来难度较 大，所提出的模型还不够完善。 同时，也出现了一些比较新颖的静态代码分析方法，如r a h m a n 等提出的将c 程序代码转换成伪代码 1 5 1 后，通过对源程序和答案程序的伪代码进行比较来评分。 1 2 2 国内研究现状 国内在针对主观题或者编程题的评分技术方面的研究起步较晚，相关文献也 不多，真正实用且效果较好的系统则更少。 基于抽象语法树的编程题自动评分系统的研究与应用 张量等【1 6 1 利用组件编程、智能匹配等技术实现了对计算机基础上机考试中 w o r d 、e x c e l 和p o w e n p o i n t 操作题的评分，该系统使用v b 和v c + + 语言混合编程 实现，主要应用动态规划算法对文本中的字符进行匹配。 王邯等【1 7 】通过研究实现了c 语言程序设计填空题的计算机自动评分。该系统 主要是应用编译原理中的词法分析和语法分析对考生程序进行分析优化，并且对 答案程序进行分解并生成语义等价类，然后在此基础上对考生程序和等价的答案 程序进行匹配，根据匹配结果给出最终得分。该系统虽然是针对填空题进行评分， 但其中的某些思想可以借鉴到编程题评分中。 随着近年来软件技术的高速发展，对拥有编程实践能力的人才的需求不断增 加，努力提高学生的编程能力对于高校计算机类教学的发展而言，其社会价值和 意义不言而喻，为满足此需求，出现了许多程序自动评分系统。如：全国计算机 等级考试上机考试中的程序设计题的评分就是采用计算机自动评分的方式，该系 统仅仅根据考生程序的运行结果进行评分，忽略了考生程序中可能也有部分代码 鼍 或语句正确的情况，不符合人工阅卷的思路。 又如针对v b 程序的自动评分系统【1 8 】，该系统和全国计算机等级考试系统类 似，主要是根据程序运行结果和一些界面参数进行评分。 1 3 主要研究内容 为解决编程题的自动评分问题，本文采用抽象语法树作为程序的中间表示， 在此基础上对程序进行标准化，并运用基于结点权值的树编辑距离算法对考生程 序和答案程序的抽象语法树进行相似度匹配，同时结合错误检测和结果文件评分 情况，模拟人工评分的思路进行评分。 本文的主要研究内容如下： ( 1 ) 研究常用的编程题自动评分方法和评分模型 对常用的编程题自动评分方法和评分模型进行深入研究，分析比较其各自的 优缺点，并在此基础上进行改进，提出基于抽象语法树的编程题自动评分的解决 方案。 ( 2 ) 研究编译原理中的词法分析、语法分析和中间代码表示技术，重点掌握抽 第1 章绪论 象语法树的生成和遍历方法 在本文中词法分析和语法分析是生成抽象语法树的基础，同时借鉴词法分析 和语法分析阶段的错误检测办法，对考生程序中的错误进行统计处理，为最后的 综合评分提供依据。 ( 3 ) 研究程序标准化 在抽象语法树的基础上研究程序标准化问题，如：表达式的标准化、控制结 构的标准化，给出表达式和控制结构标准化规则，对考生程序和答案程序的抽象 语法树进行表达式和控制结构的标准化，以达到消除程序多样化和减少模板程序 数量的目的。 ( 4 ) 研究树编辑距离算法，并结合结点权值对程序进行匹配 研究树编辑距离算法，在此基础上结合结点权值，运用基于结点权值的树编 辑距离算法对考生程序和模板程序对应的抽象语法树进行相似度匹配计算。 ( 5 ) 系统设计、实现及验证 设计实现基于抽象语法树的编程题评分系统，并将其应用到c 语言程序设计 考试系统中，验证评分方案的实用性、合理性和准确性。 1 4 论文的组织结构 本文分为六章，其组织结构如下： 第1 章绪论。通过介绍该课题的背景及意义，分析国内外研究现状，确定了 本文需要解决的问题和主要的研究内容。 第2 章课题相关的理论基础。主要介绍与本文相关的一些理论知识，如：编 译原理、抽象语法树、程序相似度计算方法、模式匹配和树编辑距离算法等。 第3 章基于抽象语法树的评分方案及程序标准化。根据对常用的评分模型的 分析，改进并提出了基于抽象语法树的评分方案，并给出了对程序中表达式和控 制结构进行标准化转换的规则。 第4 章错误检测及基于结点权值的程序匹配。对考生程序中一些常见的语法 错误的检测及处理方案进行介绍，对原有的树编辑距离算法和基于结点权值的树 编辑距离算法进行介绍、分析，并将其应用到对考生程序和答案程序对应的抽象 基于抽象语法树的编程题自动评分系统的研究与应用 语法树的相似度匹配计算中。 第5 章系统设计、实现与实验结果分析。设计实现编程题评分系统，并进行 实验，通过对实验结果进行分析，验证评分的准确性和合理性。 第6 章总结与展望。对论文中所做的工作进行总结，并对将来的进一步工作 确定研究方向。 第2 章课题相关的理论基础 第2 章课题相关的理论基础 编程题评分是一个复杂的过程，不同于普通的客观题评分，只需要进行简单 的字符匹配即可，它涉及到编译原理、模式匹配等各方面的知识。本章主要介绍 与课题相关的理论知识，包括对编译原理基础知识，抽象语法树这一程序中间表 示形式，程序相似度的计算以及一些常见的普通文本模式匹配算法的介绍和基于 树结构的模式匹配算法树编辑距离算法的介绍。 2 1 编译原理的基础知识 编译原理是一门介绍程序设计语言编译程序的构造原理、设计和实现技术的 课程，是一门非常重要的计算机专业课程。 编译程序作为现代计算机系统的重要组成部分，其实质上就是一个语言翻译 程序，它把像f o r t r a n ，p a s c a l ，或c c + + 这样的高级语言翻译成汇编或者机 器语言那样的低级语言，完成从源程序到目标程序的翻译工作。这个工作是分阶 段进行的，但逻辑上又是紧密联系在一起的，一般分为词法分析、语法分析、语 义分析、中间代码生成、代码优化和目标代码生成六个阶段 1 9 1 。 2 1 1 文法定义 任何一种程序设计语言的完整定义都包括语法和语义两部分，其中语法实质 上就是一组规则，用来生成一个合法程序的规则，反过来也可以用它来描述这种 语言，而这种语言描述就是文法。目前广泛使用的是上下文无关文法，本文就是 利用这种文法来构造抽象语法树的。 一般文法被定义为四元组m ，v r ，p ，s ) 【2 0 1 ，其中v n 代表非终结符号集，v t 代 表终结符号集，p 是产生式的集合，也就是规则的集合，s 为开始符号。通常定义 文法时，只需写出产生式，并把开始符号在左边的产生式放在所列产生式的第一 个。 例如，文法c r = - ( v n ，v t ，p ，s ) ，其中v n = s ) ，v r = 钆b ) ，p = s - - a s b ，s a b ) ， 该文法中非终结符号集中只有一个元素s ，而终结符号集有两个元素o 和1 ，开始 符号为s ，并且有两条产生式s - - - a s b 和s a b 。 基于抽象语法树的编程题自动评分系统的研究与应用 2 1 2 词法分析 词法分析是编译工作的第一步，其主要任务就是从左至右对源程序进行逐个 字符扫描，产生一个个单词序列，用以语法分析。执行词法分析的程序称为词法 分析程序或扫描程序。词法分析程序按照语言定义规则，依次逐个读入源程序的 符号，识别出有意义的符号串，即：单词符号，如：关键字、标识符、运算符、 常量和分界符，并分析其属性，然后将单词符号及其属性填充到符号表中，以备 语法分析阶段使用【2 l 】。 词法分析程序读入源程序，输出已识别的单词符号，但在实际处理的时候， 并非输出单词，而是采用二元式的表示方式：( 单词种别，单词属性值) ，因此，经 过词法分析这一步骤后，其输出结果并不是单词本身【2 2 1 。其实，词法分析程序往 往还可完成一些其它任务，如：过滤掉源程序中的注释和空白，负责记录新读入 的行号，方便记录错误信息，或者完成宏的预处理等工作。 2 1 3 语法分析 语法分析是编译工作的核心阶段，主要是用来识别由词法分析给出的单词符 号序列，并判断其是否满足给定的文法规则，若满足，则生成对应的语法树，否 则，则报告语法错误。语法分析依据程序语言的语法规则，来确定整个程序在语 法上是正确的。以c + + 程序中的循环语句“w h i l e ( n ”为例，词法分 析程序识别出了w h i l e 、( 、标识符等单词符号，再由语法分析程序检查这些单词符 号是否正确，结构是否匹配等。 其实，语法分析的过程也就是对给定的单词符号序列构造语法树的过程。语 法分析常用的两种方法是：自顶向下法和自底向上法。自顶向下法就是指语法分 析程序从生成树的根结点开始，并用开始符号对这个根结点进行标记，然后在语 法树中以前序遍历的方式生成结点，它的任务就是为已知的非终结符确定正确的 候选式。自底向上语法分析程序是以后序遍历的方式在语法树上构造结点，即： 一颗子树的根结点是在它所有的孩子结点生成之后再构造，它的任务就是反复寻 找所有孩子都已生成的第一个结点。无论哪种语法分析方法，语法分析程序都是 从左至右读入单词符号序列。 第2 章课题相关的理论基础 本文利用自底向上语法分析中的l r ( 1 ) 技术对源程序进行语法分析，其分析过 程为：从左至右扫描输入串，并逐个入栈，边移入边分析，如果栈顶符号串形成 某个句型的可归纳串，就用该产生式左部的非终结符替代它，即完成一步归约， 重复这一过程直至归约到栈中只剩右界符撑和文法的开始符号为止，此时表示 分析成功，否则，报告错误。 2 2 抽象语法树 2 2 1 抽象语法树 抽象语法树( a b s t r a c ts y n t a xt r e e ，a s t ) 是一种程序的中间表示，它由代表非保 留字终结符的叶子结点和代表语法结构的中间结点组成，并且可以进一步完善 2 3 1 ， 如，包含一些表示语义关系连接的结点，使得最后得到的抽象语法树能够包含源 代码的相关信息。因此，抽象语法树被用于很多实际的编译系统中。 抽象语法树是源程序经过词法分析和语法分析之后的产物，具有如下优点： ( 1 ) 抽象语法树有助于反映语言成分的自然层次结构，很好地体现其语法结 构，同时有利于对程序的结构进行分析； ( 2 ) 抽象语法树的结构不依赖于源语言的文法，所以它能为系统前后端建立一 个清晰的接口； ( 3 ) 存储效率高、易于遍历和操作。 鉴于上述优点，本文选取抽象语法树作为程序的中间表示。 本文通过语法分析程序得到规范的归约序列，然后在此基础上将其转换为抽 象语法树的形式，因此，需要创建和构造抽象语法树的结点对象，结点对象在结 点类中创建，如图2 1 所示为抽象语法树结点类的类图。 基于抽象语法树的编程题自动评分系统的研究与应用 a s t t r e e n o d e - n m l l e ：s t r i n g v a l u e ：s t r i n g - s y s v a l u e ：s t r i n g - w e i g h t ：i n t t y p e ：s l r m g p a r e n t ：t r e e n o d e - c h i l d r e n l i s t ：l i n k c 皿i 啦 + g e t n a m e o ：s m n g - i - 暑e t n a m e r i nn a m e ：s t r i n g ) ：v o i d + g e t v a l u e 0 ：s t r i n g + s e t v a l u e ( i nv a l u e ：s l a i n g ) ：v o i d + g e t s y s v a l u e o ：s t r i n g + s e t s y s v a l u e ( i ns y s v a l u e ：r i g ) ：v o i d + g e t w e i g h t o ：i m + s e t w e i 曲g i nw e i g h t ：i n t ) ：v o i d + g e t t y p e 0 ：s t r i n g + s e t t y p e ( i nt y p e ：s t r i n g ) ：v o i d + g e t p a r e n t o ：t r e e n o d e + s e t p a r e n t ( i np m e n t ：t r e e n o d e ) ：v o i d + g e t c h i l d r e n l i s t o ：l i n k e d l i s t + s e t c h i l d r e n l i s t ( i nd l i l 出e n l i s t ：l i n k e d l i s t ) ：v o i d + a s t t r e e n o d e o + a s t t r e e n o d e ( i nn a m e ：s t r i n g 。i nv a l u e ：s t r i n g , i ns y s v a l u e ：s t r i n g , i nw e i g h t ：i n t i nt y p e ：s t r i n g , i np a r e n t ：t r e e n o d e ) + s i m i l a r f a e t o r ( i nt r e e n o d e ：t r e e n o d e ，i nt y p e ：s t r i n g ) ：d o u b l e + e o m p a r v ( i nt r e e n o d e ：t r e e n o d e l ：b o o l 图2 1 抽象语法树结点类的类图 f i g 2 1t h ec l a s sd i a g r a mo f a s t t r e e n o d e 以c 程序为例，其抽象语法树的结点类型矧有：标识符结点( i d e i l t i f i e r s ) 、声 明结点( d e c l a r a t i o n s ) 、函数结点( f u n c t i o n s ) 、类型结点( t y p e s ) 、表达式结点 ( e x p r e s s i o n s ) 、语句结点( s t a t e m e n t s ) 、范围结点( s c o p e ) 等类型。 例如某函数定义如下： i