第三章 詞法分析及有窮自動(dòng)機(jī)

編譯原理第三章詞法分析及有窮自動(dòng)機(jī)

主要內(nèi)容

●詞法分析程序的設(shè)計(jì)過程?！衩枋鰡卧~的文法：正規(guī)文法和正規(guī)式及它們之間的轉(zhuǎn)換?！駟卧~識(shí)別機(jī)制（有窮自動(dòng)機(jī)）?！裾?guī)式，正規(guī)文法和有窮自動(dòng)機(jī)三者之間相互轉(zhuǎn)換?！?.詞法分析程序的任務(wù)一、詞法分析程序的任務(wù)及處理方式

1.詞法分析程序的任務(wù)主要任務(wù)：從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)單詞序列，用以語法分析。詞法分析程序（掃描程序）：執(zhí)行詞法分析的程序。2.詞法分析程序的處理方式詞法分析程序與語法分析程序接口方式有兩種：第一種方式： 將詞法分析作為單獨(dú)一遍掃描，即在語法分析之前，實(shí)現(xiàn)源程序的詞法分析工作。其輸出（單詞串）形成一個(gè)中間文件（內(nèi)部形式的源程序表），然后移交給語法分析程序。第二種方式：將詞法分析程序編寫成一個(gè)子程序，每當(dāng)語法分析程序需要讀一個(gè)新單詞時(shí)，便去調(diào)用它。

注：后一種方式比較好。因?yàn)椴恍枰趦?nèi)存中構(gòu)造和保存中間文件。二、詞法分析程序的I/O1.輸入 字符串表示的源程序

2.輸出 單詞符號(hào)序列或單詞符號(hào)。

1)程序語言的單詞符號(hào)單詞：指語言中具有獨(dú)立意義的最小語法單位。語言中的單詞符號(hào)：一般可歸結(jié)為五種：保留字（基本字）：如if,for,and等――個(gè)數(shù)確定標(biāo)識(shí)符：表示常量、變量、類型、過程等名稱――個(gè)數(shù)不確定常數(shù)：如34，-0.37等――個(gè)數(shù)不確定運(yùn)算符：如+，-，*，/，<等――個(gè)數(shù)確定界線符：如逗號(hào)，分號(hào)，括號(hào)等――個(gè)數(shù)確定注：·保留字，運(yùn)算符，界線符可列表，供詞法分析程序查詢；

·標(biāo)識(shí)符和常數(shù)可用正規(guī)文法或正規(guī)式描述，供詞法分析程序識(shí)別。2)輸出的單詞形式二元組：（單詞的種別碼，單詞自身值）

1o

單詞的種別碼：表示單詞的種類分類的原則：處理簡單分類的方法：使每一個(gè)單詞對(duì)應(yīng)一個(gè)整數(shù)碼分類的目的：最大限度地區(qū)別各個(gè)單詞 單詞地分類法有多種：一種一類一字一類或一符一類具體：保留字：一字一種。如：

if 1 then2

。。。標(biāo)識(shí)符：統(tǒng)歸一種。常數(shù)：整數(shù)，實(shí)數(shù)，布爾統(tǒng)為一種或按類型分整數(shù) 11實(shí)數(shù) 12布爾 13

或全體一種+ 29 :=17= 21- 14<>18>=22* 15<19>23/ 16<=20…運(yùn)算符：+，-，*，/，>，<等統(tǒng)為一種；或一符一種：

2o

單詞自身值（可有可無） 單詞自身值是單詞的機(jī)內(nèi)代碼或者單詞在表格中的地址碼。如：標(biāo)識(shí)符：自身的字符串（1，’a’）常數(shù)：自身的二進(jìn)制數(shù)（11，’100’的二進(jìn)制數(shù)）例：一種一類的單詞輸出形式 設(shè)保留字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符、分界符的種別碼分別為1，2，3，4，5；將ifa>1thenb:=10表示為一種一類的單詞輸出形式。ifa>1thenb:=10＝>詞法分析器=>(1,’if’)(字符串表示的源程序)(2,’a’),(4,’>’)(3,’1’的二進(jìn)制數(shù))(1,’then’)(2,’b’)(4,’:=’)(3,’10’的二進(jìn)制數(shù))例：采用一字一類或一符一類地分類技術(shù)，則保留字單詞自身值可無，但事先構(gòu)造一個(gè)保留字單詞對(duì)照表，其值可在詞表中查到。ifa>1thenb:=10＝>詞法分析器=>(1,◎)字符串表示的源程序(10,‘a(chǎn)’)(23,◎)(3,’1’的二進(jìn)制數(shù))(2,◎)(10,’b’)(17,◎)(11,’10’的二進(jìn)制數(shù))上面符號(hào)◎表示要查保留詞表表2.1保留字單詞表單詞類別碼單詞類別碼...............If1+29Then2-14else3*15......

/16............>23for19:=17...§2.詞法分析程序的設(shè)計(jì)過程一、詞法分析程序的設(shè)計(jì)過程設(shè)計(jì)過程：詞法分析程序設(shè)計(jì)過程：①把有的單詞（如：標(biāo)識(shí)符和常數(shù)）用正規(guī)文法或正規(guī)式描述；②將正規(guī)文法或正規(guī)式轉(zhuǎn)換成等價(jià)的狀態(tài)轉(zhuǎn)換圖（最小化的DFA圖）；③根據(jù)狀態(tài)轉(zhuǎn)換圖設(shè)計(jì)詞法分析程序（狀態(tài)轉(zhuǎn)換圖可視為詞法分析程序的框圖）。轉(zhuǎn)換規(guī)則分裂法子集法狀態(tài)轉(zhuǎn)換圖（DFA圖）二、用狀態(tài)轉(zhuǎn)換圖設(shè)計(jì)詞法分析程序

1.詞法分析程序的預(yù)處理詞法分析程序在識(shí)別單詞前，需要對(duì)輸入到緩沖區(qū)的源程序進(jìn)行預(yù)處理。預(yù)處理：刪去無用的空格，跳格，回車和換行等編輯性字符；刪去注釋部分每次對(duì)一串定長（如120個(gè)字符）的輸入字符進(jìn)行預(yù)處理，并裝入一個(gè)指定的掃描緩沖區(qū)中。掃描緩沖區(qū)是一個(gè)一分為二的區(qū)域，每一個(gè)區(qū)域可容納120個(gè)字符，且相互交替使用。搜索指針從單詞起點(diǎn)開始搜索，如果遇到半?yún)^(qū)的邊界但尚未達(dá)到單詞的終點(diǎn)時(shí)，則可將后續(xù)的120個(gè)輸入字符裝進(jìn)緩沖區(qū)的另一半中。2.狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖是為了識(shí)別正規(guī)文法或正規(guī)式而專門設(shè)計(jì)的有向圖。他是有窮自動(dòng)機(jī)的非形式化表示。狀態(tài)轉(zhuǎn)換圖的組成：

1o

有限個(gè)狀態(tài)結(jié)點(diǎn)狀態(tài)結(jié)點(diǎn)代表正規(guī)文法的非終結(jié)符（用單圈表示）；開始狀態(tài)結(jié)點(diǎn)：用雙箭頭指示；終止?fàn)顟B(tài)結(jié)點(diǎn)：用雙圈表示。

2o弧線→弧上的標(biāo)記x指明在射出弧的結(jié)點(diǎn)狀態(tài)下可能出現(xiàn)的輸入字符或字符類,即終結(jié)符。(→表示機(jī)器的識(shí)別方向).大多數(shù)單詞結(jié)構(gòu)是用正規(guī)文法描述的x例：<標(biāo)識(shí)符>∷=<字母>|<標(biāo)識(shí)符><字母>|<標(biāo)識(shí)符><數(shù)字><整數(shù)>∷=<數(shù)字>|<整數(shù)><數(shù)字><運(yùn)算符>∷=+|-|*|/|….<界線符>∷=；|，|(|)|…..。。。3.由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖1)左線性正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖 左線性正規(guī)文法的一般形式：U∷=a|wa左線性正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖的步驟如下：增加一個(gè)開始狀態(tài)結(jié)點(diǎn)s（假定文法的詞匯表中不含s）；以每個(gè)非終結(jié)符為狀態(tài)作結(jié)點(diǎn)；對(duì)于形如U∷=a的每一個(gè)規(guī)則，引一條從開始狀態(tài)s到狀態(tài)U的弧，弧上標(biāo)記為a；

