編譯原理及實現(xiàn)技術(shù)備課筆記

1、第二章 形式語言與有限自動機(jī)有限自動機(jī)之第一部分目的：使學(xué)生對自動機(jī)模型有一個總的認(rèn)識，了解自動機(jī)識別語言的原理。掌握非確定有限自動機(jī)到確定有限自動機(jī)的轉(zhuǎn)換技術(shù)。內(nèi)容：有限自動機(jī)的模型確定有限自動機(jī)DFA非確定有限自動機(jī)NFA非確定有限自動機(jī)到DFA的轉(zhuǎn)換有限自動機(jī)的引入（1）引入原因：有限自動機(jī)是一種識別裝置，它能準(zhǔn)確地識別正規(guī)集。它為詞法分析程序的構(gòu)造提供了方法和工具。（2）性質(zhì)：有限自動機(jī)是具有離散輸入輸出系統(tǒng)的數(shù)學(xué)模型。它具有有限數(shù)目的內(nèi)部狀態(tài)，系統(tǒng)可以根據(jù)當(dāng)前所處的狀態(tài)和面臨的輸入字符決定系統(tǒng)的后繼行為。其當(dāng)前狀態(tài)概括了過去輸入處理的信息。（3）用途：有限自動機(jī)是描述特定類型算法的數(shù)

2、學(xué)方法。特別地，有窮自動機(jī)可用作描述在輸入串中識別模式的過程，因此，也能用于構(gòu)造詞法分析程序。2有限自動機(jī)的模型（1）模型如圖所示：輸入帶a輸入帶bcde 讀頭讀頭輸入輸出控制器輸入輸出控制器狀態(tài)：初始狀態(tài)、中間狀態(tài)和終止?fàn)顟B(tài)。工作過程：在初始狀態(tài)下，讀頭指向輸入帶的最左單元，準(zhǔn)備讀入第一個字符，每讀入一個字符，從當(dāng)前狀態(tài)進(jìn)入下一狀態(tài)；當(dāng)讀頭讀入所有字符后，狀態(tài)進(jìn)入終態(tài)，則輸入帶上的輸入串被接受，否則，輸入串有錯。注：1)終止?fàn)顟B(tài)可以有若干個，而初始狀態(tài)一般只有一個。 2)可用狀態(tài)轉(zhuǎn)換圖表示狀態(tài)變換，狀態(tài)用結(jié)點表示，讀入符號用邊表示。（2）自動機(jī)實例：我們舉一個大家熟悉的程序設(shè)計語言中標(biāo)識符的

3、識別過程。標(biāo)識符是由字母打頭，后跟若干字母和數(shù)字的字符串。則其自動機(jī)表示如下：則標(biāo)識符xtemp的識別匹配過程為：小結(jié)：有限自動機(jī)能夠準(zhǔn)備識別程序設(shè)計語言中的單詞，因此可用于構(gòu)造詞法分析程序。方法是為程序中的每類單詞，根據(jù)詞法構(gòu)成規(guī)則設(shè)計一個FA，然后將其合并在一起構(gòu)成一個詞法分析程序。FA可以分為確定有限自動機(jī)和非確定有限自動機(jī)兩種。這次課主要學(xué)習(xí)確定有限自動機(jī)3確定有限自動機(jī)(1)定義：確定有限自動機(jī)是一個五元式 M(S,S,f,s0,Z）其中：S：有限狀態(tài)集 S ：有限字母表f：SS S上的單值映射，f(s,a)=s s0：唯一的初態(tài)，s0 SZ：終止?fàn)顟B(tài)集，ZS注：這里確定的含義，就是

4、狀態(tài)轉(zhuǎn)換關(guān)系f是一個函數(shù)，即對于給定的當(dāng)前狀態(tài)s和當(dāng)前讀入的符號a，有唯一確定的下一狀態(tài)s(2)狀態(tài)轉(zhuǎn)換關(guān)系表示：狀態(tài)轉(zhuǎn)換矩陣：DFA的映射關(guān)系由一個矩陣來表示。狀態(tài)轉(zhuǎn)換圖：注：1）用矩陣表示轉(zhuǎn)換便于計算機(jī)處理，但不直觀，而用狀態(tài)轉(zhuǎn)換圖表示比較直觀。2）在整個狀態(tài)轉(zhuǎn)換圖中只有一個初始狀態(tài)結(jié)點，用“”射入的結(jié)點表示初始狀態(tài)。可有若干終止?fàn)顟B(tài)(也可能沒有)，用雙圓圈表示。若初始狀態(tài)結(jié)點同時又是終止?fàn)顟B(tài)結(jié)點，則表示空串e可為相應(yīng)DFA識別。例：DFA M=(0,1,2,3,a,b,f,0,3)f: f(0,a)=1 f(0,b)=2 f(1,a)3 f(1,b)2 f(2,a)=1 f(2,b)=3

