1、第三章 自動(dòng)機(jī),第2章介紹的文法是從語(yǔ)言生成的角度定義了,語(yǔ)言，本章則從識(shí)別語(yǔ)言出發(fā)，討論對(duì)語(yǔ)言的,另一種定義方式，即自動(dòng)機(jī),自動(dòng)機(jī)理論是編譯程序詞法分析的理論基礎(chǔ),3.1 轉(zhuǎn)換圖,定義：,1 至少有一個(gè)初始結(jié)點(diǎn),2 存在一些終止結(jié)點(diǎn)（可空）,3 在每個(gè)邊上有字母表上的符號(hào)串（可為空串）,有限方向圖,初始結(jié)點(diǎn)為 “ ”，終止結(jié)點(diǎn)用“”表示,例如：設(shè)字母表=0，1,轉(zhuǎn)換圖中從一初始結(jié)點(diǎn)到一終止結(jié)點(diǎn)的序列為路 若一條路產(chǎn)生字符串B，則稱轉(zhuǎn)換圖接受（識(shí)別）B,被轉(zhuǎn)換圖所接受的符號(hào)串集合記為L(zhǎng)（TG）,L（TG）=01，10，0100，1011，101100,第三章 詞法分析 5,3.2 確定有限自動(dòng)

2、機(jī)（DFA）,3.2.1 有限自動(dòng)機(jī)(Finite Automation,FA) 1、有限自動(dòng)機(jī) 有限自動(dòng)機(jī)是一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正則集。它為詞法分析程序的構(gòu)造提供了方法和工具。 有限自動(dòng)機(jī)是具有離散輸入輸出系統(tǒng)的數(shù)學(xué)模型。它具有有限數(shù)目的內(nèi)部狀態(tài)，系統(tǒng)可以根據(jù)當(dāng)前所處的狀態(tài)和面臨的輸入字符決定系統(tǒng)的后繼行為。其當(dāng)前狀態(tài)概括了過(guò)去輸入處理的信息。,第三章 詞法分析 6,有限自動(dòng)機(jī)模型,每讀入一個(gè)符號(hào)，讀頭向后移動(dòng)一個(gè)位置，有限控制器控制狀態(tài)轉(zhuǎn)移到下一個(gè)狀態(tài),在初始時(shí)，讀頭處于輸入帶的開(kāi)始位置，表示準(zhǔn)備讀入，狀態(tài)處于初始狀態(tài),整個(gè)模型由三部分組成： 輸入帶：存放輸入符號(hào) 讀頭：可以在輸入

3、帶上向后移動(dòng) 有限控制器：控制狀態(tài)發(fā)生變化,如果讀頭移動(dòng)到最后一個(gè)符號(hào)后面，狀態(tài)正好是終結(jié)狀態(tài)，則輸入帶上的符號(hào)組成的字能被該有限自動(dòng)機(jī)所識(shí)別,狀態(tài)分為初始狀態(tài)、中間狀態(tài)和終止?fàn)顟B(tài)。終止?fàn)顟B(tài)可以有若干個(gè)，而初始狀態(tài)一般只有一個(gè)。,如果讀頭移動(dòng)到最后一個(gè)符號(hào)后面，狀態(tài)不是終止?fàn)顟B(tài)，則說(shuō)明此輸入串錯(cuò)誤。,一個(gè)有限自動(dòng)機(jī)的工作狀態(tài)可用狀態(tài)轉(zhuǎn)換圖來(lái)描述,狀態(tài)和狀態(tài)之間存在著一種轉(zhuǎn)換關(guān)系。處在某一個(gè)狀態(tài)，當(dāng)讀入一個(gè)字符時(shí)，則使?fàn)顟B(tài)改變?yōu)榱硪粋€(gè)狀態(tài)，從而形成了狀態(tài)轉(zhuǎn)換，改變后的狀態(tài)稱為后繼狀態(tài),第三章 詞法分析 7,2、狀態(tài)轉(zhuǎn)換圖,例：正則式(|)*的狀態(tài)轉(zhuǎn)換圖形式如下：,第三章 詞法分析 8,3.2.2

