编译原理课程设计之词法分析.pptx

《编译原理课程设计之词法分析.pptx》由会员分享，可在线阅读，更多相关《编译原理课程设计之词法分析.pptx（152页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、mcy1第第2 2章章 词法分析词法分析2.1 词法分析器的作用2.2 正规表达式 2.3 有穷自动机2.4 从正规表达式到DFA 2.5 用代码实现有穷自动机2.6 利用lex自动生成词法分析程序单词的描述工具单词的描述工具单词单词的识别系统的识别系统设计和实现词法设计和实现词法分析程序分析程序作业作业课程设计课程设计1 1 第1页/共152页mcy22.1 2.1 词法分析器的作用词法分析器的作用 词法分析器词法分析器(词法分析程序词法分析程序)的任务的任务：从源代码中读取输入字符，产生单词序列(生成独立的有意义的逻辑单元称作单词(token)，提交给语法分析使用。第2页/共152页mcy

2、3任务：逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。识别出源程序中的单词；删除无用的空白字符及注释（空格、回车 等），这些信息仅增加了源程序的可读性，便于程序员阅读和维护程序，而对于语法分析是完全无用的。进行词法检查，能够检测出输入中不能形成源语言任何单词的错误字符串。第3页/共152页mcy4The big elephant ate the peanut.The big elephant ate the peanut.big 词法分析的结果：词法分析的结果：第4页/共152页mcy5 token表示的字符

3、串（串值或词义串值或词义）：if,y,3,then,x,=,0 token的类型（词法）类型（词法）：关键字（if,else,for,int,return）操作符（+,-,）数字 （3,45,）标示符（x,y,）词法分析器的输出:token序列第5页/共152页mcy6if y3 then x=0 LT,词法分析器词法分析器例如：C源代码:if y3 then x=0,词法分析器的输出是？第6页/共152页mcy7定义逻辑项token的数据类型：typedef struct union char*stringval;int numval;attribute;TokenRecord;TokenT

4、ype tokenval;Token类型类型Token词义词义第7页/共152页mcy8词法分析程序的函数接口：TokenRecord getToken(void);TokengetToken()源程序词法分析程序语法分析程序符号表第8页/共152页mcy9第第2 2章章 词法分析词法分析2.1 词法分析器的作用2.2 正规表达式 2.3 有穷自动机2.4 从正规表达式到DFA 2.5 用代码实现有穷自动机2.6 利用lex自动生成词法分析程序记号的描述工具记号的描述工具记号的识别系统记号的识别系统设计和实现词法设计和实现词法分析程序分析程序作业作业课程设计课程设计1 1 第9页/共152页m

5、cy10正规表达式的引入：正规表达式的引入：对自动生成词法分析程序而言，正规表达 式也是非常有用的工具。所谓正规表达式就是用特定的运算符及运算对象按某种规则构造的表达式。例如：c-语言的词法。正规表达式用来描述单词结构(定义单词)。第10页/共152页mcy11正规表达式的定义正规表达式的扩展2.22.2正规表达式正规表达式 单词的描述工具单词的描述工具第11页/共152页mcy12字母表（符号表、符号集）字母表（符号表、符号集）由若干元素（符号、字母）组成的有限非空集合。不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。第12页/共152页mcy13 符号串符号串

6、由字母表中的符号组成的任何有穷序列称为符号串:例如00 11 10 是字母表 =0，1上的符号串。字母表A=a，b，c上的符号串有：a，b，c，ab，aaca。在符号串中，符号的顺序是很重要的，符号串ab就不同于ba，abca和aabc也不同。第13页/共152页mcy14符号串的长度符号串的长度 如果某符号串x x中有m m个符号，则称其长度为m m，表示为x x=m=m，如001110001110的长度是6 6。空符号串空符号串，即不包含任何符号的符号串，用表示，其长度为0 0，即=0=0。第14页/共152页mcy15符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号

7、之后得到的符号串。例如 x=ST，y=abu，则它们的连接 xy=STabu，x=2，y=3，xy=5由于的含义，显然有x=x=x。符号串的方幂：符号串自身连接n次得到的符号串xn 定义为 xxxx；n个x x1=x,x2=xx且x0=第15页/共152页mcy16例；若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页/共152页mcy17符号串集合符号串集合：若集合A A中所有元素都是某字母表 上的符号串，则称A

8、 A为字母表 上的符号串集合。符号串集合的和与积符号串集合的和与积设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 BB第17页/共152页mcy18v若用表示空集，则有：A+=+A=A A=A=A=A =Av 例：若集合A=ab,cde ，集合B=B=0,1，则AB=ab1,ab0,cde0,cde1；第18页/共152页mcy19的闭包：用*表示 上的一切符号串（包括）组成的集合，*称为的闭包。例如：=a,b=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,=,a,

9、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页/共152页mcy20正规表达式的定义正规表达式的扩展2.22.2正规表达式正规表达式第20页/共152页mcy21正规表达式(也称正则表达式)就是用特定的运算符及运算对象按某种规则构造的表达式。每个正规表达式代表一个字符串的集合，我们把其称为正规集。语言(Language)是字符串组成的集合，我们也可以把正规表达式表示的正规集称为该正规表达式表示的语言。第2

10、1页/共152页mcy22正规表达式和它所表示的正规集(字符串的集合)的递归定义如下：设有字母表为，辅助字母表=,|,.,*,(,)第22页/共152页mcy23(1)和是上的正规式，它们所表示的正规集分别为和;(2)若a，则a是上的正规式，它所表示的正规集为a;(3)若r和s都是上的正规式，且它们所表示的正规集分别为L(r)和L(s)，那么：第23页/共152页mcy24 r|s 是正规式，表示的正规集为 L(r|s)=L(r)L(s)；rs 是正规式，表示的正规集为 L(rs)=L(r)L(s)；r*是正规式，表示的正规集为(L(r)*。(r)是正规式，表示的正规集为L(r)；“.”运算符

11、常省略第24页/共152页mcy25(4)仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的符号串集合才是上的正规集。注：算符的优先级为先“*”，再“.”最后“|”,都是左结合的，它们满足结合律。举例：C-语言的词法第25页/共152页mcy26例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页/共152页mcy27例2，正规式(a)|(b)*(c)它所表示的正规集为：根据运算符的优先级，上述正规式

12、可以表示成 a|b*ca|b*c所表示的正规集为：字符串a以及由零个或多个b后跟一个c 形成的字符串的集合或写成L(a|b*c)=a bnc|其中n是大于或等于0的整数第27页/共152页mcy28给定一个正规式给定一个正规式,它唯一确定一个正规集；反之不成立。即一个正规集可由它唯一确定一个正规集；反之不成立。即一个正规集可由多个不同的正规式表示。多个不同的正规式表示。aaaa a,aa,aaa,任意个a的串a|aaa|aa a,aa,aaa,任意个a的串例如：第28页/共152页mcy29若二正规式二正规式描述同一正规集，则称二式等价等价(相等)。判断下列正规表达式e e1 1和e e2 2

13、是否等价？e1=(a b)，e2=b ae1=b(ab),e2=(ba)be1=(a b),e2=(a b)第29页/共152页mcy30正规表达式是表示模式的一种重要方法，每个模式匹配一个字符串集合(即正规集)。正规集是正规表达式所定义的语言。正规表达式可以作为字符串集合(即正规集)的名字。第30页/共152页mcy31正规表达式的定义正规表达式的扩展2.22.2正规表达式正规表达式第31页/共152页mcy32A1.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.

14、r=r=A9.r=r=rA10.r*=(|r)*=|rr*第32页/共152页mcy33正规表达式的定义正规表达式的扩展2.22.2正规表达式正规表达式第33页/共152页mcy341.一个或多个重复（+，*）：假设r是正则表达式，r的重复是通过使用标准的闭包运算来描述，写作r*。它允许r被重复0次或更多次。用r+表示r 被重复1次或更多次。因此有：(0|1)+=(0|1)(0|1)*第34页/共152页mcy352.任意字符（.）:句点“.”表示可以匹配除换行符之外的任意单个符。利用这个字符就可为所有包含至少一个b 的串写出一个正则表达式，如下所示：.*b.*3.引号“”，引号中的字符串表示

15、文本字符串本身。例如：“.”表示要匹配.字符本身。第35页/共152页mcy364.字符范围：表示法a|b|z 表示所有小写字母；0|1|9表示0到9间的所有数字；常见的表示法是利用方括号和一个连字符，如a-z是指所有小写字母，0-9则指数字。第二种表示法还可用作表示单个的解，a|b|c可写成abc，它还可用于多个范围，如 a-z A-Z 代表所有的大小写字母。第36页/共152页mcy375.正规表达式的名字为较长的正则表达式提供一个简化的名字很有用处，这样就不用每次使用正则表达式书写较长的表达式本身了；如要写一个正则表达式:a-z A-Z (a-z A-Z 0-9)它定义的正规集为：以字母

16、打头后跟若干字母或数字组成的符号串的集合。第37页/共152页mcy38上述正规式定义的是程序设计语言标识符的词法规则，通过为正规表达式提供一个简化的名字，上述正规表达式可写作：letter=a-z A-Z digit=0-9 r=letter(letter digit)第38页/共152页mcy39例：写出正则表达式signedNatnat=0-9+signedNat=nat|+nat|-nat对应的正规集？第39页/共152页mcy406.可选的子表达式（？）：如果在特定的串中包括既可能出现又可能不出现的可选部分。例如，nat=0-9+signedNat=nat|+nat|-nat我们可以

17、引入问号?来表示r 匹配的串是可选的；上面的例子可写成：nat=0-9+signedNat=(+|-)？nat第40页/共152页mcy41正规表达式的定义正规表达式的扩展2.22.2正规表达式正规表达式第41页/共152页mcy42每一种程序设计语言都有自己的字符集(字母表)。语言中的各个单词或是 上的单个字符(如运算符、分隔符等)，或是 上的字符串(如常数、表示符和关键字等)。程序设计语言的单词都能用正规式来定义.由正规式描述的单词类也称为正规集。例如：C-语言的词法第42页/共152页mcy431.1.数：nat=0-9+signedNat=(+|-)?natnumber=signedN

18、at(“.”nat)?(“E”signedNat)?例如：3,3.5,2.71E-22.2.保留字：reserved=else|if|int|return|void|while 第43页/共152页mcy443.3.标示符：letter=a-zA-Zdigit=0-9identifier=letter(letter|digit)*第44页/共152页mcy45 包含单词词法描述的语言手册是编译器的程序员最常见的。在下面的示例中，被匹配的串是汉语描述，其任务是将描述翻译为正则表达式。第45页/共152页mcy461)在字母表 =a,b,c中，考虑在这个字母表上的仅包括一个b 的所有串的集合，这个

19、集合所对应的正则表达式为：串串b、abc、abaca、baaaac、ccbaca和和ccccccb等都是满要求的符号串。等都是满要求的符号串。(a|c)*b(a|c)*第46页/共152页mcy472)在字母表 =a,b,c中，如果字符串集合是包括最多一个b 的所有串，则这个集合的正则表达式为：仅包括一个b 的串的集合对应的正则表达式 (a|c)*b(a|c)*不包括b 的串的集合对应的正则表达式 (a|c)*故所求表达式为：(a|c)*|(a|c)*b(a|c)*或者为:(a|c)*(b|)(a|c)*第47页/共152页mcy483)在字母表 =a,b上串S的集合是由一个b及在其前后有相同

