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

《编译原理及实践-第2章 词法分析》由会员分享，可在线阅读，更多相关《编译原理及实践-第2章 词法分析（149页珍藏版）》请在装配图网上搜索。

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

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

3、于程序员阅读和维护程序，而对于语法分析是完全无用的。序，而对于语法分析是完全无用的。w进行词法检查，能够检测出输入中不能形成进行词法检查，能够检测出输入中不能形成源语言任何源语言任何单词的错误字符串单词的错误字符串。4The big elephant ate the peanut.The big elephant ate the peanut.big 词法分析的结果：词法分析的结果：5 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序列序列6if y3 then x=0 LT,词法分析器词法分析器例如：例如：C源代码源代码:if y3 then x=0,词法词法分析器的输出是？分析器的输出是？类型类型 串值串值例例 ID ID 表示表示 标识符标识符 类型类型 x x 表示表示 具体的标识符串具体的标识符串7定义逻辑项定义逻辑项token的数据类型的数据类型：typedef str

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

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

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

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

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

10、=x。w符号串的方幂符号串的方幂：符号串自身连接符号串自身连接n次得到的符次得到的符号串号串xn 定义为定义为 xxx；n个个x x1=x,x2=xx且且x0=16例；若例；若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)17符号串集合符号串集合：若集合若集合A A中所有元素都是中所有元素都是某字母表某字母表 上的符号串，则称上的符号串，则称A A为字母表为字母表 上的符号串集合。上的符号串集合。符号串集合的和与积符号串集合

11、的和与积设设A A，B 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 18v若用若用表示空集，则有：表示空集，则有：A+=+A=A A=A=A=A =Av 例：若集合例：若集合A=ab,cde ，集合集合B=B=0,1，则则AB=ab1,ab0,cde0,cde1；19的闭包：的闭包：用用*表示表示 上的一切符号串（包括上的一切符号串（包括）组成的集合，组成的集合，*称为称为的闭包的闭包。例如例如：=a,ba,b *=,a,b,aa,ab,ba,bb,

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

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

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

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

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

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

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

19、=r|(s|t)A5.(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 正则式基本等价关系正则式基本等价关系332.2.1 基本概念和术语基本概念和术语2.2.2 正则表达式的定义正则表达式的定义2.2.3 正则表达式基本等价关系正则表达式基本等价关系2.2.4 正则表达式的扩展正则表达式的扩展2.2.5 单词的正则表达式举例单词的正则表达式举例2.22.2正则表达式正则表达式342.2.4 2.2.4 正则表达式的扩展正则表达式的

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

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

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

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

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

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

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

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

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

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

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

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

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

33、自动机的引入2.3.2确定性有穷自动机确定性有穷自动机(DFA)的定义的定义2.3.3非确定性有穷自动机非确定性有穷自动机(NFA)2.32.3有穷自动机有穷自动机572.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

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

35、A:D Deterministic eterministic F Finite inite A Automatautomata)。59DFA 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 s字母表字母表 初始状态初始状态接受状接受状

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

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

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

39、词法分析器处于该矢线的结点所指示的状态时，可能要识别的输入字符，而矢线进入的结点则指可能要识别的输入字符，而矢线进入的结点则指示识别相应的输入字符后进入的下一个状态。示识别相应的输入字符后进入的下一个状态。65DFADFA的接受集的接受集(即识别的字符串集合即识别的字符串集合)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 是终态。是终态。66s s0 0c c1 1s s1

40、 1c c2 2s s2 2s sn-1n-1c cn ns sn nc 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生成的语言。生成的语言。67bs1s2s3s4abba|baa例：证明字符串序列

41、例：证明字符串序列baabbaab被下图的被下图的DFADFA所接受。所接受。任意列出它接受的另外两个输入串？任意列出它接受的另外两个输入串？任意列出它拒绝接受的两个输入串？任意列出它拒绝接受的两个输入串？68证明：由于存在证明：由于存在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属于终态，得证。属于终态，得证。69(1).状态转换图中的状态转换图中的状态状态可以使用可以使用任何标识任何标识系统系统来标识来标识(2).状态转换图中的状态转换图中的转换转换可以使

42、用可以使用字符集合字符集合的名字的名字标出标出关于关于DFADFA的状态转换图的的状态转换图的2 2点说明点说明startin_idletterletterdigit7012digitdigit例例1：自然数的集合自然数的集合被下图所示的被下图所示的DFA接受。接受。注：注：digit=0-9DFADFA的示例的示例71例例2：字母表字母表 =a,b,c上上有且仅有一个有且仅有一个b构成构成的字符串集合的字符串集合被下图所示的被下图所示的DFA接受。接受。12bnotbnotb注：注：notb=a,c72例例3：字母表字母表 =a,b,c上上包含最多一个包含最多一个b构构成的字符串的集合成的字

