1、Compiler Construction Principles DFA是NFA的特例.對每個NFA N一定存在一個DFA ，使得 L(M)=L(N)。對每個NFA N存在著與之等價的DFA M。有一種算法，將NFA轉(zhuǎn)換成接受同樣語言的DFA.這種算法稱為子集法子集法.與某一與某一NFA等價的等價的DFA不唯一不唯一.Compiler Construction Principles從NFA的矩陣表示中可以看出，表項通常是一狀態(tài)的集合，而在DFA的矩陣表示中，表項是一個狀態(tài)，NFA到相應(yīng)的DFA的構(gòu)造的基本思路是： DFADFA的每一個狀態(tài)對應(yīng)的每一個狀態(tài)對應(yīng)NFA的一組狀態(tài). DFA使用它的狀

2、態(tài)去記錄在NFA讀入一個輸入符號后可能達(dá)到的所有狀態(tài).Compiler Construction PrinciplesNFA的確定化的確定化 例子4f35621iaaaabbbbIaIbi,1,21,2,31,2,41,2,31,2,3,5,6,f1,2,41,2,41,2,31,2,4,5,6,f1,2,3,5,6,f1,2,3,5,6,f1,2,4,6,f1,2,4,5,6,f1,2,3,6,f1,2,4,5,6,f1,2,4,6,f1,2,3,6,f1,2,4,5,6,f1,2,3,6,f1,2,3,5,6,f1,2,4,6,fSABACBBADCCEDFDEFDFCE4f35621ia

3、aaabbbbCompiler Construction Principles 等價的等價的DFAaCDBAEFSbaaaaabbbbbabFCompiler Construction Principles確定有窮自動機(jī)的化簡確定有窮自動機(jī)的化簡 說一個有窮自動機(jī)是化簡了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個是互相等價的。一個有窮自動機(jī)可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉(zhuǎn)換成一個最小的與之等價的有窮自動機(jī)。 所謂有窮自動機(jī)的多余狀態(tài)，是指這樣的狀態(tài)：從自動機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個狀態(tài)；或者從這個狀態(tài)沒有通路到達(dá)終態(tài)。 Compiler Construction

4、Principles DFA的最小化就是尋求最小狀態(tài)的最小化就是尋求最小狀態(tài)DFA最小狀態(tài)DFA的含義:沒有多余狀態(tài)(死狀態(tài))沒有兩個狀態(tài)是互相等價（不可區(qū)別）兩個狀態(tài)s和t可區(qū)別：不滿足兼容性同是終態(tài)或同是非終態(tài)傳播性從s出發(fā)讀入某個aa和從 t出發(fā)讀入某個a到達(dá)的狀態(tài)等價。Compiler Construction Principles C和和D同是終態(tài)同是終態(tài),讀入讀入a到達(dá)到達(dá)C和和F, C和和F同是終態(tài)同是終態(tài), C和和F讀入讀入a都到達(dá)都到達(dá)C,讀入讀入b都到達(dá)都到達(dá)E. C和和D等價等價aCDBAEFSbaaaaabbbbbabFCompiler Construction Pri

5、nciples最小狀態(tài)最小狀態(tài)DFA對于一個DFA M =（K,f, k0,kt)，存在一個最小狀態(tài)DFA M =（K,f, k0,kt)，,使L(M)=L(M). 結(jié)論接受L的最小狀態(tài)有窮自動機(jī)不計同構(gòu)是唯一的。Compiler Construction Principles“分割法分割法”DFA的最小化算法的核心 把一個DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的. 算法假定每個狀態(tài)射出的弧都是完全的,否則,引入一個新狀態(tài),叫死狀態(tài),該狀態(tài)是非狀態(tài)，將不完全的輸入弧都射向該狀態(tài)，對所有輸入，該狀態(tài)射出的弧還回到自己.Comp

6、iler Construction Principles DFA的最小化算法的最小化算法 DFA M =（K,f, k0, kt),最小狀態(tài)DFA M 1.構(gòu)造狀態(tài)的一初始劃分： 終態(tài)kt 和非終態(tài)K- kt兩組(group) 2.對施用過程過程PPPP 構(gòu)造新劃分new 3. 如new =,則令 final= 并繼續(xù)步驟4，否則:=new重復(fù)2 . 4.為final中的每一組選一代表，這些代表構(gòu)成M的狀態(tài)。若k是一代表且f(k,a)=t,令r是t組的代表，則M中有一轉(zhuǎn)換f(k,a)=rCompiler Construction Principles M 的開始狀態(tài)是含有S0的那組的代表 M

7、的終態(tài)是含有F的那組的代表 5.去掉M中的死狀態(tài).Compiler Construction Principles過程PP : Construction of Construction of newnewFor each group G of do begin 1.Partiton G into subgroups such that two states s and t of G are in the same subgroups if and only if for all input symbols a, states s and t have transitions on a to s

8、tates in the same group of ;/*at worst, a state will be in a subgroup by itself*/2.replace G in n e w by the set of all subgroups formed end Compiler Construction Principles DFA的最小化的最小化例子例子0:S,A,B C,D,E,F1:S,A,B C,D,E,F 2: CDBAEFSbaaaaaabbbbbbaA S,BbB SDBASaaabbbbaaCompiler Construction Principles從上

