正则表达式素材.pptx

《正则表达式素材.pptx》由会员分享，可在线阅读，更多相关《正则表达式素材.pptx（52页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1第四章正则表达式1.1 正则表达式的定义p1.2 正则表达式和有穷自动机的关系p1.3 正则表达式的等价变换p1.4 正则表达式的应用第1页/共52页21.1 正则表达式定义正则表达式（Regular Expression:Regex）的由来人类神经系统如何工作的早期研究:Warren McCulloch 和 Walter Pitts 两位神经生理学家研究出一种数学方式来描述这些神经网络;1956 年,一位Stephen Kleene 的数学家在 McCulloch 和 Pitts 早期工作的基础上，发表了标题为“神经网事件的表示法”的论文，引入了正则表达式的概念;Ken Thompson

2、是 Unix 的主要发明人;正则表达式的第一个实用应用程序就是 Unix 中的 qed 编辑器;Jeffrey Friedl 在其著作Mastering Regular Expressions（中文版译作：精通正则表达式，第三版）第2页/共52页3正则表达式示例例4.1 在字母表0，1上，0*1+1*0表示：出现若干个0后以一个1结尾，或者出现若干个1后以一个0结尾的一切字符串的集合。用集合的表示形式就是0*11*0；例4.2 在字母表a，b上，(a+b)*aaa(a+b)*表示：字符串中至少要连续出现三个a。用集合的表示形式就是a,b*aaaa,b*正则表达式和它所代表的集合形式上有很大的相

3、似性。大致上，正则表达式的“+”相当于集合中的并运算符“”，正则表达式的“*”与集合中的闭包运算符一致，正则表达式的“连接”相当于集合的连接运算。第3页/共52页4正则表达式的递归定义定义 4.1 设是一个字母表，上的正则表达式以及由它们代表的集合，递归定义如下：(1)是一个正则表达式，代表空集。(2)是一个正则表达式，代表集合。(3)对于中每个符号a,a是正则表达式，代表集合a。(4)如果r和s是正则表达式，分别代表集合R和S，则 (r+s),(rs)和(r*)是正则表达式，分别代表集合RS,RS和R*。正则表达式R代表的字符串集合记为L(R)。第4页/共52页5正则表达式示例例4.3 给出

4、=a，b,则对上的一些正则表达式与它们各自所代表的集合列表示于图4.1中：正则表达式r代表的集合L(r)ab(a+b)(ab)（a*）(a+b)*)(a(b*)(a*)b)(a*)aba,baba*a,b*ab*a*ba*第5页/共52页6正则表达式表示的约定为了尽量减少括号，做如下的约定：（1）每个正则表达式最外层的一对括号可以省略。（2）规定正则表达式构造的优先次序为：*最高级 连接（如 rs）次高级 +最低级凡是符合此种顺序的，括号可以省略。（3）同一种构造（如同为+，连接或*）连续出现时，规定从左到右依次构造，中间的括号可以省略。例如（0（1*）+0）就可写成01*+0，(a*)(b)

5、(a*)就可写成a*ba*。但是，(a+b)*不可写成a+b*，因为前者表示先构造(a+b)，后构造(a+b)*，结果代表集合a,b*；而后者根据优先次序的约定，表示先构造b*,再构造a+b*，结果代表集合a,b*；这两个集合显然是不相等的。第6页/共52页7正则表达式的示例例4.5 构造一个正则表达式，使它能代表如下的集合S：S的每个元素都是倒数第十个字符是1的0、1串。即使构造一个NFA接受这个S，也要设11个状态和20个函数，若是用DFA那就更复杂了。要用一个正则表达式来代表S，就简单多了：(0+1)*1(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0

6、+1)第7页/共52页8正则表达式-字符串集合01*(01*)(01)0 后面跟上任意多个1=0(1*)=0,01,011,0111,=001,0101,01101,011101,0后面跟上任意多个1，然后以01结尾S=0,1第8页/共52页9正则表达式-字符串集合(0+1)*=,0,1,00,01,10,11,任意的字符串0+1=0,1(0+1)*01(0+1)*长度为1的字符串集合包含 01 的所有字符串集合(0+1)*010以 010 结尾的字符串第9页/共52页10正则表达式-字符串集合(0+1)(0+1)(0+1)(0+1)(0+1)串长为2串长为3(0+1)(0+1)*+(0+1)

