（计算机软件与理论专业论文）编程题自动阅卷技术的研究与实现.pdf

摘要 在计算机语言类相关考试中，编程题的自动阅卷技术是一项非常具 有实用价值的应用，也是实现计算机在线考试以及全自动阅卷的一个关 键技术。由于程序实现同一功能的代码具有多样化的特性，因此，标准 答案的制定变得很复杂。并且，即使得到了标准答案，还需考虑到考生 的答案未满足标准答案要求但也可能得分的情况。 专家学者们致力于去寻找个程序的中间表示形式，并希望通过这 样的一种形式来表示程序的标准答案，然后把考生的代码也通过同样的 方法进行转换，最后来对它们进行匹配，根据匹配的程度来评分。人们 发现，系统依赖图是这样的中间形式的一种较好选择，因此，许多自动 阅卷系统和文献都提到了基于系统依赖图的转换。 本文以具有代表性的编程语言c 语言作为研究对象，提出了一种用 正则表达式来描述程序得分点的评分模型，这些得分点相互独立，互不 影响。此模型模仿人工阅卷的特点，从考生代码中搜索得分点，从而得 到一个匹配的情况，以此作为考生程序评分的依据之一。同时，在考生 程序源代码上进行词法和语法的分析来统计语法错误的数量，作为考生 程序评分的依据之二。在对语法错误检查的过程中，本文也提出了一些 有效的避免虚假错误判断的方法，提高了评分的准确度。 利用本文所述的方法对有限的编程题实例进行了自动评分，结果较 为接近人工阅卷。 关键词：自动阅卷，c 语言，正则表达式，文法，同步记号 a b s t r a c t i n c o m p u t e r - e x a m i n a t i o n s ，t h et e c h n i q u e o fg r a d i n g p r o g r a m a u t o m a t i c a l l yi sav e r yv a l u a b l ea p p l i c a t i o na n dap i v o t a lt e c h n i q u ef o r i m p l e m e n t i n go n l i n ee x a m t h e r e a r em a n yw a y st oi m p l e m e n taf u n c t i o n b yp r o g r a m s od r a w i n gt h es t a n d a r da n s w e rb e c o m e s c o m p l e x m o r e o v e r ， e v e t li ft h es t a n d a r da n s w e ri sa c h i e v e d , a n o t h e rc a s et h a ts t u d e n t s p r o g r a mm a y b ep a r t i a l l yc o r r e c tw h e ni td o e s n tm a t c ht h ea n s w e rm u s t b et a k e ni n t oa c c o u n t m a n ye x p e r t sa n ds c h o l a r sa r eb e n d i n g t h e m s e l v e st of i n da ni n t e r i m f o r ma n da t t e m p tt ou s es u c haf o r mt od e n o t et h es t a n d a r da n s w e r w h e n t h ef o r mi sf o u n d s t u d e n t sc o d e sw i l lb et r a n s f o r m e di nt h es a m ew a y a n d f i n a l l ym a t c ht h et w oi t e m st og e tad e g r e ef o rg r a d i n g p e o p l ef i n d t h a tas y s t e md e p e n d i n gg r a p hi san i c e rc h o i c eo f t h em i d d l ef o r ms ot h a t m a n ya u t o c h e c k i n gs y s t e m sa n dl i t e r a t u r e sh a v eb e e nm e n t i o n e d 。 t h i sp a p e ru s e sr e g u l a re x p r e s s i o n st od e n o t es u c hm i d d l ef o r m sa n d s i m u l a t et h ec h a r a c t e r i s t i co fm a n u a lw o r k r e g u l a re x p r e s s i o n sa r eu s e d t od e s c r i b et h es c o r ep o i n t s s e a r c h i n gt h e s es c o r ep o i n t sc a no b t a i na m a t c hr e s u l t sw h i c hc a nb eu s e dt og r a d et h es t u d e n t s p r o g r a m f u r t h e r m o r e ，e r r o rq u a n t i t yi sc o u n t e db yl e x i c a la n a l y z i n ga n dp a r s i n gi n t h i sp a p e r s o m eu s e f u lm e t h o d sf o ra v o i d i n gi l l u s i v ee r r o ri n f o r m a t i o n a t ep o i n t e do u ti nt h i sp a p e ri nt h ep r o c e s so f s y n t a xe r r o rc h e c k i n g u s i n gt h em e t h o dm e n t i o n e di i lt h i st e x tt oa u t o c h e c k i n gp r o g r a m s c a no b t a i nas i m i l a rr e s u l t 嬲m a n u a lc h e c k i n g k e y w o r d s ：a u t o c h e c k i n g ，cl a n g u a g e ，r e g u l a re x p r e s s i o n , g r a m m a r , s y n c h r o n i z e dt o k e n 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说 明。 作者签名：盈兰丝 日期：珥年月旦日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文：学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：隧导师签名l 叠幽周期：竺早年尘月丝日 硕士学位论文 第一章绪论 1 1研究背景 第一章绪论 世界上第一台计算机问世的时候，人们绝对不会想到它会发展到今天这样的 水平。它几乎已经渗透到了世界的各行各业的每个角落，当然也包括一直比较传 统的教育界。在过去几十年中，计算机以媒体的身份逐渐渗入到了教育领域，从 起初的幻灯和投影到现在的多方位辅助教学，经过几个阶段的发展，计算机已经 越来越多地帮助了教师的教学工作，减轻了教师的工作负担。随着信息技术的发 展与教育教学理念的改变，用新技术来支持教学过程的设计、互动分析与评价， 进而支持教师及其教学，在一定程度上解放教师的生产力，这已经成为一个重要 趋势。 近年来随着计算机辅助处理、多媒体技术以及计算机网络等技术的飞速发展 和推广应用，在计算机基础教育中采用计算机实现考试无纸化已成为目前发展的 必然趋势。无纸化考试涉及到多个重要组成部分，如题库的建立与维护，试卷的 智能组卷以及智能批阅等。其中试卷的智能批阅对于大规模的考试来说意义非常 重大。特别是当前各类计算机相关考试频繁，阅卷给教师带来了巨大的工作量， 因此，实现智能化批阅在目前来说尤为迫切【l j 。 目前客观题的自动阅卷技术发展已经相对成熟，如选择题和判断题等利用计 算机阅卷早已超越了人工阅卷【2 】，但主观题的阅卷技术却一直停滞难前1 3 】。其主 要原因是影响智能批阅的一些关键技术尚不成熟，如人工智能、模式识别、自然 语言的理解等还处于研究的初级阶段。因此，限于目前的技术水平，完全解决主 观题的自动测评问题是不现实的 2 1 。考虑到程序设计语言与一般的自然语言相 比，具有严格的约束和限制性，因此，可以把对编程题的阅卷作为对主观题阅卷 的突破口。 编程题是计算机考试中的常见题型，特别是近年来软件培训机构的迅速崛 起，对编程题的考核更是频繁。目前对编程题的阅卷仍然没有好的解决办法，如 全国计算机等级考试对编程题的阅卷仍采用一种单凭输出结果给定成绩的方法。 这种方法虽然简便，但很不科学。其道理很明显，它完全忽略了考生的源代码， 而这与人工阅卷恰恰是背道而驰的。 人们意识到，要想得到行之有效的方法，必须对考生源代码进行处理。因此， 如何分析考生的源代码进而了解其答题的正确程度，将成为攻克这一难题的关 键。目前虽然有很多研究者提出了一些见解，并能够解决了一定的问题，但真正 硕士学位论文第一章绪论 实用的系统还不多见。 1 2国内外发展现状 早在2 0 世纪6 0 年代，国外的一些专家和学者就已经开始研究如何对学生用 自然语言书写的文章进行自动评分，此后，经过4 0 多年的研究和开发，又出现 了许多针对不同需求和不同领域的系统，其中有的已经进入实用阶段，并取得了 较好的效果i lj 。 第一个实现类似功能的系统是e l l i sp a g e 在1 9 6 6 年开发的v r o j e c te s s a y c n a d e ( p e o ) 。p a g e 认为一个人的写作风格中蕴涵着可以被度量的内在特征，因 此只要对文章的内在特征进行量化，再对量化结果进行评价即可【l 】。 其后的l s a t * l ( l a t e n ts e m a n t i ca n a l y s i s ) 系统将每一篇文章视为一个空间 向量v ，列对应文档向量，行对应文档特征，一个文本产生出一个矩阵。用余弦 相关性计算法来度量标准文本向量和待批改文本向量的相似度。 e - r a t e r t 5 】系统主要由五个独立的模块组成，它们分别是句法分析模块、篇章 分析模块、内容分析模块、评分模型建模模块和评分模块，通过对每个模块进行 评价之后得到一个由多个分数组成的集合，最后这些分数的一个调整平均数被给 出，作为待改作文的分数。 a t m l 6 1 系统是种针对菲多项选择、有明确答案且答案简短类型题目的新的 计算机辅助评分方法，它可以对用自然语言书写的答案的内容进行评判，并且能 够用在各种具体学科上。a t m 的两个主要模块是语法分析器和语义分析器。a 1 m 提供了一个交互式语法分析器，它不管输入的句子语法上是否正确，也不管句子 语法是否极其错综复杂和有歧义，它都可以进行分析，并且分析器的语法规则可 以进行扩充，如包含扩充短语结构语法，以便适合更广泛的语法分析要求。而 a t m 最具特色的是它的语义分析器，它为自然语言的深层语义结构建立了一种 模型，从而实现了基于语义的自动评分。 a u t o m a r k 【1 是个针对开放式问题的任意文本答案的自动批改系统。系统开 发者认为，对任意文本的自动批改可以归结为信息撷取工作，学生的答案是待挖 掘的文本，每个问题对系统而言就是一个个不同的领域，从文本中找出与领域相 关的概念，即该问题的正确答案。a u t o m a r k 利用自然语言处理技术对学生的答 案自动搜索符合自动评分模式的内容。在这里，系统试图模拟人工打分的过程， 只关心学生是否真正理解并正确回答了问题，而对答案中出现的错别字或语法错 误则不追究。 在对主观题自动阅卷技术研究的同时，编程题的自动评分技术也慢慢地发展 起来。由于编程语言的词法和语法的许多限制，使得编程题的分析较自然语言来 2 硕士学位论文第一章绪论 说要容易，因此，其发展速度也相对较快。目前，已有一些阅卷系统【1 。1 ，但真 正实用的系统却还很少。按照其评分方法来区分的话，可分为动态分析方法和静 态分析评分两种例。 动态分析评分是指把源程序通过编译器的处理，并输入某些特别选择的测试 数据集，比较运行结果与期望结果即可知道答案的正确性，从而给学生程序评分。 但由于这种方法必须运行考生程序，而实际上考生程序往往存在词法或语法的错 误而不能运行，也就得不到执行的结果，导致无法进行评价。这种模式的代表有 t r y 系统f l l 】，p s g e 系统f 1 2 】和b a g s 系统1 1 3 。 静态分析评分模式一般是指运用程序理解、语义分析或软件质量度量等方法 来分析考生的源代码，然后再与标准模块进行比较的一种方案。b e r r y 和m c c k i n g s 提出了一种基于程序风格度量的方法【1 0 1 。他们认为，程序可以由一些指定的特 征项来代表，如模块长度，标识符长度，注释等，所有这些特征项综合起来可以 对整个程序进行评价。类似实用软件度量方法的还有a s s i s t 系统【1 4 1 ，k n o t s 系 统n 5 】和v e r i l o gl o g i s c o p e 系统 1 6 l 等。这类系统虽然能够使用参数来表示程序的程 序结构、y o 模式、数据流以及控制流敏感的特征，但它在分析源代码时并没有 分析程序的语义，很难达到令人满意的结果。基于程序理解和语义分析的阋卷模 式相对而言更加适合对编程题进行自动评分，但由于其实现的难度较大，所提出 的模型还并不完善。但模型的一些关键技术的文献还是较多的，如程序切片技术 例，数据流分析技术m 等等。 目前国内现有的网络教育考试系统中以标准化试题居多，即使提供主观试题， 其阅卷过程也是由教师在计算机上手工完成。国内针对各类非标准化试题自动批t 改技术的研究刚刚起步，与之相关的文献也不多见。 王邯等针对当前计算机水平考试和等级考试中普遍采用的程序填空类试题， 探讨了计算机自动批改c 程序设计填空题的实现。系统的基本思想是对学生答 案与标准答案在语义上进行匹配。1 ) 采用类似于编译程序设计技术对标准答案进 行词法和语法分析，将其分解成标识符、常量和运算符，由各部分得到整体语义； 2 ) 对每个标准答案生成其语义等价类，因为c 语言中一个语句或表达式可能有多 个等价形式；3 ) 对学生的答案进行词法、语法分析并进行优化；4 ) 将处理后的学 生答案与等价答案匹配即可【”。该系统虽然初步实现了填空题的自动批改。但并 不适合编程题的阅卷，但其思想还是有许多可以借鉴之处。 对于编程题的自动评分，目前比较成熟的模型主要有以下两种：1 ) 基于程 序理解的评分；2 ) 基于语义相似度的评分【8 】。下面分别介绍一下此两种阅卷模 式的基本特点。 1 1 基于程序理解的编程题自动评分模型 3 硕士学位论文 第一章绪论 程序理解是软件逆向工程中的一个重要研究领域。它通过对程序进行静态的 分析，抽象和推理来获取知识。从编程题自动评分需要解决的核心阃题及主要任 务来看，它与一般程序的理解是一致的，因此可用程序理解的基本原理及一些方 法来解决编程题自动评分的问题。基于该思想提出了一个基于程序理解的编程题 自动评分模型。该模型以程序理解的一般过程所涉及的几个基本策略为依据，结 合人工阅卷的思维过程采用学生程序与模板程序相比较的方法给学生程序进行 评分。其主要过程如下： ( 1 ) 将程序转化为系统依赖图。 在系统依赖图的基础上使用一系歹l j 标准化处理方法，消除程序实现形式 的多样化。 ( 3 ) 在程序的规模、结构、深度及知识应用四个层次上进行学生程序和模板 程序的匹配，根据匹配结果的相似度及评分标准，给出程序分数。 该模型中采用的评分方法，符合人工阅卷的思维过程，且易于实际应用，仅 需提供模板程序即可。 2 ) 基于语义相似度比较的编程题自动评分模型 形式语义学是程序设计语言研究的一个重要领域，通过对语义等价性的研 究，可以发现具有结构等价的程序是可以进行替换的。其思想是将学生程序与多 个模板程序相匹配，通过计算学生程序与模板程序的语义相似度给学生程序评 分。语义相似度的高低决定学生程序的得分高低。在程序进行语义分析后，归纳 程序的等价语义性，对于具有等价语义的程序，消除语义的多样化，进行标准化 处理。 这种评分方法的依据是这样的；( 1 ) 学生程序的正确性可用事先做好的标准 答案进行定义；( 2 ) 如果学生程序的语义与标准答案之一的语义等价，则其语义 正确；( 3 ) 程序语义用系统依赖图来表示，具有等价系统依赖图的两个程序具有 等价的语义；( 4 ) 改变程序的计算形式而不改变计算结果，则称该转换为语义等 价转换，由此转化可将语义等价程序标准化为相同的系统依赖圈。 以上两种阅卷模型有一些共同的特点，其一是都需要事先做好模板程序，其 二是以系统依赖图作为程序的中间模式，而对系统依赖图进行处理。这种系统存 在一些不足之处，首先，在进行匹配时。由于模板程序个数的有限性可能导致少 量正确的程序在程序模板库中找不到匹配的情况，其次，这种系统对指针的处理 不甚理想，再者严格的词法和语法分析会将学生可能的一些笔误或者非规范的书 写当成严重错误丽导致得分偏低【1 8 】。 4 硕士学位论文 第一章绪论 1 3研究思路 本文的基本思想是模拟人工阅卷，按照人工阅卷的模式来进行处理。其基本 思想是：在组建题库的时候，要求对每道考题提供评分标准和得分点，使用恰当 的正则表达式来描述得分点，然后根据此正则表达式来对学生的程序进行评价。 本文所做的工作与前述的基于程序理解和语义相似度比较的阅卷模型颇有 不同，上述两种阅卷模型都是把程序当成一个整体来处理。在本文中，一个程序 会被拆分成若干得分点，再以正则表达式描述之，因此，本文使用的是一种分割 程序语义的处理方法。 利用正则表达式来描述程序的得分点，其实质与前述阅卷模型中所提到的模 板程序有相似之处。其不同点是正则表达式的描述把程序拆开成为以得分点为单 位的许多独立的模块，从而在考生的程序中去查找这些模块是否存在，而不是拿 整个程序进行完全匹配。相比之下，这种方法更加灵活、准确，也更加合理，更 类似人工阅卷。 对于一道编程题，考生所作的答案五花八门，有对有错，对的有多种形式， 错的更是千奇百怪，但总的来说，其结果并不外乎以下三种： 1 ) 能运行且结果正确的； 2 ) 能运行但结果错误的； 3 1 不能运行的。 这三种情况分析起来应用的手段和方法并不尽相同，因此，需要对这三种情 况分别进行处理。 首先，对于能运行且结果正确的，只需要分析其代码是否可信即可。也即分 析其正确答案是否通过正确的途径而得到。要肯定一点的是，在编程题中通过错 误途径得到正确答案的可能性还是很小的，当然这要排除那些投机取巧的考生通 过数学计算，然后只做一个正确输出的情况。因此，对代码的检查还是必要的， 只是可以采取比较简便的方法，如通过测试数据或利用正则表达式对关键部分进 行匹配检查等。 第二，对于能运行而结果错误的，大致可分为两种情况。其一，程序基本正 确，只是因为粗心而导致一些较小的错误。如多或少了一次循环等：其二，算法 错误，有些程序没有实现题目要求的关键部分的算法，当然得不到正确的答案， 也有这样一种情况，有些学生根本不会做而胡乱写了几个语法正确的语句，这也 列为算法错误。这两种情况，都可以用基于得分点的检查方式来进行评分。 第三，对于不能运行的，即含有词法或语法错误的代码，因为词法和语法的 正确性很明显也应该是程序题的一个评分点，因此必须对其词法和语法错误的数 硕士学位论文 第一章绪论 量进行统计，再来结合其他得分点的情况。然后才能得到程序的最后成绩。 统 计词法和语法错误并不能单凭编译器的报错，因为编译器的目的是方便程序员调 试程序，所以其要求非常严格，常常会产生错误级联的问题，从而导致评分产生 很大偏差，这种判错的方式对于阅卷系统来说是不可取的。因此，本文设计了一 个专用于评分系统的语法分析器，提出了一些有效的措施，较好的避免了类似问 题的出现。 本文采用正则表达式来检查考生程序与得分点的匹配情况，对于语法错误， 将构造词法和语法分析器进行处理。由于语法错误可能导致严格的r e 模式搜索 的失败，因此，在构造r e 时应注意忽略一些常见的语法错误。另外对于一些程 序的死循环等导致编译器锁住而不能退出的问题已有相关文献进行了讨论，本文 只在系统实现时给出具体解决，这里就不再赘述了。下面给出整个阅卷系统的设 计流程图： 图1 - 1 设计流程图 6 硕士学位论文第一章绪论 1 。4论文组织结构 论文共分为五章，结构如下： 第一章为绪论，介绍了本文的研究背景，提出了实现编程题阅卷的关键技术， 并阐述了它们在国内外的研究现状。在总结了编程题的实现所面临的理论和技术 障碍的基础上，提出了本文的研究思路，即用正则表达式处理文本匹配，构造词 法语法分析来检查错误。 第二章介绍了正则表达式。并对其在j a v a 中的应用进行了阐述，对它们的 具体实现所用到的理论和技术细节进行了研究和设计。在程序题的自动阅卷模型 中，评分标准将使用正则表达式来进行描述。 第三章介绍了词法分析器和语法分析器构造的过程，并用j a v a 构造了一个 处理c 程序的词法分析嚣和语法分析器。词法分析得到用于语法分析的t o k e n 串，并进行了词法出错的判断和处理。语法分析器分析考生程序的语法，进行了 语法出错的判定和处理。这一部分的主要目的是对不能运行的考生程序进行语法 锝分点的评判。 第四章给出了具体的评分方法，然后给出了一些实验数据，并对其进行了分 析。 第五章主要对本文所作的工作进行了总结，同时对以后的工作进行了介绍， 并对本课题的发展前景进行了展望。 7 硕士学位论文第二章程序的r e 描述 第二章程序代码的正则表达式描述 众所周知，在人工阅卷模式下，对一道编程题进行评分，必定有其评分标准。 这个标准指出哪些地方可得分，哪些地方需要扣分。同理，在自动阅卷模型中， 也需要有一个评分标准。这个标准必须在题库设计时予以指明。这种评分标准不 能以自然语言来进行描述，否则阅卷程序根本就不能理解。本文提出了一种用正 则表达式来描述评分标准中的得分点的方法。利用正则表达式来描述得分点，在 阅卷程序中可以直接用来与考生程序进行匹配，非常方便。 定义正则表达式( r e g u l a re x p r e s s i o n ) 是以下的一种： 1 基本( b a s i c ) i e 贝l j 表达式由一个单字符a ( 其中a 在正规字符的字母表 中) ，以及元字符e 或元字符中组成。在第1 种情况下，l ( a ) = a ) ；在第2 种情 况下，l ( e ) = e ；在第3 种情况下，h o 产 。 2 r ls 格式的表达式：其中r 和s 均是正则表达式。在这种情况下，l ( r is ) = l ( r ) u l ( s ) 。 3 r s 格式的表达式：其中r 和s 是正则表达式。在这种情况下，l ( rs ) = l ( r ) l ( s ) 。 4 严格式的表达式：其中r 是正则表达式。在这种情况下，l ( r ) = l ( r ) 。 5 ( r ) 格式的表达式：其中r 是正则表达式。在这种情况下，l ( ( r ) ) = l ( r ) ， 因此，括号并不改变语言，它们只调整运算的优先权。 其中，l c a ) 表示正则表达式a 所能表示的全部符号集合。 2 1正则表达式引入的可行性分析 程序由语句构成，而语句又由单词符号组成，因此，可以这样定义： 程序是一个单词符号按照一定规则组成的符号集合。 既然给定一个自动机，可以去判别一个单词符号，那么给定一个单词符号， 可以通过规约构造出其自动机。正如给定一个句子的结构如主谓宾等，可以造句； 同样给定一个句子。也可划分其句子结构，得到其主谓宾。 给定一个程序，其单词符号就已经全部给定。由编译原理的知识可以知道， 程序语言的单词符号可以通过自动机来进行描述，当已知程序的时候，可以通过 归约来得出每个单词符号的自动机。因此一个程序可以用单词的自动机来进行描 述。 8 硕士学位论文 第二章程序的r e 描述 例如，一个最简单的c 程序如下： v o i dm a i n o 通过规约，可知v o i d 为关键字( 也是标识符) ，m a i n 为标识符，“( ”、“) ”、 “ ”，“l ”为分界符，此程序可规约为： 。由编译原理可知，这些符号都可由自动机描述。 当然这样描述一个代码段虽然它不会把正确的代码判错，但它充当的几乎只 是一个模型而已，符合这个模型的代码都可以得到匹配。歧义性太大。但如果把 标识符和界符的一部分通过精确描述之后，那么情况就会得到很大的改观。比如 关键字指明为v o i d ，界符也具体指明，则得到的描述形式变成：v o i d 一标识符 一( 一) 一 一 ，若能将代码段规约成这样一种模式，其匹配的结果已经会很准确， 基本上已不会产生歧义了。 这里牵涉到一个选择精确描述的单词符号的问题，即什么符号应该进行精确 的描述。在实际的应用中，那些不具有多样性的单词集合可以精确化，根据题意 也可以精确化一些单词集合。对于多样化的代码，可以在描述的时候把多种方式 列为候选，则可以排除那些不在这些候选中的代码所导致的歧义。 利用正则表达式来描述程序与把程序代码中的单词规约成自动机相似， 2 1 1 正则表达式与自动机的等价性 正则表达式和有限自动机( f a ) 在接收语言的能力上是相互等价的。在这里， 只证明其充分性，其必要性在本文中并不重要，所以不给出具体证明 4 1 1 4 2 1 。 定理：对任何n f am ，存在一个正则表达式r ，使得l ( r ) = l 国) 。 证明：对于字母表z 上的n f am ，在其状态转换图上加进两个结点，一个 为x ，一个为y 。从x 出发用e 弧连接到m 的所有初态结点；从m 的所有终态 结点出发用e 弧连接到y ，从而形成一个新的n f a ，记为m ，它只有一个初态结 点x 和一个终态结点y 。显然，l ( m ) = l ( m ) 。即这两个n f a 是等价的。 对于新的n f am ，逐步消去其所有结点，直至只剩下x 和y 为止。消去的规 则如图2 一l 所示。在消除结点的过程中，逐步用正则表达式来标记箭弧。最后只 剩下从x 到y 的一条箭弧，其上的正则表达式与此n f a 等价。 9 硕士学位论文第二章程序的r e 描述 代拟o 如 靛以o 哪 图2 - 1n f a 消去的替换规则 既然程序可以用自动机来描述，而正则表达式又能够描述自动机，可以得出 结论，程序可以用正则表达式来进行描述。 2 1 2r e 描述的有效性分析 把一个特定的句子规约成语法符号虽然可行，但这个句子也必将丧失其意 义，变得毫无特点可言。如：h eg a v em ea b o o k 其中h e 为主语，g a v e 为谓语， f i l e 为间接宾语，b o o k 为直接宾语。因此这个句子可以用这样一个序列来描述： 显然，这个序列几乎不能表达任何意思，也把原语句的意义丢失了。其实这 是规约的必然结果。规约是把特殊的句子转化为一般的句子结构，这就必定会导 致精确度的丧失。 为什么要进行规约? 这个问题与为什么要引入r e 几乎是一个相同的问题。 答案很明显，对一个考生的程序，不可能去完成精确的搜索，谁有把握能搜索到 特定的语句s u m = 1 0 0 7 考生很可能会写成t o t a l = 5 0 或其它的形式。但如果要搜 索一个赋值语句，这样的多样化形式就会消除，满足条件的代码都会被搜索到。 换而言之，规约的目的就是牺牲精确度来换取匹配的可能。这也是用正则表达式 来描述程序得分点的目的所在。 需要说明一点，在一定的环境中，损失精度并不一定会产生歧义。举个简单 的例子：j i mg a v ej a c kab o o k 如果我是j a c k ，我和j i m 两个人单独在一起，那 么把这句话写成：h eg a v em eab o o k 这样不会丧失语句原来的意义，虽然将具 体的人名规约到了代词，但在一定的环境下并不会产生歧义。 如何保证全面又尽量少产生歧义是正则表达式描述的有效性的关键问题。首 1 0 羹 硕士学位论文第二章程序的r e 描述 先，对于程序设计语言来说，由于其词法和语法的约束，导致其语句具有一定的 特殊性，这是正则表达式描述程序的前提条件；其次，特定的题目要求会使考生 用特定的代码进行解决，而这些代码为了实现要求必然具有其特点，这也给了正 则表达式发挥的机会；再者，程序的代码有一定的上下文相关性，即完成一定功 能的代码之间有一定的依赖关系，这些代码共同构造了一个特定的环境，从而减 少了表达式出现歧义的可能性，这也给正则表达式的描述带来了方便；最后，正 则表达式自身强大的描述能力也是一个重要的原因。本文对c 语言的一些常用 语句以及常考的问题构造了正则表达式，并用m t r a c e r 严格测试，效果很好，说 明正则表达式描述程序是可行且有效的。 2 2正则表达式描述程序的方法 正则表达式的提出起源于1 9 5 6 年，神经生理学家m c c u l l o c h 和p i t t s 最早用 它来描述神经网络，后来被应用到信息技术领域中来。正则表达式第一个应用程 序是u n i x 中的q e d 编辑器，而现在，正则表达式引擎已经被u n i x 中的许多工 具所实现嗍。另外，许多的编程语言也支持正则表达式这一强大的工具，如j a v a 、 p y t h o n 、p e r l 等，而诸如p c r l 等脚本语言对正则表达式的应用更为常见，有些人 甚至认为正则表达式是p c r l 成功的关键。 正则表达式提供了功能强大、灵活而又高效的方法来处理文本，其全面模式 匹配法可以快速地分析大量文本以找到特定的字符模式，因此，它常常被应用于 数据有效性检测、文本替换、子串提取等一些工作之中【1 9 3 8 】。 比如说，要在程序中检查一个f o r 语句，其一般形式为； f o r ( e x p l ；e x p 2 ；e x p 3 ) 由于f o r 语句的三个表达式都是可选的，因此导致了其形式的多样性。用一 般的方法进行检测会比较麻烦，并且很难达到理想的目的。但用正则表达式却能 很好的解决这一问题： f o r ( ( 【 ；】) ? ；( 【“；】。) ? ；( ) 】) ) 踟 其中，用问号标记的分组为可选的，能够恰好表达准确的意思。 2 2 1 正则表达式的基本符号 正则表达式是对某种字符模式规则的描述，是由普通字符和元字符组成的文 本模式。其中普通字符是指英文字母以及数字等，而元字符是指正则表达式中的 一些特殊字符，有着特殊的意义。下面介绍一下主要的一些语法符号。 1 ) 句点符号“，”。旬点符号“”可代表任意字符，包括字符、数字、空格、 硕士学位论文第二章程序的r e 描述 t a b 甚至换行符。如正则表达式“f n ”可匹配的字符串“f a n ”、“f e n ”、“f i n ”、“f # n ”、 “f n ”等。 2 ) 方括号“口”。方括号只允许匹配单个的由其括起的范围内的字符。如表 达式“f a b e ”匹配“a ”、”或“c ”，而不能匹配“a b e ”；又如表达式“t l a e i o u n ” 匹配“f a n ”、“f e n ”、“f m ”、“f o n ”、“f u n ”，而不匹配“f a e n ”、“l o o n ”等。又连 字符“”常与方括号一起使用，连字符号表示范围，如“【a - z a z 】”表示所有的 大小写字母中的任意一个字符。正则表达式“t l a - c n ”匹配“f a n ”、“f b n ”、“f c n ”。 需要注意的是用到连字符时需要加上转义字符“、”。 3 ) “或”符号“l ”。顾名思义，或符号表示选择。如正则表达式“g ( o l o o ) d ” 可匹配“g o d ”或者“g o o d ”。这里只能使用圆括号，而不能使用中括号，因为中 括号只能选择单个字符，且中括号中的字符本身就有多个选一之义。 “否”符号“ ，。否符号表示不想匹配韵字符。比如“ a b e l ”表示除了 a 、b 、c 以外的任何字符，又如正则表达式“ a 】【朗”表示不以a 开头而以g 结 尾的任意字符串，雨f ；】表示不含分号的任意字符集合。 5 1 边界匹配字符。主要有行开头符“一”，行结束符“$ ”，单词边界“、b ”， 输入的开头“、a ”，上一个匹配的结尾“姬”，以及输入的结尾“、z ”等。 6 ) 预定义字符。包括“x s ”，“、s ”，“w ”，“w ”，“d ”，“x d ”。“s ”表示 任意空白字符，包括空格，回车，t a b ，跳格和换页等，即“n 岫叔0 b 、删”：“、s ” 代表非空白字符，u o i x s ；“蛔”表示单词字符，包括字母，下划线和数字，即 a - z a - z _ 0 - 9 】；“、w ”表示非单词字符，即“【 w 】”：“x d ”表示数字字符，即“ o 一9 】”： “d ”表示非数字字符，即“【a 0 9 】”。 2 2 2 正则表达式的量词符号 量词符号用来标识紧靠于该量词左边的符号出现的次数，也描述了一个模式 吸收输入文本的方式 2 2 1 ： 贪婪地。量词总是贪婪的，除非设置了其他的选项。贪婪表达式会为所有可 能的模式发现尽可能多的匹配。导致此问题的一个典型理由就是假定模式仅能匹 配第一个可能的字符组，但如果它是贪婪的，那么它还会继续往下匹配。如正则 表达式“乱”会匹配最长的以a 开始以b 结束的字符串，如果用它来搜索 。a a b a b a b ”的话，它会匹配整个串。 勉强的。用问号来指定，这个量词匹配满足模式所需要的最少字符数。因此 也称作懒惰的，最少匹配的或非贪婪的。有时候，我们可能更需要懒惰匹配，也 就是只想匹配尽可能少的字符。对于贪婪的量词只需在后面加上“? ”就成了懒 惰匹配量词。如? 意味着匹配任意数量的重复，但是在能使整个匹配成功的前 1 2 碗士学位论文 第二章程序的r e 描述 提下使用最少的重复，因此正则表达式“乱? b ”匹配最短的以a 开始以b 结束的 字符串，如果应用于串“a a b a b a b ”的话，它将匹配。a a b ”、以及后续的两个。a b ”。 占有的。当正则表达式被应用于字符串时，它会产生相当多的状态，以便在 匹配失败时进行回沥。而“占有的”量词并不保存这些中间状态。因此它们可以 防止回溯。它们常用于防止正则表达式失控，因此可以使正则表达式执行起来更 有效。此量词当前只在j a v a 语言中才可用，并且它也更高级，目前尚不需用到 它。 如表2 _ i 所示：其中n ，m 都为正整数。 表2 - 1正则表达式的量词符号 贪婪的勉强的占有的匹配 x ?x ? ?x ” x ，0 或一个 x x + 7 x +x 。0 或多个 x 十x + x 付 x ，一个或多个 x n )x ( n ) ?x n +x ，恰好n 次 x t n , x ( n ， ?x n ， + x ，至少n 次 x i n ，m )x n ，m ?x n ，m l + x ，至少1 1 次不多于1 1 1 次 需要说明的是，虽然表2 - 1 中贪婪的表达式和勉强的表达式似乎具有同样的 意义，但其匹配结果却往往并不相同，因为贪婪的会尽量匹配多的次数，而勉强 的却只会尽少的匹配。 2 2 3 反向引用与零宽断言 正刚表达式中的圆括号对称为组，每个组都有一个编号，称为组号，可以根 据组号对组进行调用。第0 组表示整个正则表达式，第一组是第个用圆括号括 起来的组，依此类推。例如在表达式： a ( c ) ) d 中，有3 个组：第0 组为a b c d ，第一组为b c ，第二组为c 。 通过分组，可以对匹配的文本进行捕获，捕获的子表达式可以在表达式或其 他的地方作避一步的处理。比如说，对一个常见的w h l e 语句进行检查： w h i l e ( i 10 0 ) i 斗+ ： 其正则表达式为：溅l e 心w + ) d + 岭b 0 1 ) + 、+ ；其中。( 、w r + ) ”这一分组的编 号为1 ，在进行匹配时，它会捕获到一个子串，在正则表达式的后部则可用“、l ” 来引用这个分组的捕获串，这称之为反肉引用( b a c k - r e f e r e n c e ) 。如上例。“o w + ) ” 此分组会捕获到子串“i ”，而后面的“1 ”则全部代表字符串“i ”。 可以对分组命名，命名后的分组须用名字来引用。如“( _ w + ) ”可以这样取 1 3 硕士学位论文 第二章程序的r e 描述 名：“( ? 、w + ) ”，则此分组内容就要用“ ”来引用。 位置指定包括正向位置指定和负向位置指定两种，所用的方法称为零宽度断 言，也叫做向前探测和向后探测。形如( ? - ) ( ) 的叫做零宽先行断言，而表达式( ? ! ) ( ) 为零宽负向先行断言；相对的用( ? = x ) 表示零宽后行断言，而用( ? 蛔+ ) ( d + ) ；) 4 ， 最后个赋值语句可以这样构造： 正则表达式2 ： | 缈卢们f 一“( 1 0 0 0 1 1 0 0 1 1 0 ) ) ? ) 1 ( ( 1 0 0 0 1 1 0 0 1 1 0 ) * | 浙叨| 手埘妒印( 1 0 0 0 1 0 0 1 1 口汐纠 ( ( 1 0 0 0 1 1 0 0 1 1o ) 、w + ”+ ( ( 、w + ”( 1 0 0 0 1 1 0 0 l l o ) ) ? ) t ( ( 1 0 0 0 1 1 0 0 l l o ) + 、碣r + ) ) + ( ( w + ( 1 0 0 0 1 1 0 0 1 1 0 ) ) ? ) i ( ( 1 0 0 0 1 1 0 0 1 1 0 ) * 、w + ) ) ； 在这里我们假设考生的程序已经通过了预处理程序，消除了多余的字符，例 如不必要的空格字符等。对正则表达式1 和2 ，我们做如下实验，假设考生程序 如下； v o i dm a i n o i n tn , a , b ，e , d ，n e w i n t ； s e a n f ( o , d , & n ) ； a = n l o ； b = n 1 0 1 0 ： c = n 1 0 0 1 0 ； d = n 1 0 0 0 ； l a b e l ：n e w i n t = d + 1 0 0 0 + a + b 1 0 0 + e 1 0 ； p r i n t f ( d ”, n e w i n t ) ； 1 7 硕士学位论文 第二章程序的r e 描述 把正则表达式l 和正则表达式2 结合起来用以查找代码块a ，在语句l a b e l 中，故意打乱了顺序，以验证r e 模式的可行性。用j a v a 实现代码如下： i m p o r t j a v a u t i l r e g e x * ； p u b l i cc l a s sr e g e x t e s t p u b l i cs t a t i cv o i dm a i n ( s t r i n g a r g s ) p a t t e r n p = p a t t e r n c o m p i l e ( ”( ( w + ) = ( 、 一( 、d + ) + ；) 4 ) 、m ，+ 一”+ ”( 心州”0 0 0 0 1 1 0 0 l