第03章_詞法分析

1、12S.PO.P語(yǔ)義分析及生成中間代碼程序語(yǔ)義分析及生成中間代碼程序代碼生成程序代碼生成程序代碼優(yōu)化程序代碼優(yōu)化程序語(yǔ)法分析程序語(yǔ)法分析程序詞法分析程序詞法分析程序錯(cuò)錯(cuò)誤誤處處理理符符號(hào)號(hào)表表管管理理3教學(xué)目標(biāo)教學(xué)目標(biāo)1.1. 本章介紹編譯第一個(gè)階段詞法分析的本章介紹編譯第一個(gè)階段詞法分析的設(shè)計(jì)原理和設(shè)計(jì)原理和設(shè)計(jì)方法設(shè)計(jì)方法，要求明確此階段的，要求明確此階段的任務(wù)任務(wù)。2.2. 理解通常的單詞理解通常的單詞分類和構(gòu)詞規(guī)則分類和構(gòu)詞規(guī)則。3.3. 會(huì)使用單詞的會(huì)使用單詞的描述和識(shí)別描述和識(shí)別機(jī)制。機(jī)制。4.4. 要求掌握要求掌握正規(guī)文法、狀態(tài)圖、正規(guī)文法、狀態(tài)圖、DFADFA、NFANFA、正

2、規(guī)式、正規(guī)式和正規(guī)集和正規(guī)集的基本概念和它們之間的關(guān)系。的基本概念和它們之間的關(guān)系。5.5. 掌握詞法分析程序的掌握詞法分析程序的手工手工實(shí)現(xiàn)方法。實(shí)現(xiàn)方法。6.6. 掌握詞法分析程序的掌握詞法分析程序的自動(dòng)自動(dòng)構(gòu)造原理。構(gòu)造原理。43.1 3.1 詞法分析的功能詞法分析的功能3.2 3.2 程序語(yǔ)言的單詞符號(hào)種類及詞法分析程序語(yǔ)言的單詞符號(hào)種類及詞法分析輸出輸出3.3 3.3 正則文法及狀態(tài)圖正則文法及狀態(tài)圖3.4 3.4 詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)3.5 3.5 正則表達(dá)式正則表達(dá)式3.6 3.6 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)3.7 3.7 詞法分析程序的自動(dòng)生成器詞法分析程

3、序的自動(dòng)生成器LEXLEX教學(xué)內(nèi)容教學(xué)內(nèi)容5（1 1）分析和識(shí)別單詞及屬性，）分析和識(shí)別單詞及屬性， 包括識(shí)別語(yǔ)言的包括識(shí)別語(yǔ)言的關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符等；等；（2 2）跳過(guò)各種分隔符，如）跳過(guò)各種分隔符，如空格，回車，制表符空格，回車，制表符等；等；（3 3）刪除注釋；）刪除注釋；（4 4）進(jìn)行詞法檢查，報(bào)告所發(fā)現(xiàn)的錯(cuò)誤；）進(jìn)行詞法檢查，報(bào)告所發(fā)現(xiàn)的錯(cuò)誤；（5 5）建立符號(hào)表。）建立符號(hào)表。6main( )/*ADD*/ int x=10,y=20,sum; sum=x+y;main、(、)、int、x、=、10、,、y、=、20、,、sum、;、sum、=

4、、x、+、y、;、詞法分析詞法分析 71、詞法分析作為獨(dú)立的一遍、詞法分析作為獨(dú)立的一遍詞法分析的輸出存入一個(gè)中間文件供語(yǔ)法分析使用詞法分析的輸出存入一個(gè)中間文件供語(yǔ)法分析使用S.P.(字符串)詞法分析詞法分析S.P.(符號(hào)串)語(yǔ)法分析語(yǔ)法分析第一遍第一遍第二遍第二遍單詞串單詞串實(shí)現(xiàn)方案一實(shí)現(xiàn)方案一8實(shí)現(xiàn)方案二實(shí)現(xiàn)方案二2、詞法分析程序作為單獨(dú)的子程序、詞法分析程序作為單獨(dú)的子程序S.P.(字符串)詞法分詞法分析程序析程序語(yǔ)法分語(yǔ)法分析程序析程序取單詞取單詞單詞單詞詞法分析作為語(yǔ)法分析程序的一個(gè)子程序。詞法分析作為語(yǔ)法分析程序的一個(gè)子程序。每當(dāng)語(yǔ)法分析需要一個(gè)新的符號(hào)時(shí)，就調(diào)用詞法分析每當(dāng)語(yǔ)法

5、分析需要一個(gè)新的符號(hào)時(shí)，就調(diào)用詞法分析子程序，詞法分析子程序從字符串源程序中識(shí)別出一子程序，詞法分析子程序從字符串源程序中識(shí)別出一個(gè)具有獨(dú)立意義的單詞，將其符號(hào)返給語(yǔ)法分析。個(gè)具有獨(dú)立意義的單詞，將其符號(hào)返給語(yǔ)法分析。9單詞的種類單詞的種類 （1 1）保留）保留字：字：if、for、while等等 （2 2）標(biāo)識(shí)符：標(biāo)識(shí)符：用戶定義，如變量名、函數(shù)名等用戶定義，如變量名、函數(shù)名等 （3 3）無(wú)符號(hào)數(shù)：無(wú)符號(hào)數(shù)：如如127、0.12等等 （4 4）單分界符：?jiǎn)畏纸绶喝缛?、*、；、（等、；、（等 （5 5）雙分界符：）雙分界符：如如=、=、=、,!,= /=*結(jié)束組合標(biāo)識(shí)符查保留字 保留字 輸

