上次课主要内容 正规式的简化形式与辅助定义； 记号的识别：有限自动机 NFA的定义：M =（S，∑，move，s0，F）

Presentation on theme: "上次课主要内容 正规式的简化形式与辅助定义； 记号的识别：有限自动机 NFA的定义：M =（S，∑，move，s0，F）"— Presentation transcript:

1 上次课主要内容 正规式的简化形式与辅助定义； 记号的识别：有限自动机 NFA的定义：M =（S，∑，move，s0，F）
直观表示：状态转换图与状态转换矩阵 NFA识别记号：从初态到终态路径上的标记 NFA的不确定性：反复试探，大量回溯 DFA：对NFA施加两条限制，消除了不确定因素 模拟DFA的算法：算法2.1 自动机的等价：识别同一个正规集

2 2.4 从正规式到词法分析器 构造词法分析器的一般方法和步骤： 用正规式对模式进行描述；
为每个正规式构造一个NFA，它识别正规式所表示的正规集； 将构造的NFA转换成等价的DFA，这一过程也被称为确定化； 优化DFA，使其状态数最少，这一过程也被称为最小化； 从优化后的DFA构造词法分析器。 问题： 我们是从DFA构造词法分析器，为何不直接从正规式构造DFA，而要先构造NFA，然后转换为DFA？ 原因： 机器构造需要规范的算法； 正规式→NFA：有规范的一对一的构造算法 DFA→分析器：有便于记号识别的算法

3 2.4.1 从正规式到NFA 算法2.2 Thompson 算法 输入 字母表∑上的正规式r 输出 接受L(r)的NFA N
<1> 对ε，构造NFA N(ε)如下。其中，s0为初态，f为终态，此NFA接受{ε}； <2> 对∑上的每个字符a，构造NFA N(a)如右上，它接受{a} ； <3> 若N(p)和N(q)是正规式p和q的NFA，则 （a） 对正规式p|q，构造NFA N(p|q)如下。其中，s0为初态，f为终态，此NFA接受L(p)∪L(q)；

4 2.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*)； <4> 对于正规式(p)，使用p本身的NFA，不再构造新的NFA。 ■

5 2.4.1 从正规式到NFA（续2） 正规式与NFA的对应关系： 正规式 NFA ε表示集合L(ε)={ε} a表示集合L(a)={a} P|Q表示集合L(P)∪L(Q) PQ表示集合L(P)L(Q) P*表示集合(L(P))* (r) 仍然表示集合L(r)

6 例2.11 用Thompson算法构造正规式r=(a|b)*abb的NFA N(r)
<1> 分解正规式 <2> 自下而上构造NFA 强调： 算法的构造与正规式一一对应 构造一个新的NFA最多增加两个状态 先板书后播放

7 2.4.2 从NFA到DFA <1> NFA识别记号的“并行”方法
例2.12 从甲地到乙地，可以乘小轿车也可以骑自行车，具体路线如右图。其中c表示乘车，b表示骑自行车。现在要求从甲地到乙地，只许乘车而不许骑自行车，该如何走？ 问题抽象：识别是否有从甲到乙标记为全c的路径 试探（串行）： 甲 c 无路可走，退回 甲 c 1 c 3 无路可走，退回 甲 c 1 c 乙 到达乙地，成功 假设有足够多的小汽车，每次均到达小汽车可能到达的全体 并行： 甲 c {1, 2} c {3, 乙} 到达乙地，成功

8 2.4.2 从NFA到DFA（续1） 由于并行的方法在每试探一步时，考虑了所有的下一状态转移，因此所走的每一步都是确定的。 用NFA识别记号，并不采用串行的方法（算法不易构造，复杂度高且回溯），而是采用并行的方法，核心思想是将不确定的下一状态确定化。 NFA上识别记号的确定化方法 确定化的两个步骤（回顾DFA定义） 计算下一状态转移时： <1> 消除ε 状态转移：ε-闭包(T) <2> 消除多于一个的下一状态转移：smove(S, a)

