編譯原理張晶版第三章詞法分析

1、第三章第三章 詞法分析詞法分析第三章第三章 詞法分析詞法分析詞法分析是編譯的第一個(gè)階段，在單詞的級(jí)別上分詞法分析是編譯的第一個(gè)階段，在單詞的級(jí)別上分析和翻譯源程序析和翻譯源程序理論基礎(chǔ)：理論基礎(chǔ)： - -有限自動(dòng)機(jī)理論有限自動(dòng)機(jī)理論 -有限自動(dòng)機(jī)理論與正規(guī)文法、正規(guī)式之有限自動(dòng)機(jī)理論與正規(guī)文法、正規(guī)式之間在描述語(yǔ)言方面有一一對(duì)應(yīng)的關(guān)系間在描述語(yǔ)言方面有一一對(duì)應(yīng)的關(guān)系學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo): : - -掌握有限自動(dòng)機(jī)與正規(guī)文法、正規(guī)式之掌握有限自動(dòng)機(jī)與正規(guī)文法、正規(guī)式之間的轉(zhuǎn)換間的轉(zhuǎn)換 -能夠構(gòu)造詞法分析程序，完成實(shí)驗(yàn)一能夠構(gòu)造詞法分析程序，完成實(shí)驗(yàn)一第三章第三章 詞法分析程序（詞法分析程序（2 2）

2、第一節(jié)第一節(jié) 正規(guī)文法和有限自動(dòng)機(jī)正規(guī)文法和有限自動(dòng)機(jī)一、正規(guī)文法、正規(guī)集與正規(guī)式正規(guī)文法、正規(guī)集與正規(guī)式1.1.正規(guī)文法正規(guī)文法 - -是是chomsky 3chomsky 3型文法型文法注：正規(guī)文法是描述正規(guī)集的文法，可用于描述注：正規(guī)文法是描述正規(guī)集的文法，可用于描述程序設(shè)計(jì)語(yǔ)言的語(yǔ)法部分。例如：標(biāo)識(shí)符這種單程序設(shè)計(jì)語(yǔ)言的語(yǔ)法部分。例如：標(biāo)識(shí)符這種單詞可以用下面的規(guī)則描述詞可以用下面的規(guī)則描述 （ ） :表示任意英文字母，表示任意英文字母， :表示任意表示任意數(shù)字?jǐn)?shù)字第三章第三章 詞法分析程序（詞法分析程序（3 3）2.2.正規(guī)集正規(guī)集-由正規(guī)文法產(chǎn)生的語(yǔ)言由正規(guī)文法產(chǎn)生的語(yǔ)言注：正規(guī)集

3、是集合，可有窮也可無(wú)窮，注：正規(guī)集是集合，可有窮也可無(wú)窮，可通過(guò)正規(guī)式來(lái)形式化表示可通過(guò)正規(guī)式來(lái)形式化表示第一節(jié)第一節(jié) 正規(guī)文法和有限自動(dòng)機(jī)正規(guī)文法和有限自動(dòng)機(jī)一、一、正規(guī)文法、正規(guī)集與正規(guī)式正規(guī)文法、正規(guī)集與正規(guī)式第三章第三章 詞法分析程序（詞法分析程序（4 4）3 3、正規(guī)式、正規(guī)式-設(shè)設(shè)A A是非空的有限字母表，是非空的有限字母表，A=aA=ai i i=1,2,.n, i=1,2,.n,則則 1. 1. e e, ,和和a ai i（i=1,2,.n)i=1,2,.n)都是正規(guī)式都是正規(guī)式 2. 2.若若a a，b b是正規(guī)式，則是正規(guī)式，則a a| |b b， a ab b , ,a

4、 a* *，b b* * 也是正規(guī)式也是正規(guī)式 3. 3.正規(guī)式只能通過(guò)有限次使用正規(guī)式只能通過(guò)有限次使用1,21,2規(guī)則獲得規(guī)則獲得注注: : 1) 1) “ | | ”讀作讀作 “ 或或 ” , ,也可寫(xiě)作為也可寫(xiě)作為“ “ + + ” 或或“ , ,” ， “ ” 讀作連接讀作連接 2) 2) 僅由字母表僅由字母表A=aA=ai i |i=1,2,.n|i=1,2,.n上的正規(guī)式上的正規(guī)式a a所組成的語(yǔ)言稱作正規(guī)集所組成的語(yǔ)言稱作正規(guī)集, ,記作記作L(L(a a) ) 3) 3)利用正規(guī)集相同利用正規(guī)集相同, ,可用來(lái)證明相應(yīng)正規(guī)式等價(jià)可用來(lái)證明相應(yīng)正規(guī)式等價(jià)第三章第三章 詞法分析程

5、序（詞法分析程序（5 5）一、正規(guī)文法、正規(guī)集與正規(guī)式一、正規(guī)文法、正規(guī)集與正規(guī)式例：證明例：證明 b(ab)b(ab)* *=(ba)=(ba)* *b b證明證明: : L(b(ab) L(b(ab)* *)=b,bab,babab,.)=b,bab,babab,. L(ba) L(ba)* *b)=b,bab,babab.b)=b,bab,babab. 又又正規(guī)集的前正規(guī)集的前n n項(xiàng)相同項(xiàng)相同 可知它們的正規(guī)集相等的可知它們的正規(guī)集相等的 故正規(guī)式故正規(guī)式b(ab)b(ab)* *=(ba)=(ba)* *b b第三章第三章 詞法分析程序（詞法分析程序（7 7）一、正規(guī)文法、正規(guī)集與正

6、規(guī)式一、正規(guī)文法、正規(guī)集與正規(guī)式4 .4 .三個(gè)概念間關(guān)系三個(gè)概念間關(guān)系-一個(gè)正規(guī)語(yǔ)言可以用正規(guī)文法定義，也可一個(gè)正規(guī)語(yǔ)言可以用正規(guī)文法定義，也可以用正規(guī)式定義，對(duì)任意一個(gè)正規(guī)文法，存在以用正規(guī)式定義，對(duì)任意一個(gè)正規(guī)文法，存在一個(gè)定義同一個(gè)語(yǔ)言的正規(guī)式；同樣，對(duì)每個(gè)一個(gè)定義同一個(gè)語(yǔ)言的正規(guī)式；同樣，對(duì)每個(gè)正規(guī)式，存在一個(gè)生成同一語(yǔ)言的正規(guī)文法；正規(guī)式，存在一個(gè)生成同一語(yǔ)言的正規(guī)文法；有些正規(guī)語(yǔ)言，很容易用文法定義，有些則用有些正規(guī)語(yǔ)言，很容易用文法定義，有些則用正規(guī)式定義更容易；兩者之間是可以轉(zhuǎn)換的，正規(guī)式定義更容易；兩者之間是可以轉(zhuǎn)換的，結(jié)構(gòu)上具有等價(jià)性。結(jié)構(gòu)上具有等價(jià)性。-由正規(guī)文法或正規(guī)

7、式定義的正規(guī)語(yǔ)言的集合由正規(guī)文法或正規(guī)式定義的正規(guī)語(yǔ)言的集合構(gòu)成正規(guī)集構(gòu)成正規(guī)集第三章第三章 詞法分析程序（詞法分析程序（6 6）一、正規(guī)文法、正規(guī)集與正規(guī)式一、正規(guī)文法、正規(guī)集與正規(guī)式5 .定理：定理：若若a,b,ga,b,g是正規(guī)式，則下述等價(jià)式成立是正規(guī)式，則下述等價(jià)式成立a+b=b+aa+b=b+aa+(b+g)=(a+b)+g a(bg)=(ab)ga+(b+g)=(a+b)+g a(bg)=(ab)ga(b+g)=ab+ag (a+b)g=ag+bga(b+g)=ab+ag (a+b)g=ag+bgea=ae=aea=ae=a(a(a* *) )* *=a=a* *a a* *=a

