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

2、態去記錄在NFA讀入一個輸入符號后可能達到的所有狀態.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確定有窮自動機的化簡確定有窮自動機的化簡 說一個有窮自動機是化簡了的，即是說，它沒有多余狀態并且它的狀態中沒有兩個是互相等價的。一個有窮自動機可以通過消除多余狀態和合并等價狀態而轉換成一個最小的與之等價的有窮自動機。 所謂有窮自動機的多余狀態，是指這樣的狀態：從自動機的開始狀態出發，任何輸入串也不能到達的那個狀態；或者從這個狀態沒有通路到達終態。 Compiler Construction

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

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

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

7、的終態是含有F的那組的代表 5.去掉M中的死狀態.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、的一個正規式R構造上的一個NFA M，使得L(M)=L(R)的方法。“語法制導”的方法，即按正規式的語法結構指引構造過程，構造規則具體描述如下： Compiler Construction Principles (1)R=,構造任一具有空終態集的NFA M (2） R= ，構造的NFA M=(k0, ,f,k0.k0): f（k0,a)對于 所有a都沒定義。 (3）R=a,構造的NFA M=(k0,k1,f,k0.k1): f(k0,a) = k1 (4) R =R1 | R2, 將步驟（1）（2）（3）分別應用到R1,R2 產生M1= =(K1,f1,k1,F1), M2=(K2,f2,k2

10、,F2),其中K1,K2不相交.構造的NFA M= (K1K2k,f,k,F) : k是新增加的狀態符號， 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）分別應用到R1,R2 產生M1=(K1,f1,k1,F1), M2=(K2,f2,k2,F2),其中K1,K2不相交.構造的NFA M= (K1K2,f,k1,F2) : f包含f1和f2,且f(k,a)=f1(k,a),當 kF1時; f(k,a)

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

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

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

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