9 2.4.2 从NFA到DFA（续2） smove(S, a)：从状态集S出发，标记为a的下一状态全体。与move(s, a)的唯一区别：用状态集取代状态 ε-闭包(T)：从状态T出发，不经任何字符达到的状态全体。 定义2.6 状态集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） 算法2.4

10 2.4.2 从NFA到DFA（续3） 算法2.3 模拟NFA 输入 NFA N，x（eof）， s0， F 输出 若N接受x，回答“yes”，否则“no” 方法 用下边的过程对x进行识别。S是一个状态的集合 S := ε-闭包({s0}); 所有可能初态的集合 a := nextchar; while a ≠ eof loop end loop; if then return “yes”; else return “no”; end if; ■ S:=ε-闭包(smove(S，a))； -- 所有下一状态的集合 a := nextchar; S∩F≠Φ 与算法2.1的三点区别：模拟DFA 模拟NFA 1. 开始 初态(s0) 初态集(S) 2. 下一状态转移 下一状态 下一状态集 3. 结束 s is in F S∩F≠Φ 算法2.1 算法2.5

11 例2.13 在NFA上识别输入序列abb和abab
2.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 结束且D∩{10}={10}，接受。 识别的路径为：A a B b C b D 算法2.3的三个关键步骤（写在黑板上）： 初态： S := ε-闭包({s0}) a := nextchar; 循环： S:=ε-闭包(smove(S，a))； -- 所有下一状态的集合 判断： S∩F≠Φ 算法2.3

12 A出发经a到达：ε-闭包(smove(A,a))={3,8,6,7,1,2,4} B
2.4.2 NFA到DFA（续5） 识别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 识别路径为：A a B b C a B b C。 因为C∩{10}=Φ所以不接受

13 2.4.2 NFA到DFA（续6） <2> “子集法”构造DFA “并行”模拟NFA的弱点：每次动态计算下一状态转移的集合，效率低。 改进方法：将NFA上的全部路径均确定化并且记录下来，得到与NFA等价的DFA。 回顾从甲地到乙地的路径，它的数学模型实质上是一个NFA (左下) 。 可以找到一个等价的DFA(右下)。 它们识别的路径均是：cc ccb cbb

14 2.4.2 NFA到DFA（续7） 例2.14 用DFA识别cc和cbc： 甲 c {1,2} c {3,乙}， 接受 甲 c {1,2} b {3} c ?，不接受 优点： 消除了不确定性(将NFA的下一状态集合并为一个状态) 无需动态计算状态集合(针对模拟NFA的算法)

15 2.4.2 NFA到DFA（续8） 算法2.3 算法2.5 从NFA构造DFA（子集法）
两个数据结构：Dstates(状态)，Dtran(状态转移) 输入 NFA N 输出 等价的DFA D。初态含有NFA初态，终态集是含有NFA终态的 状态集合 方法 用下述过程构造DFA ： ε-闭包({s0})是Dstates仅有的状态，且尚未标记; while Dstates有尚未标记的状态T loop 标记T; for 每一个字符a -- T中向外转移边的标记 loop end loop; end loop; ■ U := ε-闭包(smove(T，a)); if U非空 then Dtran[T，a] := U; if U不在Dstates中 then U作为尚未标记的状态加入Dstates; end if; 与算法2.3比较： 记录了所有状态 与状态转移 保留此屏，构造(a|b)*abb的DFA ，然后进入下一屏 算法2.3