8、=a+ +e a+e a+ +=aa=aa* *=a=a* *a a(a+b)(a+b)* *=(a=(a* *+b+b* *) )* *=(a=(a* *，b b* *) )* *第三章第三章 詞法分析程序（詞法分析程序（8 8）一、正規(guī)文法、正規(guī)集與正規(guī)式一、正規(guī)文法、正規(guī)集與正規(guī)式6 .6 .正規(guī)文法轉(zhuǎn)換成相應(yīng)正規(guī)式正規(guī)文法轉(zhuǎn)換成相應(yīng)正規(guī)式其步驟為：其步驟為： -1. -1.由正規(guī)文法由正規(guī)文法G G的各個(gè)產(chǎn)生式寫(xiě)出對(duì)應(yīng)的的各個(gè)產(chǎn)生式寫(xiě)出對(duì)應(yīng)的正規(guī)方程式，得到聯(lián)立方程組正規(guī)方程式，得到聯(lián)立方程組 -2 .-2 .把方程組中的非終結(jié)符當(dāng)作變?cè)逊匠探M中的非終結(jié)符當(dāng)作變?cè)?-3.-3.求此正

9、規(guī)式方程組的解，得到關(guān)于開(kāi)始求此正規(guī)式方程組的解，得到關(guān)于開(kāi)始符號(hào)符號(hào)S S的解：的解： S= S= w w, ,w wVVT T* *, ,w w就是所求正規(guī)式就是所求正規(guī)式第三章第三章 詞法分析程序（詞法分析程序（1010） 假設(shè)正規(guī)文法G是右線性的，每個(gè)產(chǎn)生式的右部只含一個(gè)終結(jié)符，從文法G的產(chǎn)生式獲得相應(yīng)正規(guī)式方程式的規(guī)則如下： （1）若有Aa，則有A=a；若有A，則A= ； （2）若有AaA，則有A=a*A； （3）若有AaB且BA，則有A=aB； （4）若有Aa1|a2|an|aA，則有 A=a*(a1|a2|an)；例：已知正規(guī)文法例：已知正規(guī)文法G1G1的產(chǎn)生式，求出它所定義的的

10、產(chǎn)生式，求出它所定義的正規(guī)式正規(guī)式 -產(chǎn)生式為：產(chǎn)生式為：S aS |aB B bB |bA A cA |c 解：解：1.1.由產(chǎn)生式寫(xiě)出對(duì)應(yīng)的聯(lián)立方程組由產(chǎn)生式寫(xiě)出對(duì)應(yīng)的聯(lián)立方程組 S = a*S (1) S=aB (2) B= b*B (3) B=bA (4) A = c*A (5) A=c (6)第三章第三章 詞法分析程序（詞法分析程序（1111） 2.根據(jù)定理根據(jù)定理: :將將(6)代入代入(5)得到得到A=c+ (7)將將(7)代入代入(4)得到得到B=bc+ (8)將將(8)代入代入(3)得到得到B=b+c+ (9)將將(9)代入代入(2)得到得到S=ab+c+ (10)將將(10

11、)代入代入(1)得到得到S=a+b+c+ 3. 故：正規(guī)式為故：正規(guī)式為S=a+b+c+第三章第三章 詞法分析程序（詞法分析程序（1212）二、有限自動(dòng)機(jī)二、有限自動(dòng)機(jī)（Finite automation FA)1 1、有限自動(dòng)機(jī)、有限自動(dòng)機(jī)有限自動(dòng)機(jī)是一種識(shí)別裝置，他能準(zhǔn)確地識(shí)別正規(guī)有限自動(dòng)機(jī)是一種識(shí)別裝置，他能準(zhǔn)確地識(shí)別正規(guī)集，它為詞法分析程序的構(gòu)造提供了方法和工具。集，它為詞法分析程序的構(gòu)造提供了方法和工具。有限自動(dòng)機(jī)是具有離散輸入輸出系統(tǒng)的數(shù)學(xué)模型，有限自動(dòng)機(jī)是具有離散輸入輸出系統(tǒng)的數(shù)學(xué)模型，它具有有限數(shù)目的內(nèi)部狀態(tài)，系統(tǒng)可以根據(jù)當(dāng)前所它具有有限數(shù)目的內(nèi)部狀態(tài)，系統(tǒng)可以根據(jù)當(dāng)前所處的狀

12、態(tài)和面臨的輸入字符決定系統(tǒng)的后繼行為，處的狀態(tài)和面臨的輸入字符決定系統(tǒng)的后繼行為，其當(dāng)前狀態(tài)概括了過(guò)去輸入處理的信息其當(dāng)前狀態(tài)概括了過(guò)去輸入處理的信息第三章第三章 詞法分析程序（詞法分析程序（1313）2 2、有限自動(dòng)機(jī)模型、有限自動(dòng)機(jī)模型abcde.z輸入帶輸入帶有限狀態(tài)控制器有限狀態(tài)控制器讀頭讀頭狀態(tài)變換狀態(tài)變換注：狀態(tài)分為初始狀態(tài)，中間狀態(tài)和終止?fàn)顟B(tài)注：狀態(tài)分為初始狀態(tài)，中間狀態(tài)和終止?fàn)顟B(tài). .終終止?fàn)顟B(tài)可以有若干個(gè)，而初始狀態(tài)一般只有一個(gè)止?fàn)顟B(tài)可以有若干個(gè)，而初始狀態(tài)一般只有一個(gè)第三章第三章 詞法分析程序（詞法分析程序（1414）2 2、有限自動(dòng)機(jī)模型、有限自動(dòng)機(jī)模型abcde.z輸入

13、帶輸入帶有限狀態(tài)控制器有限狀態(tài)控制器讀頭讀頭狀態(tài)：初態(tài)狀態(tài)：初態(tài)第三章第三章 詞法分析程序（詞法分析程序（1515）2 2、有限自動(dòng)機(jī)模型、有限自動(dòng)機(jī)模型abcde.z輸入帶輸入帶有限狀態(tài)控制器有限狀態(tài)控制器讀頭讀頭狀態(tài)：中間狀態(tài)狀態(tài)：中間狀態(tài)第三章第三章 詞法分析程序（詞法分析程序（1616）2 2、有限自動(dòng)機(jī)模型、有限自動(dòng)機(jī)模型a ab bc cd de e.z z輸入帶輸入帶有限狀態(tài)控制器有限狀態(tài)控制器讀頭讀頭狀態(tài)：終態(tài)狀態(tài)：終態(tài)讀頭全部讀完，而此時(shí)狀態(tài)是終止?fàn)顟B(tài)，則讀頭全部讀完，而此時(shí)狀態(tài)是終止?fàn)顟B(tài)，則說(shuō)明此輸入串正確說(shuō)明此輸入串正確第三章第三章 詞法分析程序（詞法分析程序（1717）

14、a ab bc cd de e.z z輸入帶輸入帶有限狀態(tài)控制器有限狀態(tài)控制器讀頭讀頭狀態(tài)：非終態(tài)狀態(tài)：非終態(tài)2 2、有限自動(dòng)機(jī)模型、有限自動(dòng)機(jī)模型讀頭全部讀完，而此時(shí)狀態(tài)不是終止?fàn)顟B(tài)，則說(shuō)明讀頭全部讀完，而此時(shí)狀態(tài)不是終止?fàn)顟B(tài)，則說(shuō)明此輸入串錯(cuò)誤此輸入串錯(cuò)誤注：可用狀態(tài)轉(zhuǎn)換圖表示狀態(tài)變換，狀態(tài)用結(jié)點(diǎn)表示，注：可用狀態(tài)轉(zhuǎn)換圖表示狀態(tài)變換，狀態(tài)用結(jié)點(diǎn)表示，讀入符號(hào)用邊表示讀入符號(hào)用邊表示第三章第三章 詞法分析程序（詞法分析程序（1818）二、有限自動(dòng)機(jī)（二、有限自動(dòng)機(jī)（Finite automation -FA)Finite automation -FA)正規(guī)式正規(guī)式: : （ ）* *的狀態(tài)轉(zhuǎn)

