第2讲-词法分析-I.ppt

《第2讲-词法分析-I.ppt》由会员分享，可在线阅读，更多相关《第2讲-词法分析-I.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2022/12/211/28编译原理和技术编译原理和技术2022/12/212/28本讲纲要本讲纲要词法分析概念词法分析概念词法记号的描述词法记号的描述2022/12/213/28词法分析器词法分析器词法分析器词法分析器语法分析器语法分析器语法分析器语法分析器语义分析器语义分析器语义分析器语义分析器源程序源程序源程序源程序中间代码中间代码中间代码中间代码生成器生成器生成器生成器代码优化器代码优化器代码优化器代码优化器代码生成器代码生成器代码生成器代码生成器目标程序目标程序目标程序目标程序出错管理器出错管理器出错管理器出错管理器符号表符号表符号表符号表管理器管理器管理器管理器 2022/12/2

2、14/28第二章第二章 词法分析词法分析本章内容词法分析器：把构成源程序的字符流翻译成词法分析器：把构成源程序的字符流翻译成记号流，记号流，还完成和用户接口的一些任务还完成和用户接口的一些任务介绍正规式、状态转换图和有限自动机概念介绍正规式、状态转换图和有限自动机概念LexLex与词法分析器的自动生成与词法分析器的自动生成词法分析器词法分析器词法分析器词法分析器语法分析器语法分析器语法分析器语法分析器符号表符号表符号表符号表记号记号记号记号取下一个记号取下一个记号取下一个记号取下一个记号源程序源程序源程序源程序2022/12/215/28词法分析：编译第一步词法分析：编译第一步看一个中文的句子

3、看一个中文的句子你们你们你们你们 是是是是 优秀的优秀的优秀的优秀的 大工学子大工学子大工学子大工学子代词代词代词代词动词动词动词动词形容词形容词形容词形容词名词（短语）名词（短语）名词（短语）名词（短语）通过分词操作，我们会把句子以单词或者词组为单位进行划分，通过分词操作，我们会把句子以单词或者词组为单位进行划分，通过分词操作，我们会把句子以单词或者词组为单位进行划分，通过分词操作，我们会把句子以单词或者词组为单位进行划分，得到一个句型。得到一个句型。得到一个句型。得到一个句型。2022/12/216/28词法分析：编译第一步词法分析：编译第一步C语言的语句例子语言的语句例子L1L1:x x

4、=IDIDCOLONCOLONIDIDASSGNASSGNy2y2+1212;IDIDPLUSPLUSINTINTSEMI-COLSEMI-COL编译的词法分析做的工作类似于分词，编译的词法分析做的工作类似于分词，编译的词法分析做的工作类似于分词，编译的词法分析做的工作类似于分词，把原始的字符串流形式的程序文本转换为词法记号流的形式把原始的字符串流形式的程序文本转换为词法记号流的形式把原始的字符串流形式的程序文本转换为词法记号流的形式把原始的字符串流形式的程序文本转换为词法记号流的形式2022/12/217/28词法单元、词法记号词法单元、词法记号词法单元又称单词，是编程语言中合法的字符串又称

5、单词，是编程语言中合法的字符串L1L1:x x=IDIDCOLONCOLONIDIDASSGNASSGNy2y2+1212;IDIDPLUSPLUSINTINTSEMI-COLSEMI-COL例子中例子中例子中例子中哪些是词法单元？哪些是词法单元？哪些是词法单元？哪些是词法单元？2022/12/218/28词法单元、词法记号词法单元、词法记号词法单元又称单词，是编程语言中合法的字符串又称单词，是编程语言中合法的字符串词法记号满足某种规则的词法单元，采用同一种记法满足某种规则的词法单元，采用同一种记法词法记号。词法记号。L1L1:x x=IDIDCOLONCOLONIDIDASSGNASSGNy

6、2y2+1212;IDIDPLUSPLUSINTINTSEMI-COLSEMI-COL例子中例子中例子中例子中哪些是词法记号？哪些是词法记号？哪些是词法记号？哪些是词法记号？2022/12/219/28词法单元与词法记号词法单元与词法记号满足一个给定规则的词法单元，被记为一个词法记号词法单元词法单元词法单元词法单元词法记号词法记号词法记号词法记号模式模式模式模式2022/12/2110/28词法模式词法模式C语言的标识符语言的标识符?x2,12,_12,_abc 哪些是合法的哪些是合法的C标识符？标识符？C C语言标识符的规则（模式）：语言标识符的规则（模式）：语言标识符的规则（模式）：语言标