43、符串的集合被下图所示的被下图所示的DFA接受。接受。2bnotbnotb1注：注：notb=a,c73例例4：有：有C风格注释的风格注释的DFA15/other12*3*4*/other2注：注：other1other1表示除表示除*之外的所有字符的集合的名字；之外的所有字符的集合的名字；other2 other2表示除表示除*,/,/之外的所有字符的集合的名字。之外的所有字符的集合的名字。742.3.1有穷自动机的引入有穷自动机的引入2.3.2确定性有穷自动机确定性有穷自动机(DFA)的定义的定义2.3.3非确定性有穷自动机非确定性有穷自动机(NFA)2.32.3有穷自动机有穷自动机752.

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

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

46、ONE2START2START2START1START1digitdigitdigitdigitDONE1DONE1790 123:=675=89=通过通过-转换将识别转换将识别:=:=、=、=的的DFADFA合并为：合并为：80NFA(非确定性有穷自动机非确定性有穷自动机)有五个部分组成：有五个部分组成：(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

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

48、stic F Finite inite A Automatautomata),),由上述定义由上述定义可以看出，可以看出，DFADFA是是NFANFA的一个的一个特例。特例。82一个一个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;83NFANFA的状态转换图的状态转换图例：例：M=(,=,0，1，2，3，4，5,T,0,2，4，5)其中其

49、中T的定义如下：的定义如下：T(0,)=4 15302484NFA M 的的接受集接受集记作记作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的接受集的接受集85例：考虑下面的例：考虑下面的NFA图。图。231a aa

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

51、分析程序程序872.42.4从正则表达式到从正则表达式到DFADFA正则表达式正则表达式DFA词法分析程序词法分析程序NFA正则式正则式是单词的一种描述工具。由于正则是单词的一种描述工具。由于正则式的简洁性，趋向于先用式的简洁性，趋向于先用正则式来描述单正则式来描述单词词，然后，然后构造等价的有限自动机构造等价的有限自动机。有限自动机有限自动机可以描述输入串被识别的过可以描述输入串被识别的过程，我们可以根据有限自动机程，我们可以根据有限自动机构造构造我们的我们的词法分析程序词法分析程序。88正则式正则式和和有限自动机有限自动机之间可以之间可以相互转换相互转换，也就是说它们之间存在着也就是说它们

52、之间存在着等价性等价性，即，即：1)1)对于对于上的上的NFA M，可以构造一个可以构造一个上的上的正则式正则式R，使得：使得：L(R)=L(M)2)2)对于对于上的每个正则式上的每个正则式R，可以构造一个可以构造一个上的上的NFA M，使得：使得：L(M)=L(R)892.4.1 从正则表达式到从正则表达式到NFA2.4.2 从从NFA 到到DFA2.4.3 将将DFA中的状态数最小化中的状态数最小化2.42.4从正则表达式到从正则表达式到DFADFA902.4.1 2.4.1 从正则表达式到从正则表达式到NFANFA从正则表达式到从正则表达式到NFA的转化方法按正则式的运算的转化方法按正则

53、式的运算指引构造过程，指引构造过程，将正则式分解为一系列子表达式，将正则式分解为一系列子表达式，然后将子表达式对应的然后将子表达式对应的NFA依次连接而成依次连接而成，正则正则式式R转化为转化为NFA M 的基本步骤：的基本步骤：91(b)对正则式对正则式，等价的等价的NFA为：为：0 0 1 1 (a)对正则式对正则式，等价的等价的NFA为：为：0 01 1(c)对正则式对正则式a，等价的等价的NFA为：为：0 0a a1 11.基本正则式转换为基本正则式转换为NFA M的方法：的方法：920 0R R1 12.复合正则式复合正则式R转换为转换为NFA M的方法：首先将复的方法：首先将复合正

54、则表达式表示成如下合正则表达式表示成如下拓广的状态转换图拓广的状态转换图，然后按照正则式的运算然后按照正则式的运算(以下以下(a),(b),(c),(d)四种四种情况情况)递归生成递归生成NFA M93(b)若若R=rs,则将则将 代之以代之以 0 01 1rsrs0 01 1r r2 2s s(a)若若R=r|s,则将则将 代之以代之以 0 01 1r|sr|s0 01 1r rs s94(c)若若R=r*,则将则将 代之以代之以 0 01 1r r*0 01 12 2 r r(d)正则式正则式R=（r）的的NFA同正则式同正则式 R=r的的NFA相同相同95例例1 1,设有正则表达式设有正

