1从正规式到词法分析器构造词法分析器的一般方法和步骤:1用正规式对模式进行描述;2为每个正规式构造一个NFA,它识别正规式所表示的正规集;3将构造出的NFA转换成等价的DFA,这一过程也被称为确定化;4优化DFA,使其状态数最少,这一过程也被称为最小化;5从优化后的DFA构造词法分析器。问题:我们是从DFA构造词法分析器,为何不直接从正规式构造DFA,而要先构造NFA,然后转换为DFA?原因:1机器构造需要规范的算法;2正规式→NFA:有规范的一对一的构造算法3DFA→分析器:有便于记号的识别的算法21从正规式到NFA算法Thompson算法输入字母表∑上的正规式r输出接受L(r)的NFAN方法首先分解r,然后根据下述步骤构造NFA:1对ε,构造NFA如右。其中,s0为初态,f为终态,此NFA接受{ε};s0fε2对∑上的每一个字符a,构造NFA如右s0fa3若N(p)和N(q)是正规式p和q的NFA,则(a)对正规式p|q,构造NFA如右。其中,s0为初态,f为终态,此NFA接受L(p)∪L(q);(b)对正规式pq,构造NFA如右。其中,s0为初态,f为终态,此NFA接受L(p)L(q);N(P)N(Q)s0f(c)对正规式p*,构造NFA如右。其中,s0为初态,f为终态,此NFA接受L(p*);N(P)s0fεεεε4对于正规式(p),使用p本身的NFA,不再构造新的NFA。■s0εεfεεN(P)N(Q)31从正规式到NFA(续1)s0fεs0faN(P)N(Q)s0fN(P)N(Q)s0fN(P)s0fεεεε正规式NFAεaP|QPQP*定义:令Σ是一个有限字母表,则Σ上的正规式及其表示的集合递归定义如下:1.ε是正规式,它表示集合L(ε)={ε}2.若a是Σ上的字符,则a是正规式,它表示集合L(a)={a}3.若正规式r和s分别表示集合L(r)和L(s),则(a)r|s是正规式,表示集合L(r)∪L(s),(b)rs是正规式,表示集合L(r)L(s),(c)r*是正规式,表示集合(L(r))*,(d)(r)是正规式,表示的集合仍然是L(r)。(加括弧改变优先级、结合性)可用正规式描述的语言称为正规语言或正规集。■41从正规式到NFA(续2)[例]用Thompson算法构造正规式r=(a|b)*abb的NFAN(r)r11r9r10br7r8br5r6r4*(r3)r1|r2aba23a45b1εε6εε0ε7εεε8a9b10b1分解正规式2自下而上构造NFA强调:1算法的构造与正规式一一对应2构造一个新的NFA最多增加两个状态52从NFA到DFA1NFA识别记号的“并行”方法[例]从甲地到乙地,可以乘小轿车也可以骑自行车,具体路线如上。其中c表示乘车,b表示骑自行车。现在要求从甲地到乙地,只许乘车而不许骑自行车,该如何走?(即识别是否有从甲到乙标记为cc的路径)甲乙123ccccbb试探(串行方式):甲c2无路可走,退回甲c1c3无路可走,退回甲c1c乙到达乙地,成功并行(假设有足够的小汽车,每次都是到达小汽车可能到达的全体)甲c{1,2}c{3,乙}到达乙地,成功由于并行的方法在每试探一步时,考虑了所有的下一状态转移,因此所走的每一步都是确定的。用NFA识别记号,并不采用串行的方法(算法不易构造,复杂度高且回溯),而是采用并行的方法,核心思想是将不确定的下一状态确定化。6NFA上识别记号的确定化方法2从NFA到DFA(续1)确定化的两个步骤(回顾DFA定义)计算下一状态转移时:1消除ε状态转移:ε-闭包(T)2消除多于一个的下一状态转移:smove(S,a)smove(S,a):从状态集S出发,标记为a的下一状态全体。与move(s,a)的唯一区别:用状态集取代状态ε-闭包(T):从状态T出发,不经任何字符达到的状态全体。s1s2as3as4s5εε定义状态集T的ε-闭包(T)是一个状态集,且满足:(1)T中所有状态属于ε-闭包(T);(2)任何smove(ε-闭包(T),ε)属于ε-闭包(T);(3)再无其他状态属于ε-闭包(T)。■根据定义,上图中ε-闭包({s2})应该包括:1.s2自身{s2}(1)2.s4{s2,s4}(2)3.s5{s2,s4,s5}(2)算法7算法模拟NFA2从NFA到DFA(续2)输入NFAN,x(eof),s0,F输出若N接受x,回答“yes”,否则“no”方法用下边的过程对x进行识别。S是一个状态的集合S:=ε-闭包({s0});--所有可能初态的集合a:=nextchar;whilea≠eofloopS:=ε-闭包(smove(S,a));--所有下一状态的集合a:=nextchar;endloop;ifS∩F≠Φthenreturn“yes”;elsereturn“no”;endif;算法2.582NFA到DFA(续3)[例]在NFA上识别输入序列abb和abab23a45b1εε6εε0ε7εεε8a9b10b识别abb:1计算初态集ε-闭包({0})={0,1,2,4,7},A2从A出发经a到达ε-闭包(smove(A,a))={3,8,6,7,1,2,4},B3从B出发经b到达:ε-闭包(smove(B,b))={5,9,6,7,1,2,4},C4从C出发经b到达:ε-闭包(smove(C,b))={5,10,6,7,1,2,4},D5结束且D∩{10}={10},接受。识别的路径为:AaBbCbD识别abab:初态集:ε-闭包(s0)={0,1,2,4,7}A从A出发经a到达:ε-闭包(smove(A,a))={3,8,6,7,1,2,4}B从B出发经b到达:ε-闭包(smove(B,b))={5,9,6,7,1,2,4}C从C出发经a到达:ε-闭包(smove(C,a))={3,8,6,7,1,2,4}B从B出发经b到达:ε-闭包(smove(B,b))={5,9,6,7,1,2,4}C识别路径为:AaBbCaBbC。由于C∩{10}=Φ,所以不接受92“子集法”构造DFA2NFA到DFA(续4)“并行”模拟NFA的弱点:每次动态计算下一状态转移的集合,效率低。改进方法:将NFA上的全部路径均确定化并且记录下来,得到与NFA等价的DFA。甲乙123ccccbb甲1,23,乙3乙cbcbb回顾从甲地到乙地的路径,它的数学模型实质上是一个NFA(右上)。可以找到一个等价的DFA(右下),它们识别的路径均是:ccccbcbb[例]用DFA识别cc和cbc:甲c{1,2}c{3,乙},接受甲c{1,2}b{3}c?,不接受优点:1.消除了不确定性(将NFA的下一状态集合并为一个状态)2.无需动态计算状态集合(针对模拟NFA的算法)10算法从NFA构造DFA(子集法)2NFA到DFA(续5)输入NFAN输出等价的DFAD。初态含有NFA初态,终态集是含有NFA终态的状态集合方法用下述过程构造DFA:ε-闭包({s0})是Dstates仅有的状态,且尚未标记;whileDstates有尚未标记的状态Tloop标记T;for每一个输入字符aloopU:=ε-闭包(smove(T,a));ifU不在Dstates中thenU作为尚未标记的状态加入Dstates;endif;Dtran[T,a]:=U;--记录状态转移endloop;endloop;■两个数据结构:Dstates(状态),Dtran(状态转移)112NFA到DFA(续6)[例]构造(a|b)*abb的DFA010124356789abεεεεεεεεabbε-闭包({0})={0,1,2,4,7}*Aε-闭包(smove(A,a))={3,8,6,7,1,2,4}*Bε-闭包(smove(A,b))={5,6,7,1,2,4}*Cε-闭包(smove(B,a))={3,8,6,7,1,2,4}Bε-闭包(smove(B,b))={5,9,6,7,1,2,4}*Dε-闭包(smove(C,a))={3,8,6,7,1,2,4}Bε-闭包(smove(C,b))={5,6,7,1,2,4}Cε-闭包(smove(D,a))={3,8,6,7,1,2,4}Bε-闭包(smove(D,b))={5,10,6,7,1,2,4}*Eε-闭包(smove(E,a))={3,8,6,7,1,2,4}Bε-闭包(smove(E,b))={5,6,7,1,2,4}C1032aabbbbaa问题:用哪个DFA识别输入序列?识别abb和abab:AaBbDbE接受AaBbDaBbD不接受ABabCaDbabaEbab123最小化DFA定义:对于任何两个状态t和s,若从一状态出发接受输入字符串ω,而从另一状态出发不接受ω,或者从t出发和从s出发到达不同的接受状态,则称ω对状态t和s是可区分的。■反方向思考定义:设想任何输入序列ω对s和t均是不可区分的,则说明从s出发和从t出发,分析任何输入序列ω均得到相同结果。因此,s和t可以合并成一个状态。引入一个“可区分”的概念:正规式-NFA-DFA13算法最小化DFA的状态数3最小化DFA(续1)输入DFAD={S,∑,move,s0,F}。输出等价的D’={S’,∑,move‘,s0’,F‘},(D’状态数最少)方法执行如下步骤:1.初始划分Π={S-F,F1,F2,...},Fi是F的子集,接受不同记号;2.应用下述过程构造新的划分Πnew:forΠ的每一个组Gloop划分G,G的两个状态s和t在同一组中的充要条件是:a.(move(s,a)∈Gi∧move(t,a)∈Gi);--Gi是Π中某个组用新划分的组替代G,形成新的划分Πnew;endloop;3.若Πnew=Π,令Πfinal=Π,转4;否则令Π=Πnew并重复步骤2;4.在Πfinal每个组Gi中选一个代表si',使得D中从Gi所有状态出发的状态转移在D'中均从si'出发,D中所有转向Gi中的状态转移在D'中均转向si';含有D中s0的状态组G0的代表s0'称为D'的初态,D中所有含F中状态的Gj的代表sj'构成D'的终态集F';5.删除死状态,即不是终态且对所有输入字符均转向其自身,或从初态不可到达的状态。■14最小化DFA算法的主要步骤:3最小化DFA(续2)①初始划分:终态与非终态;②利用可区分的概念,反复分裂划分中的组Gi,直到不可再分裂;③由最终划分构造D',关键是选代表和修改状态转移;④消除可能的死状态和不可达状态。BAEDabbbbaCbaaa[例]用算法2.6化简DFAm(A,a)=B,m(A,b)=Cm(B,a)=B,m(B,b)=Dm(C,a)=B,m(C,b)=Cm(D,a)=B,m(D,b)=Em(E,a)=B,m(E,b)=C1.初始化划分Π1={ABCD,E}2.根据算法中步骤2,反复分裂划分中的组:①∵m(D,b)=E∴Π2={ABC,D,E}②∵m(B,b)=D∴Π3={AC,B,D,E}③Π3?于是:Πfinal={AC,B,D,E}4.根据Πfinal构造D':①选代表,用A代表AC组;②修改状态转移:m(A,a)=B,m(A,b)=Am(B,a)=B,m(B,b)=Dm(D,a)=B,m(D,b)=Em(E,a)=B,m(E,b)=A用0、1、2、3代替A、B、D、E,得:1032aabbbbaa154由DFA构造词法分析器1表驱动型的词法分析器驱动器(算法2.1)输入字符序列分析表(DFA)记号流其中,需要:1.有适当的数据结构存放DFA;2.修改算法2.1,以适应实际输入:①识别整个文件,而不是一个记号;②满足最长匹配原则。对于输入序列:result:=a+b正确的识别:id:=id+id错误的识别:1.仅识别一个:id(result)2.不满足最长匹配:idid...(r或re或res...)162直接编码的词法分析器在表驱动的词法分析器中,DFA是被动的,需要一个驱动器来模拟D