编译原理课程第2讲.ppt

《编译原理课程第2讲.ppt》由会员分享，可在线阅读，更多相关《编译原理课程第2讲.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、温故知新温故知新编译原理的内容及学习意义编译原理的内容及学习意义翻译器、编译器的定义翻译器、编译器的定义编译器的阶段划分及前端、后端的概念编译器的阶段划分及前端、后端的概念“遍遍”的概念的概念第二章第二章 词法分析词法分析本章内容本章内容词法分析器：把构成源程序的字符流翻译成词法分析器：把构成源程序的字符流翻译成词法分析器：把构成源程序的字符流翻译成词法分析器：把构成源程序的字符流翻译成记号流，记号流，记号流，记号流，还完成和用户接口的一些任务还完成和用户接口的一些任务还完成和用户接口的一些任务还完成和用户接口的一些任务围绕词法分析器的自动生成展开围绕词法分析器的自动生成展开围绕词法分析器的自

2、动生成展开围绕词法分析器的自动生成展开介绍正规式、状态转换图和有限自动机概念介绍正规式、状态转换图和有限自动机概念介绍正规式、状态转换图和有限自动机概念介绍正规式、状态转换图和有限自动机概念词法分析器词法分析器词法分析器词法分析器语法分析器语法分析器语法分析器语法分析器符号表符号表符号表符号表记号记号记号记号取下一个记号取下一个记号取下一个记号取下一个记号源程序源程序源程序源程序词法分析器的功能：词法分析器的功能：词法分析器词法分析器词法分析器词法分析器记号（记号（记号（记号（tokentoken）流）流）流）流源代码源代码源代码源代码2.1 词法记号及属性词法记号及属性 2.1.1 词法记号

3、、模式、词法单元词法记号、模式、词法单元 词法单元：又称单词，是源程序中的字符串。词法单元：又称单词，是源程序中的字符串。词法单元：又称单词，是源程序中的字符串。词法单元：又称单词，是源程序中的字符串。词法记号：满足某种规则的词法单元，采用同一种记法词法记号：满足某种规则的词法单元，采用同一种记法词法记号：满足某种规则的词法单元，采用同一种记法词法记号：满足某种规则的词法单元，采用同一种记法词法记号。该规则称为词法记号。该规则称为词法记号。该规则称为词法记号。该规则称为模式模式模式模式。模式：描述词法单元与词法记号对应关系的规则。模式：描述词法单元与词法记号对应关系的规则。模式：描述词法单元与

4、词法记号对应关系的规则。模式：描述词法单元与词法记号对应关系的规则。是描是描是描是描述源程序中某个述源程序中某个述源程序中某个述源程序中某个记记记记号的号的号的号的词词词词法法法法单单单单元集合的元集合的元集合的元集合的规则规则规则规则。源程序字源程序字源程序字源程序字符流符流符流符流顺序顺序顺序顺序组合组合组合组合词法词法词法词法单元单元单元单元词法词法词法词法记号记号记号记号模式模式模式模式2.1 词法记号及属性词法记号及属性 2.1.1 词法记号、模式、词法单元词法记号、模式、词法单元 源程序源程序源程序源程序字符流字符流字符流字符流顺序顺序顺序顺序组合组合组合组合词法词法词法词法单元单

5、元单元单元词法词法词法词法记号记号记号记号模式模式模式模式例：例：例：例：varvar countcount :integerinteger ;countcount =5 5 ;词法单元词法单元词法单元词法单元2.1 词法记号及属性词法记号及属性 2.1.1 词法记号、模式、词法单元词法记号、模式、词法单元 词法记号词法记号词法记号词法记号词法单元例举词法单元例举词法单元例举词法单元例举模式的非形式描述模式的非形式描述模式的非形式描述模式的非形式描述 varvar var var var var for for for for for for relation relation ,=,=,=,

6、=,或或或或=或或或或=或或或或 id id sum,count,D5 sum,count,D5 由字母开头的字母数字串由字母开头的字母数字串由字母开头的字母数字串由字母开头的字母数字串 num num3.1,10,2.8 E123.1,10,2.8 E12 任何数值常数任何数值常数任何数值常数任何数值常数 literal literal“seg.error”“seg.error”引引引引号号号号“和和和和”之之之之间间间间的的的的任任任任意意意意字字字字符符符符串，但引号本身除外串，但引号本身除外串，但引号本身除外串，但引号本身除外常见记号及模式的例子：常见记号及模式的例子：常见记号及模式的

