第四章詞法分析_第1頁(yè)
第四章詞法分析_第2頁(yè)
第四章詞法分析_第3頁(yè)
第四章詞法分析_第4頁(yè)
第四章詞法分析_第5頁(yè)
已閱讀5頁(yè),還剩76頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

第四章詞法分析第1頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.1詞法分析程序的設(shè)計(jì)回顧

什麼是詞法分析(lexicalanalysis)程序又稱詞法分析器或掃描器,主要功能是逐個(gè)讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞。單詞是語(yǔ)言中具有獨(dú)立意義的最小單位,包括保留字、標(biāo)識(shí)符、運(yùn)算符、標(biāo)點(diǎn)符號(hào)和常量等。詞法分析是編譯過(guò)程中的一個(gè)階段,在語(yǔ)法分析前進(jìn)行。也可以和語(yǔ)法分析結(jié)合在一起作為一遍,由語(yǔ)法分析程序調(diào)用詞法分析程序來(lái)獲得當(dāng)前單詞供語(yǔ)法分析使用。第2頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月詞法分析程序和語(yǔ)法分析程序的關(guān)系字符串源程序詞法分析

符號(hào)串源程序圖4.1a詞法分析單獨(dú)作為一遍

字符串源程序詞法分析器

語(yǔ)法分析器取符號(hào)送符號(hào)圖4.1b詞法分析作為語(yǔ)法分析子程序第3頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月詞法分析程序的任務(wù)詞法分析程序的主要任務(wù):掃描源程序,識(shí)別出具有獨(dú)立意義的單詞詞法分析程序的其他任務(wù):濾掉空格,跳過(guò)注釋、換行符追蹤換行標(biāo)志,將行號(hào)與出錯(cuò)信息相聯(lián)系起來(lái)。宏展開(kāi),……第4頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月詞法分析程序的輸出格式詞法分析的輸出常采用二元式:

(單詞類別,單詞自身的值)單詞類別通常用一個(gè)整數(shù)類碼或單詞記號(hào)表示,單詞記號(hào)比整數(shù)碼含義明確。若還需記錄單詞的一些其它屬性值:如標(biāo)識(shí)符的類別、層次等,可將這些屬性統(tǒng)一放到符號(hào)表中,并將單詞的二元式表示為:(標(biāo)識(shí)符,指向該標(biāo)識(shí)符所在符號(hào)表中位置的指針)第5頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月詞法分析程序的結(jié)構(gòu)將詞法分析從語(yǔ)法分析部分獨(dú)立出來(lái)的原因使整個(gè)編譯程序的結(jié)構(gòu)更簡(jiǎn)潔、清晰、條例化改進(jìn)編譯效率增加編譯系統(tǒng)的可移植性第6頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月手工構(gòu)造首先確定出能夠識(shí)別程序中單詞的確定的有窮自動(dòng)機(jī)(DFA),然后可以采用直接編程的方法或者表驅(qū)動(dòng)的方法來(lái)構(gòu)造詞法分析器。借助相關(guān)工具的自動(dòng)構(gòu)造如:Lex編譯系統(tǒng)詞法分析程序的常用設(shè)計(jì)方法第7頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月

多數(shù)程序設(shè)計(jì)語(yǔ)言的單詞的語(yǔ)法均可用正規(guī)文法來(lái)表示。回顧:正規(guī)文法(3型文法):任一產(chǎn)生式的形式都為A→aB或A→a,其中A∈VN

,B∈VN

,a∈VT*正規(guī)文法描述的是VT上的正規(guī)集。例:程序設(shè)計(jì)語(yǔ)言中幾類單詞的描述規(guī)則:標(biāo)識(shí)符、無(wú)符號(hào)整數(shù)、運(yùn)算符…。(參見(jiàn)課本P52)4.2單詞的描述工具-正規(guī)式第8頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.2單詞的描述工具-正規(guī)式正規(guī)式(regularexpression也叫正則表達(dá)式)正規(guī)式是定義正規(guī)集的數(shù)學(xué)工具,是說(shuō)明單詞的模式(pattern)的一種表示法,用它描述單詞符號(hào)時(shí)一般比正規(guī)文法更簡(jiǎn)潔。正規(guī)式和正規(guī)集(即其描述的語(yǔ)言)的定義可以用遞歸的形式給出。第9頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.2單詞的描述工具-正規(guī)式正規(guī)式設(shè)∑是有窮字母表,并定義輔助字母表∑’={Φ,ε,|,.,*,(,)}1.ε,Φ都是∑上的正規(guī)式,它們所表示的正規(guī)集為{ε},Φ;2.任何a是一個(gè)正規(guī)式,若a∈∑,它所表示的正規(guī)集為{a};3.如果R1和R2是正規(guī)式,其表示的正規(guī)集分別為L(zhǎng)1和L2,則

1)正規(guī)式R1|R2或R1+R2表示的正規(guī)集為L(zhǎng)1∪L2

