西北工业大学编译原理课件第三章 词法分析及词法分析程序5.pptVIP

3.3.5具有 ?动作的NFA的确定化 设已给具有?动作的NFA M=(K,?,f,S0,Z),构造相应的DFA M’=(K’, ?,f’,q0,Z’)的方法是，先令q0=[?-CLOSURE(S0)], 然后对每个a??，令 [?-CLOSURE(f’(q0,a))]为新状态，如此反复，直到无新状态产生： 1. 令 K’={[?-CLOSURE(S0)]}; f’=? ; 2. 对K’中尚未被标记的状态qi=[Si1,Si2,…,Sim]: (1)标记qi; (2)对于每个a??,令Ta=f({Si1,Si2,…,Sim},a); qj= [?-CLOSURE(Ta)]; (3)若qj?K’,则令K’=K’?{qj }; (4)令f’=f’ ?{f’(qj ,a)= qj }; 3. 重复2.,直到K’中无未标记的状态; 4. 令Z’={qj | qj ? Z??} (这里把qj 视为集合) 确定化具有?动作的NFA的例子 例3.4 考虑前面引入的具有?动作的NFA的例子(P63图3-10) 1.q0=[0,1,2,3]==K’; 2.q0未标记,故(1)标记q0; (2)令f”(q0,a)= [?-CLOSURE(f’(q0,a))] =q0; f”(q0,b)= [?-CLOSURE(f’(q0,b))]=[1,3]=q1;q1==K’; f”(q0,c)=[2,3]=q2; q2==K’; 3. 此时,K’={q0,q1,a2},q1,q2 are not marked.so,(1) mark q1; (2) let f”(q1,a)= [?-CLOSURE(f’(q1,a))]= ?; f”(q1,b)=…=q1; f”(q1,c)=…= ?; 4. q2 is not marked, so (1) mark q2; (2)f”(q2,a)= f”(q2,b)=?; f”(q2,c)=q2; K’ is not increased and all states are marked. Z’={q0,q1,q2} 手工计算确定化的方法 在人工进行NFA确定化时,可按下述的构造矩阵的方法实现: _____________| a b c_ q0: [0123] | [0123] [13] [23] q1: [13] | [ ] [13] [ ] q2: [23] | [ ] [ ] [23] 需要说明的是,本算法也适合于不含?产生式的NFA的确定化. 例3.5 对于书中图3-13所示的NFA利用上述算法所得的DFA如 P67图3-13所示.其中,圆圈中的数字是原NFA的状态编号,在图3-13中, q0={0,1,7,11,14,19,24,26,28,30,33,35,40}. 标有“#”的状态为特殊状态,在该状态下,若遇非弧线上出现的字符,则转到状态25. 3.3.6 DFA状态数的最小化 对于一DFA来说,其状态数可能并不是最小的.原因是DFA中有些状态是“等价”的.为得到效率高的DFA,需将这些“等价”状态合并,这就是DFA的最小化. DFA M的最小化: 构造等价的DFA M’其状态数达到最小. 可区分状态: 设s,t?K, s,t由某w??*所区分 iff ( f(s,w)?Z ? f(t,w)?Z ) ? ( f(s,w)?Z ? f(t,w)?Z ) 若?w??*, f(s,w)?Z ? f(t,w)?Z,则称 s与 t等价(不可区分) 在一DFA中,等价状态可合并. DFA最小化算法 基本思想: 将M的状态集K逐步地进行划分加细,以期将K划分为满足等价关系的等价类,使得在同一类中的状态不可区分;在不同类中的状态可区分.算法如下: 1.先将状态集K划分为两个子集Z和K-Z,显然分属于这两个集合的状态是可(被?)区分的.记?={Z,K-Z}. 2.设当前的划分?中已含有m个子集:?={I1,I2,…,Im},其中,属于不同子集的状态是可区分的,而属于同一子集中的状态则待区分.现对每个子集Ii={Si1,Si2,…,Sin}中的各状态Sir(Sir?K,1? r ?n )进行考查,看其是否可区分.若存在a??,使得Su=f(Sip,a) ?Ij, Sv=f(Siq,a) ?Ik 则由假设, Su和Sv被子某个w所区分,进一步, Sip 和Siq 可被aw 区分: f(Sip,aw)=f(Su