编译原理第二章_(5).ppt

《编译原理第二章_(5).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.4正则表达式主要内容：１．正则表达式和正则集；２．正则表达式和有限自动机的相互转化。一、正则表达式和正则集正则表达式是表示給定字母表上的符号串集合的一种工具,是描述程序设计语言中单词的一种简单而且数学化工具。表示符号串的构成模式。正则表达式r定义了一个符号串集合rs,rs内的每个符号串都与r所定义的模式相匹配，rs称为由r生成的语言，记作L(r)。正则表达式所表示的符号串集合又称为正则集。（一）正则表达式和正则集的定义定义1：设∑为有限字母表，在∑上的正则表达式和正则集可递归定义如下：(1)和是∑上的正则表达式，它们表示的正则集分别为{ε}和；(2)对任何a∈∑,a是∑上的

2、正则表达式，它所表示的正则集为{a};(3)若r,s都是正则表达式，它们表示的正则集分别为R和S,则(r)、r

3、s、rs、(r)*也是正则表达式，它们分别表示的正则集是：R，R∪S,RS和R*。(4)有限次使用上述三条规则构成的表达式，称为∑上的正则表达式，仅由这些正则表达式表示的集合称为正则集。另外一种定义设∑为有限字母表，R表示∑上的所有正则表达式的集合：是正则表达式，即R，则有：L()={　};是正则表达式，即R，则有：L()={};a是正则表达式，即aR，则有：L(a)={a};设Ａ和Ｂ是正则表达式，即ＡR，ＢR，则有：(A)R,

4、L((A))=L(A)A

5、BR,L(A

6、B)=L(A)∪L(B)ABR,L(AB)=L(A)L(B)A*R,L(A*)=(L(A))*（二）正则表达式示例（1）={a,b}.正则表达式eL(e)1.a{a}2.a

7、b{a,b}3.ab{ab}4.(a

8、b)(a

9、b){aa,ab,ba,bb}5.a*{ε,a,aa,aaaa,…}（二）正则表达式示例（2）={a,b}.正则表达式eab*2.a(a

10、b)*L(e)L(ab*)=L(a)L(b*)={a}{ε,b,bb,bbb,…}L(a(a

11、b)*)=L(a)L((a

12、b)*)=L(a)(L(a

13、b))*={a}{a

14、,b}*上所有以a为首后跟任意多个（包括0个）b的字符串集上所有以a为首的字符串集（三）正则表达式的性质正则表达式的等价A

15、B=B

16、A

17、的可交换性A

18、(B

19、C)=(A

20、B)C

21、的可结合性A(BC)=(AB)C连接的可结合性A(B

22、C)=AB

23、AC连接的可分配性(A

24、B)C=AC

25、BC连接的可分配性A**=A*幂的等价性A=A=A是连接的恒等元素（四）扩充的正则表达式一次或多次重复:R+任何符号:“…”在字母表中任何符号。符号范围:“--”,如[0--9][a--z][A--Z]。不在给定范围内的符号:“^”或“~”。如~(a

26、b

27、c)或[^a][Labc]（~读作：tild

28、e^读作：caret）0或1次(可选):“？”。如r?=(

29、r)（五）正则定义为较长的正则表达式提供一个简化了的名字。如要为一个或多个数字序列写一个正则表达式，则可写作：（0

30、1

31、2

32、3

33、4

34、5

35、6

36、7

37、8

38、9)（0

39、1

40、2

41、3

42、4

43、5

44、6

45、7

46、8

47、9)*或写作digitdigit*其中名字digit就是数字的正则定义，表示为：digit=0

48、1

49、2

50、3

51、4

52、5

53、6

54、7

55、8

56、9例：程序设计语言中单词的正则表达式定义保留字如Begin＝begin标识符letter=[a-z，A-Z]digit=[0-9]identifier=letter(letter

57、digit)*数字整数Int＝

58、[1-9]Digit*

59、0实数real＝Int.Int特殊符号+

60、-

61、…（六）正则表达式的局限性正则表达式不能用于描述配对或嵌套的结构正则表达式不能用于描述重复串例：{wcw

62、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:反

63、复利用下述的替换规则对正则表达式R依次进行分解，直至状态转换图中所有有向弧上标记的符号都是字母表∑上的元素或为止。替换为(1)R1R2ABR1ACBR2R1

64、R2ABABR1R2替换为R*AB替换为RεCABε例：有正规表达式(a

65、b)*aa,为之构造等价的NFA。(a

66、b)*aaSZ(a

67、b)*ASZaa(a

68、b)*SABaZa(a

69、b)*ASZaa(a

70、b)*SABaZaSSABaZaεεa

71、bSSABaZaεεa

72、bSSABaZaεεa,b定理2：