15、換的狀態(tài)轉(zhuǎn)換狀態(tài)轉(zhuǎn)換圖形式如下：狀態(tài)轉(zhuǎn)換圖形式如下：1 12 2字母字母字母字母數(shù)字?jǐn)?shù)字程序中標(biāo)識(shí)符的程序中標(biāo)識(shí)符的xtempxtemp的識(shí)別匹配過(guò)為：的識(shí)別匹配過(guò)為：12222x2temp第三章第三章 詞法分析程序（詞法分析程序（1919）二、有限自動(dòng)機(jī)（二、有限自動(dòng)機(jī)（Finite automation FA)Finite automation FA)1 12 2字母字母數(shù)字?jǐn)?shù)字q0q100101字母字母第三章第三章 詞法分析程序（詞法分析程序（2020）二、有限自動(dòng)機(jī)（二、有限自動(dòng)機(jī)（Finite automation FA)Finite automation FA)3、確定有限自動(dòng)機(jī)確

16、定有限自動(dòng)機(jī)DFADFA（Deterministic FA)Deterministic FA) 定義：確定有限自動(dòng)機(jī)定義：確定有限自動(dòng)機(jī)DFADFA是一個(gè)五元式是一個(gè)五元式 M(S, ,f,s M(S, ,f,s0 0,Z),Z)- - 其中：其中：S S：有限狀態(tài)集：有限狀態(tài)集- - ：有限字母表：有限字母表- f: S- f: S S S上的單值映射，上的單值映射，f(s,a)=sf(s,a)=s- s- s0:0:唯一的初態(tài)唯一的初態(tài)，s s0 0SS(1)(1)- Z:- Z:終止?fàn)顟B(tài)集，終止?fàn)顟B(tài)集，ZSZS注：這里確定的含義，就是狀態(tài)轉(zhuǎn)換關(guān)系注：這里確定的含義，就是狀態(tài)轉(zhuǎn)換關(guān)系f f

17、是一個(gè)函數(shù)，即對(duì)是一個(gè)函數(shù)，即對(duì)于給定的當(dāng)前狀態(tài)于給定的當(dāng)前狀態(tài)S S和當(dāng)前讀入的符號(hào)和當(dāng)前讀入的符號(hào)a a，有唯一確定的下一，有唯一確定的下一狀態(tài)狀態(tài)SS第三章第三章 詞法分析程序（詞法分析程序（2121）二、有限自動(dòng)機(jī)（二、有限自動(dòng)機(jī)（Finite automation FA)Finite automation FA)（2 2）狀態(tài)轉(zhuǎn)換表示）狀態(tài)轉(zhuǎn)換表示-狀態(tài)轉(zhuǎn)換矩陣：狀態(tài)轉(zhuǎn)換矩陣：DFADFA的映射關(guān)系由一個(gè)矩陣來(lái)表示。的映射關(guān)系由一個(gè)矩陣來(lái)表示。-狀態(tài)轉(zhuǎn)換圖：狀態(tài)轉(zhuǎn)換圖： 注：注：1 1）用矩陣表示轉(zhuǎn)換便于計(jì)算機(jī)處理，但不直觀，）用矩陣表示轉(zhuǎn)換便于計(jì)算機(jī)處理，但不直觀，而用狀態(tài)轉(zhuǎn)換圖表

18、示比較直觀而用狀態(tài)轉(zhuǎn)換圖表示比較直觀 2 2）在整個(gè)狀態(tài)轉(zhuǎn)換圖中只有一個(gè)初始狀態(tài)結(jié)點(diǎn)，）在整個(gè)狀態(tài)轉(zhuǎn)換圖中只有一個(gè)初始狀態(tài)結(jié)點(diǎn)，用用“ ”“ ”射入的結(jié)點(diǎn)表示初始狀態(tài)，可有若干終止?fàn)钌淙氲慕Y(jié)點(diǎn)表示初始狀態(tài)，可有若干終止?fàn)顟B(tài)（也可能沒(méi)有），用雙圓圈表示。若初始狀態(tài)結(jié)點(diǎn)同態(tài)（也可能沒(méi)有），用雙圓圈表示。若初始狀態(tài)結(jié)點(diǎn)同時(shí)又是終止?fàn)顟B(tài)結(jié)點(diǎn)，則表示空串時(shí)又是終止?fàn)顟B(tài)結(jié)點(diǎn)，則表示空串e e可為相應(yīng)可為相應(yīng)DFADFA識(shí)別。識(shí)別。第三章第三章 詞法分析程序（詞法分析程序（2222）例例： 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,

19、b)=2- f(2,a)=1 f(2,b)=3 f(3,a)=3 f(3,b)=3 輸輸 入入ab012132213333狀態(tài)狀態(tài)狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣102ababbaba3第三章第三章 詞法分析程序（詞法分析程序（2323）例：構(gòu)造一個(gè)例：構(gòu)造一個(gè)DFA MDFA M，它接受字母表，它接受字母表a,b,c a,b,c 上上, , 以以a a或或b b開(kāi)始的字符串，或以開(kāi)始的字符串，或以c c開(kāi)始但所含的開(kāi)始但所含的a a不多于一不多于一個(gè)的字符串。個(gè)的字符串。0132accbbabcbca第三章第三章 詞法分析程序（詞法分析程序（2424）故故：DFA： M=（0,1,2,3,a,b,c

20、,f,0,1,2,3)-其中其中：f: f(0,a)=1 f(0,b)=1 f(0,c)=2 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 第三章第三章 詞法分析程序（詞法分析程序（2525）二、有限自動(dòng)機(jī)（二、有限自動(dòng)機(jī)（Finite automation -FA)Finite automation -FA)(3) 、一步動(dòng)作一步動(dòng)作-每讀一個(gè)字符，狀態(tài)就向前進(jìn)至下一狀態(tài)；記為每讀一個(gè)字符，狀態(tài)就向前進(jìn)至下一狀態(tài)；記為“ ”，- k 表示自動(dòng)機(jī)做了表示自動(dòng)機(jī)做了k k步動(dòng)作步動(dòng)作- *表示自動(dòng)機(jī)

21、做了表示自動(dòng)機(jī)做了0 0步動(dòng)作或步動(dòng)作或0 0步以上的動(dòng)作步以上的動(dòng)作- +表示自動(dòng)機(jī)做了表示自動(dòng)機(jī)做了1 1步動(dòng)作或步動(dòng)作或1 1步以上的動(dòng)作步以上的動(dòng)作(4)4)、DFADFA對(duì)字符串的識(shí)別對(duì)字符串的識(shí)別定義：串定義：串a(chǎn) a*為為DFA M=(S, ,f,s0,Z)所識(shí)別，所識(shí)別，當(dāng)前僅當(dāng)當(dāng)前僅當(dāng)（s0,a a) *(s,e e),且且sZ第三章第三章 詞法分析程序（詞法分析程序（2626）(4)(4)、DFADFA對(duì)字符串的識(shí)別對(duì)字符串的識(shí)別二、有限自動(dòng)機(jī)（二、有限自動(dòng)機(jī)（Finite automation-FA)Finite automation-FA)注：能被注：能被DFA MDF

22、A M所接受的字符串的集合，稱為所接受的字符串的集合，稱為自動(dòng)機(jī)自動(dòng)機(jī)M M所能識(shí)別的語(yǔ)言，記為所能識(shí)別的語(yǔ)言，記為L(zhǎng)(M)L(M)不能被不能被DFA MDFA M所接受的字符串有兩種情況：所接受的字符串有兩種情況：-讀完輸入串，狀態(tài)不停在終止?fàn)顟B(tài)，讀完輸入串，狀態(tài)不停在終止?fàn)顟B(tài)， 即即：（s0,a a) * (s,e e),且且s Z-在讀過(guò)程中出現(xiàn)不存在的映射，使自動(dòng)機(jī)在讀過(guò)程中出現(xiàn)不存在的映射，使自動(dòng)機(jī)無(wú)法繼續(xù)工作。無(wú)法繼續(xù)工作。第三章第三章 詞法分析程序（詞法分析程序（2727）二、有限自動(dòng)機(jī)（二、有限自動(dòng)機(jī)（Finite automation- FA)Finite automatio