20、数目的a 组成：S=b,aba,aabaa,aaabaaa,.=anban|n0 正则表达式并不能描述这个集合，其原因在于重复运算只有闭包运算*一种，它允许有任意次的重复。因此如要写出表达式a*ba*，就不能保证在b 前后的a 的数量是否相等了。第48页/共152页mcy49并非用简单术语描述的所有串都可由 正则表达式产生，因此为了与其他集合相区分，作为正则表达式描述的串集合称作正规集(regular set)。非正规集偶尔也作为串出现在需要由扫描程序识别的程序设计语言中。第49页/共152页mcy50第第2 2章章 词法分析词法分析2.1 词法分析器的作用2.2 正规表达式 2.3 有穷自动

21、机2.4 从正规表达式到DFA 2.5 用代码实现有穷自动机2.6 利用lex自动生成词法分析程序记号的描述工具记号的描述工具记号的识别系统记号的识别系统设计和实现词法设计和实现词法分析程序分析程序作业作业课程设计课程设计1 1 第50页/共152页mcy51DFA)的定义NFA)2.32.3有穷自动机有穷自动机第51页/共152页mcy52有穷自动机(也称有限自动机)作为一种数学模型，它能准确地识别正规集，即识别正规式所表示的集合。有穷自动机是设计和实现词法分析器的有效工具，其直观图是一种状态转换图。引入有穷自动机理论，也是为词法分析程序的自动构造寻找方法和工具。第52页/共152页mcy5