4、 確定有限自動(dòng)機(jī)DFA(Deterministic FA) 1、定義：確定有限自動(dòng)機(jī)是一個(gè)五元式 M(S, K, F） 其中：S：狀態(tài)的非空有限集 ：輸入字母表 ：S S上的單值映射 K ：唯一的初態(tài)， K S F ：終止?fàn)顟B(tài)集， F S 注：這里確定的含義，就是狀態(tài)轉(zhuǎn)換關(guān)系是一個(gè)函數(shù)，即對(duì)于給定的當(dāng)前狀態(tài)s和當(dāng)前讀入的符號(hào)a，有唯一確定的下一狀態(tài)s。,由定義可見(jiàn)，有限自動(dòng)機(jī)只有一個(gè)初始狀態(tài)，可 以有若干個(gè)終止?fàn)顟B(tài)，且每個(gè)結(jié)點(diǎn)的所有輸出邊不同， 即后繼狀態(tài)是唯一的。,第三章 詞法分析 9,例：有DFA M =(0,1,2,3,a,b, ,0,3) 為：,(0,a) = 1 (0,b) = 2

5、(1,a) = 3 (1,b) = 2 (2,a) = 1 (2,b) = 3 (3,a) = 3 (3,b) = 3,狀態(tài)轉(zhuǎn)換關(guān)系表示： 狀態(tài)轉(zhuǎn)換矩陣： 狀態(tài)轉(zhuǎn)換圖：,第三章 詞法分析 10,2、DFA對(duì)字符串的接受 從狀態(tài)轉(zhuǎn)換圖看，存在一條從初態(tài)到某一終態(tài)的道路，且這條路上所有弧的標(biāo)記符連成的字符串為t，則t被DFA接受 不能被自動(dòng)機(jī)接受的字符串有兩種情況： 讀完輸入串，狀態(tài)不停在終止?fàn)顟B(tài)， 在讀過(guò)程中出現(xiàn)不存在的映射，使自動(dòng)機(jī)無(wú)法繼續(xù)動(dòng)作 若M的初態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)，則空字可為M所接受。,第三章 詞法分析 11,例：構(gòu)造一個(gè)DFA M，它接受字母表 a,b,c上，以a或b開(kāi)始的字符串，或

6、以c開(kāi) 始但所含的a不多于一個(gè)的字符串。,課堂練習(xí)：P79 3-5 （1）（2） 作業(yè)：P79 3-5 （3）,第三章 詞法分析 12,3.3、不確定有限自動(dòng)機(jī)NFA(Non-deterministic FA) 1、定義：不確定有限自動(dòng)機(jī)是一個(gè)五元式 M= (S, K, F） 其中： S：非空有限狀態(tài)集 ：有限字母表 ： S S的子集上的映射 K：初始狀態(tài)集， K S F ：終止?fàn)顟B(tài)集， F S 注：1)非確定主要是指后繼狀態(tài)可有多個(gè)。 2) DFA是NFA的特例。,第三章 詞法分析 13,例：NFA M=(S，P，Z，0，1，S，P，Z) 其中： (S，0)=P (S，1)=S，Z (Z，0

7、)=P (Z，1)=P (P，1)=Z,第三章 詞法分析 14,第三章 詞法分析 15,設(shè)A1，A2是同一字母表上的有限自動(dòng)機(jī)若有L（A1）=L（A2）則稱A1與 A2等價(jià) 即若兩個(gè)自動(dòng)機(jī)能夠接收相同的語(yǔ)言，則稱兩個(gè)自動(dòng)機(jī)等價(jià) 對(duì)于一個(gè)不確定有限自動(dòng)機(jī)AN，總存在一個(gè)確定有限自動(dòng)機(jī)AD，使得 L（AD）=L（AN） 也即NFA能接收的語(yǔ)言，也能找到一個(gè)等價(jià)的DFA接收該語(yǔ)言,第三章 詞法分析 16,NFA與DFA的變換 算法：1 若NFA的全部初始狀態(tài)為S1，S2，S3，Sn 則令DFA 的初始狀態(tài)為K=S1，S2，S3，Sn 2 設(shè)Q= Si，Si+1，Sj是DFA的一個(gè)狀態(tài)，若對(duì)符號(hào)a，在

