第二章词法分析非确定有限自动机优秀PPT.ppt
第二章词法分析非确定有限自动机第一页，本课件共有29页第2章 outlinep一、词法分析概述一、词法分析概述1 1，词法分析程序的功能，词法分析程序的功能2 2，词法分析相关的一些问题，词法分析相关的一些问题p二、正则表达式二、正则表达式p三、有限自动机三、有限自动机1 1，确定有限自动机，确定有限自动机DFADFA2 2，非确定有限自动机，非确定有限自动机NFANFA，NFANFA到到DFADFA的转换的转换3 3，DFADFA的化简的化简4 4，正则表达式到，正则表达式到NFANFA的转换的转换p四、词法分析程序构造四、词法分析程序构造 第二页，本课件共有29页2、非确定有限自动机确定有限自动机是五元组确定有限自动机是五元组(SS,SS,S0,TS,S0,TS)确定性体现：初始状态唯一、转换函数是单值函数确定性体现：初始状态唯一、转换函数是单值函数非确定有限自动机：也是五元组非确定有限自动机：也是五元组(SS,SS,S0,TS,S0,TS)其中 SS=S0,S1,SnSS=S0,S1,Sn是状态集是状态集 是字母表是字母表 S0S0 SSSS是初始状态集是初始状态集,不能为空不能为空 是转换函数，但不要求是单值的是转换函数，但不要求是单值的 :SS:SS ()2 2SSSS TS TS SSSS是终止状态集，可为空。是终止状态集，可为空。第三页，本课件共有29页非确定有限自动机的例子 =a,a,b b SS:SS:S0,S0,S1,S1,S2,S2,S3S3 初始状初始状态态集集:S0S0 ,S1S1 终终止状止状态态集集:S3S3 :(S0,a)(S0,a)S1,S1,S3S3,(S0,(S0,)S2,S2,(S1,b)(S1,b)S1,S1,(S1,(S1,)S2,S2,(S2,(S2,)S3,S3,(S3,(S3,b)b)S3S3NFANFA也可以用状也可以用状态转换图态转换图或状或状态转换态转换矩矩阵阵表示表示第四页，本课件共有29页非确定有限自动机的例子S0S0a aS2S2S3S3 a a b bb bS1S1abS+S1,S3S2S1+S1S2S2S3S3-S3状态集合状态集合第五页，本课件共有29页NFA接受的字符串NFANFA接受的字符串接受的字符串如果M是一个NFA,a a1 1 a a2 2 anan 是一个字符串，如果存在一个状态序列(S0,S1,Sn),满足 S0 S1 ,S1 S2 ,Sn-1 Sn其中 S0 是开始状态之一，Sn 是接受状态之一，则串a1 a2 an 被NFA M接受.NFANFA定定义义的串的集合的串的集合(NFA(NFA接受的接受的语语言言)NFA M接受的所有串的集合，称为M定义的语言，记为 L(M)L(M)a1a1a2a2anan第六页，本课件共有29页NFA与DFA的比较DFADFANFANFA初始状初始状态态一个初始状一个初始状态态初始状初始状态态集合集合 边边不允不允许许允允许许 (S,(S,a)a)S S or or S1,S1,SnSn or or 实现实现容易容易有不确定性有不确定性对于确定的输入串，DFA只有一条路径接受它NFA则可能需要在多条路径中进行选择！第七页，本课件共有29页NFA到DFA的转换例如输入串：100NFANFA需要在多条路径中选择，因此的效率低！但NFA描述问题方便。NFA和DFA都识别正则语言。NFA可转换成DFA。SPQ010101第八页，本课件共有29页NFA到DFA的转换对任意对任意NFANFA，都存在一个，都存在一个DFADFA与之等价。与之等价。转换的思想：消除不确定性转换的思想：消除不确定性合并初始状态集成一个状态合并初始状态集成一个状态消除消除 边边消除多重定义的边。消除多重定义的边。1 12 23 3a aa a1 12,32,3a a4 45 5 4 4，5 5第九页，本课件共有29页-closure(-closure(空空闭闭包包)对对于于给给定的定的 NFANFA A A,和它的一个状和它的一个状态态集合集合 SSSS,SSSS的空的空闭闭包包计计算如下：算如下：第一步：令第一步：令-closure(-closure(SSSS)=SSSS;第二步：如果在状第二步：如果在状态态集集SSSS中存在状中存在状态态s s,s s到状到状态态s s 存在一条存在一条 边边，并且并且s s -closure(-closure(SSSS ),),则则将将s s 加入加入SSSS的空的空闭闭包包-closure(-closure(SSSS););重复第二步重复第二步,直到再没有状直到再没有状态态可加入可加入-closure(-closure(SSSS).第十页，本课件共有29页-closure-closure的例子的例子S0S0a aS1S1S2S2S3S3 a a b bc c -closure(S0,S1)=S0,S1 S0,S1,S2 S0,S1,S2 S0,S1,S2,S3 第十一页，本课件共有29页转转向状向状态态对对于于NFANFA A A中的中的给给定状定状态态集合集合SSSS 和符号和符号 a a,NextStates(NextStates(SSSS,a a)=s s|对对于状于状态态集集SSSS中的一个状中的一个状态态s1,s1,如果如果A A中存中存在一条从在一条从s1s1到到s s的的a a转换边转换边 SSS2S3S1S1S SSSa aa a(S1,S2,S3,a)=S,S第十二页，本课件共有29页转向状态的例子S0S0a aS1S1S2S2S3S3 a a b bc c NextStates(S0,S1,a)=S1,S3 NextStates(S0,S1,b)=S1 第十三页，本课件共有29页NFANFA到到DFADFA的的转换转换算法算法(子集法子集法)给给定一个定一个 NFANFA A A =,SS,SS,SSSS0 0,TSTS 生成等价的生成等价的 DFADFA A A =,SS,SSS,S0 0,TSTS 步步骤骤(1)(1)令令S S0 0 =-closure(-closure(SSSS0 0),),将将S S0 0 加入加入 SSSS;(2)(2)从从SSSS中中选择选择一个状一个状态态s,s,对对于任意于任意 a a,若有若有 s s =-closure(-closure(NextStates(NextStates(s,s,a a),),令令 (s,(s,a)a)s s。若。若s s SS,SS,将将s s加入加入SS;SS;(3)(3)重复第二步，直到重复第二步，直到SSSS 中的所有状态都被处理过中的所有状态都被处理过;(4)(4)对对于于SSSS中的一个状中的一个状态态s,s,如如s s =S1,S1,.,.,Sn,Sn,如果有状如果有状态态 Si Si TS,TS,则则s s是是 A A 的一个接受状态的一个接受状态,将将s s加入加入 TS;TS;第十四页，本课件共有29页NFA到DFA转换的例子例1：=a,b,c,=a,b,c,S0=S0=-closure(S-closure(S0 0,S1,S10 0)=S S0 0,S1,S10 0,S2,S,S2,S*,abc S S0,S1,S1,S2,SS2,S3 +-S1,S1,S S3,S2,S2 S1,S1,S S3,S2,S2 S S3 S1,S1,S S3,S2,S2-S1,S1,S S3,S2,S2 S S3 S S3-S S3 S0S0a aS1S1S2S2S3S3 a a b bc c第十五页，本课件共有29页NFA到DFA转换的例子例2：01S0+S0,S1S0S0,S1-S0,S1,S2S0S0,S1,S2-S0,S1,S2S0S0S0S1S1S2S2SPQ010101第十六页，本课件共有29页NFA到DFA转换的例子例3：q q0 0q q1 1q q4 4q q6 6q q2 2q q3 3q q5 5a aa aa ab bb bb b a,ba,babq0+q1,q3q1,q3q1,q3q2,q4,q6,q5q2,q4,q6,q5-q4,q6,q5q6,q5,q4q4,q6,q5-q6,q5,q4q6,q5,q4第十七页，本课件共有29页DFA的化简NFANFA转换成的转换成的DFADFA，有时候会有一些，有时候会有一些等价状态等价状态，这，这些等价状态会使分析效率降低，因此应合并。些等价状态会使分析效率降低，因此应合并。合并了所有等价状态后的合并了所有等价状态后的DFADFA称为最简自动机。称为最简自动机。q q0 0a aq qA Aq qc cq qB Ba aa,ba,bb ba ab bDFA M1DFA M1第十八页，本课件共有29页等价等价DFADFA和最简和最简DFADFA的定义的定义等价等价 DFAsDFAs如果两个如果两个DFADFA接受的字符串的集合是相同的接受的字符串的集合是相同的;在接受相同字符串集的在接受相同字符串集的DFADFA中，最小中，最小DFADFA指的是状指的是状态态数数最少的最少的DFADFAq q0 0a aq qA Aq qc ca,ba,bb bDFA M2DFA M2a a第十九页，本课件共有29页等价的等价的DFAsDFAsS S0 0a aS1S1S4S4*b bd dS3S3*S2S2d dS S0 0a aS1S1b bd dS S*两个两个DFADFA等价，是因为在这两个等价，是因为在这两个DFADFA中存在接中存在接受相同字符串的状态受相同字符串的状态!第二十页，本课件共有29页主要思想主要思想等价状等价状态态对对于于DFADFA中的任意两个状中的任意两个状态态 s1s1和和 s2s2，如果分，如果分别别将将 s1s1和和s2s2当作开当作开始状始状态态，它，它们们接受的字符串集合相同，接受的字符串集合相同，则则称称 s1s1 和和 s2s2 是是等价状等价状态态;DFADFA化化简简的两种方式的两种方式合并等价状合并等价状态态;(状状态态合并法合并法)分离不等价状分离不等价状态态;(;(状状态态分离法分离法)第二十一页，本课件共有29页状状态态分离法化分离法化简简DFADFA给给定一个定一个DFADFA A A =,SS,SS,S S0 0,TSTS：要生成与其等价的要生成与其等价的 DFADFA A A =,SS,SSS,S0 0,TSTS 分离步分离步骤骤：(1)(1)将将A A的所有状的所有状态态分成两分成两组组：非非终终止状止状态态 ,终终止状止状态态 ;(2)(2)选择选择一一组组状状态态 SSSSi i =Si1,Si1,Sin,Sin,用用splitsplit(SS(SSi i)替替换换SSSSi i ;(3)(3)重复第重复第(2)(2)步，直到步，直到所有组都被处理过所有组都被处理过;(4)(4)令令SSSS =组组的集合的集合;(5)(5)S S0 0 ：包含包含S S0 0 的组作为的组作为S S0 0 ;(6)(6)TSTS :包含包含A A的的终终止状止状态态的的组组，作作为为A A 的的终终止状止状态态;(7)(7):（SSSSi i,a a）=SSSSj j,若在若在A A中有中有S Si i S Sj j,且且 si si SSSSi i,sj sj SSSSj ja a第二十二页，本课件共有29页分离状分离状态态 给给定一个定一个DFADFA A A =,SS,SS,S S0 0,TSTS：假定状假定状态态集合集合SSSS分成了分成了m m组组：SSSS1 1,SSSSm m,SSSS1 1 SSSSm m =SS,SS,SSSS1 1 SSSSm m =;任取一个状任取一个状态组态组SSSSi i =S Si1 i1,S Sin in,考察考察SSSSi i是否可是否可继续继续分离分离splitsplit(SS(SSi i)：判断：判断SSiSSi是否需要分裂，是是否需要分裂，是则则将将SSiSSi分裂成两分裂成两组组G1G1和和G2,G2,过过程如下：程如下：初始初始 G1G1 =S Sip ip ,1 1 p p n n ,即任取即任取SSSSi i中的一个状中的一个状态态放入放入G1,G1,G2G2 =.forfor j j =1 1 to to n n (假假设设 SSSSi i 有有n n个状个状态态)对对于所有于所有 a a ,任意的任意的S Sij ij SSSSi i,若有若有 (S(Sip ip,a,a )=SkSk ，(S(Sij ij,a)a)=SqSq ，如果如果 SkSk和和SqSq属于同一个组属于同一个组 SSSSt t ,则将则将 SijSij 加入组加入组 G1;G1;否则将否则将 SijSij 加入组加入组 G2;G2;第二十三页，本课件共有29页简单简单例子例子S S0 0a aS1S1S4S4*b bd dS3S3*S2S2d dSS0 0,S1,S2,S3,S1,S2,S3*,S4,S4*SS0 0,S1,S2,S1,S2,S3 S3*,S4,S4*第二十四页，本课件共有29页DFA化简的例子例1：0，1，2，3和40,1,3,2和40,3,1,2和401234aabbabbb0124aabbbb第二十五页，本课件共有29页DFA化简的例子例2：0，1，2，3，40，2、1，3，40，2，1，3，4a a 4 4 0 01 12 2a aa ab ba ab bb bb b3 3a a，b b 4 4 0 01 12 2a aa ab ba ab bb ba a，b b第二十六页，本课件共有29页DFA化简的例子例3：A,D,E,B,CA,E,D和B,C第二十七页，本课件共有29页课后练习NFA到DFA的转化0123aaba,ba,ba,b0123abba第二十八页，本课件共有29页课后练习DFA的化简 :1,3,2,4,5,61 12 24 46 65 53 3a ab ba ab bb bb bb bb ba a第二十九页，本课件共有29页