9、的一個正規(guī)式R構(gòu)造上的一個NFA M，使得L(M)=L(R)的方法。“語法制導(dǎo)”的方法，即按正規(guī)式的語法結(jié)構(gòu)指引構(gòu)造過程，構(gòu)造規(guī)則具體描述如下： Compiler Construction Principles (1)R=,構(gòu)造任一具有空終態(tài)集的NFA M (2） R= ，構(gòu)造的NFA M=(k0, ,f,k0.k0): f（k0,a)對于 所有a都沒定義。 (3）R=a,構(gòu)造的NFA M=(k0,k1,f,k0.k1): f(k0,a) = k1 (4) R =R1 | R2, 將步驟（1）（2）（3）分別應(yīng)用到R1,R2 產(chǎn)生M1= =(K1,f1,k1,F1), M2=(K2,f2,k2

10、,F2),其中K1,K2不相交.構(gòu)造的NFA M= (K1K2k,f,k,F) : k是新增加的狀態(tài)符號， f包含f1和f2,且f(k,a)=f1(k1,a)f2(k2,a). 若k1F1且k2F2則 F=F1 F2，否則F=F1 F2 kCompiler Construction Principles(5)R=R1.R2 將步驟（1）（2）（3）分別應(yīng)用到R1,R2 產(chǎn)生M1=(K1,f1,k1,F1), M2=(K2,f2,k2,F2),其中K1,K2不相交.構(gòu)造的NFA M= (K1K2,f,k1,F2) : f包含f1和f2,且f(k,a)=f1(k,a),當(dāng) kF1時; f(k,a)

11、=f2(k,a),當(dāng) k K2時;f(k1, )=k2,(6)R=R1*將步驟（1）（2）（3）分別應(yīng)用到R1,產(chǎn)生M1=(K1,f1,k1,F1), 構(gòu)造的NFA M= (K1 k0,F F0 ,f,k0,F0)其中 k0,F F0 是新增加的兩個狀態(tài),f(k,a)=f1(k,a),當(dāng) kF1時; f(k0, )=f(F1 , )= k1,F F0 ,Compiler Construction Principles再用狀態(tài)圖說明可用方法再用狀態(tài)圖說明可用方法對于正規(guī)式x,x 構(gòu)造的NFA（兩種）XCompiler Construction Principles對于正規(guī)式對于正規(guī)式 ,構(gòu)造的構(gòu)

12、造的NFA（三種）（三種） FSFCompiler Construction Principles對于正規(guī)式對于正規(guī)式R= ,構(gòu)造的構(gòu)造的NFA FSCompiler Construction Principles對于正規(guī)式對于正規(guī)式r, r= R1|R2構(gòu)造的構(gòu)造的NFACompiler Construction Principles對于正規(guī)式對于正規(guī)式r, r=R1 R2構(gòu)造的構(gòu)造的NFACompiler Construction Principles對于正規(guī)式對于正規(guī)式r, r=R1*構(gòu)造的構(gòu)造的NFACompiler Construction PrinciplesR=(a|ab)* b

13、 b*Compiler Construction Principles 正規(guī)式用于說明(描述)單詞的結(jié)構(gòu)十分簡潔方便。而把一個正規(guī)式編譯(或稱轉(zhuǎn)換)為一個NFA進(jìn)而轉(zhuǎn)換為相應(yīng)的DFA，這個NFA或DFA正是識別該正規(guī)式所表示的語言的句子的識別器。基于這種方法來構(gòu)造詞法分析程序Compiler Construction Principles詞法分析程序的設(shè)計技術(shù)可應(yīng)用于其它領(lǐng)域，比如查詢語言以及信息檢索系統(tǒng)等，這種應(yīng)用領(lǐng)域的程序設(shè)計特點(diǎn)是，通過字符串模式的匹配來引發(fā)動作，回想LEX，說明詞法分析程序的語言，可以看成是一個模式動作語言。詞法分析程序的自動構(gòu)造工具也廣泛應(yīng)用于許多方面，如用以生成一個

14、程序，可識別印刷電路板中的缺陷，又如開關(guān)線路設(shè)計和文本編輯的自動生成等。 Compiler Construction Principles習(xí)題習(xí)題4.7 練習(xí)1 （1）34 (b)5Compiler Construction Principles本章小結(jié)本章小結(jié) 詞法分析程序是編譯第一階段的工作，它讀入字符流的源程序，按照詞法規(guī)則識別單詞，交由語法分析程序接下去。 本章講述了詞法分析程序設(shè)計原則，并介紹了分別作為正規(guī)集的描述機(jī)制和識別機(jī)制的正規(guī)式和有窮動機(jī)。在此基礎(chǔ)上給出了詞法分析程序自動構(gòu)造工具如LEX的原理。Compiler Construction Principles識別識別Pl0單詞

15、的單詞的FACompiler Construction PrinciplesNFA的確定化的確定化 More exampleCompiler Construction PrinciplesCompiler Construction PrinciplesCompiler Construction PrinciplesCompiler Construction PrinciplesCompiler Construction Principles DFA的最小化算法的最小化算法英文描述英文描述1. Construct an initial partition of the set of states

16、 with two groups:the accepting states F and the nonaccepting states S-F.2. Apply the procedure PP.(Construction of new) to to construct a new partition new.3. If new =,let final= and continue with step (4). Otherwise,repeat step(2) with := new.Compiler Construction Principles4. Choose one state in e

17、ach group of the partition final as the representative for the group.The representatives will be the states of the reduced DFA M.let s be a representative state, and suppose on input a there is a transition from s to t .Let r be the representative of ts group(r may be t).Then M has a transition from s to r on a.Let the start state of M be the representative of the group containing the start state s0 of M.and let the accepting states of M be the representative that are in F.Note that each group of final either consists only of states in F or has no states in F.Compiler Co