7、识符的规则（模式）：首字符必须是首字符必须是首字符必须是首字符必须是_ _或者字母，由或者字母，由或者字母，由或者字母，由_ _、字母或数字组成的字符串、字母或数字组成的字符串、字母或数字组成的字符串、字母或数字组成的字符串2022/12/2111/28词法模式词法模式 词法记号词法记号词法单元例举词法单元例举模式的非形式描述模式的非形式描述 STRUCT STRUCT structstructstructstruct FOR FOR for for for for RELOP RELOP ,=,=,=,=,或或=0 0）2022/12/2120/282.2 词法记号的描述与识别词法记号的描述

8、与识别 语言的运算和：和：L L M M=s s|s s L L 或或 s s MM 连接连接：LM LM=stst|s s L L 且且 t t MM 指数：指数：L L0 0是是 ，L Li i是是L Li i-1-1L L 闭包：闭包：L L =L L0 0 L L1 1 L L2 2 正闭包正闭包：L L+=L L1 1 L L2 2 例2.2（p14）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+2022/12/2121/282.2 词法记号的描述与识别词法

9、记号的描述与识别 2.2.2 2.2.2 正规式正规式：按照一组定义规则，由较简单的正规式正规式：按照一组定义规则，由较简单的正规式构成的，每个正规式构成的，每个正规式 r r 表示一个语言表示一个语言 L(rL(r).).定定义规则说明义规则说明 L(rL(r)是怎样以各种方式从是怎样以各种方式从 r r 的子的子正规式所表示的语言组合而成。正规式所表示的语言组合而成。正正规规式式用来表用来表示简单的语言，示简单的语言，叫做叫做正规集正规集。正规式是用于说明词法单元如正规式是用于说明词法单元如正规式是用于说明词法单元如正规式是用于说明词法单元如何对应到词法记号的模式。与何对应到词法记号的模式

10、。与何对应到词法记号的模式。与何对应到词法记号的模式。与非形式化的描述相比，正规式非形式化的描述相比，正规式非形式化的描述相比，正规式非形式化的描述相比，正规式更具形式化，更加精确。更具形式化，更加精确。更具形式化，更加精确。更具形式化，更加精确。2022/12/2122/282.2 词法记号的描述与识别词法记号的描述与识别 2.2.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是正规式

11、是正规式(r r)*(L L(r r)*r r是正规式是正规式(r r)L L(r r)r r是正规式是正规式运算符的优先级：运算符的优先级：*连接运算连接运算|2022/12/2123/282.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 aaaa|abab|baba|bbbb aaaa,abab,baba,bbbb a a*由字母由字母a a构成的所有串集构成的所有串集(a a|b b)*由由a a和和b b构成的所有串集构成的所有串集2022/12

12、/2124/282.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 上的正规式上的正规式这样就保证了，每个名这样就保证了，每个名这样就保证了，每个名这样就保证了，每个名字对应的正规式中使用字对应的正规式中使用字对应的正规式中使用字对应的正规式中使用的各种符号已经在前面的各种符号已经在前面的各种符号已经在前面的各种符号已经在

13、前面定义了，从而可以避免定义了，从而可以避免定义了，从而可以避免定义了，从而可以避免递归定义的情况。递归定义的情况。递归定义的情况。递归定义的情况。2022/12/2125/282.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子 Pascal语言的标识符集合letter A|B|Z|a|b|zdigit 0|1|9id letter(letter|digit)*2022/12/2126/282.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子PascalPascal无符号数集合，例无符号数集合，例19461946,11.2811.28,63.663.6E8E8,1.9

14、91.99E E 6 6 digitdigit 0 0|1|9|1|9digitsdigits digitdigit digitdigit*optional_fractionoptional_fraction .digitsdigits|optional_exponentoptional_exponent (E(+|(E(+|)digits)|)digits)|numnumdigitsdigits optional_fractionoptional_fraction optional_exponentoptional_exponent简化表示简化表示numnum digitdigit+(.di

15、gitdigit+)?(E(+|)?(E(+|)?digit)?digit+)?)?简化规则：简化规则：简化规则：简化规则：(1)r+=rr*(2)r?=r|(3)a-z=a|b|c|z2022/12/2127/282.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子while while while whiledo do do doreloprelop|=|=|=|=|=|=id id letter(letter|digit)letter(letter|digit)*num num digit digit+(.digitdigit+)?(E(+|)?(E(+|)?digit)?digit+)?)?delimdelim blankblank|tabtab|newlinenewline wsws delimdelim+前面所提前面所提前面所提前面所提到的词法到的词法到的词法到的词法记号，实记号，实记号，实记号，实际上就是际上就是际上就是际上就是正规式的正规式的正规式的正规式的名字！名字！名字！名字！2022/12/2128/28习题习题作业作业习题习题2.3