7、(0+1)(0+1)*(0+1)(0+1)*串长为偶数(0+1)(0+1)(0+1)*串长为3的倍数所有字符串长度是偶数或3的倍数=串长为 0,2,3,4,6,8,9,10,12,.第10页/共52页11(0+1)(0+1)+(0+1)(0+1)(0+1)*(0+1)(0+1)(0+1)(0+1)(0+1)长度为2的串长度为 3的串(0+1)(0+1)+(0+1)(0+1)(0+1)长度为2或3的串字符串可以划分为长度为2或3的子串正则表达式-字符串集合第11页/共52页12(0+1)(0+1)+(0+1)(0+1)(0+1)*字符串可以划分为长度为2或3的子串0011010011101101

8、0110包括了所有的字符串，除了长度为1的串(0+1)(0+1)+(0+1)(0+1)(0+1)*=除了0，1之外的所有的字符串正则表达式-字符串集合第12页/共52页13(1+01+001)*(+0+00)最多两个 0在两个1之间的最多只有两个0；结论：(1+01+001)*(+0+00)=x:|x 不包含子串 000永远不能出现连续的三个00110010110001001000正则表达式-字符串集合第13页/共52页14字符串集合-正则表达式构造一个包含连续两个0的字符串集合的正则表达式.S=0,1(0+1)*00(0+1)*(任意符号串)00(任意符号串)第14页/共52页15构造一个不

9、包含两个连续0的字符串集合的正则表达式：S=0,1.每个0后面跟上至少一个1.在末尾最多只能有一个0(011*)(+0)1*(011*)*(+0)1110110101101010每个0后面跟上至少一个1结尾有可能是一个0开始的的时候可能有多个1字符串集合-正则表达式第15页/共52页16构造一个字符串中包含偶数个0的集合的正则表达式：S=0,1偶数个0=(包含两个0的子串)*包含两个0的串=1*01*01*(1*01*01*)*字符串集合-正则表达式第16页/共52页171.2 正则表达式和有穷自动机的关系定理4.1 设r是一个正则表达式，则存在一个具有-转移的有穷自动机接受L（r）。证明：（

10、结构归纳法）归纳基础 设构成r的构造数目为0，即r是没有经过任何“+”、“连接”和“*”构造的正则表达式，因此它只能是，或 中的某个符号a，下面针对这三种情况分别讨论。（1）r=,对应的 NFA M是：不能从初始状态q0到达终结状态qf，所以这个NFA 只能接受空集。第17页/共52页18正则表达式 -有穷自动机（2）r=,对应的 NFA M是：因为q0既是初始状态，又是终结状态，同时M也没有其他转移动作，所以这个NFA 只能接受。（3）r=a(a),对应的 NFA M是：因为这个NFA只有一个转移r函数(q0,a)=qf,而qf又是终结状态，所以这个NFA 只接受a。第18页/共52页19正

11、则表达式-有穷自动机归纳步骤 设对少于i(i1)次构造构成的正则表达式命题成立，现在的正则表达式r由i次构造构成。根据r最后一次构成的形式，分三种情况讨论：情况1 r=r1+r2。这里r1 和r2都是由少于i次构造构成的正则表达式，所以根据归纳法假设，存在NFA M1=（Q1,1,1,q1,f1）,使得L(M1)=L(r1)；存在NFA M2=（Q2,2,2,q2,f2）,使得L(M2)=L(r2)。不妨假定Q1,Q2不相交，现构造新的NFA M=(Q1 Q2q0,f0,12,q0 ,f0),其中定义为：（1）(q0,)=q1,q2；（2）对于Q1-f1中的q,1中的a：(q,a)=1(q,a

12、)；（3）对于Q2-f2中的q,2中的a：(q,a)=2(q,a)；（4）(f1,)=f0,(f2,)=f0。第19页/共52页20正则表达式-有穷自动机对于新构造的这个-NFA M，用图表示如下：M从它的初始状态q0出发，不用读任何符号即可同时进入M1和M2，然后，完全模拟M1和M2的动作，直到达到它们各自的终结状态f1和f2。M在这两个状态上，也不用读任何符号即可进入它自己的终结状态f0。显然，M接受的集合恰好是M1和M2接受的集合的并集，即L(M)=L(M1)L(M2)。第20页/共52页21正则表达式-有穷自动机情况2 r=r1 r2。设M1和M2与在情况1中的表示相同，仍假定Q1,Q

