《com0203-04西安电子科技大学编译原理课件》由会员分享，可在线阅读，更多相关《com0203-04西安电子科技大学编译原理课件（28页珍藏版）》请在金锄头文库上搜索。
1、1上次课主要内容记号的识别：有限自动机 NFA的定义：M =（S，move，s0，F） 直观表示：状态转换图与状态转换矩阵 NFA识别记号：从初态到状态路径上的标记 NFA的不确定性：反复试探，大量回溯 DFA：对NFA施加两条限制，消除了不确定因素 模拟DFA的算法：算法2.1 自动机的等价：识别同一个正规集22.4 从正规式到词法分析器 构造词法分析器的一般方法和步骤： 1.用正规式对模式进行描述； 2. 为每个正规式构造一个NFA，它识别正规式所表示的正规集； 3. 将构造出的NFA转换成等价的DFA，这一过程也被称为确定化 ； 4. 优化DFA，使其状态数最少，这一过程也被称为最小化；
2、 5. 从优化后的DFA构造词法分析器。问题：我们是从DFA构造词法分析器，为何不直接从正规式构 造DFA，而要先构造NFA，然后转换为DFA？原因：机器构造需要规范的算法；正规式NFA：有规范的一对一的构造算法DFA分析器：有便于记号的识别的算法32.4.1 从正规式到NFA 算法2.2 Thompson 算法 输入 字母表上的正规式r 输出 接受L(r)的NFA N 方法 首先分解r，然后根据下述步骤构造NFA：对，构造NFA N()如下。其中，s0为初态，f为终态 ，此NFA接受； 对上的每个字符a，构造NFA N(a)如右上，它接受a ；若N(p)和N(q)是正规式p和q的NFA，则
3、（a） 对正规式p|q，构造NFA N(p|q)如下。其中，s0为初 态，f为终态，此NFA接受L(p)L(q)； 42.4.1 从正规式到NFA（续1）（b） 对正规式pq，构造NFA N(pq)如 右。其中s0为初态，f为终态，此NFA接 受L(p)L(q)； （c） 对正规式p*，构造NFA N(p*)如右。其中，s0为初态， f为终态，此NFA接受L(p*)； 对于正规式(p)，使用p本身的NFA，不再构造新的NFA。52.4.1 从正规式到NFA（续2）正规式与NFA的对应关系： 正规式NFA 1. 表示集合L()=a表示集合L(a)=a1. P|Q表示集合L(P)L(Q)2. PQ
4、表示集合L(P)L(Q)3. P*表示集合(L(P)*4. (r) 仍然表示集合L(r)62.4.1 从正规式到NFA（续3）例2.11 用Thompson算法构造正规式r=(a|b)*abb的NFA N(r) 分解正规式自下而上构造NFA强调： 算法的构造与正规式一 一对应 构造一个新的NFA最多增 加两个状态72.4.2 从NFA到DFA NFA识别记号的“并行”方法例2.12 从甲地到乙地，可以乘小轿车也可以骑自行车，具体 路线如右图。其中c表示乘车，b表示骑自行车。现在要求从 甲地到乙地，只许乘车而不许骑自行车，该如何走？问题抽象：识别是否有从甲到乙标记为全c的路径 试探（串行）：甲
5、c 2 无路可走，退回甲 c 1 c 3 无路可走，退回甲 c 1 c 乙 到达乙地，成功 假设有足够多的小汽车，每次均到达小汽车可能到达的全体 并行： 甲 c 1, 2 c 3, 乙 到达乙地，成功82.4.2 从NFA到DFA（续1）由于并行的方法在每试探一步时，考虑了所有的下一 状态转移，因此所走的每一步都是确定的。用NFA识别记号，并不采用串行的方法（算法不易构 造，复杂度高且回溯），而是采用并行的方法，核心思想 是将不确定的下一状态确定化。NFA上识别记号的确定化方法确定化的两个步骤（回顾DFA定义） 计算下一状态转移时：消除 状态转移：-闭包(T) 消除多于一个的下一状态转移：sm
6、ove(S, a)92.4.2 从NFA到DFA（续2）定义2.6 状态集T的-闭包(T)是一个状态集，且满足： （1） T中所有状态属于-闭包(T)； （2） 任何smove(-闭包(T)，)属于-闭包(T)； （3） 再无其他状态属于-闭包(T)。 根据定义，-闭包(s2)应包括： 1. s2自身s2（1） 2. s4s2, s4（2） 3. s5s2, s4, s5（2） 算法smove(S, a)：从状态集S出发，标记为a的下一状态全 体。与move(s, a)的唯一区别：用状态集取代状态 -闭包(T)：从状态T出发，不经任何字符达到的状态 全体。102.4.2 从NFA到DFA（续3
7、） 输入 NFA N，x（eof）， s0， F 输出 若N接受x，回答“yes”，否则“no” 方法 用下边的过程对x进行识别。S是一个状态的集合 S := -闭包(s0); - 所有可能初态的集合 a := nextchar; while a eof loop end loop; if SF then return “yes”; else return “no”; end if; 与算法2.1的三点区别：模拟DFA模拟NFA1. 开始 初态(s0)初态集(S)2. 下一状态转移 下一状态下一状态集 3. 结束 s is in F SF 算法2.5S:=-闭包(smove(S，a)； - 所
8、有下一状态的集合a := nextchar;算法2.3 模拟NFA112.4.2 NFA到DFA（续4 ）例2.13 在NFA上识别输入序列abb和abab 识别abb: 1 计算初态集： -闭包(0) = 0,1,2,4,7， A 2 从A出发经a到达： -闭包(smove(A, a) = 3,8,6,7,1,2,4， B 3 从B出发经b到达： -闭包(smove(B, b) = 5,9,6,7,1,2,4， C 4 从C出发经b到达： -闭包(smove(C, b) = 5,10,6,7,1,2,4，D 5 结束且D10=10，接受。识别的路径为：A a B b C b D 识别abab
9、: 初态集：-闭包(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 识别路径为：A a B b C a B b C。由于C10=，所以不接受 122.4.2 NFA到DFA（续5）“并行”模拟NFA的弱点：每次动态计算下一状态转移的集 合，效率低。改进方法：将NFA上的全
10、部路径均确定化并且记录下来，得 到与NFA等价的DFA。 回顾从甲地到乙地的路径，它的数学 模型实质上是一个NFA （右上） 。例2.14 用DFA识别cc和cbc： 甲 c 1,2 c 3,乙， 接受 甲 c 1,2 b 3 c ?，不接受 优点：1. 消除了不确定性（将NFA的下一状态集合并为一个状态）2. 无需动态计算状态集合（针对模拟NFA的算法）“子集法”构造DFA可以找到一个等价的DFA（右下）。 它们识别的路径均是： ccccbcbb132.4.2 NFA到DFA（续6） 输入 NFA N 输出 等价的DFA D。初态含有NFA初态，终态集是含有NFA终态的 状态集合 方法 用下
11、述过程构造DFA ： -闭包(s0)是Dstates仅有的状态，且尚未标记; while Dstates有尚未标记的状态T loop 标记T;for 每一个输入字符aloopend loop; end loop; 与算法2.3比较： 记录了所有状态 与状态转移两个数据结构：Dstates(状态)，Dtran(状态转移)算法2.5 从NFA构造DFA（子集法）U := -闭包(smove(T，a); if U非空 then DtranT，a := U; if U不在Dstates中 then U作为尚未标记的状态加入Dstates;end if; end if;142.4.2 NFA到DFA（续
12、7）例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,
13、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： A a B b D b E 接受 A a B b D a B b D 不接受 15上次课主要内容1.正规式NFA：Thompson 算法（算法2.2） 2. NFADFA：子集构造法 确定化的两个步骤： 消除 状态转移：-闭包(T) （算法2.4） 消除多于一个的下一状态转移：smove(S, a) 3. NFA的模拟算法（算法2.3）并行方法 4. 从NFA构造DFA（算法2.5）DFA的构造注意：
14、深刻理解算法的实质，而不是死记几个干条文！162.4.3 最小化DFA 定义2.7 对于任何两个状态t和s，若从一状态出发接受输入字 符串，而从另一状态出发不接受，或者从t出发和从s出发 到达不同的接受状态，则称对状态t和s是可区分的。 反方向思考定义2.7：设想任何输入序列对s和t均是不可区分的，则说明从s 出发和从t出发，分析任何输入序列均得到相同结果。因此，s和t可以合并成一个状态。 引入一个“可区分”的概念：正规式NFADFA算法2.6 最小化DFA的状态数 输入 DFA D=S，move，s0，F。 输出 等价的D=S，move，s0，F（D状态数最少） 方法 执行如下步骤：172.
15、4.3 最小化DFA（续1）1. 初始划分=S-F，F1，F2，Fi是F的子集，接受不同记号 ；2. 应用下述过程构造新的划分new：for 的每一个组G loop 划分G，G的两个状态s和t在同一组中的充要条件是:a.(move(s,a)Gimove(t,a)Gi)；- Gi是中某个组用新划分的组替代G，形成新的划分new；end loop； 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. 删除死状态，即不是终态且对所有输入字符均转向其自身 ，或从初态不可到达的状态。 182.4.3 最小化DFA（续2）最小化DFA算法的主要步骤1.初始划分：终态与非终态； 利用可区分的概念，反复分裂划
