《正则表达式》PPT课件.ppt-淘文阁

资源描述

《《正则表达式》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《正则表达式》PPT课件.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、3.3 正则表达式广东商学院信息学院广东商学院信息学院胡建军胡建军正则表达式正则表达式l描述程序设计语言中单词的一种简单而描述程序设计语言中单词的一种简单而且数学化的工具。且数学化的工具。l表示符号串的构成模式表示符号串的构成模式l正则表达式正则表达式r r定义了一个符号串集合定义了一个符号串集合r rs s,r rs s内的每个符号串都与内的每个符号串都与r r所定义的模式相所定义的模式相匹配，匹配，r rs s称为由称为由r r生成的语言生成的语言L(r)L(r)l正则表达式中出现的所有符号构成的集正则表达式中出现的所有符号构成的集合为该正则表达式的合为该正则表达式的字母表字母表，用用表

2、示表示正则表达式正则表达式主要内容：主要内容：l基本概念基本概念l正则表达式定义及一些性质正则表达式定义及一些性质l扩扩充充的的正正则则表表达达式式及及程程序序设设计计语语言言中中单词的定义单词的定义l正则表达式的局限性。正则表达式的局限性。l正则定义正则定义正则表达式正则表达式(正规式正规式)l基本概念：基本概念：l字母表：字母表：非空有限集，非空有限集，其元素称为符号或字母，其元素称为符号或字母.l符号串：符号串：符号的有限序列，也称为符号的有限序列，也称为字字。或或表示空表示空串串空串集空串集不同于空集不同于空集。l符号串长度：符号串长度：符号串中字符的个数符号串中字符的个数.