6、出保留字 輸出標(biāo)識(shí)符組合整數(shù) 組合整數(shù) 輸出單分符 讀字符 讀字符讀字符輸出雙分符 讀字符輸出單分符/ 注釋處理 輸出單分符 錯(cuò)誤處理 YYYYYYYYYYNNNNNNNNNN31323334假設(shè)輸入文件假設(shè)輸入文件AAA.T中程序如下，運(yùn)行詞法分析程序，給中程序如下，運(yùn)行詞法分析程序，給出輸出結(jié)果。出輸出結(jié)果。 int a;a=10;解：將解：將AAA.T文件與詞法分析程序最好在同一目錄下，這文件與詞法分析程序最好在同一目錄下，這樣運(yùn)行詞法分析程序時(shí)可以省略路徑。運(yùn)行詞法分析程序：樣運(yùn)行詞法分析程序時(shí)可以省略路徑。運(yùn)行詞法分析程序：屏幕提示輸入文件名：（輸入屏幕提示輸入文件名：（輸入AAA.

7、T）和輸出文件名：）和輸出文件名：（輸入（輸入BBB.T），運(yùn)行結(jié)束后，屏幕提示詞法分析成功。），運(yùn)行結(jié)束后，屏幕提示詞法分析成功。打開打開BBB.T文件，看到上面示例小程序的詞法分析結(jié)果如文件，看到上面示例小程序的詞法分析結(jié)果如下：下：其中第一列是單詞記號(hào)，第二列是單詞值。其中第一列是單詞記號(hào)，第二列是單詞值。 intintIDa;IDa=NUM10;3536正規(guī)式中的運(yùn)算符：正規(guī)式中的運(yùn)算符：|或（選擇）：或（選擇）：R1|R2= x|xL1或 xL2 連接：連接： R1 R2=xy|xL1，yL2* 或或 重復(fù)重復(fù) R1=x|x L1*， L1*=L10L11L12（）（）括號(hào)括號(hào)運(yùn)算符

8、的優(yōu)先級(jí)：運(yùn)算符的優(yōu)先級(jí)： 先先*, 后后 , 最后最后 | 在正規(guī)式中可以省略在正規(guī)式中可以省略.正規(guī)式相等正規(guī)式相等 這兩個(gè)正規(guī)式表示的語(yǔ)言相等這兩個(gè)正規(guī)式表示的語(yǔ)言相等37正則表達(dá)式的形式定義正則表達(dá)式的形式定義38正規(guī)式正規(guī)式正規(guī)集正規(guī)集ba*所有以所有以b為首后跟任意多個(gè)為首后跟任意多個(gè)a的符號(hào)串的符號(hào)串a(chǎn)(a|b)*所有以所有以a為首的符號(hào)串為首的符號(hào)串(a|b)*abb所有以所有以abb為尾的為尾的a，b符號(hào)串符號(hào)串(a|b)*(aa|bb) (a|b)*所有含有兩個(gè)相繼的所有含有兩個(gè)相繼的a或相繼的或相繼的b的符的符號(hào)串號(hào)串(aa|ab|ba|bb) *空串和任何長(zhǎng)度為偶數(shù)的符

9、號(hào)串空串和任何長(zhǎng)度為偶數(shù)的符號(hào)串(a|b)(a|b)(a|b) *任何長(zhǎng)度大于等于任何長(zhǎng)度大于等于2的符號(hào)串的符號(hào)串39例例3.53.5，設(shè)字母表，設(shè)字母表=a,b=a,b，則，則a,b, a,b, 和和都是都是上上的正則表達(dá)式，所描述的語(yǔ)言為的正則表達(dá)式，所描述的語(yǔ)言為aa、bb、，求表達(dá)式求表達(dá)式abab、a|ba|b和和aa|ab|ba|bbaa|ab|ba|bb定義的語(yǔ)言。定義的語(yǔ)言。40例例3.63.6，設(shè)字母表，設(shè)字母表=0=0，求表達(dá)式，求表達(dá)式0000與與000|0000|0定定義的語(yǔ)言。義的語(yǔ)言。正則表達(dá)式的部分操作符滿足正則表達(dá)式的部分操作符滿足結(jié)合律結(jié)合律、交換律交換律和

10、和分配分配律律: :即即 (ab)c=a(bc) (a|b)|c=a(b|c) (ab)c=a(bc) (a|b)|c=a(b|c) a|b=b|a a(b|c)=ab|ac a|b=b|a a(b|c)=ab|ac注意：連接不滿足交換律，即注意：連接不滿足交換律，即abba abba 41設(shè)設(shè)r，s，t均是正規(guī)式，則有以下性質(zhì)：均是正規(guī)式，則有以下性質(zhì)：（1）交換律：）交換律： r|s= s|r（2）結(jié)合律：）結(jié)合律： r|(s|t)=(r|s)|t (rs)t=r(st) （3）分配律：）分配律： (r|s)t=rt|st（4）同一律：）同一律： r= r= r42步驟步驟1 將每條產(chǎn)生式

