第二章 詞法分析2-DFA

第二章詞法分析2

確定有限自動機(jī)DFA確定有限自動機(jī)（DFA）的定義DFA的兩種表示方法DFA接受的集合DFA的確定性用DFA描述單詞自動機(jī)的實現(xiàn)有限自動機(jī)FA（FiniteAutomata)

有限自動機(jī)FA作為一種識別裝置，它能準(zhǔn)確識別正規(guī)集，即識別正規(guī)表達(dá)式所表示的語言，引入FA這個理論，正是為詞法分析程序的自動構(gòu)造尋找一種特殊的方法和工具。確定有限自動機(jī)（DFA：DeterministicFiniteAutomata)

非確定有限自動機(jī)（NFA：NondeterministicFiniteAutomata)

1確定有限自動機(jī)的定義確定有限自動機(jī)M為一個五元組:M=(S,,S0,f,Z)，其中：S是一個有窮狀態(tài)集，它的每個元素稱為一個狀態(tài)；是一個有窮字母表，它的每個元素稱為一個輸入字符；S0S，是唯一的一個初始狀態(tài)(開始狀態(tài))；f是狀態(tài)轉(zhuǎn)換函數(shù):SS，且單值函數(shù).f(Si,a)=Sk

表示：當(dāng)前狀態(tài)為Si，遇輸入字符a時，自動機(jī)將唯一地轉(zhuǎn)換到狀態(tài)Sk，稱Sk為Si的一個后繼狀態(tài);ZS，是終止?fàn)顟B(tài)集（可接受狀態(tài)集、結(jié)束狀態(tài)集），其中的每個元素稱為終止?fàn)顟B(tài)（可接受狀態(tài)、結(jié)束狀態(tài)）,Z可空.一個DFA的例子DFAM=({S0,S1,S2,S3},{a,b},f,S0,{S3}),其中f定義為：

f(S0,a)=S1f(S2,a)=S1f(S0,b)=S2f(S2,b)=S3f(S1,a)=S3f(S3,a)=S3f(S1,b)=S2f(S3,b)=S32DFA的兩種表示方式

a.狀態(tài)轉(zhuǎn)換圖：用有向圖表示自動機(jī)1.結(jié)點表示狀態(tài)：1)

非終止?fàn)顟B(tài)由單圓圈圍住的狀態(tài)標(biāo)識來表示;2）

終止?fàn)顟B(tài)由雙圓圈圍住的狀態(tài)標(biāo)識來表示;3）開始狀態(tài)由一個箭頭指向的狀態(tài)結(jié)點來表示.2.狀態(tài)轉(zhuǎn)換函數(shù)用有向邊來表示，若f(Si,a)=Sk，則由表示Si的狀態(tài)節(jié)點到表示Sk的狀態(tài)節(jié)點發(fā)出一條標(biāo)識為a的有向邊.DFAM=({S0,S1,S2,S3},{a,b},f,S0,{S3}),其中f定義為：

f(S0,a)=S1f(S2,a)=S1f(S0,b)=S2f(S2,b)=S3f(S1,a)=S3f(S3,a)=S3f(S1,b)=S2f(S3,b)=S3狀態(tài)轉(zhuǎn)換圖S1S0S2S3aababab,bb.狀態(tài)轉(zhuǎn)換矩陣：用二維數(shù)組描述DFA轉(zhuǎn)換矩陣的行表示確定有限自動機(jī)的狀態(tài);標(biāo)識初始狀態(tài)和終止?fàn)顟B(tài)：一般約定，第一行表示開始狀態(tài)S0

，或在右上角標(biāo)注“+”；右上角標(biāo)有“*”或“-”的狀態(tài)為終止?fàn)顟B(tài)；轉(zhuǎn)換矩陣的列表示確定有限自動機(jī)的輸入字符；矩陣元素表示確定有限自動機(jī)的狀態(tài)轉(zhuǎn)換函數(shù).DFAM=({S0,S1,S2,S3},{a,b},f,S0,{S3}),其中f定義為：

