第03讲-词法分析-II.ppt
本章内容本章内容词法分析器：把构成源程序的字符流翻译成记词法分析器：把构成源程序的字符流翻译成记词法分析器：把构成源程序的字符流翻译成记词法分析器：把构成源程序的字符流翻译成记号流，号流，号流，号流，还完成和用户接口的一些任务还完成和用户接口的一些任务还完成和用户接口的一些任务还完成和用户接口的一些任务介绍正规式、状态转换图和有限自动机概念介绍正规式、状态转换图和有限自动机概念介绍正规式、状态转换图和有限自动机概念介绍正规式、状态转换图和有限自动机概念LexLex与词法分析器的自动生成与词法分析器的自动生成与词法分析器的自动生成与词法分析器的自动生成词法分析器词法分析器词法分析器词法分析器语法分析器语法分析器语法分析器语法分析器符号表符号表符号表符号表记号记号记号记号取下一个记号取下一个记号取下一个记号取下一个记号源程序源程序源程序源程序第二章 词法分析1回顾词法分析概念词法记号的描述2词法单元、词法记号L1L1:x x=IDIDCOLONCOLONIDIDASSGNASSGNy2y2+1212;IDIDPLUSPLUSINTINTSEMI-COLSEMI-COL词法单元词法单元又称单词，是编程语言中合法的字符串又称单词，是编程语言中合法的字符串又称单词，是编程语言中合法的字符串又称单词，是编程语言中合法的字符串词法记号词法记号满足某种规则的词法单元，采用同一种记法满足某种规则的词法单元，采用同一种记法满足某种规则的词法单元，采用同一种记法满足某种规则的词法单元，采用同一种记法词法记号。词法记号。词法记号。词法记号。3词法单元词法单元 词法记号词法记号词法单元词法单元词法单元词法单元词法记号词法记号词法记号词法记号模式模式模式模式用模式语言描述用模式语言描述用模式语言描述用模式语言描述正规式，是描述词法记号的一种最为常见的模式语言正规式，是描述词法记号的一种最为常见的模式语言正规式，是描述词法记号的一种最为常见的模式语言正规式，是描述词法记号的一种最为常见的模式语言4字母字母字母字母组合组合组合组合串串串串语言语言语言语言集合集合集合集合集合集合集合集合字母表字母表字母表字母表长度长度长度长度为为为为0 0的空的空的空的空串串串串2.2 词法记号的描述与识别长度的长度的长度的长度的表示表示表示表示|a|a|2.2.1 串和语言串和语言字母表字母表字母表字母表：符号的有限集合，：符号的有限集合，：符号的有限集合，：符号的有限集合，例：例：例：例：=0,10,10,10,1串：串：串：串：符号的有穷序列，例：符号的有穷序列，例：符号的有穷序列，例：符号的有穷序列，例：0110,0110,0110,0110,语言语言语言语言：字母表上的一个串集：字母表上的一个串集：字母表上的一个串集：字母表上的一个串集 ,0,00,000,0,00,000,0,00,000,0,00,000,52.2 词法记号的描述与识别2.2.1 串和语言串和语言串的运算串的运算连接连接连接连接xyxy，s s =s s=s s 积积积积（指数）（指数）（指数）（指数）s s0 0为为为为 ，s si i为为为为s si i-1-1s s（i i 0 0）6语言的运算语言的运算和：和：和：和：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 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 词法记号的描述与识别L L =L L0 L L+7本讲纲要正规式词法记号的识别有限自动机定义DFA构建方法8正规式正规式，又称正则表达式，Regular Expression92.2.2 2.2.2 正规式正规式正规式：按照一组定义规则，由较简单的正规式正规式：按照一组定义规则，由较简单的正规式正规式：按照一组定义规则，由较简单的正规式正规式：按照一组定义规则，由较简单的正规式构成的，每个正规式构成的，每个正规式构成的，每个正规式构成的，每个正规式 r r r r 表示一个语言表示一个语言表示一个语言表示一个语言 L(rL(rL(rL(r).).).).定定定定义规则说明义规则说明义规则说明义规则说明 L(rL(rL(rL(r)是怎样以各种方式从是怎样以各种方式从是怎样以各种方式从是怎样以各种方式从 r r r r 的子的子的子的子正规式所表示的语言组合而成。正规式所表示的语言组合而成。正规式所表示的语言组合而成。正规式所表示的语言组合而成。正规式正规式正规式正规式用来表示简单的语言，叫做用来表示简单的语言，叫做用来表示简单的语言，叫做用来表示简单的语言，叫做正规集正规集正规集正规集。正规式是用于说明正规式是用于说明正规式是用于说明正规式是用于说明词法单元如词法单元如词法单元如词法单元如何对应到词法记号的模式何对应到词法记号的模式何对应到词法记号的模式何对应到词法记号的模式。与。与。与。与非形式化的描述相比，正规式非形式化的描述相比，正规式非形式化的描述相比，正规式非形式化的描述相比，正规式更具形式化，更加精确。更具形式化，更加精确。更具形式化，更加精确。更具形式化，更加精确。2.2 词法记号的描述与识别102.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是正规式是正规式是正规式是正规式(r r)*(L L(r r)*r r是正规式是正规式是正规式是正规式(r r)L L(r r)r r是正规式是正规式是正规式是正规式运算符的优先级：运算符的优先级：运算符的优先级：运算符的优先级：*连接运算连接运算连接运算连接运算|(a)(b)a)(b)a)(b)a)(b)*)|(c)|(c)|(c)|(c)可以写成可以写成可以写成可以写成abababab*|c|c|c|c2.2 词法记号的描述与识别定义字母表定义字母表 上上正规式的规则正规式的规则11正规式的例子正规式的例子 =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构成的所有串构成的所有串构成的所有串构成的所有串集集集集复杂的例子复杂的例子(00|11|(01|10)(00|11)(01|10)句子：句子：010011010000100000101110012.2 词法记号的描述与识别122.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 上的正规式上的正规式上的正规式上的正规式保证：每个名字对应保证：每个名字对应保证：每个名字对应保证：每个名字对应的正规式中使用的各的正规式中使用的各的正规式中使用的各的正规式中使用的各种符号已经在前面定种符号已经在前面定种符号已经在前面定种符号已经在前面定义了，从而可以避免义了，从而可以避免义了，从而可以避免义了，从而可以避免递归定义的情况。递归定义的情况。递归定义的情况。递归定义的情况。2.2 词法记号的描述与识别13Pascal里面的标识符模式正规式表示 letter A|B|Z|a|b|zdigit 0|1|9id letter(letter|digit)*怎么用语言来描述怎么用语言来描述怎么用语言来描述怎么用语言来描述PascalPascal的标识符模式？的标识符模式？的标识符模式？的标识符模式？PascalPascal标识符模式的自然语言描述：标识符模式的自然语言描述：标识符模式的自然语言描述：标识符模式的自然语言描述：首字符必须是字母，由字母或数字组成的字符串首字符必须是字母，由字母或数字组成的字符串首字符必须是字母，由字母或数字组成的字符串首字符必须是字母，由字母或数字组成的字符串14C语言的标识符模式模式的非形式描述首字符必须是首字符必须是_ _或者字母，由或者字母，由_ _、字母或数字组成、字母或数字组成的字符串的字符串请仿照Pascal标识符的例子，写出C语言的标识符的正规式表示15正规定义的例子正规定义的例子C语言的标识符是字母、数字和下划线组成的串语言的标识符是字母、数字和下划线组成的串 letter_ A|B|Z|a|b|z|_ digit 0|1|9id letter_(letter_|digit)*C语言的标识符模式162.2 词法记号的描述与识别简化规则：简化规则：简化规则：简化规则：(1)r+=rr*(2)r?=r|(3)a-z=a|b|c|z正规定义的例子正规定义的例子PascalPascal无符号数集合，例无符号数集合，例无符号数集合，例无符号数集合，例19461946,11.2811.28,63.663.6E8E8,1.991.99E E 6 6 digitdigit 0 0|1|9|1|9digitsdigits digit digit digitdigit*optional_fractionoptional_fraction .digitsdigits|optional_exponentoptional_exponent (E(+|(E(+|)digits)|)digits)|numnumdigitsdigits optional_fractionoptional_fraction optional_exponentoptional_exponent简化表示简化表示简化表示简化表示num num digit digit+(.digit(.digit+)?(E(+|)?(E(+|)?digit)?digit+)?)?17while while while whiledo do do doreloprelop|=|=|=|=|=|=id id letter(letter|digit)letter(letter|digit)*num num digit digit+(.digit(.digit+)?(E(+|)?(E(+|)?digit)?digit+)?)?delimdelim blank|tab|newline blank|tab|newline wsws delimdelim+前面所提前面所提前面所提前面所提到的词法到的词法到的词法到的词法记号，实记号，实记号，实记号，实际上就是际上就是际上就是际上就是正规式的正规式的正规式的正规式的名字！名字！名字！名字！2.2 词法记号的描述与识别正规定义的例子正规定义的例子18词法分析器词法分析器记号（记号（token）流）流源代码源代码词法分析器工作原理：词法分析器工作原理：词法分析器工作原理：词法分析器工作原理：源程序源程序字符流字符流顺序顺序顺序顺序组合组合组合组合词法词法单元单元词法词法记号记号模式模式模式模式非形式非形式化描述化描述形式化形式化描述描述正规式正规式字母字母组合组合组合组合串串语言语言集合集合集合集合集合集合集合集合字母表字母表名名字字小 结19本讲纲要正规式词法记号的识别有限自动机定义DFA构建方法20词法记号的识别词法记号的识别词法记号的识别等同于对字符串的匹配过程等同于对字符串的匹配过程这个匹配过程可以基于有限状态机来完成这个匹配过程可以基于有限状态机来完成21 简单的正则式d-a0 01 1a a22 正则式d-ab0 02 2a a1 1b b23 正则式d-a|b0 01 1a ab b24正规式d-a*0 0a a25自动机的定义正规式d-a?字符a出现一次或者0次0 01 1a a26练习正规式d-a(a|b)*请画出它的状态转换图0 01 1a aa ab b27051624837return(relop,LE)return(relop,NE)return(relop,LT)return(relop,GE)return(relop,GT)return(relop,EQ)开始开始=*otherotherreloprelop|=|=|=词法记号的描述与识别2.2.4 转换图转换图 关系算符的转换图关系算符的转换图关系算符的转换图关系算符的转换图28标识符和关键字的转换图标识符和关键字的转换图91011开始开始letterother*letter或或digitreturn(install_id()id letter(letter|digit)*1 1、检查关键字表，如果在表中发现该词法单元则返回、检查关键字表，如果在表中发现该词法单元则返回、检查关键字表，如果在表中发现该词法单元则返回、检查关键字表，如果在表中发现该词法单元则返回相应的记号并退出，否则转向相应的记号并退出，否则转向相应的记号并退出，否则转向相应的记号并退出，否则转向2 22 2、该词法单元是标识符，在符号表中查找，若找到该、该词法单元是标识符，在符号表中查找，若找到该、该词法单元是标识符，在符号表中查找，若找到该、该词法单元是标识符，在符号表中查找，若找到该词法单元则返回该条目的指针并退出，否则执行词法单元则返回该条目的指针并退出，否则执行词法单元则返回该条目的指针并退出，否则执行词法单元则返回该条目的指针并退出，否则执行3 33 3、在符号表中建立一个新的条目，把该词法单元填入，、在符号表中建立一个新的条目，把该词法单元填入，、在符号表中建立一个新的条目，把该词法单元填入，、在符号表中建立一个新的条目，把该词法单元填入，并返回此新条目的指针并返回此新条目的指针并返回此新条目的指针并返回此新条目的指针词法记号的描述与识别29无符号数的转换图无符号数的转换图开始开始1912131415161718digitdigitdigitdigitdigitdigitother.E+/Edigitotherotherreturn(install_num()*num digit+(.digit+)?(E(+|)?digit+)?词法记号的描述与识别30空白空白的转换图的转换图delim blank|tab|newline ws delim+2122开始开始delimother*delim20词法记号的描述与识别31习题作业习题2.332