3、|.|l符号串连接：符号串连接：和和都是符号串，则都是符号串，则为符号串的连接为符号串的连接特别有：特别有：=l符号串集的乘积：符号串集的乘积：A A和和B B是符号串的集合，则称是符号串的集合，则称 AB=AB=|A A，B B 特别有：特别有：A=AA=A=A=A，其中其中表示空集。表示空集。l符号串的方幂：符号串的方幂：设设A A是符号串是符号串的集合，则称的集合，则称A Ai i为符号为符号串集串集A A的方幂，其中的方幂，其中i i是非负整数。是非负整数。A A0 0=A A1 1 =A ,A=A ,A2 2 =A A=A A A AK K=AA.A(k=AA.A(k个个)l符号

4、串集合的正闭包：符号串集合的正闭包：A A+=A=A1 1 A A2 2 A A3 3.l符号串集合的星闭包：符号串集合的星闭包：A A*=A=A0 0 A A1 1 A A2 2 A A3 3.A A*=A=A+A A0 0 =A=A+CS_Dept.GDCC Hjj6/292023/1/12例：设字母表 a-zA-Z a-zA-Z，串集，串集A=aA=a，串，串集集B=bcdB=bcd则 A2=aa=aa A A5aaaaaaaaaa B B+=B B1 B B2 B B3.=(bcd)=(bcd)1 (bcd)(bcd)2 (bcd)(bcd)3.=（bcdbcd）(bcdbcd)(bc

5、dbcd)bcdbcdbcd bcdbcdbcd.ABabcd 正则表达式及其一些性质正则表达式及其一些性质l 为给定的字母表，则每个为给定的字母表，则每个上的上的正则表达正则表达式将定义式将定义上的一个上的一个字符串集字符串集。用用R R 表示表示上的上的正则表达式正则表达式，用用L(RL(R)表示表示R R 所表示的字所表示的字符串集合（正则表达式的集合，符串集合（正则表达式的集合，语言语言，正规，正规集）集）。即：即：函数函数L L表示表示正则表达式正则表达式字符串集的映射。字符串集的映射。正则表达式正则表达式字符串集合字符串集合R 定义构成语言语言L(R)书上：书上：REl则则

6、R 的定义及其含义如下：的定义及其含义如下：是正则表达式，即是正则表达式，即R R 。其中其中L(L()=)=。是正则表达式，即是正则表达式，即R R 。其中其中L(L()=)=。c c是正则表达式，即是正则表达式，即c c R R。其中其中L(c)=cL(c)=c。A A和和B B是正则表达式，即是正则表达式，即A A R R，B B R R ，则有则有(A)A)R R，L(A)L(A)=L(A)=L(A)A|BA|B R R，L(A|B)L(A|B)=L(A)=L(A)L(B)L(B)A BA B R R，L(A B)L(A B)=L(A)L(B)=L(A)L(B)A A*R R，L(AL

7、(A*)=L(A)=L(A)*CS_Dept.GDCC Hjj9/292023/1/12扩充的正则表达式扩充的正则表达式 l 一次或多次重复一次或多次重复:A A+l 任何符号任何符号:“”在字母表中任何符号在字母表中任何符号.|.|.|.|.|.|.l 符号范围符号范围:0-9 :0-9 a-z A-Za-z A-Zl 不在给定范围内的符号不在给定范围内的符号:(:(a|b|c)a|b|c)或或 aal 可选可选:（|-|-）?（可有可无，即有和无两种情况）（可有可无，即有和无两种情况）例：例：A+R，L(A+)=L(A)+A？R，L(A？)=L(A)枚举枚举abc R，L(abc)_=(a

8、|b|c)0-9a-z=0-9|a-z=(0|1|29)|a-zCS_Dept.GDCC Hjj10/292023/1/12优先级约定优先级约定l括号的优先级最高l闭包运算有最高的优先级，并且是左结合的运算；l连接运算的优先级次之，且也是左结合的运算；l或运算的优先级最低，且仍是左结合的运算。闭包运算（闭包运算（*）连接运算（）连接运算（）选择运算）选择运算（|）例:(a)(b)*)|(c)ab*|c正则表达式例正则表达式例l=a,b.a,b.正则表达式正则表达式e e1.1.ab*ab*2.a(a|b)*2.a(a|b)*L(e)L(e)1.1.上所有以上所有以a a为首后跟任意多为首后跟任

9、意多个（包括个（包括0 0个）个）b b的字符串集的字符串集2.2.上所有以上所有以a a为首的字符串集为首的字符串集正则表达式的性质正则表达式的性质q A|B=B|AA|B=B|A|的可交换性的可交换性q A|(B|C)=(A|B)|CA|(B|C)=(A|B)|C|的可结合性的可结合性q A(B C)=(A B)CA(B C)=(A B)C 连接的可结合性连接的可结合性q A(B|C)=A B|A C A(B|C)=A B|A C 连接的可分配性连接的可分配性q (A|B)C=A C|B C A|B)C=A C|B C 连接的可分配性连接的可分配性q A A*=A=A*幂的等价性幂的等价性

10、q A A=A=AA=A 是连接的恒等元素是连接的恒等元素 (A|B)*A*|B*(A|B)*(A*|B*)*(AB)*A*B*CS_Dept.GDCC Hjj13/292023/1/12正则表达式的性质正则表达式的性质q A|B=B|AA|B=B|A|的可交换性的可交换性q A|(B|C)=(A|B)|CA|(B|C)=(A|B)|C|的可结合性的可结合性q A(B C)=(A B)CA(B C)=(A B)C 连接的可结合性连接的可结合性q A(B|C)=A B|A C A(B|C)=A B|A C 连接的可分配性连接的可分配性q (A|B)C=A C|B C A|B)C=A C|B C

11、连接的可分配性连接的可分配性q A A*=A=A*幂的等价性幂的等价性q A A=A=AA=A 是连接的恒等元素是连接的恒等元素 (A|B)*A*|B*(A|B)*=(A*|B*)*(AB)*A*B*程序设计语言中单词的程序设计语言中单词的正则表达式定义正则表达式定义 l保留字保留字如如 BeginBeginbeginbeginl标识符标识符 letter=a-zletter=a-z，A-ZA-Z digit=0-9digit=0-9 identifier=letter(letter|digit)identifier=letter(letter|digit)*l 数字数字整数整数IntIn