55、则表达式R=ab|a,试构造试构造NFA M，使使L(R)=L(M)。（1 1）0 0ab|aab|a1 1（2 2）0 0abab1 1a a（3 3）0 01 1a a2 2a ab b96例例2 2，设有正则表达式，设有正则表达式letter(letter|digit)letter(letter|digit)*,试构造与之等试构造与之等价的价的NFANFA。（1 1）0 0letter(letter|digit)letter(letter|digit)*1 1（2 2）0 0(letter|digit)(letter|digit)*1 1letterletter2 297（3 3）0 0

56、(letter|digit)(letter|digit)1 1letterletter2 2 3 3（4 4）0 0letterletter1 1letterletter2 2 3 3digitdigit982.4.1 从正则表达式到从正则表达式到NFA2.4.2 从从NFA 到到DFA2.4.3 将将DFA中的状态数最小化中的状态数最小化2.42.4从正则表达式到从正则表达式到DFADFA992.4.2 2.4.2 从从NFANFA 到到DFADFAw对任一对任一NFA M，总可构造一个总可构造一个DFA M，使使 L(M)=L(M)成立。这就是成立。这就是NFA与与DFA的等价性。的等价性

57、。w定理定理 对于字母表对于字母表 上的任一上的任一NFA M，必存在与必存在与M等等价的价的DFA M(即有即有 L(M)=L(M)成立成立)。在给出具体的构造算法之前先引入在给出具体的构造算法之前先引入状态状态s和状态和状态集合集合S的的-闭包的概念：闭包的概念：100（1）状态状态s的的-闭包闭包：定义为从：定义为从s出发可由一系出发可由一系列的零个或多个列的零个或多个-转换转换能达到能达到的状态的集合，的状态的集合，并将这个集合记为并将这个集合记为（2）状态集合）状态集合S的的-闭包闭包:定义为定义为S中各个状态中各个状态的的-闭包的并集闭包的并集s s-1011 14 42 2a a

58、 3 3 =1,2,4=1,2,41 1-=2=22 2-=3,2,4=3,2,43 3-=4=44 4-例：求下列状态机中状态例：求下列状态机中状态1 1、2 2、3 3、4 4的的-闭包：闭包：102从给定的从给定的NFA MNFA M构造构造DFA DFA 的原理是一次尝的原理是一次尝试所有的可能路径，避免试所有的可能路径，避免NFANFA的回溯的回溯()。M M-已知已知 NFA MNFA M=(S=(S；T T；s s0 0；A)A)设构造的与之等价的设构造的与之等价的M M-=（）S S-T T-s s0 0-A A-；DFADFAM M-DFADFA记作：记作：103M M-1.

59、计算计算M初始状态初始状态s s0 0的的-闭包，令其作为闭包，令其作为 的的初始状态初始状态：s s0 0-=;T T-S S-=s s0 0-由由NFANFA构造构造DFADFA的子集构造算法步骤如下：的子集构造算法步骤如下：1042.对对 中尚未标记的状态中尚未标记的状态 =si1,si2,sim:S S-s si i-s si i-(1)标记标记 ;(2)对于对于每个每个a及及 =si1,si2,sim 1)计算计算sa=t|满足满足 T(sij,a)=t j 1m，2)进一步计算进一步计算 sa的的 -闭包闭包 sa;-s si i-sa-S S-S S-S S-sa-(3)若若 ,

60、则令则令 =;T T-T T-T T-s si i-sa-(4)令令 =(,a)=;开始由标记的状态求新状态开始由标记的状态求新状态1053.重复步骤重复步骤2直到直到 中没有未标记的状态；中没有未标记的状态；S S-4.令令 =|A A A A-s si i-s si i-106例例1 1，考虑下图中的，考虑下图中的NFA,NFA,试构造与之等试构造与之等价的价的DFADFA。1 14 42 2a a 3 3 状态状态终结符终结符a a 1 1,2,4,2,4 3 3,2,4,2,4 3 3,2,4,2,4 3 3,2,4,2,41 10 0a aa a0 01 1107例例2 2，考虑下图