11、改寫為正規(guī)式；將每條產(chǎn)生式改寫為正規(guī)式；步驟步驟2 用代入法解正規(guī)式方程組，最后只剩下一用代入法解正規(guī)式方程組，最后只剩下一個(gè)開始符號(hào)定義的正規(guī)式，其中不含非終結(jié)符。個(gè)開始符號(hào)定義的正規(guī)式，其中不含非終結(jié)符。規(guī)則規(guī)則1 1規(guī)則規(guī)則2 2規(guī)則規(guī)則3 3文法產(chǎn)生式文法產(chǎn)生式正規(guī)式正規(guī)式AxB,ByAxB,ByAxA|yAxA|yAx,AyAx,Ay A=xy A=xyA=xA=x* *y y A=x|y A=x|y43GS:SaA|a AdA|d規(guī)則規(guī)則1 1規(guī)則規(guī)則2 2規(guī)則規(guī)則3 3文法產(chǎn)生式文法產(chǎn)生式正規(guī)式正規(guī)式AxB,ByAxB,ByAxA|yAxA|yAx,AyAx,AyA=xyA=xy

12、A=xA=x* *y yA=x|yA=x|yS=aA|aA= d*d代入代入:S=ad*d|a =ad*44先用元符號(hào)先用元符號(hào)“”和和“”將文法改將文法改寫成如下：寫成如下：S=aaBB =bCC = aa然后按解方程組的方法可得：然后按解方程組的方法可得：C=aaB= baaS=aabaa最終轉(zhuǎn)成正則表達(dá)式最終轉(zhuǎn)成正則表達(dá)式S=aabaa可以驗(yàn)證，它表示的語(yǔ)言與原來(lái)可以驗(yàn)證，它表示的語(yǔ)言與原來(lái)的正則文法描述的語(yǔ)言相同。的正則文法描述的語(yǔ)言相同。45正規(guī)式正規(guī)式正規(guī)文法正規(guī)文法步驟步驟1 構(gòu)造構(gòu)造 Sr步驟步驟2 不斷利用表不斷利用表3.4的規(guī)則做變換的規(guī)則做變換,直到每個(gè)產(chǎn)生直到每個(gè)產(chǎn)生式

13、最多含有一個(gè)終結(jié)符為止式最多含有一個(gè)終結(jié)符為止 規(guī)則規(guī)則1 1規(guī)則規(guī)則2 2規(guī)則規(guī)則3 3文法產(chǎn)生式文法產(chǎn)生式正規(guī)式正規(guī)式AxB,ByAxB,ByAxA|yAxA|yAx,AyAx,AyA=xyA=xyA=xA=x* *y y A=x|y A=x|y46例：求正規(guī)式例：求正規(guī)式(a|b)(a|b|0|1)*對(duì)應(yīng)的正規(guī)文法對(duì)應(yīng)的正規(guī)文法S(a|b)(a|b|0|1)*S(a|b)AaA|bA|0A|1A|GS：SaA|bAAaA|bA|0A|1A|A(a|b|0|1)*規(guī)則規(guī)則1 1規(guī)則規(guī)則2 2規(guī)則規(guī)則3 3文法產(chǎn)生式文法產(chǎn)生式正規(guī)式正規(guī)式AxB,ByAxB,ByAxA|yAxA|yAx,Ay

14、Ax,AyA=xyA=xyA=xA=x* *y y A=x|y A=x|y47 有窮自動(dòng)機(jī)是一種有窮自動(dòng)機(jī)是一種數(shù)學(xué)模型數(shù)學(xué)模型，具有離散的輸入與輸出，系，具有離散的輸入與輸出，系統(tǒng)可處于有窮狀態(tài)中的任何一個(gè)統(tǒng)可處于有窮狀態(tài)中的任何一個(gè) 它能準(zhǔn)確地它能準(zhǔn)確地識(shí)別正規(guī)集識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所定義的語(yǔ)言和，即識(shí)別正規(guī)文法所定義的語(yǔ)言和正規(guī)式所表示的集合正規(guī)式所表示的集合 引入有窮自動(dòng)機(jī)這個(gè)理論，正是為引入有窮自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)詞法分析程序的自動(dòng)構(gòu)造造尋找特殊的方法和工具尋找特殊的方法和工具有窮自動(dòng)機(jī)分為兩類：有窮自動(dòng)機(jī)分為兩類：確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī)（DFA

15、DFA）(Deterministic Finite Automata)(Deterministic Finite Automata)不確定的有窮自動(dòng)機(jī)不確定的有窮自動(dòng)機(jī)（NFANFA）(Nondeterministic Finite Automata) (Nondeterministic Finite Automata) 48標(biāo)識(shí)符標(biāo)識(shí)符無(wú)符號(hào)整數(shù)無(wú)符號(hào)整數(shù)單界符單界符雙界符雙界符讀字符讀字符查保留字表查保留字表返回返回S狀態(tài)圖的形式化描述狀態(tài)圖的形式化描述S1非字母數(shù)字非字母數(shù)字字母字母字母、數(shù)字字母、數(shù)字2非數(shù)字非數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字3其他字符其他字符+ * ，（ ）出口出口4其他字符其他

16、字符5=非非 =出錯(cuò)出錯(cuò)其他其他491.確定的有窮自動(dòng)機(jī)（確定的有窮自動(dòng)機(jī)（DFA M） M=（ Q， ，q0，F(xiàn)，）Q：有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)：有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)：有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)：有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)q0 ： q0 Q，是唯一的初態(tài)，是唯一的初態(tài) F：F Q，是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀，是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)態(tài)：是狀態(tài)轉(zhuǎn)換函數(shù)，是：是狀態(tài)轉(zhuǎn)換函數(shù)，是QQ上的單值映射：上的單值映射：f（q1，a）=q2 50這是一個(gè)單值函數(shù)，表示在當(dāng)前狀態(tài)為這是一個(gè)單值函數(shù)，表示在當(dāng)前狀態(tài)為q q下，下，輸

