教案編譯原理_第1頁
教案編譯原理_第2頁
教案編譯原理_第3頁
教案編譯原理_第4頁
教案編譯原理_第5頁
已閱讀5頁,還剩57頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第三章詞法分析

詞法分析是編譯的第一個(gè)階段,在單詞的級(jí)別上分析和翻譯源程序。理論基礎(chǔ):有限自動(dòng)機(jī)理論有限自動(dòng)機(jī)理論與正規(guī)文法、正規(guī)式之間在描述語言方面一一對(duì)應(yīng)的關(guān)系3.1詞法分析程序的功能3.2單詞符號(hào)及輸出單詞的形式3.3語言單詞符號(hào)的兩種定義方式3.4正規(guī)式與有窮自動(dòng)機(jī)3.5正規(guī)文法與有窮自動(dòng)機(jī)3.6詞法分析程序的編寫方法詞法分析程序(詞法分析器或掃描器)任務(wù):從左至右掃描,根據(jù)詞法規(guī)則識(shí)別單詞,并轉(zhuǎn)化為機(jī)器易于使用的內(nèi)碼形式存在形式:(1)語法分析程序的子程序;(2)組織成一遍掃描第三章詞法分析

第一節(jié)詞法分析程序的功能第三章詞法分析

第二節(jié)單詞符號(hào)及輸出單詞的形式一、程序語言單詞的分類:

1.關(guān)鍵字(保留字或基本字):begin,end2.標(biāo)識(shí)符:用來表示各種名字

3.常數(shù):如整型常數(shù)256,實(shí)型常數(shù)3.14,布爾型常數(shù)true,‘a(chǎn)bc’4.運(yùn)算符:如,+、-、*、/等等

5.分界符:如逗號(hào),分號(hào),冒號(hào),括號(hào)等第三章詞法分析

第二節(jié)單詞符號(hào)及輸出單詞的形式二、詞法分析程序輸出單詞的形式詞法分析器的輸出:(單詞種別,單詞自身的值)1、單詞種別含義:?jiǎn)卧~的種類,提供給語法分析程序使用;設(shè)置目的:最大限度地把單詞區(qū)別開來分類法:一類一種/一字一種2、單詞自身的值單詞自身的值提供給語義分析程序使用;描述方法:對(duì)于一類一種/一字一種區(qū)別對(duì)待。第三章詞法分析

第二節(jié)單詞符號(hào)及輸出單詞的形式二、詞法分析程序輸出單詞的形式設(shè)計(jì)原則:?jiǎn)卧~種別:具體的分類設(shè)計(jì)以方便語法分析程序使用為原則。關(guān)鍵字可分成一類,也可以一個(gè)關(guān)鍵字分成一類。常數(shù)可統(tǒng)歸一類,也可按類型(整型、實(shí)型、布爾型等),每個(gè)類型的常數(shù)劃分成一類。單詞自身的值:所提供的內(nèi)容由語法分析和語義分析的任務(wù)劃分決定。第三章詞法分析

第三節(jié)語言單詞符號(hào)的兩種定義方式正規(guī)式:簡(jiǎn)潔清晰l(l|d)*正規(guī)文法:易于識(shí)別S->l|Sl|Sd第三章詞法分析

第三節(jié)語言單詞符號(hào)的兩種定義方式3.3.1正規(guī)式與正規(guī)集正規(guī)式:(Def1)設(shè)A是非空的有限字母表,A={ai|i=1,2,……n},則(1),和ai(i=1,2,……n)都是正規(guī)式。(2)若、是正規(guī)式,則|、?、*、*也是正規(guī)式。(3)正規(guī)式只能通過有限次使用1,2規(guī)則獲得。第三章詞法分析

第三節(jié)語言單詞符號(hào)的兩種定義方式3.3.1正規(guī)式與正規(guī)集正規(guī)式:(Def2)

