第四章詞法分析

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

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

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

字符串源程序詞法分析器

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

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

多數(shù)程序設(shè)計語言的單詞的語法均可用正規(guī)文法來表示?；仡櫍赫?guī)文法(3型文法)：任一產(chǎn)生式的形式都為A→aB或A→a，其中A∈VN

，B∈VN

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

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

2)正規(guī)式R1.R2或R1R2表示的正規(guī)集為L1L2

3)正規(guī)式{R1}或R1*表示的正規(guī)集為L1*

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

第11頁，課件共81頁，創(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,……任意個a的串}(6){

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

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

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

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

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

,它表示的正規(guī)集中的每個元素的模式是“字母打頭的字母數(shù)字串”,即Pascal和多數(shù)程序設(shè)計語言允許的的標(biāo)識符的詞法規(guī)則.第13頁，課件共81頁，創(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頁，課件共81頁，創(chuàng)作于2023年2月一個正規(guī)語言可用正規(guī)文法表示也可用正規(guī)式表示，兩者具有等價性。一般而言正規(guī)式在描述語言時比正規(guī)文法更為簡潔。正規(guī)文法和正規(guī)式的等價性例如，用正規(guī)文法表示標(biāo)識符的文法規(guī)則如下：＜標(biāo)識符＞

a|b|…|z|＜標(biāo)識符＞a|＜標(biāo)識符＞b|…|＜標(biāo)識符＞z|＜標(biāo)識符＞0|＜標(biāo)識符＞1|…|＜標(biāo)識符＞9而采用正規(guī)表達(dá)式則為：＜標(biāo)識符＞=

(a|b|c|…|z){a|b|…|z|0|1|…|9}或簡寫成＜標(biāo)識符＞=字母{字母|數(shù)字}第15頁，課件共81頁，創(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的識別符。若x,y是正規(guī)式，對形如Axy的正規(guī)式產(chǎn)生式，重寫成：AxB,By，B為新選的非終結(jié)符。對形如Ax*y的正規(guī)式，重寫成:AxB,Ay,BxB,By，B為新選的非終結(jié)符。對形如Ax|y的正規(guī)式，重寫成:Ax,Ay。不斷利用上述規(guī)則做變換，直到每個產(chǎn)生式都符合正規(guī)文法的形式即可。正規(guī)文法和正規(guī)式的等價性第16頁，課件共81頁，創(chuàng)作于2023年2月例4.2.3：將r=a(a|d)*轉(zhuǎn)換成相應(yīng)的正規(guī)文法正規(guī)文法和正規(guī)式的等價性第17頁，課件共81頁，創(chuàng)作于2023年2月將正規(guī)文法轉(zhuǎn)換為正規(guī)式基本上是正規(guī)式到正規(guī)文法轉(zhuǎn)換過程的逆過程?？煞磸?fù)采用以下三條規(guī)則，直到只剩下一個開始符號定義的正規(guī)式為止。產(chǎn)生式AxB,By對應(yīng)正規(guī)式A=xy;產(chǎn)生式AxA|y對應(yīng)正規(guī)式A=x*y;產(chǎn)生式Ax,Ay對應(yīng)正規(guī)式A=x|y;正規(guī)文法和正規(guī)式的等價性第18頁，課件共81頁，創(chuàng)作于2023年2月例4.2.4:

將G[S]轉(zhuǎn)換為正規(guī)式SaASaAaAAdAAaAd正規(guī)文法和正規(guī)式的等價性解：由文法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頁，課件共81頁，創(chuàng)作于2023年2月4.3有窮自動機(jī)

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

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

不確定的有窮自動機(jī)(NondeterministicFiniteAutomata:NFA)第20頁，課件共81頁，創(chuàng)作于2023年2月4.3關(guān)于有窮自動機(jī)將主要討論如下問題確定的有窮自動機(jī)DFA不確定的有窮自動機(jī)NFANFA的確定化DFA的最小化第21頁，課件共81頁，創(chuàng)作于2023年2月一、確定的有窮自動機(jī)DFADFA定義:一個確定的有窮自動機(jī)（DFA）M是一個五元組:M=(K,Σ,f,S,Z),其中1.K是一個有窮集，它的每個元素稱為一個狀態(tài)；2.Σ是一個有窮字母表，它的每個元素稱為一個輸入符號，所以Σ也稱為輸入符號表；第22頁，課件共81頁，創(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時，將轉(zhuǎn)換為下一個狀態(tài)kj，我們把kj稱作ki的一個后繼狀態(tài)；4.S∈K是唯一的一個初態(tài)；5.Z

K是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。一、確定的有窮自動機(jī)DFA第23頁，課件共81頁，創(chuàng)作于2023年2月一、確定的有窮自動機(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頁，課件共81頁，創(chuàng)作于2023年2月上例中DFA的狀態(tài)圖表示bSUVQaaaba，bb一、確定的有窮自動機(jī)DFA第25頁，課件共81頁，創(chuàng)作于2023年2月上例中DFA的矩陣表示字符狀態(tài)0001一、確定的有窮自動機(jī)DFA第26頁，課件共81頁，創(chuàng)作于2023年2月概念：∑*上的符號串t被DFAM接受一、確定的有窮自動機(jī)DFA定義1:對∑*中的任何符號串t，若存在一條從初態(tài)結(jié)點(diǎn)某一終態(tài)結(jié)點(diǎn)的道路，且這條道路上所有弧連接成的符號串等于t，則稱t可為DFAM所接受，若M的初態(tài)同時又是終態(tài)結(jié)點(diǎn)，則空字可為M所接受。定義2:若t∈∑*,f(S,t)=P，其中S為DFAM的開始狀態(tài),P∈Z,Z為終態(tài)集,則稱t可為M所接受(識別)。DFAM所能接受的符號串的全體記為L(M)。DFA的確定性表現(xiàn)在f:K×

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

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

概念：∑*上的符號串t被DFAM上運(yùn)行上一個符號串集V

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

，使得V=L(M)。第28頁，課件共81頁，創(chuàng)作于2023年2月一、確定的有窮自動機(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頁，課件共81頁，創(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’)一、確定的有窮自動機(jī)DFA第30頁，課件共81頁，創(chuàng)作于2023年2月二、不確定的有窮自動機(jī)NFA

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

到K的子集的映射，SK是一個非空初態(tài)集，ZK為終態(tài)集。NFA與DFA的區(qū)別主要有:NFA中狀態(tài)轉(zhuǎn)換函數(shù)為多值函數(shù)。NFA中起始狀態(tài)可以有多個，但從正規(guī)文法出發(fā)構(gòu)造的NFA起始狀態(tài)是唯一的。第31頁，課件共81頁，創(chuàng)作于2023年2月二、不確定的有窮自動機(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頁，課件共81頁，創(chuàng)作于2023年2月矩陣表示簡化為二、不確定的有窮自動機(jī)NFA第33頁，課件共81頁，創(chuàng)作于2023年2月

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

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

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

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

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

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

f:K

K的子集

f:K*

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

若將NFAN所能接受的符號串的全體記為L(N)，則有如下結(jié)論：對每個NFAN存在著與之等價的DFAM，使得L(M)=L(N)。并且最小的DFAM是唯一的。將NFA轉(zhuǎn)換成等價的DFA的算法---子集法。二、不確定的有窮自動機(jī)NFA第38頁，課件共81頁，創(chuàng)作于2023年2月有關(guān)狀態(tài)集合I的兩個運(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)過一條a弧而到達(dá)的狀態(tài)的全體。三、NFA的確定化

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

a三、NFA的確定化

有關(guān)狀態(tài)集合I的運(yùn)算實例計算下列各式的值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頁，課件共81頁，創(chuàng)作于2023年2月三、NFA的確定化

子集法:

假設(shè)NFAN=(K,,f,K0,Kt)，按如下方法可構(gòu)造一個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ī)則排列的，即對于子集{S1,S2}={S2,S1,}來說，S的狀態(tài)就是[S1,S2]；第41頁，課件共81頁，創(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的開始狀態(tài)；5St={[Si,Sk,...,

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

Se]S

且{Si,Sk,,...,

Se}Kt

}三、NFA的確定化第42頁，課件共81頁，創(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每個輸入字母ado {U:=-closure(move(T,a))；

ifU不在CS中then

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

} }三、NFA的確定化

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

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

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

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

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

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

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

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

化簡后的DFA第54頁，課件共81頁，創(chuàng)作于2023年2月四、DFA的化簡∏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:對例4.3.9的DFA進(jìn)行化簡。至此，不能再進(jìn)行劃分，所得狀態(tài)集為{A},{S},{B},{C,D,E,F}，每個狀態(tài)集留一個狀態(tài)后得到化簡后的DFA如右圖所示DECBFGAbaaaaaabbbbbba第55頁，課件共81頁，創(chuàng)作于2023年2月正規(guī)式和有窮自動機(jī)的等價性表現(xiàn)在以下兩個方面：

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

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

SS1S1R1

R2

S1ZS1ZSS1R1|R2

SS1R1

R2

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

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

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

SS1R*

SS1S1ε

ε

RS1ZS1Z第59頁，課件共81頁，創(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)*等價的NFA。解：設(shè)初始狀態(tài)為0，目標(biāo)狀態(tài)為1，將整個正則表達(dá)式(a)*(ε|bb)(a|b)*

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

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

02(a)*31ε|bb

(a|b)*

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

a|b

45εεa

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

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

02ε31ε

a45εεa

ε6b

b

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

添加兩個新的結(jié)點(diǎn)S和T，將S與NFAM上的所有初態(tài)結(jié)點(diǎn)相連，將T與所有終態(tài)結(jié)點(diǎn)相連，所有連接弧線上均標(biāo)記為ε，從而使NFAM只有一個初態(tài)S和一個終態(tài)T。2逐步去掉NFAM中的結(jié)點(diǎn)，直到只剩下結(jié)點(diǎn)S和T。在去掉結(jié)點(diǎn)的過程中，逐步用正則表達(dá)式來標(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頁，課件共81頁，創(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*等價的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的逆過程即可作為此處實例來學(xué)習(xí)第64頁，課件共81頁，創(chuàng)作于2023年2月4.5

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

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

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

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

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

直接編程的詞法分析器直接編程的詞法分析器是將DFA識別過程轉(zhuǎn)化為程序，即用程序來模擬DFA的行為?？砂聪铝胁襟E將DFA轉(zhuǎn)換成程序流程圖：1)初始狀態(tài)對應(yīng)程序的開始；2)

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

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

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

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

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

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

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

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

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

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

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

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