16 2.4.2 NFA到DFA（续9） 例2.15 用算法2.5构造(a|b)*abb的DFA 问题：用哪个DFA识别输入序列？
ε-闭包(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： A a B b D b E 接受 A a B b D a B b D 不接受

17 结束（2007年3月 日）

18 上次课主要内容 DFA的构造 正规式－NFA：Thompson 算法（算法2.2） NFA－DFA：子集构造法 确定化的两个步骤：
消除多于一个的下一状态转移：smove(S, a) NFA的模拟算法（算法2.3）－并行方法 从NFA构造DFA（算法2.5） 其中算法2.3和算法2.5： 共同点：确定化，即ε-闭包(smove(S, a)) 区别：一条路径的确定化与全部路径的确定化 注意：深刻理解算法的实质，而不是死记几个干条文！

19 2.4.3 最小化DFA 正规式－NFA－DFA 引入一个“可区分”的概念：
定义2.7 对于任何两个状态t和s，若从一状态出发接受输入字符串ω，而从另一状态出发不接受ω，或者从t出发和从s出发到达不同的接受状态，则称ω对状态t和s是可区分的。 ■ 反方向思考定义2.7： 设想任何输入序列ω对s和t均是不可区分的，则说明从s出发和从t出发，分析任何输入序列ω均得到相同结果。 因此，s和t可以合并成一个状态。

20 输入 DFA D={S，∑，move，s0，F}。 输出 等价的D’={S’，∑，move’，s0’，F’}（D’状态数最少）
方法 执行如下步骤： 1. 初始划分Π={S-F，F1，F2，..}， 其中，Fi是F的子集，接受不同记号； 2. 应用下述过程构造新的划分Πnew： for Π的每一个组G loop 划分G，G的两个状态s和t在同一组中的充要条件是: a.(move(s,a)∈Gi∧move(t,a)∈Gi)；-- Gi是Π中的组 用新划分的组替代G，形成新的划分Πnew； end loop； 3.若 Πnew=Π 则 Πfinal:=Π且转4； 否则 Π=:Πnew 且转2；

21 2.4.3 最小化DFA（续1） 4. 在Πfinal每个组Gi中选一个代表si’，使得D中从Gi所有状态出发的状态转移在D’中均从si’出发，D中所有转向Gi中的状态转移在D’中均转向si’。 含有D中s0的状态组G0的代表s0'称为D'的初态，D中所有含F中状态的Gj的代表sj'构成D'的终态集F'； 5. 删除死状态，即不是终态且对所有输入字符均转向其自身，或从初态不可到达的状态。 ■ D D'

22 2.4.3 最小化DFA（续2） 最小化DFA算法的主要步骤 初始划分：终态与非终态； 利用可区分的概念，反复分裂划分中的组Gi，直到不可再分裂； 由最终划分构造D'，关键是选代表和修改状态转移； 消除可能的死状态和不可达状态。

23 2.4.3 最小化DFA（续3） 例2.17 用算法2.6化简DFA 1．初始化划分Π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} m(A,a)=B, m(A,b)=C m(B,a)=B, m(B,b)=D m(C,a)=B, m(C,b)=C m(D,a)=B, m(D,b)=E m(E,a)=B, m(E,b)=C 4．根据Πfinal构造D'： ① 选代表，用A代表AC组； ② 修改状态转移： 用0、1、2、3 代替A、B、D、E： m(A,a)=B, m(A,b)=A m(B,a)=B, m(B,b)=D m(D,a)=B, m(D,b)=E m(E,a)=B, m(E,b)=A

24 2.4.4 由DFA构造词法分析器 <1> 表驱动型的词法分析器 其中，需要： 1. 有适当的数据结构存放DFA；
2.修改算法2.1，适应实际输入： 识别整个文件，而不是一个记号； 满足最长匹配原则。 对于输入序列： result := a + b 正确的识别：id := id + id 错误的识别： 1. 仅识别一个： id （result） 2. 不满足最长匹配：id id ...（r或re或res ... ）