2)正規(guī)式R1.R2或R1R2表示的正規(guī)集為L(zhǎng)1L2

3)正規(guī)式{R1}或R1*表示的正規(guī)集為L(zhǎng)1*

4)正規(guī)式(R)表示的正規(guī)集仍是L1,但調(diào)整優(yōu)先權(quán),使括號(hào)內(nèi)的運(yùn)算符優(yōu)先權(quán)高于括號(hào)外的。第10頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.僅有有限次使用上述三步驟而定義的表達(dá)式才是∑上的正規(guī)式,僅有這些正規(guī)式表示的字集才是∑上的正規(guī)集。4.2單詞的描述工具-正規(guī)式注意:不要混淆Φ和ε,正則表達(dá)式ε描述的語(yǔ)言只含一個(gè)空字符串ε,而Φ表示的語(yǔ)言不含有任何字符串。

第11頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月例4.2.1:令

={a,b},則上的正規(guī)式和相應(yīng)正規(guī)集為(1)a(2)ab(3)ab(4)(ab)(ab) (5)a

(6)(ab)

(7)(ab)

(aabb)(ab)

(1){a}(2){a,b}(3){ab}(4){aa,ab,ba,bb}(5){

,a,aa,……任意個(gè)a的串}(6){

,a,b,aa,ab,bb……所有由a和b組成的串}(7)

上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b組成的串}第12頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月例4.2.2:令

={l,d},則上的正規(guī)式r=l(ld)

定義的正規(guī)集為程序設(shè)計(jì)語(yǔ)言的單詞都能用正規(guī)式來(lái)定義。若兩個(gè)正規(guī)式e1,e2表示的正規(guī)集相同,則稱它們等價(jià)。記作:e1=e2

{l,ll,ld,ldd,……},其中l(wèi)代表字母,d代表數(shù)字,即:字母(字母|數(shù)字)

,它表示的正規(guī)集中的每個(gè)元素的模式是“字母打頭的字母數(shù)字串”,即Pascal和多數(shù)程序設(shè)計(jì)語(yǔ)言允許的的標(biāo)識(shí)符的詞法規(guī)則.第13頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月正規(guī)式服從的代數(shù)運(yùn)算規(guī)律:設(shè)r,s,t為正規(guī)式,則它們滿足如下運(yùn)算規(guī)律:r|s=s|rr|(s|t)=(r|s)|t(rs)t=r(st)r(s|t)=rs|rt;(s|t)r=sr|tr:或的分配律

r=r;r

=r:

是“連接”的恒等元素r|r=r:“或”的抽取律第14頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月一個(gè)正規(guī)語(yǔ)言可用正規(guī)文法表示也可用正規(guī)式表示,兩者具有等價(jià)性。一般而言正規(guī)式在描述語(yǔ)言時(shí)比正規(guī)文法更為簡(jiǎn)潔。正規(guī)文法和正規(guī)式的等價(jià)性例如,用正規(guī)文法表示標(biāo)識(shí)符的文法規(guī)則如下:<標(biāo)識(shí)符>

a|b|…|z|<標(biāo)識(shí)符>a|<標(biāo)識(shí)符>b|…|<標(biāo)識(shí)符>z|<標(biāo)識(shí)符>0|<標(biāo)識(shí)符>1|…|<標(biāo)識(shí)符>9而采用正規(guī)表達(dá)式則為:<標(biāo)識(shí)符>=

(a|b|c|…|z){a|b|…|z|0|1|…|9}或簡(jiǎn)寫成<標(biāo)識(shí)符>=字母{字母|數(shù)字}第15頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月將上的正規(guī)式r轉(zhuǎn)換成正規(guī)文法G=(VN,VT,S,P).

令VT=,產(chǎn)生式和VN按如下方法確定:選擇一非終結(jié)符S生成類似產(chǎn)生式的形式Sr,并將S定為文法G的識(shí)別符。若x,y是正規(guī)式,對(duì)形如Axy的正規(guī)式產(chǎn)生式,重寫成:AxB,By,B為新選的非終結(jié)符。對(duì)形如Ax*y的正規(guī)式,重寫成:AxB,Ay,BxB,By,B為新選的非終結(jié)符。對(duì)形如Ax|y的正規(guī)式,重寫成:Ax,Ay。不斷利用上述規(guī)則做變換,直到每個(gè)產(chǎn)生式都符合正規(guī)文法的形式即可。正規(guī)文法和正規(guī)式的等價(jià)性第16頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月例4.2.3:將r=a(a|d)*轉(zhuǎn)換成相應(yīng)的正規(guī)文法正規(guī)文法和正規(guī)式的等價(jià)性第17頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月將正規(guī)文法轉(zhuǎn)換為正規(guī)式基本上是正規(guī)式到正規(guī)文法轉(zhuǎn)換過(guò)程的逆過(guò)程??煞磸?fù)采用以下三條規(guī)則,直到只剩下一個(gè)開(kāi)始符號(hào)定義的正規(guī)式為止。產(chǎn)生式AxB,By對(duì)應(yīng)正規(guī)式A=xy;產(chǎn)生式AxA|y對(duì)應(yīng)正規(guī)式A=x*y;產(chǎn)生式Ax,Ay對(duì)應(yīng)正規(guī)式A=x|y;正規(guī)文法和正規(guī)式的等價(jià)性第18頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月例4.2.4:

將G[S]轉(zhuǎn)換為正規(guī)式SaASaAaAAdAAaAd正規(guī)文法和正規(guī)式的等價(jià)性解:由文法G[S]得S=aA|aA=(aA|dA)|(a|d)則S=a(a|d)*(a|d)|a=a((a|d)*(a|d)|)=a(a|d)*第19頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.3有窮自動(dòng)機(jī)

有窮自動(dòng)機(jī)(有限自動(dòng)機(jī))作為一種識(shí)別裝置,它能準(zhǔn)確地識(shí)別正規(guī)集(即正規(guī)式所表示的集合)。有窮自動(dòng)機(jī)為詞法分析程序的自動(dòng)構(gòu)造提供了有效的方法和工具。

有窮自動(dòng)機(jī)分為兩類:確定的有窮自動(dòng)機(jī)(DeterministicFiniteAutomata:DFA)

不確定的有窮自動(dòng)機(jī)(NondeterministicFiniteAutomata:NFA)第20頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.3關(guān)于有窮自動(dòng)機(jī)將主要討論如下問(wèn)題確定的有窮自動(dòng)機(jī)DFA不確定的有窮自動(dòng)機(jī)NFANFA的確定化DFA的最小化第21頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月一、確定的有窮自動(dòng)機(jī)DFADFA定義:一個(gè)確定的有窮自動(dòng)機(jī)(DFA)M是一個(gè)五元組:M=(K,Σ,f,S,Z),其中1.K是一個(gè)有窮集,它的每個(gè)元素稱為一個(gè)狀態(tài);2.Σ是一個(gè)有窮字母表,它的每個(gè)元素稱為一個(gè)輸入符號(hào),所以Σ也稱為輸入符號(hào)表;第22頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月DFA定義(續(xù)):3.f是轉(zhuǎn)換函數(shù),是在K×Σ→K上的單值映射,即如存在f(ki,a)=kj,(ki∈K,kj∈K),則當(dāng)前狀態(tài)為ki且輸入符為a時(shí),將轉(zhuǎn)換為下一個(gè)狀態(tài)kj,我們把kj稱作ki的一個(gè)后繼狀態(tài);4.S∈K是唯一的一個(gè)初態(tài);5.Z

K是一個(gè)終態(tài)集,終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。一、確定的有窮自動(dòng)機(jī)DFA第23頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月一、確定的有窮自動(dòng)機(jī)DFA例4.3.1:DFAM=({S,U,V,Q},{a,b},f,S,{Q})其中f定義為:f(S,a)=U f(V,a)=Uf(S,b)=V f(V,b)=Qf(U,a)=Q f(Q,a)=Qf(U,b)=V f(Q,b)=Q第24頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月上例中DFA的狀態(tài)圖表示bSUVQaaaba,bb一、確定的有窮自動(dòng)機(jī)DFA第25頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月上例中DFA的矩陣表示字符狀態(tài)0001一、確定的有窮自動(dòng)機(jī)DFA第26頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月概念:∑*上的符號(hào)串t被DFAM接受一、確定的有窮自動(dòng)機(jī)DFA定義1:對(duì)∑*中的任何符號(hào)串t,若存在一條從初態(tài)結(jié)點(diǎn)某一終態(tài)結(jié)點(diǎn)的道路,且這條道路上所有弧連接成的符號(hào)串等于t,則稱t可為DFAM所接受,若M的初態(tài)同時(shí)又是終態(tài)結(jié)點(diǎn),則空字可為M所接受。定義2:若t∈∑*,f(S,t)=P,其中S為DFAM的開(kāi)始狀態(tài),P∈Z,Z為終態(tài)集,則稱t可為M所接受(識(shí)別)。DFAM所能接受的符號(hào)串的全體記為L(zhǎng)(M)。DFA的確定性表現(xiàn)在f:K×

K是一個(gè)單值函數(shù)。第27頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月一個(gè)輸入符號(hào)串t(表示為t1tx),其中t1∈∑,tx∈∑*,則t在DFAM上運(yùn)行的定義為:f(Q,t1tx)=f(f(Q,t1),tx)

其中Q∈K,f(Q,)=Q。一、確定的有窮自動(dòng)機(jī)DFA

概念:∑*上的符號(hào)串t被DFAM上運(yùn)行上一個(gè)符號(hào)串集V

是正規(guī)的,當(dāng)且僅當(dāng)存在一個(gè)上的DFAM