8、NFA中有 (Si，Si+1，Sj,a)=Si ，Si+1 ，Sk 則令 (Si，Si+1，Sj,a)=Si ，Si+1 ，Sk 為DFA的一個(gè)映射 3 重復(fù)2 直到不出現(xiàn)新的狀態(tài)為止 4 上面得到的所有狀態(tài)構(gòu)成DFA的狀態(tài)S，映射構(gòu)成DFA的映射，NFA的字母表仍為DFA的字母表 5 在DFA的狀態(tài)中，凡含有NFA的終止?fàn)顟B(tài)的狀態(tài)為DFA的終止?fàn)顟B(tài),例：將不確定有限自動(dòng)機(jī)AN AN=S0，S1，S2，a，b，S0 ，S1，S2,狀態(tài)轉(zhuǎn)換圖：,轉(zhuǎn)換為確定有限自動(dòng)機(jī)AD,狀態(tài)轉(zhuǎn)換矩陣：,NFA與DFA對(duì)應(yīng)的轉(zhuǎn)換函數(shù),(S0,S1,a)=S1, (S0,S1,a)=S1,(S0,S1,b)=S0,

9、S2,(S0,S1,b)=S0,S2,(S1,b)=S2, (S1,b)=S2,(S0,S2,a)=S1, (S0,S2,a)=S1,(S0,S2,b)=S0, S1, S2, (S0,S2,b)=S0, S1, S2,(S2,b)=S1, (S2,b)=S1,(S0, S1, S2,a)=S1, (S0, S1, S2,a)=S1,(S0, S1, S2,b)=S0, S1, S2, (S0, S1, S2,b)=S0, S1, S2,有限確定自動(dòng)機(jī)AD為,AD=S，K，F(xiàn),S=S0,S1,S1,S0, S2,S2,S0, S1, S2,=a,b,K=S0,S1,F=S2,S0,S2,S0,

10、S1,S2,其中：,狀態(tài)轉(zhuǎn)換矩陣：,狀態(tài)轉(zhuǎn)換圖：,例：將NFA確定化為DFA,NFA：,NFA與DFA對(duì)應(yīng)的轉(zhuǎn)換函數(shù),(0,a)=0,1,(0,a)=0,1,(0,1,a)=0,1, (0,1,a)=0,1,(0,1,b)=1, (0,1,b)=1,(1,a)=0, (1,a)=0,(0,b)=1, (0,b)=1,有限確定自動(dòng)機(jī)AD為,AD=S，K，F(xiàn),其中:,S=0, 0,1,1,=a,b,F=0,0,1,K=0,狀態(tài)轉(zhuǎn)換矩陣：,狀態(tài)轉(zhuǎn)換圖：,3.4 自動(dòng)機(jī),轉(zhuǎn)換圖允許邊上有空符號(hào)串 ，而自動(dòng)機(jī)（狀態(tài)圖）不允許邊上有空符號(hào)串 ，這在設(shè)計(jì)編譯算法是常常要遇到的情況。為了方便，將自動(dòng)機(jī)擴(kuò)充，使

11、邊上有空符號(hào)串，將邊上有空符號(hào)串的自動(dòng)機(jī)稱為自動(dòng)機(jī)。對(duì)于含有空符號(hào)串的確定自動(dòng)機(jī)和不確定自動(dòng)機(jī)分別記為DFA 和NFA。,FA是FA的特例，對(duì)于任意FA 均可構(gòu)造一個(gè) 等價(jià)的FA，即L（FA）=L（ FA）,由 FA構(gòu)造FA的算法,1 在FA中找邊，如,且狀態(tài)B沒(méi)有邊輸出，此時(shí)進(jìn)行2，否則進(jìn)行4,2 設(shè)狀態(tài)B的直接后繼狀態(tài)為S1，S2，SK，且有,A,B,SI,A,B,ai,做如下工作：,I 消除原邊，引進(jìn)新邊,A,SI,ai,II 如果B為終止?fàn)顟B(tài)，則A為終止?fàn)顟B(tài),B,B,A,SI,ai,ai,ai,4 若還有邊，則一定有閉路，如：,此時(shí)將這個(gè)閉路中的狀態(tài)合并為一個(gè)結(jié)點(diǎn),S,A,B,a,S,