23、n- FA)4 .4 .不確定有限自動(dòng)機(jī)不確定有限自動(dòng)機(jī)NFA(Non-deterministic FA)NFA(Non-deterministic FA)（1 1）定義：不確定有限自動(dòng)機(jī)是一個(gè)五元式，）定義：不確定有限自動(dòng)機(jī)是一個(gè)五元式， M= M=（S, ,f,SS, ,f,S0,0,Z)Z)-其中：其中：S:S:有限狀態(tài)集有限狀態(tài)集-：有限字母表：有限字母表- f:S- f:S 2 2s s(S(S的子集）上的映射的子集）上的映射-S-S0 0：非空的初態(tài)集，：非空的初態(tài)集，S S0 0是是S S的真子集的真子集-Z-Z：終止?fàn)顟B(tài)集，：終止?fàn)顟B(tài)集，Z Z是是S S的子集，可為空集的子集，

24、可為空集注：注：1 1）非確定主要是指后繼狀態(tài)可有多個(gè)）非確定主要是指后繼狀態(tài)可有多個(gè) 2 2）DFADFA是是NFANFA的特例的特例第三章第三章 詞法分析程序（詞法分析程序（2828）例：設(shè)例：設(shè)NFA M=NFA M=（qq0 0,q,q1 1,0,1,f,q,0,1,f,q0 0,q,q1 1)映射為映射為01q0q0q1q1q0,q1q0字符字符狀態(tài)狀態(tài)q010001q1第三章第三章 詞法分析程序（詞法分析程序（2929）二二、有限自動(dòng)機(jī)有限自動(dòng)機(jī)（Finite automation -FA)4 4、不確定有限自動(dòng)機(jī)、不確定有限自動(dòng)機(jī)NFA(Non-deterministic -NF

25、A)NFA(Non-deterministic -NFA)(2).(2).兩自動(dòng)機(jī)等價(jià)：兩自動(dòng)機(jī)等價(jià)：-任何兩個(gè)有限自動(dòng)機(jī)任何兩個(gè)有限自動(dòng)機(jī)M M和和MM，若它們識(shí)別的語(yǔ)言，若它們識(shí)別的語(yǔ)言相同（相同（L(M)=L(M)L(M)=L(M)）, ,則稱則稱M M和和MM等價(jià)等價(jià)-注：存在判定任何兩個(gè)有限自動(dòng)機(jī)等價(jià)性的算法注：存在判定任何兩個(gè)有限自動(dòng)機(jī)等價(jià)性的算法5 5、NFA NFA 確定化確定化(1).定理：對(duì)于每個(gè)定理：對(duì)于每個(gè)NFA MNFA M，存在一個(gè)，存在一個(gè)DFA M DFA M L(M)=L(M)L(M)=L(M)，即，設(shè)，即，設(shè)L L是一是一NFANFA接受的正規(guī)集，則存接受的

26、正規(guī)集，則存在一個(gè)在一個(gè)DFADFA接受接受L L第三章第三章 詞法分析程序（詞法分析程序（3030）二、有限自動(dòng)機(jī)（二、有限自動(dòng)機(jī)（Finite automation FA)Finite automation FA)(2)(2)算法算法由由NFA M=NFA M=（S,f,SS,f,S0 0,Z,Z ）構(gòu)造一個(gè)等價(jià)的）構(gòu)造一個(gè)等價(jià)的DFA M=DFA M=（ Q,Q,I,I0 0,F,F）1.1.取取I I0 0=S=S0 0，2.2.若狀態(tài)集若狀態(tài)集Q Q中有狀態(tài)中有狀態(tài)I Ii i=S=S0 0，S S1 1SSj j ，S SK KSS，0Kj0Kj；而且而且M M中有中有f f（SS

27、0 0，S S1 1,.S,.SJ J,a),a)=f(s=f(s0 0,a) f(s,a) f(s1 1,a) . f(s,a) . f(sj j,a)= f(s,a)= f(sk k,a),a)=(s=(s0 0,s,s1 1,.s,.st t)=I)=It t, ,若若I It t不在不在Q Q中，則將中，則將I It t加入加入Q QjK=0第三章第三章 詞法分析程序（詞法分析程序（3131）(2)(2)、算法（續(xù)）、算法（續(xù)）3.3.重復(fù)步驟重復(fù)步驟2 2，直到，直到Q Q中無(wú)新?tīng)顟B(tài)加入為止。中無(wú)新?tīng)顟B(tài)加入為止。4.4.取終態(tài)取終態(tài)F=I|IQF=I|IQ，且，且IZ IZ 注：注：

28、1 1）上述過(guò)程可在有限步內(nèi)完成，因?yàn)椋┥鲜鲞^(guò)程可在有限步內(nèi)完成，因?yàn)镸 M機(jī)狀態(tài)的冪集是有機(jī)狀態(tài)的冪集是有限的；限的； 2 2）上述過(guò)程也可用表格法來(lái)描述，其中列是字符集）上述過(guò)程也可用表格法來(lái)描述，其中列是字符集中中的字符；行是的字符；行是Q Q中的各狀態(tài)，開(kāi)始僅包含中的各狀態(tài)，開(kāi)始僅包含I I0 0狀態(tài)，隨著算法狀態(tài)，隨著算法的執(zhí)行，的執(zhí)行，Q Q的狀態(tài)逐漸增多直至不再增加為止；表格元素就的狀態(tài)逐漸增多直至不再增加為止；表格元素就是是映射函數(shù)。映射函數(shù)。二、有限自動(dòng)機(jī)（二、有限自動(dòng)機(jī)（Finite automation FA)Finite automation FA)第三章第三章 詞法分

29、析程序（詞法分析程序（3232）二、有限自動(dòng)機(jī)（二、有限自動(dòng)機(jī)（Finite automation FA)Finite automation FA)注：注：3 3）NFANFA確定化的實(shí)質(zhì)是以原有狀態(tài)集的覆蓋片確定化的實(shí)質(zhì)是以原有狀態(tài)集的覆蓋片（COVERCOVER）作為）作為DFADFA的一個(gè)狀態(tài)。將原狀態(tài)間的轉(zhuǎn)換的一個(gè)狀態(tài)。將原狀態(tài)間的轉(zhuǎn)換改為覆蓋片間的轉(zhuǎn)換，從而將不確定問(wèn)題確定化。改為覆蓋片間的轉(zhuǎn)換，從而將不確定問(wèn)題確定化。 4 4）通常，經(jīng)確定化后，狀態(tài)數(shù)增加，而且可能）通常，經(jīng)確定化后，狀態(tài)數(shù)增加，而且可能出現(xiàn)一些等價(jià)狀態(tài)，這時(shí)需要化簡(jiǎn)。出現(xiàn)一些等價(jià)狀態(tài)，這時(shí)需要化簡(jiǎn)。第三章第三章

30、詞法分析程序（詞法分析程序（3333）二、有限自動(dòng)機(jī)（二、有限自動(dòng)機(jī)（Finite automation FA)Finite automation FA) 例：設(shè)例：設(shè)NFA M=NFA M=（qq0 0,q,q1 1,0,1,f,q,0,1,f,q0 0,q,q1 1) 映射為映射為 將其確定化將其確定化01q0q0q1q1q0,q1q0字符字符狀態(tài)狀態(tài)q010001q1第三章第三章 詞法分析程序（詞法分析程序（3434）MM的狀態(tài)：的狀態(tài)：I I0 0=q=q0 0,則則Q Q中就有了中就有了I I0 0狀態(tài)。狀態(tài)。由由Q Q中的狀態(tài)中的狀態(tài)I I0 0 =q=q0 0,查看查看M M機(jī)，