,使得V=L(M)。第28頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月一、確定的有窮自動(dòng)機(jī)DFA例4.3.2:證明t=baab被下圖的DFA所接受bSUVQabba,baaf(S,baab)=f(f(S,b),aab)=f(V,aab)=f(f(V,a),ab)=f(U,ab)=f(f(U,a),b)=f(Q,b)=QQ屬于終態(tài)。得證。第29頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月DFA行為的程序模擬.DFAM=(K,Σ,f,S,Z)的行為的模擬程序K:=S;c:=getchar;whilec<>eofdo{K:=f(K,c);c:=getchar;};ifKisinZthenreturn(‘yes’)elsereturn(‘no’)一、確定的有窮自動(dòng)機(jī)DFA第30頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月二、不確定的有窮自動(dòng)機(jī)NFA

NFA定義:NFAN=(K,,f,S,Z),其中K為有窮狀態(tài)集,為有窮輸入字母表,f為K

到K的子集的映射,SK是一個(gè)非空初態(tài)集,ZK為終態(tài)集。NFA與DFA的區(qū)別主要有:NFA中狀態(tài)轉(zhuǎn)換函數(shù)為多值函數(shù)。NFA中起始狀態(tài)可以有多個(gè),但從正規(guī)文法出發(fā)構(gòu)造的NFA起始狀態(tài)是唯一的。第31頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月二、不確定的有窮自動(dòng)機(jī)NFA例4.3.3:NFAN=({S,P,Z},{0,1},f,{S,P},{Z})其中f(S,0)={P}f(S,1)={S,Z}f(P,1)={Z}f(Z,0)={P}f(Z,1)={P}SPZ00,1111狀態(tài)圖表示第32頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月矩陣表示簡(jiǎn)化為二、不確定的有窮自動(dòng)機(jī)NFA第33頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月

類似DFA,NFAN=(K,,f,S,Z)也有如下定義:符號(hào)串t在NFAN上運(yùn)行一個(gè)輸入符號(hào)串t(將它表示成Tt1的形式,其中T∈∑,t1∈∑*)在NFAN上運(yùn)行的定義為:

f(Q,Tt1)=f(f(Q,T),t1)其中Q∈K.符號(hào)串t被NFAN接受若f(S0,t)=P,其中t

∑*,S0∈S,PZ,則稱t為NFAN所接受(識(shí)別)二、不確定的有窮自動(dòng)機(jī)NFA第34頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月

符號(hào)串t被NFAN接受也可以這樣理解對(duì)于任何一個(gè)符號(hào)串t(t∈∑*),若存在一條從某一初態(tài)到某一終態(tài)的道路,且這條道路上所有弧的標(biāo)記字依序連接成的串(不計(jì)ε弧)等于t,則稱t為NFAN所接受。二、不確定的有窮自動(dòng)機(jī)NFA

有了上述定義后,實(shí)際上也就是對(duì)NFA的轉(zhuǎn)換函數(shù)

f進(jìn)行了如下擴(kuò)充:

f:K

K的子集

f:K*

K的子集第35頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月二、不確定的有窮自動(dòng)機(jī)NFA例4.3.4:下列符號(hào)串哪些可以被圖中NFA所接受?11110100010001100第36頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月二、不確定的有窮自動(dòng)機(jī)NFA例4.3.4:下列符號(hào)串哪些可以被圖中NFA所接受?11110100010001100第37頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月

若將NFAN所能接受的符號(hào)串的全體記為L(zhǎng)(N),則有如下結(jié)論:對(duì)每個(gè)NFAN存在著與之等價(jià)的DFAM,使得L(M)=L(N)。并且最小的DFAM是唯一的。將NFA轉(zhuǎn)換成等價(jià)的DFA的算法---子集法。二、不確定的有窮自動(dòng)機(jī)NFA第38頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月有關(guān)狀態(tài)集合I的兩個(gè)運(yùn)算:1.狀態(tài)集合I的ε-閉包,記為ε-closure(I),定義為一狀態(tài)集,是由狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條ε弧而能到達(dá)的狀態(tài)所構(gòu)成的集合。狀態(tài)集合I的任何狀態(tài)都屬于ε-closure(I)。2.狀態(tài)集合I的a弧轉(zhuǎn)換,記為move(I,a),是所有那些可從I中的某一狀態(tài)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)的全體。三、NFA的確定化

第39頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月12534687aa

a三、NFA的確定化

有關(guān)狀態(tài)集合I的運(yùn)算實(shí)例計(jì)算下列各式的值1)move({1,2},a)2)-closure({5,3,4})運(yùn)算結(jié)果:1)={5,3,4};2)={2,3,4,5,6,7,8};例4.3.5:若I1={1},則

-closure(I1)={1,2};move(I1,a)={4,5};-closure(move({1,2},a))第40頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月三、NFA的確定化

子集法:

假設(shè)NFAN=(K,,f,K0,Kt),按如下方法可構(gòu)造一個(gè)DFAM=(S,,d,S0,St),使得L(M)=L(N):1.M的狀態(tài)集S由K的一些子集組成。用[S1,S2,...,

Sj]表示S的元素,其中S1,S2,,...

Sj是K的狀態(tài)。并且約定:狀態(tài)S1,S2,,...

Sj是按某種規(guī)則排列的,即對(duì)于子集{S1,S2}={S2,S1,}來(lái)說(shuō),S的狀態(tài)就是[S1,S2];第41頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月2M和N的輸入字母表是相同的,即是;3轉(zhuǎn)換函數(shù)是這樣定義的: d([S1,S2,...

Sj],a)=[R1,R2,...

,Rt]

其中[R1,R2,...

,Rt]=

-closure(

move([S1,S2,...

Sj],a))

4S0=-closure(K0)為M的開(kāi)始狀態(tài);5St={[Si,Sk,...,

Se],其中[Si,Sk,...,

Se]S

且{Si,Sk,,...,

Se}Kt

}三、NFA的確定化第42頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月構(gòu)造NFAN中狀態(tài)K的子集的算法:

假定所構(gòu)造的子集族為CS,即CS=(T1,T2,,...

Ti),其中T1,T2,...,Ti為狀態(tài)K的子集,則其構(gòu)造步驟如下:

1.令

-closure(K0)為CS中唯一成員,且它是未被標(biāo)記的。2.while(CS中存在尚未被標(biāo)記的子集T)do{標(biāo)記T;

for每個(gè)輸入字母ado {U:=-closure(move(T,a));

ifU不在CS中then

將U作為未標(biāo)記的子集加在CS中

} }三、NFA的確定化

第43頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月例4.3.6:將下圖NFAN=(K,,f,K0,Kt)轉(zhuǎn)換為等價(jià)的DFAM其中M=(S,,d,S0,St)。4f35621i

aaaabbbb三、NFA的確定化第44頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月表1NFA狀態(tài)子集的構(gòu)造結(jié)果4f35621i

aaaabbbb第45頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月aDECBFFAbaaaaabbbbbabG三、NFA的確定化轉(zhuǎn)換為DFA后的狀態(tài)圖第46頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月四、DFA的化簡(jiǎn)結(jié)論:對(duì)于任何給定的DFA,都存在一個(gè)與之等價(jià)的最少狀態(tài)DFA,并且該最少狀態(tài)DFA是唯一的。最少狀態(tài)DFA應(yīng)滿足:

1).沒(méi)有多余狀態(tài);2).沒(méi)有等價(jià)狀態(tài)。多余狀態(tài):從自動(dòng)機(jī)的開(kāi)始狀態(tài)出發(fā),任何輸入串也不能到達(dá)的狀態(tài);或者是沒(méi)有通路到達(dá)終態(tài)的狀態(tài)。兩個(gè)狀態(tài)s和t等價(jià)是指它們具備以下特性:一致性(兼容性):即兩狀態(tài)同是終態(tài)或同是非終態(tài)蔓延性:對(duì)所有輸入符號(hào),狀態(tài)s和t必須轉(zhuǎn)換到等價(jià)的狀態(tài)里?;蛘哒f(shuō)從兩狀態(tài)出發(fā)所接受的符號(hào)串集合相同。第47頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月四、DFA的化簡(jiǎn)例4.3.7:判斷下圖中那些狀態(tài)是多余狀態(tài)。012345bbbaa0234bba刪除多余狀態(tài)后的狀態(tài)圖

第48頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月四、DFA的化簡(jiǎn)例4.3.8:判斷下圖中那些狀態(tài)是等價(jià)狀態(tài)。解:因?yàn)閒(1,a)=3,f(2,a)=3,所以狀態(tài)1和狀態(tài)2是等價(jià)的02134abaab4第49頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月上圖DFA中D、E、F、G為等價(jià)狀態(tài)。四、DFA的化簡(jiǎn)例4.3.9:判斷下圖中那些狀態(tài)是等價(jià)狀態(tài)。aDECBFFAbaaaaabbbbbabG第50頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月結(jié)論:一個(gè)DFA可以通過(guò)消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)與之等價(jià)的最小DFA。

DFA的最小化算法(分割法)算法的核心思想:把一個(gè)DFA的狀態(tài)分成一些不相交的子集,使得任何不同的兩子集的狀態(tài)都是可區(qū)別的,而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的。算法具體步驟:以DFAM=(K,∑,f,k0,kt)的最小化為例

