《词法分析精选PPT.ppt》由会员分享，可在线阅读，更多相关《词法分析精选PPT.ppt（149页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、词法分析词法分析1第1页，此课件共149页哦2.1 2.1 词法分析器的作用词法分析器的作用 词法分析器词法分析器(词法分析程序词法分析程序)的任务的任务：从源从源代码中读取输入字符，产生单词序列代码中读取输入字符，产生单词序列(生生成独立的有意义的逻辑单元称作单词成独立的有意义的逻辑单元称作单词(token)，提交给语法分析使用。，提交给语法分析使用。2第2页，此课件共149页哦任务任务：逐个读入源程序字符并按照：逐个读入源程序字符并按照构词规则构词规则切分成一系切分成一系列单词。单词是语言中具有独立意义的最小单位，列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点
2、符号和常量等。包括保留字、标识符、运算符、标点符号和常量等。w识别出源程序中的单词；识别出源程序中的单词；w删除无用的空白字符及注释（空格、回车删除无用的空白字符及注释（空格、回车 等），这些信息等），这些信息仅增加了源程序的可读性，便于程序员阅读和维护程序，仅增加了源程序的可读性，便于程序员阅读和维护程序，而对于语法分析是完全无用的。而对于语法分析是完全无用的。w进行词法检查，能够检测出输入中不能形成进行词法检查，能够检测出输入中不能形成源语言任何单词的错源语言任何单词的错误字符串误字符串。3第3页，此课件共149页哦The big elephant ate the peanut.The b
3、ig elephant ate the peanut.big 词法分析的结果：词法分析的结果：4第4页，此课件共149页哦 token表示的字符串表示的字符串（串值或词义串值或词义）：）：if,y,3,then,x,=,0 token的的类型（词法）类型（词法）：关键字（关键字（if,else,for,int,return）操作符（操作符（+,-,）数字数字 （3,45,）标识符（标识符（x,y,name）补充：补充：typedef enum 类似宏类似宏 IF,THEN,PLUS,MINUS,NUM,ID TokenType;词法分析器的输出词法分析器的输出:token序列序列5第5页，此课
4、件共149页哦if y3 then x=0 LT,词法分析器词法分析器例如：例如：C源代码源代码:if y3 then x=0,词法分词法分析器的输出是？析器的输出是？类型类型 串值串值例例 ID 表示表示 标识符标识符 类型类型 x 表示表示 具体的标识符串具体的标识符串6第6页，此课件共149页哦定义逻辑项定义逻辑项token的数据类型的数据类型：typedef struct union char*stringval;int numval;attribute;TokenRecord;TokenType tokenval;Token类型类型Token词义词义补充：补充：union数据类型数据
5、类型7第7页，此课件共149页哦词法分析程序的函数接口：词法分析程序的函数接口：TokenRecord getToken(void);TokengetToken()源程序源程序词法分析程序词法分析程序语法分析程序语法分析程序符号表符号表8第8页，此课件共149页哦第第2 2章章 词法分析词法分析2.1 词法分析器的作用词法分析器的作用2.2 正则表达式正则表达式 2.3 有穷自动机有穷自动机2.4 从正则表达式到从正则表达式到DFA 2.5 用代码实现有穷自动机用代码实现有穷自动机2.6 利用利用lex自动生成词法分析自动生成词法分析程序程序记号的描记号的描述工具述工具记号的识记号的识别系统别
6、系统设计和实设计和实现词法分现词法分析程序析程序9第9页，此课件共149页哦正则表达式：正则表达式：对自动生成词法分析程序而言，正则表达对自动生成词法分析程序而言，正则表达 式也是非常有用的工具。式也是非常有用的工具。所谓所谓正则表达式正则表达式就是用特定的就是用特定的运算符运算符及及运算对运算对象象按某种规则构造的表达式。按某种规则构造的表达式。例如：例如：a*匹配匹配 空串空串,a,aa,aaa,其表示的是一个集合，记为其表示的是一个集合，记为L(a*)。正则表达式用来描述单词正则表达式用来描述单词结构结构(定义单词定义单词)。10第10页，此课件共149页哦2.2.1 基本概念和术语基本
7、概念和术语2.2.2 正则表达式的定义正则表达式的定义2.2.3 正则表达式基本等价关系正则表达式基本等价关系2.2.4 正则表达式的扩展正则表达式的扩展2.2.5 单词的正则表达式举例单词的正则表达式举例2.22.2正则表达式正则表达式 单词的描述工具单词的描述工具11第11页，此课件共149页哦2.2.1 2.2.1 基本概念和术语基本概念和术语字母表（符号表、符号集）字母表（符号表、符号集）由若干元素由若干元素（符号、字母）组成的有限非空集合。（符号、字母）组成的有限非空集合。不同的语言可以有不同的字母表，例如不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点汉语的字母
8、表中包括汉字、数字及标点符号等。符号等。12第12页，此课件共149页哦 符号串符号串 由字母表中的符号组成的任何有穷由字母表中的符号组成的任何有穷序列称为符号串序列称为符号串:例如例如00，11，10 是字母表是字母表 =0，1上的符号串。上的符号串。字母表字母表A=a，b，c上的符号串有：上的符号串有：a，b，c，ab，aaca等。等。在符号串中，符号的顺序是很重要的，符号串在符号串中，符号的顺序是很重要的，符号串ab就不同于就不同于ba，abca和和aabc也不同。也不同。13第13页，此课件共149页哦符号串的长度符号串的长度 如果某符号串如果某符号串x x中有中有m m个符号，则称个
9、符号，则称其长度为其长度为m m，表示为，表示为x x=m=m，如，如001110001110的长度是的长度是6 6。空符号串空符号串，即不包含任何符号的符号串，用，即不包含任何符号的符号串，用表示，其长度为表示，其长度为0 0，即，即=0=0。14第14页，此课件共149页哦w符号串的连接符号串的连接：设：设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第15页，此课件共149页哦例；若例；若x=ab x=ab 则则:x x0 0=x x1 1=ab=ab x x2 2=abab=abab x x3 3=ababab=ababab x xn n=xx=xxn-1 n-1=x=xn-1n-1x (n0)x (n0)16第16页，此课件共149页哦符号串集合符号串集合：若集合若集合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=xy|xAB=xy|x A,yA,y BB17第17页，此课件共149页哦v若用若用表示空集，则有：表示空集，则有：A+=+A=A A=A=A=A =Av 例：若集合例：若集合A=ab,cde ，集合集合B=B=0,1，则则AB=ab1,ab0,cde0,cde1；18第18页，此课件共149页哦的闭包：的闭包：用用*表示表示 上的一切符号串（包括上的一切符号串（包括）组成的集
12、合，）组成的集合，*称为称为的闭包的闭包。例如：例如：=a,b=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,的正闭包：的正闭包：上上除除外的所有符号串组成的外的所有符号串组成的集合记为集合记为+，+称为称为的正闭包的正闭包。例如：例如：=a,b=a,b+=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab,19第19页，此课件共149页哦2.2.1 基本概念和术语基本概念和术语2.2.2 正则表达式的定义正则表达式的定义2.2.3 正则表达式基本等价关系正则表达式基本等价关系2.2
13、.4 正则表达式的扩展正则表达式的扩展2.2.5 单词的正则表达式举例单词的正则表达式举例2.22.2正则表达式正则表达式20第20页，此课件共149页哦w正则表达式正则表达式就是用特定的就是用特定的运算符运算符及及运算对象运算对象按某种按某种规则构造的表达式。规则构造的表达式。w每个正则表达式代表一个每个正则表达式代表一个字符串的集合字符串的集合，我们把其称为，我们把其称为正则集。正则集。w语言语言(Language)是字符串组成的集合，我们也可以是字符串组成的集合，我们也可以把正则表达式表示的把正则表达式表示的正则集正则集称为该正则表达式表示的称为该正则表达式表示的语言语言。2.2.22.
14、2.2正则表达式的定义正则表达式的定义21第21页，此课件共149页哦w正则表达式和它所表示的正则集正则表达式和它所表示的正则集(字符串的集字符串的集合合)的递归定义如下：的递归定义如下：设有字母表为设有字母表为，辅助字母表，辅助字母表=,|,.,*,(,)22第22页，此课件共149页哦(1)和和是是上的正则式，它们所表示的正则集分上的正则式，它们所表示的正则集分别为别为和和;(2)若若a，则，则a是是上的正则式，它所表示的正则上的正则式，它所表示的正则集为集为a;(3)若若r和和s都是都是上的上的正则式正则式，且它们所表示的，且它们所表示的正则正则集集分别为分别为L(r)和和L(s)，那么
15、：，那么：23第23页，此课件共149页哦 r|s 是是正则式正则式，表示的，表示的正则集正则集为为 L(r|s)=L(r)L(s)；rs 是是正则式正则式，表示的，表示的正则集正则集为为 L(rs)=L(r)L(s)；r*是是正则式正则式，表示的，表示的正则集正则集为为(L(r)*。(r)是是正则式正则式，表示的，表示的正则集正则集为为L(r)；“.”运算符运算符常省略常省略24第24页，此课件共149页哦(4)仅由有限次使用上述三步骤而定义的表达式仅由有限次使用上述三步骤而定义的表达式才是才是上的上的正则式正则式，仅由这些正则式所表示仅由这些正则式所表示的符号串集合才是的符号串集合才是上的
16、上的正则集。正则集。注：算符的优先级为先注：算符的优先级为先“*”，再，再“.”最最后后“|”,都是左结合的，它们满足结合律。都是左结合的，它们满足结合律。25第25页，此课件共149页哦例例1，令，令=a，b，上的正则式和相应的正则集的例子：上的正则式和相应的正则集的例子：正则式正则式 正则集正则集aaa bab(a b)(a b)a a,babaa,ab,ba,bb ,a,aa,任意个任意个a的串的串(a b)a,b*即即,a,b,aa,ab,ba,bb,26第26页，此课件共149页哦例例2，正则式，正则式(a)|(b)*(c)它所表示的正则集为：它所表示的正则集为：根据运算符的优先级，
17、上述正则式可以表示成根据运算符的优先级，上述正则式可以表示成 a|b*ca|b*c所表示的正则集为：字符串所表示的正则集为：字符串a以及由零个或多个以及由零个或多个b后跟一个后跟一个c 形成的字符串的集合形成的字符串的集合或写成或写成L(a|b*c)=a bnc|其中其中n是大于或等于是大于或等于0的的整数整数27第27页，此课件共149页哦给定一个正则式给定一个正则式,它唯一确定一个正则集；反之它唯一确定一个正则集；反之不成立。即一个正则集可由多个不同的正则式不成立。即一个正则集可由多个不同的正则式表示。表示。aaaa a,aa,aaa,任意个任意个a的串的串a|aaa|aa a,aa,aa
18、a,任意个任意个a的串的串例如：例如：28第28页，此课件共149页哦若若二个二个正则式正则式描述同一正则集，则称二式描述同一正则集，则称二式等等价价(相等相等)。判断下列正则表达式判断下列正则表达式e e1 1和和e e2 2是否等价？是否等价？e1=(a b)，e2=b ae1=b(ab),e2=(ba)be1=(a b),e2=(a b)29第29页，此课件共149页哦w正则表达式正则表达式是表示模式的一种重要方法，每是表示模式的一种重要方法，每个模式匹配一个字符串集合个模式匹配一个字符串集合(即正则集即正则集)。w正则集正则集是正则表达式所定义的语言。是正则表达式所定义的语言。w正则表
19、达式正则表达式可以作为字符串集合可以作为字符串集合(即正则集即正则集)的名字。的名字。30第30页，此课件共149页哦2.2.1 基本概念和术语基本概念和术语2.2.2 正则表达式的定义正则表达式的定义2.2.3 正则表达式基本等价关系正则表达式基本等价关系2.2.4 正则表达式的扩展正则表达式的扩展2.2.5 单词的正则表达式举例单词的正则表达式举例2.22.2正则表达式正则表达式31第31页，此课件共149页哦A1.r|s=s|r A2.r|r=rA3.r|=rA4.(r|s)|t=r|(s|t)A5.(rs)t=r(st)A6.r(s|t)=rs|rtA7.(s|t)r=sr|trA8.
20、r=r=A9.r=r=rA10.r*=(|r)*=|rr*从集合论的角度去理解！从集合论的角度去理解！2.2.3 2.2.3 正则式基本等价关系正则式基本等价关系32第32页，此课件共149页哦2.2.1 基本概念和术语基本概念和术语2.2.2 正则表达式的定义正则表达式的定义2.2.3 正则表达式基本等价关系正则表达式基本等价关系2.2.4 正则表达式的扩展正则表达式的扩展2.2.5 单词的正则表达式举例单词的正则表达式举例2.22.2正则表达式正则表达式33第33页，此课件共149页哦2.2.4 2.2.4 正则表达式的扩展正则表达式的扩展w1.一个或多个重复（一个或多个重复（+，*）：）
21、：假设假设r是正则表达式，是正则表达式，wr的重复是通过使用标准的闭包运算来描述，的重复是通过使用标准的闭包运算来描述，写作写作r*。它允许。它允许r被重复被重复0次或更多次次或更多次。w用用r+表示表示r 被重复被重复1次或更多次次或更多次。因此有：。因此有：(0|1)+=(0|1)(0|1)*34第34页，此课件共149页哦2.任意字符（任意字符（.）:句点句点“.”表示可以匹配除换行符之外的任意单个符。表示可以匹配除换行符之外的任意单个符。利用这个字符就可为利用这个字符就可为所有包含至少一个所有包含至少一个b 的串的串写出写出一个一个正则表达式正则表达式，如下所示：，如下所示：.*b.*
22、3.引号引号“”，引号中的字符串表示文本字符串，引号中的字符串表示文本字符串本身。例如：本身。例如：“.”表示要匹配表示要匹配.字符本身。字符本身。35第35页，此课件共149页哦4.字符字符范围范围：表示法表示法a|b|z 表示所有小写字母；表示所有小写字母；0|1|9表示表示0到到9间的所有数字；间的所有数字；常见的表示法是利用常见的表示法是利用方括号方括号和和一个连字符一个连字符，如，如a-z是指所有小写字母，是指所有小写字母，0-9则指数字。则指数字。第二种表示法还可用作表示单个的解，第二种表示法还可用作表示单个的解，a|b|c可写可写成成abc，它还可用于多个范围，如，它还可用于多个
23、范围，如 a-z A-Z 代表所有的大小写字母。代表所有的大小写字母。36第36页，此课件共149页哦5.正则表达式的正则表达式的名字名字为较长的正则表达式提供一个简化的名字很有用处，为较长的正则表达式提供一个简化的名字很有用处，这样就不用每次使用正则表达式书写较长的表达式本身这样就不用每次使用正则表达式书写较长的表达式本身了；了；如要写一个正则表达式如要写一个正则表达式:a-z A-Z (a-z A-Z 0-9)它定义的正则集为：以字母打头后跟若干字母或数字它定义的正则集为：以字母打头后跟若干字母或数字组成的符号串的集合组成的符号串的集合。37第37页，此课件共149页哦上述正则式上述正则式
24、定义的是程序设计语言定义的是程序设计语言标识符标识符的的词法词法规则规则，通过为通过为正则表达式提供一个简化的名字，上述正则表正则表达式提供一个简化的名字，上述正则表达式可写作：达式可写作：letter=a-z A-Z digit=0-9 identify=letter(letter digit)38第38页，此课件共149页哦例：写出正则表达式例：写出正则表达式signedNatnat=0-9+signedNat=nat|+nat|-nat对应的正则集？对应的正则集？39第39页，此课件共149页哦6.可选的子表达式（可选的子表达式（？）：）：w如果在特定的串中包括既可能出现又可能不出现的如
25、果在特定的串中包括既可能出现又可能不出现的可选部分。例如，可选部分。例如，nat=0-9+signedNat=nat|+nat|-natw我们可以引入问号我们可以引入问号?来表示来表示r 匹配的串是可选的；上面的例子匹配的串是可选的；上面的例子可写成：可写成：nat=0-9+signedNat=(+|-)？nat40第40页，此课件共149页哦2.2.1 基本概念和术语基本概念和术语2.2.2 正则表达式的定义正则表达式的定义2.2.3 正则表达式基本等价关系正则表达式基本等价关系2.2.4 正则表达式的扩展正则表达式的扩展2.2.5 单词的正则表达式举例单词的正则表达式举例2.22.2正则表
26、达式正则表达式41第41页，此课件共149页哦2.2.5 2.2.5 单词的正则表达式举例单词的正则表达式举例每一种程序设计语言都有自己的字符集每一种程序设计语言都有自己的字符集(字母表字母表)。语言中的各个语言中的各个单词单词或是或是 上的单个字符上的单个字符(如运算符、分隔如运算符、分隔符等符等)，或是，或是 上的字符串上的字符串(如常数、表示符和关键字等如常数、表示符和关键字等)。程序设计语言的程序设计语言的单词单词都能用都能用正则式正则式来定义来定义.由正则式描述由正则式描述的的单词类单词类也称为也称为正则集正则集。42第42页，此课件共149页哦1.1.数：数：nat=0-9+sig
27、nedNat=(+|-)?natnumber=signedNat(“.”nat)?(“E”signedNat)?例如：例如：3,3.5,2.71E-22.2.保留字：保留字：reserved=else|if|int|return|void|while 43第43页，此课件共149页哦3.3.标识符：标识符：letter=a-zA-Zdigit=0-9identifier=letter(letter|digit)*44第44页，此课件共149页哦 包含单词词法描述的包含单词词法描述的语言手册语言手册是编译器是编译器的程序员最常见的。在下面的示例中，的程序员最常见的。在下面的示例中，被匹配的串是汉
28、语描述，其任务是将描被匹配的串是汉语描述，其任务是将描述述翻译为正则表达式翻译为正则表达式。45第45页，此课件共149页哦1)在字母表在字母表 =a,b,c中，考虑在这个字母中，考虑在这个字母表上的表上的仅包括一个仅包括一个b 的所有串的集合的所有串的集合，这个，这个集合所对应的正则表达式为：集合所对应的正则表达式为：串串b、abc、abaca、baaaac、ccbaca和和ccccccb等都是满要求的符号串。等都是满要求的符号串。(a|c)*b(a|c)*46第46页，此课件共149页哦2)在字母表在字母表 =a,b,c中，中，如果字符串集合是如果字符串集合是包括最多一包括最多一个个b 的
29、所有串的所有串，则这个集合的正则表达式为：，则这个集合的正则表达式为：仅包括一个仅包括一个b 的串的集合对应的正则表达式的串的集合对应的正则表达式 (a|c)*b(a|c)*不包括不包括b 的串的集合对应的正则表达式的串的集合对应的正则表达式 (a|c)*故所求表达式为：故所求表达式为：(a|c)*|(a|c)*b(a|c)*或者为或者为:(a|c)*(b|)(a|c)*47第47页，此课件共149页哦3)在在字母表字母表 =a,b上串上串S的集合是由一个的集合是由一个b及在及在其前后有相同数目的其前后有相同数目的a 组成：组成：S=b,aba,aabaa,aaabaaa,.=anban|n0
30、 正则表达式并不能描述这个集合正则表达式并不能描述这个集合，其原因在于重复运算只有，其原因在于重复运算只有闭包运算闭包运算*一种，它允许有任意次的重复。因此如要写出一种，它允许有任意次的重复。因此如要写出表达式表达式a*ba*，就不能保证在，就不能保证在b 前后的前后的a 的数量是否相等了。的数量是否相等了。48第48页，此课件共149页哦w并非用简单术语描述的所有串都可由并非用简单术语描述的所有串都可由 正则表正则表达式产生，因此为了与其他集合相区分，作达式产生，因此为了与其他集合相区分，作为正则表达式描述的串集合称作正则集为正则表达式描述的串集合称作正则集(regular set)。w非正
31、则集偶尔也作为串出现在需要由扫描程非正则集偶尔也作为串出现在需要由扫描程序识别的程序设计语言中。序识别的程序设计语言中。49第49页，此课件共149页哦第第2 2章章 词法分析词法分析2.1 词法分析器的作用词法分析器的作用2.2 正则表达式正则表达式 2.3 有穷自动机有穷自动机2.4 从正则表达式到从正则表达式到DFA 2.5 用代码实现有穷自动机用代码实现有穷自动机2.6 利用利用lex自动生成词法分析程序自动生成词法分析程序记号的描记号的描述工具述工具记号的识记号的识别系统别系统设计和实设计和实现词法分现词法分析程序析程序50第50页，此课件共149页哦2.3.1有穷自动机有穷自动机2
32、.3.2确定性有穷自动机确定性有穷自动机(DFA)的定义的定义2.3.3非确定性有穷自动机非确定性有穷自动机(NFA)2.32.3有穷自动机有穷自动机51第51页，此课件共149页哦2.3.1 2.3.1 有穷自动机有穷自动机有穷自动机有穷自动机(也称有限自动机也称有限自动机)作为一种数学模作为一种数学模型，它能准确地识别正则集，即识别正则式所型，它能准确地识别正则集，即识别正则式所表示的集合。表示的集合。有穷自动机是有穷自动机是设计和实现词法分析器设计和实现词法分析器的有效的有效工具，其直观图是一种状态转换图。工具，其直观图是一种状态转换图。引入有穷自动机理论，也是为词法分析程序引入有穷自动
33、机理论，也是为词法分析程序的自动构造寻找方法和工具。的自动构造寻找方法和工具。52第52页，此课件共149页哦有穷自动机有穷自动机(Finite Automata,or finite-state machines)有穷自动机分为两类：有穷自动机分为两类：确定的有穷自动机确定的有穷自动机(Deterministic Finite Automata，DFA)。不确定的有穷自动机不确定的有穷自动机(Nondeterministic Finite Automata，NFA)。53第53页，此课件共149页哦在程序设计语言中，用正则式在程序设计语言中，用正则式定义定义的标识符的标识符如下：如下：lett
34、er=a-zA-Zdigit=0-9identifier=letter(letter|digit)*该正则式匹配的标识符是以一个字母开头且该正则式匹配的标识符是以一个字母开头且其后为任意字母、数字序列形成的字符串。其后为任意字母、数字序列形成的字符串。54第54页，此课件共149页哦12letterletterdigit标识符的有穷自动机标识符的有穷自动机变量变量xtemp xtemp 识别为标识符的过程可表示为：识别为标识符的过程可表示为：1x2t2e2m2p2 标识符模式的标识符模式的识别识别过程：过程：55第55页，此课件共149页哦2.3.1有穷自动机的引入有穷自动机的引入2.3.2确
35、定性有穷自动机确定性有穷自动机(DFA)的定义的定义2.3.3非确定性有穷自动机非确定性有穷自动机(NFA)2.32.3有穷自动机有穷自动机56第56页，此课件共149页哦2.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，
36、s s S S，c c上述转换函数表示：若当前状态为上述转换函数表示：若当前状态为s s,且当前识别的输入且当前识别的输入符号为符号为c c,识别识别c c后进入的下一个状态为后进入的下一个状态为s s 。57第57页，此课件共149页哦(4)(4)初始状态初始状态s s0 0 S S;指示识别符号串的开始状态指示识别符号串的开始状态;(5)(5)若干个若干个识别符号串的识别符号串的接受状态接受状态(或称为终止状或称为终止状 态态)的集合的集合 A A S S;(由上述五个要素组成的五元式由上述五个要素组成的五元式M=(S;M=(S;T;s;T;s0 0;A);A)称为一个确定称为一个确定的有
37、限自动机的有限自动机(DFADFA:D Deterministic eterministic F Finite inite A Automatautomata)。58第58页，此课件共149页哦DFA 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 的例子：的例子：有限个状有限个状态
38、的集合态的集合s字母表字母表 初始状态初始状态接受状接受状态的集合态的集合A A59第59页，此课件共149页哦状态转换图状态转换图一个一个DFADFA可以表示成一个状态图可以表示成一个状态图(或称或称状态状态转换图转换图)。状态转换图是由一组矢线连结的有。状态转换图是由一组矢线连结的有限个结点所组成的有向图。限个结点所组成的有向图。例如：例如：s0 0s2 20s1 11060第60页，此课件共149页哦假定假定DFA MDFA M含有含有m m个状态，那么这个状态图就个状态，那么这个状态图就含有含有m m个结点；结点用小圆圈表示，个结点；结点用小圆圈表示，圆圈中标入圆圈中标入状态的名字状态
39、的名字或编号。或编号。为了醒目起见，用为了醒目起见，用箭头指示初始状态，箭头指示初始状态，用双圆圈表示终止转态。用双圆圈表示终止转态。s结点结点s0 0初始状态初始状态sn n接受状态接受状态61第61页，此课件共149页哦sas状态转换的图形表示状态转换的图形表示w若若 T(s,a)=s，则从状态结点，则从状态结点s到状态结点到状态结点s画标记为画标记为a的矢线。的矢线。表示当词法分析器处于该矢线的结点所指示的表示当词法分析器处于该矢线的结点所指示的状态状态s时，可能要识别的输入字符为时，可能要识别的输入字符为a，而矢线，而矢线进入的结点进入的结点s则指示识别相应的输入字符则指示识别相应的输
40、入字符a后后进入的下一个状态。进入的下一个状态。62第62页，此课件共149页哦 例：例：M=(s0 0,s1 1,s2 2,0,1,T,s0 0,s2 2)其中其中,T的定义如下：的定义如下：T(s0 0,0)=s1 1 T(s1 1,0)=s1 1 T(s1 1,1)=s2 2 s0 0s2 20s1 110状态转换图举例状态转换图举例上述上述DFADFA对应的状态转换图：对应的状态转换图：63第63页，此课件共149页哦w在状态转换图中，从一个结点可以同时引出若干条矢在状态转换图中，从一个结点可以同时引出若干条矢线到有向图中的其余结点线到有向图中的其余结点(也可从一结点引矢线到其也可从一
41、结点引矢线到其自身自身)；w每一矢线上均标记一个字符或字符类记号，表示当词法分每一矢线上均标记一个字符或字符类记号，表示当词法分析器处于该矢线的结点所指示的状态时，可能要识别的输析器处于该矢线的结点所指示的状态时，可能要识别的输入字符，而矢线进入的结点则指示识别相应的输入字符后入字符，而矢线进入的结点则指示识别相应的输入字符后进入的下一个状态。进入的下一个状态。64第64页，此课件共149页哦DFADFA的接受集的接受集(即识别的字符串集合即识别的字符串集合)DFA识别的字符串识别的字符串c c1 1 c c2 2 c cn n的集合的集合满足如下条件：满足如下条件：每个每个c ci i ，且
42、存在状态，且存在状态 s1=T(s0，c1),s2=T(s1，c2),sn=T(sn-1，cn),其中其中s0 是初态，是初态，sn 是终态。是终态。65第65页，此课件共149页哦s s0 0c c1 1s s1 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
43、c2 2 c cn nvDFA M识别的字符串的集合识别的字符串的集合 记作记作L(M)L(M)也称为由正则表达式也称为由正则表达式M生成的语言。生成的语言。66第66页，此课件共149页哦bs1s2s3s4abba|baa例：证明字符串序列例：证明字符串序列baabbaab被下图的被下图的DFADFA所接受。所接受。任意列出它接受的另外两个输入串？任意列出它接受的另外两个输入串？任意列出它拒绝接受的两个输入串？任意列出它拒绝接受的两个输入串？67第67页，此课件共149页哦证明：由于存在证明：由于存在T(sT(s1 1,b,b）=s=s3 3T(sT(s3 3,a,a）=s=s2 2T(sT
44、(s2 2,a,a）=s=s4 4T(sT(s4 4,b,b）=s=s4 4s s4 4属于终态，得证。属于终态，得证。68第68页，此课件共149页哦(1).状态转换图中的状态转换图中的状态状态可以使用可以使用任何标识任何标识系统系统来标识来标识(2).状态转换图中的状态转换图中的转换转换可以使用可以使用字符集合字符集合的名字的名字标出标出关于关于DFADFA的状态转换图的的状态转换图的2 2点说明点说明startin_idletterletterdigit69第69页，此课件共149页哦12digitdigit例例1：自然数的集合自然数的集合被下图所示的被下图所示的DFA接受。接受。注：注
45、：digit=0-9DFADFA的示例的示例70第70页，此课件共149页哦例例2：字母表字母表 =a,b,c上上有且仅有一个有且仅有一个b构成的构成的字符串集合字符串集合被下图所示的被下图所示的DFA接受。接受。12bnotbnotb注：注：notb=a,c71第71页，此课件共149页哦例例3：字母表字母表 =a,b,c上上包含最多一个包含最多一个b构成构成的字符串的集合的字符串的集合被下图所示的被下图所示的DFA接受。接受。2bnotbnotb1注：注：notb=a,c72第72页，此课件共149页哦例例4：有：有C风格注释的风格注释的DFA15/other12*3*4*/other2注
46、：注：other1other1表示除表示除*之外的所有字符的集合的名字；之外的所有字符的集合的名字；other2other2表示除表示除*,/*,/之外的所有字符的集合的名字。之外的所有字符的集合的名字。73第73页，此课件共149页哦2.3.1有穷自动机的引入有穷自动机的引入2.3.2确定性有穷自动机确定性有穷自动机(DFA)的定义的定义2.3.3非确定性有穷自动机非确定性有穷自动机(NFA)2.32.3有穷自动机有穷自动机74第74页，此课件共149页哦2.3.32.3.3非确定性有穷自动机（非确定性有穷自动机（NFANFA）下图是识别下图是识别=、,字符串的一个有字符串的一个有穷自动机，
47、对于输入符号穷自动机，对于输入符号,在状态在状态0 0上存上存在不止一种转换。在不止一种转换。15302475第75页，此课件共149页哦w有穷自动机对于某个输入符号，如果有穷自动机对于某个输入符号，如果在同一个状态上存在不止一种转换，在同一个状态上存在不止一种转换，我们称该有穷自动机为不确定的有穷我们称该有穷自动机为不确定的有穷自动机。自动机。w在给出非确定性有穷自动机的定义之在给出非确定性有穷自动机的定义之前先引入前先引入-转换转换的概念。的概念。76第76页，此课件共149页哦-转换转换是无需考虑输入串就有可能发生的转换。是无需考虑输入串就有可能发生的转换。它可看作是一个空串它可看作是一
48、个空串 的的“匹配匹配”，-转换的转换的图形表示为：图形表示为：0 1-转换的引入转换的引入-转换转换可以清晰地描述出空串的匹配：可以清晰地描述出空串的匹配：0 177第77页，此课件共149页哦0 -转换转换可以通过添加一个新的初始状态来链接各个自动可以通过添加一个新的初始状态来链接各个自动机，从而将它们合并为一个自动机。机，从而将它们合并为一个自动机。将识别数字和字符将识别数字和字符的两个的两个DFADFA和并为一个非确定的有穷自动机：和并为一个非确定的有穷自动机：letterletterletterletterDONE2DONE2START2START2START1START1digit
49、digitdigitdigitDONE1DONE178第78页，此课件共149页哦0 123:=675=89=通过通过-转换将识别转换将识别:=:=、=、=的的DFADFA合并为：合并为：79第79页，此课件共149页哦NFA(非确定性有穷自动机非确定性有穷自动机)有五个部分组成：有五个部分组成：(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
50、S,且要识别的输入符号为且要识别的输入符号为c c ,识别识别c c后后进入的状态是进入的状态是S S的一个状态的一个状态子集子集ssk1,s skm ;2.3.22.3.2非确定性有穷自动机（非确定性有穷自动机（NFANFA）的定义）的定义80第80页，此课件共149页哦(4)(4)初始状态初始状态s s0 0 S S;(5)(5)若干个接受状态的集合若干个接受状态的集合:A A S S 由上述五个要素组成的五元式由上述五个要素组成的五元式 M=(SM=(S；T T；s s0 0；A)A)称为一个非确定的有限自动机称为一个非确定的有限自动机 (NFANFA:Nondeterministico