（计算机应用技术专业论文）程序作业自动测评的研究与实现.pdf

摘要 近年来计算机辅助测评( c a a ) 领域受到了更多的关注，但所解决的多为 客观题测评问题，而主观题由于灵活性和仓0 造性强等因素，一直没有出现很好 的测评方案。程序作业属于主观题，与自然语言相比，由于程序设计语言的规 范性强，多义性少，加之学生程序主要是中小程序，可作为主观题测评领域的 一1 个研究出发点和突破点。 本文研究学生程序作业的计算机辅助评价。在本工作室研发的编程学习可 视化环境基础上，通过扩充基于程序作业标准答案模板的测评技术，实现对学 生程序作业的计算机辅助评价，既有利于程序设计语言初学者更快更好地理解 掌握程序设计的基本概念和方法，也有利于减轻教师批改程序作业的负担，增 强学生程序测评工作的客观性、准确性和实时性。 本课题的主要研究目标是程序测评系统的设计和实现。在该系统中，采用 源码特征比较的方案，将学生程序与存储在题库中的模板程序集依次比较，然 后根据基于相似度概念的评分规则得出对学生程序完成程度和质量的测评结 果。在学生程序与模板程序比较前需要对二者进行一系列信息提取和结构转换 工作。输入源程序后通过语法分析主要建立起对程序控制结构的信息树，称作 扩展语法树( e s t ) ；在e s t 的基础上通过对数据流向的分析，建立起扩展流图 ( e f g ) 作为过渡；在e f g 基础上通过对程序基本块的划分，对各子块的控制 和数据依赖关系分析，以及使用一些规范化规则等技术，得到了程序特征属性 图( p f s g ) 。之后的程序评价过程是基于程序对等结构和程序等价结构的概念， 对学生程序和模板程序的p f s g 进行的。 本文的内容组织如下：第一章介绍自动测评相关技术背景、现状和意义， 并介绍本课题的研究点；第二章介绍整个测评系统的总体架构和处理过程；第 三章提出程序对等结构和等价结构的概念，并分析了需要从程序中提取的信息； 第四章讨论测评系统中数据结构的选用；第五章介绍表达式、条件语句和循环 语句等程序结构规范化技术；第六章介绍变量跟踪技术和比较评分技术；第七 章以一个实际的例子说明如何使用模板程序测评学生程序的整体过程。 广东上业大学工学硕士学位论文 关键词程序的测量与评价；对等结构：等价结构；程序结构规范化；程 序结构比较 a b s t r a c t c o m p u t e ra u x i l i a r ya s s e s s m e n t ( c a a ) h a sg o tm o r ea t t e n t i o ni n t h er e c e n t y e a r s o b j e c t i v ep r o b l e m sb e i n gr e s o l v e d ，t h e r ea r en o ta n yg o o dm e t h o d sa p p e a r e d f o rs u b j e c t i v ep r o b l e m sb e c a u s eo ft h e i rv a r i e t ya n dc r e a t i v i t y s t u d e n tp r o g r a m e x e r c i s e sb e l o n gt os u b j e c tp r o b l e m s s i n c ep r o g r a ml a n g u a g eh a ss o m ef e a t u r e s d i f f e r e n tf r o mh u m a nl a n g u a g e ，s u c ha ss t r o n g l yr i g i dc r i t e r i o n ，f e w e rm u l t i v o c a l s i t u a t i o n s ，a n dh e r em a i n l ym o d e r a t es i z ep r o g r a m sp r o c e s s e d c a af o rs t u d e n tp r o g r a mi ss t u d i e di n t h i sp a p e r o nt h eb a s i so fp r o g r a m s t u d y i n gv i s u a l i z a t i o ne n v i r o n m e n t ，w h i c hw a sd e v e l o p e db yo u rs t u d i o ，s t u d e n t p r o g r a mi sa s s e s s e dl o g i c a l l yu s i n ga u t o m a t e dp r o g r a ma s s e s s m e n tt e c h n i q u eb a s e d o nm o d e lp r o g r a m s t h a tw o u l db e n e f i tn o to n l yb e g i n n e rf r o mc o m p r e h e n s i o na n d m a s t e r y o fb a s i cp r o g r a mc o n c e p t sa n dd e s i g nm e t h o d s ，b u ta l s ot u t o r sf r o m o r i g i n a lt a s k sa l l e v i a t i o n ，a n di nt h em e a nt i m e ，p r o g r a ma s s e s s m e n tw o r kw o u l d b em o r ei m p e r s o n a l ，e x a c t ，a n dr e a l t i m e t h eg o a li st od e s i g na n dt oi m p l e m e n tt h ep r o g r a ma s s e s s m e n ts y s t e m i nt h e s y s t e m ，t h ei d e ao fc o m p a r i n gs o u r c ec o d e s f e a t u r e si sa d o p t e d s t u d e n tp r o g r a m a n dm o d e lp r o g r a m ss t o r e di nt h ep r o b l e ml i b r a r ya r ec o m p a r e di nt u r n ，a n dt h e n a s s e s s m e n tr e s u l ta b o u ta c c o m p l i s h e dd e g r e ea n dq u a l i t yo fs t u d e n tp r o g r a mi s a c q u i r e dt h r o u g ha s s e s s m e n tr u l e sb a s e do nt h ec o n c e p to fe q u i v a l e n td e g r e e b e f o r ec o m p a r i n gs t u d e n tp r o g r a mw i t hm o d e lp r o g r a m ，as e r i e so fw o r ki sn e e d e d t ob ed o n e ，s u c ha si n f o r m a t i o na b s t r a c t i o n ，s t r u c t u r et r a n s f o r m a t i o n a f t e rs o u r c e p r o g r a mi n p u t t e d ，i n f o r m a t i o nt r e eo fp r o g r a mc o n t r o ls t r u c t u r e ，w h i c hi sc a l l e d e x t e n d e ds y n t a xt r e e ( e s t ) ，i sp r o d u c e db ys y n t a xa n a l y z i n gp r o c e s s ；e x t e n d e d f l o wg r a p h ( e f g ) i sp r o d u c e db yd a t af l o wa n a l y z i n go nt h eb a s i so fe s t ；p r o g r a m f e a t u r e sa n da t t r i b u t e sg r a p h ( p f s g ) i sp r o d u c e do nt h eb a s i so fe f g b yas e r i e s o ft e c h n i q u e s ，s u c ha sp r o g r a mb a s i cb l o c kp a r t i t i o n ，c o n t r o ld e p e n d e n c ea n dd a t a i n 耋奎三些奎兰圭耋至圭兰堡耋耋 d e p e n d e n c ea n a l y z i n g ，s t a n d a r d i z i n g ，e t c o fs t u d e n tp r o g r a ma n dm o d e lp r o g r a m s t r u c t u r ea n de q u i v a l e n ts t r u c t u r e t h ea s s e s s m e n tp r o c e s si sont h ep f s g s b a s e do nt h ec o n c e p t so fc o r r e s p o n d i n g t h es t r u c t u r eo ft h i sp a p e ri so r g a n i z e da st h i s ：t h eb a c k g r o u n d ，r e c e n t s i t u a t i o n ，a n ds t u d y i n gv a l u eo fa u t o m a t e dp r o g r a ma s s e s s m e n ta r ep r o d u c e di n c h a p t e r1 ；t h ef r a m e w o r k ，e n v i r o n m e n t ，a n dp r o c e s so fa s s e s s m e n ts y s t e ma r e p r o d u c e di nc h a p t e r2 ；t h ec o n c e p t so fp r o g r a mc o r r e s p o n d i n g s t r u c t u r ea n d p r o g r a me q u i v a l e n ts t r u c t u r ea r ep r o p o s e d ，a n di n f o r m a t i o nt ob ea b s t r a c t e df r o m p r o g r a ms t r u c t u r ei s d i s c u s s e di n c h a p t e r3 ；t h ed a t as t r u c t u r e so fa s s e s s m e n t s y s t e ma r ed i s c u s s e di nc h a p t e r4 ：s t a n d a r d i z a t i o nt e c h n i q u e sf o re x p r e s s i o n sa n d c o n t r o ls t r u c t u r e sa r ep r o d u c e di nc h a p t e r5 ；v a r i a b l et r a c i n gt e c h n i q u e sa n d c o m p a r i s o na s s e s s m e n tt e c h n i q u e sa r ep r o d u c e di nc h a p t e r6 ：a ne x a m p l eo fh o w t oa s s e s ss t u d e n tp r o g r a ma saw h o t ei se x p l a i n e di nc h a p t e r7 k e y w o r d sp r o g r a ma s s e s s m e n t ，c o r r e s p o n d i n gs t r u c t u r e ，e q u i v a l e n t s t r u c t u r e ，p r o g r a ms t r u c t u r es t a n d a r d i z a t i o n ，p r o g r a ms t r u c t u r ec o m p a r i s o n 1 1 本文研究背景 第一章绪论 随着计算机技术的飞速发展和社会信息化水平的不断提高，将计算机应用 于教育测量和钡0 评( 以下简称测评) 的全过程，即计算机辅助测评( c o m p u t e r a s s i s t e d a s s e s s m e n t ，简称c a a ) ，已经成为一种发展趋势。国外已经成立了有 关的研究组织，并召开了五届c a a 国际学术会议，c a a 已成为计算机教育应 用研究的热点；国内有关c a a 研究的成果尚不多见，与之相关的报导零散而 不系统。 从测评的内容和目标分类，c a a 大体上可分为知识测评和技能测评两大 类，它们共同构成能力素质测评的基础。但目前国内外的c a a 研究主要集中 在知识维度的客观题测试，技能测评研究还相对薄弱，尤其缺乏一般性的理论 与方法。技能包括操作技能和心智技能，对操作技能的考核，要求考生在真实 或仿真环境下完成特定的技能任务，这通常称为操作题。一般意义上的操作技 能测评，考生与评分者的比例应为l ：1 ，这在实际操作上存在困难；而且不同 的阅卷人对错误的解释不一样，很容易导致评分规则的不一致。解决此问题的 根本出路在于实现技能测评的自动化。心智技能测评一般使用主观题，主观题 的最重要特征是题目的解答通常要靠语言表述来完成，因此，主观题的自动测 评必然涉及到自然语言理解问题。限于目前的水平，完全解决主观题的自动测 评问题是不现实的。程序设计( 编程) 能力主要属于心智技能的范畴，试题形 式也主要采用主观题。但由于程序设计语言与一般的自然语言相比，具有严格 得多的约束和限制。因此，选取程序自动测评作为主观题自动阅卷研究的突破 口是合适的。在这方面，尽管国内外目前并无成熟的系统，但是一些相关的技 术和系统做出了一定程度的探索，程序测试( p r o g r a m t e s t ) 和程序理解( p r o g r a m c o m p r e h e n s i o n ) 这些术语都是对于这一研究课题的不同侧重。 广东工业大学工学硕士学位论文 1 1 1 程序测试技术现状 程序测试是程序的一种执行过程，目的是尽可能发现并改正被测试软件中 的错误，提高软件的可靠性。它是软件生命周期中一项非常重要且非常复杂的 二【：作，对软件可靠性保证具有极其重要的意义。在过去的数年中，通过使用自 动化的测试工具对软件的质量进行保障的例子已经越来越多。到现在为止自动 化测试工具在逐步完善，许多软件项目在软件的测试中都应用自动化的测试工 具来大幅度的提供软件测试的效率和质量。自动化测试的范围很广，其中包括 了代码级的自动化测试、g u i 的自动化测试以及性能自动化测试等。 近年来在软件测试研究领域，出现了一系列自动化测试工具如r a t i o n a l r o b o t 【1 0 1 号称是业界最顶尖的功能测试工具，它可以在测试人员没有高级脚 本技术知识的情况下帮助其进行成功的测试；w i n r u n n e r 3 1 是一种企业级的用 于检验应用程序是否如期运行的功能性测试工具；q u i c k t e s t p r o f e s s i o n a l t 4 1 是一 个主要应用在回归测试中的功能测试自动化工具；s i l k t e s t1 4 是业界领先的、 用于对企业级应用进行功能测试的产品，可用于测试w e b 、j a v a 或是传统的c s 结构，s i l k t e s t 提供了许多功能，使用户能够高效率地进行软件自动化测试； q a r u n 5 1 的测试实现方式是通过鼠标移动、键盘点击操作被测应用程序，继 而得到相应的测试脚本，对该脚本可以进行编辑和调试；t e s tp a r t n e r 5 1 专为测 试基于微软、j a v a 和w e b 技术的复杂应用而设，通过可视的导航器录制并回 放测试过程，每一个测试实例都将被展示为树状结构，以清楚地显现测试通过 应用的路径。 2 0 0 3 年吉林大学运用信息流分析技术，通过遍历抽象语法树，较好地解决 了程序路径分析和测试用例的自动生成的问题6 1 。其侧重于测试路径的建立和 测试用例的生成，尽管一定程度实现了程序自动化测试，但其不能量化测试结 果的正确或错误程度。 1 1 2 程序理解技术现状 程序理解是一个从计算机程序中获取知识的过程。旨在理解一段已有的程 序，通过不断地检查代码，逐步构建所需的理解。理解过程中，不断地从中获 2 第一章绪论 取知识并提炼。程序理解是一个复杂的过程。理解过程中容易出现信息丢失、 前后不一致的情况，而造成理解困难。程序理解在提供给程序初学者的程序教 学中已是广为讨论的话题7 ，8 ，9 ，1 0 】。 在程序理解方面国外的研究可以追溯到1 9 7 0 年，随着程序证明、程序维护 和人工智能的发展，人们开始涉足程序理解这一领域。在最近2 0 年来，程序理 解系统开始被人们提出，如支持逆向工程的程序理解工具r i g i 【7 1 1 1 2 ，它的工 作由两部分组成：l 涪0 祈阶段。2 发掘阶段。剖析阶段主要的工作是：剖析源 程序，用自带的图像编辑器生成一个能够操作和浏览的资源流平面图。随后的 发掘阶段是一个半自动化阶段，涉及了一些模式识别技巧和领域知识。此阶段 中逆向工程人员通过剖析阶段建立的平面图，确定源程序中含有的子系统，构 造出有意义的高层抽象模型。这些子系统能够递归地收缩和打开，形成一个层 次结构。r i g i 能够根据用户关心的类型过滤掉不需要的信息，方便用户的浏览。 不过，r i g i 不支持直接地搜索源代码文本。总之，r i g i 主要的工作放在揭示系 统的抽象信息和子系统层次的生成。这些层次结构为在工具中从容地浏览起到 了重要的作用。s h r i m p 7 a 3 1 是一个通过嵌套的平面图形在单个窗体中展示一个 软件系统的结构的程序理解工具。在嵌套图中，每个复合结点一般表示软件系 统中的子系统，它们中含有其它子结点，复合结点与子结点构成层次关系。嵌 套图中的符合曲线表示低层结点问含有层次关系。这些关系一般为委托和合成 关系。s h r i m p 集成了鱼眼视图7 ，1 4 1 和平移缩放两种方法，使理解者关心的对象 总处在有利于理解的位置。鱼眼视图能够同时显示关心的对象上下文和细节， 放大关心对象，缩小与对象无关的事物。平移缩放方法允许理解者在不失真的 情况下，平移缩放视图。与r i g i 相同，s h r i m p 生成的底层事物与源程序文本 密切相关。但是，s h r i m p 以超文本的形式呈现了源程序中函数调用、数据类 型引用和变量引用。s h r i m p 当前不足的是，缺少一个有效的搜索工具，没有 信息过滤的功能，更重要的是，在某些情况下，它所生成的图并不可靠。 s n i f f + ( 7 , 1 5 是一个商业的软件开发环境，它提供项目管理、源程序浏览、 交叉引用和超强搜索的功能。一些相对独立的工具通过集成实现了这些功能。 这些工具都是工作在由s n i f f + 音0 析源程序生成的符号表基础上。项目管理窗口 列出了源程序的头文件和实现文件。符号浏览器显示了函数、常量、宏和变量 等符号。这些符号可以自定义显示条件。源代码编辑器用语法规则高亮显示了 3 广东工业大学工学硕士学位论文 源代码文本搜索后的结果。 1 9 9 8 年日本的h a r u k i u e n o 开发了基于知识生成方法的对p a s c a l 和c 语言理解的环境a l p u s 及a l p u si i ，建立了四个知识库：算法知识库、编程 技巧知识库、变量知识库和b u g 库。通过知识库及其学习规则生成某些模板 与标准化后的学生程序进行比较，生成模板的种类包括标准模板、可接受模板 以及b u g 模板。需要依次与这些模板进行比照，从而相应确定程序质量 1 6 1 。 国内在程序理解方面的研究主要有北大青鸟工程的青鸟程序理解系统 一一j b p a s 。青鸟程序理解系统j b p a s ( j a d eb i r dp r o g r a ma n a l y s i ss y s t e m ) 是 一个针对c + + 语言的程序理解系统，由一个c + + 分析器前端和一组分析工具组 成，分析器前端采用e e r ( e n h a n c e de n t i t y r e l a t i o n s h i p ) 为c + + 程序建立概念 模型，该模型较为全面，以适合多种程序信息需求。通过增量分析技术静态分 析程序员代码，按照概念模型抽取程序信息并将信息保存在增量数据库中。最 后，启动增量库链接器，将各个增量数据库链接成程序信息库 7 , 1 7 , 1 8 , 19 1 。 2 0 0 3 年哈尔滨工业大学提出一种程序理解方法 7 1 ，利用层次结构分析方法 通过对程序的逆向分析可以得到一个程序的结构信息，并将其最后用图形化方 法表示出来，以便于分析者理解程序的逻辑含义和程序结构间的逻辑关系。这 篇论文主要侧重于程序结构的理解，对于分析大型软件结构有很大帮助，但是 不能做到较精确地查看程序正确性。 1 1 3 其他相关技术现状 针对反编译后得到的程序没有文档和注释的问题，1 9 9 2 年，东南大学计算 机科学与工程系研制了一种c 源程序分析及理解的辅助工具一一c a a t ，其主 要通过对源程序的逐级抽象理解来对没有注释的反编译源代码进行添加注释、 格式化显示，分析显示各类变量的使用情况，提供对宏、变量、结构和联合等 定义说明的查询显示，另外可输出模块调用关系及源程序中的函数调用关系图 2 0 i 。 在1 9 9 9 年，新加坡国际大学计算机学院的s o n g w e n x u 等研制出了一个 名为s i p l e s i i 的系统用来分析学生程序，查找其中错误并提供出错提示，从 而提供一个较为智能化的编程学习环境。其主要采用了下列一些技术：采用了 4 第一章绪论 一种名为面向对象程序依赖关系图( a o p d g ) 的结构：基于转化的程序标准化 方法；语义级程序比较；基于最大可能性的程序查错方法【2 “。 另外，北京师范大学的许骏、柳泉波博士近年来在技能测评自动化方面做 了一些工作，i t a s 是技能测评自动化研究项目系列成果之一，供学校或培训单 位组织课程考试或水平测试使用。i t a s 由自动测评、测评管理和辅助命题系统 组成，可以在单机或局域网环境下运行。利用i n t e r n e t 作为信息交换平台，可 以实现远程在线自动测评。i t a s 涵盖计算机基础教育的全部内容，包括 w i n d o w s9 8 、w o r d 9 7 2 0 0 0 、e x c e l 9 7 ，2 0 0 0 、p o w e r p o i n t9 7 2 0 0 0 、i n t e r n e t 和演4 览器i e5 o 以及网页设计等 2 2 i 。但是，i t a s 是应用于计算机基础教育的操作 技能考核问题的，对于程序测评技术却没有给予解决。 尽管在程序分析、程序理解和程序测试的研究中出现了以上一些技术和产 品，但是没有真正从程序的测评角度出发，并很好地实现在提供的一定交互式 学习环境中进行程序设计学习，并可对程序结果进行合理性测评的研究成果出 现。 1 2 本文研究点 近年来尽管不少人在程序测试、程序理解等相关技术方面做了不少工作， 但是并没有出现立足于学生，尤其程序设计初学者的角度，进而发展为辅助教 学工具，而且具备程序自动测评的一整套系统环境的较为成功的成果。通过切 身的初学体会和调查多数学习者的初学情况发现，对于理想的编程学习环境， 强调学生学习环境中共同理解的建立。而且，随着近年来学校不断地扩招，学 生和老师的比例越来越大，所以教师负担加重，甚至短期内不可能了解到所有 学生的学习情况，只能抽查；如果能将这种检查过程使用计算机技术自动化， 则会大大减轻教师的负担；同时，计算机的准确性会保证对学生程序作业测评 的一致性和客观性。所以，在开发了编程学习可视化环境的经验基础上，我们 发现在程序学习环境中加入对学生程序质量的判断的必要性。综合上述因素， 我们工作室就是致力于这样一项持续性的工作，逐步完成各个程序设计语言版 本的程序设计与调试全过程可视化的集成开发软件，并能利用互联网环境使用 经典题目编程题库系统，并加上本文所要研究的程序自动测评方法，从而构成 5 广东工业大学工学硕上学位论文 一个完整的可视化程序设计学习环境。 一般意义上的程序测试，是程序的一种执行过程，目的是尽可能发现并改 正被测试软件中的错误。所以其前提是要求程序可执行。对于学生程序，或者， 我们称之为程序作业，有一部分可能是不可执行的；还有一部分，可执行而且 运行结果正确，但是可能会有作弊现象的存在( 如只使用一些输出语句显示正 确结果) 。对学生程序测评的目的是合理地测评程序的质量。由于目的和前提不 同，所以程序测试和程序测评采用的方法和得到的结果也不相同。 1 2 ，1 基于模板的程序测评 基于上述背景和需求，本文研究的目标是找出一种自动测试学生程序完成 程度和完成质量的方法。 本文主要着眼于在语法语义分析的基础上建立抽象语法树提取程序结构 和数据信息，然后运用信息流分析、静态测试技术和一些标准化规则对语法树 进行规范化，并进一步转换使用流图1 思想表示为程序特征属性图结构，然后 根据等价结构定义对规范化后的模板语法树和学生程序语法树进行比较，最后 根据一定评分规则对学生程序做出一定程度上的正确测评。 前期工作的重点和难点在于程序信息的抽取，在抽取结果的基础上进行规 范化整理和比较，以能达到对学生程序测评的目的。程序结构信息比较容易抽 取，但主要的问题是如何正确地利用这些信息。另一方面，语义信息则相对较 难抽取出来。各种基于知识的系统经常会阐述这个问题。典型地，程序计划的 知识库被创建后常常可在程序中自动识别概念。但是，在使用知识库时有个潜 在的难题，那就是首先必须有人去创建它。将这些专业领域知识搜集整理起来 是非常耗时且花费很大的【2 4 1 。 如果不使用知识库技术，可以有三个主要方法来自动检测程序。第一种方 法是使用一种标准即使用对程序目标的高级描述来匹配学生程序。这种方法被 称为源码标准方法2 1 1 。第二种方法是从学生程序中抽取标准并拿它和任务标准 做比较。这种方法被称为标准标准方法f 2 1 1 。这两种方法与程序理解的着眼点是 一致的。然而，程序理解技术的不成熟阻碍了这两种方法在程序学习的教学系 统中广泛实际的应用。 6 第一章绪论 第三种方法是利用一个存储在题库中的模板程序去匹配学生程序。这种方 法被称作源码源码方法2 1 1 。有个早期的使用这种方法的是对f o r t r a n 语言理 解的l a u r a 系统。l a u r a 使用了非常简单的程序表达和转换方法，不适用于 结构性语言和面向对象语言。这种学生程序和模板程序之间的匹配不是语义级 的匹配。然而，随着程序分析和编译器设计的进步发展，面向对象程序依赖图 ( o r i e n t e dp r o g r a md e p e n d e n c eg r a p h ) 表示法、程序转换和程序比较等技术逐 渐成熟了，第三种方法用于自动检测程序错误具备了可能性2 1 1 。 在本文中，我们提出一种方法叫等价结构判别法( 等价结构相关定义在第 三章将有详细阐述) ，借鉴基于第三种方法的思路。在等价结构判别法中，学生 程序和模板程序都使用扩展了的语法树结构和程序特征属性图表示。其中学生 程序和模板程序都在使用转换技术被规范化后，确定二者程序中的对等结构( 对 等结构相关定义在第三章将有详细阐述) ，然后进行比较，最后根据一+ 定标准和 规则自动诊断学生程序完成情况。 针对以上目标，本文几个研究点为： 程序结构信息抽取； 程序结构规范化方法； 程序对等结构的判定； 程序对等结构等价性的判定： 程序结构比较方法； 程序评分方法； 变量跟踪方法。 具体各种方法和技术在后续章节都有详细阐述。 1 2 2 实验对象 本文选择学生程序作为实验对象，主要由于学生程序较之大型软件系统具 有以下特点： 1 程序规模较小，异构度( 关于异构的概念见第三章相关阐述) 相对较小， 如引用文件数、函数调用、外部变量等等情况都比较少； 2 训练题目大多有章可循，加之通过多算法模板可以在一定程度上克服由 7 广东工业大学工学硕士学位论文 算法本身不同弓i 起的不同； 3 使用程序规范可以对其做一定限制； 4 程序作业可能会由于存在错误导致不能运行，但这种错误对于程序质量 判断并不一定是很重要的。所以需要一种相对较为智能的技术识别之。 最关键的特点包含于第二个特点中，就是学生程序都会有标准答案( q 做 算法模板或模板程序) ，学生程序的模板程序是预先就存储于题库中的，通过 总体结构上和具体语句级的分别做对照，得到其相似度( 相似度的概念见第七 章) ，从面得到对学生程序的质量测评。 1 2 3 实验语言 本文选取c 语言的子集作为实验语言。目前c 语言仍然是主要的程序设计 入门语言之一，其语法结构与大多主流编程语言具有很大相似性，而且c 语言 在工业控制等应用领域依然广泛使用。 对于程序语言的形式化表示方法，可以使用公理化表示法、自动机、范式 等等，这里使用上下文无关文法表示。 上下文无关文法包含如下四个部分1 2 3 ： 1 ，一个记号集合，集合中符号称为终结符号； 2 一个非终结符集合； 3 一个产生式集合。每个产生式具有一个左部和一个右部，左部和右部由 箭头在连接，左部是一个非终结符。右部是记号和( 或) 非终结符序列。 4 一个开始符号。开始符号是一个特定的非终结符。 这里使用b n f 表示c 语言文法，其中 间的表示非终结符，无 的单 词或由单引号引起来的符号都为终结符2 5 ： ：= i f ( 1 ) l i f ( ) e l s e w h i l e ( 1 ) f o r ( 1 ； ； ) l 第一章绪论 ：= i f ( ) e l s e w h i l e ( ) f o r ( ；1 ； ) i ：= d o w h i l e ( 。 ) ； s w i t c h ( ) “f + 。 i i ； b r e a k ； c o n t i n u e ；。 r e t u r n 1 ； ：= 【 】 ：= c a s ei d ： 【d e f a u l t ： ：= ( ：= ) ! ：= = = = = = = = = = = = = = 一= = = = = = = = = = ：= = = 一一= = = = ! 下面是按照1 5 级运算优先顺序排列的文法规则 ! = = ：= = = = = = ：= = = = ：= = = = = = = = = = = ：= = = = = = 一：= = = = ：= ：= ：= ，1 ) ：= ( = f + = i 一i 8 = i ，= f “= 。f & = i f = ) l ：= 【? ： 】 ：= ( i i l ：= & & ：= i ：= ：= f & ：= ( ( = = il _ ) ) q 三奎三些奎兰三兰堡圭茎堡鎏耋 ：= ( ：= ( 。 1 ) 一1 ) 1 l ) 1 1 1 + + 1 i 1 + + 1 j 1 l 一 1 ( ) i 85 l s i z e o f l ：= ( ) i d ( ) o c t l i t e r a l h e x l i t e r a l d e c l i t e r a l s t r i n g l i t e r a l c h a r l i t e r a l f l o a t l i t e r a l l ：= i d ( lv a l u e l 1 ：= i ( 1 ( (+ 1 0 一 i d j $ ) 1 ) 第一章绪论 1 2 4 测评结果 在我们的方法中，通过将学生程序和模板程序在经过标准化转换后做比较 从而来检验学生程序的完成程度和完成质量。程序使用扩展的语法树结构和程 序特征属性图结构来表示。对用c 语言编写的程序做试验后结果表明，即使学 生程序与模板程序结构有很大差别，但只要是正确的，系统也能够识别；即使 学生程序不能运行，也能根据一定评分规则给出一个合理范围的分值。 第二章程序作业测评系统结构 2 1 总体系统结构 将学生编写程序，对程序进行可视化修改调试，以及系统对学生程序作业 的批改等环境集成起来，是我们整个编程学习可视化环境的作用和目标，所以 本文研究的程序测评技术以及在此技术指导下生成的系统是整个系统环境的一 个子系统。下面是对整个可视化a n y v i e w 系统的简要介绍。 近几年来，我们工作室对交互式编程学习可视化环境做了不少工作，开发 出了针对p a s c a l 和c 程序运行可视化的虚拟系统，称为a n y v i e w p 和 a n y v i e w c 。本系统主要基于如下需求考虑：程序的运行基本上仍处于“黑箱作 业”的状况。各种语言环境提供的排错工具只允许用户查看程序断点上部分数值 变量的当前值。在程序运行过程中，程序员难以观察程序对数据处理的细节和 复杂的数据抽象关系的动态变化的视图。需要通过复杂的编程，才能显示程序 运行的结果。因此，程序测试需要耗费大量的人力和时间资源，使得软件产品 是相对来说测试成本较高且隐藏错误较多的工业产品之一。同时培养和提高程 序的设计和调试能力主要依赖个人较高的悟性和长期实践的摸索。 目前流行的v i s u a lb a s i c 、v i s u a lc + + 、d e l p h i 和c + + b u i l d e r 等“可视化程 序设计语言”主要是向程序员提供图形界面，简化程序界面的设计，仅仅做到了 编程界面的可视化，而没有提供程序运行、调试过程中的可视化，并非是真正 全面的可视环境。 a n y v i e w 系列软件为进行高级语言程序设计提供了可视化运行和调试环 境。可在该集成环境中编辑源程序，并对其进行可视化运行、分析和调试。通 过设置断点和随时切换单指令、单行或可变换速度的连续执行等运行模式，可 在多个窗口上动态观察程序执行时的数据变量的物理和逻辑2 d 或3 d 动态视 图，使得程序运行期间本来不可见的程序对数据的处理过程和数据之间的动态 抽象关系全部可视化。 第二章程序作业测评系统结构 在a n y v i e w 环境的基础上，进一步建立了一个网络题库系统。此系统提供 给学生编程调试学习环境的同时，提供了经典练习题目的题库，供学生选择练 习；并且有一组测试数据存储在题库中，只要运行编译好的学生程序，就能检 查运行结果。这种情况下存在的不足之处就是，对于部分完成或者存在个别错 误但是不能够运行的学生程序，就不能够检测其完成程度和质量。 2 2 本文基于的编译技术简介 2 2 1 已有工作基础 本工作室已有的编译器只有前端部分，即只完成词法、语法和语义分析， 生成扩展的语法树形式的中间语言，并不进行真正的代码的生成工作。 本文的编译环境是使用一趟扫描，经过词法分析、语法分析、语义分析， 然后生成虚拟机执行的解释指令。在整个过程中，需要与符号表管理器和错误 处理器不断交互，从词法分析开始逐步在符号表中填入相关信息，从语法分析 开始逐步建立语法树，并在其中逐渐增加有用信息，为后面的规范化和比较阶 段做准备。整个处理过程如图2 1 所示。 本文的程序结构规范化和程序结构比较技术都是基于目前a n y v i e w 已有的 编译环境基础，没有使用第三方编译器及其提供的抽象语法树定义和a p ! 函数， 全部采用自己定义的结构和方法，在编译器和符号表上适当扩充，这样可便于 整个系统集成，同时也增加了信息提取时的灵活性。 2 2 2 基于散列技术的符号表简介 符号表1 2 3 是一种数据结构，通常用于保存源语言结构的各种信息。在本编 译环境中，对于语法语义分析，以及将所提取信息用于规范化和比较都需要使用 到符号表。 一个组织结构较好的符号表必须同时兼顾二个方面的要求：一方面，要能 正确地记录源程序中各种名字的属性和特征等有关信息；另一方面，还必须方 便编译处理过程以及后续的标准化和比较过程中对源程序中各种名字的不断汇 广东工业大学工学硕士学位论文 集和反复查找。因此，符号表的组织结构恰当与否对编译算法以及编译效率的 影响至关重要。符号表的一般组织方法有两种：线性表2 3 1 和散列表2 3 1 。 源程序 解释程序 图2 1 编译处理过程 f i g u r e2 - ic o m p l i n gp r o c e d u r e 尽管线性表容易实现，但存在使用效率不高、查找速度慢的缺点，所以在 大多编译器中，一般不会使用线性表来实现符号表结构。 散列技术有许多种，这里提到的是外散列技术 23 1 ，外散列表对表中的表项 的数量没有限制。这种表在n 个名字中做e 条查找时，查找时间与n ( n + e ) m 成 正比，其中m 为任意常数。既然m 可以取任意值，就可以把它取得很大，直到 n 【23 1 。基本的散列表如图2 - 2 所示： 它的数据结构包括两部分：由一个固定的数组组成的散列表，数组的m 个 元素是n 1 个指向表项的指针；表项被组织到m 个独立的链表中，这些链表称为 桶( 有些桶可能是空的) 。符号表中的每条记录刚好出现在某一个链表中。记录 的存储可能来源于记录数组。 为了判断字符串s 的表项是否在符号表中，对s 采用散列函数h ，h ( s ) 返 圈0 到n l ，1 之间的一个整数。如果s 在符号表中，那么它位于链表的h ( s ) 位 1 4 第二章程序作业测评系统结构 置上。如果s 不在符号表中，那么为它创建一条记录，并把它插到h ( s ) 对应 的链表前。 0 图2 - 2 基本散列表结构 f i g u r e2 - 2 b a s i ch a s ht a b l e m 的选择依赖于对符号表的应用。如果把m 选为几百，那么即使对于中等 大小的程序来说，查表所用的时间相对于编译程序的总开销而言也是可以忽略 的。但是当程序的规模很大时，m 的值应该适当取较大的值。 散列函数设计的优劣是决定散列表查找效率高低的关键。具体要求是该函 数能够容易地计算出字符串地散列值并把所有的字符串均匀地分配到m 个链表 中取。 在本编译环境中，为了信息的动态增长及快速查询，采用的是散列表。 1 本编译环境的符号表结构 ( 1 ) 标识符表 p o i n t o b j = “o b j e c t r e c o r d ； o b j e c t r e c o r d = r e c o r d n a m e ，n a m e l e n g t h ，l a s t c h a r ：i n t e g e r ； p r e v i o u s ，n e x t s t a t i c ：p o i n t o b j ； p t e l t y ：b o o l e a n ； t r a c k ：t t r a c k v a r ； c a s ek i n d ：c l a s s 0o f s t a n d a r d t y p e ：( n o n e l ，n o n e 2 ：p o i n t o b j ；o r i g i n a l n a m e ：i n t e g e r ) ； a r r a y t y p e ， s t r i n g t y p e ：( e l e m e n t t y p e ，i n d e x t y p c ：p o i n t o b j ； 三查三些奎兰三兰堡圭耋堡丝三 l o w e r b o u n d ，u p p e r b o u n d ：i n t e g e r ； d e m o ：b o o l e a n ：f ：f r e c t p t r ) ； e n u m t y p e ：( l a s t e