西安電子科技大學(xué)編譯原理 (2)

1、1上次課內(nèi)容回顧FNFA FDFAF等價(jià)性22.4 從正規(guī)式到詞法分析器構(gòu)造詞法分析器的一般方法和步驟：1. 描述：用正規(guī)式對(duì)模式進(jìn)行描述；2. 構(gòu)造NFA：為每個(gè)正規(guī)式構(gòu)造一個(gè)NFA；3. 確定化：將NFA轉(zhuǎn)換成等價(jià)的DFA；4. 最小化：優(yōu)化DFA，使其狀態(tài)數(shù)最少；5. 構(gòu)造詞法分析器：由DFA構(gòu)造詞法分析器。32.4 從正規(guī)式到詞法分析器F從正規(guī)式到NFA 算法2.2 Thompson 算法輸入字母表上的正規(guī)式 r輸出接受 L(r) 的NFA N方法首先分解 r，然后根據(jù)下述步驟構(gòu)造NFA：1. 對(duì)，構(gòu)造NFA N() 接受； 2. 對(duì)上的每個(gè)字符a，構(gòu)造NFA N(a) 接受a；3.

2、若N(p)和N(q)是正規(guī)式p和q的NFA，則ar|srsr*(r)42.4 從正規(guī)式到詞法分析器（a）對(duì)正規(guī)式p|q，構(gòu)造NFA N(p|q) 接受L(p)L(q)；（b）對(duì)正規(guī)式pq，構(gòu)造NFA N(pq) 接受L(p)L(q)； （c）對(duì)正規(guī)式p*，構(gòu)造NFA N(p*) 接受L(p*)； （d）對(duì)于正規(guī)式(p)，使用p本身的NFA，不再構(gòu)造。ar|srsr*(r)52.4 從正規(guī)式到詞法分析器例2.11 用Thompson算法構(gòu)造正規(guī)式r = (a | b)* a b b的NFA N(r) 。先分解正規(guī)式，再自下而上構(gòu)造NFA注意：算法的構(gòu)造與正規(guī)式一一對(duì)應(yīng)構(gòu)造一個(gè)新的NFA最多增加兩

3、個(gè)狀態(tài)62.4 從正規(guī)式到詞法分析器F從NFA到DFA1. NFA識(shí)別記號(hào)的“并行”方法例2.12 從甲地到乙地，可以乘汽車也可以騎自行車，具體路線如右圖。其中c表示乘車，b表示騎自行車?，F(xiàn)在要求從甲地到乙地，只許乘車而不許騎自行車，該如何走？抽象：識(shí)別是否有從甲到乙標(biāo)記為全c的路徑串行（試探）：甲 c 2 無(wú)路可走，退回甲 c 1 c 3 無(wú)路可走，退回甲 c 1 c 乙 到達(dá)乙地，成功 并行：有多輛汽車，每次到達(dá)汽車能到達(dá)的全體甲 c 1, 2c 3, 乙到達(dá)乙地，成功72.4 從正規(guī)式到詞法分析器由于并行的方法在每試探一步時(shí)，考慮了所有的下一狀態(tài)轉(zhuǎn)移（所有下一狀態(tài)作為一個(gè)狀態(tài)集合），因此

4、所走的每一步都是確定的。用NFA識(shí)別記號(hào)，并不采用串行的方法（算法不易構(gòu)造，復(fù)雜度高且回溯），而是采用并行的方法，核心思想是將不確定的下一狀態(tài)確定化。NFA上識(shí)別記號(hào)的確定化方法是在計(jì)算下一狀態(tài)轉(zhuǎn)移時(shí)，實(shí)施如下確定化的兩個(gè)步驟：1. 消除 狀態(tài)轉(zhuǎn)移：-閉包(T) 2. 消除多于一個(gè)的下一狀態(tài)轉(zhuǎn)移：smove(S, a)82.4 從正規(guī)式到詞法分析器-閉包(T)：從狀態(tài)集T出發(fā)，不經(jīng)任何字符達(dá)到的狀態(tài)全體。定義2.6 狀態(tài)集T的-閉包(T)是一個(gè)狀態(tài)集，且滿足：（1）T中所有狀態(tài)屬于-閉包(T)；（2）任何smove(-閉包(T)，)屬于-閉包(T)；（3）再無(wú)其他狀態(tài)屬于-閉包(T)。 根據(jù)定