5、 f(3,a)3 f(3,b)3 狀態(tài)轉(zhuǎn)換矩陣 輸入狀態(tài) a1 11 1a0 03 32 b a bbabba 0 1 2 1 3 2 2 1 3 3 3 3狀態(tài)轉(zhuǎn)換圖：例：構(gòu)造一個DFA M，它接受字母表a,b,c上，以a或b開始的字符串，或以c開始但所含的a不多于一個的字符串。故：DFA: M=(0,1,2,3,a,b,c,f,0,1,2,3)其中：f： f(0,a)=1 f(0,b)=1 f(0,c)=1 f(1,a)=1 f(1,b)=1 f(1,c)=1 f(2,a)=3 f(2,b)=2 f(2,c)=2 f(3,b)=3 f(3,c)=3(3)一步動作每讀一個字符，狀態(tài)就向前進(jìn)至

6、下一狀態(tài)。 記為：“ ” K 表示自動機(jī)做了K步動作 *表示自動機(jī)做了0步動作或0步以上動作 +(4) DFA對字符串的識別定義：串Sa*為 DFA M=(S, S,f,s0,Z) 所識別，當(dāng)且僅當(dāng)(s0, a ) *(s,e),且s Z能被DFA M所接受的字符串的集合，稱為自動機(jī)M所能識別的語言，記為L(M)注：不能被自動機(jī)接受的字符串有兩種情況：讀完輸入串，狀態(tài)不停在終止?fàn)顟B(tài)，即： (s0,a) *(s,e),且s Z在讀過程中出現(xiàn)不存在的映射，使自動機(jī)無法繼續(xù)動作4、不確定有限自動機(jī)NFA(Non-deterministic FA)(1)定義：不確定有限自動機(jī)是一個五元式 M=（S,S

7、,f,S0,Z）其中：S：有限狀態(tài)集S ：有限字母表f： S S2S(S的子集)上的映射S0：非空的初態(tài)集，S0 是S的真子集Z：終止?fàn)顟B(tài)集，Z是S的子集，可為空集注：1)非確定主要是指后繼狀態(tài)可有多個。2) DFA是NFA的特例。 3)字母表可包括e例 設(shè)NFA M(q0,q1,0,1,f,q0q1) f映射為字符狀態(tài)01q0q0q1q1q0， q1q0(2)兩自動機(jī)等價：任何兩個有限自動機(jī)M和M，若它們識別的語言相同(L(M)=L(M)，則稱M和M等價注：存在判定任何兩個有限自動機(jī)等價性的算法5、NFA確定化(1)定理 對于每個NFA M，存在一個DFA M，使得L(M)=L(M)。即，設(shè)

8、L是一NFA接受的正規(guī)集，則存在一個DFA接受L(2)算法由NFA M=(S,S,f,S0,Z)構(gòu)造一個等價的DFA M=(Q, S ,d,I0,F）1.取I0=S0，2.若狀態(tài)集Q中有狀態(tài)Ii=s0,s1,sj , skS , 0 kj;而且M機(jī)中有f(s0,s1,sj,a) = f(s0,a) f(s1,a) f(sj,a)=s0,s1,st =It，若It不在Q中，則將It加入Q。3.重復(fù)步驟2，直到Q中無新狀態(tài)加入為止。4.取終態(tài)F=I | I Q,且I Z F 注：1)上述過程可在有限步內(nèi)完成，因為M機(jī)狀態(tài)的冪集是有限的；2)上述過程也可用表格法來描述，其中列是字符集S中的字符；行是