對(duì)于形如U∷=wa的每一個(gè)規(guī)則，引一條從狀態(tài)w到狀態(tài)U的弧，弧上標(biāo)記為a；以識(shí)別符號(hào)為終止?fàn)顟B(tài)。例：設(shè)有正規(guī)文法G[Z]：

Z∷=U0|V1 U∷=Z1|1 V∷=Z0|0（描述的語言為L(G)={01,10}）則狀態(tài)轉(zhuǎn)換圖如下：＋以開始符號(hào)Z作終態(tài)新增加開始狀態(tài)S例：標(biāo)識(shí)符的轉(zhuǎn)換圖：

從開始狀態(tài)出發(fā)到某一終止?fàn)顟B(tài)結(jié)點(diǎn)為止，所經(jīng)過的路徑上的符號(hào)串，稱能為該狀態(tài)轉(zhuǎn)換圖所接收（識(shí)別）的符號(hào)串。如：標(biāo)識(shí)符x26為上述轉(zhuǎn)換圖識(shí)別，識(shí)別路徑為2)

右線性正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖右線性正規(guī)文法U∷=a|aV構(gòu)造狀態(tài)轉(zhuǎn)換圖的步驟：增加一個(gè)終止?fàn)顟B(tài)結(jié)點(diǎn)z（假定文法的詞匯表中不含z）；以每個(gè)非終結(jié)符為狀態(tài)作結(jié)點(diǎn)；對(duì)于形如U∷=a的每一個(gè)規(guī)則，引一條從開始狀態(tài)U到終止?fàn)顟B(tài)z的弧，弧上標(biāo)記為a；對(duì)于形如U∷=aV的每一個(gè)規(guī)則，引一條從狀態(tài)U到狀態(tài)V的弧，弧上標(biāo)記為a；以識(shí)別符號(hào)為開始狀態(tài)。４．根據(jù)狀態(tài)轉(zhuǎn)換圖設(shè)計(jì)詞法分析程序狀態(tài)轉(zhuǎn)換圖實(shí)際上是編寫詞法分析程序的框圖根據(jù)狀態(tài)轉(zhuǎn)換圖寫出相應(yīng)的詞法分析程序的方法：

1o對(duì)于每個(gè)狀態(tài)構(gòu)造一小段程序。 功能：從輸入串中讀一個(gè)字符；判明讀入字符與由此狀態(tài)出發(fā)的哪條弧上的標(biāo)記匹配，便轉(zhuǎn)至相匹配的那條弧所指的狀態(tài)；均不匹配時(shí)便失?。ú荒苓_(dá)到正常出口）2o再根據(jù)圖形決定小段程序之間的調(diào)用。 注：詞法分析程序除了識(shí)別單詞外，還可為語法程序提供更多的信息。因此，可在這些小段程序中加上一些語義處理（如對(duì)數(shù)值進(jìn)行10=>2等）例：設(shè)有關(guān)于單詞<無符號(hào)數(shù)>的文法G=(VN,VT,P,N1)其中，VN={N1,N2,N3,N4,N5,N6,N7}VT={d,．,e,f,∧}P： N1∷=dN2|．N3|eN5 N2∷=dN2|．N3|eN5|∧ N3∷=dN4

這里d表示數(shù)字（0～9）；e＝10；f＝；∧表示空字符；N1表示無符號(hào)數(shù)，其一般形式為：d…d．d…defd…dN4∷=dN4|eN5|∧N5∷=dN7|fN6N6∷=dN7N7∷=dN7|∧試構(gòu)造識(shí)別此單詞的詞法分析程序1>根據(jù)右線性正規(guī)文法，畫出狀態(tài)轉(zhuǎn)換圖N1=>3N2=>34N2=>34·N3=>34·5N4

=>34·56N4=>34·56(達(dá)到出口),自上而下的推導(dǎo)過程。2>根據(jù)狀態(tài)轉(zhuǎn)換圖寫詞法分析程序?yàn)槊恳粋€(gè)狀態(tài)結(jié)點(diǎn)寫一個(gè)過程或函數(shù)：對(duì)N1結(jié)點(diǎn)：ProcedurePN1 Begin Ch:=getchar(); Ifch=”e”thenPN5 Elseifch=”d”thenPN2 Elseifch=”·”thenPN3 Elseerror End;對(duì)N2結(jié)點(diǎn)：ProcedurePN2 Begin Ch:=getchar(); Ifch=”e”thenPN5 Elseifch=”d”thenPN2 Elseifch=”·”thenPN3 Elsereturn; End;對(duì)N3,N4,N5,N6,N7結(jié)點(diǎn)分別寫出程序段：……§3正規(guī)式與有窮自動(dòng)機(jī)為了進(jìn)一步討論詞法分析程序的自動(dòng)生成，需要將狀態(tài)轉(zhuǎn)換圖的概念加以形式化；同時(shí)將由正規(guī)文法描述的單詞由正規(guī)式描述，可利用有窮自動(dòng)機(jī)生成詞法分析程序。一、正規(guī)式與正規(guī)集 語言的單詞結(jié)構(gòu)不僅由正規(guī)文法描述，還可以由正規(guī)式描述。例：<標(biāo)識(shí)符>∷=<字母>|<標(biāo)識(shí)符><字母>|<標(biāo)識(shí)符><數(shù)字>

此正規(guī)文法描述了一個(gè)語言的集合。定義在{字母，數(shù)字}上的以字母開頭的符號(hào)串的集合。這個(gè)集合還可以用正規(guī)式描述：字母(字母|數(shù)字)*。正規(guī)式描述的字符串的集合稱為正規(guī)集1．正規(guī)式（也稱正則式，正則表達(dá)式）和正規(guī)集的遞歸定義設(shè)有字母表∑={a1,a2,…,an},那么(1)ε,Φ,ai

都是∑上的正規(guī)式，它們所描述的正規(guī)集分別為{ε}，Φ，{ai}；(2)若e1和e2都是∑上的正規(guī)式，它們所描述的正規(guī)集L(e1)、L(e2)，則：1o正規(guī)式的“或”（|）運(yùn)算：

e1|e2也是正規(guī)式，相應(yīng)正規(guī)集為L(e1|e2)=L(e1)∪L(e2)；2o正規(guī)式的“連接”（.）運(yùn)算：e1e2也是正規(guī)式，相應(yīng)正規(guī)集為L(e1e2)=L(e1)L(e2)；3o正規(guī)式的“閉包”（*）運(yùn)算:(e1)*也是正規(guī)式，相應(yīng)正規(guī)集為

L((e1)*)=(L(e1))*；(3)僅由有限次使用(1),(2)定義的表達(dá)式才是∑上的正規(guī)式，由這些正規(guī)式所表示的字符集才是∑上的正規(guī)集。例：設(shè)∑={a,b}，則∑上的正規(guī)式和正規(guī)集有正規(guī)式正規(guī)集1o

a和baL(a)={a}和L(b)=L(a)=L(a)∪L(a)∪L(a)∪…={a}={a,aa,...}基本3oa|bL(a|b)=L(a)∪L(b)={a,b}4oabL(ab)=L(a)L(b)={ab}5oa*L(a*)=(L(a))*=L(a)∪L(a)∪L(a)∪….={a}*={ε,a,aa,aaa,..…}復(fù)合6oba*L(ba*)=L(b)L(a*)={b,ba,baa,baaa,……}7oa|ba*L(a|ba*)=L(a)∪L(ba*)={a,b,ba,baa,……}8o(a|b)*L((a|b)*)=(L(a|b))*={a,b}*={ε,a,b,aa,ab,……所有ab組成的串}9oa(a|b)*L(a(a|b)*)=L(a)(L(a)∪L(b))*={a}{a,b}*10o(a|b)*(aa|bb)(a|b)*L((a|b)*(aa|bb)(a|b)*)={a,b}*{aa,bb}{a,b}*012+123++2o注：.正規(guī)式僅由字母∑中的終結(jié)符號(hào)，通過或，連接和閉包三種運(yùn)算組成的式子。例：有字母表∑={a，b}，下面正規(guī)式，求正規(guī)集。

ba*正規(guī)集：b開頭后面跟0個(gè)或若干個(gè)a。

