编译原理第二章_(5).ppt

2.4 正则表达式主要内容： １．正则表达式和正则集； ２．正则表达式和有限自动机的相互转化 一、正则表达式和正则集 l正则表达式是表示給定字母表上的符号串集合的 一种工具,是描述程序设计语言中单词的一种简单 而且数学化工具l表示符号串的构成模式l正则表达式r定义了一个符号串集合rs, rs内的每 个符号串都与r所定义的模式相匹配，rs称为由r 生成的语言，记作L(r)l正则表达式所表示的符号串集合又称为正则集一）正则表达式和正则集的定义 定义1：设∑为有限字母表，在∑上的正则表达 式和正则集可递归定义如下： (1)  和是∑上的正则表达式，它们表示的 正则集分别为{ε}和； (2) 对任何a∈∑,a 是∑上的正则表达式，它 所表示的正则集为{a};(3) 若r,s都是正则表达式，它们表示的正则集 分别为R和S, 则(r)、r|s、rs、(r)*也是正 则表达式，它们分别表示的正则集是：R， R∪S , RS和R* (4) 有限次使用上述三条规则构成的表达式， 称为∑上的正则表达式，仅由这些正则表达 式表示的集合称为正则集另外一种定义 设∑为有限字母表， R表示∑上的所有正则表达式 的集合：ü 是正则表达式，即  R，则有： L( )={ }; ü 是正则表达式，即  R，则有： L( )={};ü a  是正则表达式，即a  R，则有： L(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）l={ a,b }.正则则表达式eL(e) 1.a{a}2.a|b{a, b}3.ab{ ab }4.(a|b) (a|b){aa, ab, ba, bb}5. a*{ε,a,aa,aaaa,…}（二）正则表达式示例（2）l={ a,b }.正则表达式e1. ab*2. a(a|b)* 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))* ={a}{a,b}*上所有以a为首后跟任意多个（包括0个）b的字符串集上所有以a为首的字符串集（三）正则表达式的性质l正则表达式的等价 q A | B = B | A | 的可交换性q A | (B | C) =(A | B ) C | 的可结合性q A (B C) =(A B )C 连接的可结合性q A (B | C) =A B | A C 连接的可分配性q (A | B ) C =A C | B C 连接的可分配性q A** =A* 幂的等价性q A  =  A=A 是连接的恒等元素 （四）扩充的正则表达式 l 一次或多次重复: R+l 任何符号: “…” 在字母表中任何符号。

l符号范围: “--” ,如[0--9] [a--z] [A--Z]l 不在给定范围内的符号: “^”或“~”如 ~(a|b|c)或[^a] [Labc] （~ 读作：tilde ^ 读作： caret） l 0或1次(可选): “？”如r?=( |r)（五）正则定义l为较长的正则表达式提供一个简化了的名字如要为一个或多个数字序列写一个正则表达式，则可写作：（0|1|2|3|4|5|6|7|8|9) （0|1|2|3|4|5|6|7|8|9)*或写作 digit digit*其中名字digit就是数字的正则定义，表示为：digit = 0|1|2|3|4|5|6|7|8|9例：程序设计语言中单词的正则表达式定义 l保留字 如 Begin＝beginl标识符letter=[a-z，A-Z]digit=[0-9]identifier=letter(letter|digit)*l 数字 整数Int＝[1-9]Digit*|0 实数real＝Int.Int l 特殊符号 +|-|…（六）正则表达式的局限性l正则表达式不能用于描述配对或嵌套的结构l正则表达式不能用于描述重复串例：{w c w | w是a和b的串}无法用正则表达式表 示（保证两边w是相同的）。

二、正则表达式和有限自动机的 相互转化l l定理定理 1 1 对∑上的每一个正则表达r，存在一个∑ 上的非确定有限自动机M，使得 L(M) = L(r) l证明：对于字母表∑上的任意一个正则表达式R, 一定可以构造出一个非确定有限自动机 M, 使得 L(M)=L(R)Ø Step1:首先构造此非确定有限自动机M的初始 状态S和终止状态Z，由S射出指向Z的有向弧上 标记正则表达式RØ step2:反复利用下述的替换规则对正则表达式 R依次进行分解，直至状态转换图中所有有向弧 上标记的符号都是字母表∑上的元素或为止 替换为(1)R1 R2ABR1ACBR2R1|R2ABABR1R2替换为R*AB替换为RεCABεl例 ：有正规表达式(a|b)*aa,为之构造等 价的NFAa|b)*aaSZ(a|b)*ASZaa(a|b)*SABaZa(a|b)*ASZaa(a|b)*SABaZaSSABaZaεεa|bSSABaZaεεa|bSSABaZaεεa,bl定理2：对于字母表∑上的非确定有限自动机M，存 在∑上的正则表达式R，使得L(R) = L(M)l证明： Step1:在M的状态转换图中加入两个节点，一个是唯一 的开始状态节点S,另一个是唯一的终止状态节点Z 。

从S出发用标有ε的有向弧连接到M 的所有初始状态 节点上，从M 的所有终止状态节点用标有ε的有向弧 连接到Z节点Step2:反复利用下述的替换规则进行替换，直到状态转 换图中只剩下节点S和Z，在S指向Z的有向弧上所标 记的正则表达式就是所求的结果l规则1：l规则2：l规则3：l例 有如下图所示的NFA M,试构造与之等价的 正则表达式r a651324aabba bZSa651324aabba bεεbaSεaabZεb6512aab|ba65bZεSεa 12abaSεaabZεb6512aab|ba65bZεSεa12aa612(ab|ba )a*bSεZεa(ab|ba )a*bSZ单元总结l三个工具：文法、有限自动机、正则表达式l三个算法：NFA到DFA的转换DFA的化简正则表达式与FA的相互转换l一个实现：DFA的实现 l练习题：将下述自动机最小化0123aaba bba,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整除的二进制数表示形式的正则 定义。