31、有機(jī)，有f(qf(q0 0,0)=q,0)=q0 0= I= I0 0 f(qf(q0 0,1)=q,1)=q1 1= I= I1 1 此時(shí)，此時(shí)，Q=IQ=I0 0， I I1 1 由由Q Q中的狀態(tài)中的狀態(tài)I I1 1=q=q1 1,查看查看M M機(jī)。機(jī)。 有：有：f(qf(q1 1,0)= q,0)= q0 0, q, q1 1= I= I2 2, f(q, f(q1 1,1)=q,1)=q0 0= I= I0 0 此時(shí)，此時(shí)，Q=IQ=I0 0, I, I1 1, I, I2 2 由由Q Q中的狀態(tài)中的狀態(tài)I I2 2=q=q0 0, q, q1 1 ，查看，查看M M機(jī)，機(jī)， 有：有

32、： f(qf(q0 0, q, q1 1,0)= q,0)= q0 0, q, q1 1= I= I2 2, , f(q f(q0 0, q, q1 1,1)= q,1)= q0 0, q, q1 1= I= I2 2， 此時(shí)此時(shí),Q=I,Q=I0 0，I I1 1，I I2 2 F=IF=I1 1， I I2 2 第三章第三章 詞法分析程序（詞法分析程序（3535）NFA NFA 經(jīng)過(guò)確定化后，經(jīng)過(guò)確定化后，變?yōu)椋鹤優(yōu)椋?DFA M=(IDFA M=(I0 0,I,I1 1,I,I2 2,0,1, ,0,1, ,I,I0 0,I,I1 1,I,I2 2)01I0=q0I0=q0I1=q1I1

33、=q1I2=q0,q1I0=q0I2=q0,q1I2=q0,q1I2=q0,q1Q第三章第三章 詞法分析程序（詞法分析程序（3636）01I0I0I1I1I2I0I2I2I2狀態(tài)轉(zhuǎn)換圖如下?tīng)顟B(tài)轉(zhuǎn)換圖如下: :I0I1I2011001第三章第三章 詞法分析程序（詞法分析程序（3737）二、有限自動(dòng)機(jī)（二、有限自動(dòng)機(jī)（Finite automation FA)Finite automation FA)6.6.確定有限自動(dòng)機(jī)的化簡(jiǎn)確定有限自動(dòng)機(jī)的化簡(jiǎn)( (最小化最小化) )(1)(1)化簡(jiǎn)條件化簡(jiǎn)條件: :接受的語(yǔ)言必須相同接受的語(yǔ)言必須相同(2)(2)化簡(jiǎn)化簡(jiǎn)( (最小化最小化) )算法基本思想算

34、法基本思想-劃分法劃分法-1.-1.將將DFA MDFA M中的狀態(tài)劃分為互不相交的子集中的狀態(tài)劃分為互不相交的子集, ,每個(gè)子集內(nèi)部的狀態(tài)都等價(jià)每個(gè)子集內(nèi)部的狀態(tài)都等價(jià), ,而在不同子集間的狀而在不同子集間的狀態(tài)均不等價(jià)態(tài)均不等價(jià)-2.-2.從每個(gè)子集中任選一個(gè)狀態(tài)作為代表從每個(gè)子集中任選一個(gè)狀態(tài)作為代表, ,消去消去其它等價(jià)狀態(tài)其它等價(jià)狀態(tài). .-3.-3.把那些原來(lái)射入其它等價(jià)狀態(tài)的弧改為射把那些原來(lái)射入其它等價(jià)狀態(tài)的弧改為射入相應(yīng)的代表狀態(tài)入相應(yīng)的代表狀態(tài)第三章第三章 詞法分析程序（詞法分析程序（3838）二、有限自動(dòng)機(jī)（二、有限自動(dòng)機(jī)（Finite automation FA)Fin

35、ite automation FA)6.6.確定有限自動(dòng)機(jī)的化簡(jiǎn)確定有限自動(dòng)機(jī)的化簡(jiǎn)( (最小化最小化) )(3) (3) 狀態(tài)等價(jià)狀態(tài)等價(jià): :設(shè)設(shè)DFA MDFA M中有兩個(gè)狀態(tài)中有兩個(gè)狀態(tài)s,ts,ts,t s,t 等價(jià)等價(jià): :-(s,w) -(s,w) * *(s(s1 1, ,e e) ) 同時(shí)同時(shí)(t,w) (t,w) * *(t(t1 1, ,e e),s),s1 1,t,t1 1都都是終態(tài)，是終態(tài)，wVwVt t* *, ,那如果從狀態(tài)那如果從狀態(tài)S S出發(fā)能讀出某個(gè)字出發(fā)能讀出某個(gè)字w w 而停于終態(tài)而停于終態(tài), ,從從t t出發(fā)也能讀出同樣的字出發(fā)也能讀出同樣的字w w而

36、停于終態(tài)而停于終態(tài), ,則稱則稱s,ts,t等價(jià)等價(jià)s,ts,t可區(qū)別可區(qū)別: :如果如果s,t s,t 不等價(jià)不等價(jià), ,則稱則稱s,ts,t可區(qū)別可區(qū)別第三章第三章 詞法分析程序（詞法分析程序（3939）6.6.確定有限自動(dòng)機(jī)的化簡(jiǎn)確定有限自動(dòng)機(jī)的化簡(jiǎn)(4) (4) 化簡(jiǎn)化簡(jiǎn)( (最小化最小化) )算法算法1.1.把狀態(tài)把狀態(tài)S S劃分為終態(tài)集和非終態(tài)集劃分為終態(tài)集和非終態(tài)集:0 0=I=I0 01 1,I,I0 02 2 I I0 01 1屬于非終態(tài)集屬于非終態(tài)集,I,I0 02 2屬于終態(tài)集屬于終態(tài)集, ,因?yàn)榻K態(tài)能識(shí)別因?yàn)榻K態(tài)能識(shí)別e e, ,而非終態(tài)不能，所以它們是可區(qū)別的而非終態(tài)

37、不能，所以它們是可區(qū)別的. .假定經(jīng)過(guò)假定經(jīng)過(guò)K K次劃分后：次劃分后：k k I Ik k0 0,I,Ik k1 1,.I,.Ik km m 這這m m個(gè)子集可區(qū)分個(gè)子集可區(qū)分, ,子集內(nèi)部還是否可以劃分子集內(nèi)部還是否可以劃分? ?-任取一個(gè)子集任取一個(gè)子集I IK Ki i=s=s1 1,s,s2 2,.s,.sk k.若存在某讀若存在某讀入字符入字符a,a,使使f(If(Ik ki i,a),a)的結(jié)果不是全部包含在的結(jié)果不是全部包含在k k的某的某個(gè)子集中個(gè)子集中, ,則說(shuō)明則說(shuō)明I Ik ki i中有不等價(jià)的狀態(tài)中有不等價(jià)的狀態(tài), ,還要進(jìn)一步還要進(jìn)一步劃分劃分. .-對(duì)對(duì)k k中所

38、有子集都進(jìn)行測(cè)試中所有子集都進(jìn)行測(cè)試, ,以完成一次劃分以完成一次劃分. .第三章第三章 詞法分析程序（詞法分析程序（4040）二、有限自動(dòng)機(jī)（二、有限自動(dòng)機(jī)（Finite automation FA)Finite automation FA)(4) (4) 化簡(jiǎn)化簡(jiǎn)( (最小化最小化) )算法（續(xù)）算法（續(xù)）3.3.重復(fù)步驟重復(fù)步驟2 2，直到所含的子集數(shù)不再增加為止。，直到所含的子集數(shù)不再增加為止。4.4.對(duì)每個(gè)子集任取一狀態(tài)為代表，若該子集包含原對(duì)每個(gè)子集任取一狀態(tài)為代表，若該子集包含原有的初態(tài)，則相應(yīng)代表狀態(tài)就是最小化后的有的初態(tài)，則相應(yīng)代表狀態(tài)就是最小化后的M M的初的初態(tài)；同樣，若