13、2不相交，现构造新的NFA M=(Q1 Q2,12,q1 ,f2),其中定义为：(1)对于Q1-f1中的q,1中的a，(q,a)=1(q,a)；(2)(f1,)=q2；(3)对于Q2中的q,2中的a，(q,a)=2(q,a)。第21页/共52页22正则表达式-有穷自动机情况3 r=r1*。r1是由少于i次构造构成的正则表达式，所以根据归纳法假设，存在NFA M1=（Q1,1,1,q1,f1）,使得L(M1)=L(r1)。现在构造-NFA M =（Q1 q0,f0,1,1,q0,f0）,其中定义为：(1)(q0,)=q1,f0；(2)对于Q1-f1中的q,1中的a，(q,a)=1(q,a)；(3

14、)(f1,)=q1,f0。第22页/共52页23正则表达式-有穷自动机：q0q0a Sq0q1aRSNFARNFASq0q1第23页/共52页24正则表达式-有穷自动机：R+SNFARNFASq0q1R*NFARq0q1第24页/共52页25正则表达式-有穷自动机例4.6 根据定理4.1给出的构造方法，对正则表达式10*+0构造一个对应的NFA。第25页/共52页26Road mapregularexpressionNFA第26页/共52页27Road mapregularexpressionNFA2-stateGNFAGNFA第27页/共52页28有穷自动机-正则表达式定理4.2 如果L被一

15、个DFA接受，则L可用一个正则表达式代表。证明 设DFA:A=(q1,q2,qn,q1,F)中的状态进行1,2,3,.,n编号。编号可以是任意的，但是编号一旦定好，在定理证明过程中不能改变；其中1表示起始状态。引入记号R（k)ij,是字符串的集合，具体定义如下：R（k）ij=x|(qi,x)=qj,且中间仅经过编号正则表达式对Rkij的k取值进行归纳证明：（k取值从0开始）basis：（k=0）当ij：当i=j：induction:第29页/共52页30有穷自动机-正则表达式例4.6 给出一个由图4.2表示的DFA M，按照定理4.2中的方法，构造一个正则表达式代表L(M)。对于所有的i和j,

16、以及k=0,1,2,rkij的值列在图4.3中。其中某些正则表达式已被化简。例如，根据定理4.2中的（4-1）式，r122=r021(r011)*r012+r022=0()*0+,显然可以化简为00+。又例如，r213=r112（r122）*r123+r113=0(+00)*(1+01)+1,由于(+00)*可以化简成(00)*，(1+01)可以写成(+0)1，我们可以有r213=0(00)*(+0)1+1。更进一步，由于(00)*(+0)可以化简为0*，于是r213可以化简为00*1+1，最后化简为0*1。第30页/共52页31有穷自动机-正则表达式图4.2中DFA的rkij表k=0k=1k

17、=2rk11rk12rk13rk21rk22rk23rk31rk32rk3301010+1010+001+010+1(00)*0(00)*0*10(00)*(00)*0*1(0+1)(00)*0(0+1)(00)*+(0+1)0*1问题：每次计算需要构造问题：每次计算需要构造n3个个rkij，每次迭代时每次迭代时rkij长度增长长度增长4n第31页/共52页32有穷自动机-正则表达式状态消除法（构造GNFA,Generalized-NFA）相对每一个终结状态相对每一个终结状态q,都消除中间状都消除中间状态，只保留态，只保留q0.第32页/共52页33有穷自动机-正则表达式对于每一个 ,通过上述

18、的状态消除法，会得到以下：或者第33页/共52页34有穷自动机-正则表达式 示例转成GNFA消除状态B第34页/共52页35有穷自动机-正则表达式 示例第35页/共52页36正则表达式的等价变换+操作的交换律:R+S=S+R。因为：R+S代表集合L(R)L(S),而S+R代表集合L(S)L(R)，集合的并运算是满足交换律的;+操作的结合律:(R+S)+T=R+(S+T)；“连接”构造的结合律：(RS)T=R(ST)。“连接”构造不满足交换律：对于一般的正则表达式R和S，不能写RS=SR。反例，如：R=1,S=0,它们分别代表集合1和0，RS代表集合10，而SR代表集合01，显然这两个集合是不相

19、等的。第36页/共52页37正则表达式的化简：+R=R+=R。根据正则表达式与它们所代表的集合的对应关系，等式正确;是构造符“+”的单位元。R=R=R。是连接构造的单位元。R=R=。代表集合L(R)或L(R)，任何集合与空集的连接结果都是空集。这就说明是连接构造的零元。R(S+T)=RS+RT。这一条称为“连接”对于“+”的左分配律。(S+T)R=SR+TR。这一条称为“连接”对于“+”的右分配律。(R*)*=R*；*=；*=；扩充定义R+：代表集合：L(R)+。定律：+R+=R*，R+=RR*第37页/共52页38发现正则表达式定律的一般方法考虑一条所谓的定律：(R+S)*=(R*S*)*这