25 <2> 直接编码的词法分析器 在表驱动的词法分析器中，DFA是被动的，需要一个驱动器来模拟DFA的行为，以实现对输入序列的分析。 直接编码的词法分析器，将DFA和DFA识别输入序列的过程合并在一起，直接用程序代码模拟DFA识别输入序列的过程。 问题： 如何用程序模拟DFA识别输入序列的过程？即如何用程序模拟DFA的状态和它的状态转移？ 1. 状态和状态转移与语句的对应关系 ① 初态→程序的开始； ② 终态→程序的结束（不同终态return不同记号）； ③ 状态转移→分情况或者条件语句（case/if）； ④ 环→循环语句（loop）； ⑤ return满足最长匹配原则。

26 <2> 直接编码的词法分析器（续1）
2. 识别(a|b)*abb的程序框架 void main(){ char buf[]="aba#", *ptr=buf; while (*ptr!='#' ) { l0: while (*ptr=='b') ptr++; // state 0 l1: while (*ptr=='a') ptr++; // state 1 switch (*ptr) { case 'a': goto l1; case 'b': ptr++; switch (*ptr) // state 2 switch (*ptr) // state3 case 'b': goto l0; case '#': cout<<"yes"<<endl; return; default: break; } default: break; break; // 遇到非法字符 cout << "no" << endl; } // 看实例运行

27 2.4.5 词法分析器生成器简介（上机课再介绍） <3> 两类分析器的比较 表驱动 直接编码 分析器的速度 慢 快
程序与模式的关系 无关 有关 分析器的规模 较大 较小 适合的编写方法 工具生成 手工编写 2.4.5 词法分析器生成器简介（上机课再介绍） <1> 构造词法分析器的全过程均有算法： 正规式－NFA－DFA－最小化DFA－词法分析器（分析表） <2> LEX的基本结构 根据正规式构造的分析表＋驱动器框架（不变的） <3> 利用LEX构造词法分析器的关键 ① 用LEX提供的正规式集合设计记号的模式； ② 用LEX提供的语义支持识别记号或指出输入中的错误。

28 2.5 本章小结 词法分析的两个重要环节：规定所有合法输入＋识别合法输入 重要内容： <1> 记号、模式与单词
<1> 记号、模式与单词 <2> 记号的说明：模式的形式化描述－正规式 <3> 记号的识别：有限自动机 NFA：与正规式有对应关系，易于构造，状态数少； DFA：确定性便于记号识别，不易构造，状态数可能多； 记号识别的方法： 模拟DFA： 模拟NFA（特殊情况下）：需要动态计算状态子集。

29 2.5 本章小结（续） <4> 从正规式到词法分析器（等价变换的过程） 正规式描述模式 由正规式构造NFA NFA的确定化（子集法：smove， ε-闭包） DFA的最小化（可区分概念） 词法分析器：表驱动（自动生成）与直接编码（手工编写）

30 第二章 结束（3月28日） 下次课介绍第一次上机题

31 算法2.4 求ε-闭包 返回 两个数据结构： 闭包U和模拟递归的stack 输入 状态集T。 输出 状态集T的ε-闭包
方法 用下边的函数计算ε-闭包 用算法计算ε-闭包({s2})： U stack 1. {s2} s2 2. {s2, s4} s4 3. {s2, s4, s5} s5 4. {s2, s4, s5} function ε-闭包(T) is begin for T中每个状态t loop end loop; while 栈不空 return U; endε-闭包; 加入t到U; push(t); pop(t); for 每个u=move(t, ε) loop end loop; 问题：试将函数直接写为递归的 if u不在U中 then 加入u到U; push(u); end if; 返回

32 算法2.1 模拟DFA 输入 DFA D和输入字符串x(eof)。D的初态为s0，终态集为F。
输出 若D接受x，回答“yes”，否则回答“no”。 方法 用下述过程识别x： s:=s0； ch:=nextchar； -- 初值 while ch≠eof -- 循环 loop end loop; if 返回 then return “yes”; else return “no”; end if; ■ s:=move(s,ch); ch:=nextchar; s is in F 算法2.3