39、該子集包含原有的終態(tài)，則相應(yīng)代態(tài)；同樣，若該子集包含原有的終態(tài)，則相應(yīng)代表狀態(tài)就是最小化后表狀態(tài)就是最小化后M M的終態(tài)。的終態(tài)。6.6.確定有限自動(dòng)機(jī)的化簡(jiǎn)確定有限自動(dòng)機(jī)的化簡(jiǎn)第三章第三章 詞法分析程序（詞法分析程序（4141）二、有限自動(dòng)機(jī)（二、有限自動(dòng)機(jī)（Finite automation FA)Finite automation FA)注：注：1 1）當(dāng)一個(gè)自動(dòng)機(jī)沒(méi)有任何多余的狀態(tài)，并且它）當(dāng)一個(gè)自動(dòng)機(jī)沒(méi)有任何多余的狀態(tài)，并且它的狀態(tài)中沒(méi)有兩個(gè)是互相等價(jià)的時(shí)候，我們說(shuō)這個(gè)的狀態(tài)中沒(méi)有兩個(gè)是互相等價(jià)的時(shí)候，我們說(shuō)這個(gè)有限自動(dòng)機(jī)是化簡(jiǎn)了的。有限自動(dòng)機(jī)是化簡(jiǎn)了的。 2 2）可以通過(guò)消除多余狀

40、態(tài)，合并等價(jià)狀態(tài)而轉(zhuǎn)）可以通過(guò)消除多余狀態(tài)，合并等價(jià)狀態(tài)而轉(zhuǎn)化成一個(gè)最小化的、與之等價(jià)的有限自動(dòng)機(jī)?；梢粋€(gè)最小化的、與之等價(jià)的有限自動(dòng)機(jī)。6.6.確定有限自動(dòng)機(jī)的化簡(jiǎn)確定有限自動(dòng)機(jī)的化簡(jiǎn)第三章第三章 詞法分析程序（詞法分析程序（4242）例：設(shè)有一例：設(shè)有一DFADFA的狀態(tài)轉(zhuǎn)換圖如下，試化簡(jiǎn)之的狀態(tài)轉(zhuǎn)換圖如下，試化簡(jiǎn)之 125346babbaabaabab0ba第三章第三章 詞法分析程序（詞法分析程序（4343）解：解：1.1.把把M M的狀態(tài)集分為兩組：終態(tài)集、非終態(tài)集的狀態(tài)集分為兩組：終態(tài)集、非終態(tài)集 0 0=0,1,2,3,4,5,6=0,1,2,3,4,5,62.12.1考察非終態(tài)

41、集考察非終態(tài)集: : f(0,1,2,a)=1,3, f(0,1,2,a)=1,3,不屬于不屬于0 0的任何一個(gè)子集的任何一個(gè)子集, ,所以所以0,1,20,1,2要分開(kāi)要分開(kāi). .得到：得到： 1 1=1=1，0,2,3,4,5,60,2,3,4,5,6再看再看:f(0,2,a)=1 :f(0,2,a)=1 屬于屬于1 1的子集的子集f(0,2,b)=2,5f(0,2,b)=2,5不屬于不屬于1 1的任何子集的任何子集, ,所以所以0,20,2要分開(kāi)要分開(kāi). .得到得到: : 1 1”=1,0,2,3,4,5,6”=1,0,2,3,4,5,6第三章第三章 詞法分析程序（詞法分析程序（4444

42、）解解: : ( (續(xù)續(xù)) )2.22.2考察終態(tài)集考察終態(tài)集: :f(3,4,5,6,a)=3,6f(3,4,5,6,a)=3,6包含于包含于1 1”的子集的子集3,4,5,63,4,5,6f(3,4,5,6,b)=4,5f(3,4,5,6,b)=4,5包含于包含于1 1”的子集的子集3,4,5,63,4,5,6所以所以3,4,5,63,4,5,6不可再劃分不可再劃分. .3.3.整個(gè)劃分為整個(gè)劃分為4 4個(gè)組個(gè)組: : 2 2=1,0,2,3,4,5,6=1,0,2,3,4,5,64.4.令狀態(tài)令狀態(tài)3 3代表代表3,4,5,6,3,4,5,6,把原來(lái)到達(dá)狀態(tài)把原來(lái)到達(dá)狀態(tài)4,5,64,5

43、,6的弧都導(dǎo)入的弧都導(dǎo)入3,3,并刪除并刪除4,5,64,5,6。得。得: :第三章第三章 詞法分析程序（詞法分析程序（4545）123bbaaba0ab即為化簡(jiǎn)了的即為化簡(jiǎn)了的DFADFA第三章第三章 詞法分析程序（詞法分析程序（4646）第一節(jié)第一節(jié) 正規(guī)文法與有限自動(dòng)機(jī)正規(guī)文法與有限自動(dòng)機(jī)三、正規(guī)式與有限自動(dòng)機(jī)之間的關(guān)系三、正規(guī)式與有限自動(dòng)機(jī)之間的關(guān)系1.1.關(guān)系定理關(guān)系定理: :定理定理:上的上的NFA MNFA M所能識(shí)別語(yǔ)言所能識(shí)別語(yǔ)言L(M)L(M)可以用可以用上的正規(guī)式來(lái)上的正規(guī)式來(lái)表示表示. .即即: :對(duì)對(duì)上的上的NFA M,NFA M,可構(gòu)造一個(gè)正規(guī)式可構(gòu)造一個(gè)正規(guī)式a,

44、a, 使得使得L(a)= L(M)L(a)= L(M)定理定理:上任何正規(guī)式上任何正規(guī)式a,a,存在存在NFA M,NFA M,使得使得L(M) = L(a) L(M) = L(a) 即即: :由正規(guī)式由正規(guī)式a a可以構(gòu)造一個(gè)可以構(gòu)造一個(gè)NFA M,NFA M,使得使得L(M) = L(a) L(M) = L(a) 第三章第三章 詞法分析程序（詞法分析程序（4747）2.2.有限自動(dòng)機(jī)有限自動(dòng)機(jī)M M向正規(guī)式向正規(guī)式a a的轉(zhuǎn)換的轉(zhuǎn)換. .1)1)把狀態(tài)轉(zhuǎn)換圖的概念拓廣把狀態(tài)轉(zhuǎn)換圖的概念拓廣, ,令每條弧上都可以用一個(gè)正規(guī)式令每條弧上都可以用一個(gè)正規(guī)式作標(biāo)記作標(biāo)記, ,2) M2) M轉(zhuǎn)換圖

45、上加兩個(gè)結(jié)點(diǎn)轉(zhuǎn)換圖上加兩個(gè)結(jié)點(diǎn):x,y,:x,y,從從x x用用e e弧連接到弧連接到M M的所有初態(tài)結(jié)的所有初態(tài)結(jié)點(diǎn)點(diǎn); ;從從M M的終態(tài)結(jié)點(diǎn)用的終態(tài)結(jié)點(diǎn)用e e弧連接到弧連接到y(tǒng),y,這個(gè)新的這個(gè)新的NFANFA為為M,M,且且L(M) L(M) = L(M) = L(M) 3)3)通過(guò)引入的通過(guò)引入的3 3條有限自動(dòng)機(jī)替換規(guī)則逐步消去條有限自動(dòng)機(jī)替換規(guī)則逐步消去MM中的所有結(jié)中的所有結(jié)點(diǎn)點(diǎn), ,直到只剩下直到只剩下x x和和y y為止為止, ,這樣這樣, ,在在x x至至y y的弧線上的標(biāo)記就是的弧線上的標(biāo)記就是上的正規(guī)式上的正規(guī)式, ,也就是也就是M M接受的正規(guī)式接受的正規(guī)式. .

