09--第三章 有限自动机与词法分析器.ppt

1、第三章 有穷自动机与词法分析器,任课教师 王养廷,1 正则表达式,基本概念 字母表：它是非空有限集合，其中的元素称为字母（或符号），一般使用表示。 例如： =a,b,c,.,z 符号串：符号的有限序列 例如：a, ab, cda 、表示空串 区分和,1 正则表达式（续）,符号串长度：符号串中包含符号的个数，使用|表示符号串的长度 例如：| a |=1, | abc |=3, | |=0 符号串的连接：、是符号串，为符号串和的连接 例如： =aa, =bb, =aabb = = ,1 正则表达式（续）,符号串的乘积：A、B是符号串的集合，则AB定义为符号串A和B的乘积。AB=| A, B，若为空

2、集，则A=A=A。 例如：A=ab, cd, B=12,34，则AB=ab12, ab34, cd12, cd34 符号串集合的方幂：设A是符号串的集合，则称Ai为符号串的方幂 A0= A1=A Ak=AA.A(k个),1 正则表达式（续）,符号串的正闭包：设A是符号串的集合，则称A+ 是符号串的正闭包 A+= A1 A2 A3 . 例如：A=a, A+=a,aa,aaa,. 符号串的星闭包：设A是符号串的集合，则称A* 是符号串的星闭包 A+= A0 A+ 例如：A=a, A*=, a,aa,aaa,. 问题 A=a, b，A的正闭包和星闭包是什么,1 正则表达式（续）,正则符号串集：用RS

3、S表示，定义为： 字母表的任何子集 空集 若A、B是RSS,则AB是RSS 若A、B是RSS,则AB是RSS 若A、B是RSS,则A*是RSS,1 正则表达式（续）,正则表达式 设是给定字符集，则每个上的正则表达式将定义上的一个字符串集。若用RE表示的正则表达式，则用L(RE ) 表示RE所表示的正则集，则RE的定义及含义如下： 是正则表达式，即 R E，其中L()= 是正则表达式，即 R E，其中L()=a a是正则表达式，即 a RE ，其中L(a)=a 设A和B是正则表达式，即A RE ，B RE ,则有 (A) R E， L(A)=L(A) A|B R E ， L(A|B)=L(A)

4、| L(B) AB R E ， L(AB)=L(A) L(B) A* R E ， L(A*)=L(A)*,1 正则表达式（续）,算符优先级 幂运算 连接 选择 a*b|c =(a*)b) | c 扩充RE A+ R E ， L(A+)=L(A)+ A? R E ， L(A?)=L(A) chi-chk R E 表示（ chi |chi+1 | chk ） abc R E 表示（ a| b| c ） chi-chk chj-chl表示chi-chk | chj-chl,正则表达式（续）,正则表达式的性质：P48 A|B =B|A |的可交换性 A|(B|C)=(A|B)|C |的可结合性 A(BC)=(AB)C 连接的可结合性 A(B|C)=AB|AC 连接的可分配性 (A|B)C=AC|BC 连接的可分配性 A*=A* 幂的等价性,正则表达式（续）,正则表达式示例 假设：D=0,1,9, L=az, AZ D+ D+. D+ L(D|L) 举例 (a|bc)*d)+ (0|1)* (2|3)+)|0011,正则表达式（续）,实例 a a | b ab a* a*b* (a|b)* (ab)*,a+ a(b|c) a+(b|c)a* (a|