第03讲-词法分析-II.ppt

《第03讲-词法分析-II.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、本章内容词法分析器：把构成源程序的字符流翻译成记号流，还完成和用户接口的一些任务介绍正规式、状态转换图和有限自动机概念Lex与词法分析器的自动生成词法分析器语法分析器符号表记号取下一个记号源程序第二章词法分析1回顾词法分析概念词法记号的描述2词法单元、词法记号L1:x=IDCOLONIDASSGNy2+12;IDPLUSINTSEMI-COL词法单元又称单词，是编程语言中合法的字符串词法记号满足某种规则的词法单元，采用同一种记法——词法记号。3词法单元词法记号词法单元词法记号模式用模式语言描述正规式，是描述词法记号的一种最为常见的模式语言4字母组合串

2、语言集合集合字母表长度为0的空串2.2词法记号的描述与识别长度的表示

3、a

4、2.2.1串和语言字母表：符号的有限集合，例：={0,1}串：符号的有穷序列，例：0110,语言：字母表上的一个串集{,0,00,000,…},{},52.2词法记号的描述与识别2.2.1串和语言串的运算连接xy，s=s=s积（指数）s0为，si为si-1s（i>0）6语言的运算和：L∪M={s

5、sL或sM}连接：LM={st

6、sL且tM}指数：L0是{}，Li是Li-1L闭包：L=L0∪L1∪L2∪…正闭包：L+=L1∪L2∪…例2.2（p17）L

7、:{A,B,…,Z,a,b,…,z},D:{0,1,…,9}L∪D,LD,L6,L*,L(L∪D)*,D+2.2词法记号的描述与识别L=L0∪L+7本讲纲要正规式词法记号的识别有限自动机定义DFA构建方法8正规式正规式，又称正则表达式，RegularExpression92.2.2正规式正规式：按照一组定义规则，由较简单的正规式构成的，每个正规式r表示一个语言L(r).定义规则说明L(r)是怎样以各种方式从r的子正规式所表示的语言组合而成。正规式用来表示简单的语言，叫做正规集。正规式是用于说明词法单元如何对应到词法记号的模式。与非形式化的描述相比，

8、正规式更具形式化，更加精确。2.2词法记号的描述与识别102.2.2正规式正规式定义的语言备注{}a{a}a(r)

9、(s)L(r)∪L(s)r和s是正规式(r)(s)L(r)L(s)r和s是正规式(r)*(L(r))*r是正规式(r)L(r)r是正规式运算符的优先级：*>连接运算>

10、((a)(b)*)

11、(c)可以写成ab*

12、c2.2词法记号的描述与识别定义字母表上正规式的规则11正规式的例子={a,b}a

13、b{a,b}(a

14、b)(a

15、b){aa,ab,ba,bb}aa

16、ab

17、ba

18、bb{aa,ab,ba,bb}a*由字母a构成的所有串集(

19、a

20、b)*由a和b构成的所有串集复杂的例子(00

21、11

22、((01

23、10)(00

24、11)(01

25、10)))句子：010011010000100000101110012.2词法记号的描述与识别122.2.3正规定义对正规式命名，使表示简洁。d1r1d2r2...dnrn各个di的名字都不同每个ri都是{d1,d2,…,di-1}上的正规式保证：每个名字对应的正规式中使用的各种符号已经在前面定义了，从而可以避免递归定义的情况。2.2词法记号的描述与识别13Pascal里面的标识符模式正规式表示letterA

26、B

27、…

28、Z

29、a

30、b

31、…

32、zdig

33、it0

34、1

35、…

36、9idletter(letter

37、digit)*怎么用语言来描述Pascal的标识符模式？Pascal标识符模式的自然语言描述：首字符必须是字母，由字母或数字组成的字符串14C语言的标识符模式模式的非形式描述首字符必须是_或者字母，由_、字母或数字组成的字符串请仿照Pascal标识符的例子，写出C语言的标识符的正规式表示15正规定义的例子C语言的标识符是字母、数字和下划线组成的串letter_A

38、B

39、…

40、Z

41、a

42、b

43、…

44、z

45、_digit0

46、1

47、…

48、9idletter_(letter_

49、digit)*C语言的标识符模式162.

50、2词法记号的描述与识别简化规则：r+=rr*r?=r

51、[a-z]=a

52、b

53、c

54、…

55、z正规定义的例子Pascal无符号数集合，例1946,11.28,63.6E8,1.99E6digit0

56、1

57、…

58、9digitsdigitdigit*optional_fraction.digits

59、optional_exponent(E(+

60、

61、)digits)

62、numdigitsoptional_fractionoptional_exponent简化表示numdigit+(.digit+)?(E(+

63、)?digit+)?17whilewhi

64、ledodorelop<

65、<=

66、=

67、<>

68、>

69、>=idletter(letter

70、digit)*num