(精品)编译原理第二章_(5)

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2.4,正则表达式,主要内容：,正则表达式和正则集；,正则表达式和有限自动机的相互转化。,一、正则表达式和正则集,正则表达式是表示給定字母表上的符号串集合的一种工具,是描述程序设计语言中单词的一种简单而且数学化工具。,表示符号串的构成模式。,正则表达式,r,定义了一个符号串集合,rs,rs,内的每个符号串都与,r,所定义的模式相匹配，,rs,称为由,r,生成的语言，记作,L(r,),。,正则表达式所表示的符号串集合又称为,正则集。,（一）正则表达式和正则集的定义,定义,1,：设为有限字母表，在上的正则表达式和正则集可递归定义如下：,(1),和,是上的正则表达式，它们表示的正则集分别为,和,；,(2),对任何,a,a,是上的正则表达式，它所表示的正则集为,a;,(3),若,r,s,都是正则表达式，它们表示的正则集分别为,R,和,S,则,(r),、,r|s,、,r,s,、,(r),*,也是正则表达式，它们分别表示的正则集是：,R,，,RS,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,）,=,a,b.,正则表达式,e,L(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,）,=,a,b.,正则表达式,e,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,)*,=,aa,b,*,上所有以,a,为首后跟任意多个,（包括0个）,b,的字符串集,上所有以,a,为首的字符串集,（三）正则表达式的性质,正则表达式的等价,A|B=B|A,|,的可交换性,A|(B|C)=(A|B)C,|,的可结合性,A(B C)=(A B)C,连接的可结合性,A(B|C)=A B|A C,连接的可分配性,(,A|B)C=A C|B C,连接的可分配性,A,*,=A,*,幂的等价性,A,=,A=A,是连接的恒等元素,（四）扩充的正则表达式,一次或多次重复:,R,+,任何符号:“”在字母表中任何符号。,符号范围:“,-”,如,0-9 a-z A-Z,。,不在给定范围内的符号:“,”,或“,”,。如,(a|b|c),或,a,L,abc,（,读作：,tilde,读作：,caret,）,0,或1次(可选):“？”。如,r?=(,|r),（五）正则定义,为较长的正则表达式提供一个简化了的名字。如要为一个或多个数字序列写一个正则表达式，则可写作：,（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,例：程序设计语言中单词的正则表达式定义,保留字 如,Beginbegin,标识符,letter=a-z，A-Z,digit=0-9,identifier=letter(letter|digit),*,数字,整数,Int1-9Digit,*,|0,实数,realInt,.,Int,特殊符号+|-|,（六）正则表达式的局限性,正则表达式不能用于描述配对或嵌套的结构,正则表达式不能用于描述重复串,例：,w c w|w,是,a,和,b,的串无法用正则表达式表示（保证两边,w,是相同的）。,二、正则表达式和有限自动机的相互转化,定理,1,对上的每一个正则表达,r,，存在一个上的非确定有限自动机,M,，使得,L(M)=,L(r,),。,证明：对于字母表上的任意一个正则表达式,R,一定可以构造出一个非确定有限自动机,M,使得,L(M)=L(R),。,Step1:,首先构造此非确定有限自动机,M,的初始状态,S,和终止状态,Z,，由,S,射出指向,Z,的有向弧上标记正则表达式,R,。,step2:,反复利用下述的替换规则对正则表达式,R,依次进行分解，直至状态转换图中所有有向弧上标记的符号都是字母表上的元素或,为止。,替换为,(,1,),R,1,R,2,A,B,R,1,A,C,B,R,2,R,1,|R,2,A,B,A,B,R,1,R,2,替换为,R*,A,B,替换为,R,C,A,B,例：有正规表达式,(,a|b,)*,aa,为之构造等价的,NFA,。,(,a|b,)*,aa,S,Z,(,a|b,)*,A,S,Z,aa,(,a|b,)*,S,A,B,a,Z,a,(,a|b,)*,A,S,Z,a,a,(,a|b,)*,S,A,B,a,Z,a,S,S,A,B,a,Z,a,a|b,S,S,A,B,a,Z,a,a|b,S,S,A,B,a,Z,a,a,b,定理,2,：,对于字母表上的非确定有限自动机,M,，存在上的正则表达式,R,，使得,L(R)=L(M),。,证明：,Step1:,在,M,的状态转换图中加入两个节点，一个是唯一的开始状态节点,S,另一个是唯一的终止状态节点,Z,。从,S,出发用标有,的有向弧连接到,M,的所有初始状态节点上，从,M,的所有终止状态节点用标有,的有向弧连接到,Z,节点。,Step2:,反复利用下述的替换规则进行替换，直到状态转换图中只剩下节点,S,和,Z,，在,S,指向,Z,的有向弧上所标记的正则表达式就是所求的结果。,规则,1,：,规则,2,：,规则,3,：,例 有如下图所示的,NFA M,试构造与之等价的正则表达式,r,a,6,5,1,3,2,4,a,a,b,b,a,b,Z,S,a,6,5,1,3,2,4,a,a,b,b,a,b,ba,S,a,ab,Z,b,6,5,1,2,a,ab|ba,6,5,b,Z,S,a,1,2,a,ba,S,a,ab,Z,b,6,5,1,2,a,ab|ba,6,5,b,Z,S,a,1,2,a,a,6,1,2,(,ab|ba,)a,*,b,S,Z,a(ab|ba,)a,*,b,S,Z,单元总结,三个工具：,文法、,有限自动机、正则表达式,三个算法：,NFA,到,DFA,的转换,DFA,的化简,正则表达式与,FA,的相互转换,一个实现：,DFA,的实现,练习题：将下述自动机最小化。,0,1,2,3,a,a,b,a,b,b,a,b,作业,S,=a,b,c,试给出,S-,上一个,不包含连续两个,b,的所有符号串集合的正则定义,.,S,=a,b,c,叙述正则式(,b|c),*,a(b|c),*,a),*,(b|c),*,描述的符号串,S,0,1,叙述正则式,(00|11),(01|10)(00|11),(01|10),),(00|11),描述的符号串,给出能被5整除的二进制数表示形式的正则定义。,