5、義，-閉包(s2)應(yīng)包括：1. s2自身s2（1）2. s4s2, s4（2）3. s5s2, s4, s5 （2）92.4 從正規(guī)式到詞法分析器算法2.4 求-閉包輸入狀態(tài)集T輸出狀態(tài)集T的-閉包（U）方法for T中每個(gè)狀態(tài)t將t加入U(xiǎn); push(t); end for;while 棧不空pop(t); for 每個(gè)u = move(t, )if u不在U中 then 將u加入U(xiǎn); push(u); end if; end for;end while; return U;集合U和模擬遞歸的stack102.4 從正規(guī)式到詞法分析器-閉包(s1,s2)U= 112.4 從正規(guī)式到詞法分析器

6、-閉包(s1,s2)U=s1,s2 s1s2122.4 從正規(guī)式到詞法分析器-閉包(s1,s2)U=s1,s2 s1Move(s2,)=s4132.4 從正規(guī)式到詞法分析器-閉包(s1,s2)U=s1,s2 s1Move(s2,)=s4U=s1,s2,s4s4142.4 從正規(guī)式到詞法分析器-閉包(s1,s2)U=s1,s2 s1Move(s4,)=s5U=s1,s2,s4152.4 從正規(guī)式到詞法分析器-閉包(s1,s2)U=s1,s2 s1Move(s4,)=s5U=s1,s2,s4U=s1,s2,s4,s5s5162.4 從正規(guī)式到詞法分析器-閉包(s1,s2)U=s1,s2 s1Mov

7、e(s5,)= U=s1,s2,s4U=s1,s2,s4,s5172.4 從正規(guī)式到詞法分析器-閉包(s1,s2)U=s1,s2 U=s1,s2,s4U=s1,s2,s4,s5Move(s1,)= 182.4 從正規(guī)式到詞法分析器-閉包(s1,s2)U=s1,s2 Move(s1,)= U=s1,s2,s4U=s1,s2,s4,s5192.4 從正規(guī)式到詞法分析器Fsmove(S, a)：從狀態(tài)集S出發(fā)，標(biāo)記為a的下一狀態(tài)全體。與move(s, a)的唯一區(qū)別：用狀態(tài)集取代狀態(tài)。1234aabasmove(1,3, a)=5,4,25a202.4 從正規(guī)式到詞法分析器算法2.3 模擬NFA（并

