（计算机软件与理论专业论文）数据库自然语言查询及代码相似匹配研究.pdf

o；_-fji-l；_-l 独创性声明 吣, t8 删9 5 3 9 3 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已注明引用的内容以外，本论文不包含任何其他个人 或集体己经发表或撰写过的作品成果，也不包含为获得江苏大学或其他教育机构 的学位或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 弥为 z j , i1 年6 月多日 学位论文版权使用授权书 江苏大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、 缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致， 允许论文被查阅和借阅，同时授权中国科学技术信息研究所将本论文编入中国 学位论文全文数据库并向社会提供查询，授权中国学术期刊( 光盘版) 电子杂 志社将本论文编入中国优秀赙硕士学位论文全文数据库并向社会提供查询。 论文的公布( 包括刊登) 授权江苏大学研究生处办理。 j 本学位论文属于不保密豳。 学位论文作者签名：丫盔力 沙，年乡月参日 指导教师签名：撇 年月日 江苏大学硕士研究生毕业论文 l 。 摘要 数据库技术是信息化社会的重要基础，数据库课程是国内高校计算机专业的 必修课程。数据库教学中高效能、高质量实验技能训练，对提高课程的教学质量 起着至关重要的作用。因此，构建一个高效的在线实验学习环境，使学生在学习 中能够再学习、能够检验自己的学习效果，对改善教师疲于应对学生的共性问题， 对实验教学环节能进行量化考核，准确地掌握和评价每个学生的能力，促进学生 分析问题和解决问题能力的提高有着十分重要的现实意义。 籍此，在研究自然语言处理技术及代码自动评估的基础上，采用改进后的数 据库模式提取技术抽取自然语言描述的查询要求中包含的信息，构造语义依存树 并转化为等价的s q l 代码。采用静态分析方法，通过构造抽象语法树并计算目 标代码和源代码的树编辑距离来对学生提交的代码进行评估。同时，在评估过程 中，针对出错节点推送相关知识，为解决学习过程中出现的问题提供及时的帮助。 本文的主要工作如下： 1 ) 研究自然语言数据库相关技术，借鉴受限领域自然语言处理方法，通过 构造结构化的字典作为自然语言分析处理的基础，为分析自然语言查询要求提供 充足的辅助信息； 2 ) 引入词性标注信息，优化数据库模式提取技术，通过构造集合块的方法 分析语义依存树并将其转化为等价的s q l 代码； 3 ) 研究常用的代码相似度评估技术，借鉴语言编译过程中的处理方法，通 过静态分析代码结构，构造等价抽象语法树的方式完整保存代码语法信息，并采 取树编辑距离作为评估代码相似度的依据，对于存储过程的匹配引入匹配向量记 录变量依赖关系。计算过程中引入结点权重因子以体现不同考察点的重要性； 4 ) 构造结点知识点关联集，在代码匹配的异同点自动向用户推送相关知识 点供用户参考学习； 5 ) 论文对数据库实验学习支撑平台原型系统进行了设计与实现。通过实际 运行该学习支撑平台验证本文研究内容的可行性，测试各个功能模块的实用性。 关键词：自然语言数据库；代码自动评估；抽象语法树；语义依存树 江苏大学硕士研究生毕业论文 a b s t r a c t d a t a b a s et e c h n o l o g yi st h eb a s eo fm o d e r ns o c i e t y , t h ed a t a b a s ec o u r s ei so n eo f t h eo b l i g a t o r yc o u r s e so fc o l l e g es t u d e n t si nc h i n a aw e l lc o n s t r u c t e dd a t a b a s e t e a c h i n ga n dl e a r n i n ge n v i r o n m e n ti sv e r yi m p o r t a n tt oi m p r o v et h eq u a l i t yo f d a t a b a s et e a c h i n g h e n c e ，t ob u i l dae f f i c i e n to n l i n es t u d y i n gp l a t f o r mi no r d e rt o g a t h e ra n dp r o c e s sq u e s t i o n sa u t o m a t i c l l y , a s s e s st h el e a r n i n ge f f e c ts c i e n t i f i c l l ya n d p r o v i d eh e l pp r o m p t l y t h e s em a yi m p r o v et h eq u a l i t yo fd a t a b a s et e a c h i n ga n d l e a r n i n g ，a n dc o m p e n s a t e st h ef a u l t so ft r a d i t i o n a lw a y i ti sv e r ys i g n i f i c a n ta n d i m p o r t a n tt ob o t ht h el e a r n i n ga n dt e a c h i n go fd a t a b s ec o u r s e a i m m i n ga ts o l v i n gt w oc r u c i a lp r o b l e m sf r o mt h ec o n s t r u c t i o no fd a t a b a s e i n t e l l i g e n ts t u d y i n gp l a t f o r m ，t h i sp a p e ri m p r o v et h e “d a t a b a s es c h e m ae x t r a c t t e c h n o l o g yt oe x t r a c ti n f o r m a t i o nh i d i n gi nn a t u r a ll a n g u a g eq u e r yd e m a n d s ，b u i l da s e m a n t i cd e p e n d e n c et r e ea n dt h e nt r a n s f o r mt o e q u i v a l e n ts q lc o d e a s s e s s i n g s t u d e n t sc o d eb ys t a t i ca n a l y s i s ，c o n s t r u c tt h ea b s t r a c ts y n t a xt r e e so f t a r g e tc o d ea n d s o u r c ec o d ea n dc a l c u l a t et h et r e ee d i td i s t a n c ea st h eb a s eo ft h es i m i l a r i t yo ft w o p i e c e so f c o d e s t h i sp a p e ra l s oa d o p tt h ew e i g h tf a c t o ri n t ot h ec a l c u l a t i o na n dm a k e t h ea s s e s s m e n tm o r e s c i e n t i f i c l l y m e a n w h i l e ，t h ep l a t f o r m w i l l p u s h r e l a t e d k n o w l e d g et ou s e r sw h e nm i s t a k eh a p p e n e d t h i sp a p e rm a i n l yi n c l u d ew o r k sa sb e l o w ： 1 ) s t u d y i n gs o m et e c h n o l o g yr e l a t e dt on a t u r a ll a n g u a g ep r o c e s s i n g ，b o r r o w i d e a sf r o mm e t h o d su s i n gi nr e s t r i c t e da r e a s ，b u i l dd i c t i o n a r yw i t hs t r u c t e de l e m e n t s a st h eb a s e o fa n a l y z i n ga n dp r o v i d es u f f i c i e n ti n f o r m a t i o nd u r i n gt h ea n a l y z e p r o f r e s s ； 2 ) u s i n gm o r p h o l o g i c a lm a r k ，o p t i m i z i n gt h e “d a t a b a s es c h e m a e x t r a c t ” t e c h n o l o g y , g e n e r a t es q lc o d e st h r o u g hp r o c e s s i n gt h es e tb l o c ko ft h es e m a n t i c d e p e n d e n c et r e e 3 1 s t u d y i n gp o p u l a rm e t h o d so fc o d e sa s s e s s i n gp r o b l e m b o r r o wi d e a sf r o mt h e c o m p i l ep r o c e s s ，a n a l y z et h ec o d e ss t a t i c l ya n db u i l dt h ea b s t a c ts y n t a xt r e et os a v e t h ew h o l ei n f o r m a t i o ni n c l u d e di ns q l c o d e s ，t h e nc a l c u l a t et h et r e ee d i td i s t a n c ea n d t h es i m i l a r i t yb e t w e e nt a r g e tc o d ea n ds o u r c ec o d e ，a n da d o p tw e i g h tf a c t o rt o e m b o d yt h ed i f f e r e n c eo ft e s td e m a n d s ； 4 ) g e n e r a t i n gn o d e k n o e l e d g er e f l e c t i n gs e tt os a v et h ec o n n e c t i o nb e t w e e n e a c hn o d ea n di t sr e l a t i v ek n o w l e d g e ，t h e nt h e p l a t f o r mw i l lp u s ht h ek n o w l e d g et o i l l 江苏大学硕士研究生毕业论文 u s e r sw h e nm i s t a k eo c c u r s ； 5 ) d e s i g n i n ga n di m p l e m e n t i n gt h eo r i g i n a ls y s t e m ，v e r i f y i n gt h ef e a s i b i l i t yo f a l lt h em e t h o d sp r o p o s e db yt h i sp a p e ra n dt e s tt h ep l a t f o r m sf u n c t i o nb yu s i n gi ti n p r a c t i c e k e y w o r d s ：n a t u r a ll a n g u a g ed a t a b a s e ，c o d ea s s e s s m e n t ，a b s t r a c ts y n t a xt r e e ，s e m a n t i c d e p e n d e n c et r e e i v 江苏大学硕士研究生毕业论文 目录日豕 摘要l a b s t r a c t i i i 第一章概述。1 1 1 研究背景及意义1 1 2 国内外研究现状一l 1 2 1 自然语言数据库接口技术2 1 2 2 代码相似度匹配2 1 3 研究内容及组织形式3 第二章相关研究工作5 2 1 自然语言处理技术一5 2 1 1 基于模式匹配的分析技术5 2 1 2 基于格语法约束的分析技术6 2 1 3 基于语义依存的分析技术一7 2 1 4 基于扩充转移网络的分析技术8 2 2 代码自动评估8 2 2 1 属性计数法9 2 2 2 结构度量技术1 l 2 2 3 动态评估方法15 2 3 本章小结15 第三章自然语言查询1 6 3 1 总体框架1 6 3 2 数据库规范化1 7 3 3 自然语言代码分析j 18 3 3 1 结构化字典1 8 3 3 2 词性标注19 3 3 3 单词提取2 0 3 4 语义关系描述2 2 3 5 查询代码生成2 5 3 6 存储过程生成2 6 3 7 本章小结2 6 第四章代码评估及知识推送2 7 4 1 处理流程2 7 4 2 查询语句的结构化描述2 8 4 2 1 规范化处理2 8 v 江苏大学硕士研究生毕业论文 4 2 2 记号抽取及自动机构造3 0 4 2 3 结构化描述3 3 4 3 存储过程的结构化描述3 4 4 3 1 参数规范化处理3 4 4 3 2 构造依赖向量3 4 4 4 查询语句相似度匹配3 5 4 4 1 树编辑距离3 6 4 4 2 引入权重因素3 7 4 4 3 相似度的计算3 8 4 5 存储过程相似度匹配3 8 4 5 1 转化依赖向量3 8 4 5 2 匹配依赖向量3 9 4 6 异同节点知识推送4 0 4 6 1 语法树树映射4 0 4 6 2 知识点映射及推送4 2 4 7 本章小结。4 3 第五章原型系统4 4 5 1 体系结构4 4 5 2 核心类设计4 5 5 2 1 词性标注及单词提取4 5 5 2 2 代码评估4 6 5 3 系统实现4 8 5 3 1 开发工具4 8 5 3 2 原型系统实例4 9 5 4 评估准确性影响因素5 4 5 5 本章小结、5 4 第六章总结与展望5 5 6 1 总结5 5 6 2 展望5 5 参考文献5 7 v i 苏大学硕士研究生毕业论文 1 1 研究背景及意义 第一章概述 数据库是数据管理的最新技术，是计算机科学的重要分支。随着科学技术的 飞速发展，人类获取的数据量急剧增加，信息资源已经成为各个国家及部门重要 的财富。作为信息系统核心的数据库技术也成为现代社会信息处理中最为关键 的技术之一。 数据库课程是高校计算机专业学生必修的专业基础课程，根据中国计算机科 学与技术学科教程c c c 2 0 0 2 ( c h i n ac o m p u t i n gc u r r i c u l a2 0 0 2 ) 1 2 j 标准，数据库系 统被明确规定为计算机科学与技术学科专业的1 6 门核心课程之一。因此，提高 数据库课程的教学质量变得尤为重要。然而，传统的数据库实践教学环节存在诸 多不足l j 】，如：教师以一对多的方式进行实验教学，反复解答学生提出的大量共 性问题：学生自我学习环节缺乏支撑及管理；教师评价环节任务繁琐等。由于教 学实践中，教师必须对学生的问题进行逐个解答，而这些问题中大部分是重复的， 无疑增加了教师的工作量，使学生无法及时得到教师的指导，教学效果不理想。 随着计算机网络的高速发展，网络学习方式以其灵活高效，智能互动等特色 得到了广泛的应用。数据库课程的实验和自主学习同样可以借助这一新颖高效的 方式，通过构建数据库学习支撑平台，达到支持和自动评估学习者的实验过程， 同时，组织利用数据库课程实验已有的知识去帮助学生完成课程实验的全过程。 学习者使用这个平台不仅能够进行数据库的实验，还能够在有疑问或者错误的地 方得到准确的指导。教师可以借助该平台监督管理学生的学习及实验情况，清楚 把握学生知识上的薄弱点，完善教学环节。 数据库技术是当今信息处理的基本手段，数据库课程是国内高校计算机专业 学生必修的专业基础课程，数据库课程建设的好坏直接影响到培养学生的质量的 高低。构建数据库实验学习支撑平台，探讨课程实验教改的新模式，不仅对本课 程实验环节教改具有重要的意义，而且对其他课程的教学实验的教改，具有十分 重要推广应用价值。 1 2 国内外研究现状 本文着重研究数据库实验学习支撑平台构建过程中自然语言描述的查询要 求向s q l 代码转化以及代码相似度匹配的问题。第一个问题是如何将按照某些 规则描述的自然语言查询要求转化为s q l 代码，作为用户结题遇到困难时的参 江苏大学硕士研究生毕业论文 考答案。第二个问题是如何将用户提交的代码与参考答案进行有效的匹配并反馈 结果。这两个问题中第一个问题涉及到自然语言数据库接口技术，第二个涉及到 代码相似度匹配。下面将分别介绍这两个方面的研究现状。 1 2 1 自然语言数据库接口技术 自然语言数据【4 1 库允许用户用自然的语言对数据库的内容提出各种操作要 求，然后由系统自动地将其转换为数据库的操作语言，从而在数据库中查询到正 确的信息，提供给用户。在经历了多年的发展后，已经诞生了多个自然语言数据 库系统如： 1 ) l u n a r 副，l u n a r 系统用来协助地质学家查找、比较和评价阿波罗飞 船带回的月球岩石和土壤标本的化学分析数据。l u n a r 通过扩充转移网络 ( a 1 m ) 句法分析器对输入句子进行句法分析，生成语法树并翻译成一种以谓词 形式来表达查询请求的形式化语言，最后对数据库执行这个查询语言表达式，以 产生该请求的回答。本文2 1 4 节将对a t n 进行介绍。 2 ) p l a n e s 6 1 ，p l a n e s 系统针对飞机维修数据及飞行信息查询。同样采取 a t n 语法分析技术，同时引入上下文寄存器和概念格框架处理语义信息。它能 够接受复杂的语法请求。 3 ) 微软公司的e n g l i s h q u e r y 【7 】，e n g l i s hq u e r y 提供一个自动化a p i ，该a p i 使用户得以解决就s q ls e r v e r 数据库中的信息用自然语言提出的问题。给出与 s q ls e r v e r 数据库关联的实体和关系的定义后，e n g l i s hq u e r y 将就数据库内的 数据用自然语言提出的问题翻译成一组s q ls e l e c t 语句，然后可以对这个s q l s e r v e r 数据库执行这些语句以找到答案。 国内中文自然语言数据库的研究主要是从九十年代之后开始的，这些研究提 出了关键词及句法模式匹配、扩充转移网络，语义依存等理论。但是在这些理论 的研究的基础上并没有诞生出成熟的系统。随后孟小峰教授等人从领域知识自动 提取、自然语言分析处理和受限领域查询语言等角度对中文自然语言数据库系统 进行深入探索，开发出n c h i q l 系统【4 】，该系统是个内容广泛的可移植的通 用自然语言数据库系统。它包含数据库与词典，领域知识提取子系统，自 然语言处理部分及用户界面管理四个部分组成，可以满足复杂的中文自然 语言信息检索要求。 1 2 2 代码相似度匹配 代码相似度匹配的研究在抄袭检测和e 1 e a r n i n g 环境中有着广泛的应用。在 面向教学领域的研究方面，国内外有许多针对程序设计语言( 如c ，c + + ，j a v a 等) 的自动化评估研究，这些研究采取的方法主要有：系统依赖图( s d g ) 8 q o l ，抽 象语法树( a s t ) 【1 1 ，12 1 ，以及动态运行评价等方法。也出现了许多成熟的自动评 估系统，如： 江苏大学硕士研究生毕业论文 1 ) n c r e 上机考试系统，是由教育部考试中心针对全国计算机等级考试开 发的，该系统包括一级、二级、三级共3 种等级的上机考试，从二级考试以上就 包括多种程序设计语言。对于其中的程序题评阅部分，采用的就是动态评分方法， 使用多个测试数据集运行程序来进行评分，有一定的借鉴价值。但该系统的不足 之处在于对程序的评阅依赖运行结果，有0 分或满分的极端现象存在，而不是采 用按劳动成果给分的原则。 2 ) b o s s 系统i 乃j ：w a r w i c k 大学开发，用于网上提交程序作业，用i a v a 编 写，具有很大的跨平台兼容性。系统按功能将作业提交、评分、测试划分到不同 的服务器，使得某个功能的出错不会对其他应用造成影响。但其客户端不是基于 网络的，必须在u n i x 系统下启动，并且安装很困难。它采用面向方法的测试， 评估由系统自动完成，但仍然由教师来给最终的分数，是一个半自动化的程序评 分系统，仅仅提供考核的参数供教师参考。 3 ) a n a l y s i s 系纠1 4 1 ：英国n o t t i n g h a m 大学开发，系统考虑了静态评分与动 态评分的诸多要素。引入软件工程的理念，将影响软件质量的正确性、可维护性 和效率作为考核一个程序的标准。通过使用测试数据集动态执行程序来查看程序 的正确性和效率。通过建立程序复杂模型、难点模型、编程风格模型来衡量静态 评分因子。系统能比较全面地去评估学生的表现。 综上研究表明，代码相似度方向的研究主要集中在程序设计类语言上，针对 数据库查询语言s q l 的相似度分析研究还有待深入开展。 1 3 研究内容及组织形式 为了解决用户从自然语言描述的查询要求获取参考答案以及自动评估学习 者提交代码的问题，论文进行了如下的研究工作。 1 ) 研究自然语言数据库的相关技术，分析了常用的处理方法。结合s q l 语 言和本文应用实际情况对自然语言描述的查询进行单词的扫描和提取并进行语 义分析，采取结构化的方式描述查询要求所蕴含的语义信息。 2 ) 针对结构化的描述形式，给出了将其转化为s q l 代码的算法。 3 ) 研究s q l 语句的语法语义抽取技术。将目标代码和源代码的语法语义信 息进行分析提取，采取结构化的描述方式完整保存s q l 代码包含的信息。 4 ) 给出了s q l 结构化评估方法。结合s q l 语法规范，静态地评估源代码 和目标代码结构化之后的相似度，将评估结果返回给学习者。 5 ) 原型系统的设计验证。通过设计开发数据库实验学习支撑原型系统，验 证本文研究内容的实用性和有效性。 本文结构分为六章，组织形式如下： 第一章对项目的研究背景及其中两个关键技术在国内外研究现状进行分 3 江苏大学硕士研究生毕业论文 析，确定本文的研究内容以及所需要解决的主要问题； 第二章对自然语言处理以及自然语言数据库相关的理论方法分别进行阐述 和讨论，并指出了它们的适用范围和存在的不足； 第三章通过对自然语言描述的查询要求进行分析，构造结构化字典和引入 词性标注信息，采用语义依存树为手段描述查询要求中包含的信息，最后适用集 合块划分技术将其转化为等价的s q l 代码； 第四章通过对学生提交的目标代码和参考答案源代码进行静态分析，抽取 各自的结构信息，构造自动机并转化为抽象语法树，构造依赖向量记录存储过程 中的变量依赖。再采用包含权重因子的树编辑距离计算方法得出两棵树的相似度 并以此作为学生代码的评估结果； 第五章设计并实现了数据库学习支撑平台原型系统，验证本文提出方法的 可行性，通过实际运行该系统测试各个模块的实用性和准确性，并分析了影响评 估结果准确性的因素； 第六章总结和展望，对本文工作进行总结，对本文涉及问题域的进一步研 究及改工作进行了分析。 4 第二章相关研究工作 分别介绍并研究自然语言处理和代码自动评估方面的研究工作。自然语言处 理方面，研究基于模式匹配、基于语法格、基于语义依存的分析技术等。自动评 估方面介绍了从静态和动态两个方面介绍并研究了常用的处理技术。 2 i 自然语言处理技术 自然语言处理，是用计算机通过可计算的方法对自然语言的各级语言单位 ( 字、词、语句、篇章等等) 进行转换、传输、存贮、分析等加工处理的科学【1 5 】。 从研究的侧重点角度看，自然语言处理研究主要有两方面【l6 】，其一是偏向于理 论的自然语言理解研究，它一般偏向于用计算机分析自然语言输入，从中得出与 输入有关的一些结论；其二为机器翻译研究，它较偏向于实用效果，主要面向不 同自然语言文种之问的转换；也包括自然语言表达到系统内部命令形式的转换， 即自然语言接口研究。目前，自然语言处理的研究成果已在数据库系统设计、大 型软件包、人工智能研究、专家系统设计等领域得到了广泛的应用。自然语言处 理的难点在于自然语言的多义性。解决这一问题的方法是将自然语言的输入转化 为内部非多义性描述。 从分析处理整体方法的角度可以将主要的自然语言分析技术分为如下几类： 基于模式匹配的分析技术、基于格语法约束的分析、基于语义依存的分析和扩充 转移网络语法( a t n ) 。 2 1 1 基于模式匹配的分析技术 模式匹配是最简单的一种自然语言分析技术，它把输入的语言表达作为一个 整体看待。模式中出现的变量可以匹配任意单词序列，对输入的语表达式的解释 是通过单词模式与输入表达式之问的匹配得到的。模式和解释都是递归的概念， 与每个模式相联的是一种解释，该解释可以用来构造更高一级的解释，也可以直 接作为一种解释输出。考虑下面的模式p l , p 2 有： p l ：x 喜欢y ； p 2 ：x 看y 对自然语言表达式s = “我喜欢看书”进行分析会得出如下结论： 依照p ，分析，x _ “我”，y _ “看书”； 依照阳分析，x - “我喜欢 t 73 , y = “书 。 从上面的例子里我们可以看出，对于同一条语句，依照不同的模式分析往往 会得到不一样的结果。在大型系统中，输入端提供的自然语言语句可能非常复杂， 江苏大学硕士研究生毕业论文 同时系统中也包含成千上万的模式，因此必然出现大量不一致现象。这是因为基 于模式匹配的分析技术没有考虑到语言语义结构等重要信息，这样，若单单采用 模式匹配分析技术就会使得许多模式含有相同的子模式。为了解决这一问题，在 此基础上发展处了层次模式匹配技术。在层次模式匹配中，首先采用子模式对输 入进行局部匹配，形成一些规范的结果，然后用这些结果与更高一层的模式进行 匹配，直到顶层模式可以匹配整体输入为止，其对应解释是通过从低层到高层构 造形成的。但是其缺点是模式层次复杂，遇到复杂语义描述的语句时，不能从根 本上解决分析结果不一致的问题。另外，正因为模式是一种递归的概念，因此实 际应用中很难确定模式的嵌套或递归深度，解决这一问题只能依靠对领域语言结 构的分析，以确保输出的解释与语言本身的描述语义相似度最大化。 2 1 2 基于格语法约束的分析技术 格语法的概念是f i l l m o r e 于1 9 6 7 年在论文t h ec a s ef o rc a s e 1 。中提出的。它 的提出试图探讨句法结构与语义之间关系。传统语言学中的格只是表层格，格语 法中的“格”是“深层格”，它是句子中体词( 名词，代词等) 和谓词( 动词，形容 词等) 之间的及物性关系( t r a n s i t i v i t y ) ，这些关系是语义关系，它是一切语言中 普遍存在的现象i l 引。这种格是在底层结构中依据名词与动词之间的句法语义关 系来确定的，这种关系一经确定就固定不变，不管它们经过什么转换操作，在表 层结构中处于什么位置，与动词形成什么语法关系，底层上的格与任何具体语言 中的表层结构上的语法概念没有对应关系。 按照格语法技术来分析自然语言，首先要构造出格框架。格框架是由一个头 部和一组辅助概念( 也称域) 组成的。辅助概念以规范的定义形式与头部概念相联 系。格框架的头部一般由动词组成，每个域对应于一个格。另外，到底需要多少 “格”并没有定论，f i l l m o r e 曾给出建议格应包含以下几种： 1 ) 施事格：事件或行为的执行者、行动者、表现者。 2 ) 感受格：某种行动后果的承受者、接受者。 3 ) 对象格：动作对象或考虑对象。 4 ) 工具格：导致某事件的物理手段或精神刺激。 5 ) 来源格：事物的来源( 地) 。 6 ) 目的格：事物的目的( 地) 。 7 ) 场所格：事物所处场所。 8 1 时间格。 9 1 路径格。 例如，t h es t u d e n ts o l v e dp r o b l e m s w i t hac a l c u l a t o ri nt h ec l a s s r o o mt h i sm o r n i n g ( 学生今天早上在教室里用计算器做习题) 的格语法用语义网络形式表示( 图2 1 ) 是很方便的。 6 江苏大学硕士研究生毕业论文 图2 1 一个语义网络图 在实际问题中究竟设置多少格，完全根据问题需要和运用是否方便来定。因 此在格的设定上容易产生误差，这也导致了采用格语法分析难以支撑大规模的通 用系统。 2 1 3 基于语义依存的分析技术 法国语言学家t e s n i e r e l 在其1 9 5 9 年所著的结构句法基础一书提出了 依存语法这一概念。依存语义观点认为认为句子是一个“有组织的整体”，其组 织性体现于构成句子的词和词与相邻词之问的“联系”，所有这些联系构成了句 子的框架1 1 9 1 。r o b i n s o nj j 在对这一概念进行细致地研究之后于1 9 7 0 年提出了依 存关系的四大公理，为依存关系奠定了基础，这四条公理是f 1 5 】： 1 ) 一个句子中只有一个成分是独立的，不受任何成分支配； 2 ) 其他成分直接依存于另外的某一个成分； 3 ) 何一个成分都不能直接依存于两个或两个以上的其他成分； 4 ) 如果a 成分直接依存于b 成分，而c 成分在句中位于a 成分和b 成分 之间的话，那么，c 或者直接依存于a ，或者直接依存于b ，或者直接依存于a 和b 之间的某一成分。 基于依存语义的分析结果也是采用结构化的描述方式，通常称这一输出为 “依存树”，其中包括动词，行动元( 由名词词组组成) 和状态元( 由副词词组 组成) ，以动词为分界线，行动元位于动词的左边，状态元位于动词的右边。图 2 2 是句子“张三的大哥轻轻地点头”的依存树。 占盟 、 哥轻轻地 张三大 图2 2 语义依存树示例 依存树具有简洁，便于处理的特点。这也使得基于语义依存的分析技术成为 目前使用最普遍的自然语言分析技术之一。 7 江苏大学硕士研究生毕业论文 2 1 4 基于扩充转移网络的分析技术 扩充转移网络( a t n ) 是美国人工智能专家w a w o o d s 于1 9 7 0 年提出的1 2 0 l 。 它采用状态图来控制自然语言的分析过程。每幅状态图相当于一个网络，由状态 和边构成，在状态图的各条边上，可以注明所分析的词，或词组类型符号( 如名 词词组注为n p ，介词词组注为p p ) 。每一个词组类型符号又可以作为一个子网 络的开头，因而当采用扩充转移网络来分析自然语言的句子时，如果分析到某一 词组类型符号，就可以转移到相应的子网络，如果处理结束或处理失败，可再回 到原来的网络继续进行分析，直到分析完整个句子为止。 假设我们有下列语法规则： ：= ； ：= ； ：= l ； ：= ； ：= i ； ：= ； ：= i 则上述语法规则的a t n 转移网络如图2 3 所示： 名训矩语3 等x 蔓户争( = p 聊 p o p 图2 3a t n 网络示例 这样我们便很容易判断一个句子是否符合上述语法规则。例如，句子：t h e l i t t l eb o yk i c k e dt h eb a l l ，可以通过上面的状态路径并最终到达终点输出，而句子： t h el i t t l eb o yi nt h es w i m s u i tk i c k e dt h eb a l l ，就没办法通过。 扩充转移网络在人机对话和机器翻译的研究中得到了广泛的应用，许多自 然语言信息处理的专用软件都是根据扩充转移网络的原理设计的，如1 2 1 节中 l u n a r 和p l a n e s 两个专用系统就是基于a t n 技术设计实现的。 2 2 代码自动评估 程序自动评估是一种使用计算机来代替人工进行学生程序评测的方法。不管 评测对象是什么语言，其方法可归结为两大类：动态方法和静态方法【3 , 2 1 1 。两者 8 江苏大学硕士研究生毕业论文 的目的都是为了核查程序的正确性。其中，动态评估方法通过使用测试数据执行 代码，然后对比输出与预期输出的一致性来评测，它能发现执行时错误。而静态 评估方法并不执行程序，只通过检查代码的结构和语法来进行评测，它能发现静 态错误( 无限循环、冲突条件等) ，并产生统计信息( 变量个数，行长度等) 。动 态评估方法虽然理论足够但实践不强，对于主观性很强可变性很大的程序设计 题，目前尚没有很好的解决方案。本节将主要讨论代码静态评估方法。 我们评估代码的目的是给出目标代码和源代码的相似度并返回语法语义上 相异的节点。为此我们借鉴y a m a m o t o 等人对大规模软件系统相似度的定义1 2 2 l 来理解代码之间的相似度。y a m a m o t o 对软件系统之间的相似度定义如下： 设有一个软件系统尸是由p ，勘，；脚这些元素组成的，则可以将系统j p 记为 集合p ，助) 。同样的，软件系统q 可以记为 g ，钐：劬) 。同时假设我们能 够得到两个元素p ，和缈( j 对嘲，j 对面) 之间的匹配，并且称b ( 如图2 4 所 示) 为匹配元组( p ，缈) 的集合，其中r s c p xq 则尸，q 两个系统之间的相似度 s i m ( p ，9 可以描述为公式2 1 ： s i m ( p ，9 ：也划立丛丝呈争蚌爿努弘鱼盟立呈型 公式2 1 图2 4 系统只p 之问的匹配元组集合胎 上面我们提到代码评估主要可分为两种途径：静态评估和动态评估。动态评 估简单高效但是评估结果可信度较低。与动态评估对应的是静态评估方法，它可 分成两类：属性计数技术和结构度量技术【2 3 1 。下面将作具体介绍： 2 2 1 属性计数法 属性计数法是从程序中提取出数个软件度量特征，计算每一个程序的n 个 不同的软件度量指标，以便于将程序映射到一个n 维的笛卡尔空间，然后利用 向量空间模型来度量程序代码相似性。该方法最初是应用在软件抄袭检测系统 上的，上世纪7 0 年代出现了基于属性计数法的抄袭检测系统，这些系统大多采 用h a l s t e a d 的软件系统度量方法【2 4 1 ，m c c a b e 提出的圈复杂度理论【2 5 】以及域计数 理论【2 引。这些方法或者理论为描述一段代码的容量、控制流、结构、数据依赖、 9 江苏大学硕士研究生毕业论文 嵌套深度、控制结构这六种信息奠定了基础。当然，仅针对前面提到的六种信息 中每一种信息的度量都可以单独用于计算两个系统或者两段代码之间的相似度。 但是若要追求相对的高精准度，还是要综合这六种信息的度量结果。下面就介绍 这六种基本度量信息： 1 ) 容量 大多数容量度量方法采用的指标过于单一2 7 1 ，如l o c ( l i n e so f c o d e ) 方法用 来计算代码行数作为系统容量的度量，在此就不在一一介绍。相比而言，h a l s t e a d 的容量计算方法抽取了软件系统中有代表性的属性元组加以计数。依照h a l s t e a d 的方法，一段代码主要包含以下四个属性【2 4 , 2 7 , 2 8 1 ： 刀，_ 代码中唯一的操作符数； 坳= 代码中唯一的操作数数； n ，- 代码中操作符总数； n 2 = 代码中操作数总数。 在抽取的系统的四个基本属性之后，h a l s t e a d 随后又定义了词汇数n = ，? j + 砌 以及代码长度n = n i + n 2 另外还有一个重要的属性“容量”，h a l s t e a d 定义其为： v = n l 0 9 2 ”定义中的y 即为属性“容量j , t 考虑到公式中的是一个整数， 那么v 就可以以“位”( b i t ) 为单位来表示，这样我们可以将v 看做代码所需存储 容量的表利2 7 1 。事实上，直接通过h a l s t e a d 方法便可以得出一组代码的相似度， 可以将一段代码所包含的属性用h a l s t e a d 特征向量表征出来：日阮m 功。在一组 待测相似度的程序中，每一个程序都用这样的特征向量表示出来，最后通过测试 这些特征向量之间的“距离”( 如欧几旱德距离) 来得到程序之间的相似性1 3 j ， 但是这样做往往忽略的代码中包含的重要信息，所以还要融合下面将提到的其他 属性综合考量。 2 ) 控制流 m c c a b e 提出的圈复杂度是通过计算一段程序代码的执行路径来描述该段代 码的控制流的。事实上这种方法是软件系统开发周期复杂度描述方式的一种。 m c c a b e 的方法着眼于最终成型的源代码，因此可以将该方法用来描述代码执行 过程中的控制流。方法将程序代码转换为一个带有唯一入口和出口结点的控制流 图。这种方法具有语言依赖性，这意味着在创建控制流图前，必须理解编写代码 的语言的语法和语义【2 3 】。在一段程序的控制流图中，节点表示每一个顺序执行 的声明( s t a t e m e n t ) ，边表示代码的执行路径。一个有p 条边和刀个节点的控制流 图g ，其圈复杂度定义为： 以g ) = e 一刀+ 2 p 公式2 2 其中：p = 控制流图中的模块数。为了帮助创建