7、例子：常见记号及模式的例子：2.1 词法记号及属性词法记号及属性 2.1.1 词法记号、模式、词法单元词法记号、模式、词法单元 词法记号词法记号词法记号词法记号词法单元例举词法单元例举词法单元例举词法单元例举模式的非形式描述模式的非形式描述模式的非形式描述模式的非形式描述relation relation ,=,=,=,=,或或或或=0 0）2.2 词法记号的描述与识别词法记号的描述与识别 语言的运算语言的运算和：和：和：和：L L M M=s s|s s L L 或或或或 s s MM 连接连接连接连接：LM LM=st st|s s L L 且且且且 t t MM 指数：指数：指数：指数：

8、L L0 0是是是是 ，L Li i是是是是L Li i-1-1L L 闭包：闭包：闭包：闭包：L L L L =L L L L0 0 L L L L1 1 L L L L2 2 正闭包正闭包正闭包正闭包：L L L L+=L L L L1 1 L L L L2 2 例例2.2（p17）L L:A A,B B,Z Z,a a,b b,z z,D D:0,1,9 0,1,9 L L D D,LDLD,L L6 6,L L*,L L(L L D D)*,D D+2.2 词法记号的描述与识别词法记号的描述与识别 2.2.2 2.2.2 正规式正规式正规式：按照一组定义规则，由较简单的正规式正规式：按

9、照一组定义规则，由较简单的正规式正规式：按照一组定义规则，由较简单的正规式正规式：按照一组定义规则，由较简单的正规式构成的，每个正规式构成的，每个正规式构成的，每个正规式构成的，每个正规式 r r r r 表示一个语言表示一个语言表示一个语言表示一个语言 L(r).L(r).L(r).L(r).定定定定义规则说明义规则说明义规则说明义规则说明 L(r)L(r)L(r)L(r)是怎样以各种方式从是怎样以各种方式从是怎样以各种方式从是怎样以各种方式从 r r r r 的子的子的子的子正规式所表示的语言组合而成。正规式所表示的语言组合而成。正规式所表示的语言组合而成。正规式所表示的语言组合而成。正正

10、正正规规规规式式式式用来表用来表用来表用来表示简单的语言，示简单的语言，示简单的语言，示简单的语言，叫做叫做叫做叫做正规集正规集正规集正规集。正规式是用于说明词法单元如正规式是用于说明词法单元如正规式是用于说明词法单元如正规式是用于说明词法单元如何对应到词法记号的模式。与何对应到词法记号的模式。与何对应到词法记号的模式。与何对应到词法记号的模式。与非形式化的描述相比，正规式非形式化的描述相比，正规式非形式化的描述相比，正规式非形式化的描述相比，正规式更具形式化，更加精确。更具形式化，更加精确。更具形式化，更加精确。更具形式化，更加精确。2.2 词法记号的描述与识别词法记号的描述与识别 2.2.

11、2 2.2.2 正规式正规式正规式正规式正规式正规式 定义的语言定义的语言定义的语言定义的语言 备注备注备注备注 a a a a a a (r r)|()|(s s)L L(r r)L L(s s)r r和和和和s s是正规式是正规式是正规式是正规式(r r)()(s s)L L(r r)L L(s s)r r和和和和s s是正规式是正规式是正规式是正规式(r r)*(L L(r r)*r r是正规式是正规式是正规式是正规式(r r)L L(r r)r r是正规式是正规式是正规式是正规式运算符的优先级：运算符的优先级：运算符的优先级：运算符的优先级：*连接运算连接运算连接运算连接运算|(a)(

12、b)a)(b)a)(b)a)(b)*)|(c)|(c)|(c)|(c)可以写成可以写成可以写成可以写成abababab*|c|c|c|c 2.2 词法记号的描述与识别词法记号的描述与识别 正规式的例子正规式的例子 =a a,b b a a|b b a a,b b(a a|b b)()(a a|b b)aaaa,abab,baba,bbbb aa aa|ab ab|ba ba|bbbb aaaa,abab,baba,bbbb a a*由字母由字母由字母由字母a a构成的所有串集构成的所有串集构成的所有串集构成的所有串集(a a|b b)*由由由由a a和和和和b b构成的所有串集构成的所有串集构

