编译原理及实践-第2章 词法分析.ppt

《编译原理及实践-第2章 词法分析.ppt》由会员分享，可在线阅读，更多相关《编译原理及实践-第2章 词法分析.ppt（149页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2 2章章 词法分析词法分析2.1 词法分析器的作用词法分析器的作用2.2 正则表达式正则表达式 2.3 有穷自动机有穷自动机2.4 从正则表达式到从正则表达式到DFA 2.5 用代码实现有穷自动机用代码实现有穷自动机2.6 利用利用lex自动生成词法分析自动生成词法分析程序程序单词的描单词的描述工具述工具单词单词的识的识别系统别系统设计和设计和实现词实现词法分析法分析程序程序12.1 2.1 词法分析器的作用词法分析器的作用 词法分析器词法分析器(词法分析程序词法分析程序)的任务的任务：从源从源代码中读取输入字符，产生单词序列代码中读取输入字符，产生单词序列(生生成独立的有意义的逻辑单元

2、称作单词成独立的有意义的逻辑单元称作单词(token)，提交给语法分析使用。，提交给语法分析使用。2任务任务：逐个读入源程序字符并按照：逐个读入源程序字符并按照构词规则构词规则切分切分成一系列单词。单词是语言中具有独立意义的最成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符小单位，包括保留字、标识符、运算符、标点符号和常量等。号和常量等。w识别出源程序中的单词；识别出源程序中的单词；w删除无用的空白字符及注释（空格、回车删除无用的空白字符及注释（空格、回车 等），这些信等），这些信息仅增加了源程序的可读性，便于程序员阅读和维护程息仅增加了源程序的可读性，便于

3、程序员阅读和维护程序，而对于语法分析是完全无用的。序，而对于语法分析是完全无用的。w进行词法检查，能够检测出输入中不能形成进行词法检查，能够检测出输入中不能形成源语言任何源语言任何单词的错误字符串单词的错误字符串。3The big elephant ate the peanut.The big elephant ate the peanut.big 词法分析的结果：词法分析的结果：4 token表示的字符串表示的字符串（串值或词义串值或词义）：）：if,y,3,then,x,=,0 token的的类型（词法）类型（词法）：关键字（关键字（if,else,for,int,return）操作符（操

4、作符（+,-,）数字数字 （3,45,）标识符（标识符（x,y,name）补充：补充：typedef enum 类似宏类似宏 IF,THEN,PLUS,MINUS,NUM,ID TokenType;词法分析器的输出词法分析器的输出:token序列序列5if y3 then x=0 LT,词法分析器词法分析器例如：例如：C源代码源代码:if y3 then x=0,词词法分析器的输出是？法分析器的输出是？类型类型 串值串值例例 ID 表示表示 标识符标识符 类型类型 x 表示表示 具体的标识符串具体的标识符串6定义逻辑项定义逻辑项token的数据类型的数据类型：typedef struct un

5、ion char*stringval;int numval;attribute;TokenRecord;TokenType tokenval;Token类型类型Token词义词义补充：补充：union数据类型数据类型7词法分析程序的函数接口：词法分析程序的函数接口：TokenRecord getToken(void);TokengetToken()源程序源程序词法分析程序词法分析程序语法分析程序语法分析程序符号表符号表8第第2 2章章 词法分析词法分析2.1 词法分析器的作用词法分析器的作用2.2 正则表达式正则表达式 2.3 有穷自动机有穷自动机2.4 从正则表达式到从正则表达式到DFA 2

6、.5 用代码实现有穷自动机用代码实现有穷自动机2.6 利用利用lex自动生成词法分析自动生成词法分析程序程序记号的描记号的描述工具述工具记号的识记号的识别系统别系统设计和设计和实现词实现词法分析法分析程序程序9正则表达式：正则表达式：对自动生成词法分析程序而言，正则表达对自动生成词法分析程序而言，正则表达 式也是非常有用的工具。式也是非常有用的工具。所谓所谓正则表达式正则表达式就是用特定的就是用特定的运算符运算符及及运算运算对象对象按某种规则构造的表达式。按某种规则构造的表达式。例如：例如：a*匹配匹配 空串空串,a,aa,aaa,其表示的是一个集合，记为其表示的是一个集合，记为L(a*)。正

7、则表达式用来描述单词正则表达式用来描述单词结构结构(定义单词定义单词)。102.2.1 基本概念和术语基本概念和术语2.2.2 正则表达式的定义正则表达式的定义2.2.3 正则表达式基本等价关系正则表达式基本等价关系2.2.4 正则表达式的扩展正则表达式的扩展2.2.5 单词的正则表达式举例单词的正则表达式举例2.22.2正则表达式正则表达式 单词的描述工具单词的描述工具112.2.1 2.2.1 基本概念和术语基本概念和术语字母表（符号表、符号集）字母表（符号表、符号集）由若干元素由若干元素（符号、字母）组成的有限非空集合。（符号、字母）组成的有限非空集合。不同的语言可以有不同的字母表，例如

8、不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点汉语的字母表中包括汉字、数字及标点符号等。符号等。12 符号串符号串 由字母表中的符号组成的任何有由字母表中的符号组成的任何有穷序列称为符号串穷序列称为符号串:例如例如00，11，10 是字母表是字母表 =0，1上的符号串。上的符号串。字母表字母表A=a，b，c上的符号串有：上的符号串有：a，b，c，ab，aaca等。等。在符号串中，符号的顺序是很重要的，符在符号串中，符号的顺序是很重要的，符号串号串ab就不同于就不同于ba，abca和和aabc也不同。也不同。13符号串的长度符号串的长度 如果某符号串如果某符号串x x中有中

9、有m m个符号，个符号，则称其长度为则称其长度为m m，表示为表示为x x=m=m，如如001110001110的长度是的长度是6 6。空符号串空符号串，即不包含任何符号的符号串，用，即不包含任何符号的符号串，用表示，其长度为表示，其长度为0 0，即，即=0=0。14w符号串的连接符号串的连接：设：设x和和y是符号串，它们的连是符号串，它们的连接接xy是把是把y的符号写在的符号写在x的符号之后得到的符的符号之后得到的符号串。号串。例如例如 x=ST，y=abu，则它们的连接则它们的连接 xy=STabu，x=2，y=3，xy=5由于由于的含义，显然有的含义，显然有x=x=x。w符号串的方幂符号

10、串的方幂：符号串自身连接符号串自身连接n次得到的符次得到的符号串号串xn 定义为定义为 xxx；n个个x x1=x,x2=xx且且x0=15例；若例；若x=x=abab 则则:x x0 0=x x1 1=abab x x2 2=abababab x x3 3=abababababab x xn n =xx=xxn-1 n-1=x=xn-1n-1x (n0)x (n0)16符号串集合符号串集合：若集合若集合A A中所有元素都是中所有元素都是某字母表某字母表 上的符号串，则称上的符号串，则称A A为字母表为字母表 上的符号串集合。上的符号串集合。符号串集合的和与积符号串集合的和与积设设A A，B

11、B为两个符号串集合，定义为两个符号串集合，定义和和 A A+B(+B(或或A A B)B)=w|w=w|w A A，或或w w BB积积 AB=AB=xy|xxy|x A,yA,y B B 17v若用若用表示空集，则有：表示空集，则有：A+=+A=A A=A=A=A =Av 例：若集合例：若集合A=ab,cde ，集合集合B=B=0,1，则则AB=ab1,ab0,cde0,cde1；18的闭包：的闭包：用用*表示表示 上的一切符号串（包括上的一切符号串（包括）组成的集合，组成的集合，*称为称为的闭包的闭包。例如例如：=a,ba,b *=,a,b,aa,ab,ba,bb,aaa,aab,a,b,

12、aa,ab,ba,bb,aaa,aab,的正闭包：的正闭包：上上除除外的所有符号串组成的外的所有符号串组成的集合记为集合记为+，+称为称为的正闭包的正闭包。例如例如：=a,ba,b +=a,b,aa,ab,ba,bb,aaa,aaba,b,aa,ab,ba,bb,aaa,aab,192.2.1 基本概念和术语基本概念和术语2.2.2 正则表达式的定义正则表达式的定义2.2.3 正则表达式基本等价关系正则表达式基本等价关系2.2.4 正则表达式的扩展正则表达式的扩展2.2.5 单词的正则表达式举例单词的正则表达式举例2.22.2正则表达式正则表达式20w正则表达式正则表达式就是用特定的就是用特定

13、的运算符运算符及及运算对象运算对象按某按某种规则构造的表达式。种规则构造的表达式。w每个正则表达式代表一个每个正则表达式代表一个字符串的集合字符串的集合，我们把，我们把其称为正则集。其称为正则集。w语言语言(Language)是字符串组成的集合，我们也可是字符串组成的集合，我们也可以把正则表达式表示的以把正则表达式表示的正则集正则集称为该正则表达式称为该正则表达式表示的表示的语言语言。2.2.22.2.2正则表达式的定义正则表达式的定义21w正则表达式和它所表示的正则集正则表达式和它所表示的正则集(字符串的集字符串的集合合)的递归定义如下的递归定义如下：设有字母表为设有字母表为，辅助字母表辅助

14、字母表=,|,.,*,(,)22(1)和和是是上的正则式，它们所表示的正则集上的正则式，它们所表示的正则集分别为分别为和和;(2)若若a，则则a是是上的正则式，它所表示的上的正则式，它所表示的正则集为正则集为a;(3)若若r和和s都是都是上的上的正则式正则式，且它们所表示，且它们所表示的的正则集正则集分别为分别为L(r)和和L(s)，那么：那么：23 r|s 是是正则式正则式，表示的，表示的正则集正则集为为 L(r|s)=L(r)L(s)；rs 是是正则式正则式，表示的，表示的正则集正则集为为 L(rs)=L(r)L(s)；r*是是正则式正则式，表示的，表示的正则集正则集为为(L(r)*。(r

15、)是是正则式正则式，表示的，表示的正则集正则集为为L(r)；“.”运算符运算符常省略常省略24(4)仅由有限次使用上述三步骤而定义的表仅由有限次使用上述三步骤而定义的表达式才是达式才是上的上的正则式正则式，仅由这些正则式所仅由这些正则式所表示的符号串集合才是表示的符号串集合才是上的上的正则集。正则集。注：算符的优先级为先注：算符的优先级为先“*”，再，再“.”最后最后“|”,都是左结合的，它们满足结合都是左结合的，它们满足结合律。律。25例例1，令，令=a，b，上的正则式和相应的正则集的例子：上的正则式和相应的正则集的例子：正则式正则式 正则集正则集aaa bab(a b)(a b)a a,b

16、abaa,ab,ba,bb ,a,aa,任意个任意个a的串的串(a b)a,b*即即,a,b,aa,ab,ba,bb,26例例2，正则式，正则式(a)|(b)*(c)它所表示的正则集为：它所表示的正则集为：根据运算符的优先级，上述正则式可以表示成根据运算符的优先级，上述正则式可以表示成 a|b*ca|b*c所表示的正则集为：字符串所表示的正则集为：字符串a以及由零个以及由零个或多个或多个b后跟一个后跟一个c 形成的字符串的集合形成的字符串的集合或写成或写成L(a|b*c)=a bnc|其中其中n是大于或等是大于或等于于0的整数的整数27给定一个正则式给定一个正则式,它唯一确定一个正则集；它唯一

17、确定一个正则集；反之不成立。即一个正则集可由多个不同反之不成立。即一个正则集可由多个不同的正则式表示。的正则式表示。aaaa a,aa,aaa,任意个任意个a的串的串a|aaa|aa a,aa,aaa,任意个任意个a的串的串例如：例如：28若若二个二个正则式正则式描述同一正则集，则称二式描述同一正则集，则称二式等价等价(相等相等)。判断下列正则表达式判断下列正则表达式e e1 1和和e e2 2是否等价？是否等价？e1=(a b)，e2=b ae1=b(ab),e2=(ba)be1=(a b),e2=(a b)29w正则表达式正则表达式是表示模式的一种重要方法，每是表示模式的一种重要方法，每个

18、模式匹配一个字符串集合个模式匹配一个字符串集合(即正则集即正则集)。w正则集正则集是正则表达式所定义的语言。是正则表达式所定义的语言。w正则表达式正则表达式可以作为字符串集合可以作为字符串集合(即正则集即正则集)的名字。的名字。302.2.1 基本概念和术语基本概念和术语2.2.2 正则表达式的定义正则表达式的定义2.2.3 正则表达式基本等价关系正则表达式基本等价关系2.2.4 正则表达式的扩展正则表达式的扩展2.2.5 单词的正则表达式举例单词的正则表达式举例2.22.2正则表达式正则表达式31A1.r|s=s|r A2.r|r=rA3.r|=rA4.(r|s)|t=r|(s|t)A5.(

19、rs)t=r(st)A6.r(s|t)=rs|rtA7.(s|t)r=sr|trA8.r=r=A9.r=r=rA10.r*=(|r)*=|rr*从集合论的角度去理解！从集合论的角度去理解！2.2.3 2.2.3 正则式基本等价关系正则式基本等价关系322.2.1 基本概念和术语基本概念和术语2.2.2 正则表达式的定义正则表达式的定义2.2.3 正则表达式基本等价关系正则表达式基本等价关系2.2.4 正则表达式的扩展正则表达式的扩展2.2.5 单词的正则表达式举例单词的正则表达式举例2.22.2正则表达式正则表达式332.2.4 2.2.4 正则表达式的扩展正则表达式的扩展w1.一个或多个重复

20、（一个或多个重复（+，*）：）：假设假设r是正则表达式是正则表达式，r的重复是通过使用标准的闭包运算来描述，的重复是通过使用标准的闭包运算来描述，写作写作r*。它允许它允许r被重复被重复0次或更多次次或更多次。用用r+表示表示r 被重复被重复1次或更多次次或更多次。因此有：。因此有：(0|1)+=(0|1)(0|1)*342.任意字符（任意字符（.）:句点句点“.”表示可以匹配除换行符之外的任意单个符。表示可以匹配除换行符之外的任意单个符。利用这个字符就可为利用这个字符就可为所有包含至少一个所有包含至少一个b 的串的串写出写出一个一个正则表达式正则表达式，如下所示：，如下所示：.*b.*3.引

21、号引号“”，引号中的字符串表示文本字符，引号中的字符串表示文本字符串本身。例如：串本身。例如：“.”表示要匹配表示要匹配.字符本字符本身。身。354.字符字符范围范围：表示法表示法a|b|z 表示所有小写字母；表示所有小写字母；0|1|9表示表示0到到9间的所有数字；间的所有数字；常见的表示法是利用常见的表示法是利用方括号方括号和和一个连字符一个连字符，如，如a-z是指所有小写字母，是指所有小写字母，0-9则指数字。则指数字。第二种表示法还可用作表示单个的解，第二种表示法还可用作表示单个的解，a|b|c可写成可写成abc，它还可用于多个范围，它还可用于多个范围，如如 a-z A-Z 代表所有的

22、大小写字母。代表所有的大小写字母。365.正则表达式的正则表达式的名字名字为较长的正则表达式提供一个简化的名字很有用为较长的正则表达式提供一个简化的名字很有用处，这样就不用每次使用正则表达式书写较长的处，这样就不用每次使用正则表达式书写较长的表达式本身了；表达式本身了；如要写一个正则表达式如要写一个正则表达式:a-z A-Z (a-z A-Z 0-9)它定义的正则集为：以字母打头后跟若干字母或数它定义的正则集为：以字母打头后跟若干字母或数字组成的符号串的集合字组成的符号串的集合。37上述正则式上述正则式定义的是程序设计语言定义的是程序设计语言标识符标识符的的词法词法规则规则，通过为，通过为正则

23、表达式提供一个简化的名字，正则表达式提供一个简化的名字，上述正则表达式可写作：上述正则表达式可写作：letter=a-z A-Z digit=0-9 identify=letter(letter digit)38例：写出正则表达式例：写出正则表达式signedNatnat=0-9+signedNat=nat|+nat|-nat对应的正则集？对应的正则集？396.可选的子表达式（可选的子表达式（？）：）：w如果在特定的串中包括既可能出现又可能不出现如果在特定的串中包括既可能出现又可能不出现的可选部分。例如，的可选部分。例如，nat=0-9+signedNat=nat|+nat|-natw我们可以

24、引入问号我们可以引入问号?来表示来表示r 匹配的串是可选的；上面的匹配的串是可选的；上面的例子可写成：例子可写成：nat=0-9+signedNat=(+|-)？nat402.2.1 基本概念和术语基本概念和术语2.2.2 正则表达式的定义正则表达式的定义2.2.3 正则表达式基本等价关系正则表达式基本等价关系2.2.4 正则表达式的扩展正则表达式的扩展2.2.5 单词的正则表达式举例单词的正则表达式举例2.22.2正则表达式正则表达式412.2.5 2.2.5 单词的正则表达式举例单词的正则表达式举例每一种程序设计语言都有自己的字符集每一种程序设计语言都有自己的字符集(字母表字母表)。语言中

25、的各个语言中的各个单词单词或是或是 上的单个字符上的单个字符(如运算符、如运算符、分隔符等分隔符等)，或是，或是 上的字符串上的字符串(如常数、表示符和关如常数、表示符和关键字等键字等)。程序设计语言的程序设计语言的单词单词都能用都能用正则式正则式来定义来定义.由正则式由正则式描述的描述的单词类单词类也称为也称为正则集正则集。421.1.数：数：nat=0-9+signedNat=(+|-)?natnumber=signedNat(“.”nat)?(“E”signedNat)?例如：例如：3,3.5,2.71E-22.2.保留字：保留字：reserved=else|if|int|return|

26、void|while 433.3.标识符：标识符：letter=a-zA-Zdigit=0-9identifier=letter(letter|digit)*44 包含单词词法描述的包含单词词法描述的语言手册语言手册是编译是编译器的程序员最常见的。在下面的示例器的程序员最常见的。在下面的示例中，被匹配的串是汉语描述，其任务中，被匹配的串是汉语描述，其任务是将描述是将描述翻译为正则表达式翻译为正则表达式。451)在字母表在字母表 =a,b,c中，考虑在这个字中，考虑在这个字母表上的母表上的仅包括一个仅包括一个b 的所有串的集合的所有串的集合，这个集合所对应的正则表达式为：这个集合所对应的正则表达

27、式为：串串b、abc、abaca、baaaac、ccbaca和和ccccccb等都是满要求的等都是满要求的符号串。符号串。(a|c)*b(a|c)*462)在字母表在字母表 =a,b,c中，中，如果字符串集合是如果字符串集合是包括最包括最多一个多一个b 的所有串的所有串，则这个集合的正则表达式为：，则这个集合的正则表达式为：仅包括一个仅包括一个b 的串的集合对应的正则表达式的串的集合对应的正则表达式 (a|c)*b(a|c)*不包括不包括b 的串的集合对应的正则表达式的串的集合对应的正则表达式 (a|c)*故所求表达式为：故所求表达式为：(a|c)*|(a|c)*b(a|c)*或者为或者为:(

28、a|c)*(b|)(a|c)*473)在在字母表字母表 =a,b上串上串S的集合是由一个的集合是由一个b及及在其前后有相同数目的在其前后有相同数目的a 组成：组成：4)S=b,aba,aabaa,aaabaaa,.=anban|n0 正则表达式并不能描述这个集合正则表达式并不能描述这个集合，其原因在于重复运，其原因在于重复运算只有闭包运算算只有闭包运算*一种，它允许有任意次的重复。因此一种，它允许有任意次的重复。因此如要写出表达式如要写出表达式a*ba*，就不能保证在，就不能保证在b 前后的前后的a 的数的数量是否相等了。量是否相等了。48w并非用简单术语描述的所有串都可由并非用简单术语描述的