設(shè)有字母表Σ={a1,a2

,…,an},在Σ上的正規(guī)式和它所表示的正規(guī)集可用如下規(guī)則來定義:(1)Φ是Σ上的正規(guī)式,它所表示的正規(guī)集是Φ,即空集{}。(2)是Σ上的正規(guī)式,它所表示的正規(guī)集僅含一空符號(hào)串,即{}。(3)ai是Σ上的一個(gè)正規(guī)式,它所表示的正規(guī)集是單個(gè)符號(hào)是所組成,即{ai}。第三章詞法分析

第三節(jié)語言單詞符號(hào)的兩種定義方式3.3.1正規(guī)式與正規(guī)集正規(guī)式:(Def2)(4)如果e1和e2是Σ上的正規(guī)式,它們所表示的正規(guī)集分別為L(e1)和L(e2),則:①

e1||e2是Σ上的正規(guī)式,它所表示的正規(guī)集為L(e1|e2)=L(e1)L(e2)②e1e2是Σ上的正規(guī)式,它所表示的正規(guī)集為L(e1e2)=L(e1)L(e2)③

(e1

)*是Σ上的正規(guī)式,它所表示的正規(guī)集為L((e1)*)=(L(e1))*第三章詞法分析

第三節(jié)語言單詞符號(hào)的兩種定義方式3.3.1正規(guī)式與正規(guī)集正規(guī)集由正規(guī)文法或正規(guī)式產(chǎn)生的語言注:正規(guī)集是集合,可有窮也可無窮。可通過正規(guī)式來形式化表示。例:(a|b)*(aa|bb)*(a|b)*的正規(guī)集為

{a,b}*{aa,bb}*{a,b}*第三章詞法分析

第三節(jié)語言單詞符號(hào)的兩種定義方式3.3.1正規(guī)式與正規(guī)集注:1)利用正規(guī)集相同,可用來證明相應(yīng)正規(guī)式等價(jià)。2)“|”讀作為“或”,也可寫作為“+”或“,”;“?”讀作連接。例:求正規(guī)集L()={aibjck|i,j,k>=1}的正規(guī)式=a+b+c+第三章詞法分析

第三節(jié)語言單詞符號(hào)的兩種定義方式3.3.1正規(guī)式與正規(guī)集正規(guī)式性質(zhì):定理1若、、是正規(guī)式則下述等價(jià)式成立1.+=+2.+(+)=(+)+

()=()3.(+)=+(+)=

+4.==5.(*)*=*6.*=++(+|)

=*

=*7.(+)*=(*+*)*=(**)*(|)*=(*|*)*=(**)*第三章詞法分析

第三節(jié)語言單詞符號(hào)的兩種定義方式3.3.1正規(guī)式與正規(guī)集正規(guī)式性質(zhì):定理2若、、是字母表A上的正規(guī)式,且L(),則=|當(dāng)且僅當(dāng)=*=|當(dāng)且僅當(dāng)=*2015.3.11第三章詞法分析

第三節(jié)語言單詞符號(hào)的兩種定義方式3.3.2正規(guī)文法與正規(guī)式1、正規(guī)文法到正規(guī)式的轉(zhuǎn)換步驟:(1)聯(lián)立方程組(2)按照定理2,將正規(guī)文法轉(zhuǎn)換成正規(guī)式第三章詞法分析

第三節(jié)語言單詞符號(hào)的兩種定義方式1、正規(guī)文法到正規(guī)式的轉(zhuǎn)換例:已知正規(guī)文法G1的產(chǎn)生式,求出它所定義的正規(guī)式。產(chǎn)生式為:SaS|aBBbB|bAAcA|c第三章詞法分析

第三節(jié)語言單詞符號(hào)的兩種定義方式1).由產(chǎn)生式寫出對(duì)應(yīng)的聯(lián)立方程組

S=aS|aB……(1)

B=bB|bA……(2)

A=cA|c……(3)2).根據(jù)定理2,由(1)得:S=a*aB=a+B……(4)同理,由(2)得:B=b+A……(5)同理,由(3)得:A=c*c=c+……(6)將(6)代入(5)得:B=b+c+……(7)將(7)代入(4)得:S=a+b+c+……(8)3).故:正規(guī)式為S=a+b+c+第三章詞法分析