17、入符號(hào)為輸入符號(hào)為a a時(shí)，自動(dòng)機(jī)將從狀態(tài)時(shí)，自動(dòng)機(jī)將從狀態(tài)q q轉(zhuǎn)換到下一轉(zhuǎn)換到下一個(gè)狀態(tài)個(gè)狀態(tài)q q，q q稱為稱為q q的后繼狀態(tài)。的后繼狀態(tài)。51例如例如: M: M:（0,1,2,3,a,b,0,1,2,3,a,b,0, , 3 , , ） （0，a）=1 （0，b）=2 （1，a）=3 （1，b）=2 （2，a）=1 （2，b）=3 （3，a）=3 （3，b）=3M=（ Q， ，q0，F(xiàn)，）字母表字母表含有含有n n個(gè)輸入字個(gè)輸入字符，那末任何一個(gè)狀態(tài)符，那末任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有結(jié)點(diǎn)最多有n n條弧射出，條弧射出，而且每條弧以一個(gè)不同而且每條弧以一個(gè)不同的輸入字符標(biāo)記。的輸入字符

18、標(biāo)記。52 輸入輸入 字符字符 狀態(tài)狀態(tài) a b 0 1 2 1 3 2 2 1 3 3 3 3DFADFA的狀態(tài)圖表示：的狀態(tài)圖表示：1032aabba,bba所謂確定的狀態(tài)機(jī)，其確定性表現(xiàn)在所謂確定的狀態(tài)機(jī)，其確定性表現(xiàn)在狀態(tài)轉(zhuǎn)移函數(shù)是單值函數(shù)！狀態(tài)轉(zhuǎn)移函數(shù)是單值函數(shù)！53DFADFA識(shí)別的字：若存在一條初始狀態(tài)到某一終止?fàn)钭R(shí)別的字：若存在一條初始狀態(tài)到某一終止?fàn)顟B(tài)的路徑，且這條路徑上所有弧的標(biāo)記符號(hào)連接成態(tài)的路徑，且這條路徑上所有弧的標(biāo)記符號(hào)連接成符號(hào)串符號(hào)串，則稱，則稱為為DFA MDFA M（接受）識(shí)別。（接受）識(shí)別。DFA MDFA M所接受的語(yǔ)言為：所接受的語(yǔ)言為：DFA MDF

19、A M所能接受的符號(hào)串的全體記為所能接受的符號(hào)串的全體記為L(zhǎng)(M)L(M)若若M M的初態(tài)結(jié)點(diǎn)同時(shí)為終態(tài)，或者存在一條從初態(tài)到的初態(tài)結(jié)點(diǎn)同時(shí)為終態(tài)，或者存在一條從初態(tài)到某個(gè)終態(tài)結(jié)點(diǎn)的某個(gè)終態(tài)結(jié)點(diǎn)的通路，則通路，則為為M M所識(shí)別。所識(shí)別。 54 （0，abaab） =（1，baab） =（2，aab） =（1，ab） =（3，b） =3 (接受接受)DFADFA的狀態(tài)圖表示：的狀態(tài)圖表示：1032aabba,bba （0，abab） =（1，bab） =（2，ab） =（1，b） =2 (拒絕拒絕)對(duì)于符號(hào)串對(duì)于符號(hào)串a(chǎn)baababaab對(duì)于符號(hào)串對(duì)于符號(hào)串a(chǎn)bababab55SABC1101

20、0010下面判別下面判別110101、11101能否被該自能否被該自動(dòng)機(jī)接受：動(dòng)機(jī)接受：(S，110101)=(A，10101) =(S，0101)=(B，101) =(C，01)=(A，1) = S(接受接受)(S，11101)=(A，1101) =(S，101)=(A，01) =(C，1) = B(拒絕拒絕) 56 有窮自動(dòng)機(jī)的不確定性表現(xiàn)在在某個(gè)狀態(tài)下，對(duì)有窮自動(dòng)機(jī)的不確定性表現(xiàn)在在某個(gè)狀態(tài)下，對(duì)于某個(gè)輸入字符存在多個(gè)后繼狀態(tài)，即狀態(tài)的轉(zhuǎn)向于某個(gè)輸入字符存在多個(gè)后繼狀態(tài)，即狀態(tài)的轉(zhuǎn)向是不確定的。是不確定的。 5758例：例： NFA N=(1,2,3,4, a,b,c, 1, 4, )5

21、9u對(duì)于對(duì)于*上的任何符號(hào)串上的任何符號(hào)串 ，若存在一條從某一初，若存在一條從某一初態(tài)到某一終態(tài)的通路，且該通路上所有弧的標(biāo)記字態(tài)到某一終態(tài)的通路，且該通路上所有弧的標(biāo)記字符依次連接成的串等于符依次連接成的串等于 ，則稱，則稱 可以被可以被NFA N所所識(shí)別或接受。識(shí)別或接受。u若若N的初態(tài)結(jié)點(diǎn)同時(shí)為終態(tài)，或者存在一條從初的初態(tài)結(jié)點(diǎn)同時(shí)為終態(tài)，或者存在一條從初態(tài)到某個(gè)終態(tài)結(jié)點(diǎn)的態(tài)到某個(gè)終態(tài)結(jié)點(diǎn)的 通路，則通路，則 為為N所識(shí)別。所識(shí)別。 NFA N所能識(shí)別的符號(hào)串的全體記為所能識(shí)別的符號(hào)串的全體記為L(zhǎng)(N)，稱為，稱為NFA N所識(shí)別的語(yǔ)言所識(shí)別的語(yǔ)言 601234abac ac 符號(hào)符號(hào) 狀