29、所有串都可由 正则表正则表达式产生，因此为了与其他集合相区分，作达式产生，因此为了与其他集合相区分，作为正则表达式描述的串集合称作正则集为正则表达式描述的串集合称作正则集(regular set)。w非正则集偶尔也作为串出现在需要由扫描程非正则集偶尔也作为串出现在需要由扫描程序识别的程序设计语言中。序识别的程序设计语言中。49第第2 2章章 词法分析词法分析2.1 词法分析器的作用词法分析器的作用2.2 正则表达式正则表达式 2.3 有穷自动机有穷自动机2.4 从正则表达式到从正则表达式到DFA 2.5 用代码实现有穷自动机用代码实现有穷自动机2.6 利用利用lex自动生成词法分析程序自动生成

30、词法分析程序记号的描记号的描述工具述工具记号的识记号的识别系统别系统设计和设计和实现词实现词法分析法分析程序程序502.3.1有穷自动机有穷自动机2.3.2确定性有穷自动机确定性有穷自动机(DFA)的定义的定义2.3.3非确定性有穷自动机非确定性有穷自动机(NFA)2.32.3有穷自动机有穷自动机512.3.1 2.3.1 有穷自动机有穷自动机有穷自动机有穷自动机(也称有限自动机也称有限自动机)作为一种数学模作为一种数学模型型，它能准确地识别正则集，即识别正则式所它能准确地识别正则集，即识别正则式所表示的集合。表示的集合。有穷自动机是有穷自动机是设计和实现词法分析器设计和实现词法分析器的有效的