a(a|b)*正規(guī)集：a開頭后面跟0個(gè)或a、b任意排列。例：有字母表∑={a，b}，下面用自然語言描述的正規(guī)集，求正規(guī)式(可能不唯一)。以ab結(jié)尾的所有字符串。(a|b)*ab

包含偶數(shù)個(gè)b的所有字符串。(bb)*

只包含一個(gè)a的所有字符串。b*ab*

不包含ab子串的所有字符串。b*a*

以a開頭b結(jié)尾的所有字符串。a(a|b)*b２．正規(guī)式的性質(zhì)（1）正規(guī)式的等價(jià)性定義：若正規(guī)式e1與e2描述的正規(guī)集相同，即L(e1)=L(e2)，則e1與e2等價(jià)，記做e1=e2。（2）正規(guī)式的代數(shù)性質(zhì)設(shè)r,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：1or|s=s|r“或”滿足交換律2or|(s|t)=(r|s)|t“或”滿足結(jié)合律3o(rs)t=r(st)“連接”滿足結(jié)合律。

“連接”不滿足交換律4or(s|t)=rs|rt(s|t)r=sr|tr“連接”滿足分配律5oεr=rrε=r

ε

是“連接”的恒等元素(3)正規(guī)式的恒等式 設(shè)A和B式正規(guī)式，有例：證明：A*=ε|AA*成立。

證明:利用對(duì)應(yīng)的正規(guī)集來證明：

L(AA*|ε)=L(A)L(A*)UL(ε)=L(A)L(A)*UL(ε)=L(A)((L(A))UL((A))U(L(A))…..)UL(ε)=L(ε)U((L(A))U(L((A))U(L(A))…..)=(L(A)*)=L(A*)∴A*=AA*|ε例：設(shè)∑={d,．,e,+,-}則∑上的正規(guī)式：

d*(．dd*|ε)(e(+|-|ε)dd*|ε)表示無符號(hào)數(shù)：2.12,3.6e-2等。表示無符號(hào)數(shù)的正規(guī)式，比表示無符號(hào)數(shù)的正規(guī)文法顯得直觀，簡潔。1o（A*）*=A*2oA|BA=(ε|B)A3oAA*=A*A；A=AA*4oA*=ε|AA*;A*=(A|ε)*012312+3．正規(guī)文法與正規(guī)式的轉(zhuǎn)換關(guān)系：對(duì)任意一個(gè)正規(guī)文法存在定義同一語言的正規(guī)式反之：對(duì)于每一個(gè)正規(guī)式，存在一個(gè)生成同一語言的正規(guī)文法。兩者之間具有等價(jià)的轉(zhuǎn)換關(guān)系。 有的語言容易用正規(guī)文法定義，有的語言則更容易用正規(guī)式定義轉(zhuǎn)換：1o

正規(guī)式-——>正規(guī)文法將∑上的一個(gè)正規(guī)式轉(zhuǎn)換成正規(guī)文法G=(VN,VT,S,P)：首先：令VT=∑再確定產(chǎn)生式P和VN，其方法：

對(duì)任何正規(guī)式r，選擇非終結(jié)符S生成產(chǎn)生式S∷=r，并將S定義為G的識(shí)別符號(hào)。<a>若r含有正規(guī)式x,y,對(duì)形如A∷=xy（連接的變換）產(chǎn)生式，用A∷=xB,B∷=y兩個(gè)產(chǎn)生式替換。其中B是新選擇的非終結(jié)符。<b>對(duì)已經(jīng)轉(zhuǎn)換成文法中的形如：A∷=x*y

（閉包和連接的變換）的產(chǎn)生式，則重寫為：

A∷=xA

注：若y是ε則，A→xA A∷=yA→

ε<c>對(duì)形如：A∷=x|y

（或的變換）的產(chǎn)生式，重寫為A∷=x,A∷=y<d>不斷利用上述規(guī)則作變換，直到每個(gè)產(chǎn)生式右部最多含有一個(gè)終結(jié)符為止。例：將正規(guī)式R=a(a|d)*轉(zhuǎn)換成相應(yīng)的正規(guī)文法。解：令S是文法的識(shí)別符號(hào)，則首先形成：

S∷=a(a|d)*然后形成：

S∷=aA,A∷=(a|d)*(其中A∈VN)對(duì)于A∷=(a|d)*重寫為：

A∷=(a|d)A A∷=ε對(duì)于A∷=(a|d)A重寫成：A∷=aA,A∷=dA

最后轉(zhuǎn)換的等價(jià)正規(guī)文法G=(VN,VT,S,P) VT={a,d} VN={S,A} P:S∷=aA A∷=aA|dA|ε2o正規(guī)文法——>正規(guī)式 基本是上述的逆過程。最后只剩下一個(gè)識(shí)別符號(hào)定義的產(chǎn)生式，且產(chǎn)生式的右部不含非終結(jié)符。其轉(zhuǎn)換規(guī)則如下表：規(guī)則文法產(chǎn)生式正規(guī)式1A∷=xB,B∷=yA=xy2A∷=xA|yA=x*y3A∷=x,A∷=yA=x|y注：正規(guī)文法與正規(guī)式互相轉(zhuǎn)換，關(guān)鍵式：A→xA|yA=x*y例：正規(guī)文法G[s]：

S∷=aA S∷=a A∷=aA A∷=dA A∷=a A∷=d求正規(guī)式解：先有：S＝aA|a

規(guī)則3 A=(aA|dA)|(a|d) 規(guī)則3再將A的正則式變成：A=(a|d)A|(a|d) “或”分配律根據(jù)規(guī)則2變成：A=(a|d)*(a|d)再代入S的右部得：S=a(a|d)*(a|d)|a再利用正則式代數(shù)變換：

S=a((a|d)*(a|d)|ε) S=a(a|d)*

即：a(a|d)*為所求的正則式簡便轉(zhuǎn)換方法是:(1)將正規(guī)文法中的每一個(gè)非終結(jié)符表示成關(guān)于它的一個(gè)正規(guī)方程,獲得一個(gè)聯(lián)立方程組.(2)依據(jù)求解規(guī)則:若x∷=αx|β,寫成方程x=αx+β(“|”用“+”表示);則解為x=α*β.若x∷=xα|β,寫成方程x=xα+β(“|”用“+”表示);則解為x=βα*.以及正規(guī)式的分配律,交換律和結(jié)合律求關(guān)于文法識(shí)別符號(hào)的正規(guī)式方程組的解.此解就是關(guān)于文法識(shí)別符號(hào)S的一個(gè)正規(guī)式.例如,上例:先寫出正規(guī)式方程組(方程組中用“+”代替“|”): S∷=aA|a

寫成:S=aA+a……（1）

A∷=aA|dA|a|d

寫成:A=aA+dA+a+d……（2）將（2）式簡化為：A=(a+d)A+(a+d)使用求解規(guī)則：A=(a|d)*(a|d)……（3）將（3)的A代入（1)式：S=a(a|d)*(a|d)|a=a((a|d)*(a|d)|ε)∴a((a|d)*(a|d)|ε)=a(a|d)*即為所求的正規(guī)式。例：設(shè)有正規(guī)文法G:Z∷=0AA∷=0A|0BB∷=1A|ε試給出該文法的正規(guī)式。解：給出相應(yīng)的正規(guī)式方程組：

Z=0A……（1）

A=0A+0B……（2）

B=1A+ε……（3）（3）代入（2）中的B得：A=0A+01A+0=(0+01)A+0使用求解規(guī)則：A=(0|01)*0……（4）（4）代入（1）式中的A得：Z=0(0|01)*0所以，0(0|01)*0即為所求的正規(guī)式。例：設(shè)有正規(guī)文法G:P:{A::=aB|bB,B::=aC|a|b,C::=aB}相應(yīng)的正規(guī)式方程：A=aB+bB………（1）

B=aC+a+b………(2)C=aB……….(3)(3)代入(2)中的C:B=aaB+a+b…….(4)

對(duì)(4)式使用求解規(guī)則：B=(aa)*(a|b)…….(5)