46、注注: :在消除結(jié)點(diǎn)的過(guò)程中在消除結(jié)點(diǎn)的過(guò)程中, ,逐步用正規(guī)式來(lái)標(biāo)記弧逐步用正規(guī)式來(lái)標(biāo)記弧. .第一節(jié)第一節(jié) 正規(guī)文法與有限自動(dòng)機(jī)正規(guī)文法與有限自動(dòng)機(jī)三、正規(guī)式與有限自動(dòng)機(jī)之間的關(guān)系三、正規(guī)式與有限自動(dòng)機(jī)之間的關(guān)系第三章第三章 詞法分析程序（詞法分析程序（4848）有限自動(dòng)機(jī)替換規(guī)則有限自動(dòng)機(jī)替換規(guī)則1131211312222ababbaaba|bab*第三章第三章 詞法分析程序（詞法分析程序（4949）例例: :將下面的將下面的DFA MDFA M所接受的語(yǔ)言表示為正規(guī)式所接受的語(yǔ)言表示為正規(guī)式. .302111110000ye ee ex第三章第三章 詞法分析程序（詞法分析程序（5050

47、）y03x10|0101|1000|1100|11e ee e0y(10|01)(00|11)*(01|10)xe ee e00|11x(10|01)(00|11)*(01|10)| (00|11)*y第三章第三章 詞法分析程序（詞法分析程序（5151）3.3.正規(guī)式正規(guī)式a a向確定有限自動(dòng)機(jī)向確定有限自動(dòng)機(jī)M M的轉(zhuǎn)換的轉(zhuǎn)換1)1)由正規(guī)式構(gòu)造一個(gè)如下僅有兩個(gè)結(jié)點(diǎn)由正規(guī)式構(gòu)造一個(gè)如下僅有兩個(gè)結(jié)點(diǎn)x,yx,y的狀態(tài)圖的狀態(tài)圖第一節(jié)第一節(jié) 正規(guī)文法與有限自動(dòng)機(jī)正規(guī)文法與有限自動(dòng)機(jī)三、正規(guī)式與有限自動(dòng)機(jī)之間的關(guān)系三、正規(guī)式與有限自動(dòng)機(jī)之間的關(guān)系yxa2)2)按所引入的按所引入的3 3條正規(guī)式分裂

48、規(guī)則分裂條正規(guī)式分裂規(guī)則分裂a(bǔ) a3)3)重復(fù)步驟重復(fù)步驟2 2直到每個(gè)弧上的標(biāo)記是直到每個(gè)弧上的標(biāo)記是上的一個(gè)字符上的一個(gè)字符或或e e為止為止4)4)將所得的將所得的NFA M(NFA M(因?yàn)榘驗(yàn)榘琫 e弧弧) )進(jìn)行確定化就得進(jìn)行確定化就得DFADFA正規(guī)式分裂規(guī)則正規(guī)式分裂規(guī)則. .第三章第三章 詞法分析程序（詞法分析程序（5252）112122aba|bb*1131122abbaeb1e正規(guī)式分裂規(guī)則正規(guī)式分裂規(guī)則第三章第三章 詞法分析程序（詞法分析程序（5353）第一節(jié)第一節(jié) 正規(guī)文法與有限自動(dòng)機(jī)正規(guī)文法與有限自動(dòng)機(jī)三、正規(guī)式與有限自動(dòng)機(jī)之間的關(guān)系三、正規(guī)式與有限自動(dòng)機(jī)之間

49、的關(guān)系3.3.正規(guī)式正規(guī)式a a向確定有限自動(dòng)機(jī)向確定有限自動(dòng)機(jī)M M的轉(zhuǎn)換的轉(zhuǎn)換注注: :這里將這里將NFA MNFA M進(jìn)行確定化與前面所講的子集法確進(jìn)行確定化與前面所講的子集法確定化是一回事定化是一回事, ,不過(guò)不過(guò), ,這里的這里的NFA MNFA M中含有中含有e e弧弧, ,所以所以在求覆蓋片時(shí)應(yīng)考慮在求覆蓋片時(shí)應(yīng)考慮e e弧弧, ,方法是求方法是求e e閉包閉包( (e eclosure),closure),將此閉包將此閉包( (狀態(tài)子集狀態(tài)子集) )作為作為DFADFA的一個(gè)狀的一個(gè)狀態(tài)使用態(tài)使用, ,而將而將NFANFA上的狀態(tài)間轉(zhuǎn)換變?yōu)殚]包間的轉(zhuǎn)上的狀態(tài)間轉(zhuǎn)換變?yōu)殚]包間的轉(zhuǎn)

50、換換, ,使得不確定的自動(dòng)機(jī)確定化使得不確定的自動(dòng)機(jī)確定化第三章第三章 詞法分析程序（詞法分析程序（5454）例例: :根據(jù)正規(guī)式根據(jù)正規(guī)式(a|b)(a|b)* *(aa|bb) (a|b)(aa|bb) (a|b)* *構(gòu)造構(gòu)造DFA M DFA M 使得它們等價(jià)使得它們等價(jià)yx(a|b)*(aa|bb) (a|b)*yx(a|b)*(aa|bb)(a|b)*xee2eeya|ba|baabb51621xee2eeyaa51634bbaabb第三章第三章 詞法分析程序（詞法分析程序（5555）第一節(jié)第一節(jié) 正規(guī)文法與有限自動(dòng)機(jī)正規(guī)文法與有限自動(dòng)機(jī)三、正規(guī)式與有限自動(dòng)機(jī)之間的關(guān)系三、正規(guī)式與

51、有限自動(dòng)機(jī)之間的關(guān)系4.4.對(duì)含有對(duì)含有e e弧的弧的NFANFA進(jìn)行確定化進(jìn)行確定化(1) (1) e e閉包閉包: :是可以從某狀態(tài)或某些狀態(tài)通過(guò)是可以從某狀態(tài)或某些狀態(tài)通過(guò)e e弧所能弧所能到達(dá)的所有狀態(tài)的集合到達(dá)的所有狀態(tài)的集合, ,狀態(tài)集合狀態(tài)集合I I的的e e閉包閉包( (e eclosure(I)closure(I)形式定義如下形式定義如下: :(a)(a)若若sI,sI,則則sse eclosure(I)closure(I)(b)(b)若若sI,sI,那么從那么從s s出發(fā)經(jīng)過(guò)任意段的出發(fā)經(jīng)過(guò)任意段的e e弧所能達(dá)到弧所能達(dá)到的任意狀態(tài)的任意狀態(tài)ss都屬于都屬于e eclos

52、ure(I)closure(I)第三章第三章 詞法分析程序（詞法分析程序（5656）第一節(jié)第一節(jié) 正規(guī)文法與有限自動(dòng)機(jī)正規(guī)文法與有限自動(dòng)機(jī)三、正規(guī)式與有限自動(dòng)機(jī)之間的關(guān)系三、正規(guī)式與有限自動(dòng)機(jī)之間的關(guān)系4.4.對(duì)含有對(duì)含有e e弧的弧的NFANFA進(jìn)行確定化進(jìn)行確定化(2)(2)閉包間轉(zhuǎn)換閉包間轉(zhuǎn)換. .設(shè)設(shè)e eclosure(I)=qclosure(I)=q0 0,q,q1 1,q,qn n,當(dāng)讀入字母表中字當(dāng)讀入字母表中字母母a a時(shí)，它轉(zhuǎn)換到另一閉包時(shí)，它轉(zhuǎn)換到另一閉包e eclosure(I)closure(I)e eclosure(J)closure(J)的組成的組成 J=f(qJ

53、=f(q0 0,a) f(q,a) f(q1 1,a) .f(q,a) .f(qn n,a),a) 對(duì)得到的對(duì)得到的J J按按e e閉包的定義求閉包的定義求e eclosure(J)closure(J)第三章第三章 詞法分析程序（詞法分析程序（5757）第一節(jié)第一節(jié) 正規(guī)文法與有限自動(dòng)機(jī)正規(guī)文法與有限自動(dòng)機(jī)三、正規(guī)式與有限自動(dòng)機(jī)之間的關(guān)系三、正規(guī)式與有限自動(dòng)機(jī)之間的關(guān)系4.4.對(duì)含有對(duì)含有e e弧的弧的NFANFA進(jìn)行確定化進(jìn)行確定化（3 3）對(duì)含有）對(duì)含有e e弧的弧的NFANFA進(jìn)行確定化方法進(jìn)行確定化方法設(shè)由設(shè)由NFA M=NFA M=（S,f,SS,f,S0 0,Z),Z)構(gòu)造一個(gè)等價(jià)