31、有效工具，其直观图是一种状态转换图。工具，其直观图是一种状态转换图。引入有穷自动机理论，也是为词法分析程序引入有穷自动机理论，也是为词法分析程序的自动构造寻找方法和工具。的自动构造寻找方法和工具。52有穷自动机有穷自动机(Finite Automata,or finite-state machines)有穷自动机分为两类：有穷自动机分为两类：确定的有穷自动机确定的有穷自动机(Deterministic Finite Automata，DFA)。不确定的有穷自动机不确定的有穷自动机(Nondeterministic Finite Automata，NFA)。53在程序设计语言中，用正则式在程序设

32、计语言中，用正则式定义定义的标识符的标识符如下：如下：letter=a-zA-Zdigit=0-9identifier=letter(letter|digit)*该正则式匹配的标识符是以一个字母开头且该正则式匹配的标识符是以一个字母开头且其后为任意字母、数字序列形成的字符串。其后为任意字母、数字序列形成的字符串。5412letterletterdigit标识符的有穷自动机标识符的有穷自动机变量变量xtempxtemp 识别为标识符的过程可表示为：识别为标识符的过程可表示为：1x2t2e2m2p2 标识符模式的标识符模式的识别识别过程：过程：552.3.1有穷自动机的引入有穷自动机的引入2.3.