將（5）代入(1)式中的B：A=(a|b)(aa)*(a|b)∴(a|b)(aa)*(a|b)即為所求。二、有窮自動(dòng)機(jī)(FA)自動(dòng)機(jī)：是一種能進(jìn)行運(yùn)算，并能實(shí)現(xiàn)自我控制的裝置。裝有程序的計(jì)算機(jī)也具有運(yùn)算和自我控制能力，因此計(jì)算機(jī)是一部自動(dòng)機(jī)所謂有窮自動(dòng)機(jī)：自動(dòng)機(jī)受囿于它能存儲(chǔ)的信息量，因此是有限的（有窮的）自動(dòng)機(jī)是識(shí)別符號(hào)串處理的強(qiáng)有力的工具，因而它成為研究詞法分析器的重要基礎(chǔ)。有窮自動(dòng)機(jī)分為：確定的有窮自動(dòng)機(jī)（DFA）非確定的有窮自動(dòng)機(jī)（NFA）１．確定的有窮自動(dòng)機(jī)（DFA）(1)DFA的形式定義：一個(gè)DFAM是一個(gè)五元組：

M=(S,∑,f,S0,F)其中：S：非空有窮的狀態(tài)集：每個(gè)元素是一個(gè)狀態(tài)?！疲河懈F輸入字母表；每個(gè)元素是輸入的一個(gè)字符。

f：狀態(tài)轉(zhuǎn)換函數(shù)：是從S×∑－>S的單值映射函數(shù)：

f(S1,a)=S2S0∈S是唯一的開始狀態(tài)

FS是終止?fàn)顟B(tài)集，可空（識(shí)別不出的字符串）例：設(shè)有DFAM=({0,1,2,3},{a,b},f,0,{3})其中：f：f(0,a)=1 f(0,b)=2DFA的函數(shù)式表示

f(1,a)=3 f(1,b)=2 f(2,a)=1 f(2,b)=3 f(3,a)=3 f(3,b)=3(2)DFA的狀態(tài)圖表示：開始狀態(tài)為0，終止?fàn)顟B(tài)為3，狀態(tài)集為{0,1,2,3}，字母表為：{a,b}

一般：假定DFAM含有m個(gè)狀態(tài)，n個(gè)輸入字符，則狀態(tài)圖含有m個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多有n條弧射出。(3)DFA的矩陣表示：矩陣的行表示狀態(tài)，列表示輸入字符，矩陣中的元素表示相應(yīng)狀態(tài)行和輸入字符列下的新狀態(tài)。即K行a列為f(K,a)的值。DFA的功能：對(duì)于∑*中的任何字符串α,若存在一條從開始結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的道路，其路上所有弧的標(biāo)記符連成的字符串等于α，則稱α能為DFA所識(shí)別（接受）。特別：若DFA的開始態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則空串可為DFA所識(shí)別。狀態(tài)\字符ab012132213333注：

①

DFA有3種表示法：函數(shù)表示，狀態(tài)圖表示，狀態(tài)矩陣表示。

②

DFA的確定性表現(xiàn)在轉(zhuǎn)換函數(shù)f:S×∑－>S是一個(gè)單值函數(shù)。即：對(duì)于任何狀態(tài)s∈S，和輸入符號(hào)a∈∑,f(s,a)能唯一確定下一個(gè)狀態(tài)。③可以證明：若存在一個(gè)正規(guī)文法G，G產(chǎn)生的語言L（G）,當(dāng)且僅當(dāng)存在一個(gè)∑上的確定有窮自動(dòng)機(jī)M，使得L（G）＝L（M）。

即：正規(guī)文法G在∑上描述的語言，一定存在DFA能夠識(shí)別這個(gè)語言。反之：若存在一個(gè)被DFA識(shí)別的語言，一定由存在的正規(guī)文法所描述。④由于DFA能識(shí)別正規(guī)文法描述的單詞，因此要想構(gòu)造識(shí)別單詞的詞法分析程序，也就成為怎樣構(gòu)造DFA的問題了。2.非確定的有窮自動(dòng)機(jī)（NFA）定義：一個(gè)NFA也是一個(gè)五元組：

M＝（S，∑，f，S0，F(xiàn)）其中：S，∑，F(xiàn)同DFAS0S是一個(gè)非空開始狀態(tài)集f：是一個(gè)多值的轉(zhuǎn)換函數(shù)：S×∑－>S的子集映射NFA與DFA的區(qū)別：NFA有一個(gè)開始狀態(tài)集，而DFA只有一個(gè)開始狀態(tài)；NFA轉(zhuǎn)換函數(shù)是多值函數(shù)，DFA的轉(zhuǎn)換函數(shù)是單值函數(shù)。例：設(shè)有NFAM＝（S,∑,f,S0,F）其中，S={q0,q1,q2,q3},∑={x,y},S0={q0},F={q1}f: f(q0,x)={q1,q2} f(q0,y)={q0} f(q1,x)={q0} f(q1,y)={q1,q2} f(q2,x)={q3} f(q2,y)={q3} f(q3,x)={q1,q3} f(q3,y)={q3}NFAM的狀態(tài)圖表示：狀態(tài)\字符xyq0{q1,q2}{q0}q1{q0}{q1,q2}q2{q3}{q3}q3{q1,q3}{q3}NFAM的矩陣表示：注：DFA是NFA的特例；對(duì)于每個(gè)NFAM，存在一個(gè)DFAM’,使得L(M)=L(M’)對(duì)于任何兩個(gè)有窮自動(dòng)機(jī)M和M’，若L(M)=L(M’)，則稱M與M’等價(jià)。三、由正規(guī)式構(gòu)造NFA或?qū)FA轉(zhuǎn)換成正規(guī)式１．理論依據(jù)定理：正規(guī)式與有窮自動(dòng)機(jī)是等價(jià)的。１o

∑上的NFAM，可以構(gòu)造∑上的正規(guī)式R，使：

L(M)=L(R)２o

在∑上的每個(gè)正規(guī)式R，可以構(gòu)造∑上的NFAM使：

L(R)=L(M)注：由正規(guī)式（或正規(guī)文法）構(gòu)造有窮自動(dòng)機(jī)的意義在于：將單詞的描述結(jié)構(gòu)轉(zhuǎn)換為對(duì)單詞的識(shí)別結(jié)構(gòu)。２．由正規(guī)式構(gòu)造NFA

方法：分裂法輸入：∑上的正規(guī)式R輸出：識(shí)別R的NFA步驟：1o引進(jìn)一個(gè)開始狀態(tài)結(jié)點(diǎn)x和終止?fàn)顟B(tài)結(jié)點(diǎn)y：

2o若R為復(fù)合公式，分裂R直到每條邊上只留下一個(gè)符號(hào)（可以為ε）為止；3o

分裂的結(jié)果：保證一個(gè)唯一的開始狀態(tài)結(jié)點(diǎn)和終止?fàn)顟B(tài)結(jié)點(diǎn)。例：設(shè)∑={x,y}上的正規(guī)式e=xy*(xy|yx)x*,構(gòu)造一個(gè)NFAM，使得L(M)=L(e)解:例：已知正則式e=0(1*)*|01 ，求：NFA ∵(A*)*=A* (A|A*=A*) ∴e=0(1*)*|01（利用恒式化簡，然后構(gòu)造NFA）

=01*|01=0(1*|1)=01*構(gòu)造NFA：３．將NFA轉(zhuǎn)換成正規(guī)式方法：合并法

（與分裂法相反） 輸入：NFAM

輸出：一個(gè)正規(guī)式e

步驟：

1o

對(duì)于NFAM中的開始狀態(tài)和終止?fàn)顟B(tài)分別新設(shè)置一個(gè)唯一的開始狀態(tài)和終止?fàn)顟B(tài)，使所設(shè)的開始狀態(tài)到原開始狀態(tài)連接ε弧；原終止?fàn)顟B(tài)到所設(shè)的終止?fàn)顟B(tài)連接ε弧。s為新增的開始狀態(tài)Z為新增的終止?fàn)顟B(tài)2o

利用下列規(guī)則進(jìn)行合并，直到圖中只剩下新設(shè)置的開始態(tài)和終止態(tài)為止。那么在開始態(tài)和終止態(tài)弧上的正規(guī)式便是所求的結(jié)果。例：已知NFA如下，求正規(guī)式e1o新設(shè)置一個(gè)唯一的開始狀態(tài)和終止?fàn)顟B(tài)：2o

按照合并規(guī)則進(jìn)行合并