1.構(gòu)造自動(dòng)機(jī)的初始劃分:終態(tài)集kt和非終態(tài)集K-kt兩組四、DFA的化簡(jiǎn)第51頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月2.對(duì)各狀態(tài)集按下面方法進(jìn)行劃分,直到所有狀態(tài)集合不再產(chǎn)生新的劃分為止。設(shè)第m次劃分將K分成n個(gè)狀態(tài)集合(K=S1∪S2…∪Sn)。對(duì)狀態(tài)集合Si中的各狀態(tài)逐一檢查,設(shè)q1,q2是狀態(tài)集合Si中的兩個(gè)狀態(tài),對(duì)任意輸入符號(hào)a,有f(q1,a)=S’,f(q2,a)=S”,若狀態(tài)S’和S”不屬于同一狀態(tài)集,則將q1和q2分為兩個(gè)集合。3.重復(fù)第2步,直到所有狀態(tài)集合都不能劃分。4.將每個(gè)狀態(tài)集中的等價(jià)狀態(tài)合并成一個(gè)狀態(tài)。5.刪除多余狀態(tài)。四、DFA的化簡(jiǎn)第52頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月四、DFA的化簡(jiǎn)對(duì)S1={0,1,2}劃分:因?yàn)閒(0,a)=1,f(1,a)=3,f(2,a)=1,故1,2不屬于同一狀態(tài)集,所以將S1分成S3={0,2},S4={1}對(duì)S3={0,2}劃分:因?yàn)閒(0,b)=2,f(2,b)=4,故S3應(yīng)分成S5={0},S6={2}對(duì)S2={3,4}劃分:因?yàn)閒(3,a)=3,f(4,a)=3,f(3,b)=4,f(4,b)=4,故3,4屬于同一狀態(tài)集,所以S2不能劃分,也就是說(shuō)狀態(tài)3和4等價(jià)。至此,不再能繼續(xù)劃分01234bbbaaabaab例4.3.10:對(duì)下圖DFA進(jìn)行化簡(jiǎn)。解:首先將狀態(tài)集合分成非終止?fàn)顟B(tài)集S1和終止?fàn)顟B(tài)集S2,即S1={0,1,2};S2={3,4}第53頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月四、DFA的化簡(jiǎn)最終得到不能劃分的狀態(tài)集有:

S2={3,4},S4={1},S5={0},S6={2}每個(gè)狀態(tài)集留一個(gè)狀態(tài)得:S2={3},S4={1},S5={0},S6={2}所以化簡(jiǎn)后的DFA如下圖所示0123bbbaaaab

化簡(jiǎn)后的DFA第54頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月四、DFA的化簡(jiǎn)∏0:{A,B,C},{D,E,F,G}∏1:{A,B,C}

∏2:

a{A,C},{B}{D,E,F,G}b{A},{C}aDCBAaaabbbb例4.3.11:對(duì)例4.3.9的DFA進(jìn)行化簡(jiǎn)。至此,不能再進(jìn)行劃分,所得狀態(tài)集為{A},{S},{B},{C,D,E,F},每個(gè)狀態(tài)集留一個(gè)狀態(tài)后得到化簡(jiǎn)后的DFA如右圖所示DECBFGAbaaaaaabbbbbba第55頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性表現(xiàn)在以下兩個(gè)方面:

1.對(duì)于∑上的一個(gè)正規(guī)式R,可以構(gòu)造一個(gè)∑上的NFAN,使的L(N)=L(R)。2.對(duì)于∑上的一個(gè)NFAN,可以構(gòu)造一個(gè)∑上的正規(guī)式R,使得L(R)=L(N)。4.4正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性第56頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.4.1為∑上的正規(guī)式R構(gòu)造相應(yīng)的NFAM“語(yǔ)法制導(dǎo)”構(gòu)造方法首先將正規(guī)式分解成一系列子表達(dá)式,然后按下列規(guī)則來(lái)構(gòu)造NFAM:1)基本正規(guī)式Φ,ε,a(a∈∑)對(duì)應(yīng)的NFA為:圖4.4.1Φ,ε,a對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖SSSaεS1ZS1ZS1Z第57頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月2)連接:設(shè)R1和R2都是正規(guī)式,則構(gòu)造與正則表達(dá)式R1R2等價(jià)的NFA如圖4.4.2:

4.4.1為∑上的正規(guī)式R構(gòu)造相應(yīng)的NFAM圖4.4.2R1.R2的狀態(tài)轉(zhuǎn)換圖3)選擇:設(shè)R1和R2都是正規(guī)式,則構(gòu)造與正則表達(dá)式R1|R2等價(jià)的NFA如圖4.4.3:

圖4.4.3R1|R2的狀態(tài)轉(zhuǎn)換圖SS1R1R2

SS1S1R1

R2

S1ZS1ZSS1R1|R2

SS1R1

R2

S1ZS1Z第58頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.4.1為∑上的正規(guī)式R構(gòu)造相應(yīng)的NFAM4)重復(fù):設(shè)R是正規(guī)式,則構(gòu)造與正規(guī)式R*等價(jià)的NFA如圖4.4.4

圖4.4.4R*的狀態(tài)轉(zhuǎn)換圖

對(duì)于任何正規(guī)式,都可根據(jù)上述規(guī)則構(gòu)造出等價(jià)的NFA

SS1R*

