（计算机软件与理论专业论文）主观题自动阅卷系统的设计与实现.pdf

摘要 摘要 在各类考试系统中，客观题阅卷技术已经非常成熟也得到了广泛的应用， 但主观题阅卷技术却一直进展缓慢，其主要原因是一些核心技术还在发展阶段， 例如：自然语言的理解、模式识别、人工智能等一些技术还处于研究的初级阶 段。主观题自动阅卷是在线考试系统实现自动阅卷的一个关键技术。由于同一 程序可以编写多种不同的代码，其各种代码可以用不同的算法来实现。所以， 标准答案也有好几种同时也变的比较复杂。 由于各高校都开设了c 语言程序设计课程，因此，本论文以c 语言作为研 究对象，用正则表达式来描述得分点，这些得分点彼此都是相互独立，互不影 响。此模型主要是模仿老师阅卷的特点，对于可以编译运行而且结果正确的考 生程序，通过功能测试模块进行测试，结合测试结果评分。对于可以编译运行 但是结果错误和不可以编译运行的考生程序，通过知识要点评分模块对程序进 行分析即把程序分成多个独立的知识要点模块，并用正则表达式描述，然后在 考生程序中去搜索这些知识要点，根据知识要点评分。 最后，本文用c # 语言设计和开发了主观题自动阅卷系统，该系统能实现c 语言程序设计题自动评分功能。该系统设计成功后，通过在小范围应用，初步 实验结果证明自动评分模块运行稳定，评分标准能够统一。 关键词：自动阅卷，c 语言，正则表达式 a b s t r a c t a b s t r a c t i nm a n yk i n d so fe x a m i n a t i o ns y s t e m ，m a r k i n gt e c h n o l o g yf o r0 b j e c t i v e q u e s t i o n si sv e r ym a t u r ea n du s e dw i d e l y b t i ts u b j e c t i v em a r k i n gt e c h n o l o g yi s d e v e l o p i n gs l o w l y t h er e a s o ni st h a ts o m ek e yt e c h n o l o g yi sn o tc o m p l e m e n t s u c ha s a i ，p a t t e mr e c o g n i t i o n , n a t u r a ll a n g u a g ei ss t i l li ni n t i a ls t a g er e s e a r c h i n g s u b j e c t i v e m a r k i n gt e c h n o l o g yi sak e yw a yt or e a l i s ee x a m i n a t i o no nl i n ea n dm a r k i n g a u t o m a t i c b e c a u s et h ec o d ei sv e r yd i f f e r e n tw h i c hi su s e dt or e a c ht h es a m e f o u n t i o n ，s t a n d a r da n s w e ri sc o m p l e xt om a k e s i n c ea l lc o l l e g e sa n du n i v e r s i t i e so p e n e dcl a n g u a g ep r o g r a m m i n g ，s o ，t h e a r t i c l ep a ya t t e n t i o nt oc l a n g u a g e ，p u tf o r w a r das c o r i n gm o d e lt od i s e r i b ep r o c e d u r e s c o r ep o i n tw h i c hu s er e g u l a re x p r e s s i o n s t h e s es c o r ep o i n t sa r ei n d e p e n d e n t t 1 1 i s m o d e li m i t a t e t h ec h r a c t e r i s t i e so fa r t i f i c i a lm a r k i n g f o rt h ec a n d i d a t ep r o g r a m w h i c hh a v ec o r r e c tr e s u l ta n di sa v a i l a b l et oc o m p i l er u n ，t h r o u g hf u n c t i o n a lt e s t m o d u l et oc h e e k ，t h e ng e tt h el a s tr e s u l t i fc o m p i l er u ni sp o s s i b l ew i t haw r o n g r e s u l to rc o m p i l er u ni si m p o s s i b l e d e v i d ep r o c e d u r ei n t os o m ei n d e p e n d e n t k n o w l e d g em o d e l s ，a n dd e s c r i b e i n t or e g u l a re x p r e s s i o n s t h e nr e s e a r c ht h e k n o w l e d g ep o i n t si nc a n d i d a t ep r o g r a m ，a n dr e s u l ti n t oas c o r e f i n a l l y , t h ec 撑l a n g u a g eh a v ed e s i g n e da n dd e v e l o p e dt h es u b j e c t i v eq u e s t i o n a u t o m a t i cg r a d i n gs y s t e mi nt h ea r t i c l e t h es y s t e mc a na c h i e v et h ecl a n g u a g e p r o g r a m m i n go fa u t o m a t i cs c o r i n gf u n c t i o n w h e nt h ed e s i g ns u c c e s s ，p r o v et h e s t a b i l i t yo f r a t i n gm o d u l ei ns m a l lr a n g e ，s ot h a tt h es c o r es t a n d a r di su n i f i e d k e yw o r d s ：m a r k i n ga u t o m a t i c c l a n g u a g er e g u l a re x p r e s s i o n s 学位论文独刨性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特另l j j n 以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得南昌文学或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位做储签名c 瑚移歹仗签字吼一年朋多7 日 学位论文版权使用授权书 本学位论文作者完全了解南昌大学有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权南昌大学可以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。同时授 权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名( 手写) ： 稗嗍叼朋钟 导师签名( 手写) ：乍乏习乃 签字日恸矿歹 学位论文作者签名( 手写) 移；西。字日期 年，y 月弓日 年，胡芗l 第1 章绪论 1 1 研究背景 第1 章绪论 1 9 4 6 年2 月1 4 日，世界上第一台电脑e n i a c 在美国宾夕法尼亚大学诞生。 谁也没有想到计算机已经在各行各业得到非常广泛的应用，特别是在教育行业 得到了广泛的应用。计算机最早是以幻灯片的角色出现在各个学校，从最早的 幻灯片、投影仪等到现在的多角度辅助老师教学，特别是经过最近几年计算机 主观题阅卷技术的发展，计算机辅助教学( c o m p u t e ra i d e di n s t r u c t i o n ，简 称c a i ) 以对话方式与学生讨论教学内容、安排教学进程、进行教学训练。c a i 为学生提供一个良好的个人化学习环境。综合应用多媒体、超文本、人工智能 和知识库等计算机技术，克服了传统教学方式上单一、片面的缺点。它的使用 能有效地缩短学习时间、提高教学质量和教学效率，实现最优化的教学目标， 在很大程度上可以减轻老师的工作负担。近年来随着互联网等技术的快速发展 和计算机的普及，在全国各高校中计算机文化基础课程普遍采用上机考试，这 样成绩快速就可以出来。无纸化考试己成为目前考试发展的一个趋势。无纸化 考试涉及到几个重要的组成部分，如题库的建立，试卷的自动组卷以及自动阅 卷等。其中试卷的自动阅卷对于大规模的考试来说意义非常重大。比如全国计 算机等级考试采用计算机自动阅卷给老师减轻了巨大的工作量。因此，实现自 动阅卷在目前来说尤为重要1 4 l 。 目前，选择题和判断题自动阅卷技术发展已经相当成熟，如选择题和判断 题等利用计算机自动阅卷其速度和准确率远远超过人工阅卷，但是主观题的计 算机自动阅卷技术却一直停滞，其效率和准确率不如人工阅卷。其主要原因是 计算机主观题自动阅卷技术尚不成熟，比如人工智能( a r t i f i c i a l i n t e l l i g e n c e ) 、模式识别( p a t t e r nr e c o g n i t i o n ) 、自然语言的理解等一些关 键技术还处于研究的初级阶段，发展潜力很大。所以，目前要完全解决主观自 动阅卷是很难实现的。考虑到程序设计语言比自然语言具有严格的约束和限制 性，所以，可以把对程序设计题的自动阅卷作为主观题阅卷的一个突破口 1 2 3 。 程序设计题是计算机语言考试中的非常常见的题型，也是最能反映考生学 第1 章绪论 习水平的考试题型，目前对编程题的阅卷仍然没有好的解决办法，以全国计算 机二级c 语言考试为例，该系统中有程序设计题，但对该类试题主要采用的是 结果评分法，即只依据程序运行结果给出相应分数，并不看考生程序内容。在 这种评分机制下，程序中一个小小的错误就将导致一个几乎正确的程序无法运 行，从而导致没有运行结果，考生将丢失全部分数。而这与人工阅卷恰恰是背 道而驰的。 很多专家意识到，要想很好地解决程序题自动阅卷，一定要对考生程序进 行相应的处理。所以，怎样分析考生的程序进而了解其答题的正确程度，将成 为攻克这一难题的重点。当前有很多专家提出了一些解决主观题阅卷的方法， 且能够解决一定的问题，但真正有实用价值的计算机自动阅卷系统还不多见。 1 。2 国内外研究现状 程序设计题的自动阅卷是在线考试的一个关键技术，在6 0 年代初期，国外 很多专家就开始研究如何对主观题进行自动阅卷。p e g 系统是e l l i sp a g e 在1 9 6 6 年开发的第一个实现自动评分功能的系统( 即p r o j e te s s a yg r a d e ) ，e l l i sp a g e r 在所开发的系统把文章的内在特征进行量化，之后把量化的结果在计算机内表 示并计算，再模仿老师评分的过程对这些量化了的内在特征进行评价，最后给 出评分结果。 潜在语义分析系统( l a t e n ts e m a n t i ca n a l y s i s ) 简称为l s a 系统，将文 本转化为空间向量矩阵，列对应文档向量，行对应文档特征。应用相关系数测 量来分析词与词、词与文档、文档与文档之间的相似程度【i2 1 。 a t m ( a u t o m a t e dt e x tm a r k e r ) 系统主要是针对主观题，如填空题、问答 题等有明确答案且答案简短类型题目的新的计算机辅助评分方法，a t m ( a u t o m a t e dt e 磕m a r k e r ) 系统可以对自然语言书写的答案的内容进行评判。 a t m 非常重要的模块是语法分析器和语义分析器。a t m 系统不管语法正确与否、 句子是否有歧义，它都可以对其进行分析。 a u t o m a r k 自动批改系统、a s s y s t 系统、k n o t s 系统、v e r i l o gl o g i s c o p e 系统等都是使用软件质量度量的方法来评价学生程序的质量。 目前，全国各高校及各类培训机构都有各种考试系统，这些考试系统大多 都具有自动组卷、上机考试及自动评阅等功能，但其中自动评阅功能的实现要 2 第l 章绪论 受到试题类型的限制。目前各高校的计算机文化基础课都实现了上机考试自动 阅卷的功能，但是对于一些主观性很强的题目，尤其是程序设计的题目，还没 有很好的解决方案。 网络考试系统目前有两类：一类是基于局域网，一类是基于w e b 的。基于 局域网的考试系统通常用于比较重要的考试，如全国计算机等级考试、行业考 试等；基于w e b 的网络考试系统通常用于考生自测或网络教学系统。下面介绍 国内流行的考试系统的研究现况： 1 清华泰豪网络考试系统 “清华泰豪网络考试系统 具有教学题库管理、自动试卷生成、自动成绩 统计分析等多项功能，系统是全面网络化的多用户系统，系统安装分布于题库 服务器、普通教师机、监考教师机、学生机等多台计算机上，适用于电子教室 环境，是校园网软件系统的的重要组成部分。该系统主要的缺点是题型比较单 一，主要以选择题和填空题为主，系统使用复杂，需要安装相应的教学系统作 为支撑。 2 全国计算机等级考试 全国计算机等级考试较早地采用了网络考试系统。这种考试系统一般采用 局域网的形式，在考试之前，由专门的考试网站提供相关的报名、考务安排等 软件，然后在开始考试时，将题库统一安装在各考点的服务器上。为了测试系 统的方便，在正式考试之前，一般给每个考生测试一次的机会。考试采用现场 打分的方式，考生只要一提交试卷，系统就给出相应的分数。为了安全起见， 一般还要求考生到服务器上确认。 目前，很多主观题评分方法主要有两种：一种是动态分析方法、另外一种 是静态评分方法。动态分析评分是指把源代码通过编译程序，然后输入相应的 测试数据，根据程序运行结果进行评分。如果程序有错误则程序不能运行，这 样一来就不能输入相应的测试数据，故没有运行结果，最终会导致无法评分。 静态评分是指利用程序理解、语义分析等方法来评价源代码，然后再与标准答 案进行匹配，最后根据匹配结果进行评分。 目前，国内现在有很多自动评分系统都是以客观题为主，且大多是以选择 题和判断题为主，即使有主观题，也是很简单的填空题。对于程序设计题，计 算机自动阅卷系统大多通过以下两种方式来实现： ( 1 ) 结果比较。首先运行程序，然后系统利用考生程序代码和测试数据得 3 第1 章绪论 到程序结果，再将程序结果和标准结果进行比较，如果完全相同则给满分，如 果不同即为零分，即使是大部分相同，只有少数不相同同样为零分，这样对考 生是很不公平的。也与人工评分背道而驰。国家计算机等级考试系统就是才用 结果匹配这种方法。 ( 2 ) 计算机评分与老师评分相结合。选择题、判断题由系统自动评分，由 于主观题计算机考试系统无法自动阅卷，所以只能才用人工阅卷。这样一来实 际上还不能实现自动评分。 两种评分都不是很完善，对于第一种情况，如果考生由于极少数错误而导 致程序不能运行，最终只能得零分。对于第二种情况，虽然评分结果很公平， 但总体来上还是人工阅卷。严格意义上来说不能算主观题自动阅卷。实际上主 观题还是由老师评分。 1 3 课题的研究意义 考试是评价学生成绩好坏的一个关键环节，怎么利用计算机来提高考试的 质量，提高考试的效率，是检验教学成果的一个关键的方面。近年来，随着全 国高校的不断扩招，给教师增加了很大的工作师量，如果可以把教师从批改大 量作业中解放出来，使老师可以集中精力来提高教学质量和教学效率是至关重 要的，利用计算机自动考试系统可以及时把学生考试成绩及相关统计数据提供 给学校领导，以便学校作出更加合理的决定是至关重要的，其主要意义如下1 5 】： 1 利用考试系统可以大大提高考试阅卷的速度 没有考试系统之前，评卷教师需要多次翻阅试卷且效率低下，有了考试系 统计算机可完成阅卷工作，且无须流水线上的中间等待，使阅卷效率大大提高， 同时也大大节省了教学资源。 2 利用考试系统可以大大减轻教师批改作业的的负担 以前老师先要布置作业，然后再统一把作业收集上来由老师评改，由于现 在各高校老师带的学生很多，这样一来老师要花费大量的时间去批发作业，严 重增加教师负担。不利于老师的教学工作，考试系统可以大大减轻老师的工作 量。 3 考试系统可以为学校领导提供科学合理的决策 考试系统可以快速地对各学院各专业进行考试和评分，同时也使得评卷的 4 第1 章绪论 标准化和规范化得到了很大的保证。现在考试系统可以快速、准确、完整地生 成考试分析报告，同时为学校的教学管理决策提供科学合理的依据。 4 最大限度地实现考试成绩及分析数据的资源共享 考试系统导出的e x c e l 和p d f 文件格式的考试数据，不但可供其它教学系 统直接调用，而且也可直接搬上校园网，同时，教师的考试讲评及学校的质量 分析均可通过校园网直接调用系统数据，省去了人工录入和书写的麻烦。 5 节省教学投资，降低考试成本，提高资源利用率 使用考试系统不必再使用精致的答卷或答题卡，因而，它不但可节省教学 投资，降低考试成本，而且还充分发挥了现有教学资源的效用。 1 4 研究思路 本文的主要研究思想是模仿老师评分的方式。其基本方法是在创建题库的 时候提供评分标准和程序的得分点，对每个得分点用正则表达式进行描述。最 后，根据正则表达式来进行评分。 在本论文中，把一个完整的程序拆分成多个得分点，再用正则表达式来进 行描述，因此，本论文使用的是一种基于分割程序语义的处理方法。其基本方 法是：首先，考生程序的得分点用正则表达式来进行描述。其次，利用正则表 达式把一个完整的程序拆分成多个相互独立的模块，从而在考生的程序中去查 找这些模块是否存在，如果存在则根据模块的个数进行评分。这种方法比根据 结果比较、计算机评分与老师评分相结合更加灵活、准确，同时也更加合理， 与人工阅卷方式更加接近。 对于每一道程序设计题，考生所写的的答案有多种多样，正确的答案也有 若干种，这样会增加评分的难度，错误的答案同样是多种多样。但是，从总体 上来说，其结果主要还是有以下三种： 1 ) 考生程序可以运行并且考生结果也是正确的； 2 ) 考生程序没有编译错误，可以进行运行但是结果是错误的，这一般是主 义错误不是语法错误： 3 ) 由于程序有语法错误不能运行，所以没有结果。 本主观题自动阅卷系统在对考生程序进行自动评分时，首先，判断其结果 文件是否存在，如果结果文件存在则对其进行动态测试，根据动态测试的结果 5 第1 章绪论 与标准答案进行匹配，然后进行评分；如果文件不存在则直接对考生程序源代 码进行分析，主要进行语法分析和词法分析； 1 5 本章小节 本文主要讨论了计算机程序设计题评分的思想和如何实现，本论文一共分 为五章，其结构如下： 第一章：介绍了本文的研究背景、国内外发展现状、研究意义、研究思想， 提出了计算机程序设计题自动阅卷的一些关键技术，总结了目前主观题所面对 技术和理论难题，本文提出了用正则表达式描述程序得分点，最后介绍了本论 文的组织结构。 第二章：主要阐述了什么是正则表达式和正则集，并对其在c # 中的应用进 行了说明。 第三章：阐述了计算机主观题自动阅卷系统的总体设计及主要模块并介绍 了各个模块的功能，同时阐述了词法分析器和语法分析器构造的过程，并用c 语言构造了一个词法分析器和语法分析器，并介绍了对词法出错的查找并对错 误进行处理。 第四章：阐述了计算机主观题自动阅卷系统的总体测试，并对测试结果进 行分析，判断其合理性。 第五章：对本文所作的工作进行了总结，进一步阐述了计算机主观题自动 阅卷系统需要完善的地方，同时对本课题研究的发展前景进行了展望。 6 第2 章正则表达式在程序代码中的应用 第2 章正则表达式在程序代码中的应用 很多人都知道，老师在评改学生试卷时，对每道程序设计题进行打分时， 通常都是根据每道题目的评分标准进行的。这个评分标准详细地指出什么地方 是得分点且同时指出哪些地方应该要进行扣分。同样，计算机主观题自动阅卷 评分系统也有一个相应的评分标准。不过这个评分标准需要在设计题库时就应 该同时给出。这种评分标准应该用正则表达式对得分点进行描述，否则计算机 自动阅卷系统就不能自动评分。在本论文中提出了用正则表达式来描述评分标 准中的得分点。在计算机自动阅卷系统中利用正则表达试与考生程序进行直接 匹配，然后评分，所以非常方便。 2 1 正则表达式和正则集 正则表达式也叫做匹配模式( p a t t e r n ) ，它由一组具有特定含义的字符串组 成，通常用于匹配和替换文本。通常情况下，如果一个文本中出现了多个匹配， 正则表达式返回第一个匹配，如果将g l o b a l 设置为t r u e ，则会返回全部匹配； 匹配模式是对大小写敏感的，如果设置了i g n o r ec a s e 为t r u e ，则将忽略大小写 区别【”j 。 对于字母表，其上的正则式及其表示的正则集可以递归定义如下： ( 1 ) 是一个正则式，它表示集合l ( a ) = ； ( 2 ) 若a 是上的字符，则a 是一个正则式，它所表示的正则集为 a ； ( 3 ) 若正则式r 和s 分别表示正则集l ( r ) 和l ( s ) ，则 ris 是正则式，表示集合l ( r ) u l ( s ) ； 0r s 是正则式，表示集合l ( r ) l ( s ) ； 0r ：i c 是正则式，表示集合( l ( r ) ) 术； ( r ) 是正则式，表示集合l ( r ) 。 仅由有限次地使用上述3 个步骤定义的表达式才是上的正则式，其中运 算符“l 、“修、“木、分别称为“或 、“连接、“闭包 。在正则式的书 写中，连接运算符“可省略。运算符的优先级从高到低顺序排列依次为：“木 、 7 第2 章正则表达式在程序代码中的应用 “i 一 、o 设e = a ，b ，表2 1 列出了上的一些正式和相应的正则集。 表2 1 正式与正则集 正则式正则集 a b 符号串a b 构成的集合 a lb符号串a 、b 构成的集合 a 牢由零个或多个a 构成的符号串集合 ( a i b ) 木 所有由字符a 和b 构成的串的集合，包括空串符e a ( a i b ) 木以a 为首字符的a 、b 字符串的集合 ( a i b ) * a b b以a b b 结尾的a 、b 字符串的集合 若两个正则式表示的正则集相同，则认为二者等价。两个等价的正则式u 和v 记u = v 。例如，b ( a b ) 水= ( b a ) 木b ，( a f b ) 杠( a 袖木) ：i c 。设u 、v 和w 均为正则 式，正则式的代数性质如表2 2 所示： 表2 2 正则式的代数性质 公理公理 u i v = v i u( u v ) w = u ( v w ) ( u f v ) w = u ( v i w ) u = u = u u ( v l w ) = u v l u wv 木= ( v + i ) ( uv ) w = u w iv w v 木木= v 木 2 1 1 正则式与有限自动机之间的转换 有限自动机是一种识别装置的抽象概念，它能准确地识别正则集。基本的 有限自动机分为两类：确定的有限自动机和不确定的有限自动机【5 l 】。 1 ) 确定的有限自动机( d e t e t m i n i s t i cf i n i t ea u t o m a t a ，d f a ) 一个确定的有限自动机是个五元组：( s ，e ，f ，s o ，z ) ，其中： ( 1 ) s 是一个有限集，其每个元素称为一个状态： ( 2 ) 是一个有限字母表，其每个元素称为一个输入字符； ( 3 ) f 是从s 一s 上的单值部分映像。f ( a ，a ) = q 表示当前状态为a ，输 8 第2 章正则表达式在稃序代码中的应用 入为a 时，将转换到的下一状态q 。我们称q 为a 的一个后继状态； ( 4 ) s 0 s ，是惟一的个开始状态； ( 5 ) z 是非空的终止状态集合，z s 。 一个d n f 可以用两种直观的方式表示：状态转换图和状态转换矩阵。状态 图简称为转换图，它是一个有向图。d f a 中的每个状态对应转换图中一个节点， d f a 中的每转换函数对应图中条有向弧，若转换函数为f ( a ，a ) = q ，则该有向 弧从节点a 出发，进入节点q ，字符a 是弧上的标记。 2 ) 不确定的有限自动机( n o n d e t e r m i n i s t i cf i n i t ea u t o m a t a ，n f a ) 一个不确定的有限自动机也是一个五元组，它与确定有限自动机的区别是： 首先，f 是从s xe 一2 5 上的映像。对于s 中的一个给定状态及输入符号， 返回一个状态的集合。即当前状态后继状态不一定是惟一的，其次，有向弧状 态的后继状态不定是惟一的。 1 对于上的n f am ，可以构造一个上的正则式r ，使的l ( r ) = l ( m ) 。 我们把状态转换图的概念拓广，令每条弧用一个正则式标记。为上的n f a m 构造相应的正则式r 可分为两步： 在m 的状态转换图中加两个节点：一个x 节点：一个y 节点。从x 节点 到n f am 初始状态节点引一条弧并用标记。形成一个与m 等价的m ，m 只 有一个初态x 和一个终态y 。 按下面的方法逐步消去m 中除x 和y 的所有节点。在消除节点的过程 中，用正则式来标记弧，最后节点x 和y 之间的弧上的标记就是所求的正则式。 削除节点的规则如图2 3 所示。 9 第2 章正则表达式在程序代码中的应用 一 一v 2 图2 3 有限自动机到正则式的转换规则示意图 2 同样地，对于上的每个正则式r ，可以构造一个上的n f am ，使得 l ( m ) = l ( r ) 对于正则式r ，可用图所示的拓广状态图表示。 0 通过对正则式r 进行分裂并加入新的节点，逐步把图转变成每条弧上的 标记是上的一个字符或，最后的得的图即为一个n f am ，x 为初态节点，y 为终态结点。显然，l ( m ) = l ( r ) 。 2 2 正则表达式引入的可行性分析 一个程序是由若干条语句组成，而一条语句又由多个标识符构成，所以， 可以这样说：一个程序是由标识符按照相应的规则组成的符号集合。 由于通过一个自动机可以识别一个标识符，那么给定一个标识符可以构造 出一个自动机。好比给定一个主语+ 谓语+ 间接宾语+ 直接宾语的语法结构，可以 造一个句子如：h eg a v em eab o o k ；相反给定一个句子我们也可以找出它的语 法结构，得到其主+ 谓+ 间宾+ 直宾结构。一个程序确定了，其标识符号也就确定 了。根据编译原理的相关知识可以知道，程序语言的标识符可以通过自动机来 进行描述，当给定一个程序的时候，可以通过归约来得出每个标识符的自动机。 因此一个程序可以用标识符的自动机来进行描述。 例如，一个输出结果h e l l o 的c 程序如下： l o 第2 章正则表达式在稃序代码中的应用 # i n c l u d e “s t d i o h ” m a i n o p r i n t f ( “h e l l o ”1 ； 通过规约，可知i n c l u d e 为关键字( 标识符) ，m a i n 、p r i n t f , s t d i o h 为标识符， “( 、“) 一、“ 一、“ 一为分界符，此程序可规约为： 。 由编译原理可知，这些标识符都可由自动机进行描述。 这样描述一个代码段，虽然它不会把正确的代码判错，但它充当的仅仅是 一个模型，符合这个模型的程序代码都可以匹配，但歧义性比较大。如果把标 识符和界符的一部分通过精确描述之后，那么情况就会有很大的改进。 2 3 正则表达式描述程序的方法 正则表达式的“祖先 可以一直上溯至对人类神经系统如何工作的早期研 究。w a r r e nm c c u l l o c h 和w a l t e rp i t t s 这两位神经生理学家研究出一种数学方式 来描述这些神经网络。1 9 5 6 年，一位叫s t e p h e nk l e e n e 的数学家在 m c c u l l o c h 和p i t t s 早期工作的基础上，发表了一篇标题为“神经网事件的表示 法 的论文，首次引入了正则表达式这个概念【1 2 】。 随后正则表达式应用到信息技术，u n i x 的主要发明人是k e nt h o m p s o n 。正 则表达试第一个应用程序是u n i x 中的q c d 编辑器，目前很多高级语言也都支持 正则表达式，如c 拌，j a v a 、p e r l 等，m i c r o s o f t 的n e t f r a m e w o r k 类库提供了 s y s t e m t e s t r e g u l a r e x p r e s s i o n s 命名空间作为正则表达式的编程接口。而p e r l 脚 本语言对正则达试的应用更为常见。 正则表达式是一种威力无比强大的武器，几乎在所有的程序设计语言里和 计算机平台上都可以用它来完成各种复杂的文本处理工作，所以，正则表达常 常对数据进行检测、子串提取、文本替换等。 例如：要在程序中检查一个f o r 语句，其形式为： f o r ( 表达式l ；表达式2 ；表达式3 ) 对于f o r 语句的表达式l 、表达式2 、表达式3 都是可选的，导致了其形式 第2 章正则表达式在稃序代码中的应用 的多样性。用变通的方法进行检测非常麻烦且难达到理想的目的。若用j 下则表 达式可以很好地解决这个问题： f o r ( ( 【 ：】幸) ? ；( 【 ：】+ ) ? ：( 【 ) 】) ) ? ) 其中，用问号标记的分组表示为可选的，能够准确地表这语句的意思。 2 3 1 正则表达式的基本符号 正规表达式由一个或多个字符型文字或元字符组成。在最简单的格式下， 正规表达式仅由字符文字组成，如正规表达式b e e r 。它被读作字母b ，接着是 字母e 、e 和r ，这种模式匹配b e e r 、b e e r a 和b e e r c a t 之类的字符串。下 面主要介绍语法符号 1 ) 句点符号。 ，“”表示可以代表任何字符，如正则表达式“a c d ”， 它可匹配“a b c d 、“a f c d 、“a f c d 、“ac d 等，当然还包括空格、换行、 t a b 2 ) 方括号符号 ”，表示只匹配方括号内的一个字符，方括号外的不 可以匹配，如j 下则表达式“ e f g 一只可以匹配“e 、“f 、“g ，不可以 匹配“e f ”、 “e f g 、“f g ，正则表达式“a b c d e f g 只可以匹配“a b g 、 “a c g 、“a d g 、“a e g ”、“a f g ，不可以匹配“a b c g 因为在方括号 内可以匹配一个字符。 3 ) “或 符号，表示选择，正则表达式a ( a a 8 a a a i a a a a ) b 只可以匹配 “a a b 、“a a a b 、“a a a a b ”、“a a a a a b ， 但是要注意的是这里只能使用 “( ) ，不可以使用“ ，因为“ 只可以匹配单个字符。 4 ) 表示匹配次数的符号表2 - - 3 显示了表示匹配次数的符号，这些符号用 来确定紧靠该符号左边的符号出现的次数，如表2 - 3 所示 表2 3 正规表达试符号 符号次数 ，| 0 次或者多次 + 1 次或者多次 0 次或者1 次 1 3 恰好1 3 次 1 2 第2 章正则表达式在程序代码中的应用 l r l ，m ) l从f 1 次到m 次l 5 ) “否 符号。符号旷 表示不能匹配的字符，正则表达式“ e f g 表示除了e 、f 、g 以外的字符，正则表达式“ e f 表示不以e 开头以f 结 尾的任意字符。 6 ) 常见正则表达式创建的快捷符号，如表2 4 所示： 表2 4 常用符号 符号等价的正则表达式 、d 【0 - 9 】 、d 【 o - 9 】 f i 矽 【a - z 0 - 9 】 | 【 a z 0 - 9 】 、s p 胁沪田 s 【 t x n k r w l 2 3 2 正则表达式的量词符号 量词可以制定某个特定模式出现的次数。当指定某个模式应当出现的次数 时，可以指定硬性数量( 如某个字符应该出现三次) ，也可以指定软性数量( 如 莫个字符至少出现一次，但可以出现任意多次) ： ? ：表示出现零次或一次； 木：表示出现零次或多次( 任意次) ；如正则表达式：b a * d 匹配 b d “。“b a d “b a a d “。“b a a a d “等 + ：表示出现一次或多次( 至少出现一次) ； 1 1 ：一定出现n 次： n ，m ) ：至少出现n 次但不超过m ； n ， ：至少出现f i 次； 贪婪量词：贪婪量词先看整个的字符串是否匹配。如果没有发现匹配，它 就去掉该字符串中的最后一个字符，并再次尝试。如果还是没有发现匹配，那 第2 章正则表达式在程序代码中的应用 么再次去掉最后一个字符，这个过程会一直重复直到发现一个匹配或者字符串 不剩任何字符。例如正则表达式“c ；i c f 匹配以c 开始以f 结束的最长字符串， 如果搜索“a c a b a b f a b 的话，它会匹配“c a b a b f 。 勉强量词：先看字符串中的第一个字母是否匹配。如果单独这一个字符还 不够，就读入下一个字符，组成两个字符的字符串。如果还是没有发现匹配， 勉强量词继续从字符串中添加字符直到发现匹配或者整个字符串都检查过也没 有匹配。它与贪婪量词的工作方式恰好相反 占有量词。只尝试整个字符串。如果这个字符串不能产生匹配，不做进一 步尝试。如表1 1 所示：其中n ，m 都为正整数。 表2 4 正则表达式的量词符号 贪婪勉强占有匹配 x ?x ? ?x ? +x ，0 或一个 x x ?x 木+x ，0 或一个 x +x + ?x + + x ，一个或多个 x n x n ) ?x n ) +x ，恰好n 次 x n ，x n ，m ?x n ，) +x ，至少n 次 x n ，m )x n , mx n ，m ) +x ，至少n 次不多于m 次 说明：表2 4 中勉强的表达式和贪婪的表达式好像具有相同的意思，但贪 婪题词会尽量匹配多的次数，而勉强题词会尽少的匹配。 2 4 常用的匹配正则表达式和程序实例 匹配中文字符的正则表达式： 【u 4 e o o a u 9 f a 5 】 匹配双字节字符( 包括汉字在内) ：【 b 0 0 0 ) c 司 应用：计算字符串的长度( 一个双字节字符长度计2 ，a s c i i 字符计1 ) s t r i n g p r o t o t y p e 1 e n = f u n c t i o n o r e t u r nt h i s r e p l a c e ( l x 0 0 一) 【司儋，”勰) 1 e n g t h ； 匹配空行的正则表达式：i l i1 r 匹配h t m l 标记的正则表达式： i 匹配首尾空格的正则表达式：( 宰) i ( s 幸$ ) 应用：j a v a s c r i p t 中没有像v b s c r i p t 那样的t r i m 函数，我们就可以利用 1 4 第2 章正则表达式在程序代码中的应用 这个表达式来实现，如下： s t r i n g p r o t o t y p e t r i m = f u n c t i o n 0 r e t u r nt h i s r e p l a c e ( ( k s 宰) 1 6 s 木$ ) 儋，”) ； ) 利用正则表达式分解和转换i p 地址： 下面是利用正则表达式匹配i p 地址，并将i p 地址转换成对应数值的 j a v a s c r i p t 程序： f u n c t i o ni p 2 v ( i p ) r e = 6 d + ) n + ) 、( d + ) 、( d + ) 儋匹配i p 地址的正则表达式 i f ( r e t e s t ( i p ) ) r e t u r n r e g e x p $ l 木m a t h p o w ( 2 5 5 ，3 ) ) + r e g e x p $ 2 幸m a t h p o w ( 2 5 5 ，2 ) ) + r e g e x p $ 3 木2 5 5 + r e g e x p $ 4 幸1 ) e l s e t h r o wn e we r r o r ( n o tav a l i di pa d d r e s s ! ”) ) 匹配e m a i l 地址的正则表达式：w + ( 【- + 】w + ) 幸 w + ( 【- 】w + ) 枣w + ( 【- 】w + ) 匹配网址u r l 的正则表达式：h t t p ：( b w 一】“卜【w - 】+ ( 【、种7 & = 】) ? 利用正则表达式去除字串中重复的字符的算法程序： v a rs = ”a b a c a b e f g e e i i ” v a ts l = s r e p l a c e ( ( ) 事l 儋，”$ ln ) v a l r e = n e wr e g e x p ( ”【”+ s l + 】t t ，g t - ) v a ts 2 = s r e p l a c e ( r e , ) a l e r t ( s 1 + s 2 ) 结果为：a b c e f g i 得用正则表达式从u r l 地址中提取文件名的j a v a s c r i p t 程序，如下结果为： 第2 章正则表达式在程序代码中的应用 _ _ _ - _ _ _ _ _ 一 p a g e l s = ”h t t p ：w w w 9 4 9 9 n e t p a g e1 h t m ” s - s r e p l a c e ( ( * v ) 0 ，) ( 【 】+ ) + i g ，f t $ 2 ”) a l e r t ( s ) 利用正则表达式限制网页表单里的文本框输入内容：用正则表达式限制只 能输入中文： o n k e y u p = ”v a l u e = v a l u e r e p l a c e ( u 4 e 0 0 - u 9 f a 5 g , ) ” o n b e f o r e p a s t e = ”e l i p b o a r d d a t a s e t d a t a ( t e x t ，c l i p b o a r d d a t a g e t d a t a ( t e x t ) r e p l a c e ( u 4 e 0 0 - u 9 f a 5 】儋，”) ) ” 用正则表达式限制只能输入全角字符： o n k e y u p = ”v a l u e = v a l u e r e p l a c e ( u f f 0 0 - u f f f f g , ) ” o n b e f o r e p a s t e = ”c l i p b o a r d d a t a s e t d a t a ( t e x t ，, c l i p b o a r d d a t a g e t d a t a ( t e x t ) r e p l a c e ( u f f 0 0 u f f f f 】儋，”) ) ” 用正则表达式限制只能输入数字：o n k e y u p = ”v a l u e = v a l u e r e p l a c e ( d 】儋，”) o n