∴e=(x|y)*(xy*y|yx*x)四、NFA到DFA的轉(zhuǎn)換（NFA的確定化）

1.理論依據(jù)和目的

定理：若L為一個(gè)能被NFA接受的語言，則存在一個(gè)能接受L的DFA：

即：L(NFAM)=L(DFAM)

目的：①

消除NFA中ε弧。ε弧會(huì)使自動(dòng)機(jī)做無用功。

②合并NFA中不確定的狀態(tài)。不確定狀態(tài)不僅給自動(dòng)機(jī)識(shí)別字符串帶來困難，而且使得編制相應(yīng)的詞法分析程序變得更為復(fù)雜。

NFA到DFA的轉(zhuǎn)換的基本思想：

DFA的每一個(gè)狀態(tài)對(duì)應(yīng)于NFA的一組狀態(tài)（狀態(tài)集合）。

方法：子集法

2.子集法分兩種情況介紹NFA的確定化：①不含ε弧的NFA的確定化。②含ε弧的εNFA的確定化 由NFAA=（S,∑,f,S0,F）構(gòu)造DFAA’=（S’,∑,f’,q0,F’）方法：1o

DFAA’的輸入字母表∑與NFAA的∑完全相同2o

把NFAA的每一個(gè)狀態(tài)子集作為DFAA’的一個(gè)狀態(tài)，因此該構(gòu)造方法稱為子集法。3o

設(shè)NFAA的任一狀態(tài)子集{r1，r2，…,rn},ri∈S(i=1,2,…,n),令r’=[r1，r2，…,rn],r’∈S’。取a∈∑,DFAA’的映射函數(shù)定義為：

f’(r’,a)=q’∈S’

其中，q’=[q1，q2，…,qm],而{q1，q2，…,qm}=f(r1,a)∪f(r2,a)∪…∪f(rm,a)。4oDFAA的開始狀態(tài)q0={S1，S2，…,SK}，其中，Si∈S0(i=1,2,…,K)5oDFAA的終止?fàn)顟B(tài)F’={e’|e’=[e1，e2，…,ep],{e1，e2，…,ep}∩F≠Φ}具體操作方法：1o

依據(jù)NFA,構(gòu)造確定化矩陣：

步驟：設(shè)狀態(tài)S0是NFA的開始狀態(tài)，以[S0]作為DFA的開始狀態(tài)，[S0]∈S’.再由f’([S0],a)=[S1,S2]（a∈∑）若：f’([S0],b)=[S0]（b∈∑）則：[S0]狀態(tài)對(duì)于輸入字符a,b的映射分別是狀態(tài)[S1,S2]與[S0]。其中：[S1,S2]∈S’是DFA的新狀態(tài)。再求新狀態(tài)[S1,S2]對(duì)于a,b的映射，設(shè)：

f’([S1,S2],a)=[S0,S3]∈S’ f’([S1,S2],b)=[S1,S2,S3]∈S’，即：[S0,S3]和[S1,S2,S3]均為DFA的新狀態(tài)。每得到一個(gè)新狀態(tài)，就繼續(xù)求新狀態(tài)對(duì)a,b的映射，直到再?zèng)]有新狀態(tài)為止。

2o

依據(jù)1o求出的確定化矩陣，代換出確定化的狀態(tài)轉(zhuǎn)換矩陣。

3o

依據(jù)確定化的狀態(tài)轉(zhuǎn)換矩陣畫出狀態(tài)轉(zhuǎn)換圖。（1）不含ε弧的NFA的確定化例:設(shè)有NFA的N=({q0,q1,q2,q3},{x,y},f,{q0},{q1})的狀態(tài)轉(zhuǎn)換圖如下：求等價(jià)的DFA（見前例）

解：1o依據(jù)NFA，構(gòu)造確定化矩陣：狀態(tài)\輸入xy{q0}{q1,q2}{q0}{q1,q2}{q0,q3}{q1,q2,q3}{q0,q3}{q1,q2,q3}{q0,q3}{q1,q2,q3}{q0,q1,q3}{q1,q2,q3}{q0,q1,q3}{q0,q1,q2,q3}{q0,q1,q2,q3}{q0,q1,q2,q3}{q0,q1,q2,q3}{q0,q1,q2,q3}2o

依據(jù)構(gòu)造的確定化矩陣，代換成確定化的狀態(tài)轉(zhuǎn)換矩陣(用符號(hào)重寫確定化矩陣)

將確定化矩陣中的{q0}，{q1,q2}，{q0,q3}……分別用符號(hào)標(biāo)記：A1,A2,……，A6即可。狀態(tài)\輸入xyA1A2A1A2A3A4A3A4A3A4A5A4A5A6A6A6A6A63o

依據(jù)確定化的轉(zhuǎn)換矩陣畫出狀態(tài)轉(zhuǎn)換圖確定開始狀態(tài)為：A1(代替[q0])終止?fàn)顟B(tài)為：A2，A4，A5，A6（A2，A4，A5，A6分別代替{q1,q2}，{q1,q2,q3}，{q0,q1,q3}，{q0,q1,q2,q3},其中包含NFA中的終止態(tài)q1）（2）εNFA的確定化（帶有空移或空環(huán)路的NFA）設(shè)εNFAM=(Q,∑∪{ε},f,Q0,F)，有：

1o狀態(tài)子集I的ε閉包（記為ε-closure(I)）I蘊(yùn)涵于Q,狀態(tài)子集I的ε-closure(I)定義如下：若狀態(tài)q∈I，則q∈ε-closure(I);若狀態(tài)q∈ε-closure(I),q’是由q出發(fā)經(jīng)多條ε弧到達(dá)的狀態(tài)，則q’∈ε-closure(I)，顯然，

ε-closure(I)蘊(yùn)涵于Q例：設(shè)有狀態(tài)轉(zhuǎn)換圖如下：

顯然，狀態(tài)集Q={1,2,3,4,5,6,7,8}若子集I={1}，則：ε-closure(I)={1,2}(∵狀態(tài)1∈I,∴1∈ε-closure(I)；

又∵從狀態(tài)1出發(fā)經(jīng)ε弧可到達(dá)狀態(tài)2∴2∈ε-closure(I))若子集I={4，5}，則：ε-closure(I)={2,4,5,6,7,8}2o狀態(tài)集合I的a弧轉(zhuǎn)換表示為

f(I,a)={q’|f(q,a)=q’,q∈I}=J（其中J蘊(yùn)涵Q）即：J是由子集I中的狀態(tài)出發(fā)，經(jīng)過一條a?。ㄌ^a弧前的任意條ε?。┛傻竭_(dá)的狀態(tài)的集合。令：Ia=ε-closure(J)表示：子集Ia是從子集I中任意狀態(tài)出發(fā)，經(jīng)a?。ㄇ昂罂商^ε?。┒竭_(dá)的狀態(tài)的集合。例：上例，若子集I={1},根據(jù)定義：子集J=f({1},a)={5,3,4}