SS1S1ε

ε

RS1ZS1Z第59頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.4.1為∑上的正規(guī)式R構(gòu)造相應(yīng)的NFAM例4.4.1構(gòu)造出與正規(guī)式R=(a)*(ε|b)(a|b)*等價(jià)的NFA。解:設(shè)初始狀態(tài)為0,目標(biāo)狀態(tài)為1,將整個(gè)正則表達(dá)式(a)*(ε|bb)(a|b)*

看成一個(gè)整體,則狀態(tài)圖如圖4.4.5所示01(a)*(ε|bb)(a|b)*圖4.4.5正規(guī)式到NFA轉(zhuǎn)換圖1

因R由(a)*,(ε|bb),(a|b)*連接而成,故展開(kāi)連接后如圖4.4.6

02(a)*31ε|bb

(a|b)*

圖4.4.6正規(guī)式到NFA轉(zhuǎn)換圖2第60頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.4.1為∑上的正規(guī)式R構(gòu)造相應(yīng)的NFAM將重復(fù)展開(kāi)后如圖4.4.7所示02ε31ε|bb

a|b

45εεa

ε圖4.4.7正規(guī)式到NFA轉(zhuǎn)換圖3將選擇展開(kāi)后,最終得到的NFA狀態(tài)圖如圖4.4.8所示

圖4.4.8正規(guī)式到NFA轉(zhuǎn)換圖4

02ε31ε

a45εεa

ε6b

b

b第61頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月例4.4.2:構(gòu)造正規(guī)式(0|1)*(000|111)(0|1)*對(duì)應(yīng)的NFA,并對(duì)其進(jìn)行化簡(jiǎn)。第62頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.4.1將NFAM變?yōu)橄鄳?yīng)的正規(guī)式R由NFAM構(gòu)造正規(guī)式相對(duì)較容易,處理方法與根據(jù)正規(guī)式構(gòu)造NFAM的方法互逆。具體如下:1

添加兩個(gè)新的結(jié)點(diǎn)S和T,將S與NFAM上的所有初態(tài)結(jié)點(diǎn)相連,將T與所有終態(tài)結(jié)點(diǎn)相連,所有連接弧線上均標(biāo)記為ε,從而使NFAM只有一個(gè)初態(tài)S和一個(gè)終態(tài)T。2逐步去掉NFAM中的結(jié)點(diǎn),直到只剩下結(jié)點(diǎn)S和T。在去掉結(jié)點(diǎn)的過(guò)程中,逐步用正則表達(dá)式來(lái)標(biāo)記弧線。去掉結(jié)點(diǎn)的規(guī)則如下:①連接:設(shè)R1和R2都是基本正則表達(dá)式,去掉結(jié)點(diǎn),用弧線直接連接結(jié)點(diǎn)1和3,弧線上標(biāo)記R1R2,如圖4.4.9所示:

13R1R2

123R1

R2

圖4.4.9由NFA構(gòu)造正則表達(dá)式R1R2

第63頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.4.1將NFAM變?yōu)橄鄳?yīng)的正規(guī)式R②選擇:設(shè)R1和R2都是正規(guī)式,去掉標(biāo)記為R1和R2的弧線并用一根弧線直接連接結(jié)點(diǎn)1和2,弧線上標(biāo)記R1|R2。③重復(fù):設(shè)R是正規(guī)式,則構(gòu)造與R*等價(jià)的NFA如圖4.4.11

圖4.4.10由NFA構(gòu)造正規(guī)式R1|R2

12R1|R2

12R1

R2

13R*

123ε

ε

R圖4.4.11由NFA構(gòu)造正規(guī)式R*

例題4.4.1的逆過(guò)程即可作為此處實(shí)例來(lái)學(xué)習(xí)第64頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.5

正規(guī)文法和有窮自動(dòng)機(jī)的等價(jià)性從正規(guī)文法G直接構(gòu)造一NFAN取N的字母表和G的終結(jié)符集相同。為G的每個(gè)非終結(jié)符生成N中的一狀態(tài),G的開(kāi)始符對(duì)應(yīng)N的開(kāi)始狀態(tài)。增加一個(gè)新?tīng)顟B(tài)Z作為NFA的終態(tài)。對(duì)G中形如AtB的規(guī)則,構(gòu)造一轉(zhuǎn)換函數(shù)f(A,t)=B對(duì)G中形如At的規(guī)則,構(gòu)造一轉(zhuǎn)換函數(shù)f(A,t)=Z反復(fù)使用上述規(guī)則對(duì)文法G中的規(guī)則進(jìn)行替換即可得到等價(jià)的NFAN。第65頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.5

正規(guī)文法和有窮自動(dòng)機(jī)的等價(jià)性例題1:第66頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月從NFAN構(gòu)造正規(guī)文法G對(duì)轉(zhuǎn)換函數(shù)f(A,t)=B,可寫一產(chǎn)生式AtB對(duì)可接受狀態(tài)Z,增加一產(chǎn)生式Zε有窮自動(dòng)機(jī)的初態(tài)對(duì)應(yīng)文法開(kāi)始符,字母表為文法的終結(jié)符集。4.5