22、態(tài)狀態(tài) a b c 1 4 2，3 2 2 4 3 3，4 4 61能接受能接受0001111010001110000001不能接受不能接受0001100(0|1)(0|1)* *(000|111)(0|1) (000|111)(0|1) * *62畫出能夠識(shí)別畫出能夠識(shí)別C語(yǔ)言注釋語(yǔ)言注釋/* */的的DFA12453othersothers/*/6othersothersall all6312453othersothers/*/狀態(tài)狀態(tài)1：注釋開始狀態(tài)。：注釋開始狀態(tài)。狀態(tài)狀態(tài)2：進(jìn)入注釋體前的中間狀態(tài)。：進(jìn)入注釋體前的中間狀態(tài)。狀態(tài)狀態(tài)3：表明目前正在注釋體中的狀態(tài)。：表明目前正在注釋體

23、中的狀態(tài)。狀態(tài)狀態(tài)4：離開注釋前的中間狀態(tài)。：離開注釋前的中間狀態(tài)。狀態(tài)狀態(tài)5：注釋結(jié)束狀態(tài)，即接受狀態(tài)。：注釋結(jié)束狀態(tài)，即接受狀態(tài)。 64已證明：非確定的有窮自動(dòng)機(jī)與確定的有窮自動(dòng)已證明：非確定的有窮自動(dòng)機(jī)與確定的有窮自動(dòng)機(jī)從功能上來(lái)說(shuō)是等價(jià)的，也就是說(shuō)，我們能夠機(jī)從功能上來(lái)說(shuō)是等價(jià)的，也就是說(shuō)，我們能夠從：從：DFA是是NFA的特例。有一種算法，將的特例。有一種算法，將NFA轉(zhuǎn)換成接轉(zhuǎn)換成接受同樣語(yǔ)言的受同樣語(yǔ)言的DFA。這種算法稱為這種算法稱為子集法子集法。與某一與某一NFA等價(jià)的等價(jià)的DFA不唯一不唯一 NFA NDFA M構(gòu)造成一個(gè)構(gòu)造成一個(gè)使得使得 L(M)=L(N)L(M)=L(

24、N)65正規(guī)文法正規(guī)文法NFA正規(guī)式正規(guī)式654312DFA最小化最小化8766 輸入輸入 字符字符 狀態(tài)狀態(tài) a b 0 1 2 1 3 2 2 1 3 3 3 3DFA 符號(hào)符號(hào) 狀態(tài)狀態(tài) a b c 1 4 2，3 2 2 4 3 3，4 4 NFA從從NFANFA的矩陣表示中可以看出，表項(xiàng)通常是一狀態(tài)的的矩陣表示中可以看出，表項(xiàng)通常是一狀態(tài)的集合，而在集合，而在DFADFA的矩陣表示中，表項(xiàng)是一個(gè)狀態(tài)。的矩陣表示中，表項(xiàng)是一個(gè)狀態(tài)。NFANFA到相應(yīng)的到相應(yīng)的DFADFA的構(gòu)造的基本思路是：的構(gòu)造的基本思路是： DFADFA的每一個(gè)的每一個(gè)狀態(tài)對(duì)應(yīng)狀態(tài)對(duì)應(yīng)NFANFA的一組狀態(tài)的一組狀

25、態(tài). .67 (1) 合并如果有 ，則把S2合并到S1S S1 1S S2 2轉(zhuǎn)換需解決的問題：轉(zhuǎn)換需解決的問題：ijkmaban（a）i,jmkaabn（b）68(2)狀態(tài)合并0123aabc（a）01,23abc（b）69定義定義1 狀態(tài)集合狀態(tài)集合I I的的 - -閉包，表示為閉包，表示為 -closure(I) -closure(I) 若若qIqI，則，則qq -closure(I)-closure(I)； 若若qIqI，則從，則從q q出發(fā)經(jīng)過(guò)任意條出發(fā)經(jīng)過(guò)任意條 弧而能到達(dá)弧而能到達(dá)的任何狀態(tài)的任何狀態(tài)qq都屬于都屬于 -closure(I)-closure(I)。 為了使得為了使

26、得NFANFA確定化，我們首先給出兩個(gè)定義確定化，我們首先給出兩個(gè)定義：_ closure(I)IIS2S2S1S1S3S370例：例：如圖所示的狀態(tài)圖：如圖所示的狀態(tài)圖：令令I(lǐng)=1，求求-closure（I）=？156432aaa根據(jù)定義：根據(jù)定義：-closure（I）=1，3課堂練習(xí)：課堂練習(xí)：令令I(lǐng)=1,2，求求-closure（I）=？71定義定義2 2 狀態(tài)集狀態(tài)集P P的的a a弧轉(zhuǎn)換集弧轉(zhuǎn)換集I I是狀態(tài)集，由是狀態(tài)集，由I I中的狀態(tài)出發(fā)，經(jīng)過(guò)一條中的狀態(tài)出發(fā)，經(jīng)過(guò)一條a a弧弧可能到達(dá)的狀態(tài)的集合稱為可能到達(dá)的狀態(tài)的集合稱為movemove（I I，a a），），則則: :