第三節(jié)語言單詞符號(hào)的兩種定義方式2、正規(guī)式到正規(guī)文法的轉(zhuǎn)換字母表上Σ的正規(guī)式到正規(guī)文法G=(VN,VT,P,S)的轉(zhuǎn)換方法如下:(1)令VT=Σ

;(2)對(duì)任意正規(guī)式R選擇一個(gè)非終結(jié)符Z生成規(guī)則Z->R,并令S=Z;(3)若a和b都是正規(guī)式,對(duì)形如A->ab的規(guī)則轉(zhuǎn)換成A-aB和B->b兩規(guī)則,其中B是新增的非終結(jié)符;(4)在已轉(zhuǎn)換的文法中,將形如A->a*b的規(guī)則進(jìn)一步轉(zhuǎn)換成A->aA|b;(5)不斷利用規(guī)則(3)和(4)進(jìn)行變換,直到每條規(guī)則最多含有一個(gè)終結(jié)符為止。第三章詞法分析

第三節(jié)語言單詞符號(hào)的兩種定義方式2、正規(guī)式到正規(guī)文法的轉(zhuǎn)換例:將R=(a|b)(aa)*(a|b)第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)*有限自動(dòng)機(jī):為什么研究有窮自動(dòng)機(jī)?有限自動(dòng)機(jī)是一種識(shí)別裝置,它能準(zhǔn)確地識(shí)別正規(guī)集。它為詞法分析程序的構(gòu)造提供了方法和工具。有限自動(dòng)機(jī)的基本屬性與功能:有限自動(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)概括了過去輸入處理的信息。第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)*有窮自動(dòng)機(jī)模型狀態(tài):初始狀態(tài)、中間狀態(tài)和終止?fàn)顟B(tài)。

在初始狀態(tài)下,讀頭指向輸入帶的最左單元,準(zhǔn)備讀入第一個(gè)字符,每讀入一個(gè)字符,從當(dāng)前狀態(tài)進(jìn)入下一狀態(tài);當(dāng)讀頭讀入所有字符后,狀態(tài)進(jìn)入終態(tài),則輸入帶上的輸入串被接受,否則,輸入串有錯(cuò)。注:1)終止?fàn)顟B(tài)可以有若干個(gè),而初始狀態(tài)一般只有一個(gè)。

2)可用狀態(tài)轉(zhuǎn)換圖表示狀態(tài)變換,狀態(tài)用結(jié)點(diǎn)表示,讀入符號(hào)用邊表示。

abcde……有限狀態(tài)控制器輸入帶讀頭狀態(tài)變換第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)例:正規(guī)式<標(biāo)識(shí)符>=<字母>(<字母><數(shù)字>)*的狀態(tài)轉(zhuǎn)換圖形式如下:標(biāo)程序中識(shí)符xtemp的識(shí)別匹配過程為:

12222212字母字母數(shù)字xtemp第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)3.4.1確定有窮自動(dòng)機(jī)DFA(DeterministicFiniteAutomation)(1)定義:確定有限自動(dòng)機(jī)是一個(gè)五元組M=(Q,,f,S,Z)其中:Q:有限狀態(tài)集 :有限字母表f:QQ上的單值映射,f(qi,a)=qjS:唯一的初態(tài),S

