西安电子科技大学编译原理02-3

13)--终态判断2)--循环1)--准备初值2.3.2确定的有限自动机（续3）s:=s0；ch:=nextchar()；whilech≠eofloopendloop;ifthenreturn“yes”;elsereturn“no”;endif;■用算法2.1识别abb：1.s=0,ch=a2.s=1,ch=b3.s=2,ch=b4.s=3,ch=eof5.yes用算法2.1识别abab：1.s=0,ch=a2.s=1,ch=b3.s=2,ch=a4.s=1,ch=b5.s=2,ch=eof6.no输入DFAD和输入字符串x(eof)。D的初态为s0，终态集为F。输出若D接受x，回答“yes”，否则回答“no”。方法用下述过程识别x：算法2.1模拟DFAs:=move(s,ch);ch:=nextchar();s∈F1032aabbbbaa算法2.322.3.3有限自动机的等价定义2.6若有限自动机M和M’识别同一正规集，则称M和M’是等价的，记为M=M’。■0123abbab1032aabbbbaa正规式(a|b)*abb的NFA正规式(a|b)*abb的DFA特别提示：正规式与有限自动机从两个侧面表示正规集。正规式是描述，自动机是识别。因此，当它们表示相同集合时，均存在等价的问题。正规集正规式有限自动机描述识别32.4从正规式到词法分析器构造词法分析器的一般方法和步骤：1.用正规式描述模式（为记号设计正规式）；2.为每个正规式构造一个NFA，它识别正规式所表示的正规集；3.将构造的NFA转换成等价的DFA，这一过程也被称为确定化；4.优化DFA，使其状态数最少，这一过程也被称为最小化；5.根据优化后的DFA构造词法分析器。问题：1.为何不直接从正规式构造DFA?2.为何不从NFA直接构造词法分析器？原因：1.正规式→NFA：有规范的一对一的构造算法2.DFA→分析器：便于实现记号识别的算法42.4.1从正规式到NFA算法2.2Thompson算法输入字母表∑上的正规式r输出接受L(r)的NFAN方法首先分解r，然后根据下述步骤构造NFA：1对ε，构造NFAN(ε)如下。其中，s0为初态，f为终态，此NFA接受{ε}；2对∑上的每个字符a，构造NFAN(a)如右上，它接受{a}；3若N(P)和N(Q)是正规式P和Q的NFA，则（a）对正规式P|Q，构造NFAN(P|Q)如下。其中，s0为初态，f为终态，此NFA接受L(P)∪L(Q)；s0fεs0fa参照P20正规式定义N(P)N(Q)s0εεfεε52.4.1从正规式到NFA（续1）（b）对正规式PQ，构造NFAN(PQ)如下。其中s0为初态，f为终态，此NFA接受L(P)L(Q)；（c）对正规式P*，构造NFAN(P*)如下。其中，s0为初态，f为终态，此NFA接受L(P*)（等价于(L(P))*）；（d）对于正规式(P)，使用P本身的NFA，不再构造新的NFA。■N(P)f’s0N(Q)fsN(Q)fN(P)εs0εfεε62.4.1从正规式到NFA（续2）正规式、正规集、NFA的对应关系：正规式正规集NFA1.ε2.a3.P|Q4.PQ5.P*6.(P)L(ε)={ε}L(a)={a}L(P)∪L(Q)L(P)L(Q)(L(P))*L(P)s0fεs0faN(P)N(Q)s0εεfεεN(P)fs0N(Q)fN(P)εs0εfεε72.4.1从正规式到NFA（续3）例2.11用Thompson算法构造正规式r=(a|b)*abb的NFAN(r)ε1分解正规式2自下而上构造NFA强调：•构造过程与正规式一一对应•构造一个新的NFA最多增加两个状态010124356789abεεεεεεεεabbrr9r10br7r8br5r6ar4*(r3)r1|r2ab82.4.2从NFA到DFA1NFA识别记号的“并行”方法例2.12从甲地到乙地，可以乘车也可以骑自行车，具体路线如右图。其中c表示乘车，b表示骑自行车。现在要求从甲地到乙地，只许乘车而不许骑自行车，该如何走？问题抽象：识别是否有从甲到乙标记为全c的路径试探（串行）：甲c2无路可走，回退甲c1c3无路可走，回退甲c1c乙到达乙地，成功假设有足够多的小汽车，每次均到达小汽车可能到达的全体并行：甲c{1,2}c{3,乙}到达乙地，成功甲乙123ccccbb92.4.2从NFA到DFA（续1）并行的方法，核心思想是将不确定的下一状态确定化：•在每试探一步时，考虑了所有的下一状态转移，因此所走的每一步都是确定的。NFA上识别记号的确定化方法确定化的两个方面（回顾DFA定义）计算下一状态转移时：1消除ε状态转移：ε-闭包(T)2消除多于一个的下一状态转移：smove(S,a)s2as1因此，用NFA识别记号，常用并行方法，而不采用串行的方法（算法不易构造，复杂度高且回溯）s4s5εεas3102.4.2从NFA到DFA（续2）定义2.7状态集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）•smove(S,a)：从状态集S出发，标记为a的下一状态全体。与move(s,a)的唯一区别：用状态集取代状态•ε-闭包(T)：从状态集T出发，不经任何字符达到的状态全体。as3s4s5εεs2as1算法2.4113)2)--循环1)--所有可能初态的集合2.4.2从NFA到DFA（续3）输入NFAN，x（eof），s0，F输出若N接受x，回答“yes”，否则“no”方法用下边的过程对x进行识别。S是一个状态的集合与算法2.1的三点区别：模拟DFA模拟NFA1.开始初态(s0)初态集(S)2.下一状态转移下一状态下一状态集3.结束:判断s∈FS∩F≠Φ算法2.5S:=ε-闭包(smove(S，ch))；--所有下一状态的集合ch:=nextchar();算法2.3模拟NFAS∩F≠Φ算法2.1例2.13在NFA上识别输入序列abb和abab010124356789abεεεεεεεεabbS:=ε-闭包({s0});ch:=nextchar();whilech≠eofloopendloop;ifthenreturn“yes”;elsereturn“no”;endif;■122.4.2NFA到DFA（续4）例2.13在NFA上识别输入序列abb和abab识别abb:1计算初态集：ε-闭包({0})=2A出发经a到达：ε-闭包(smove(A,a))=3B出发经b到达：ε-闭包(smove(B,b))=4C出发经b到达：ε-闭包(smove(C,b))=5结束且D∩{10}={10}，接受。识别的路径为：AaBbCbD010124356789abεεεεεεεεabb算法2.3{0,1,2,4,7}，A{3,8,6,7,1,2,4}，B{5,9,6,7,1,2,4}，C{5,10,6,7,1,2,4}，D132.4.2NFA到DFA（续5）识别abab:1计算初态集：ε-闭包(s0)=2A出发经a到达：ε-闭包(smove(A,a))=3B出发经b到达：ε-闭包(smove(B,b))=4C出发经a到达：ε-闭包(smove(C,a))=5B出发经b到达：ε-闭包(smove(B,b))=识别路径为：AaBbCaBbC。因为C∩{10}=Φ所以不接受010124356789abεεεεεεεεabb{0,1,2,4,7}A{3,8,6,7,1,2,4}B{5,9,6,7,1,2,4}C{3,8,6,7,1,2,4}B{5,9,6,7,1,2,4}C142.4.2NFA到DFA（续6）•“并行”模拟NFA的弱点：每次动态计算下一状态转移的集合，效率低。•改进方法：将NFA上的全部路径均确定化并且记录下来，得到与NFA等价的DFA。•回顾从甲地到乙地的路径，它的数学模型实质上是一个NFA(左下)。2“子集法”构造DFA•可以找到一个等价的DFA(右下)。•它们识别的路径均是：ccccbcbb甲乙123ccccbb甲1,23,乙3乙cbbcb152.4.2NFA到DFA（续7）甲c{1,2}c{3,乙}，接受甲c{1,2}b{3}c?，不接受优点：1.消除了不确定性(将NFA的下一状态集合并为一个状态)2.无需动态计算状态集合(针对模拟NFA的算法)例2.14用DFA识别cc和cbc：甲1,23,乙3乙cbbcb162.4.2NFA到DFA（续8）输入NFAN输出等价的DFAD，其初态是NFA初态的ε闭包，终态是含有NFA终态的状态集合方法用下述过程构造DFA：ε-闭包({s0})是Dstates仅有的状态，且尚未标记;whileDstates有尚未标记的状态Tloop标记T;for每一个字符a--T中向外转移边的标记loopendloop;endloop;■与算法2.3比较：记录了所有状态与状态转移两个数据结构：Dstates(状态)，Dtran(状态转移)算法2.5从NFA构造DFA（子集法）U:=ε-闭包(smove(T，a));ifU非空thenendif;算法2.3Dtran[T，a]:=U;ifU不在Dstates中thenU作为尚未标记的状态加入Dstates;endif;172.4.2NFA到DFA（续9）例2.15用算法2.5构造(a|b)*abb的DFAε-闭包({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}C问题：用哪个DFA识别输入序列？识别abb和abab：AaBbDbE接受AaBbDaBbD不接受010124356789abεεεεεεεεabb1032aabbbbaaBAEDabbbbaCbaaa18算法2.4求ε-闭包输入状态集T。输出状态集T的ε-闭包方法用下边的函数计算ε-闭包functionε-闭包(T)isbeginforT中每个状态tloopendloop;while栈不空loopendloop;returnU;endε-闭包;用算法计算ε-闭包({s2})：Ustack两个数据结构：闭包U和一个堆栈加入t到U;push(t);pop(t);for每个u=move(t,ε)loopendloop;ifu不在U中then加入u到U;push(u);endif;as3s4s5εεs2as11.{s2}s22.{s2,s4}s43.{s2,s4,s5}s54.{s2,s4,s5}返回2)任何smove(ε-闭包(T)，ε)属于ε-闭包(T)；1）T中所有状态属于ε-闭包(T)19定义2.2令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定义如下: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)是正规式，表示的集合仍然是