61、中的，考虑下图中的NFA,NFA,试构造与之等试构造与之等价的价的DFADFA。a ab b状态状态终结符终结符a ab b001,21,21,21,211110 01 1a a2 2a ab b3 35 54 43 34 45 5108例例3 3，考虑下图中的，考虑下图中的NFA,NFA,试构造与之等价试构造与之等价的的DFADFA。0 0letter|digitletter|digit1 1letterletter2 2 3 3状态状态终结符终结符letterletterdigitdigit002,3,12,3,12,3,12,3,1 3,13,13,13,13,13,13,13,13,1

62、3,1109letterletterletter|digitletter|digit4 45 56 6letter|digitletter|digit构造的与上述等价的构造的与上述等价的DFADFA如下图所示：如下图所示：1102.4.1 从正则表达式到从正则表达式到NFA2.4.2 从从NFA 到到DFA2.4.3 将将DFA中的状态数最小化中的状态数最小化2.42.4从正则表达式到从正则表达式到DFADFA1112.4.3 2.4.3 将将DFADFA中的状态数最小化中的状态数最小化结论结论：对于任何给定的：对于任何给定的DFADFA，都有一个都有一个含有含有最少状态等价的最少状态等价的D

63、FADFA，而且这个最小而且这个最小状态的状态的DFADFA在同构意义下是唯一的。在同构意义下是唯一的。状态集合的等价类状态集合的等价类：若两个状态：若两个状态s1,s2在在DFA中完成相同的识别功能，则可中完成相同的识别功能，则可将将s1,s2置于同一个等价类置于同一个等价类中。中。112对于任意对于任意给定的输入串给定的输入串w，若若DFA分别从分别从状态状态s1,s2出发，能够得到是否接受出发，能够得到是否接受w的相同的结的相同的结论，则称论，则称状态状态s1,s2位于同一个等价类位于同一个等价类，即，即若从若从s1出发出发DFA能接受能接受w,则从则从s2出发出发DFA也能接也能接受受

64、w，反之，若从反之，若从s1出发出发DFA拒绝拒绝w,则从则从s2出发出发DFA亦亦拒绝拒绝w。否则称状态否则称状态s1,s2是可区分的是可区分的。113DFADFA最小化算法：最小化算法：1.1.首先将状态集合首先将状态集合S分为两个等价类：分为两个等价类：A及及S-A；()2.等价类细分：对于当前已经划分的任意等价类细分：对于当前已经划分的任意等价类等价类K,如果如果a)或或b)条件满足，就将当条件满足，就将当前划分的等价类前划分的等价类K细分为两个更小的等细分为两个更小的等价类价类K1,K2,并使并使s1,s2分别落入细分后分别落入细分后的不同等价类中；的不同等价类中；114a)如果存在

65、输入符号如果存在输入符号a()，K中的两个状中的两个状态态s1,s2可由可由a转换到转换到当前已经划分的不当前已经划分的不同的等价类中；同的等价类中；b)如果存在输入符号如果存在输入符号a()，K中的两个状中的两个状态态s1,s2，当切仅当存在一个状态（当切仅当存在一个状态（s1或或s2）对于对于a 的转换没有意义即的转换没有意义即T(si,a)=；1153.3.对于对于步骤步骤2 2细分之后的所有等价类细分之后的所有等价类，递递归归上述步骤上述步骤2 2中细分等价类的工作，直中细分等价类的工作，直到对于同一等价类中的所有状态及任何到对于同一等价类中的所有状态及任何输入符号输入符号a()，我们

66、都不能将其细分我们都不能将其细分到不同的等价类为止。到不同的等价类为止。116对于处于同一等价类中的状态，我们可对于处于同一等价类中的状态，我们可以选用其中任一状态作为代表即可，等以选用其中任一状态作为代表即可，等价类中的其他状态皆可省略，同时，价类中的其他状态皆可省略，同时，把把所有引向省略状态的弧引向代表状态所有引向省略状态的弧引向代表状态。这就是这就是实现实现DFA最小化的基本原理最小化的基本原理。1171 1letterletter2 2letter|digitletter|digit3 3letter|digitletter|digit(1)(1)首先划分为两个等价类：首先划分为两个等价类：2，3，1例例1 1：将下图所示的：将下图所示的DFA MDFA M最小化最小化(2)对于输入符号对于输入符号letter:T(2,letter)=3,T(3,letter)=3;对于输入符号对于输入符号digit:T(2,digit)=3,T(3,digit)=3;118letterletter1 13 3letter|digitletter|digit同一等价类同一等价类2，3中的状态