于是：子集Ia=εclosure(J)=εclosure({5,3,4}={5,3,4,6,2,8,7}1,2的定義是為了消除空弧或空環(huán)。例：已知εNFAM如下圖。下面以此為例介紹εNFA確定化過程。解：依據(jù)εNFA的開始狀態(tài)集{S},求ε-closure({S})={S}（匯集S射出ε弧的結(jié)點(diǎn)集合）作為DFA的開始狀態(tài)。不斷地按新的非空子集求對(duì)輸入符號(hào)x,y的Ix和Iy，并將新的Ix或Iy作為DFA的狀態(tài)。這一過程一直重復(fù)到不再出現(xiàn)新的Ix或Iy為止。如：Ix=ε-closure({1})={1,2,3} Iy=ε-closure(Φ)=Φ∵Ix為非空新子集，作為DFA的狀態(tài)，且繼續(xù)以{1,2,3}求Ix和Iy。

Ix=ε-closure({1,2,3})={4} Iy=ε-closure({1,2,3})={2,3,5}

其中，{4}和{2,3,5}作為DFA的結(jié)點(diǎn)，且又是新的Ix,Iy,,繼續(xù)求Ix，ly，過程如下矩陣：IxIy{S}{1,2,3}Φ{1,2,3}{4}{2,3,5}{4}Φ{6,7,Z}{2,3,5}{4,6,7,Z}{2,3,5}{6,7,Z}{7,Z}Φ{4,6,7,Z}{7,Z}{6,7,Z}{7,Z}{7,Z}Φ分別：將七種狀態(tài)集：{S}，{1,2,3},{4},{2,3,5}, {6,7,Z},{4,6,7,Z},{7,Z}用符號(hào)q0~q6命名得DFA七 種狀態(tài)矩陣：DFA圖如下：

即為所求的DFA。IxIyq0q1Φq1q2q3q2Φq4q3q5q3q4q6Φq5q6q4q6q6Φ例：已知εNFA（如圖），求與之等價(jià)的DFA。

解：求DFA的開始狀態(tài)（與上例不同）

ε-closure({x})={x,0,1}，作為DFA的開始態(tài)。構(gòu)造確定化矩陣：IaIb{x,0,1}{0,2,1}{0,1}{0,2,1}{0,2,1}{0,1,3}{0,1}{0,2,1}{0,1}{0,1,3}{0,2,1}{0,y,1}{0,y,1}{0,2,1}{0,1}IaIbABCBBDCBCDBEEBC畫DFA的圖形表示五、DFA的化簡（DFA的最小化）

1.化簡DFA的目的尋找一個(gè)狀態(tài)數(shù)比M少的DFAM’，使得L(M)=L(M’)DFA的狀態(tài)少，則依據(jù)它編寫的詞法分析程序就簡單。

2.化簡化簡問題：

①使化簡后的DFA中，沒有多余的狀態(tài)。②使化簡后的DFA中，沒有兩個(gè)是相互等價(jià)的狀態(tài)。－－采用分割法。所謂多余狀態(tài)：從自動(dòng)機(jī)的開始狀態(tài)出發(fā)，輸入任何的字符串也不能到達(dá)的那個(gè)狀態(tài)。從自動(dòng)機(jī)的開始狀態(tài)到某個(gè)結(jié)點(diǎn)有弧，但該結(jié)點(diǎn)無弧通向終止?fàn)顟B(tài)。不可到達(dá)的狀態(tài)對(duì)于生成自動(dòng)機(jī)的語言毫無意義。因此，應(yīng)該從自動(dòng)機(jī)中刪去。兩個(gè)狀態(tài)s和t等價(jià)的條件是：一致性條件：狀態(tài)s和t必須同時(shí)為可接受狀態(tài)（終止?fàn)顟B(tài)）或不可接受狀態(tài)（非終止?fàn)顟B(tài)）。漫延條件：對(duì)于所有輸入符號(hào)，狀態(tài)s和t必須轉(zhuǎn)換到等價(jià)的狀態(tài)集里。

如果兩個(gè)狀態(tài)不等價(jià)，則稱這兩個(gè)狀態(tài)是可區(qū)別的。自動(dòng)機(jī)中的非終止?fàn)顟B(tài)與終止?fàn)顟B(tài)是可區(qū)別的（∵不滿足一致性條件）非終止?fàn)顟B(tài)0，2，1，3與終止?fàn)顟B(tài)4可區(qū)別。不滿足一致性條件。狀態(tài)2與狀態(tài)3可區(qū)別（∵狀態(tài)2讀入b后到達(dá)2;狀態(tài)3讀入b后到達(dá)4，而2和4不等價(jià)：即2，3不滿足漫延條件）。注：分割法就是使?fàn)顟B(tài)滿足漫延條件和一致性條件。關(guān)鍵：滿足漫延條件的分割方法。3.用分割法化簡DFA

基本思想：將DFA的狀態(tài)集分成若干個(gè)互不相交的子集，使每個(gè)子集中的狀態(tài)都是等價(jià)的，而不同狀態(tài)子集中的狀態(tài)則是不等價(jià)的。即是可區(qū)分的。1o

首先，將DFA的狀態(tài)分成兩個(gè)子集：終止?fàn)顟B(tài)子集和非終止?fàn)顟B(tài)子集。（因?yàn)榻K止?fàn)顟B(tài)與非終止?fàn)顟B(tài)是可區(qū)別的）。（使?fàn)顟B(tài)滿足一致性條件）2o

然后對(duì)每個(gè)子集進(jìn)行再分解。分解后的兩個(gè)狀態(tài)屬于同一個(gè)子集，當(dāng)且僅當(dāng)對(duì)于任何一個(gè)輸入字符，它們的映射屬于同一個(gè)子集，此過程一直執(zhí)行到不能再分解為止。（使?fàn)顟B(tài)滿足漫延條件）3o

將分解的每個(gè)子集作為化簡后的DFA的每一個(gè)狀態(tài)。且含有原來開始狀態(tài)的子集和含有原來終止?fàn)顟B(tài)的子集分別作為開始狀態(tài)和終止?fàn)顟B(tài)。具體DFA的化簡過程。例：已知有DFA圖如下，化簡DFA：

解：1o將所有終止?fàn)顟B(tài)歸為一個(gè)子集S1={q1,q3,q4,q5};其余非終止?fàn)顟B(tài)歸為另一個(gè)子集：S2={q0,q2}2o按可區(qū)別性分解子集S1和S2

分解S1：∵f(q1,x)=q2∈S2 f(q3,x)=q4∈S1 f(q4,x)=q5∈S1 f(q5,x)=q5∈S1 (也可對(duì)y字符進(jìn)行)∴將S1分解成兩個(gè)子集S1’={q1},S2’={q3,q4,q5}分解S2： ∵f(q0,x)=q1∈S1’ f(q2,x)=q3∈S2’ ∴將S2分解成兩個(gè)子集{q0},{q2}最后分解成4個(gè)子集：{q1},{q3,q4,q5},{q0},{q2}分別用q1,q3,q0,q2來替換成4個(gè)子集的狀態(tài)名。DFA的化簡：用狀態(tài)矩陣形式輔助完成化簡xyq0q1q0q1q2q3q2q3q2q3q4q3q4q5q5q5q5q5分解：S1={q0,q2},S2={q1,q3,q4,q5}對(duì)x，S2分解：S21={q1},S22={q3,q4,q5}對(duì)x，s1分解：S12={q0},s12={q2},S22對(duì)x或y不能分解。最后得到分解：{q0},{q1},{q2},{q3,q4,q5}例：將DFA（如下圖）最小化。解：1o

將終止態(tài)與非終止態(tài)的結(jié)點(diǎn)分為2個(gè)子集：

=({A,B,C,D},{E})(其中S0={A,B,C,D},S1={E})20分解子集：S0＝{A,B,C,D}對(duì)a：對(duì)b：f(A,a)=B∈S0寫成{A,B,C,D}a={B}∵B包含在{A,B,C,D}中,∴{A,B,C,D}對(duì)a不被分裂f(B,a)=B∈S0f(C,a)=B∈S0f(D,a)=B∈S0f(A,b)=C∈S0寫成{A,B,C,D}b={C,D,E}∵{C,D,E}既不包含在{A,B,C,D}中，又不包含在{E}中，∴{A,B,C,D}對(duì)b要被分裂。f(B,b)=D∈S0f(C,b)=C∈S0f(D,b)=E∈S1∴=({A,B,C},{D},{E})(若令S2={A,B,C}，S3={D},S4={E})再分解：{A,B,C}對(duì)a：對(duì)b：f(A,a)=B∈S2寫成{A,B,C}a={B}∵B包含在{A,B,C}中,∴{A,B,C}對(duì)a不被分裂f(B,a)=B∈S2f(C,a)=B∈S2f(A,b)=C∈S2寫成{A,B,C}b={C,D}∵{C,D}既不包含在{A,B,C}中，又不包含在{D}中，∴{A,B,C}對(duì)b要被分裂。f(B,b)=D∈S3f(C,b)=C∈S2∴＝（{A,C},{B},{D},{E}）再分解：{A,C}∵{A,C}a={B}(∵{B}包含在{B}中,∴對(duì)a,{A,C}不被分裂) {A,C}b={C}(∵{C}包含在{A,C}中，∴對(duì)b,{A,C}不被分裂)

