《第03章 詞法分析與有窮自動機(2).ppt》由會員分享，可在線閱讀，更多相關《第03章 詞法分析與有窮自動機(2).ppt(59頁珍藏版)》請在人人文庫網上搜索。

1、3.4.5 DFA的化簡,1. DFA的化簡,所謂一個DFA M 的化簡是指尋找一個狀態數比 M 少的 DFA M ，使得 L(M)=L(M) 。,(1) 沒有多余狀態。,化簡了的DFA滿足兩個條件:,(2) 它的狀態集中沒有兩個狀態是 互相等價的。,所謂有窮自動機的多余狀態是指從該自動機的開始狀態出發，任何輸入串不能到達的狀態。,3.4.5 DFA的化簡,2. 多余狀態,3.等價狀態,設 DFA M(Q,f, S0, Z), s, t Q ，若對任何 *, f (s , )Z 當且僅當 f (t , )Z ，則稱狀態 s 和 t 是等價的。,例如，終態與非終態是可區別的。因為終態有一條到達自。

2、身的道路，而非終態沒有到達終態的道路。,3.4.5 DFA的化簡,如果 s 和 t 不等價, 則稱 s 和 t 是可區別的。,5.化簡方法,一致性條件: 狀態s和t必須同時為 終態或非終態。,4.兩個狀態等價的條件:,蔓延性條件: 對于所有輸入符號a, 狀態 s 和 t 必須轉到等價的狀態里。,輸入：一個DFA M 。,輸出：接受與M相同語言的DFA M ， 且其狀態數最少。,3.4.5 DFA的化簡,無多余狀態下把M的狀態集 Q劃分成一些不相交的子集，使得每個子集中任何兩個狀態是等價的，而任何兩個屬于不同子集的狀態都是可區別的。,化簡方法:,然后在每個子集中任取一個狀態作“代表”, 而刪去子。

3、集中其余狀態, 并把射向其余狀態的箭弧都改作射向作“代表”的狀態中。,3.4.5 DFA的化簡,A,F,G,I,L,M,W,Z,E,H,K,O,R,T,X,A,M,W,H,T,下面給出化簡算法的具體執行步驟:,1. 將DFA M的狀態集Q分成兩個子集：終態集F和非終態集F，形成初始分劃。,2. 對使用如下方法建立新劃分NEW：,(1) 把G劃分成新的子集，使得G的兩個狀態s和t屬于同一子集，當且僅當對任何輸入符號a ，狀態s和t轉換到的狀態都屬于的同一子集。,對的每個狀態子集G:,3.4.5 DFA的化簡,用G劃分出的所有新子集替換G, 形 成新的劃分NEW；,如果NEW，則執行第4步；否則令。

4、 NEW，重復第2步。,劃分結束后，對劃分中的每個狀態子集，選出一個狀態作代表，而刪去其它一切等價的狀態，并把指向其它狀態的箭弧改為指向這個作為代表的狀態。,3.4.5 DFA的化簡,例1. 將右面的DFA最小化,初始分劃=(A,B,C,DE),A,B,C,Da=B,分析 由圖可知，給定的DFA中無多余狀態。,A,B,C,Db=C,D,E,=(A,B,CDE),A,B,Ca=B,A,B,Cb=C,D,=(A,CBDE),A,Ca=B,A,Cb=C,=(A,CBDE),a,例2. 將右面的DFA M最小化,1,2l =2,=(1,20),分析 由圖可知，給定的DFA無多余狀態。,初始分劃=(1,。

5、20),1,2d =2,3.4.5 DFA的化簡,3.4.6 有窮自動機到正規式的轉換,1. 在 M 的轉換圖上添加兩個結點： X 結和Y結。從X結點用連線連結到M的所有初態結點，從 M 的所有終態結點用連線連結到 Y 結，從而構成一新的非確定有窮自動機 M，它只有一個初態結 X和一個終態結Y。顯然，L(M)=L(M)。即，這兩個NFA是等價的。,3.4.6 有窮自動機到正規式的轉換,2. 逐步消去M中的其它結點，直至只剩下X，Y結點。在消除結點過程中，逐步用正規式來標記相應的箭弧。,消除結點的過程是很直觀的，只需反復使用下圖的替換規則即可。,3.4.6 有窮自動機到正規式的轉換,對于,代換為。

