编译原理课件第3章

《编译原理课件第3章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章词法分析3.1词法分析器的功能3.2单词的描述3.3单词的识别3.4词法分析程序的自动生成3.5本章小结7/20/202113.1词法分析器的功能功能：输入源程序，输出单词符号(token)。即：把构成源程序的字符串转换成“等价的”单词(记号)序列根据词法规则识别及组合单词，进行词法检查对数字常数完成数字字符串到二进制数值的转换删去空格字符和注释7/20/202123.1.1单词的分类与表示&3.1.2词法分析器的输出一、单词的种类1.关键字:也称基本字，begin、end、for、do...2.标识符:由用户定义，表示各种名字3.常数:整常数、实

2、常数、布尔常数、字符串常数等4.运算符:算术运算符+、-、*、/等；逻辑运算符not、or与and等；关系运算符=、<>、、、和等5.分界符:，、；、（、）...7/20/20213二、单词的内部形式几种常用的单词内部形式：1、按单词种类分类2、保留字和分界符采用一符一类3、标识符和常数的单词值又为指示字（指针值）种别属性值表示单词的种类，可用整数编码或记忆符表示不同的单词不同的值7/20/20214单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数保留字分界符类别编码1234567单词值内部字符串整数值数值0或1内部字符串保留字或

3、内部编码分界符或内部编码1、按单词种类分类7/20/202152、保留字和分界符采用一符一类单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数BEGINENDFORDO………:+*,(类别编码123456789……20212223……单词值内部字符串整数值数值0或1内部字符串----……-----7/20/20216例3.1语句ifcount>7thenresult:=3.14的单词符号序列(IF，0)(ID，指向count的符号表入口)(GT，0)(INT，7)(THEN，0)(ID，指向result的符号表入口)(ASSIGN，0)(REA

4、L，3.14)(SEMIC，0)跟实现有关7/20/202173.1.3源程序的输入缓冲与预处理超前搜索和回退双字符运算符（**,/*,:=,…）DO90k=1,10DO90k=1.10缓冲区假定源程序存储在磁盘上，这样每读一个字符就需要访问一次磁盘，效率显然是很低的。空白字符的剔除剔除源程序中的无用符号、空格、换行、注释等7/20/202183.1.4词法分析阶段的错误处理1．非法字符检查2．关键字拼写错误检查3．不封闭错误检查4．重复说明检查5．错误恢复与续编译紧急方式恢复(panic-moderecovery)反复删掉剩余输入最前面的字符，直到词法

5、分析器能发现一个正确的单词为止。7/20/202193.1.5词法分析器的位置目标程序词法分析器语法分析器语义分析与代码生成目标代码整理图3.4以语法分析器为中心源程序符号表以语法分析器为中心的优点：比较简单以词法分析作为独立的一个阶段：简化编译器的设计。提高编译器的效率。增强编译器的可移植性。7/20/2021103.2单词的描述3.2.1正则文法正则文法G=(V，T，P，S)中，对αβ∈P，αβ均具有形式Aw或AwB(Aw或ABw)，其中A，B∈V，w∈T+。例3.2标识符的文法A

6、B

7、…

8、X

9、a

10、b

11、…

12、z

13、A

14、B

15、…

16、Za

17、b

18、…

19、z0

20、1

21、2

22、…

23、97/20/202111例3.2标识符的文法或者定义为约定：用digit表示数字：0,1,2,…,9;用letter表示字母：A,B,…,Z,a,b,…,z

24、

25、A

26、B

27、…

28、Z

29、a

30、b

31、…

32、z0

33、1

34、2

35、…

36、9例3.3无符号数的文法7/20/2021123.2.2正则表达式例3.2：标识符的另一种表示letter(le

37、tter

38、digit)*

39、表示"或"*表示Kleene闭包+表示正闭包？表示“0或1个”Letter和(letter

40、digit)*的并列表示两者的连接正则式r表示正则集,相应的正则集记为L(r)7/20/2021133.2.2正则表达式(续)—RE定义3.1设∑是一个字母表，则∑上的正则表达式及其所表示的正则语言可递归地定义如下：⑴是∑上的一个正则表达式，它表示空集；⑵ε是∑上的一个正则表达式，它表示语言{ε}；⑶对于a(a∈∑)，a是∑上的一个正则表达式，它表示的正则语言是{a}；⑷假设r和s都是∑上的正则表达式，它们表示的语言分别为L(r)和L

41、(s)，则：①(r)也是∑上的正则表达式，它表示的语言为L(r)；②(r

42、s)也