12、t1-9Digit1-9Digit*|0|0 实数实数realrealIntInt.IntInt l 特殊符号特殊符号+|-|+|-|正则表达式的局限性正则表达式的局限性l正则表达式正则表达式不能不能用于描述用于描述配对配对或或嵌套嵌套的结的结构构l正则表达式不能用于描述正则表达式不能用于描述重复串重复串例：例：wcw|w是是a和和b的串的串无法用正则表达无法用正则表达式表示（保证两边式表示（保证两边w是相同的）。是相同的）。CS_Dept.GDCC Hjj16/292023/1/12正则表达式的应用程序设计语言中的基本元素程序设计语言中的基本元素-单字单字(token)的描述和判读。的描述和

14、23/1/12课堂练习2假定字母表=0,1，如何用正则表达式描述下述语言(字符串集)?1)?=w|w中恰好有一个1 0*10*2)?=w|w是由任意个0和1组成的字符串（0|1）*3)?=w|w中至少有一个1 （0|1）*1（0|1）*4)?=w|w含有子串001 （0|1）*001（0|1）*5)?=w|w的长度是3的整数倍 (0|1)(0|1)(0|1)*6)?=w|w的开始符号和结束符号相同 0（0|1）*0|1（0|1）*1CS_Dept.GDCC Hjj20/292023/1/12正则定义正则定义l正则表达式的优点是：便于描述符号串的集合，而且它是结构化的描述工具。然而有时书写出来式

15、子比较复杂（较长）l正则定义是一组正则表达式的集合正则定义是一组正则表达式的集合为较长的正则表达式提供一个简化了的为较长的正则表达式提供一个简化了的名字。名字。正则定义正则定义如要为一个或多个数字序列写一个正则表如要为一个或多个数字序列写一个正则表达式，则可写作：达式，则可写作：（0|1|2|0|1|2|9)(0|1|2|9)(0|1|2|9)9)*或写作或写作 digit digitdigit digit*其中其中 digit=digit=0|1|2|0|1|2|9|9就是名字就是名字digitdigit的正则定义，表示为：的正则定义，表示为：digit digit 0|1|2|0|1|2

16、|9|9CS_Dept.GDCC Hjj22/292023/1/12正则定义正则定义如要为一个或多个数字序列写一个正则表如要为一个或多个数字序列写一个正则表达式，则可写作：达式，则可写作：（0|1|2|0|1|2|9)(0|1|2|9)(0|1|2|9)9)*或写作或写作 digit digitdigit digit*其中其中 digit=digit=0|1|2|0|1|2|9|9就是名字就是名字digitdigit的正则定义，表示为：的正则定义，表示为：digit digit 0|1|2|0|1|2|9|9正则名宏正则表达式。其中只允许出现已定义的正则名，而不允许包含未定义的正则名CS_De

17、pt.GDCC Hjj23/292023/1/12正则定义正则定义l l例：例：例：例：MM1 1 e e e e1 1;MM2 2 e e e e2 2;MM3 3 e e e e3 3;MM(M(M(M(M1 1M M M M2 2|M|M|M|M3 3)*l lAA0 0 0 0 表示符号串表示符号串 0 0 A或或A生成生成符号串符号串0l l 读作读作“生成生成”或或 “由由.组成组成”CS_Dept.GDCC Hjj24/292023/1/12正则表达式的缩写形式正则表达式的缩写形式l一个或多个实例一元后缀算符“+”，表示“一个或多个实例”例：a+表示一个或多个a的所有串的集合。

18、r*=r+|r+=r r*l零个或一个实例一元后缀算符“？”表示“零个或一个实例”例:(r)?表示 L(r)|l字符组 abc 表示正则表达式 a|b|cCS_Dept.GDCC Hjj25/292023/1/12习题作业1、叙述由正规式0（0|1）*0所描述的语言。以以0开始并且以开始并且以0结尾的字符串结尾的字符串2、一个语言的非形式化定义为：字母表0，1上所有不含子串001的0、1串。试写出它的正则表达式。CS_Dept.GDCC Hjj26/292023/1/12重点重点l正则表达式的性质l用正则表达式描述字符串CS_Dept.GDCC Hjj27/292023/1/122023年1月12日Any Question?Thank you!

展开阅读全文