6、,對于,代換為,代換為,對于,3.4.6 有窮自動機到正規式的轉換,例1. 設有窮自動機的狀態圖如圖所示,試求該自動機識別語言的正規式。,R=(10|01)(10|01)*,3.5 正規文法與有窮自動機,前面提到程序設計語言的單詞符號可用喬母斯基3型文法正規文法來描述 對于正規文法所描述的語言可用一種有窮自動機來識別 下面分別就左線性正規文法/右線性正規文法給出構造相應有窮自動機的方法,3.5 正規文法與有窮自動機,右線性正規文法到有窮自動機的轉換方法,則相應的有窮自窮自動機 M = (Q , , f , q0 , Z ),1. 令 Q= VND (D VN) Z=D = VT q0=S,2.。

7、 對G中每一形 AaB (A ,BVN ,aVT) 的產生式 , 令 f (A , a)=B,設給定了一個右線性正規文法 G = (VN ,VT , P , S),a= AB 令f (A , )=B,AaB Aa,3.5.1 右線性正規文法到有窮自動 機的轉換方法,3. 對G中每一形如Aa(AVN ,aVT) 的產生式, 令 f (A , a)=D,4. 對G中每一形如A (AVN )的產生 式, 令A為接受狀態或令 f (A , )=D,例1 構造下述文法GZ的有窮自動機。,Z0A,A0A | 0B,B1A | ,M = (Q , , f , q0 , Z ),G = (VN ,VT , P。

8、 , S),M=(VN D, VT ,f, Z, D),M=( Z,A,B,D, 0,1),f, Z, D),f =? 根據規則來確定,f(Z,0)=A f(Z,1)= f(z, )= f(A,0)=A,B f(A,1)= f(A, )= f(B,0)= f(B,1)=A f(B, )=D,Z0A,A0A | 0B,B1A | ,AaB (A ,BVN ,aVT),令 f (A , a)=B,Aa(AVN ,aVT), 令 f (A , a)=D,A (AVN ), 令A為接受狀態 或令 f (A , )=D,3.5.2 左線性正規文法到有窮自動 機的轉換方法,則相應的有窮自窮自動機 M = 。

9、(Q , , f , q0 , Z ),1. 令 Q= VNq0 (q0 VN) Z=S = VT,2. 對G中每一形如 ABa (A ,BVN ,aVT) 的產生式, 令 f (B , a)=A,設給定了一個左線性正規文法 G = (VN ,VT , P , S),a= AB 令f (B , )=A,ABa Aa,3.5.2 左線性正規文法到有窮自動 機的轉換方法,3. 對G中每一形如 Aa (AVN, aVT) 的產生式, 令 f (q0 , a) =A,例1. 構造下述文法GA的自動機。,其狀態圖如下圖所示。,顯然,該自動機是確定的。它識別的語言就是文法GA所描述的語言。 即 L(GA)。

10、=L(M)=00*11*,BB0 | 0,AA1 | B1,3.5.3 有窮自動機到正規文法的轉換,設給定有窮自動機M = (Q , , f , q0 , Z ),則相應的正規文法 G = (VN ,VT , P , S),1. 令 VN = Q VT = S = q0,3. 若f (A,a)=B 且BZ時，則將產生式 AaB | a 或將產生式AaB、B 加到P中。,3.5.3 有窮自動機到正規文法的轉換,若文法的開始符號S是一個終態，則 將產生式 S 加到P中。,例1 設有窮自動機 M=(S,A,a,b,0,1 ,f , S , A),M的狀態轉換圖如圖所示。,根據上述轉換規則,與M等價的。

11、正規文法G為:,其中P:,自動機M所識別的語言L(M)=L(G)=(a|b)(0|1|a|b)*。,f (S,a)=A f (S,b)=A,f (A,a)=A f (A,b)=A,f (A,0)=A f (A,1)=A,其中,G=(S,A,a,b,0,1,P,S),SaA | bA | a | b,AaA | bA| 0A | 1A | a | b | 0 | 1,例3 設DFA M=(A,B,C,D,0,1, , A,B),該自動機相應的狀態轉換圖如下圖所示。,構造一個右線性文法G,使得L(G)=L(M)。, (A,0)=B (A,1)=D, (B,0)=D (B,1)=C, (C,0)=B。