27、I Ia a= _closure ( move( I , a ) )= _closure ( move( I , a ) )72例：令例：令 I=1I=1 I Ia a=-closure(move=-closure(move（I I，a a）) ) =-closure( =-closure(（1 1，a a） =-closure(2=-closure(2，44）=2=2，4 4，66根據(jù)定義根據(jù)定義1 1，2 2，可以將上述的，可以將上述的MM確定化（即確定化（即可構(gòu)造出狀態(tài)轉(zhuǎn)換矩陣）可構(gòu)造出狀態(tài)轉(zhuǎn)換矩陣）156432aaa課堂練習(xí)：課堂練習(xí)：令令I(lǐng)=1,2,3求求I Ia a =？73課堂練

28、習(xí)：課堂練習(xí)：令令I(lǐng)=1I=1，設(shè)，設(shè)SS= -closure= -closure（I I），求），求SS？SSa a = =？將從狀態(tài)將從狀態(tài)S S出發(fā)經(jīng)過(guò)任意條出發(fā)經(jīng)過(guò)任意條 弧所能到達(dá)的狀態(tài)作為弧所能到達(dá)的狀態(tài)作為DFADFA的初態(tài)的初態(tài)S S 從從S S 出發(fā)，把遇到輸入符號(hào)出發(fā)，把遇到輸入符號(hào)a a所轉(zhuǎn)移到的后繼狀態(tài)集作所轉(zhuǎn)移到的后繼狀態(tài)集作為為DFADFA的新狀態(tài)的新狀態(tài)如此重復(fù)，直到不再有新的如此重復(fù)，直到不再有新的狀態(tài)出現(xiàn)為止?fàn)顟B(tài)出現(xiàn)為止 NFA轉(zhuǎn)換為轉(zhuǎn)換為DFA的思想的思想1234abacac74 I Ia Ib Ic 1,4 2,3 2,3 2 4 3,4 2 2 4 4

29、3,4 3,4 （1 1）構(gòu)造一張表，它共有）構(gòu)造一張表，它共有+1+1列列（ 2 2 ） 第 一 行 第 一 列 為） 第 一 行 第 一 列 為 - -closure(S)closure(S)（3 3）求）求I Ia a、I Ib b、I Ic c（4 4）重復(fù)步驟（）重復(fù)步驟（3 3）（5 5）將狀態(tài)子集重新命名）將狀態(tài)子集重新命名1234abacac75將求得的狀態(tài)轉(zhuǎn)換矩陣重新編號(hào)將求得的狀態(tài)轉(zhuǎn)換矩陣重新編號(hào)DFA M狀態(tài)轉(zhuǎn)換矩陣：狀態(tài)轉(zhuǎn)換矩陣： 符號(hào)符號(hào)狀態(tài)狀態(tài)abc0 2 341221_334476DFA M的狀態(tài)圖：的狀態(tài)圖：注意：包含原終止?fàn)顟B(tài)注意：包含原終止?fàn)顟B(tài)4的狀態(tài)子集為

30、的狀態(tài)子集為DFA M的終態(tài)。的終態(tài)。1234abacac14231,42,342acabbc3,407778S0S1S0S1S0S1a圖圖3.16 、和和a的狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換圖 792)2)連接：連接：設(shè)設(shè)R1R1和和R2R2都是基本正則表達(dá)式，則構(gòu)造與正都是基本正則表達(dá)式，則構(gòu)造與正則表達(dá)式則表達(dá)式R1.R2R1.R2等價(jià)的等價(jià)的NFANFA如圖如圖3.173.17： S0S1R1.R2 S0S2S1R1 R2 圖3.17 R1.R2的狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換圖 3)3)選擇：選擇：設(shè)設(shè)R1 R1 和和R2 R2 都是正則表達(dá)式，則構(gòu)造與正則都是正則表達(dá)式，則構(gòu)造與正則表達(dá)式表達(dá)式R1|R

31、2R1|R2等價(jià)的等價(jià)的NFANFA如圖如圖3.183.18： S0S1R1|R2 S0S1R1 R2 圖3.18 R1|R2的狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換圖 804) 4) 重復(fù)：重復(fù)：設(shè)設(shè)R R是正則表達(dá)式，則構(gòu)造與正則表達(dá)式是正則表達(dá)式，則構(gòu)造與正則表達(dá)式RR等價(jià)的等價(jià)的NFANFA如圖如圖3.193.19： S0S1R S0S2S1 R圖3.19 R 的狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換圖 81正規(guī)表達(dá)式正規(guī)表達(dá)式R=(a|b)R=(a|b)* *abbabb構(gòu)造構(gòu)造NFA,NFA,使得使得L(N)=L(R)L(N)=L(R) AZS(a|b) *abb SZbabABbaZbbSa|bAa82例例: :M

32、 M: :03214starta,ba,ba,bbbaa解解: (1)(1)加加S ZS ZS03412Zaa,ba,ba,babb(1)(1)在在M上加兩個(gè)結(jié)點(diǎn)上加兩個(gè)結(jié)點(diǎn)S,ZS,Z，從從S S結(jié)點(diǎn)用結(jié)點(diǎn)用弧到弧到M的所有初的所有初態(tài)，從態(tài)，從M的所有終態(tài)用的所有終態(tài)用到到Z結(jié)成與結(jié)成與M等價(jià)的等價(jià)的M，M只有只有一個(gè)初態(tài)一個(gè)初態(tài)S和一個(gè)終態(tài)和一個(gè)終態(tài)Z.83(2)逐步消去逐步消去M中的所有結(jié)點(diǎn)中的所有結(jié)點(diǎn),直至剩下直至剩下S和和Z結(jié)點(diǎn)結(jié)點(diǎn),在消結(jié)過(guò)程中在消結(jié)過(guò)程中,逐步用正規(guī)式來(lái)標(biāo)記弧逐步用正規(guī)式來(lái)標(biāo)記弧, 規(guī)則如下規(guī)則如下:13R1.R2 123R1 R2 圖3.25 由NFA構(gòu)造正則