∈QZ:終止?fàn)顟B(tài)集,ZQ注:這里確定的含義,就是狀態(tài)轉(zhuǎn)換關(guān)系f是一個(gè)函數(shù),即對(duì)于給定的當(dāng)前狀態(tài)qi和當(dāng)前讀入的符號(hào)a,有唯一確定的下一狀態(tài)qj第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)3.4.1確定有窮自動(dòng)機(jī)(2)狀態(tài)轉(zhuǎn)換關(guān)系表示:狀態(tài)轉(zhuǎn)換矩陣:DFA的映射關(guān)系由一個(gè)矩陣來表示。狀態(tài)轉(zhuǎn)換圖:注:1)用矩陣表示轉(zhuǎn)換便于計(jì)算機(jī)處理,但不直觀,而用狀態(tài)轉(zhuǎn)換圖表示比較直觀。2)在整個(gè)狀態(tài)轉(zhuǎn)換圖中只有一個(gè)初始狀態(tài)結(jié)點(diǎn),用“”射入的結(jié)點(diǎn)表示初始狀態(tài)。可有若干終止?fàn)顟B(tài)(也可能沒有),用雙園圈表示。若初始狀態(tài)結(jié)點(diǎn)同時(shí)又是終止?fàn)顟B(tài)結(jié)點(diǎn),則表示空串可為相應(yīng)DFA識(shí)別。例:DFAM=({0,1,2,3},{a,b},f,0,{3})f:f(0,a)=1f(0,b)=2f(1,a)=3f(1,b)=2f(2,a)=1f(2,b)=3f(3,a)=3f(3,b)=3狀態(tài)轉(zhuǎn)換矩陣

輸入狀態(tài)ab0121322133331aa032bbabab第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)(3)DFA對(duì)字符串的識(shí)別對(duì)Σ*上的任何符號(hào)串,若存在一條從初態(tài)結(jié)到終結(jié)態(tài)的道路,而且在這條路上所有弧的標(biāo)記連接成的符號(hào)串等于,則稱為DFAM所識(shí)別(接受)。DFAM所示別的符號(hào)串的全體記為L(M),稱為DFAM所識(shí)別的語言。第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)3.4.2非確定有窮自動(dòng)機(jī)NFA(Non-deterministicFA)(1)定義:非確定有窮自動(dòng)機(jī)是一個(gè)五元組

M=(Q,,f,S,Z),其中:Q:有限狀態(tài)集 :有限字母表f:Q2Q(Q的子集)上的映射S:非空的初態(tài)集,S是Q的真子集Z:終止?fàn)顟B(tài)集,Z是Q的子集,可為空集注:*非確定主要是指后繼狀態(tài)可有多個(gè)*DFA是NFA的特例3.4.1確定有窮自動(dòng)機(jī)DFA(DeterministicFiniteAutomation)注:*NFA映射的含義可表達(dá)成:f(Q’0,a)={Q0,Q1,Q2,…..,Qk},其中Qi∈Q*多值映射還可以擴(kuò)展到對(duì)輸入字符串,即f(S,ω)=P,P∈2s。如:設(shè)ω=ab,根據(jù)對(duì)讀入字符的映射關(guān)系,有f(S,ab)=f(f(S,a),b)=f({S1,S2,…,Sn},b)=f(S1,b)∪f(S2,b)∪…∪f(Sn,b)第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)例設(shè)NFAM=({q0,q1},{0,1},f,{q0},{q1})f映射為

字符狀態(tài)01q0q0

q1q1

q0,q1q0q0q111000第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)3.4.2非確定有窮自動(dòng)機(jī)NFA(2)兩自動(dòng)機(jī)等價(jià):任何兩個(gè)有限自動(dòng)機(jī)M和M’,若它們識(shí)別的語言相同(L(M)=L(M’)),則稱M和M’等價(jià)注:存在判定任何兩個(gè)有限自動(dòng)機(jī)等價(jià)性的算法第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)3.4.3由正規(guī)表達(dá)式R構(gòu)造NFA關(guān)系定理定理:上的NFAM所能識(shí)別的語言L(M)可以用上的正規(guī)式來表示。即:對(duì)上的NFAM,可構(gòu)造一個(gè)正規(guī)式,使得L()=L(M)定理:上任何正規(guī)式,存在DFAM使得L(M)=L()。即:由正規(guī)式可以構(gòu)造一個(gè)DFAM,使得L(M)=L()第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)3.4.3由正規(guī)表達(dá)式R構(gòu)造NFA輸入:字母表上的正規(guī)式R輸出:識(shí)別(接受)語言L(R)的NFAM1)由正規(guī)式

