《(精品)编译原理第二章_(5).ppt》由会员分享，可在线阅读，更多相关《(精品)编译原理第二章_(5).ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2.4 正则表达式正则表达式主要内容：主要内容：正则表达式和正则集；正则表达式和正则集；正则表达式和有限自动机的相互转化。正则表达式和有限自动机的相互转化。一、正则表达式和正则集一、正则表达式和正则集 l正则表达式是表示給定字母表上的符号串集合的一正则表达式是表示給定字母表上的符号串集合的一种工具种工具,是描述程序设计语言中单词的一种简单而且是描述程序设计语言中单词的一种简单而且数学化工具。数学化工具。l表示符号串的构成模式。表示符号串的构成模式。l正则表达式正则表达式r r定义了一个符号串集合定义了一个符号串集合rs,rsrs,rs内的每个内的每个符号串都与符号串都与r r所定义的模式相匹配
2、，所定义的模式相匹配，rsrs称为由称为由r r生成生成的语言，记作的语言，记作L(rL(r)。l正则表达式所表示的符号串集合又称为正则表达式所表示的符号串集合又称为正则集。正则集。（一）正则表达式和正则集的定义（一）正则表达式和正则集的定义定义定义1 1：设：设为有限字母表，在为有限字母表，在上的正则表达上的正则表达式和正则集可递归定义如下：式和正则集可递归定义如下：(1)(1)和和是是上的正则表达式，它们表示的正上的正则表达式，它们表示的正则集分别为则集分别为和和；(2)(2)对任何对任何a,a a,a 是是上的正则表达式，它所上的正则表达式，它所表示的正则集为表示的正则集为a;a;(3)
3、(3)若若r,sr,s都是正则表达式，它们表示的正则集都是正则表达式，它们表示的正则集分别为分别为R R和和S,S,则则(r)(r)、r|sr|s、r r s s、(r)(r)*也是正也是正则表达式，它们分别表示的正则集是：则表达式，它们分别表示的正则集是：R R，RS,RSRS,RS和和R R*。(4)(4)有限次使用上述三条规则构成的表达式，称有限次使用上述三条规则构成的表达式，称为为上的正则表达式，仅由这些正则表达式表上的正则表达式，仅由这些正则表达式表示的集合称为正则集。示的集合称为正则集。另外一种定义另外一种定义 设设为有限字母表，为有限字母表，R 表示表示上的所有正则表达式上的所有
4、正则表达式的集合：的集合：是是正则表达式，即正则表达式，即 R R，则有：则有：L(L()=;是正则表达式，即是正则表达式，即 R R，则有：，则有：L(L()=)=;a a 是是正则表达式，即正则表达式，即a a R R，则有：则有：L(aL(a)=a;设和是正则表达式，即设和是正则表达式，即 R ，R ，则有：则有：(A)R ,L(A)=L(A)A|B R ,L(A|B)=L(A)L(B)A B R ,L(A B)=L(A)L(B)A*R ,L(A*)=(L(A)*（二）正则表达式示例（二）正则表达式示例（1 1）l=a,b.a,b.正则表达式正则表达式eL(e)1.a1.aaa2.a|b
5、2.a|ba,ba,b3.ab3.ab abab 4.4.(a|b)(a|b)aaaa,abab,baba,bb,bb5.5.a*,a,aa,aaaa,a,aa,aaaa,（二）正则表达式示例（二）正则表达式示例（2 2）l=a,b.a,b.正则表达式正则表达式e e1.1.abab*2.a(a|b)2.a(a|b)*L(e)L(e)L(ab*)=L(a)L(b*)=a,b,bb,bbb,L(a(a|b)*)=L(a)L(a|b)*)=L(a)(L(a|b)*=aa,b*上所有以上所有以a a为首后跟任意多个为首后跟任意多个（包括（包括0 0个）个）b b的字符串集的字符串集 上所有以上所有以
6、a a为首的字符串集为首的字符串集（三）正则表达式的性质（三）正则表达式的性质（三）正则表达式的性质（三）正则表达式的性质l正则表达式的等价正则表达式的等价 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*幂的等价性幂的等
7、价性q A A =A=AA=A 是连接的恒等元素是连接的恒等元素 （四）扩充的正则表达式（四）扩充的正则表达式（四）扩充的正则表达式（四）扩充的正则表达式 l一次或多次重复一次或多次重复:R+l 任何符号任何符号:“”在字母表中任何符号。在字母表中任何符号。l符号范围符号范围:“-”,如如0-9 a-z A-Z。l 不在给定范围内的符号不在给定范围内的符号:“”或或“”。如。如(a|b|c)或或a L Labc （读作：读作：tilde读作：读作：caret）l 0或或1次次(可选可选):“？”。如。如r?=(|r)（五）正则定义（五）正则定义（五）正则定义（五）正则定义l为较长的正则表达式提
8、供一个简化了的名字。为较长的正则表达式提供一个简化了的名字。如要为一个或多个数字序列写一个正则表达式，如要为一个或多个数字序列写一个正则表达式，则可写作：则可写作：（0|1|2|0|1|2|3 3|4 4|5 5|6 6|7 7|8|9)8|9)（0|1|2|0|1|2|3 3|4 4|5 5|6 6|7 7|8|9)8|9)*或写作或写作 digit digitdigit digit*其中其中名字名字digitdigit就是数字的正则定义，表示为：就是数字的正则定义，表示为：digitdigit =0|1|2|0|1|2|3 3|4 4|5 5|6 6|7 7|8|98|9例：程序设计语言中
9、单词的正则表达式定义例：程序设计语言中单词的正则表达式定义例：程序设计语言中单词的正则表达式定义例：程序设计语言中单词的正则表达式定义 l保留字保留字 如如 BeginBeginbeginbeginl标识符标识符 letter=a-zletter=a-z，A-ZA-Z digit=0-9digit=0-9 identifier=letter(letter|digit)identifier=letter(letter|digit)*l 数字数字 整数整数IntInt1-9Digit1-9Digit*|0|0 实数实数realrealIntInt.IntInt l 特殊符号特殊符号+|-|+|-|
10、（六）正则表达式的局限性（六）正则表达式的局限性（六）正则表达式的局限性（六）正则表达式的局限性l正则表达式不能用于描述配对或嵌套的结构正则表达式不能用于描述配对或嵌套的结构l正则表达式不能用于描述重复串正则表达式不能用于描述重复串 例：例：w c w|w是是a和和b的串的串无法用正则表达式表无法用正则表达式表示（保证两边示（保证两边w是相同的）。是相同的）。二、正则表达式和有限自动机的二、正则表达式和有限自动机的相互转化相互转化l定理定理 1对对上的每一个正则表达上的每一个正则表达r，存在一个，存在一个上的非确定有限自动机上的非确定有限自动机M，使得，使得 L(M)=L(r)。l证明：对于字
11、母表证明：对于字母表上的任意一个正则表达式上的任意一个正则表达式R,一定可以构造出一个非确定有限自动机一定可以构造出一个非确定有限自动机 M,使得使得L(M)=L(R)。Step1:首先构造此非确定有限自动机首先构造此非确定有限自动机M的初始的初始状态状态S和终止状态和终止状态Z，由，由S射出指向射出指向Z的有向弧上标的有向弧上标记正则表达式记正则表达式R。step2:反复利用下述的替换规则对正则表达式反复利用下述的替换规则对正则表达式R依次进行分解，直至状态转换图中所有有向弧上依次进行分解，直至状态转换图中所有有向弧上标记的符号都是字母表标记的符号都是字母表上的元素或上的元素或 为止。为止。
12、替换为替换为(1)R1R2ABR1ACBR2R1|R2ABABR1R2替换为替换为R*AB替换为替换为RCABl例例：有正规表达式：有正规表达式(a|b)*aa,为之构造等为之构造等价的价的NFA。(a|b)*aaSZ(a|b)*ASZaa(a|b)*SABaZa(a|b)*ASZaa(a|b)*SABaZaSSABaZaa|bSSABaZaa|bSSABaZaa,bl定理定理2：对于字母表对于字母表上的非确定有限自动机上的非确定有限自动机M，存在，存在上的正则表达式上的正则表达式R，使得，使得L(R)=L(M)。l证明：Step1:在在M的状态转换图中加入两个节点，一个是唯一的的状态转换图中
13、加入两个节点，一个是唯一的开始状态节点开始状态节点S,另一个是唯一的终止状态节点另一个是唯一的终止状态节点Z。从。从S出发用标有出发用标有的有向弧连接到的有向弧连接到M 的所有初始状态节点上，的所有初始状态节点上，从从M 的所有终止状态节点用标有的所有终止状态节点用标有的有向弧连接到的有向弧连接到Z节节点。点。Step2:反复利用下述的替换规则进行替换，直到状态转换反复利用下述的替换规则进行替换，直到状态转换图中只剩下节点图中只剩下节点S和和Z，在，在S指向指向Z的有向弧上所标记的的有向弧上所标记的正则表达式就是所求的结果。正则表达式就是所求的结果。l规则1：l规则2：l规则3：l例例 有如下
14、图所示的有如下图所示的NFA M,NFA M,试构造与之等价的正试构造与之等价的正则表达式则表达式r r a651324aabbabZSa651324aabbabbaSaabZb6512aab|ba65bZSa12abaSaabZb6512aab|ba65bZSa12aa612(ab|ba)a*bSZa(ab|ba)a*bSZ单元总结单元总结l三个工具：三个工具：文法、文法、有限自动机、正则表达式有限自动机、正则表达式l三个算法：三个算法：NFA NFA到到DFADFA的转换的转换 DFADFA的化简的化简 正则表达式与正则表达式与FAFA的相互转换的相互转换l一个实现：一个实现：DFADFA的实现的实现l练习题：将下述自动机最小化。练习题：将下述自动机最小化。0123aababba,b作业作业z=a,b,c 试试给给出出-上上一一个个不不包包含含连连续续两两个个b的的所所有有符符号号串集合的正则定义串集合的正则定义.z =a,b,c 叙叙述述正正则则式式(b|c)*a(b|c)*a)*(b|c)*描描述述的的符符号号串串 z 0,1 叙述正则式叙述正则式(00|11)(01|10)(00|11)(01|10)(00|11)描述的符号串描述的符号串z 给给出出能能被被5整整除除的的二二进进制制数数表表示示形形式式的的正正则则定定义。义。