33、表達(dá)式R1R2 8412R1|R2 12R1 R2 圖3.26由NFA構(gòu)造正則表達(dá)式R1|R2 13R 123 R圖3.27由NFA構(gòu)造正則表達(dá)式R 85(2)(2)消除消除M M中的所有結(jié)點(diǎn)中的所有結(jié)點(diǎn)a|bx024yaabba|ba|bx0yaa(a|b) *bb(a|b) *a|b例例: (1)(1)加加xyxyx03412yaa,ba,ba,babbxy(a|b)*(aa|bb)(a|b)*86如果不同的如果不同的DFADFA能識(shí)別相同的語(yǔ)言，則稱它們能識(shí)別相同的語(yǔ)言，則稱它們是是等價(jià)的等價(jià)的DFADFA。在等價(jià)的在等價(jià)的DFADFA中，如果某一個(gè)中，如果某一個(gè)DFADFA的狀態(tài)數(shù)是最

34、的狀態(tài)數(shù)是最少的，則這個(gè)少的，則這個(gè)DFADFA是最簡(jiǎn)的是最簡(jiǎn)的。 對(duì)于任一個(gè)對(duì)于任一個(gè)DFADFA，存在一個(gè)唯一的狀態(tài)最少的，存在一個(gè)唯一的狀態(tài)最少的等價(jià)的等價(jià)的DFADFA最簡(jiǎn)的最簡(jiǎn)的DFA 它沒有多余它沒有多余狀態(tài)和等價(jià)狀態(tài)狀態(tài)和等價(jià)狀態(tài)871 1、等價(jià)狀態(tài)與不等價(jià)狀態(tài)等價(jià)狀態(tài)與不等價(jià)狀態(tài) 在一個(gè)確定的有窮自動(dòng)機(jī)里，如果從在一個(gè)確定的有窮自動(dòng)機(jī)里，如果從S S1 1狀態(tài)出發(fā)狀態(tài)出發(fā)接受的所有符號(hào)串集合與從接受的所有符號(hào)串集合與從S S2 2狀態(tài)出發(fā)接受的所有符狀態(tài)出發(fā)接受的所有符號(hào)串集合一樣，那么稱狀態(tài)號(hào)串集合一樣，那么稱狀態(tài)S S1 1和和S S2 2是等價(jià)的；否則是是等價(jià)的；否則是不

35、等價(jià)的。不等價(jià)的。02134abaab狀態(tài)狀態(tài)1 1和狀和狀態(tài)態(tài)2 2等價(jià)等價(jià) 88多余狀態(tài)有兩種。多余狀態(tài)有兩種。一是指從初始狀態(tài)出發(fā)，輸入任何輸入串也無(wú)法到達(dá)一是指從初始狀態(tài)出發(fā)，輸入任何輸入串也無(wú)法到達(dá)的狀態(tài)，即從初始狀態(tài)到該狀態(tài)之間沒有通路。的狀態(tài)，即從初始狀態(tài)到該狀態(tài)之間沒有通路。二是指從初始狀態(tài)出發(fā)能夠到達(dá)的狀態(tài)，但從它出發(fā)二是指從初始狀態(tài)出發(fā)能夠到達(dá)的狀態(tài)，但從它出發(fā)卻無(wú)法到達(dá)終止?fàn)顟B(tài)的狀態(tài)，即從該狀態(tài)到終止?fàn)顟B(tài)卻無(wú)法到達(dá)終止?fàn)顟B(tài)的狀態(tài)，即從該狀態(tài)到終止?fàn)顟B(tài)之間沒有通路。之間沒有通路。2 2、多余狀態(tài)多余狀態(tài)012345bbbaa0234bba893 3、DNADNA化簡(jiǎn)算法化簡(jiǎn)

36、算法設(shè)設(shè)DFA M= DFA M= （Q Q， ， ，q q0 0，F(xiàn) F），化簡(jiǎn)算法如下：），化簡(jiǎn)算法如下：1 1）先將自動(dòng)機(jī)的狀態(tài)劃分成終止?fàn)顟B(tài)集合）先將自動(dòng)機(jī)的狀態(tài)劃分成終止?fàn)顟B(tài)集合S1S1和非終止和非終止?fàn)顟B(tài)集合狀態(tài)集合S2S2： Q= S1S2Q= S1S201234bbbaaabaab123401232143434S1S2abS10，1，2S23，4902 2）對(duì)各狀態(tài)集合按下面方法劃分，直到所有狀態(tài)集合不再產(chǎn)生）對(duì)各狀態(tài)集合按下面方法劃分，直到所有狀態(tài)集合不再產(chǎn)生新的劃分為止。設(shè)第新的劃分為止。設(shè)第m m次劃分將次劃分將Q Q分成分成N N個(gè)狀態(tài)集合，即個(gè)狀態(tài)集合，即Q= Q=