正規(guī)文法和有窮自動(dòng)機(jī)的等價(jià)性第67頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月例題2:4.5

正規(guī)文法和有窮自動(dòng)機(jī)的等價(jià)性第68頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.6

詞法分析程序的構(gòu)造根據(jù)DFA構(gòu)造詞法分析程序的方法直接編程的方法表驅(qū)動(dòng)的實(shí)現(xiàn)方法借助自動(dòng)生成器Lex的構(gòu)造方法第69頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月1.

直接編程的詞法分析器直接編程的詞法分析器是將DFA識(shí)別過(guò)程轉(zhuǎn)化為程序,即用程序來(lái)模擬DFA的行為??砂聪铝胁襟E將DFA轉(zhuǎn)換成程序流程圖:1)初始狀態(tài)對(duì)應(yīng)程序的開(kāi)始;2)

終止?fàn)顟B(tài)對(duì)應(yīng)程序的結(jié)束3)

狀態(tài)轉(zhuǎn)移對(duì)應(yīng)條件語(yǔ)句或分支選擇語(yǔ)句;4)

狀態(tài)圖的環(huán)對(duì)應(yīng)程序中循環(huán)語(yǔ)句;5)

終態(tài)返回時(shí),應(yīng)滿足最長(zhǎng)匹配原則。4.6.1根據(jù)DFA構(gòu)造詞法分析程序的方法第70頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.6.1根據(jù)DFA構(gòu)造詞法分析程序的方法這種方法適合手工實(shí)現(xiàn),編寫出的詞法分析程序比較精簡(jiǎn),分析速度快。但這種詞法分析程序與要識(shí)別的語(yǔ)言單詞密切有關(guān),通過(guò)程序的控制流轉(zhuǎn)移來(lái)完成對(duì)輸入字符的響應(yīng),程序中的每一條語(yǔ)句都與要識(shí)別的單詞符號(hào)有關(guān),一但語(yǔ)言的單詞符號(hào)集發(fā)生變化,則要重新編寫程序。故這種方法僅適合編寫比較簡(jiǎn)單的詞法分析程序。

第71頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.6.1根據(jù)DFA構(gòu)造詞法分析程序的方法2.表驅(qū)動(dòng)的詞法分析程序

表驅(qū)動(dòng)的詞法分析程序的模型如圖4.6.1所示。它由輸入字符序列、分析表和控制程序組成。分析表就是DFA的狀態(tài)轉(zhuǎn)換矩陣,如圖4.6.2。控制程序有兩個(gè)參數(shù),一個(gè)參數(shù)接受掃描的字符a,另一個(gè)參數(shù)為DFA的狀態(tài)i。輸入字符序列分析表控制程序圖4.6.1表驅(qū)動(dòng)的詞法分析程序的模型

Σ狀態(tài)01S*BAACSBSCCAB圖4.6.2分析表

第72頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.6.1根據(jù)DFA構(gòu)造詞法分析程序的方法

其控制程序的算法是:1)

在輸入字符序列后面加一個(gè)字符‘#’,叫結(jié)束符。將掃描指針設(shè)在輸入序列的最左端,狀態(tài)參數(shù)i設(shè)為開(kāi)始狀態(tài)。2)

掃描下一字符a,如果是結(jié)束符‘#’,則停止;否則,根據(jù)狀態(tài)參數(shù)i和輸入的字符a查分析表,將狀態(tài)參數(shù)i設(shè)為查分析表(i,a)后得到的狀態(tài)。3)

如果i是終態(tài),則表示識(shí)別出一個(gè)單詞轉(zhuǎn)到4;否則轉(zhuǎn)到2。4)處理識(shí)別出的單詞,輸出單詞符號(hào)。狀態(tài)參數(shù)i設(shè)為開(kāi)始狀態(tài),轉(zhuǎn)到2。第73頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.6.1根據(jù)DFA構(gòu)造詞法分析程序的方法表驅(qū)動(dòng)的詞法分析程序是根據(jù)分析表的內(nèi)容進(jìn)行操作,與要識(shí)別的單詞符號(hào)無(wú)關(guān),是一種典型的數(shù)據(jù)與操作分離的工作模式。構(gòu)造不同的詞法分析程序?qū)嵸|(zhì)上是構(gòu)造不同的分析表,而控制程序是不變的。這為詞法分析程序的自動(dòng)生成提供了極大的方便。表驅(qū)動(dòng)的詞法分析程序相對(duì)直接編程方法來(lái)說(shuō),程序較復(fù)雜。由于在工作中需要查表確定分析動(dòng)作,因此分析速度也慢一些。第74頁(yè),課件共81頁(yè),創(chuàng)作于2023年2月4.

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(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)論