12、 (C,1)=D, (D,0)=D (D,1)=D,其中：,從狀態轉換圖可以看出, 狀態D是多余的,可以去掉,于是得到與M等價的DFA M的狀態轉換圖如圖所示。,3.5.3 有窮自動機到正規文法的轉換,3.5.3 有窮自動機到正規文法的轉換,G=(A,B,C,0,1, P, A)其中P為,或,該自動機所識別的語言為 0(10)*。,A0B | 0,B1C,C0B | 0,根據轉換規則所求右線性文法為,A0B,B1C | ,C0B,C,A,0,0,1,3.6 詞法分析程序的編寫方法,構造詞法分析程序的方法:,第二種方法是利用詞法分析程序的自動生成工具LEX自動生成詞法分析程序,第一種方法是用手工。

13、方式，即根據識別語言單詞的狀態轉換圖，使用某種高級語言，例如C語言直接編寫詞法分析程序。,下面以某種簡單語言為例，對第一種方法作簡要的介紹。,例如，下表列出了某個簡單語言的所有單詞符號，以及它們的種別編碼和單詞值。,右圖是一張識別前表的單詞符號的狀態轉換圖。,圖中, 狀態0為初態, 凡帶雙圈者均為終態; 狀態17是識別不出單詞符號的出錯情況。 l 代表任一字母，d 代表任一數字。,根據這張轉換圖，我們用C語言直接編寫出識別該語言所有單詞的詞法分析程序。,3.6 詞法分析程序的編寫方法,在例中，我們規定所有關鍵字, 用戶不得使用它們作為自己定義的標識符，這樣我們可以把關鍵字作為一類特殊的標識符來。

14、處理，不再專設對應的轉換圖。但需把它們預先安排在一個表格中，此表叫關鍵字表。當利用狀態轉換圖識別出一個標識符時，就去查關鍵字表，以確定它是否是一個關鍵字。,其次規定，若關鍵字、標識符和常數之間沒有確定的運算符或界符作間隔，則必須至少用一個空白符作間隔，即此時的空白符是有意義的。,根據狀態轉換圖構造出詞法分析程序最簡單的辦法是讓每個狀態對應一小段程序。,1. ch 字符變量，存放當前讀進的源程序字符。,2. token 字符數組, 存放構成單詞符號的字符串。,3. getch( )讀字符函數，每調用一次從輸入緩沖區中讀進源程序的下一個字符放在ch中，并把讀字符指針指向下一個字符。,4. getb。

15、c( )函數，每次調用時，檢查ch中的字符是否為空白字符，若是空白字符，則反復調用getbc( )，直至ch中進入一個非空白字符為止。,首先，我們引進詞法分析程序所用的全局變量和需調用的函數如下：,3.6 詞法分析程序的編寫方法,6. letter(ch) 和 degit(ch)布爾函數，它們分別判定 ch 中的字符是否為字母和數字， 從而給出true 或 false。,7. reserve( )整型函數，對token中的字符串查關鍵字表，若它是一個關鍵字, 則回送它的編碼，否則回送標識符的種別碼10。,5. concat( )函數，每次調用把當前ch中的字符與token中的字符串聯接。例如，。

