编译原理第2章 词法分析2.ppt
文本预览下载声明
2.3 正规表达式与有限自动机简介 ;正则表达式;符号串集的方幂:
设A是符号串的集合,则称Ai为符号串集A的方幂,其中i是非负整数。
A0 ={?}
A1 = A , A2 = A A
AK = AA......A(k个)
符号串集合的正闭包:
A+ =A1 ? A2 ?A3 ......
符号串集合的闭包(星闭包)(克林闭包):
A* =A0 ? A1 ? A2 ?A3 ......;正则表达式及其一些性质;■ ?是 正则表达式,即??R 。其中L(?)={ }。(特殊)
■ ?是正则表达式,即??R 。其中L(?)={ ? }。
■ c??是正则表达式,即c?R。其中L(c)={c}。
■ A和B是正则表达式,即A ?R,B ?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)*
; 为了理解正规式与正规集的含义,我们以程序语言中的标识符为例予以说明。
程序语言中使用的标识符是一个以字母开头的字母数字串,如果字母用letter表示,数字用digit表示,则标识符可表示为
letter (letter∣digit)*
其中,letter与 (letter∣digit)*的并置表示两者的连接;括号中的“∣”表示letter或digit两者选一;“*”表示零次或多次引用由“*”标记的表达式;(letter∣digit)*是letter∣digit的零次或多次并置,即表示一长度为0、1、2、…的字母数字串;letter (letter∣digit)*表示以字母开头的字母数字串,也即标识符集。letter (letter∣digit)*就是表示标识符的正规式,而标识符集就是这个正规式所表示的正规集。; 对于给定的字母表Σ,正规式和正规集的递归定义如下:
(1) ε和Ф都是Σ上的正规式,它们所表示的正规集分别为{ε}和Ф。
(2) 对任一个a∈Σ,a是Σ上的一个正规式,它所表示的正规集为{a}。
(3) 如果R和S是Σ上的正规式,它们所表示的正规集分别为L(R)和L(S),则:;① R∣S是Σ上的正规式,它所表示的正规集为L(R)∪L(S);
② R.S是Σ上的正规式,它所表示的正规集为L(R) L(S);
③ (R)*是Σ上的正规式,它所表示的正规集为(L(R))*;
④ R也是Σ上的正规式,它所表示的正规集为L(R)。
; (4) 仅由有限次使用规则(1)~(3)得到的表示式是Σ上的正规式,它所表示的集合是Σ上的正规集。
在上述定义中,规则(1)、(2)为基础规则,规则(3)为归纳规则,规则(4)是界限规则或终止规则。此外,Σ上的一个字(符号串)是指由Σ中的字符所构成的一个有穷序列;不包含任何字符的序列称为空字,用ε表示。我们用Σ*表示Σ上所有字的全体,则空字ε也在其中。例如,若Σ={a,b},则Σ*={ε,a,b,aa,ab,ba,bb,aaa,…}。我们还用Ф表示不含任何元素的空集{}。这里需要注意ε、{}和{ε}的区别:{ε}是由空字组成的集合,而{}则表示不含任何字的集合。; 正规式间的运算符“∣”表示或,“· ”表示连接(通常可省略),“*”表示闭包,使用括号可以改变运算的次序。如果规定“*”优先于“· ”,“· ”优先于“∣”,则在不出现混淆的情况下括号也可以省去。注意,Σ*的正规式R和S的连接可以形式化地定义为
RS={α β∣α∈Rβ∈S}
即集合RS中的字是由R和S中的字连接而成的,且R自身的n次连接记为 ; 我们规定R0={ε},并令R*=R0∪R1∪R2∪R3∪…,则称R*是R的闭包;此外,令R+=RR*,并称R+是R的正闭包。闭包R*中的每个字都是由R中的字经过有限次连接而成的。对于Σ上的正规式R和S,如果它所表示的正规集L(R)=L(S),则称R和S等价并记为R=S。不难证明,正规式具有下列性质:
(1) 交换律:R∣S = S∣R。
(2) 结合律:R∣(S∣T) = (R∣S)∣T;
显示全部