構(gòu)造一個(gè)如下僅有兩個(gè)結(jié)點(diǎn)x,y的狀態(tài)圖。2)按所引入的3條正規(guī)式分裂規(guī)則分裂;對(duì)于R=,,a的情況,按書P40-41圖3.7,3.8,3.9所示處理。3)重復(fù)步驟2直到每個(gè)弧上的標(biāo)記是上的一個(gè)字符或?yàn)橹?。注:將所得的NFAM(因?yàn)榘?進(jìn)行確定化就得到DFA。xy第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)3.4.3由正規(guī)表達(dá)式R構(gòu)造NFA正規(guī)式分裂規(guī)則:12|1221121‘12*

211‘xy(a|b)*(aa|bb)(a|b)*例:根據(jù)正規(guī)式(a|b)*(aa|bb)(a|b)*,構(gòu)造DFAM,使之等價(jià)1y(a|b)*(a|b)*

2x(aa|bb)1y

2xaa5

bba|b

6

a|b1y

2xa5

ba

6

abb34ab第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)3.4.4NFA確定化為DFA的方法(1)定理對(duì)于每個(gè)NFAM,存在一個(gè)DFAM’,使得L(M)=L(M’)。即,設(shè)L是一NFA接受的正規(guī)集,則存在一個(gè)DFA接受L第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)3.4.4NFA確定化為DFA的方法(2)問題已知-輸入:一個(gè)NFAN求-輸出:一個(gè)接受相同語言的DFAM求解基本思想:把NFA狀態(tài)集的一個(gè)子集轉(zhuǎn)化為DFA中的一個(gè)狀態(tài);通過DFA的狀態(tài)記錄在NFA輸入符號(hào)之后可能到達(dá)的所有狀態(tài)的集合。3.4.4NFA確定化為DFA的方法

(3)算法①:算法:由NFAM=(Q,,f,S,Z)構(gòu)造一個(gè)等價(jià)的DFAM’=(Q’,,f’,S’,Z’)1.取S’=S,2.若狀態(tài)集Q’中有狀態(tài)S’i={s0,s1,……sj},sk∈Q,0kj;而且M機(jī)中有f({s0,s1,……sj},a)=f(s0,a)∪f(s1,a)∪……∪f(sj,a)= ={s0,s1,……st},令其為St’

,若St’不在Q’中,則將St’加入Q’。

算法:

3.重復(fù)步驟2,直到Q’中無新狀態(tài)加入為止。

4.取終態(tài)Z’={I|I∈Q’,且I∩Z<>}

注:1)上述過程可在有限步內(nèi)完成,因?yàn)镸機(jī)狀態(tài)的冪集是有限的;2)上述過程也可用表格法來描述,其中列是字符集中的字符;行是Q’中的各狀態(tài),開始僅包含S’狀態(tài),隨著算法的執(zhí)行,Q’的狀態(tài)逐漸增多直止不再增多為止;表格元素就是f’映射函數(shù)。3.4.4NFA確定化為DFA的方法

(3)算法①:

注:3)NFA確定化的實(shí)質(zhì)是以原有狀態(tài)集上的覆蓋片(COVER)作為DFA上的一個(gè)狀態(tài),將原狀態(tài)間的轉(zhuǎn)換改為覆蓋片間的轉(zhuǎn)換,從而將不確定問題確定化。4)通常,經(jīng)確定化后,狀態(tài)數(shù)增加,而且可能出現(xiàn)一些等價(jià)狀態(tài),這時(shí)需要化簡(jiǎn)。3.4.4NFA確定化為DFA的方法

(3)算法①:3.4.4NFA確定化為DFA的方法

(4)算法②:通過-closure()

