编译原理 陈意云课件 第二章.ppt

《编译原理 陈意云课件 第二章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章词法分析本章内容词法分析器：把构成源程序的字符流翻译成记号流，还完成和用户接口的一些任务围绕词法分析器的自动生成展开介绍正规式、状态转换图和有限自动机概念词法分析器语法分析器符号表记号(token)取下一个记号源程序2.1词法记号及属性2.1.1词法记号、模式、词法单元记号名词法单元例举模式的非形式描述ifif字符i,fforfor字符f,o,rrelation<,<=,=,…<或<=或=或…idsum,count,D5由字母开头的字母数字串number3.1,10,2.8E12任何数值常数literal“seg.error”引号“和”之间任意不含引号本身的字符串2.1词法记号及

2、属性历史上词法定义中的一些问题忽略空格带来的困难DO8I3.75等同于DO8I3.75DO8I3,75关键字不保留IFTHENTHENTHEN=ELSE；ELSE…关键字、保留字和标准标识符的区别保留字是语言预先确定了含义的词法单元标准标识符也是预先确定了含义的标识符，但程序可以重新声明它的含义2.1词法记号及属性2.1.2词法记号的属性position=initial+rate60的记号和属性值：id，指向符号表中position条目的指针assign_opid，指向符号表中initial条目的指针add_opid，指向符号表中rate条目的指针mul_

3、opnumber，整数值602.1词法记号及属性2.1.3词法错误词法分析器对源程序采取非常局部的观点例：难以发现下面的错误fi(a==f(x))…在实数是“数字串.数字串”格式下，可以发现下面的错误123.x紧急方式的错误恢复删掉当前若干个字符，直至能读出正确的记号错误修补进行增、删、替换和交换字符的尝试2.2词法记号的描述与识别2.2.1串和语言字母表：符号的有限集合，例：={0,1}串：符号的有穷序列，例：0110,语言：字母表上的一个串集{,0,00,000,…},{},句子：属于语言的串串的运算连接（积）xy，s=s=s幂s0为，si为si-1s（i>0

4、）2.2词法记号的描述与识别语言的运算并：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…例L:{A,B,…,Z,a,b,…,z},D:{0,1,…,9}LD,LD,L6,L*,L(LD)*,D+2.2词法记号的描述与识别2.2.2正规式正规式用来表示简单的语言，叫做正规集正规式定义的语言备注{}a{a}a(r)

7、(s)L(r)∪L(s)r和s是正规式(r)(s)L(r)L(s)r和s是正规式(r)*(L(r))*r是正规式(r)L(r)r是正规式((a)(b)*

8、)

9、(c)可以写成ab*

10、c2.2词法记号的描述与识别正规式的例子={a,b}a

11、b{a,b}(a

12、b)(a

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

14、ab

15、ba

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

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

18、11

19、((01

20、10)(00

21、11)(01

22、10)))句子：010011010000100000101110012.2词法记号的描述与识别2.2.3正规定义对正规式命名，使表示简洁d1r1d2r2...dnrn各个di的名字都不同每个ri都是{d1,d2,…,di-1}上的正规式2.2词法记号的描述与识别正规

23、定义的例子C语言的标识符是字母、数字和下划线组成的串letter_A

24、B

25、…

26、Z

27、a

28、b

29、…

30、z

31、_digit0

32、1

33、…

34、9idletter_(letter_

35、digit)*2.2词法记号的描述与识别正规定义的例子无符号数集合，例1946,11.28,63E8,1.99E6digit0

36、1

37、…

38、9digitsdigitdigit*optional_fraction.digits

39、optional_exponent(E(+

40、

41、)digits)

42、numberdigitsoptional_fractionoptional_exponent简化表示numberd

43、igit+(.digit+)?(E(+

44、)?digit+)?2.2词法记号的描述与识别正规定义的例子（进行下一步讨论的例子）whilewhiledodorelop<

45、<=

46、=

47、<>

48、>

49、>=letterA

50、B

51、…

52、Z

53、a

54、b

55、…

56、zidletter(letter

57、digit)*numberdigit+(.digit+)?(E(+

58、)?digit+)?delimblank

59、tab

60、newlinewsdelim+2.2词法记号的