12、A,a,III 若有一條從初始狀態(tài)到A的路，則B為初始狀態(tài)， 即,3 重復(fù)2，直到1 中所指出的邊消除,Si,B,A,ai,ai,S,例1：,S3,a,找出所有的邊,S0,S1,S3,b,1,2,S0,S1,S0,a,3,S2,S0,S3,b,4,S2,S0,S0,a,S0,S1,S2,S4,b,b,a,b,b,a,b,a,例2：,S0,S1,S3,S2,a,b,a,a,a,找出所有的邊,S1,S3,S0,1,a,a,2,S0,S1,S0,a,a,3,S0,S1,S2,a,a,對(duì)于2II，A為初態(tài)除外；對(duì)于2III，包括A為初態(tài),第三章 詞法分析 30,3.5 自動(dòng)機(jī)的簡(jiǎn)化,對(duì)于任意給的一個(gè)確

13、定有限自動(dòng)機(jī)A1,構(gòu)造另 一個(gè)確定有限自動(dòng)機(jī)A2,使L(A1)=L(A2),并且A2的 狀態(tài)個(gè)數(shù)不多于A1的狀態(tài)個(gè)數(shù),而且一定能夠找 到一個(gè)狀態(tài)個(gè)數(shù)最少的A2,第三章 詞法分析 31,首先設(shè)Si為自動(dòng)機(jī)A的一個(gè)狀態(tài)，從Si出發(fā)能導(dǎo)出的所有符號(hào)串集合記為L(zhǎng)（ Si ） 設(shè)有兩個(gè)狀態(tài)Si，Sj，若有 L(Si)=L(Sj) 則稱Si和Sj是等價(jià)狀態(tài),一、 等價(jià)狀態(tài)與無(wú)關(guān)狀態(tài),第三章 詞法分析 32,對(duì)于狀態(tài)Si ，若對(duì)于任意輸入符號(hào)a都轉(zhuǎn)到其自身，而不能從它到達(dá) 終止?fàn)顟B(tài)，則稱Si為死狀態(tài) 對(duì)于狀態(tài)Si ，若從開(kāi)始狀態(tài)不可能到達(dá)該狀態(tài)，則稱Si為無(wú)用狀態(tài) 無(wú)用狀態(tài)和死狀態(tài)統(tǒng)稱為無(wú)關(guān)狀態(tài),一、 等價(jià)

14、狀態(tài)與無(wú)關(guān)狀態(tài),第三章 詞法分析 33,二 自動(dòng)機(jī)的簡(jiǎn)化 所謂自動(dòng)機(jī)簡(jiǎn)化就是求自動(dòng)機(jī)的狀態(tài)最少化問(wèn)題（即求自動(dòng)機(jī)的極小機(jī)），也即是在自動(dòng)機(jī)中合并等價(jià)狀態(tài)和刪除無(wú)關(guān)狀態(tài)。 化簡(jiǎn)(最小化)算法基本思想劃分法 1.將FA M 中的狀態(tài)劃分為互不相交的子集，每個(gè)子集內(nèi)部的狀態(tài)都等價(jià)；而在不同子集間的狀態(tài)均不等價(jià)。 2.從每個(gè)子集中任選一個(gè)狀態(tài)作為代表，消去其它等價(jià)狀態(tài)。 3.把那些原來(lái)射入其它等價(jià)狀態(tài)的弧改為射入相應(yīng)的代表狀態(tài)。,第三章 詞法分析 34,3、自動(dòng)機(jī)的簡(jiǎn)化方法,1 將自動(dòng)機(jī)的狀態(tài)分為終止?fàn)顟B(tài)集S1和非終止?fàn)?態(tài)集S2,S= S1 S2,顯然，終止?fàn)顟B(tài)和非終止 狀態(tài)所產(chǎn)生的符號(hào)串是不相同的

