资源描述：
《西安电子科技大学编译原理.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、3)--终态判断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。
2、输出若D接受x，回答“yes”，否则回答“no”。方法用下述过程识别x：算法2.1模拟DFAs:=move(s,ch);ch:=nextchar();s∈F算法2.312.3.3有限自动机的等价定义2.6若有限自动机M和M’识别同一正规集，则称M和M’是等价的，记为M=M’。■正规式(a
3、b)*abb的NFA正规式(a
4、b)*abb的DFA特别提示：正规式与有限自动机从两个侧面表示正规集。正规式是描述，自动机是识别。因此，当它们表示相同集合时，均存在等价的问题。22.4从正规式到词法分析器构造词法分析器的一般方法和步骤：用正规式描述模式（为记号设计正规式）；为每
5、个正规式构造一个NFA，它识别正规式所表示的正规集；将构造的NFA转换成等价的DFA，这一过程也被称为确定化；优化DFA，使其状态数最少，这一过程也被称为最小化；根据优化后的DFA构造词法分析器。问题：1.为何不直接从正规式构造DFA? 2.为何不从NFA直接构造词法分析器？原因：正规式→NFA：有规范的一对一的构造算法DFA→分析器：便于实现记号识别的算法32.4.1从正规式到NFA算法2.2Thompson算法输入字母表∑上的正规式r输出接受L(r)的NFAN方法首先分解r，然后根据下述步骤构造NFA：<1>对ε，构造NFAN(ε)如下。其中，s0为初态，f
6、为终态，此NFA接受{ε}；<2>对∑上的每个字符a，构造NFAN(a)如右上，它接受{a}；<3>若N(P)和N(Q)是正规式P和Q的NFA，则（a）对正规式P
7、Q，构造NFAN(P
8、Q)如下。其中，s0为初态，f为终态，此NFA接受L(P)∪L(Q)；参照P20 正规式定义s0εεfεε42.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）对于正规式
9、(P)，使用P本身的NFA，不再构造新的NFA。■εs0εfεε52.4.1从正规式到NFA（续2）正规式、正规集、NFA的对应关系：正规式正规集NFAε2.a3.P
10、Q4.PQ5.P*6.(P)L(ε)={ε}L(a)={a}L(P)∪L(Q)L(P)L(Q)(L(P))*L(P)s0εεfεεεs0εfεε62.4.1从正规式到NFA（续3）例2.11用Thompson算法构造正规式r=(a
11、b)*abb的NFAN(r)<1>分解正规式<2>自下而上构造NFA强调：构造过程与正规式一一对应构造一个新的NFA最多增加两个状态72.4.2从NFA到DFA<1>N
12、FA识别记号的“并行”方法例2.12从甲地到乙地，可以乘车也可以骑自行车，具体路线如右图。其中c表示乘车，b表示骑自行车。现在要求从甲地到乙地，只许乘车而不许骑自行车，该如何走？问题抽象：识别是否有从甲到乙标记为全c的路径试探（串行）：甲c2无路可走，回退甲c1c3无路可走，回退甲c1c乙到达乙地，成功假设有足够多的小汽车，每次均到达小汽车可能到达的全体并行：甲c{1,2}c{3,乙}到达乙地，成功82.4.2从NFA到DFA（续1）并行的方法，核心思想是将不确定的下一状态确定化：在每试探一步时，考虑了所有的下一状态转移，因此所走的每一步都是确定的。NFA上识别
13、记号的确定化方法确定化的两个方面（回顾DFA定义）计算下一状态转移时：<1>消除ε状态转移：ε-闭包(T)<2>消除多于一个的下一状态转移：smove(S,a)因此，用NFA识别记号，常用并行方法，而不采用串行的方法（算法不易构造，复杂度高且回溯）92.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
14、）3.s5{s2,s4,