問題回顧:已知-輸入:一個(gè)NFAN求-輸出:一個(gè)接受相同語言的DFAM預(yù)備知識(shí):-closure設(shè)I是NFAN的一個(gè)狀態(tài)子集,-closure(I)的定義為:(1)若s∈I,則s∈-closure(I)。(2)若s∈I,則從s出發(fā)經(jīng)過任意條弧而能到達(dá)的任何狀態(tài)s’,都屬于-closure(I)。算法:1.置DFAM中的狀態(tài)集Q’和Z’為;2.給出M的初態(tài)S’=-closure({S}),并把S’置為未標(biāo)記狀態(tài)后加入到Q’中;3.如果Q’中存在未標(biāo)記的狀態(tài)T={t0,t1,……tj},

ti∈Q,則進(jìn)行如下變換:(1)對(duì)于每個(gè)a∈Σ,置:J=f({t0,t1,……,tj},a)=f(t0,a)f(t1,a)…f(ti,a)U=-closure(J)如果U不在Q’中,則將U置為無標(biāo)記的狀態(tài)添加到Q’中,且把狀態(tài)轉(zhuǎn)移f’(T,a)=U添加到M中,如果U中至少含有一個(gè)元素是N的終態(tài),則把U置為M的終態(tài),即把U添加到Z’中;3.4.4NFA確定化為DFA的方法

(4)算法②:通過-closure()

第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)(2)對(duì)T置標(biāo)記(表示不再是新加入Q’中的狀態(tài))。4.重復(fù)步驟3,直到Q’中不再含有未標(biāo)記的狀態(tài)為止;5.重命名Q’中的狀態(tài),最后獲得等價(jià)的DFAM。例把上例的NFA確定化

設(shè)NFAM=({q0,q1},{0,1},f,{q0},{q1}),狀態(tài)轉(zhuǎn)換圖為,試將其確定化解:

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

此時(shí),Q={I0,I1}q0q1110003.由Q中的狀態(tài)I1={q1},查看M機(jī),有:

f({q1},0)={q0,q1}

=I2、f({q1},1)={q0}=I0此時(shí),Q={I0,I1,I2}3.由Q中的狀態(tài)I2={q0,q1},查看M機(jī),有:

f({q0,q1},0)={q0,q1}、f({q0,q1},1)={q0,q1}=I2此時(shí),Q={I0,I1,I2}4.F={I1,I2}NFA經(jīng)過確定化后,變?yōu)椋篋FAM’=({I0,I1,I2},{0,1},,I0,{I1,I2}

Q01I0={q0}I0={q0}I1={q1}I1={q1}I2={q0,q1}

I0={q0}I2={q0,q1}

I2={q0,q1}

I2={q0,q1}

01I0I0I1I1I2I0I2I2I2狀態(tài)轉(zhuǎn)換圖如下:I0I111000I21第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)3.4.5DFA的化簡(jiǎn)(最小化)********(1)問題:化簡(jiǎn)DFAM已知-輸入:DFAM求-輸出:DFAM’,使得L(M’)=L(M)且M’的狀態(tài)數(shù)最少化簡(jiǎn)前提:接受的語言必須相同第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)3.4.5DFA的化簡(jiǎn)(2)概念:DFA化簡(jiǎn):尋找一個(gè)狀態(tài)數(shù)比源DFAM少的DFAM’,使得L(M’)=L(M)且對(duì)于M’(1)沒有多余狀態(tài)(2)它的狀態(tài)集中,沒有兩個(gè)狀態(tài)是互相等價(jià)的多余狀態(tài)::從該自動(dòng)機(jī)的開始狀態(tài)出發(fā),任何輸入串都不能達(dá)到的狀態(tài)。等價(jià)狀態(tài):設(shè)DFAM=(Q,,f,S0,F),s,t∈Q。若對(duì)任何Σ,f(s,)F當(dāng)且僅當(dāng)f(t,)F