37、S1S2S1S2SnSn。對(duì)狀態(tài)集合。對(duì)狀態(tài)集合SiSi（i=1i=1，2 2，n n）中的各個(gè)狀）中的各個(gè)狀態(tài)逐一檢查，設(shè)狀態(tài)態(tài)逐一檢查，設(shè)狀態(tài)q q1 1和和q q2 2是狀態(tài)集合是狀態(tài)集合SiSi中的兩個(gè)狀態(tài)，對(duì)于輸中的兩個(gè)狀態(tài)，對(duì)于輸入符號(hào)入符號(hào)a a（aa），有），有(q(q1 1,a)= S,a)= S、(q(q2 2,a)=S,a)=S”, ,若狀態(tài)若狀態(tài)S S和和S S”屬于同一狀態(tài)集合，則將狀態(tài)屬于同一狀態(tài)集合，則將狀態(tài)q q1 1和和q q2 2放在同一狀態(tài)集合中；放在同一狀態(tài)集合中；否則，將狀態(tài)否則，將狀態(tài)q q1 1和和q q2 2分為兩個(gè)集合。分為兩個(gè)集合。12340

38、1232143434S1S2abS10，1，2S23，4213401214323434S3S2abS4 S30，2 S41S23，4913 3）重復(fù)第）重復(fù)第2 2步，直到所有狀態(tài)集合都不能劃分。此步，直到所有狀態(tài)集合都不能劃分。此時(shí)，每個(gè)狀態(tài)集合中的狀態(tài)都是等價(jià)的。時(shí)，每個(gè)狀態(tài)集合中的狀態(tài)都是等價(jià)的。213401214323434S3S2abS4 S30，2 S41S23，4213401214323434S5S2abS4S6 S50S62 S41S23，4924 4）將每個(gè)狀態(tài)集合中的等價(jià)狀態(tài)合并成一個(gè)等價(jià)代表狀態(tài)。將）將每個(gè)狀態(tài)集合中的等價(jià)狀態(tài)合并成一個(gè)等價(jià)代表狀態(tài)。將狀態(tài)函數(shù)中的所有狀態(tài)

39、用相應(yīng)的等價(jià)代表狀態(tài)表示。從狀態(tài)圖狀態(tài)函數(shù)中的所有狀態(tài)用相應(yīng)的等價(jià)代表狀態(tài)表示。從狀態(tài)圖上看，要將一個(gè)狀態(tài)集合中的等價(jià)狀態(tài)結(jié)點(diǎn)合并成一個(gè)結(jié)點(diǎn)。上看，要將一個(gè)狀態(tài)集合中的等價(jià)狀態(tài)結(jié)點(diǎn)合并成一個(gè)結(jié)點(diǎn)。5 5）刪除多余狀態(tài)。）刪除多余狀態(tài)。 0123bbbaaaab圖圖3.31 化簡(jiǎn)后的有窮自動(dòng)機(jī)化簡(jiǎn)后的有窮自動(dòng)機(jī) S50S41 S62S23，4S50S41 S62S23939495輸入字符序列 分析表 控制程序 圖3.32表驅(qū)動(dòng)的詞法分析程序的模型 圖3.33分析表 96輸入字符序列 分析表 控制程序 圖3.32表驅(qū)動(dòng)的詞法分析程序的模型 圖3.33分析表 其控制程序的算法是：其控制程序的算法是：

40、 1)1)在輸入字符序列后面加一個(gè)字符在輸入字符序列后面加一個(gè)字符# #，叫結(jié)束符。將掃描指針，叫結(jié)束符。將掃描指針設(shè)在輸入序列的最左端，狀態(tài)參數(shù)設(shè)在輸入序列的最左端，狀態(tài)參數(shù)i i設(shè)為開始狀態(tài)。設(shè)為開始狀態(tài)。2)2) 掃描下一字符掃描下一字符a a，如果是結(jié)束符，如果是結(jié)束符# #，則停止；否則，根據(jù)狀，則停止；否則，根據(jù)狀態(tài)參數(shù)態(tài)參數(shù)I I和輸入的字符和輸入的字符a a查分析表，將狀態(tài)參數(shù)查分析表，將狀態(tài)參數(shù)i i設(shè)為查分析表（設(shè)為查分析表（i i，a a）后得到的狀態(tài)。）后得到的狀態(tài)。3)3) 如果如果i i是終態(tài)，則表示識(shí)別出一個(gè)單詞轉(zhuǎn)到是終態(tài)，則表示識(shí)別出一個(gè)單詞轉(zhuǎn)到4 4；否則，轉(zhuǎn)到；否則，轉(zhuǎn)到2 2。4 4）處理識(shí)別出的單詞，輸出單詞符號(hào)。狀態(tài)參數(shù)）處理識(shí)別出的單詞，輸出單詞符號(hào)。狀態(tài)參數(shù)i i設(shè)為開始狀態(tài)，設(shè)為開始狀態(tài)，轉(zhuǎn)到轉(zhuǎn)到2 2。 97構(gòu)造詞法分析器的一般步驟：構(gòu)造詞法分析器的一般步驟：1)1) 用正則表達(dá)式對(duì)程序設(shè)計(jì)語(yǔ)言單詞組成進(jìn)行描述。用正則表達(dá)式對(duì)程序設(shè)計(jì)語(yǔ)言單詞組成進(jìn)行描述。2)2)為每一個(gè)正則表達(dá)式構(gòu)造一個(gè)不確定的有窮自動(dòng)機(jī)，用來(lái)識(shí)