8、行）輸入NFA N，x(eof)，s0，F(xiàn) 輸出若N接受x，回答“yes”，否則“no” 方法用下邊的過(guò)程對(duì)x進(jìn)行識(shí)別。S是一個(gè)狀態(tài)的集合 S := -閉包(s0);- 所有可能初態(tài)的集合a := nextchar;while a eof loop S := -閉包(smove(S，a); - 所有下一狀態(tài)的集合a := nextchar;end loop;if SF then return “yes”; else return “no”; end if; 模擬模擬DFA模擬模擬NFA開(kāi)始開(kāi)始初態(tài)初態(tài)(s0)初態(tài)的初態(tài)的s0的的-閉包閉包下一狀下一狀態(tài)轉(zhuǎn)移態(tài)轉(zhuǎn)移當(dāng)前狀態(tài)的當(dāng)前狀態(tài)的下一狀態(tài)下一

9、狀態(tài)當(dāng)前狀態(tài)集當(dāng)前狀態(tài)集的的下一狀態(tài)集下一狀態(tài)集結(jié)束結(jié)束s 是否在是否在 F中中SF212.4 從正規(guī)式到詞法分析器識(shí)別abb: 計(jì)算初態(tài)集：-閉包(0)= 0,1,2,4,7 A從A出發(fā)經(jīng)a到達(dá)：-閉包(smove(A, a)= 3,8,6,7,1,2,4 B從B出發(fā)經(jīng)b到達(dá)：-閉包(smove(B, b)= 9,5, 6,7,1,2,4 C從C出發(fā)經(jīng)b到達(dá)：-閉包(smove(C, b)= 10,5,6,7,1,2,4 D結(jié)束且D10=10，可以識(shí)別abb。識(shí)別的路徑為：A a B b C b D例2.13 在NFA上識(shí)別輸入序列abb和abab222.4 從正規(guī)式到詞法分析器識(shí)別abab

10、: 初態(tài)集：-閉包(s0)=0,1,2,4,7 A從A出發(fā)經(jīng)a到達(dá)：-閉包(smove(A, a) = 3,8,6,7,1,2,4 B從B出發(fā)經(jīng)b到達(dá)：-閉包(smove(B, b) = 9,5, 6,7,1,2,4 C從C出發(fā)經(jīng)a到達(dá)：-閉包(smove(C, a) = 8,3, 6,7,1,2,4 B從B出發(fā)經(jīng)b到達(dá)：-閉包(smove(B, b) = 9,5, 6,7,1,2,4 C識(shí)別路徑為：A a B b C a B b C。由于C10=，所以不能識(shí)別例2.13 在NFA上識(shí)別輸入序列abb和abab232.4 從正規(guī)式到詞法分析器2. 子集法構(gòu)造DFA并行模擬NFA的弱點(diǎn)：每次動(dòng)態(tài)

11、計(jì)算下一狀態(tài)轉(zhuǎn)移的集合，效率低。改進(jìn)方法：將NFA上的全部路徑均確定化并且記錄下來(lái)，得到與NFA等價(jià)的DFA。 從甲地到乙地的路徑是一個(gè)NFA ，可找到一個(gè)等價(jià)的DFA。例例2.14 用用DFA識(shí)別識(shí)別cc和和cbc：甲甲 c 1,2 c 3,乙乙， 接受接受 甲甲 c 1,2 b 3 c ?，不接受，不接受 1. 消除了不確定性2. 無(wú)需動(dòng)態(tài)計(jì)算狀態(tài)集合24算法2.5 從NFA構(gòu)造DFA（子集法）輸入 NFA N輸出等價(jià)的DFA D，其初態(tài)含有NFA初態(tài)，終態(tài)是含有NFA終態(tài)的狀態(tài)集合。方法用下述過(guò)程構(gòu)造DFADstates = -閉包(s0) ;-是唯一狀態(tài)且未標(biāo)記while Dstate

12、s有未標(biāo)記狀態(tài)集T loop 標(biāo)記T; for 每一個(gè)字符a loopU := -閉包(smove(T，a);if U非空 thenDtranT，a := U; if U不在Dstates中 then U作為未標(biāo)記狀態(tài)加入Dstates;end if;end if; end for; end while; return：Dstates和轉(zhuǎn)換矩陣Dtran狀態(tài)集的集合狀態(tài)集的集合Dstates和轉(zhuǎn)換矩陣和轉(zhuǎn)換矩陣Dtran25-閉包(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-閉包(smov

13、e(B, a)=3,8,6,7,1,2,4B-閉包(smove(B, b)=5,9,6,7,1,2,4*D-閉包(smove(C, a)=3,8,6,7,1,2,4B-閉包(smove(C, b)=5,6,7,1,2,4C-閉包(smove(D, a)=3,8,6,7,1,2,4B-閉包(smove(D, b)=5,10,6,7,1,2,4*E-閉包(smove(E, a)=3,8,6,7,1,2,4B-閉包(smove(E, b)=5,6,7,1,2,4C例2.15 用算法2.5構(gòu)造(a|b)*abb的DFA 選擇哪一個(gè)選擇哪一個(gè)DFA？262.4 從正規(guī)式到詞法分析器3. 最小化DFA對(duì)于

14、若干個(gè)等價(jià)的DFA，總是希望由狀態(tài)數(shù)最小的DFA構(gòu)造詞法分析器。將一個(gè)DFA等價(jià)變換為另一個(gè)狀態(tài)數(shù)最小的DFA的過(guò)程被稱為最小化DFA。定義2.7 對(duì)于任何兩個(gè)狀態(tài)t和s，若從一狀態(tài)出發(fā)接受輸入字符串，而從另一狀態(tài)出發(fā)不接受，或者從t出發(fā)和從s出發(fā)到達(dá)不同的接受狀態(tài)，則稱對(duì)狀態(tài)t和s是可區(qū)分的。設(shè)想任何輸入序列對(duì)s和t均是不可區(qū)分的，則說(shuō)明從s出發(fā)和從t出發(fā)，分析任何輸入序列均得到相同結(jié)果。因此，s和t可以合并成一個(gè)狀態(tài)。 最小化DFA的實(shí)質(zhì)：在狀態(tài)集S上不可區(qū)分的狀態(tài)合并成一個(gè)狀態(tài)。272.4 從正規(guī)式到詞法分析器算法2.6 最小化DFA的狀態(tài)數(shù)輸入DFA D=S，move，s0，F(xiàn)。輸出等

15、價(jià)的D=S，move，s0，F(xiàn)(D狀態(tài)數(shù)最少)方法執(zhí)行如下步驟：1. 初始劃分=S-F，F(xiàn)1，F(xiàn)2，.，其中，F(xiàn)i是F的子集，接受不同記號(hào)；2. 應(yīng)用下述過(guò)程構(gòu)造新的劃分new：for 的每一個(gè)組G劃分G，G的兩個(gè)狀態(tài)s和t在同一組中的充要條件是:a.(move(s,a)Gimove(t,a)Gi)；用新劃分的組替代G，形成新的劃分new； end for；3.若 new= 則final:=且轉(zhuǎn)4； 否則=:new且轉(zhuǎn)2；282.4 從正規(guī)式到詞法分析器4. 在final每個(gè)組Gi中選一個(gè)代表si，使得D中從Gi所有狀態(tài)出發(fā)的狀態(tài)轉(zhuǎn)移在D中均從si出發(fā)，D中所有轉(zhuǎn)向Gi中的狀態(tài)轉(zhuǎn)移在D中均轉(zhuǎn)向

16、si。 含有D中s0的狀態(tài)組G0的代表s0稱為D的初態(tài)，D中所有含F(xiàn)中狀態(tài)的Gj的代表sj構(gòu)成D的終態(tài)集F； 5. 刪除死狀態(tài)，即不是終態(tài)且對(duì)所有輸入字符均轉(zhuǎn)向其自身，或從初態(tài)不可到達(dá)的狀態(tài)。最小化DFA算法的主要步驟1. 初始劃分：終態(tài)與非終態(tài)；2. 利用可區(qū)分的概念，反復(fù)分裂劃分中的組Gi，直到不可再分裂；3. 由最終劃分構(gòu)造D，關(guān)鍵是選代表和修改狀態(tài)轉(zhuǎn)移；4. 消除可能的死狀態(tài)和不可達(dá)狀態(tài)。292.4 從正規(guī)式到詞法分析器例2.17 用算法2.6化簡(jiǎn)DFA1初始化劃分1=ABCD，E2反復(fù)分裂劃分中的組： m(D, b)=E 2=ABC，D，E m(B, b)=D 3=AC，B，D，E 3？ 于是：final=AC，B，D，E 4根據(jù)final構(gòu)造D： 選代表，用A代表AC