f(S0,a)=S1f(S2,a)=S1f(S0,b)=S2f(S2,b)=S3f(S1,a)=S3f(S3,a)=S3f(S1,b)=S2f(S3,b)=S3

輸入字符狀態(tài)abS0+S1,S2S1S3S2S2S1,S3S3*S3S33DFA接受的字符串對于中的任何字符串t,若存在一條從初始結(jié)點到某一終止結(jié)點的路徑，且這條路上所有弧上的標(biāo)記符連接成的字符串等于t,則稱t可為DFAM所接受（識別）.注意路徑中可以多次經(jīng)過終止?fàn)顟B(tài).若DFAM的初始狀態(tài)同時又是終止?fàn)顟B(tài)，則空字符串可為DFAM所接受（識別）.DFAM所能接受的字符串的全體記為L(M).

例1：L(M1)={aba,abaa,abab,abaab,…}0123abaa,b

例2：L(M2)={a,ab,abb,abbb,…}DFAM201ab

例3：L(M3)={,b,bb,bbb,…}DFAM31b4陷阱狀態(tài)例4:設(shè)有DFAM=（{0,1,2,3},{a,b,c},f,{0},{3}）其中f定義為：

f(0,a)=1f(0,b)=4f(1,a)=4f(1,b)=2 f(2,a)=3f(2,b)=4 f(3,a)=3f(3,b)=3 f(4,a)=4f(4,b)=401

23abaa,b4a,babb01

23abaa,bΣS

ab0+11223

3*334444445DFA的確定性初始狀態(tài)唯一.狀態(tài)轉(zhuǎn)換函數(shù)f:SS是一個單值函數(shù)，也就是說，對任何狀態(tài)sS,和輸入符號a,f(S,a)唯一地確定了下一個狀態(tài)，即至多確定一個狀態(tài).沒有空邊，即不接受沒有任何輸入就進(jìn)行狀態(tài)轉(zhuǎn)換（沒有輸入為的情況）。標(biāo)識符的描述L表示所有字母,L=[a-zA-Z]D表示數(shù)字，D=[0-9]則有：01LL|D6DFA描述單詞常數(shù)的描述D1=[1-9],D=[0-9]無符號整數(shù)帶符號整數(shù)實數(shù)01D1D320405..6DD.+|-D1特殊符號01{2+3EOF7DFA的兩種程序?qū)崿F(xiàn)方法_1直接轉(zhuǎn)向法：狀態(tài)轉(zhuǎn)換圖的形式每個狀態(tài)對應(yīng)一個帶標(biāo)號的switch語句例：ijkabLi:switch(CurChar){case‘a(chǎn)’： goto

Lj;case‘b’: goto

Lk;case‘Eof’: Accept;default:Error();}7DFA的兩種程序?qū)崿F(xiàn)方法_1直接轉(zhuǎn)向法：狀態(tài)轉(zhuǎn)換圖的形式每個狀態(tài)對應(yīng)一個帶標(biāo)號的switch語句例：ijkab特點：程序長但占用存儲空間少while((curChar=getchar())!=Eof)

switch(state)case1:……break;……casei:

switch(curChar){case‘a(chǎn)’：state=j;break;case‘b’:state=k;break;default:Error();}break;casej:……狀態(tài)轉(zhuǎn)換矩陣的形式：

state=S0;

curChar=readNextChar();

while(curChar!=eof&&T[state,curchar]error)

{//則當(dāng)前狀態(tài)轉(zhuǎn)為新的狀態(tài)state

=T[state,curChar];

curChar=readNextChar()；

}

if(curChar==eof&&stateFinalState)return(1);elsereturn(0);特點：程序短小，但占用存儲空間多.7DFA的兩種程序?qū)崿F(xiàn)方法_2練習(xí)1設(shè)計DFA以識別所有能被3整除的無符號