22、3有穷自动机有穷自动机(Finite Automata,or finite-state machines)有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)。不确定的有穷自动机(Nondeterministic Finite Automata)。第53页/共152页mcy54在程序设计语言中，用正规式定义的标示符如下：letter=a-zA-Zdigit=0-9identifier=letter(letter|digit)*该正规式匹配的标示符是以一个字母开头且其后为任意字母、数字序列形成的字符串。第54页/共152页mcy5512letterl

23、etterdigit标示符的有穷自动机变量xtemp xtemp 识别为标示符的过程可表示为：识别为标示符的过程可表示为：1x2t2e2m2p2 标示符模式的识别过程：第55页/共152页mcy56DFA)的定义NFA)2.32.3有穷自动机有穷自动机第56页/共152页mcy57DFADFA）的定义的定义DFA(DFA(确定性有穷自动机)有五个部分组成：(1)(1)有限个输入符号组成的字母表,记作;(2)(2)有限个状态的集合,记作S S;(3)(3)转换函数T T T:T:S S S S 即：T(s,c)=sT(s,c)=s 其中s s S S，s s S S，c c上述转换函数表示若当前

24、状态为s s,且当前识别的输入符号为c c,识别c c后进入的下一个状态为s s ;第57页/共152页mcy58(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 Deterministic eterministic F Finite inite A Automatautomata)。第58页/共152页mcy59DFA MDFA M=（ss1 1,s,s2 2,s,s3

25、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 A第59页/共152页mcy60状态转换图状态转换图一个DFADFA可以表示成一个状态图(或称状态转换图)。状态转换图是由一组矢线连结的有限个结点所组成的有向图。例如：s0 0s2 20s1 110

26、第60页/共152页mcy61假定DFA MDFA M含有m m个状态，那么这个状态图就含有m m个结点；结点用小圆圈表示，圆圈中标入状态的名字或编号。为了醒目起见，用箭头指示初始状态，用双圆圈表示终止转态。s结点s0 0初始状态sn n接受状态第61页/共152页mcy62sas状态转换的图形表示若 T(s,a)=s，则从状态结点s到状态结点s画标记为a的矢线。表示当词法分析器处于该矢线的结点所指示的状态s时，可能要识别的输入字符为a，而矢线进入的结点s则指示识别相应的输入字符a后进入的下一个状态。第62页/共152页mcy63 例：M=(s0 0,s1 1,s2 2,0,1,T,s0 0,

27、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页/共152页mcy64在状态转换图中，从一个结点可以同时引出若干条矢线到有向图中的其余结点(也可从一结点引矢线到其自身)；每一矢线上均标记一个字符或字符类记号，表示当词法分析器处于该矢线的结点所指示的状态时，可能要识别的输入字符，而矢线进入的结点则指示识别相应的输入字符后进入的下一个状态。第64页/共152页mcy65DFADFA的接受集的接受集(即识别的字符串集合即识别的字符

28、串集合)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 是终态。第65页/共152页mcy66s 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 c2 2 c cn nvDFA M识

29、别的字符串的集合 记作L(M)第66页/共152页mcy67bs1s2s3s4abba|baa例：证明字符串序列baabbaab被下图的DFADFA所接受。任意列出它接受的另外两个输入串？任意列出它拒绝接受的两个输入串？第67页/共152页mcy68证明：由于存在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页/共152页mcy69(1).状态转换图中的状态可以使用任何标识系统来标识(2).状态转换图中的转换可以使用字符集合的名字标出关于关

30、于DFADFA的状态转换图的的状态转换图的2 2点说点说明明startin_idletterletterdigit第69页/共152页mcy7012digitdigit例1：自然数的集合被下图所示的DFA接受。注：digit=0-9DFADFA的示例的示例第70页/共152页mcy71例2：字母表 =a,b,c上有且仅有一个b构成的字符串集合被下图所示的DFA接受。12bnotbnotb注：notb=a,c第71页/共152页mcy72例3：字母表 =a,b,c上包含最多一个b构成的字符串的集合被下图所示的DFA接受。2bnotbnotb1注：notb=a,c第72页/共152页mcy73例4

31、：有C风格注释的DFA15/other12*3*4*/other2注：other1other1表示除*之外的所有字符的集合的名字；other2 other2表示除*,/*,/之外的所有字符的集合的名字。第73页/共152页mcy74DFA)的定义NFA)2.32.3有穷自动机有穷自动机第74页/共152页mcy75NFANFA）下图是识别=、,字符串的一个有穷自动机，对于输入符号,在状态0 0上存在不止一种转换。153024第75页/共152页mcy76有穷自动机对于某个输入符号，如果在同一个状态上存在不止一种转换，我们称该有穷自动机为不确定的有穷自动机。在给出非确定性有穷自动机的定义之前先引

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

33、3:=675=89=通过-转换将识别:=:=、=、=的DFADFA合并为：第79页/共152页mcy80NFA(非确定性有穷自动机)有五个部分组成：(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后进入的状态是S S的一个状态子集ssk1,s skm ;NFANFA）的定义的定义第80页/共152页mcy81(4)(4)初始状态s s0 0 S S;(5)(5)若干个接受状

34、态的集合:A A S S 由上述五个要素组成的五元式 M=(SM=(S；T T；s s0 0；A)A)称为一个非确定的有限自动机 (NFANFA:Nondeterministicondeterministic F Finite inite A Automatautomata),),由上述定义可以看出，DFADFA是NFANFA的一个特例。第81页/共152页mcy82一个一个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=

35、Z;T（Z Z，1 1）=P;=P;T T（S S，1 1）=S=S，Z;Z;第82页/共152页mcy83NFANFA的状态转换图的状态转换图例：M=(,=,0，1，2，3，4，5,T,0,2，4，5)其中T的定义如下：T(0,)=4 153024第83页/共152页mcy84NFA M 的接受集记作L(M)L(M)L(M)定义为字符串c c1 1c c2 2 c cn n的集合，其中每个c ci i ，且存在：s s1 1 T(sT(s0 0,c c1 1),s s2 2 T(sT(s1 1,c c2 2),),s sn n T(sT(sn-1 n-1,c cn n),),其中s s0 0

36、是初态，s sn n是终态集中的一个元素。NFANFA的接受集的接受集第84页/共152页mcy85例：考虑下面的NFA图。231a aa ab b4 这个NFA接受集与正则表达式ab+|ab*|b*对应的正规集相同。列举两个转换序列都可接受串abb？1a2b4 2b41a3 4 2b4 2b4第85页/共152页mcy86第第2 2章章 词法分析词法分析2.1 词法分析器的作用2.2 正规表达式 2.3 有穷自动机2.4 从正规表达式到DFA 2.5 用代码实现有穷自动机2.6 利用lex自动生成词法分析程序记号的描述工具记号的描述工具记号的识别系统记号的识别系统设计和实现词法设计和实现词法

37、分析程序分析程序作业作业课程设计课程设计1 1 第86页/共152页mcy872.42.4从正规表达式到从正规表达式到DFADFA正规表达式DFA词法分析程序NFA正规式是单词的一种描述工具。由于正规式的简洁性，趋向于先用正规式来描述单词，然后构造等价的有限自动机。有限自动机可以描述输入串被识别的过程，我们可以根据有限自动机构造我们的词法分析程序。第87页/共152页mcy88正规式和有限自动机之间可以相互转换，也就是说它们之间存在着等价性，即：1)1)对于上的NFA M，可以构造一个上的正规式R，使得：L(R)=L(M)2)2)对于上的每个正规式R，可以构造一个上的NFA M，使得：L(M)

38、=L(R)第88页/共152页mcy89NFANFA 到DFADFA中的状态数最小化2.42.4从正规表达式到从正规表达式到DFADFA第89页/共152页mcy90NFANFA从正规表达式到NFA的转化方法按正规式的运算指引构造过程，将正规式分解为一系列子表达式，然后将子表达式对应的NFA依次连接而成，正规式R转化为NFA M 的基本步骤：第90页/共152页mcy91(b)对正规式，等价的NFA为：0 0 1 1 (a)对正规式，等价的NFA为：0 01 1(c)对正规式a，等价的NFA为：0 0a a1 11.基本正规式转换为NFA M的方法：第91页/共152页mcy920 0R R1

39、 12.复合正规式R转换为NFA M的方法：首先将复合正规表达式表示成如下拓广的状态转换图，然后按照正规式的运算(以下(a),(b),(c),(d)四种情况)递归生成NFA M第92页/共152页mcy93(b)若R=rs,则将 代之以 0 01 1rsrs0 01 1r r2 2s s(a)若R=r|s,则将 代之以 0 01 1r|sr|s0 01 1r rs s第93页/共152页mcy94(c)若R=r*,则将 代之以 0 01 1r r*0 01 12 2 r r(d)正规式R=（r）的NFA同正规式 R=r的NFA相同第94页/共152页mcy95例1 1,设有正规表达式R=ab|

40、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 b第95页/共152页mcy96例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 2第96页/共152页mcy97（3 3）0 0(let

41、ter|digit)(letter|digit)1 1letterletter2 2 3 3（4 4）0 0letterletter1 1letterletter2 2 3 3digitdigit第97页/共152页mcy98NFANFA 到DFADFA中的状态数最小化2.42.4从正规表达式到从正规表达式到DFADFA第98页/共152页mcy99NFANFA 到到DFADFA对任一NFA M，总可构造一个DFA M，使 L(M)=L(M)成立。这就是NFA与DFA的等价性。定理 对于字母表 上的任一NFA M，必存在与M等价的DFA M(即有 L(M)=L(M)成立)。在给出具体的构造算法

42、之前先引入状态s和状态集合S的-闭包的概念：第99页/共152页mcy100（1）状态s的-闭包：定义为从s出发可由一系列的零个或多个-转换能达到的状态的集合，并将这个集合记为（2）状态集合S的-闭包:定义为S中各个状态的-闭包的并集s s-第100页/共152页mcy1011 14 42 2a a 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的-闭包：第101页/共152页mcy102从给定的NFA MNFA M构造DFA DFA 的原理是一次尝试所有的可能路径，避免NFANFA的

43、回溯()。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记作：第102页/共152页mcy103M M-1.计算M初始状态s s0 0的-闭包，令其作为 的初始状态：s s0 0-=;T T-S S-=s s0 0-由NFANFA构造DFADFA的子集构造算法步骤如下：第103页/共152页mcy1042.对 中尚未标记的状态 =si1,si2,sim:S S-s si i-s si i-(1)标记 ;(2)对于每个a及 =si1,si2,sim 1)计算sa

44、=t|满足 T(sij,a)=t j 1m，2)进一步计算 sa的 -闭包 sa;-s si i-sa-S S-S S-S S-sa-(3)若 ,则令 =;T T-T T-T T-s si i-sa-(4)令 =(,a)=;开始由标记的状态求新状态第104页/共152页mcy1053.重复步骤2直到 中没有未标记的状态；S S-4.令 =|A A A A-s si i-s si i-第105页/共152页mcy106例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,

45、4,2,4 3 3,2,4,2,41 10 0a aa a0 01 1第106页/共152页mcy107例2 2，考虑下图中的NFA,NFA,试构造与之等价的DFADFA。a ab b状态终结符a ab b001,21,21,21,211110 01 1a a2 2a ab b3 35 54 43 34 45 5第107页/共152页mcy108例3 3，考虑下图中的NFA,NFA,试构造与之等价的DFADFA。0 0letter|digitletter|digit1 1letterletter2 2 3 3状态终结符letterletterdigitdigit002,3,12,3,12,3,

46、12,3,13,13,13,13,13,13,13,13,13,13,1第108页/共152页mcy109letterletterletter|digitletter|digit4 45 56 6letter|digitletter|digit构造的与上述等价的DFADFA如下图所示：第109页/共152页mcy110NFANFA 到DFADFA中的状态数最小化2.42.4从正规表达式到从正规表达式到DFADFA第110页/共152页mcy111DFADFA中的状态数最小化中的状态数最小化结论：对于任何给定的DFADFA，都有一个含有最少状态等价的DFADFA，而且这个最小状态的DFADFA在

47、同构意义下是唯一的。状态集合的等价类：若两个状态s1,s2在DFA中完成相同的识别功能，则可将s1,s2置于同一个等价类中。第111页/共152页mcy112对于任意给定的输入串w，若DFA分别从状态s1,s2出发，能够得到是否接受w的相同的结论，则称状态s1,s2位于同一个等价类，即若从s1出发DFA能接受w,则从s2出发DFA也能接受w，反之，若从s1出发DFA拒绝w,则从s2出发DFA亦拒绝w。否则称状态s1,s2是可区分的。第112页/共152页mcy113DFADFA最小化算法：最小化算法：1.1.首先将状态集合S分为两个等价类：A及S-A；()2.等价类细分：对于当前已经划分的任意

48、等价类K,如果a)或b)条件满足，就将当前划分的等价类K细分为两个更小的等价类K1,K2,并使s1,s2分别落入细分后的不同等价类中；第113页/共152页mcy114a)如果存在输入符号a()，K中的两个状态s1,s2可由a转换到当前已经划分的不同的等价类中；b)如果存在输入符号a()，K中的两个状态s1,s2，当切仅当存在一个状态（s1或s2）对于a 的转换没有意义即T(si,a)=；第114页/共152页mcy1153.3.对于步骤2 2细分之后的所有等价类，递归上述步骤2 2中细分等价类的工作，直到对于同一等价类中的所有状态及任何输入符号a()，我们都不能将其细分到不同的等价类为止。第

49、115页/共152页mcy116对于处于同一等价类中的状态，我们可以选用其中任一状态作为代表即可，等价类中的其他状态皆可省略，同时，把所有引向省略状态的弧引向代表状态。这就是实现DFA最小化的基本原理。第116页/共152页mcy1171 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)=

50、3,T(3,digit)=3;第117页/共152页mcy118letterletter1 13 3letter|digitletter|digit同一等价类2，3中的状态2，3不能被任何输入符号所区分。故状态集合最终划分为两个等价类：2，3，1。最小化后的DFA MDFA M如下图所示。1 1letterletter2 2letter|digitletter|digit3 3letter|digitletter|digit第118页/共152页mcy119例2 2：将下图所示的DFA MDFA M最小化a a0 01 13 32 2a aa aa aa ab bb bb bb b4 41.1