16、假定token字符數組中原有值為 “ab”, ch中存放著 “c”,經調用concat( )后，token數組中的值變為“abc”。,3.6 詞法分析程序的編寫方法,8. retract( )函數，讀字符指針回退一個字符。,9. return( )函數，收集并攜帶必要的信息返回調用程序，即返回語法分析程序。,10. dtb( ) 進制轉換函數, 它將token中的數字串轉換成二進制數值表示, 并以此作為函數值返回。,根據該語言的狀態轉換圖用C語言編寫出詞法分析程序如下:,Scaner( ) token=NULL; getch( ); getbc( ); if (letter(ch) while。

17、(letter(ch) | digit(ch) concat( ); getch( ); retract( ); c=reserve( ); if(c!=10) return(c,token); else return( 10,token); ,相對于狀態轉換圖用C語言編寫出詞法分析程序如下:,else if(digit(ch) while (digit(ch) concat( ); getch( ); retract( ); return(11,dtb( ); ,else switch(ch) case+: return(13, ); break ; case-: return(14, );。

18、 break ; case*: return(15, ); break ; case/: return(16, ); break ; case) return(18, ); retract( ); return(19, ); break; case: : getch( ); if(ch= = =) return(22, ); retract( ); return(21, ); break; case;: return(23, ); break; default: error( ); break; ,由此可知, 只要構造出識別語言單詞符號的有窮自動機, 就很容易構造出識別語言單詞符號的詞法分析程。

19、序。,3.6 詞法分析程序的編寫方法,作業,1、用正規式描述下列正規集： (1)C語言的十六進制整數； (2)以ex開始或以ex結束的所有小寫字母構成的符號串； (3)十進制的偶數。 2、構造下列正規式所對應的最小化確定有限自動機： (1)(aa|b)*(a|bb)* (2)ab*c*d (3)(a|b)*| bb)*,本章小結,本章重點介紹了詞法分析程序的設計思想和構造方法。主要內容有：,1. 詞法分析程序的功能是從左到右掃描源程序字符串，根據語言的詞法規則識別出各類單詞符號。,輸出單詞符號的形式是二元組: (單詞種別，單詞自身值),本章小結,例如定義“標識符”單詞的正規式是 l (l | 。

20、d)*,正規文法是 標識符 l |標識符l | 標識符d,2程序語言單詞符號的兩種定義方式,正規文法,正規式,本章小結,3有窮自動機有確定的和非確定兩大類：,NFA N = (Q , , f , S , Z )其中f是多值映射函數，S為非空初態集。,有窮自動機通常表示為狀態轉換圖，它是有窮自動機的非形式化描述。,DFA M = (Q , , f , S , Z )其中是f單值映射函數，S是唯一初態,本章小結,從單詞兩種定義方式中構造詞法分析程序的過程是：,4正規式、正規文法和有窮自動機三者都是描述正規集的工具, 它們的描述能力是等價的，它們之間可相互轉換。,5證明兩正規式是等價的,如果它們的最。

21、小狀態DFA是相同的。也可以利用正規式的基本等價關系將一個正規式化簡來證明兩正規式之間的等價性或兩正規式識別的語言一樣。,本章小結,本章小結,例1 構造正規式R=1(0|1)*101的狀態最小化的DFA,分析 首先對R采用分裂法構造NFA，見下圖:,對NFA采用子集法構造其等價的DFA的狀態轉換矩陣,見右表,A F B C D E,字符,狀態,0,1,X,1,2,3,2,3,4,2,3,5,2,3,4,Y,2,3,2,3,1,2,3,2,3,4,2,3,2,3,4,2,3,5,2,3,4,2,3,2,3,4,Y,2,3,5,2,3,4,本章小結,對DFA采用分化的方法化簡，得到狀態最小化的DF。

22、A，見下圖 :,例2. 構造一個DFA它接收=0,1上所有滿足如下條件的字符串，每個1都有0直接跟在右邊。,分析 首先給出描述語言的正規式R=(0|10)*,采用分裂法從正規式構造NFA,采用子集法將NFA確定化為DFA,采用分化方法將DFA化簡,字符,狀態,0,1,X,A,Y,B,A,Y,A,Y,B,B,A,Y,A,Y,分析 給出描述語言的正規文法,S0S | 1A | A 0S,根據右線性文法構造有窮自動機的方法, 構造出如下的狀態轉換圖:,例2. 構造一個DFA它接收=0,1上所有滿足如下條件的字符串，每個1都有0直接跟在右邊。,S0A | 1B A1S | 1 B0S | 0,分析 根。

23、據正規文法轉換成正規式的方法，首先給出該 正規文法對應的正規式方程組：,S=0A+1B (1) A=1S+1 (2) B=0S+0 (3),將(2)、(3)代入(1)得 S=01S+01+10S+10 (4),對(4)使用求解規則得 S=(01|10)(01|10),即正規文法所生成語言的正規式是(01|10)(01|10)。,例3. 給出下述文法所對應的正規式：,例4 將右圖確定化和最小化。,圖示是一個無 邊轉移的NFA,采用子集法將NFA確定化為DFA,采用分化方法將DFA化簡,本章小結,字符,狀態,a,b,0,1,0,1,0,1,1,1,0,1,0,本章小結,例4. 設字母表=a,b，給出上的正規式 R= b*ab(b|ab)*,1. 試構造狀態最小化的DFA M，使得 L(M)=L(R)。,2. 求右線性文法G，使L(G)=L(M)。,本章小結,對正規式R=b*ab(b|ab)*采用分列法構造NFA，見下圖。,對NFA采用子集法構造其等價的DFA的狀態轉換矩陣，見表。,X B A Y E F,字符,狀態,a,b,X,1,2,1,2,4,5,Y,6,5,Y,3,3,3,1,2,1,2,4,5,Y,6,5,Y,5,Y,6,5,Y,本章小結,對DFA采用分化的方法得到狀態最小化的DFA，見圖。

總結

以上是生活随笔為你收集整理的利用自动机识别c 语言单词,第03章 词法分析与有穷自动机(2).ppt的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。