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