54、的構(gòu)造一個(gè)等價(jià)的DFADFA M= M=（Q,d,IQ,d,I0 0,F),F)(a)I(a)I0 0= = e eclosure(Sclosure(S0 0),I),I0 0QQ(b)(b)若狀態(tài)集若狀態(tài)集Q Q中有狀態(tài)中有狀態(tài)I Ii i=s=s0 0,s,s1 1,s,sj j,s,sk kS,0kj; S,0kj; 且有且有I It t= = e eclosure(f(Iclosure(f(Ii i,a),a),若若I It t不在不在Q Q中，則將中，則將I It t加入加入Q Q（c)c)重復(fù)步驟重復(fù)步驟2 2，直到，直到Q Q中無(wú)新?tīng)顟B(tài)加入中無(wú)新?tīng)顟B(tài)加入（d)d)取終態(tài)取終態(tài)F=

55、I|IQF=I|IQ，且，且IZFIZF第三章第三章 詞法分析程序（詞法分析程序（5858）xee2eeya51634bbaabb例例IabI0=x,5,1I1=5,3,1I2=5,4,1I1=5,3,1I3=5,3,2,1,6,yI2=5,4,1I2=5,4,1I1=5,3,1I4=5,4,1,2,6,yI3=5,3,2,1,6,yI3=5,3,2,1,6,yI5=5,1,4,6, yI4=5,4,1,2,6,yI6=5,3,1,6,yI4=5,4,1,2,6,yI5=5,1,4,6, yI6=5,3,1,6,yI4=5,4,1,2,6,yI6=5,3,1,6,yI3=5,3,2,1,6,y

56、I5=5,1,4,6, ya第三章第三章 詞法分析程序（詞法分析程序（5959）IabI0I1I2I1I3I2I2I1I4I3I3I5I4I6I4I5I6I4I6I3I5I1I2I4I3I5I6babbaabaababI0baDFA為:第三章第三章 詞法分析程序（詞法分析程序（6060）四、正規(guī)文法和有限自動(dòng)機(jī)四、正規(guī)文法和有限自動(dòng)機(jī)1 1、關(guān)系定理、關(guān)系定理 設(shè)設(shè)G=G=（V VN N,V,VT T,P,S),P,S)是正規(guī)文法，則存在一個(gè)有限自是正規(guī)文法，則存在一個(gè)有限自動(dòng)機(jī)動(dòng)機(jī)M=M=（Q,f,qQ,f,q0 0,Z),Z)使得使得 L(G)=L(M). L(G)=L(M). 注：注：1

57、 1）正規(guī)文法分為右線性文法和左線性文法。）正規(guī)文法分為右線性文法和左線性文法。但對(duì)一個(gè)正規(guī)文法，不能既是左線性，又是右線但對(duì)一個(gè)正規(guī)文法，不能既是左線性，又是右線性。性。2 2）對(duì)每個(gè)有限自動(dòng)機(jī)）對(duì)每個(gè)有限自動(dòng)機(jī)M,M,都存在一個(gè)右線性正規(guī)文法都存在一個(gè)右線性正規(guī)文法G GR R和左線性正規(guī)文法和左線性正規(guī)文法G GL L， 使得使得 L(M)=L(GL(M)=L(GR R)= L(G)= L(GL L).).第三章第三章 詞法分析程序（詞法分析程序（6161）四、正規(guī)文法和有限自動(dòng)機(jī)四、正規(guī)文法和有限自動(dòng)機(jī)2 2、右線性文法轉(zhuǎn)換為等價(jià)自動(dòng)機(jī)、右線性文法轉(zhuǎn)換為等價(jià)自動(dòng)機(jī)設(shè)有右線性文法：設(shè)有右

58、線性文法： G=G=（V VN N,V,VT T,P,S),P,S)，將其轉(zhuǎn)換為，將其轉(zhuǎn)換為自動(dòng)機(jī)自動(dòng)機(jī)M=M=（Q,f,qQ,f,q0 0,Z),Z)。轉(zhuǎn)換步驟如下：轉(zhuǎn)換步驟如下：1 1）將）將V VN N中的每個(gè)非終結(jié)符視為狀態(tài)符號(hào)，并增加中的每個(gè)非終結(jié)符視為狀態(tài)符號(hào)，并增加一個(gè)新的終結(jié)狀態(tài)符號(hào)一個(gè)新的終結(jié)狀態(tài)符號(hào)T T，即令，即令Q=VQ=VN NT; T; 同時(shí)，同時(shí)，令令=V=VT T,q,q0 0=S;=S;若若P P中含有中含有S S e e , ,則令則令Z=S,T,Z=S,T,否則令否則令Z=TZ=T；第三章第三章 詞法分析程序（詞法分析程序（6262）四、正規(guī)文法和有限自動(dòng)

59、機(jī)四、正規(guī)文法和有限自動(dòng)機(jī)2 2、右線性文法轉(zhuǎn)換為等價(jià)自動(dòng)機(jī)、右線性文法轉(zhuǎn)換為等價(jià)自動(dòng)機(jī)2 2）P P中的產(chǎn)生式用如下映射中的產(chǎn)生式用如下映射f f來(lái)代替來(lái)代替 a) a)對(duì)于對(duì)于P P中每一條形如中每一條形如A A1 1 aA aA2 2的產(chǎn)生式，的產(chǎn)生式，M M中中設(shè)為設(shè)為f(Af(A1 1,a)=A,a)=A2 2. . b) b)對(duì)于對(duì)于P P中每一條形如中每一條形如A A1 1 a a的產(chǎn)生式，的產(chǎn)生式，M M中設(shè)中設(shè)為為f(Af(A1 1,a)=T.,a)=T. c) c)對(duì)對(duì)上的所有上的所有a a，取，取f(T,a)= f(T,a)= , ,即在終態(tài)下有即在終態(tài)下有限自動(dòng)機(jī)無(wú)動(dòng)作

60、限自動(dòng)機(jī)無(wú)動(dòng)作第三章第三章 詞法分析程序（詞法分析程序（6363）例：有文法例：有文法G=(S,A,B,a,b,c,P,S G=(S,A,B,a,b,c,P,S 其中產(chǎn)其中產(chǎn)生式生式P:P: -S aS|aB -S aS|aB -B bB|bA -B bB|bA -A cA|c -A cA|c構(gòu)造與之等價(jià)的構(gòu)造與之等價(jià)的FAFA解：構(gòu)造自動(dòng)機(jī)解：構(gòu)造自動(dòng)機(jī)M=M=（Q,f,qQ,f,q0 0,Z),Z)1 1）增加一個(gè)新的終結(jié)狀態(tài)符號(hào)）增加一個(gè)新的終結(jié)狀態(tài)符號(hào)T T，Q=S,B,A,TQ=S,B,A,T=a,b,c,q=a,b,c,q0 0=S,Z=T=S,Z=T第三章第三章 詞法分析程序（詞