,則稱狀態(tài)s和t是等價(jià)的。如果s和t不等價(jià),則稱s和t是可區(qū)別的。第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)3.4.5DFA的化簡(jiǎn)(3)化簡(jiǎn)(最小化)算法基本思想——?jiǎng)澐址?.將DFAM中的狀態(tài)劃分為互不相交的子集,每個(gè)子集內(nèi)部的狀態(tài)都等價(jià);而在不同子集間的狀態(tài)均不等價(jià)。2.從每個(gè)子集中任選一個(gè)狀態(tài)作為代表,消去其它等價(jià)狀態(tài)。3.把那些原來射入其它等價(jià)狀態(tài)的弧改為射入相應(yīng)的代表狀態(tài)。3.4.5DFA的化簡(jiǎn)(4)化簡(jiǎn)算法1.把狀態(tài)集S劃分為終態(tài)集和非終態(tài)集:∏0={I01,I02},I01屬于非終態(tài)集,I02屬于終態(tài)集。因?yàn)榻K態(tài)能識(shí)別,而非終態(tài)不能,所以它們是可區(qū)別的;2.假定經(jīng)過k次劃分后:∏k={Ik1……Ikm}.這m個(gè)子集之間可區(qū)分,子集內(nèi)部還是否可以劃分?任取一個(gè)子集Iki={s1,s2,……sk},若存在某讀入字符a,使f(Iki,a)的結(jié)果不是全部包含在∏k的某個(gè)子集中,則說明Iki中有不等價(jià)的狀態(tài),還要進(jìn)一步劃分。對(duì)∏k中所有子集都進(jìn)行測(cè)試,以完成一次劃分。第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)3.4.5DFA的化簡(jiǎn)(4)化簡(jiǎn)算法3.重復(fù)步驟2,直到所含的子集數(shù)不再增加為止。4.對(duì)每個(gè)子集任取一狀態(tài)為代表。若該子集包含原有的初態(tài),則相應(yīng)代表狀態(tài)就是最小化后M的初態(tài);同樣,若該子集包含原有的終態(tài),則相應(yīng)代表狀態(tài)就是最小化后M的終態(tài)。注:可以通過消除多余狀態(tài),合并等價(jià)狀態(tài)而轉(zhuǎn)化成一個(gè)最小化的與之等價(jià)的有限自動(dòng)機(jī)。第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)例:設(shè)有一DFA的狀態(tài)轉(zhuǎn)換圖如下,試化簡(jiǎn)之。0123546aaaaaaabbbbbbb解:1.把M的狀態(tài)分為兩組:終態(tài)集,非終態(tài)集∏0={{0,1,2},{3,4,5,6}}2.a)考察非終態(tài)集:

f({0,1,2},a)={1,3}不屬于∏0的任何一個(gè)子集,所以{0,1,2}要分開得到:∏1`={{1},{0,2},{3,4,5,6}}再看:f({0,2},a)={1}屬于∏1‘的子集

f({0,2},b)={2,5}不屬于∏1‘的任何子集,所以{0,2}要分開得到:∏1``={{1},{0},{2},{3,4,5,6}}第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)解:(續(xù))2.b)考察終態(tài)集:

f({3,4,5,6},a)={3,6}包含于∏1“的子集{3,4,5,6}f({3,4,5,6},b)={4,5}包含于∏1“的子集{3,4,5,6}所以{3,4,5,6}不可再劃分3.整個(gè)劃分為4個(gè)組:∏2={{1},{0},{2},{3,4,5,6}}4.令狀態(tài)3代表{3,4,5,6},把原來到達(dá)狀態(tài)4,5,6的弧都導(dǎo)入3,并刪除4,5,6。得:第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)第三章詞法分析

第四節(jié)正規(guī)式與有窮自動(dòng)機(jī)012aab3aabb即為化簡(jiǎn)了的DFA3.4.6有窮自動(dòng)機(jī)到正規(guī)式的轉(zhuǎn)換方法:(1)在原有轉(zhuǎn)換圖上添加兩節(jié)點(diǎn)x,y;x通過線與所有初態(tài)節(jié)點(diǎn)相連,所有終態(tài)節(jié)點(diǎn)通過線與y相連(2)按如下法則逐步消

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論