15、,對(duì)各狀態(tài)集每次按下面的方法進(jìn)一步劃分，直 到不再產(chǎn)生新的劃分,假設(shè)第i次劃分已將狀態(tài)集劃分為k組，即 S=S1（i） S2（i） Sk（i） 對(duì)于狀態(tài)集Sj（i）中（j=1，2，3，k）中的各個(gè)狀態(tài)逐個(gè)檢查， 設(shè)有兩個(gè)狀態(tài)Sj, Sj Sj（i）,且對(duì)于輸入符號(hào)a ， 有 (Sj,a)= Sm (Sj,a)= Sn 若Sm和Sn屬于同一個(gè)狀態(tài)集，則將Sj和Sj放在 同一個(gè)集合中，否則，將Sj和Sj分為兩個(gè)集合,第三章 詞法分析 35,重復(fù)2 ，直到每一個(gè)集合不能再劃分為止，此時(shí) 每一個(gè)狀態(tài)集合中的狀態(tài)均是等價(jià)狀態(tài)。,合并等價(jià)狀態(tài)，即在等價(jià)狀態(tài)集中任取一個(gè)狀 態(tài)為代表刪除其它一切等價(jià)狀態(tài)。,5

16、 刪除無(wú)關(guān)狀態(tài)。,解：,S=S0, S1, S2 S3, S4,1,2,S0, S1, S2,(S0, a)= S1 (S1, a)= S3 (S2, a)= S1,(S0, b)= S2 (S1, b)= S2 (S2,b)= S4,S0, S1, S2= S0 S1 S2,S3, S4,(S3, a)= S3 (S4, a)= S3,(S3, b)= S4 (S4, b)= S4,S0, S2, S1,S0 S2 S1,S= S0 S1 S2 S3,S4,S3,S4是等價(jià)狀態(tài)，合并S3和S4，簡(jiǎn)化后的自動(dòng)機(jī) 如下圖所示,例2：,解：,1 0,1 2,3,4,5,2,0,1,(0,a)=1

17、(1,a)=1,(0,b)=2 (1,b)=4,2,3,4,5,(2,a)=1 (4,a)=0 (3,a)=3 (5,a)=5,(2,b)=3 (4,b)=5,(3,b)=2 (5,b)=4,2,4 3,5,簡(jiǎn)化后的狀態(tài)為0,1 2,4 3,5,合并等價(jià)狀態(tài)，最后得自動(dòng)機(jī)如下圖,第二章 基礎(chǔ)知識(shí) 40,3.6 語(yǔ)法圖與自動(dòng)機(jī),正則表達(dá)式與自動(dòng)機(jī)的等價(jià)性,對(duì)于字母表上的任意正則表達(dá)式e，總存在一 確定有限自動(dòng)機(jī)A，使L（A）=L（e）.反之亦然。,第二章 基礎(chǔ)知識(shí) 41,正規(guī)式向有限自動(dòng)機(jī)M的轉(zhuǎn)換 1)由正規(guī)式 構(gòu)造一個(gè)如下僅有兩個(gè)結(jié)點(diǎn)x,y的狀態(tài)圖。 2)按所引入的3條正規(guī)式分裂規(guī)則分裂 。

18、3)重復(fù)步驟2直到每個(gè)弧上的標(biāo)記是上的一個(gè)字符或?yàn)橹埂?第二章 基礎(chǔ)知識(shí) 42,正規(guī)式分裂規(guī)則,返回,第二章 基礎(chǔ)知識(shí) 43,例：設(shè)l表示任意一個(gè)字母，d表示任意一個(gè)數(shù)字，則標(biāo)識(shí)符的正規(guī)表達(dá)式為 l（l | d）* 構(gòu)造DFA M,第二章 基礎(chǔ)知識(shí) 44,例：根據(jù)正規(guī)式(a|b)*(aa|bb)(a|b)*, 構(gòu)造DFA M，使之等價(jià),第二章 基礎(chǔ)知識(shí) 45,補(bǔ)充：不確定有限自動(dòng)機(jī)NFA(Non-deterministic FA) 1、定義：不確定有限自動(dòng)機(jī)是一個(gè)五元式 M= (S, , K, F） 其中： S：有限狀態(tài)集 ：有限字母表 ： S * 2S(S的子集)上的映射 K：非空的初態(tài)集，

19、 K 是S的真子集 F ：終止?fàn)顟B(tài)集， F是S的子集，可為空集,第二章 基礎(chǔ)知識(shí) 46,NFA的確定化,第一步：對(duì)狀態(tài)圖進(jìn)行改造： (1)增加狀態(tài)X,Y,使之成為新的唯一的初態(tài)和終態(tài)。從X引弧到原初態(tài)結(jié)點(diǎn), 從原終態(tài)結(jié)點(diǎn)引弧到Y(jié)結(jié)點(diǎn)。 (2) 對(duì)狀態(tài)圖進(jìn)一步進(jìn)行如下形式的改變,第二章 基礎(chǔ)知識(shí) 47,假定I是NFA的狀態(tài)集的一個(gè)子集，我們定義-closure(I)為 若狀態(tài)q I，則q -closure(I)； 任何狀態(tài)q I，則q經(jīng)任意條 弧而能到達(dá)的狀態(tài)的q -closure(I) 。 狀態(tài)集-closure(I) 稱為I的-閉包， 例： I=1, -closure(I)=1,2； I=5