33、2确定性有穷自动机确定性有穷自动机(DFA)的定义的定义2.3.3非确定性有穷自动机非确定性有穷自动机(NFA)2.32.3有穷自动机有穷自动机562.3.22.3.2确定性有穷自动机（确定性有穷自动机（DFADFA）的定义的定义DFA(DFA(确定性有穷自动机确定性有穷自动机)有五个部分组成：有五个部分组成：(1)(1)有限个输入符号组成的字母表有限个输入符号组成的字母表,记作记作;(2)(2)有限个状态的集合有限个状态的集合,记作记作S S;(3)(3)转换函数转换函数T T T:T:S SS S 即：即：T(s,c)=sT(s,c)=s 其中其中s s S S，s s S S，c c上述

34、转换函数表示：若当前状态为上述转换函数表示：若当前状态为s s,且当前识别的输且当前识别的输入符号为入符号为c c,识别识别c c后进入的下一个状态为后进入的下一个状态为s s 。57(4)(4)初始状态初始状态s s0 0 S S;指示识别符号串的开始状态指示识别符号串的开始状态;(5)(5)若干个若干个识别符号串的识别符号串的接受状态接受状态(或称为终止状或称为终止状 态态)的集合的集合 A A S S;(由上述五个要素组成的五元式由上述五个要素组成的五元式M=(S;M=(S;T;s;T;s0 0;A);A)称为一个称为一个确定的有限自动机确定的有限自动机(DFADFA:D Determi

35、nistic eterministic F Finite inite A Automatautomata)。58DFA MDFA M=（ss1 1,s,s2 2,s,s3 3,s,s4 4,a,b,T,s,a,b,T,s1 1,s,s4 4）其中其中转换函数转换函数T T定定义为：义为：T(s1,a)=s2 T(s3,a)=s2 T(s1,b)=s3 T(s3,b)=s4T(s2,a)=s4 T(s4,a)=s4T(s2,b)=s3 T(s4,b)=s4一个一个DFA DFA 的例子：的例子：有限个状有限个状态的集合态的集合s字母表字母表 初始状态初始状态接受状接受状态的集合态的集合A A59

36、状态转换图状态转换图一个一个DFADFA可以表示成一个状态图可以表示成一个状态图(或称或称状状态转换图态转换图)。状态转换图是由一组矢线连。状态转换图是由一组矢线连结的有限个结点所组成的有向图。结的有限个结点所组成的有向图。例如：例如：s0 0s2 20s1 11060假定假定DFA MDFA M含有含有m m个状态，那么这个状态图个状态，那么这个状态图就含有就含有m m个结点；结点用小圆圈表示，个结点；结点用小圆圈表示，圆圈圆圈中标入状态的名字中标入状态的名字或编号。或编号。为了醒目起见，用为了醒目起见，用箭头指示初始状箭头指示初始状态，用双圆圈表示终止转态。态，用双圆圈表示终止转态。s结点

37、结点s0 0初始状态初始状态sn n接受状态接受状态61sas状态转换的图形表示状态转换的图形表示w若若 T(s,a)=s，则从状态结点则从状态结点s到状态结点到状态结点s画标记为画标记为a的矢线。的矢线。表示当词法分析器处于该矢线的结点所指示的表示当词法分析器处于该矢线的结点所指示的状态状态s时，可能要识别的输入字符为时，可能要识别的输入字符为a，而矢线而矢线进入的结点进入的结点s则指示识别相应的输入字符则指示识别相应的输入字符a后后进入的下一个状态。进入的下一个状态。62 例：例：M=(s0 0,s1 1,s2 2,0,1,T,s0 0,s2 2)其中其中,T的定义如下：的定义如下：T(s

38、0 0,0)=s1 1 T(s1 1,0)=s1 1 T(s1 1,1)=s2 2 s0 0s2 20s1 110状态转换图举例状态转换图举例上述上述DFADFA对应的状态转换图：对应的状态转换图：63w在状态转换图中，从一个结点可以同时引出若干在状态转换图中，从一个结点可以同时引出若干条矢线到有向图中的其余结点条矢线到有向图中的其余结点(也可从一结点引矢也可从一结点引矢线到其自身线到其自身)；w每一矢线上均标记一个字符或字符类记号，表示每一矢线上均标记一个字符或字符类记号，表示当词法分析器处于该矢线的结点所指示的状态时，当词法分析器处于该矢线的结点所指示的状态时，可能要识别的输入字符，而矢线

39、进入的结点则指可能要识别的输入字符，而矢线进入的结点则指示识别相应的输入字符后进入的下一个状态。示识别相应的输入字符后进入的下一个状态。64DFADFA的接受集的接受集(即识别的字符串集合即识别的字符串集合)DFA识别的字符串识别的字符串c c1 1 c c2 2 c cn n的集合的集合满足如下满足如下条件：每个条件：每个c ci i ，且存在状态，且存在状态 s1=T(s0，c1),s2=T(s1，c2),sn=T(sn-1，cn),其中其中s0 是初态，是初态，sn 是终态。是终态。65s s0 0c c1 1s s1 1c c2 2s s2 2s sn-1n-1c cn ns sn n

40、c c3 3c cn-1n-1v字符串字符串c c1 1 c c2 2 c cn n若被若被DFA识别，则在状态识别，则在状态转换图中存在一条从初态到终态的有向路经，转换图中存在一条从初态到终态的有向路经，该路径上所有该路径上所有矢线上方的字符连接在一起即是矢线上方的字符连接在一起即是字符串字符串c c1 1 c c2 2 c cn nvDFA M识别的字符串的集合识别的字符串的集合 记作记作L(M)L(M)也称为由正则表达式也称为由正则表达式M生成的语言。生成的语言。66bs1s2s3s4abba|baa例：证明字符串序列例：证明字符串序列baabbaab被下图的被下图的DFADFA所接受。

41、所接受。任意列出它接受的另外两个输入串？任意列出它接受的另外两个输入串？任意列出它拒绝接受的两个输入串？任意列出它拒绝接受的两个输入串？67证明：由于存在证明：由于存在T(sT(s1 1,b,b）=s=s3 3T(sT(s3 3,a,a）=s=s2 2T(sT(s2 2,a,a）=s=s4 4T(sT(s4 4,b,b）=s=s4 4s s4 4属于终态，得证。属于终态，得证。68(1).状态转换图中的状态转换图中的状态状态可以使用可以使用任何标识任何标识系统系统来标识来标识(2).状态转换图中的状态转换图中的转换转换可以使用可以使用字符集合字符集合的名字的名字标出标出关于关于DFADFA的状

42、态转换图的的状态转换图的2 2点说明点说明startin_idletterletterdigit6912digitdigit例例1：自然数的集合自然数的集合被下图所示的被下图所示的DFA接受。接受。注：注：digit=0-9DFADFA的示例的示例70例例2：字母表字母表 =a,b,c上上有且仅有一个有且仅有一个b构成构成的字符串集合的字符串集合被下图所示的被下图所示的DFA接受。接受。12bnotbnotb注：注：notb=a,c71例例3：字母表字母表 =a,b,c上上包含最多一个包含最多一个b构构成的字符串的集合成的字符串的集合被下图所示的被下图所示的DFA接受。接受。2bnotbnot

43、b1注：注：notb=a,c72例例4：有：有C风格注释的风格注释的DFA15/other12*3*4*/other2注：注：other1other1表示除表示除*之外的所有字符的集合的名字；之外的所有字符的集合的名字；other2 other2表示除表示除*,/*,/之外的所有字符的集合的名字。之外的所有字符的集合的名字。732.3.1有穷自动机的引入有穷自动机的引入2.3.2确定性有穷自动机确定性有穷自动机(DFA)的定义的定义2.3.3非确定性有穷自动机非确定性有穷自动机(NFA)2.32.3有穷自动机有穷自动机742.3.32.3.3非确定性有穷自动机（非确定性有穷自动机（NFANFA

44、）下图是识别下图是识别=、,字符串的一个字符串的一个有穷自动机，对于输入符号有穷自动机，对于输入符号,在状态在状态0 0上上存在不止一种转换。存在不止一种转换。15302475w有穷自动机对于某个输入符号，如果有穷自动机对于某个输入符号，如果在同一个状态上存在不止一种转换，在同一个状态上存在不止一种转换，我们称该有穷自动机为不确定的有穷我们称该有穷自动机为不确定的有穷自动机。自动机。w在给出非确定性有穷自动机的定义之在给出非确定性有穷自动机的定义之前先引入前先引入-转换转换的概念。的概念。76-转换转换是无需考虑输入串就有可能发生的是无需考虑输入串就有可能发生的转换。它可看作是一个空串转换。它

45、可看作是一个空串 的的“匹配匹配”，-转换的图形表示为：转换的图形表示为：0 1-转换的引入转换的引入-转换转换可以清晰地描述出空串的匹配：可以清晰地描述出空串的匹配：0 1770 -转换转换可以通过添加一个新的初始状态来链接各个可以通过添加一个新的初始状态来链接各个自动机，从而将它们合并为一个自动机。自动机，从而将它们合并为一个自动机。将识别数字将识别数字和字符的两个和字符的两个DFADFA和并为一个非确定的有穷自动机：和并为一个非确定的有穷自动机：letterletterletterletterDONE2DONE2START2START2START1START1digitdigitdigi

46、tdigitDONE1DONE1780 123:=675=89=通过通过-转换将识别转换将识别:=:=、=、=的的DFADFA合并为：合并为：79NFA(非确定性有穷自动机非确定性有穷自动机)有五个部分组成：有五个部分组成：(1)(1)有限个输入符号组成的字母表有限个输入符号组成的字母表,记作记作;(2)(2)有限个状态的集合有限个状态的集合,记作记作S S;(3)(3)转换函数转换函数T T;T:T:S S()(S)(S),T(s,c)=s T(s,c)=sk1,s skm 表示若当前状态为表示若当前状态为s s S S,且要识别的输入符号为且要识别的输入符号为c c ,识别识别c c后进入

47、的状态是后进入的状态是S S的一个状态的一个状态子集子集ssk1,s skm ;2.3.22.3.2非确定性有穷自动机（非确定性有穷自动机（NFANFA）的定义的定义80(4)(4)初始状态初始状态s s0 0 S S;(5)(5)若干个接受状态的集合若干个接受状态的集合:A A S S 由上述五个要素组成的五元式由上述五个要素组成的五元式 M=(SM=(S；T T；s s0 0；A)A)称为一个非确定的有限自称为一个非确定的有限自动机动机 (NFANFA:Nondeterministicondeterministic F Finite inite A Automatautomata),),由

48、上述定义由上述定义可以看出，可以看出，DFADFA是是NFANFA的一个特例。的一个特例。81一个一个NFA NFA 的例子：的例子：NFA M=NFA M=（SS，P P，ZZ，00，11，T T，SS，ZZ）其中其中 T T（S S，0 0）=P;=P;T T（Z Z，0 0）=P;=P;T T（P P，1 1）=Z;T=Z;T（Z Z，1 1）=P;=P;T T（S S，1 1）=S=S，Z;Z;82NFANFA的状态转换图的状态转换图例：例：M=(,=,0，1，2，3，4，5,T,0,2，4，5)其中其中T的定义如下：的定义如下：T(0,)=4 15302483NFA M 的的接受集接

49、受集记作记作L(M)L(M)L(M)定义为定义为字符串字符串c c1 1c c2 2 c cn n的集合的集合，其中每个，其中每个c ci i ，且存在：，且存在：s s1 1 T(T(s s0 0,c c1 1),s s2 2 T(T(s s1 1,c c2 2),),s sn n T(T(s sn-1 n-1,c cn n),),其中其中s s0 0是初态，是初态，s sn n是终态集中的一个元素。是终态集中的一个元素。NFANFA的接受集的接受集84例：考虑下面的例：考虑下面的NFA图。图。231a aa ab b4 这个这个NFA接受集与正接受集与正则表达式则表达式ab+|ab*|b*

50、对应的对应的正则集相同。正则集相同。列举两个转换序列都可接受串列举两个转换序列都可接受串abb？1a2b4 2b41a3 4 2b4 2b485第第2 2章章 词法分析词法分析2.1 词法分析器的作用词法分析器的作用2.2 正则表达式正则表达式 2.3 有穷自动机有穷自动机2.4 从正则表达式到从正则表达式到DFA 2.5 用代码实现有穷自动机用代码实现有穷自动机2.6 利用利用lex自动生成词法分析自动生成词法分析程序程序记号的描记号的描述工具述工具记号的识记号的识别系统别系统设计和设计和实现词实现词法分析法分析程序程序862.42.4从正则表达式到从正则表达式到DFADFA正则表达式正则表