编译原理与实现03第3章 词法分析1.ppt

《编译原理与实现03第3章 词法分析1.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、3.5正则表达式由于各种高级程序设计语言的单词形式基本上差不多，人们就希望能否构造一个自动生成系统，只要给出程序设计语言的各类单词描述以及识别出各类单词后应输出的结果，这种自动系统便能自动产生此程序设计语言的词法分析程序。词法分析程序自动生成系统的实现涉及正则表达式和有限自动机理论假设有字母表∑={0，1}，那么，字母表上的每个元素都是正则表达式，这样的正则表达式表示的语言只有一个句子。例如，0是一个正则表达式，表示的语言为{0}，该语言只有一个句子0。如果想表示更加复杂的语言，就必须使用运算符组成复杂的正则表达式，

2、这一点很像用加减乘除运算符构造算术表达式。在正则表达式中，可使用的运算符有连接、选择和重复。例3.4，有正则表达式R1=1,R2=1,R3=0，所描述的语言分别为L1={1},L2={1},L3={0}，求正则表达式R1.R2.R3、R1

3、R3{R1}描述的语言。解：根据正则表达式运算符的操作定义，可得如下结果：R1.R2.R3是一个正则表达式，描述的语言为{110}，该语言有一个句子110。R1

4、R3是一个正则表达式，描述的语言为{1,0}，该语言有两个句子1和0。{R1}是一个正则表达式，描述的语言为{1n

5、n=

6、0,1,2,….}，该语言有无穷的句子，如1、11、11111等等。标识符的正则表达式为：{标识符}=字母{字母

7、数字}而带有符号的实数的正则表达式为：{数}=（ε

8、+

9、-）（{数字}.数字{数字}）3.5.1正则表达式定义设有两个正则表达式R1和R2，它们分别产生语言L1和L2，则正则表达式运算符的操作定义如下：连接：R1.R2={xy

10、x∈L1，y∈L2}选择：R1

11、R2={x

12、x∈L1或x∈L2}重复：{R1}={x

13、x∈L1*，L1*=L10∪L11∪L12∪…}3.5.1正则表达式定义定义了运算符后，下面

14、我们给出正则表达式的形式定义。设∑是有穷字母表，在∑上的正则表达式及所描述的语言可递归定义如下：1.Φ是一个表示空集的正则表达式。2.ε是一个正则表达式，它所表示的语言仅含一个空符号串，即{ε}3.a是一个正则表达式，a∈∑，它所表示的语言由符号a所组成{a}4.如果R1和R2是正则表达式，其表示的语言分别为L1和L2，则1)R1

15、R2或R1+R2是一个表示语言L1∪L2的正则表达式2)R1.R2或R1R2是一个表示语言L1L2的正则表达式3){R1}或R1*是一个表示语言L1*的正则表达式4)(R)表示的语言仍是L

16、1的正则表达式，但调整优先权，使括号内的运算符优先权高于括号外的。5.所有∑上的正则表达式可由上述4条规则构造出来。注意：不要混淆Φ和ε，正则表达式ε描述的语言只含一个空字符串ε，而Φ表示的语言不含有任何字符串。3.5.1正则表达式定义在正则表达式的运算符中，重复优先级高于连接，而连接高于选择，因此，(p)

17、((p).(q))可写成p

18、pq,但表达式(p

19、q).r中的括号则不能去掉。例3.5，设字母表∑={a,b}，则a,b,Φ和ε都是∑上的正则表达式，所描述的语言为{a}、{b}、{}、{ε}，求表达式{a}{b}

20、、{a

21、b}和{aa

22、ab

23、ba

24、bb}定义的语言。解：根据正则表达式的形式定义，可得如下结果：表达式{a}{b}定义的语言为：{ambn

25、m≥0,n≥0}，表达式{a

26、b}定义的语言为：{x

27、x∈{a,b}*}，即字母a或b组成的任意长度字符串。而表达式{aa

28、ab

29、ba

30、bb}表示的语言由字母a或b组成的所有偶长度字符串。3.5.1正则表达式定义例3.6，设字母表∑={0}，求表达式0{0}与00{0}

31、0定义的语言。解：表达式0{0}定义的语言是{0i

32、i≥1}表达式00{0}

33、0定义的语言是{0i

34、i≥1}例

35、3.6给出了两个不同的正则表达式，但描述的语言却相同，这说明不同的正则表达式可描述相同的语言。如果两个正则表达式表示相同的语言，则称这两个表达式等价或相等。显然，例3.6的表达式0{0}和00{0}

36、0是等价的。正则表达式的部分操作符满足结合律、交换律和分配律:即(ab)c=a(bc)(a

37、b)

38、c=a(b

39、c)a

40、b=b

41、aa(b

42、c)=ab

43、ac注意：连接不满足交换律，即ab≠ba3.5.2正则文法与正则表达式的等价性正则文法与正则表达式有等价性，即可以将正则文法转换成正则表达式。例如，用正则文法表示标识符的文法

44、规则如下：＜标识符＞∷=a

45、b

46、…

47、z

48、＜标识符＞a

49、＜标识符＞b

50、…

51、＜标识符＞z

52、＜标识符＞0

53、＜标识符＞1

54、…

55、＜标识符＞9而采用正则表达式则为：＜标识符＞=(a

56、b

57、c

58、…

59、z){a

60、b

61、…

62、z

63、0

64、1

65、…

66、9}或简写成＜标识符＞=字母{字母

67、数字}由此可见，正则表达式在描述语言时比正则文法更为简洁。3.5.2正则文法与正则表达式的等价