13、成的所有串集构成的所有串集复杂的例子复杂的例子(00|11|(01|10)(00|11)(01|10)句子：句子：010011010000100000101110012.2 词法记号的描述与识别词法记号的描述与识别 2.2.3 正规定义正规定义对正规式命名，使表示简洁。对正规式命名，使表示简洁。对正规式命名，使表示简洁。对正规式命名，使表示简洁。d d1 1 r r1 1 d d2 2 r r2 2.d dn n r rn n各个各个各个各个d di i的名字都不同的名字都不同的名字都不同的名字都不同每个每个每个每个r ri i都是都是都是都是 d d1 1,d d2 2,d di i-1-1

14、 上的正规式上的正规式上的正规式上的正规式这样就保证了，每个名这样就保证了，每个名这样就保证了，每个名这样就保证了，每个名字对应的正规式中使用字对应的正规式中使用字对应的正规式中使用字对应的正规式中使用的各种符号已经在前面的各种符号已经在前面的各种符号已经在前面的各种符号已经在前面定义了，从而可以避免定义了，从而可以避免定义了，从而可以避免定义了，从而可以避免递归定义的情况。递归定义的情况。递归定义的情况。递归定义的情况。2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子正规定义的例子 Pascal语言的标识符集合语言的标识符集合letter A|B|Z|a|b|zdigit 0

15、|1|9id letter(letter|digit)*2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子正规定义的例子PascalPascal无符号数集合，例无符号数集合，例无符号数集合，例无符号数集合，例19461946,11.2811.28,63.663.6E8E8,1.991.99E E 6 6 digitdigit 0 0|1|9|1|9digitsdigits digitdigit digitdigit*optional_fractionoptional_fraction .digitsdigits|optional_exponentoptional_exponent

16、 (E(+|(E(+|)digits)|)digits)|numnumdigits optional_fraction optional_exponentdigits optional_fraction optional_exponent简化表示简化表示简化表示简化表示numnum digitdigit+(.digitdigit+)?(E(+|)?(E(+|)?digit)?digit+)?)?简化规则：简化规则：简化规则：简化规则：(1)r+=rr*(2)r?=r|(3)a-z=a|b|c|z(4)abc=a|b|c2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子正规定义的例

17、子while while while whiledo do do dorelop relop|=|=|=|=|=|=id id letter(letter|digit)letter(letter|digit)*num num digit digit+(.digit(.digit+)?(E(+|)?(E(+|)?digit)?digit+)?)?delim delim blankblank|tabtab|newlinenewline ws ws delimdelim+前面所提前面所提前面所提前面所提到的词法到的词法到的词法到的词法记号，实记号，实记号，实记号，实际上就是际上就是际上就是际上就是正

18、规式的正规式的正规式的正规式的名字！名字！名字！名字！小结小结词法分析器词法分析器记号（记号（token）流）流源代码源代码词法分析器工作原理：词法分析器工作原理：词法分析器工作原理：词法分析器工作原理：源程序源程序字符流字符流顺序顺序顺序顺序组合组合组合组合词法词法单元单元词法词法记号记号模式模式模式模式非形式非形式化描述化描述形式化形式化描述描述正规式正规式字母字母组合组合组合组合串串语言语言集合集合集合集合集合集合集合集合字母表字母表名名字字习题习题 作业作业作业作业 习题习题习题习题 2.3 2.3 练习题练习题练习题练习题（要求使用伪代码给出算法）：（要求使用伪代码给出算法）：（要求

19、使用伪代码给出算法）：（要求使用伪代码给出算法）：编写一个程序，用于统计文件中单词的总数，不同单编写一个程序，用于统计文件中单词的总数，不同单编写一个程序，用于统计文件中单词的总数，不同单编写一个程序，用于统计文件中单词的总数，不同单词的数目。（假设输入文件中只包含字母和空格）词的数目。（假设输入文件中只包含字母和空格）词的数目。（假设输入文件中只包含字母和空格）词的数目。（假设输入文件中只包含字母和空格）eg:eg:I love Dalian and I love DLUTI love Dalian and I love DLUT单词总数：单词总数：单词总数：单词总数：7 7不同单词数目：不同单词数目：不同单词数目：不同单词数目：5 5