9、Q中的各狀態(tài)，開始僅包含I0狀態(tài)，隨著算法的執(zhí)行，Q的狀態(tài)逐漸增多直止不再增多為止；表格元素就是d映射函數(shù)。注：3)NFA確定化的實質(zhì)是以原有狀態(tài)集上的覆蓋片(COVER)作為DFA上的一個狀態(tài)，將原狀態(tài)間的轉(zhuǎn)換改為覆蓋片間的轉(zhuǎn)換，從而將不確定問題確定化。4)通常，經(jīng)確定化后，狀態(tài)數(shù)增加，而且可能出現(xiàn)一些等價狀態(tài)，這時需要化簡。例 把上例的NFA確定化1.M的初態(tài)：I0=q0。則Q中就有了I0狀態(tài)2.由Q中的狀態(tài)I0=q0，查看M機(jī)，有： f(q0,0)=q0、 f(q0,1)=q1=I1此時，Q=I0,I13.由Q中的狀態(tài)I1=q1，查看M機(jī)，有： f(q1,0)=q0,q1 =I2、 f(

10、q1,1)=q0=I0此時，Q=I0,I1,I23.由Q中的狀態(tài)I2=q0,q1 ，查看M機(jī)，有： f(q0,q1 ,0)=q0,q1 、 f(q0,q1 ,1)=q0,q1 =I2此時，Q=I0,I1 ,I24.F=I1 ,I2NFA經(jīng)過確定化后，變?yōu)椋篋FA M=(I0,I1 ,I2,0,1, S,I0, I1 ,I2 ） SQ01I0 =q0I0 =q0I1 =q1I1 =q1I2 =q0,q1 I0 =q0I2 =q0,q1 I2 =q0,q1 I2 =q0,q1 d01I0I0I1 I1 I2I0I2I2I2狀態(tài)轉(zhuǎn)換圖如下：第二章 形式語言與有限自動機(jī)有限自動機(jī)之第二部分目的：使學(xué)生

11、在了解了非確定有限自動機(jī)的基礎(chǔ)上，進(jìn)一步認(rèn)識其更一般的形式-帶空邊的非確定有限自動機(jī)，并掌握其到確定有限自動機(jī)的轉(zhuǎn)換技術(shù)，進(jìn)而學(xué)習(xí)DFA的最小化技術(shù)。內(nèi)容：有限自動機(jī)的模型確定有限自動機(jī)DFA非確定有限自動機(jī)NFA非確定有限自動機(jī)到DFA的轉(zhuǎn)換1、含空邊的非確定有限自動機(jī)2、含空邊的非確定有限自動機(jī)到DFA的轉(zhuǎn)換3、確定有限自動機(jī)的化簡（最小化）(1)化簡條件：接受的語言必須相同(2)化簡(最小化)算法基本思想劃分法1.將DFA M 中的狀態(tài)劃分為互不相交的子集，每個子集內(nèi)部的狀態(tài)都等價；而在不同子集間的狀態(tài)均不等價。2.從每個子集中任選一個狀態(tài)作為代表，消去其它等價狀態(tài)。3.把那些原來射入其

12、它等價狀態(tài)的弧改為射入相應(yīng)的代表狀態(tài)。(3) 狀態(tài)等價：設(shè)DFA M中有兩個狀態(tài)s,t， s,t 等價： (s,w) *(s1,e)同時(t,w) *(t1, e)，s1,t1都是終態(tài)，w VT* ，即如果從狀態(tài)s出發(fā)能讀出某個字w而 停于 終態(tài)，從t出發(fā)也能讀出同樣的字w而停于終態(tài)，則稱s,t 等價。 s,t可區(qū)別 ：如果s,t不等價，則稱為s,t可區(qū)別(4)化簡(最小化)算法 1.把狀態(tài)集S劃分為終態(tài)集和非終態(tài)集： 0I01,I02，I01屬于非終態(tài)集,I02屬于終態(tài)集。因為終態(tài)能識別e，而非終態(tài)不能，所以它們是可區(qū)別的； 2.假定經(jīng)過k次劃分后： kIk0,Ik1Ikm.這m個子集之間可

13、區(qū)分，子集內(nèi)部還是否可以劃分？任取一個子集Iki=s1,s2,sk,若存在某讀入字符a，使f(Iki,a)的結(jié)果不是全部包含在k的某個子集中，則說明Iki中有不等價的狀態(tài)，還要進(jìn)一步劃分。對k中所有子集都進(jìn)行測試，以完成一次劃分。 3.重復(fù)步驟2，直到所含的子集數(shù)不再增加為止。 4.對每個子集任取一狀態(tài)為代表。若該子集包含原有的初態(tài)，則相應(yīng)代表狀態(tài)就是最小化后M的初態(tài)；同樣，若該子集包含原有的終態(tài)，則相應(yīng)代表狀態(tài)就是最小化后M的終態(tài)。注：1）當(dāng)一個自動機(jī)沒有任何多余的狀態(tài)，并且它的狀態(tài)中沒有兩個是互相等價的時，我們說這個有限自動機(jī)是化簡了的。 2）可以通過消除多余狀態(tài)，合并等價狀態(tài)而轉(zhuǎn)化成一個最小化的與之等價的有限自動機(jī)。例：設(shè)有一DFA 的狀態(tài)轉(zhuǎn)換圖如下，試化簡之。解：1.把M的狀態(tài)分為兩組：終態(tài)集，非終態(tài)集00,1,2,3,4,5,62.1考察非終態(tài)集： f(0,1,2,a)=1,3 不屬于0的任何一個子集，所以0，1，2要分開得到：11，0,2，3,4,5,6再看：f(0,2,a)=1屬于1的子集 f(