結(jié)論：A,C狀態(tài)等價(jià)。整個(gè)分解終止。∴ =（{A,C},{B},{D},{E}）DFA最小化為：IaIbABCBBDCBCDBEEBC注：可通過DFA確定化矩陣，應(yīng)用狀態(tài)滿足漫延條件和一致性條件，直接得出等價(jià)的狀態(tài)。如：上面的確定化矩陣，{B}b={D},{D}b={E},而E,D不等價(jià)，導(dǎo)致B,D不等價(jià)，所以，D和B要分裂。例：已知正規(guī)式R=l(l|d)*,求最小DFA解：步驟：1o求DFA2o求DFA子集法：構(gòu)造確定化的矩陣IlId{x}{1,2,y}Φ{1,2,y}{2,y}{2,y}{2,y}{2,y}{2,y}IlIdABΦBCCCCC3o最小化DFA分割法：首先將DFA分解成兩個(gè)子集：=({A},{B,C}){B,C}不能分解：對(duì)l： 對(duì)d：∴B,C等價(jià)：去掉C

最小化DFA：

注：實(shí)現(xiàn)時(shí)，擴(kuò)充為：

且規(guī)定：字符串的長度為n,f(B,l)=C寫成{B,C}l={C}f(C,l)=Cf(B,d)=C寫成{B,C}d={C}f(C,d)=C六、由最小化的DFA到詞法分析程序的構(gòu)造若指明DFA的每一個(gè)狀態(tài)要完成的任務(wù)再把從狀態(tài)0出發(fā)的弧上所標(biāo)記的輸入字符視為控制條件則：DFA實(shí)際上就是一個(gè)程序流程圖。例：上例最小化DFA：要識(shí)別一個(gè)標(biāo)識(shí)符是否結(jié)束，必須讀到該標(biāo)識(shí)符后繼字符是分界符（或非l,d）因此，實(shí)現(xiàn)時(shí)，將標(biāo)識(shí)符DFA作適當(dāng)修改：如果賦予狀態(tài)A,B,Z一定的操作，則DFA變?yōu)樽R(shí)別標(biāo)識(shí)符程序的框圖?！?.正規(guī)文法與有窮自動(dòng)機(jī)之間的轉(zhuǎn)換一、正規(guī)文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換分別就左,右線性文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換1.右線性文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換

設(shè)給定右線性文法G=(VN,VT,P,S),則相應(yīng)的有窮自動(dòng)機(jī)M=(Q,∑,f,q0,Z).

轉(zhuǎn)換方法：(1)將VN中每一個(gè)非終結(jié)符視作M1中的一個(gè)狀態(tài)，并增加一個(gè)終結(jié)狀態(tài)D,DVN,令Q=VN∪{D},Z={D},∑=VT,q0=S,f函數(shù)構(gòu)造如下：(2)對(duì)G中每一形如:A∷=aB的產(chǎn)生式(A,B∈VN,a∈VT∪{ε}),令f(A,a)=B;(3)對(duì)G中每一形如:A∷=a的產(chǎn)生式(A∈VN,a∈VT),令f(A,a)=D;(注意：D是終結(jié)狀態(tài))(4)對(duì)G中每一形如:A∷=ε的產(chǎn)生式(A∈VN),令f(A,ε)=D;

顯然，這樣構(gòu)造的M是具有一個(gè)開始狀態(tài)的NFA。例：構(gòu)造下列右線性文法G[Z]的有窮自動(dòng)機(jī)。

Z∷=0AA∷=0A|0BB∷=1A|1則構(gòu)造等價(jià)自動(dòng)機(jī)M=({Z,A,B,D},{0,1},f,{Z},{D}),其中：

f(Z,0)={A},f(A,0)={A,B},f(B,1)={D},f(B,1)={A}右線性文法構(gòu)造狀態(tài)圖

A

B

Z

D

0

1

0

1

0狀態(tài)矩陣表示：2.左線性正規(guī)文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換設(shè)給定義左線性正規(guī)文法G=(VN,VT,P,S),則相應(yīng)的有窮自動(dòng)機(jī)M=(Q,∑,f,q0,Z).(1)新增加一個(gè)初始狀態(tài)q0,且q0VN;將VT中每個(gè)非終止?fàn)顟B(tài)視作M中的狀態(tài)，令Q=VN∪{q0},并將G的開始符號(hào)S看成終結(jié)狀態(tài)，即Z={S},∑=VT;(2)對(duì)G中每一形如:A∷=Ba的產(chǎn)生式(A,B∈VN,a∈VT∪{ε}),令f(B,a)=A;

01Z{A}ΦA(chǔ){A,B}ΦBΦ{A,D}DΦ

Φ(3)對(duì)G中每一形如:A∷=a的產(chǎn)生式(A∈VN,a∈VT∪{ε}),令f(q0,a)=A;例，構(gòu)造G[A]的自動(dòng)機(jī)A∷=A1|B1B∷=B0|0根據(jù)轉(zhuǎn)換方法，與G對(duì)應(yīng)的自動(dòng)機(jī)M=({S,A,B},{0,1},f,S,{A}),其中：

f(A,1)=A,

f(B,1)=A,

f(B,0)=B,

f(S,0)=B其狀態(tài)圖：它為確定的，且識(shí)別的語言為：L(M)=L(G[A])=00*11*二、有窮自動(dòng)機(jī)到正則文法的轉(zhuǎn)換給定有窮自動(dòng)機(jī)M=(Q,∑,f,q0,Z),按下列方法構(gòu)造對(duì)應(yīng)右線性文法G=(VN,VT,P,S):(1)令VN=Q，VT=∑，S=q0;(2)若f(A,a)=B,且B不是終結(jié)狀態(tài),則將A∷=aB加到p中；(3)若f(A,a)=B,且B是終結(jié)狀態(tài),則將A∷=aB|a或A∷=aB,B∷=ε加到p中；(4)若G的開始符號(hào)S是一個(gè)終結(jié)狀態(tài)，則將S∷=ε

加到p中。例：設(shè)DFAM=({A,B,C,D},{0,1},f,A,{B}),其中：

f(A,0)=B,f(B,1)=C,f(C,0)=B,

（1）根據(jù)函數(shù)式構(gòu)造右線性正規(guī)文法G[A]：

A→0B|0,B→1C,C→0C|0

或A∷=0B,B∷=1C|ε,C∷=0B（2）將函數(shù)式換成狀態(tài)圖，然后轉(zhuǎn)換成右線性正規(guī)文法。由函數(shù)式得到等價(jià)的DFAM:根據(jù)狀態(tài)轉(zhuǎn)換圖，所求右線性文法G=({A,B,C},{0,1},P,A),P為：

A∷=0B|0,B∷=1C,C∷=0B|0