20、里R，S是任意两个正则表达式。一般方法：将每个变量都当做一个不同的符号，即可将任何带变量的一般的正则表达式都看做一个具体的正则表达式，即一个没有变量的正则表达式。例如，把表达式(R+S)*中的变量R和S分别换成符号a和b,就得出正则表达式(a+b)*。而这个正则表达式所代表的语言L(a+b)*)，显然是字符a和b组成的一切串的集合。另一方面，把表达式(R*S*)*的变量R和S也分别换成符号a和b,就得出正则表达式(a*b*)*。而这个正则表达式所代表的语言L(a*b*)*)，显然也是字符a和b组成的一切串的集合。左右相等成立。定理 4.4 设E是带有变量V1，V2，Vm 的正则表达式，通过把V

21、i的每次出现，都换成符号ai（i=1，2，,m）得到具体的表达式C。则从每个属于L(C)的串a1a2ak出发，把每个符号ai（1ik）都换成对应语言L(Vi)，就构造出L(E)。第38页/共52页391.4 正则表达式的应用UNIX中的正则表达式词法分析查找文本中的模式.第39页/共52页40UNIX中的正则表达式对正则表达式记号的第一项扩展是：大多数实际应用都处理ASC字符集，这是比较大的字母表。如果有一种需要在表达式中把所有字符都列出来，书写起来就非常不方便。因此，UNIX中的正则表达式允许书写字符类来尽可能紧凑地表示大的字符集。字符类的规则是：符号“.”(圆点)表示任意字符。(真正的小数

22、点要用其它办法区分)序列a1a2ak表示正则表达式a1+a2+ak。利用这个记号大约节省一半字符，因为不需要写出+号。例如，C语言中的比较运算所用的4种运算符可表示成 =！。第40页/共52页41UNIX中的正则表达式 在方括号之内规定形如x-y的范围，表示ASC序列中从x到y的所有字符。由于数字是按顺序编号的，大写字母和小写字母也是这样，所以只用很少的输入就能表示真正关心的许多字符。例如，十个数字表示成0-9，大写字母表示成A-Z，所有字母和数字的集合表示成A-Za-z0-9。如果要在字符列表中包含负号，就放在开头或结尾，这就不会和字母范围的表示形式混淆。例如，要形成带符号的十进制整数，所用

23、的数字集合以及正号和负号等表示成-+0-9。几种最常见的字符类有特殊记号。例如：a):digit:表示十进制数字的集合,和0-9意义相同。b):alpha:表示字母字符的集合,和A-Za-z意义相同。c):alnum:表示字母和数字字符的集合,和A-Za-z0-9意义相同。第41页/共52页42UNIX中的正则表达式另外，有几个在UNIX正则表达式中使用的运算符，这些运算符不扩大所表示的语言范围，但有时更容易表达所要表达的内容。它们是：（1）用代替+来表示并。（2）运算符?表示“0个或1个”。因此在UNIX中，R？与本书中定义的正则表达式的+R是一样的。（3）运算符+表示“1个或多个”。因此在

24、UNIX中，R+与本书中的正则表达式RR*是一样的。（4）运算符n表示“n个副本”。因此在UNIX中，R5是RRRRR的缩写。第42页/共52页43词法分析例 4.9 图4.4中是lex命令的部分输入的一个例子,描述了C语言中一些单词。其中第一行处理关键字else，要执行的动作是返回一个符号常量（在这里是ELSE），交给语法分析器进一步处理。第二行包含一个描述标识符的正则表达式：定义标识符为一个字母后跟零个或多个字母或数字。要执行的动作是首先把这个标识符输入到符号表（如果这个标识符还没有在表中出现的话）；lex还在一个缓冲区记下所发现的这个单词，所以这段代码确切地知道发现了什么标识符；最后，词

25、法分析器返回符号常量ID（在本例中用ID表示标识符）。第43页/共52页44词法分析图4.4第三项是符号=，这是一个双字符运算符，图中显示的最后一行是一个单字符运算符=，这种单词都将转化为内部符号（本例中分别用GE和ASGN表示）。在实际上在图中可能出现每一个关键字，每一个运算符和每一个标点符号（如逗号和括号），以及各种常量（如数与串）的表达式。这些表达式大多是非常简单的，只是一个或多个具体的字符的序列。但是，有一部分带有一些标识符的风格，需要用正则表达式记法的所有能力来描述。整数、浮点数、字符串以及注释都是串的例子，它们都是用正则表达式描述的。把一组表达式（如图中所显示的这些）转化为有穷自动

