3.4正规表达式与正规集 到目前为止，我们已了解了对于任意三型语言L(G), 存在DPAM使L(M①=L(G),反之，任意的M,存在G,使 L(G)=LM).这称为描述语言的等价性 本节将引入正规表达式的概念，它们可用于描述三 型语言的特征，特别是对自动生成词法分析程序而 言，它是非常有用的工具。 所谓正规表达式就是用特定的运算符及运算对象 按某种规则构造的表达式，用于描述给定三型语 言的所有句子
3.4正规表达式与正规集 到目前为止,我们已了解了对于任意三型语言L(G), 存在DFA M使L(M)=L(G),反之,任意的M,存在G,使 L(G)=L(M).这称为描述语言的等价性. 本节将引入正规表达式的概念,它们可用于描述三 型语言的特征,特别是对自动生成词法分析程序而 言，它是非常有用的工具。 所谓正规表达式就是用特定的运算符及运算对象 按某种规则构造的表达式，用于描述给定三型语 言的所有句子
3.4.1正规表达式及正规集的定义 定义设Σ是一字母表，则Σ上的正规表达式（正则表达式，正规式）及其表 示的正规集可递归定义如下： (1)是一~，相应的正规集为； (2)ε是一~，相应的正规集为{8}； (3)Va∈∑，a是一~，相应的正规集为a; (4)设r,s是~，且它们所表示的正规集为L,Ls,则 1.()(S)是~，相应的正规集为LLs; 2.()(s)是~，相应的正规集为ULs; 3.()*是，相应的正规集为L* 有限地使用上面的规则(4)，所得的表达式均是~ 定义中的括号主要用于规定运算顺序.我们规定优先级从高到低依次为* ·，,则可以省略一些括号，例如(0)(S)*(0可简写为s*.另外，·常 常可省略不写：rs*r
3.4.1正规表达式及正规集的定义 • 定义 设是一字母表,则上的正规表达式(正则表达式,正规式)及其表 示的正规集可递归定义如下: (1) 是一~, 相应的正规集为; (2) 是一~, 相应的正规集为{}; (3) a,a 是一~, 相应的正规集为{a}; (4) 设r,s是~, 且它们所表示的正规集为Lr,Ls,则 1. (r) •(s)是~, 相应的正规集为Lr•Ls; 2. (r)|(s)是~, 相应的正规集为Lr Ls; 3. (r)*是~ , 相应的正规集为Lr * 有限地使用上面的规则(4),所得的表达式均是~. 定义中的括号主要用于规定运算顺序.我们规定优先级从高到低依次为 * , • , |,则可以省略一些括号,例如((r) •((s)*)|(r) 可简写为r •s*|r.另外, • 常 常可省略不写: rs*|r
正规式与正规集的例子 正规式 正规集 Ua'=Ua}=e,a,aa,…y 给定正规式，它唯一 a 确定一正规集；反之 i=0 i=0 不真即一个正规集 aa a,aa,aaa,. 可由多个不同的正 a b {a,b} 规式表示， a ba' a,b,ba,baa,baaa, 若二正规式描述同 (a b)"abb 任何以abb结尾的a,b符号串 一正规集，则称二式 等价（相等） (aa ab ba bb)长度为偶数的a,b符号串 正规式间的基本等 (ab)(ab)(ab)长度大等于2的a,b符号串 价关系见下页
正规式与正规集的例子 长度大等于 的 符号串 长度为偶数的 符号串 任何以 结尾的 符号串 正规式 正规集 a b a b a b a b aa ab ba bb a b a b abb abb a b a ba a b ba baa baaa a b a b aa a aa aaa a a a a aa i i i i ( | )( | )( | ) 2 , ( | | | ) , ( | ) | , | { , , , , , } | { , } { , , , } { } { } { , , , } * * * * 0 0 * = = = = 给定正规式,它唯一 确定一正规集;反之 不真.即一个正规集 可由多个 不同的正 规式表示. 若二正规式描述同 一正规集,则称二式 等价(相等) 正规式间的基本等 价关系见下页
正规式的基本等价关系(“公理”） A1.rs=sr A2.rr=r A3.rφ=r A4.(rls)t=rl(st) A5.(rs)t=r(st) A6.r(s t)=rs rt A7.(s t)r=srst A8.r=φr=0 A9.ra=sr=r A10.*=(er）*=rr*
A1. r|s=s|r A2. r|r=r A3. r|=r A4. (r|s)|t=r|(s|t) A5. (rs)t=r(st) A6. r(s|t)=rs|rt A7. (s|t)r=sr|st A8. r=r= A9. r=r=r A10. r*=(|r)*=|rr*
3.4.2由正规文法构造相应的正规式 ·本小节介绍对于给定的三型文法G,如何构造正规式r,使虬L=L(G) 方法：将G视为定义所含非终结符为变量的联立方程组，通过解方程组 求得相应的正规式： 例S→aS|bAbA-→aS设S,A所产生的正规集为s,LA则有 Ls=fa)Ls Ub}LAUb) LA =fa Ls 由定义可知，L(G)=Ls,视S,A为LS,LA的正规式，相应的关系为 S=aS|bAbA=aS记I'为‘+’，有S=aS+bA+b(1)A=aS (2) 将(2)代入(1)，得S=aS+baS+b=(a+ba)S+b(3) 得到形如ox+B的方程.关于这类方程有如下论断： 论断3.1方程xox+B有解=o*B(不唯一) 证：将X=o*B代入右边：右=o0*B+B=(o0*+8)B=*B=左∥ 由论断3.1可知，S=(a+ba)*b=(aba)*b. 另外，对(3)连续使用两次论断3.1，有S=a*(baS+b)=a*baS+ab=(a*ba)*a*b 我们可得一副产品：(aba)*b=(a*ba)*a*b
3.4.2 由正规文法构造相应的正规式 • 本小节介绍对于给定的三型文法G,如何构造正规式r,使Lr=L(G) • 方法: 将G视为定义所含非终结符为变量的联立方程组,通过解方程组 求得相应的正规式. • 例 S→aS | bA | b A→aS 设S,A所产生的正规集为LS, LA 则有 LS={a} LS {b} LA {b} LA ={a} LS 由定义可知,L(G)= LS,视S, A为LS, LA 的正规式,相应的关系为 S=aS | bA |b A=aS 记 ‘|’ 为‘+’ ,有S=aS + bA + b (1) A=aS (2) 将(2)代入(1),得 S=aS + baS + b = (a+ba) S +b (3) 得到形如 x= x + 的方程.关于这类方程有如下论断: 论断3.1 方程x= x + 有解 x= * (不唯一) 证: 将x= * 代入右边: 右= *+ =(*+) = *=左// 由论断3.1可知,S=(a+ba)*b=(a|ba)*b . 另外,对(3)连续使用两次论断3.1,有S=a*(baS+b)=a*baS+a*b=(a*ba)*a*b 我们可得一副产品: (a|ba)*b = (a*ba)*a*b
正规文法与正规式 · 例S→aAA→bA|aB|bB-→>aA 相应的方程组为S=aA(1)A=bA+aB+b(2)B=aA(3) (3)代入(2)：A=(b+aa)A+b得 A=(b+aa)*b 代入(1)：S=a(b+aa)*b=a(blaa)*b 对于左线性文法，在解联立方程时最终会得到形如x=+B的方程，类似 于论断3.1，可知其有解xβ* · 例：标识符的文法为：i→id il l相应的方程为i=i(d+)+d 解为： i=1(d+l)*=l(d)* 在正规式的实际应用中，人们还引入了许多新的运算符，如正闭包‘+” 限制重复次数的‘{m,n},可选符？，字符类[]'，首符号‘，尾符号 ‘$等这里不再赘述.详细内容我们将在中介绍
正规文法与正规式 • 例 S→aA A→bA | aB | b B→aA 相应的方程组为 S=aA (1) A=bA+aB+b (2) B=aA (3) (3)代入(2): A=(b+aa)A+b 得 A=(b+aa)*b 代入(1): S=a(b+aa)*b=a(b|aa)*b • 对于左线性文法,在解联立方程时最终会得到形如x=x+的方程,类似 于论断3.1,可知其有解x=* • 例: 标识符的文法为: i→id |il |l相应的方程为 i=i(d+l)+d 解为: i= l(d+l)* =l(d|l)* • 在正规式的实际应用中,人们还引入了许多新的运算符,如正闭包‘+’, 限制重复次数的‘{m,n}’,可选符‘?’,字符类‘[ ]’,首符号‘^’,尾符号 ‘$’等.这里不再赘述.详细内容我们将在中介绍
3.4.3正规式构造FA-Thompson法 ·对于V正规式r,FAM,使L(M)=Lr 。 构造方法：根据正规式的运算的递归定义，按运算符的个数，归纳地给 出FA.M将只含一个初态，一个终态，且终态无矢线射出. 。 设r为Σ上的正规式，且含个运算符，构造M的方法如下： 1.r=0 r=8 r=a∈ 2.设当n=1,2,,k-1时，M均可构造，当n=k时，根据正规式的定义，r只 能是，r,*这三种形式之一其中，I,2中最多含k-1个运算符， 且设相应的自动机为 M1=(K1,Σ，fi,S01,{Sfn}) L(MI)=Lr M2=(K2,∑，f五，S02,{S2}) L(M2)=Lr2 K1∩K2=☑
3.4.3 正规式构造FA⎯Thompson法 • 对于正规式r,FA M,使 L(M)=Lr • 构造方法: 根据正规式的运算的递归定义,按运算符的个数n,归纳地给 出FA. M将只含一个初态,一个终态,且终态无矢线射出. • 设r 为上的正规式,且含n个运算符,构造M的方法如下: 1. r= r= r=a s f f s f 2.设当n=1,2,…,k-1时,M均可构造,当n=k时,根据正规式的定义,r只 能是 r1|r2, r1•r2, r1*这三种形式之一.其中, r1,r2 中最多含k-1个运算符, 且设相应的自动机为 M1=(K1, ,f1,S01,{Sf1}) L(M1)=Lr1 M2=(K2, ,f2,S02,{Sf2}) L(M2)=Lr2 K1K2= a
Thmopson法（续） (1)=r12,引入新开始状态S0,终态S,将M1,M2并联： S So2 [2]=12,将M1,M串联 D +S02 (fD [3)=*,引入新开始状态S,终态S, 令原M构成循环 在实际的构造中，我们可以省略 一些矢线。 书中P77例3.11给出了由正规式 a(blaa)*b构造相应的FA过程
Thmopson 法(续) (1) r= r1|r2 ,引入新开始状态S0,终态Sf,将M1,M2并联: S01 f1 S02 f2 s Sf (2) r=r1•r2 , 将M1,M2串联 S01 f1 S02 f1 (3) r=r*,引入新开始状态S0,终态Sf, 令原M1构成循环 s S01 f1 Sf 在实际的构造中，我们可以省略 一些矢线。 书中P77例3.11给出了由正规式 a(b|aa)*b 构造相应的FA过程