或A∷=0B,B∷=1C|ε,C∷=0B注：以開始狀態(tài)作為開始符號(hào)，然后依弧的方向?qū)懗霎a(chǎn)生式右邊的式子。若到達(dá)的是終結(jié)狀態(tài)弧，則，該弧上的符號(hào)要作為產(chǎn)生式右邊的式子。該自動(dòng)機(jī)所識(shí)別的語言為0(01)*.注：1.自動(dòng)機(jī)3種形式：函數(shù)式、狀態(tài)圖和狀態(tài)矩陣都可以轉(zhuǎn)換成正規(guī)文法。例：已知自動(dòng)機(jī)3種形式如下，轉(zhuǎn)換成右線性正規(guī)文法01SBΦBBAAΦA(chǔ)f（S,0）=B，f（B,0）=B,f（B,1）=A,f（A,1）=A.轉(zhuǎn)換成右線性正規(guī)文法G[S]=({S,A,B}，{0,1}，P，S)P:S→0B，B→0B|1A|1，A→1A|1.2.通過狀態(tài)圖將左右線性正規(guī)文法可以互換上例狀態(tài)圖轉(zhuǎn)化成左線性正規(guī)文法G[A],P:A→A1|B1，B→B0|0(終結(jié)狀態(tài)作為開始符號(hào)，原來開始狀態(tài)作為終結(jié)狀態(tài)，然后以弧逆方向?qū)懗霎a(chǎn)生式右邊的式子。）§5.詞法分析程序的編寫方法及實(shí)驗(yàn)要求一、詞法分析程序編寫方法兩種方法：手工編寫方法：根據(jù)識(shí)別語言單詞的狀態(tài)圖，使用某種高級(jí)語言，例如c語言直接編寫詞法分析程序。利用詞法分析程序的自動(dòng)生成工具LEX自動(dòng)生成此法分析程序。下面僅介紹手工編寫詞法分析程序的構(gòu)造過程。二、詞法分析程序構(gòu)造過程：1.分析列出待分析語言的所有單詞符號(hào)，編寫對(duì)應(yīng)的種別碼。例：c語言子集的單詞符號(hào)及種別碼：(1)有窮的單詞符號(hào)：關(guān)鍵字：main,void,if,then,while,for,printf,scanf,int,…運(yùn)算符：+,-,*,/,>,>=,<,<=,==,!=,(,),…分界符：{,},;,:,，,[,],…編寫對(duì)應(yīng)的種別碼：單詞符號(hào)種別碼單詞符號(hào)種別碼單詞符號(hào)種別碼單詞符號(hào)種別碼main1=21,30‘‘39int2+22;31‘\0100char3-23:32ERROR-1if4*24>33else5/25<34for6(26>=35while7)27<=36ID10{28==37NUM11}29!=38(2)無窮的單詞符號(hào)應(yīng)寫出對(duì)應(yīng)的文法。如：標(biāo)識(shí)符(ID)和常數(shù)(NUM) ID：letter(letter|digit)*(ID種別碼見上表) letter∷=a|b|…|z|A|B|…|Z digit∷=0|1|…|9常數(shù)：整常數(shù)：NUM:digit(digit)*(NUM種別碼見上表)2.畫單詞的狀態(tài)轉(zhuǎn)換圖(下頁)Z1035678941011letter非letter非digitletter|digitdigit非digitdigit+-*/>其它=100n其它出錯(cuò)處理……3.根據(jù)狀態(tài)圖和單詞符號(hào)的種別碼表，構(gòu)造詞法分析程序簡單的方法：讓每個(gè)狀態(tài)對(duì)應(yīng)一小段程序。在此引進(jìn)詞法分析程序所用的全局變量和需要調(diào)用的函數(shù)；(1)ch字符變量，存放當(dāng)前讀入的源程序字符。(2)token字符數(shù)組，存放構(gòu)成單詞符號(hào)的字符串.(3)getch()讀字符函數(shù)，每調(diào)用一次從輸入緩沖區(qū)中讀入源程序的下一個(gè)字符放在ch中，并把讀字符指針指向下一個(gè)字符串。(4)getbc()函數(shù)，每次調(diào)用時(shí)，檢查ch中的字符是否為空白字符。是，則反復(fù)調(diào)用getch()，直至ch讀入一個(gè)非空白字符為止。(5)concat()函數(shù),每次調(diào)用把當(dāng)前ch中的字符與token中的字符串連接。例如：token字符數(shù)組中原有值為”ab”,ch存放著”c”，經(jīng)調(diào)用concat后，token中的值為:”abc”.(6)lett(ch)和digi()布爾函數(shù)，分別用來判斷ch中的字符是否為字母和數(shù)字，從而給出true或false值。(7)reserve()整型函數(shù)，對(duì)token中的字符串查種別碼表，若是一個(gè)關(guān)鍵字，則返回他的種別碼,否則返回標(biāo)識(shí)符的種別碼10。(8)retract()函數(shù)，讀字符指針回退一個(gè)字符。(9)return()函數(shù)，收集并攜帶必要信息返回調(diào)用程序。即返回語法分析程序。(10)dtb()十進(jìn)制轉(zhuǎn)換函數(shù)，它將token中的數(shù)字出轉(zhuǎn)換成二進(jìn)制數(shù)值表示，并以此作為涵數(shù)值返回。根據(jù)狀態(tài)轉(zhuǎn)換圖，用c語言編寫的詞法分析程序如下：scaner(){ token=NULL;

getch();

getbc(); if(lett(ch)) { while(lett(ch)||digi(ch))//識(shí)別關(guān)鍵字和標(biāo)識(shí)符

{ cancat();

getch(); } retract();c=reserve(); if(c!=10)return(c,token); elsereturn(10,token); }elseif(digi(ch))//識(shí)別常數(shù)

{while(digi(ch)) { concat();

getch(); } retract(); return(11,dtb()); } else//識(shí)別運(yùn)算符和分界符

switch(ch){ case‘+’:retrun(22,-);break; case‘-’:retrun(23,-);break; case‘*’:retrun(24,-);break; case‘/’:retrun(25,-);break; case‘>’:getch();

if(ch==‘=‘)return(35,-); retract();break; …… default:error(); }}三、詞法分析程序構(gòu)造的實(shí)驗(yàn)1.實(shí)驗(yàn)報(bào)告的內(nèi)容(1)實(shí)驗(yàn)?zāi)康?2)實(shí)驗(yàn)要求a.待分析c語言子集的詞法

1)關(guān)鍵字

2)運(yùn)算符和分界符

3)其它標(biāo)記:ID和NUM ID標(biāo)記：標(biāo)識(shí)符的正規(guī)式定義

NUM標(biāo)記：整數(shù)的正規(guī)式定義

4)空格由空白，制表符和換行符組成； 空格用來分隔ID，NUM，關(guān)鍵字和運(yùn)算符，分界符。b.各種單詞符號(hào)對(duì)應(yīng)的種別碼表c.詞法分析程序的功能

輸入：所給文法的源程序字符串。(打印給出待分析的源程序)

輸出：二元組(syn,token或sum)構(gòu)成的序列。其中：(打印輸出二元組清單)syn為單詞種別碼。token存放的單詞自身字符串。Sum為整常數(shù)。例如，對(duì)c源程序main(){ inti=10; while(i) i=i-1;}源文件中，經(jīng)詞法分析后，輸出下列形式的序列:(1,main)(37,()(38,))(33,{)(14,int)……注：出錯(cuò)處理要求給出錯(cuò)誤字符(或字符串)所在源程序的行號(hào)和列號(hào)。(3).詞法分析程序主要算法思想

1)主程序的流程圖

如：(下頁)開始打開源程序文件打開成功否？過濾程序送緩沖區(qū)調(diào)用詞法分析程序輸出單詞二元組源程序串分析完畢否？出錯(cuò)處理結(jié)束NNYY

2)詞法分析程序的流程圖

2.應(yīng)交的文檔資料

1).源程序清單：函數(shù)及定義的數(shù)據(jù)結(jié)構(gòu)要加注釋.2).結(jié)果清單

●被分析的源程序清單

●單詞的二元組清單

●運(yùn)行的命令行清單

3).體會(huì)和收獲

§6.小結(jié)一、本章主要內(nèi)容有二

單詞的描述機(jī)制：正規(guī)式和正規(guī)文法。單詞的識(shí)別機(jī)制：確定的有窮自動(dòng)機(jī)。

1.描述單詞的語法描述無窮的單詞有：標(biāo)識(shí)符和常數(shù)描述單詞的語法形式：正規(guī)式正規(guī)文法它們之間可以互相轉(zhuǎn)換：2.有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī)：DFAM=(S,∑,f,S,Z)，其中f是單值映射函數(shù)，S為唯一初態(tài)。非確定的有窮自動(dòng)機(jī)：NFAM=(S,∑,f,S,Z)，其中f是多值映射函數(shù)，S為非空初態(tài)集。有窮自動(dòng)機(jī)通常非形式化表示為狀態(tài)轉(zhuǎn)換圖和矩陣。構(gòu)造詞法分析程序的過程：正規(guī)式、正規(guī)文法和有窮自動(dòng)機(jī)三者都是描述單詞語法的工具，它們的描述能力是等價(jià)的，它們之間可相互轉(zhuǎn)換。但有窮自動(dòng)機(jī)還具有識(shí)別能力，有窮自動(dòng)機(jī)最小化的DFA狀態(tài)轉(zhuǎn)換圖視為詞法分析程序的框圖。

主要練習(xí)的問題：正規(guī)式－最小化的DFA－正規(guī)文法

利用最小化DFA：證明兩正規(guī)式或正規(guī)文法相互等價(jià)（最小化DFA

相同），或正規(guī)式與正規(guī)文法之間等價(jià)。將左（右）線性文法轉(zhuǎn)換為等價(jià)的右（左）線性文法。二、例子例1，試寫出在∑={a,b}上且不以a開頭，但以aa結(jié)尾的字符串集合的正規(guī)式，并構(gòu)造與之等價(jià)且狀態(tài)最少的DFA。解：不以a開頭，即意味著一定以b