26、机，原则上像在定理4.2.1所述的形式化方法那样，先把正则表达式化为具有转移的NFA，必要时可化为DFA。现在唯一的问题是一次可能识别出多个单词。例如串else不仅匹配关键字else，而且也匹配标识符表达式else，标准的解决办法是让词法分析器优先处理先列出的表达式。因此，如果要让像else这样的关键字成为保留的（即不能用做标识符），就简单地把这些关键字列在所有标识符表达式的前面。当然，要想不发生这种问题，最好在语言中规定不能将关键字做为标识符使用。第44页/共52页45查找文本中的模式假设要扫描非常大的Web页面并探测出个人或单位地址。可能只是想建立邮件地址表，或者也许是在尝试根据地点来对业

27、务进行分类，使得系统能够回答像“替我找一家在我目前位置需10分钟车程的饭馆”这样的模糊查询。要解决这样的问题就会把注意力集中到街道的地址上。什么样的字符串是街道的地址呢？这是要解决的中心问题。也许在测试软件时发现遗漏了某些情形，就需要修改表达式以“捕捉”所遗漏情形。首先，街道地址可能以“Street（大街）”或缩写“St.”来结尾。但是，有些人住在“Avenue（大道）”或“Road（大路）”上，这些也可能有缩写。因此，可能把类似于StreetSt.AvenueAve.RoadRd.这样的东西做为正则表达式的结尾.在上述表达式中,使用了UNIX风格的记号,用垂直竖线而不是+号做为“并”运算符。

28、还有，用前面加一个反斜杠对“.”进行转义,使其恢复圆点“.”的原来的意义。因为在UNIX表达式中，圆点“.”已规定为具有“任意字符”的特殊含义。第45页/共52页46查找文本中的模式像Street这样的称乎前面必须有街道的名称。在英美等国家，这个名称通常是一个大写字母后跟着一些小写字母，可以用UNIX表达式 A-Za-z*来描述这个模式。但是有些街道名称包含多个单词，比如美国华盛顿特区的Rhode Island Avenue（罗得岛大道）就是这样。因此，在发现遗漏了这种形式的地址之后，就可以把街道名称的描述修订为：A-Za-z*（A-Za-z*）*上述表达式以包含一个大写字母和零个或多个小写字

29、母的一组字符开头，后面跟着零个或多个同样的组，但后面这些组的前面都有一个空格。因为空格也是UNIX中的一个字符，为了避免上述表达式看起来像一条UNIX命令行中用空格分开的两个表达式，所以用引号把整个表达式都括起来，但引号不是表达式的一部分。第46页/共52页47查找文本中的模式现在，要包括门牌号做为地址的一部分。大多数门牌号都是一个数字串，但有些后面跟着一个字母，比如在“123A Main St.”中就是这样。因此，用来表示门牌号的表达式有一个可选的大写字母跟在后面：0-9+A-Z？其中UNIX“+”运算符表示“一个或多个”（数字），“？”运算符表示零个或一个（大写字母）。于是，表示街道地址的

30、整个表达式是：0-9+A-Z？A-Za-z*（A-Za-z*）*（StreetSt.AvenueAve.RoadRd.）第47页/共52页48查找文本中的模式如果让这个表达式来工作,会得到很好的效果。但逐渐会发现还是遗漏了一些情况:街道可能不叫Street（大街）,也不叫Avenue（大道）或Road（大路）,可能叫“Boulivard”，“Place”，“Way”及其缩写。街道名称可能完全是数字或是以数字开头，如42nd Street（第42大街）。地址是邮政信箱或乡村投递路线。不以任何有Street，Road意义的字样结尾。一个例子是美国硅谷的EI Camino Real，作为西班牙语的“

31、皇家大路”，说“EI Camino Real Road”是多余的，所以就需要 处理像“2000 EI Camino Real”这样的真实地址。还有一些暂时没有想到的地址形式。不管怎样，只要有一个正则表达式编译器，就能通过逐步修正地址的表示形式，来构造一个完整的地址识别器。这比不断修改用常规程序设计语言所写的代码，要容易得多。第48页/共52页49课后作业：阅读第4章；P.78,4.1(3)(4)(9)(10)(11),P.79,4.2(5)(6);4.3(2)(4);4.5(b)4.7第49页/共52页人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。第50页/共52页第51页/共52页52谢谢您的观看！第52页/共52页