20、, -closure(I)=5,6,2；,有一種算法，將NFA轉(zhuǎn)換成接受同樣語(yǔ)言的DFA.這種算法稱為子集法. 第二步：對(duì)上述改造后的NFA進(jìn)行確定化：,第二章 基礎(chǔ)知識(shí) 48,例： I=1,2, J = 5,3,4 ; Ia= -closure(5,3,4)=2,3,4,5,6,7,8,假定I是NFA的狀態(tài)集的一個(gè)子集，a是中的一個(gè)字符，我們定義 Ia = -closure(J) 其中J是所有那些可從I中的某一狀態(tài)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)的全體。,第二章 基礎(chǔ)知識(shí) 49,對(duì)一個(gè)NFA 進(jìn)行確定化的算法： 為方便，令字母表只包含兩個(gè)字符a和b。我們構(gòu)造一張表，此表的每一行含有三列，第一列記為I

21、，第二和第三列分別記為Ia和Ib 首先，置這個(gè)表的第一行第一列為-closure(X) ，這是一個(gè)包含NFA的初態(tài)X的-閉包 如果某一行的第一列的狀態(tài)子集已經(jīng)確定下來(lái)，例如記為I，那么，就可以根據(jù)上述的定義，求出這一行的第二和第三個(gè)子集Ia和Ib，然后，檢查這兩個(gè)Ia和Ib，看它們是否已在表的第一列中出現(xiàn)，把未曾出現(xiàn)者填入到后面空行的第一列位置上。 之后，對(duì)未填入Ia和Ib的新行重復(fù)上述過(guò)程，直至所有第二列和第三列的子集全都在第一列中出現(xiàn)了為止,第二章 基礎(chǔ)知識(shí) 50,NFA的確定化例子,第二章 基礎(chǔ)知識(shí) 51,等價(jià)的DFA,第二章 基礎(chǔ)知識(shí) 52,有NFA M定義如下： M= (S, , K

22、, F）其中：S=0，1 =a，b K=0 F=0 (0，a)=0，1 (0，b)=1 (1，a)=0,（1）畫(huà)出NFA M的狀態(tài)轉(zhuǎn)換圖 （2）構(gòu)造NFA M的最小DFA D,第二章 基礎(chǔ)知識(shí) 53,作業(yè)題： 試構(gòu)造一個(gè)識(shí)別除5余3的整數(shù)的有限機(jī),3.7 下推自動(dòng)機(jī)PDA,下推自動(dòng)機(jī)可以認(rèn)為是由一條輸入帶、一個(gè)有限 控制器和一個(gè)下推棧組成 。,定義,AP=(S, , , ,K, x0,F),S 狀態(tài)的非空有限集, 輸入字母表, 下推字母表，即棧符號(hào)的有限集, ： 是一個(gè)從S (U ) 到 S *的 一個(gè)映射 ,K 初始狀態(tài)集,X0 下推棧中的初始下推符號(hào)， X0 ,F 終止?fàn)顟B(tài)集,一 下推自動(dòng)機(jī)PDA,(Si,a,xk)=(Sj,B),表示在狀態(tài)Si ，輸入符號(hào)為a，且下推棧的棧頂符號(hào) 為xk時(shí)，進(jìn)入狀態(tài)Sj ，下推棧的棧頂符號(hào)xk由符號(hào)串B 代替，同時(shí)讀頭右移