编译原理词法剖析.ppt

* Thanks. * * 例1：NFA转换成DFA (符号合并) 例2：设计一个DFA，其输入字母表是{0,1}，它能接受以0开始，以1结尾的所有序列。 a a 3 c b 0 1 2 a 0 1,2 c b 3 0,1 0 Z C S A B ε 1 ε 解：①根据题意，得出相应的正则式：0(0|1)*1 ②得状态转换图(NFA)如下： * 0 1 state DFA state S S S ABC S,ABC S,ABC ABC BC BCZ ABC,BC,BCZ S,ABC,BC,BCZ BC BC BCZ BC,BCZ S,ABC,BC,BCZ BCZ BC BCZ BCZ S,ABC,BC,BCZ ③NFA确定为DFA过程： DFA的初态（为NFA的初始状态经过ε合并后的状态的并集）例：δ(S,ε)=; DFA的其它状态（ 为NFA的状态经过输入符号后产生的状态，再经过ε合并后的状态的并集）例：求δ(S,0)=？ δ(S,0)=A; δ(A,ε)=B; δ(B,ε)=C; δ(C,ε)=； DFA的终态（为所有含有NFA的终态的状态） 0,1 0 Z C S A B ε 1 ε * 得状态转换图(DFA)如下： 0 0 0 S C A 1 0 1 B 1 0 0 0 S BCZ ABC 1 0 1 BC 1 在DFA中，所有含有NFA的终态的状态作为DFA的终态 DFA M=( { S,A,B,C } , { 0,1 } , δ, S , { C } ) 其中δ如上（不可省略） * 定义1：集合I的ε-闭包： 令I是一个状态集的子集，定义ε-closure（I）为： 1）若s∈I，则s∈ε-closure（I）； 2）若s∈I，则从s出发经过任意条ε弧能够到达的任何状态都属于ε-closure（I）。 状态集ε-closure（I）称为I的ε-闭包 为了使得NFA确定化，我们首先给出两个定义： 5 6 4 3 2 a ε a a ε 1 例：如图所示的状态图： 令I={1}，求ε-closure（I）=？ 根据定义： ε-closure（I）={1，3} * —— J是从状态子集I中的每个状态出发，经过标记为a的弧而达到的状态集合. —— Ia是状态子集,其元素为J中的状态，加上从J中每一个状态出发通过ε弧到达的状态 定义2: 令I是NFA M’的状态集的一个子集, a∈Σ 定义: Ia=ε-closure(J) 其中J = ∪δ(s,a) S∈I 5 6 4 3 2 a ε a a ε 1 例：令I={1}，求Ia=? Ia=ε-closure(J) =ε-closure(δ(1，a)） =ε-closure({2，4}） ={2，4，6} * 例：有NFA M，求DFA M’。 a 1 2 3 4 start a b a c c ε I=ε-closure({1})={1,4} Ia=ε-closure(δ(1,a)∪δ(4,a)) = ε-closure({2,3}∪φ） = ε-closure ({2,3}) ={2,3} Ib= ε-closure(δ(1,b)∪δ(4,b)) = ε-closure(φ） =φ Ic= ε-closure(δ(1,c)∪δ(4,c)) = φ I={2,3}, Ia={2},Ib={4},Ic={3,4}… I Ia Ib Ic {1,4} {2,3} φ φ {2,3} {2} {4} {3,4} {2} {2} {4} φ {4} φ φ φ {3,4} φ φ {3,4} 初态 * start I Ia Ib Ic {1,4} {2,3} φ φ {2,3} {2} {4} {3,4} {2} {2} {4} φ {4} φ φ φ {3,4} φ φ {3,4} 符号 状态