編譯原理—清華大學(xué)—第2版—第4章詞法分析

1、第四章第四章 詞法分析詞法分析 教學(xué)要求：教學(xué)要求：本章介紹編譯程序的第一個(gè)階本章介紹編譯程序的第一個(gè)階段詞法分析的設(shè)計(jì)原理，要求掌握正規(guī)文段詞法分析的設(shè)計(jì)原理，要求掌握正規(guī)文法、法、DFADFA、NFANFA、正規(guī)式和正規(guī)集的基本概、正規(guī)式和正規(guī)集的基本概念和詞法分析器的設(shè)計(jì)原理。念和詞法分析器的設(shè)計(jì)原理。 教學(xué)重點(diǎn)：教學(xué)重點(diǎn)：詞法分析器的任務(wù)與設(shè)計(jì)，自詞法分析器的任務(wù)與設(shè)計(jì)，自動(dòng)機(jī)的建立、表示、確定化及化簡(jiǎn)。動(dòng)機(jī)的建立、表示、確定化及化簡(jiǎn)。（1 1）分析和識(shí)別單詞及屬性，分析和識(shí)別單詞及屬性， 包括識(shí)別包括識(shí)別語(yǔ)言的語(yǔ)言的關(guān)鍵字關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符等、標(biāo)識(shí)符、常數(shù)、運(yùn)算符等；（2

2、2）跳過(guò)各種分隔符，如空格，回車，制表符等；跳過(guò)各種分隔符，如空格，回車，制表符等；（3 3）刪除注釋）刪除注釋；（4 4）進(jìn)行詞法檢查，報(bào)告所發(fā)現(xiàn)的錯(cuò)誤；）進(jìn)行詞法檢查，報(bào)告所發(fā)現(xiàn)的錯(cuò)誤；（5 5）建立符號(hào)表。）建立符號(hào)表。4.14.1詞法分析的任務(wù)詞法分析的任務(wù)實(shí)現(xiàn)方案：基本上有兩種實(shí)現(xiàn)方案：基本上有兩種1.詞法分析單獨(dú)作為一遍詞法分析單獨(dú)作為一遍2.詞法分析程序作為單獨(dú)的子程序詞法分析程序作為單獨(dú)的子程序S.P.(字符串字符串)詞法分析詞法分析S.P.(符號(hào)串符號(hào)串)語(yǔ)法分析語(yǔ)法分析第一遍第一遍第二遍第二遍單詞串單詞串優(yōu)點(diǎn)優(yōu)點(diǎn): 結(jié)構(gòu)清晰、各遍功能單一結(jié)構(gòu)清晰、各遍功能單一缺點(diǎn)：效率低缺

3、點(diǎn)：效率低S.P.(字符串字符串)詞法分詞法分析程序析程序語(yǔ)法分語(yǔ)法分析程序析程序取單詞取單詞單詞單詞單詞符號(hào)單詞符號(hào) 單詞符號(hào)一般可分為下列五種：?jiǎn)卧~符號(hào)一般可分為下列五種：（）：）：if,for,whileif,for,while等等：各種名稱，如常量名、變量名、過(guò)程：各種名稱，如常量名、變量名、過(guò)程名等名等（量）：（量）：25, 3.1415, 25, 3.1415, TRUE, TRUE, “ABCABC”等等：如：如 + - + - * * / = / =等等：逗號(hào)，分號(hào)，括號(hào)等：逗號(hào)，分號(hào)，括號(hào)等詞法分析程序的輸出形式詞法分析程序的輸出形式-二元式二元式( (單詞類別單詞類別, ,

4、單詞的屬性值單詞的屬性值) )單詞類別可以用整數(shù)編碼表示單詞類別可以用整數(shù)編碼表示: :一類一種或一字一種一類一種或一字一種單詞類別單詞類別關(guān)鍵字關(guān)鍵字標(biāo)識(shí)符標(biāo)識(shí)符常數(shù)常數(shù)運(yùn)算符運(yùn)算符分界符分界符編碼編碼1 12 23 34 45 5表3.1 int x=10,y=20,sum;詞法分析的結(jié)果單詞類別單詞類別單詞的屬性值單詞的屬性值1int2指向指向x的符號(hào)表入口指針的符號(hào)表入口指針4=3105,2指向指向y的符號(hào)表入口指針的符號(hào)表入口指針4=3205,2指向指向sum的符號(hào)表入口指針的符號(hào)表入口指針5;例例 int x=10,y=20,sum;詞法分析的結(jié)果詞法分析的結(jié)果 4.2 4.2 單

5、詞的描述工具單詞的描述工具一、正規(guī)文法：一、正規(guī)文法： 文法文法G=G=（V VN N，V VT T，P P，S S），），P P中每一產(chǎn)中每一產(chǎn)生式的形式都為：生式的形式都為：或或，其中其中AVAVN N ，BVBVN N ，aVaVT T幾類單詞正規(guī)文法的描述幾類單詞正規(guī)文法的描述：標(biāo)識(shí)符標(biāo)識(shí)符l | ll | l字母數(shù)字字母數(shù)字字母數(shù)字字母數(shù)字l | d | ll | d | l字母數(shù)字字母數(shù)字| | d d字母數(shù)字字母數(shù)字：無(wú)符號(hào)整數(shù)無(wú)符號(hào)整數(shù)d | dd | d無(wú)符號(hào)整數(shù)無(wú)符號(hào)整數(shù)：運(yùn)算符運(yùn)算符 + + | - | | - | * * | / | = | = | / | = | |

6、= =：界符界符 , | ; | ( | ) | , | ; | ( | ) |二、正規(guī)式二、正規(guī)式（一）定義（一）定義（正規(guī)式正規(guī)式和它所表示的和它所表示的正規(guī)集正規(guī)集）：）：設(shè)字母表為設(shè)字母表為 ，輔助字母表，輔助字母表 = ， ， ， ， ，( (，)。1 1、 和和 都是都是 上的正規(guī)式，它們所表示的正規(guī)集分別為上的正規(guī)式，它們所表示的正規(guī)集分別為 和和 ；2 2、任何、任何a a ，a a是是 上的一個(gè)正規(guī)式，它所表示的正規(guī)集上的一個(gè)正規(guī)式，它所表示的正規(guī)集為為 aa；3 3、假定假定e e1 1和和e e2 2都是都是 上的正規(guī)式，它們所表示的正規(guī)集分上的正規(guī)式，它們所表示的正規(guī)集

7、分別為別為L(zhǎng)(eL(e1 1) )和和L(eL(e2 2) )，那么，那么，( (e e1 1), ), e e1 1 e e2 2, , e e1 1 e e2 2, , e e1 1 也都也都是正規(guī)式是正規(guī)式, ,它們所表示的正規(guī)集分別為它們所表示的正規(guī)集分別為L(zhǎng)(eL(e1 1), ), L(eL(e1 1)L(e)L(e2 2), L(e), L(e1 1)L(e)L(e2 2) )和和( (L(eL(e1 1) 。4 4、僅由有限次使用上述三步驟而定義的表達(dá)式才是、僅由有限次使用上述三步驟而定義的表達(dá)式才是 上的上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是正規(guī)式，僅由這些正規(guī)式所表示的

8、字集才是 上的正規(guī)上的正規(guī)集。集。例例:令令 =a，b， 上的正規(guī)式和相應(yīng)的正規(guī)集上的正規(guī)式和相應(yīng)的正規(guī)集的例子有：的例子有：正規(guī)式正規(guī)式 正規(guī)集正規(guī)集a aa ba,bab ab(a b)(a b) aa,ab,ba,bba ,a,aa, 任意個(gè)任意個(gè)a的串的串(a b) ,a,b,aa,ab 所有由所有由a 和和b組成的串組成的串(a b) (aa bb)(a b) 上所有含有兩個(gè)相繼上所有含有兩個(gè)相繼 的的a或兩個(gè)相繼的或兩個(gè)相繼的b組成組成 的串的串例例 =l l，dd，r=l(lr=l(l d)d) 定義的正規(guī)集定義的正規(guī)集: : l,ll,ld,ldd,l,ll,ld,ldd, （

9、標(biāo)識(shí)符）標(biāo)識(shí)符）其中：其中：l l代表字母代表字母, ,d d代表數(shù)字代表數(shù)字, ,正規(guī)式即是正規(guī)式即是 字母字母( (字母字母| |數(shù)字?jǐn)?shù)字) ) 它表示的正規(guī)集是它表示的正規(guī)集是“字母打頭的字母數(shù)字串字母打頭的字母數(shù)字串”。例例4.3 4.3 =d d，. .，e e，+ +，-,-,則則 上的正規(guī)式上的正規(guī)式 ：d d (.dd(.dd )(e(+ )(e(+ - -)dd)dd ) )表示的是無(wú)符號(hào)數(shù)的集合。其中：表示的是無(wú)符號(hào)數(shù)的集合。其中：d d為為0-90-9的數(shù)字。的數(shù)字。（二）兩個(gè)正規(guī)式（二）兩個(gè)正規(guī)式等價(jià)等價(jià) 若兩個(gè)正規(guī)式若兩個(gè)正規(guī)式e e1 1和和e e2 2所表示的所表

10、示的, ,則說(shuō)則說(shuō)e e1 1和和e e2 2等價(jià)等價(jià), ,寫(xiě)作寫(xiě)作e e1 1= =e e2 2。例如：例如： e e1 1= (a= (a b)b)， e e2 2 = b = b a a又如：又如： b(ab)b(ab) = (ba) = (ba) b b (a (a b)b) = (a= (a b b ) ) （三）正規(guī)式的運(yùn)算律（三）正規(guī)式的運(yùn)算律 設(shè)設(shè)r,s,tr,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：1 1、r r s=ss=s r r “或或”服從交換律服從交換律2 2、r r ( (s s t)=(t)=(r r s s) ) t t “或

11、或”的可結(jié)合律的可結(jié)合律3 3、( (rs)t=r(st)rs)t=r(st) “連接連接”的可結(jié)合律的可結(jié)合律4 4、r(sr(s t)=rst)=rs rtrt (s(s t)r=srt)r=sr trtr 分配律分配律 5 5、 r=r, rr=r, r =r=r 是是“連接連接”的恒等元的恒等元素素6 6、r r r=rr=rr r = = r r rrrr “或或”的抽取律的抽取律 三、正規(guī)文法到正規(guī)式三、正規(guī)文法到正規(guī)式 V VT T= = , , S S V VN N ， （1 1）對(duì)正規(guī)式）對(duì)正規(guī)式r r，生成生成正規(guī)產(chǎn)生式正規(guī)產(chǎn)生式 S Sr r （2 2）若）若x x和和y

12、 y都是正規(guī)式都是正規(guī)式 對(duì)形如對(duì)形如A Axyxy的的正規(guī)產(chǎn)生式：正規(guī)產(chǎn)生式： A AxBxB，B By y，B B V VN N 對(duì)形如對(duì)形如A Ax x y y的的正規(guī)產(chǎn)生式：正規(guī)產(chǎn)生式： A AxBxB，A Ay y，B BxBxB，B By y，B B V VN N 對(duì)形如對(duì)形如A Ax x y y的的正規(guī)產(chǎn)生式正規(guī)產(chǎn)生式: : A Ax x，A Ay y 不斷應(yīng)用上述規(guī)則做變換，直到每個(gè)產(chǎn)生式右端只含一個(gè)不斷應(yīng)用上述規(guī)則做變換，直到每個(gè)產(chǎn)生式右端只含一個(gè)V VT T對(duì)對(duì) 上的正規(guī)式上的正規(guī)式r ,r ,存在一個(gè)存在一個(gè)G=(VG=(VN N,V,VT T,P,S),P,S)使得使得

13、L(G)=L(r) L(G)=L(r) ，反之亦然。反之亦然。NVNV 例例 r = a(a d) VT=a,d Sa(a d) SaA A(a d) A(a d)B A B(a d)B BGs: SaA A VT=a,d AaBVN=S,A,B AdB BaB BdB B 使用如下規(guī)則，最后只剩下一個(gè)開(kāi)始符號(hào)定義使用如下規(guī)則，最后只剩下一個(gè)開(kāi)始符號(hào)定義的產(chǎn)生式，并且右部不含非終結(jié)符。的產(chǎn)生式，并且右部不含非終結(jié)符。規(guī)則規(guī)則1 1 ：A-xB,B-y = A=xyA-xB,B-y = A=xy規(guī)則規(guī)則2 2： A-xA|y = A=xA-xA|y = A=x* *y y規(guī)則規(guī)則3 3： A-x

14、, A-y = A=x|yA-x, A-y = A=x|y例如：文法例如：文法GSGS為：為： S-aA, S-a, A-aA, A-dA, A-a, A-dS-aA, S-a, A-aA, A-dA, A-a, A-dS=aA|aS=aA|aA=(aA|dA)|(a|d)A=(aA|dA)|(a|d)A=(a|d)A|(a|d)A=(a|d)A|(a|d)A=(a|d)A=(a|d)* *(a|d)=(a|d)(a|d)=(a|d)+ +A A代入代入S S得：得：S=a(a|d)S=a(a|d)+ +|a|aS=a(a|d)S=a(a|d)+ +|）S=a(a|d)S=a(a|d)* *所

15、以，對(duì)應(yīng)正規(guī)式為：所以，對(duì)應(yīng)正規(guī)式為：a(a|d)a(a|d)* *4.3 4.3 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī) 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)( (也稱有限自動(dòng)機(jī)也稱有限自動(dòng)機(jī),DFA),DFA)是識(shí)別是識(shí)別正規(guī)集的裝置。正規(guī)集的裝置。正規(guī)式正規(guī)式正規(guī)文法正規(guī)文法NFANFADFADFA識(shí)別單詞識(shí)別單詞輸入串輸入串轉(zhuǎn)換轉(zhuǎn)換構(gòu)造構(gòu)造確定化確定化本章學(xué)習(xí)思路本章學(xué)習(xí)思路一個(gè)確定的有窮自動(dòng)機(jī)（一個(gè)確定的有窮自動(dòng)機(jī)（DFADFA）M M是一個(gè)五元組：是一個(gè)五元組：M=M=（K K，f f，S S，Z Z）其中其中1.1. 是一個(gè)有窮集，它是一個(gè)有窮集，它稱稱一個(gè)一個(gè)；2.2.一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符

16、號(hào)，一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱所以也稱為為；3.3.，是，是K KK K上的映射，上的映射，f(kf(ki i,a)=k,a)=kj j，(k(ki i，k kj jK)K)表示：當(dāng)前狀態(tài)為表示：當(dāng)前狀態(tài)為k ki i，輸入符為輸入符為a a時(shí)，將轉(zhuǎn)換為下時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)一個(gè)狀態(tài)k kj j，把把k kj j稱作稱作k ki i的一個(gè)后繼狀態(tài)；的一個(gè)后繼狀態(tài)；4.4. K K的一個(gè)的一個(gè)；5.5. K K一個(gè)一個(gè)，終態(tài)也稱，終態(tài)也稱可接受狀態(tài)可接受狀態(tài)或或結(jié)束狀態(tài)結(jié)束狀態(tài)。例：例：DFA M=DFA M=（S,U,V,Q, a,b, f, S, QS,U,V,

17、Q, a,b, f, S, Q）其中其中 f f 定義為：定義為：f f（S S，a a）=U=Uf f（V V，a a）=U=Uf f（S S，b b）=V=Vf f（V V，b b）=Q=Qf f（U U，a a）=Q=Qf f（Q Q，a a）=Q=Qf f（U U，b b）=V=Vf f（Q Q，b b）=Q=Q（1 1）DFA DFA 的狀態(tài)圖表示的狀態(tài)圖表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVaaaba，bQb（2 2）DFA DFA 的矩陣表示的矩陣表示f（S，a）=Uf（V，a）

18、=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QabSUVUQVVUQQQQ字符字符狀態(tài)狀態(tài)0100終態(tài)行在表的右端標(biāo)以終態(tài)行在表的右端標(biāo)以1 1，非終態(tài)標(biāo)以，非終態(tài)標(biāo)以0 0。 =a=a，aa，* *，則有：，則有：a a其中其中QKQK。 即：即： * *，S S為為DFA MDFA M的開(kāi)始狀態(tài)，的開(kāi)始狀態(tài)，P P Z Z，Z Z為終為終態(tài)集。若態(tài)集。若f(Sf(S，)=P)=P，則稱則稱為為DFA MDFA M所所。對(duì)于對(duì)于 * *中的符號(hào)串中的符號(hào)串，若存在一條從初態(tài)到某，若存在一條從初態(tài)到某一終態(tài)的道路，且這條路上所有弧上的符號(hào)連

19、一終態(tài)的道路，且這條路上所有弧上的符號(hào)連接成符號(hào)串接成符號(hào)串 ，則稱，則稱為為DFA MDFA M所識(shí)別所識(shí)別例：證明例：證明=baab=baab被如下的被如下的DFADFA所接受。所接受。bSUVQaaaba，bb證明證明： f（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)。得證屬于終態(tài)。得證。 DFA MDFA M所能識(shí)別的符號(hào)串的全體記為所能識(shí)別的符號(hào)串的全體記為L(zhǎng)(M)L(M) 結(jié)論：結(jié)論： 上一個(gè)字符串集上一個(gè)字符串集V V 是正規(guī)的，當(dāng)且僅當(dāng)存在是正規(guī)的，當(dāng)且僅

20、當(dāng)存在一個(gè)一個(gè) 上的確定有窮自動(dòng)機(jī)上的確定有窮自動(dòng)機(jī)M M，使得使得V=L(M)V=L(M)。DFA M=（K，f，S，Z）的算法的算法:R:=S；c:=getchar;while ceof and RK do R:=f(R,c); c:=getchar; ;if R is in Z then return (yes) else return (no)二、不確定的有窮自動(dòng)機(jī)二、不確定的有窮自動(dòng)機(jī)NFANFA 定義定義 N= N=KK，f f，S S，ZZ，其中其中的有窮非的有窮非空空， 有窮輸入有窮輸入，K K * * 到到K K的的子集子集的的， K K始狀始狀， K K止止?fàn)顮?。例例NFA

21、 N=（S，P，Z，0，1，f，S，P，Z）其中其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=PSPZ00,1111狀態(tài)圖表示狀態(tài)圖表示表格表示表格表示01SPS,Z0PZ0ZPP1簡(jiǎn)化為簡(jiǎn)化為01SPS,Z0P.Z0ZPP1NFA N=（S，P，Z，0，1，f，S，P，Z）其中其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=P狀態(tài)集合狀態(tài)集合I I的有關(guān)運(yùn)算：的有關(guān)運(yùn)算： 1 1、狀態(tài)集合、狀態(tài)集合I I，定義，定義I I的的 - -閉包閉包 -closure(I)=I-closure(I)=I ss| |從某

22、個(gè)從某個(gè)s s I I出發(fā)經(jīng)過(guò)任意條出發(fā)經(jīng)過(guò)任意條 弧能到達(dá)弧能到達(dá)s s 2 2、狀態(tài)集合、狀態(tài)集合I I的的a a弧轉(zhuǎn)換弧轉(zhuǎn)換定義：定義： move(I,a)=s move(I,a)=s| |從某個(gè)從某個(gè)s s I I出發(fā)經(jīng)過(guò)一條出發(fā)經(jīng)過(guò)一條a a弧能到弧能到達(dá)達(dá)s s I=1, -closure(I)=1,2；I=5, -closure(I)=5,6,2； -closure(5,3,4)=5,3,4,6,2,8,7；move(1,2,a)=5,4,3; -closure(move(1,2,a)= -closure(5,3,4)= 5,4,3,6,2,8,7；12534687aaa -cl

23、osure(I)=I-closure(I)=I ss| |從從某個(gè)某個(gè)s s I I出發(fā)經(jīng)過(guò)任意條出發(fā)經(jīng)過(guò)任意條 弧能到達(dá)弧能到達(dá)s s move(I,a)=smove(I,a)=s| |從某個(gè)從某個(gè)s s I I出發(fā)經(jīng)過(guò)一條出發(fā)經(jīng)過(guò)一條a a弧弧能到達(dá)能到達(dá)s s NFANFAD DFAFA的過(guò)程的過(guò)程( (子集法子集法):): 假設(shè)假設(shè)NFA N=(K,NFA N=(K,f,K,f,K0 0,K,Kt t) )按如下辦法構(gòu)造一個(gè)按如下辦法構(gòu)造一個(gè)DFA M,DFA M,使得使得L(M)=L(N)L(M)=L(N). . 不失一般性，設(shè)不失一般性，設(shè)=a,ba,b，我們構(gòu)造一張表，我們構(gòu)造一

24、張表: : 狀態(tài)狀態(tài)= -closure(move(Ti,a)= -closure(move(Ti,b)T0= -closure( )TaTbK0首先，置第首先，置第1 1行第行第1 1列為列為 -closure(K-closure(K0 0) )求出這一求出這一列的列的T Ta a，T Tb b；然后，檢查這兩個(gè)然后，檢查這兩個(gè)T Ta a，T Tb b，看它們是否已在表中，看它們是否已在表中的第一列中出現(xiàn)，把未曾出現(xiàn)的填入后面的空行的第一列中出現(xiàn)，把未曾出現(xiàn)的填入后面的空行的第的第1 1列上，求出每行第列上，求出每行第2 2，3 3列上的集合列上的集合.重復(fù)上述過(guò)程，直到所有第重復(fù)上述過(guò)程

25、，直到所有第2 2，3 3列子集全部出現(xiàn)列子集全部出現(xiàn)在某行第一列為止。在某行第一列為止。 狀態(tài)狀態(tài)= -closure(move(Ti,a)= -closure(move(Ti,b)T0= -closure( )TaTbK0例例 將下圖的將下圖的NFA NNFA N轉(zhuǎn)換成轉(zhuǎn)換成DFA MDFA M023456789101bbbaaNFA N023456789101bbbaa 狀態(tài)狀態(tài)T0= -closure(0) =0,1,2,4,71,2,3,4,6,7,8=T11,2,4,5,6,7=T2T1= 1,2,3,4,6,7,8T11,2,4,5,6,7,9 =T3T2= 1,2,4,5,6,

26、7T1T2T3= 1,2,4,5,6,7,9T1T4T4= 1,2,4,5,7,10T1T2NoImage= -closure(move(Ti,a)Ta= -closure(move(Ti,b)Tb 現(xiàn)在把這張表看成一個(gè)狀態(tài)轉(zhuǎn)換矩陣，把其中現(xiàn)在把這張表看成一個(gè)狀態(tài)轉(zhuǎn)換矩陣，把其中的每個(gè)子集看成一個(gè)狀態(tài)。的每個(gè)子集看成一個(gè)狀態(tài)。 這張表唯一刻劃了一個(gè)確定的有限自動(dòng)機(jī)這張表唯一刻劃了一個(gè)確定的有限自動(dòng)機(jī)M M，它，它的初態(tài)是的初態(tài)是 -closure(K-closure(K0 0) ) ，它的終態(tài)是含有原，它的終態(tài)是含有原終態(tài)終態(tài)K Kt t的子集。的子集。 不難看出，這個(gè)不難看出，這個(gè)DFA M

27、DFA M與與M M等價(jià)。等價(jià)。 -closure(move(Ti,a) -closure(move(Ti,b)T0= -closure(0) =0,1,2,4,7 1,2,3,4,6,7,8=T1 1,2,4,5,6,7 =T2T1= 1,2,3,4,6,7,8 T1 1,2,4,5,6,7,9 =T3T2= 1,2,4,5,6,7 T1 T2T3= 1,2,4,5,6,7,9 T1 T4T4= 1,2,4,5,7,10 T1 T2初態(tài)初態(tài)終態(tài)終態(tài)b02134abaaaabbbDFA M取取T Ti i的下標(biāo)的下標(biāo)i i為為狀態(tài)名狀態(tài)名四、四、DFADFA的最小化（化簡(jiǎn)）的最小化（化簡(jiǎn)） 最

28、小狀態(tài)最小狀態(tài)DFADFA 沒(méi)有多余狀態(tài)沒(méi)有多余狀態(tài)( (死狀態(tài)死狀態(tài)) ) 沒(méi)有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）沒(méi)有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別） 多余狀態(tài)：多余狀態(tài)：從自動(dòng)機(jī)的開(kāi)始狀態(tài)出發(fā)，任何輸從自動(dòng)機(jī)的開(kāi)始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)入串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒(méi)有通路到達(dá)終態(tài)。沒(méi)有通路到達(dá)終態(tài)。消除多余狀態(tài)消除多余狀態(tài)s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0

29、s1s2s3s5s7 兩個(gè)狀態(tài)兩個(gè)狀態(tài)s s和和t t等價(jià)等價(jià), ,滿足滿足: : 一致性一致性同是終態(tài)或同是非終態(tài)同是終態(tài)或同是非終態(tài) 蔓延性蔓延性從從s s出發(fā)讀入某個(gè)出發(fā)讀入某個(gè)a(a(a a)和從和從 t t出發(fā)出發(fā)讀入某個(gè)讀入某個(gè)a a到達(dá)的狀態(tài)等價(jià)。到達(dá)的狀態(tài)等價(jià)。 狀態(tài)狀態(tài)2 2和和4 4是不等價(jià)的是不等價(jià)的( (可區(qū)別的可區(qū)別的) )。b02134abaaaabbbDFA M2 2是非終態(tài)而是非終態(tài)而4 4是終態(tài)是終態(tài)狀態(tài)狀態(tài)2 2和和3 3是不等價(jià)的，因?yàn)樽x入是不等價(jià)的，因?yàn)樽x入b b后分別到后分別到達(dá)達(dá)2 2和和4 4，而，而2 2和和4 4是不等價(jià)的。是不等價(jià)的。 對(duì)于一

30、個(gè)對(duì)于一個(gè)DFA M =DFA M =（K,f,kK,f,k0 0,k,kt t) )，存在一存在一個(gè)最小狀態(tài)個(gè)最小狀態(tài)DFA MDFA M = =（K K,f,f,k,k0 0,k,kt t),),使使L(ML(M)=L(M).)=L(M). DFADFA的最小化算法的核心：的最小化算法的核心： 把一個(gè)把一個(gè)DFADFA的狀態(tài)分成一些不相交的子的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個(gè)狀態(tài)都是等別的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的價(jià)的. .將下圖中的將下圖中的DFA MDFA M最小化最小化 1,2,

31、3,4,5,6,7Ia: 6,7,1,4,7,4,4Ib: 3,3,5,6,3,1,21352746aaaaaaabbbbbbba13546aaaabbbbb1,2,3,4 5,6,71,2 3,41,256,73 4 56,7 1.1.對(duì)于對(duì)于上的上的NFA MNFA M，可以構(gòu)造一個(gè)，可以構(gòu)造一個(gè)上的上的正規(guī)式正規(guī)式R,R,使得使得L(R)=L(M)L(R)=L(M)。 2 2. .對(duì)于對(duì)于上的一個(gè)正規(guī)式上的一個(gè)正規(guī)式R R，可以構(gòu)造一個(gè)，可以構(gòu)造一個(gè)上的上的NFA MNFA M，使得，使得L L( (M)=L(R)M)=L(R)。 1.1. 對(duì)于對(duì)于上的上的NFA MNFA M，可以構(gòu)造

32、一個(gè)，可以構(gòu)造一個(gè)上的正規(guī)上的正規(guī)式式R,R,使得使得L(R)=L(M)L(R)=L(M)。 第一步：在第一步：在M M的狀態(tài)轉(zhuǎn)換圖上的狀態(tài)轉(zhuǎn)換圖上，一，一個(gè)為個(gè)為x x結(jié)點(diǎn)，一個(gè)為結(jié)點(diǎn)，一個(gè)為y y結(jié)點(diǎn)。從結(jié)點(diǎn)。從x x結(jié)點(diǎn)用結(jié)點(diǎn)用弧連接弧連接到到M M的的，從，從M M的的用用弧連接到弧連接到y(tǒng) y結(jié)點(diǎn)。形成一個(gè)與結(jié)點(diǎn)。形成一個(gè)與M M等價(jià)的等價(jià)的M,MM,M只只有有和和。 第二步：逐步消去第二步：逐步消去M M中的所有結(jié)點(diǎn)，直至只剩下中的所有結(jié)點(diǎn)，直至只剩下x x和和y y。（。（消去規(guī)則見(jiàn)下頁(yè)）消去規(guī)則見(jiàn)下頁(yè)） 最后最后x x和和y y結(jié)點(diǎn)間的弧上的標(biāo)記則為所求的正規(guī)式結(jié)點(diǎn)間的弧上的標(biāo)

33、記則為所求的正規(guī)式R R。123R1R213R1 R213R1R213R1| R2123R1R3R213R1 R2* R3例：例：03124a,baaa,ba,bbb求正規(guī)式求正規(guī)式R R03124a,baaa,ba,bbbxy024a|baaa|ba|bbbxy024a|baaa|ba|bbbxy0a|baa(a|b)*bb(a|b)*xy0a|baa(a|b)*bb(a|b)*xyxy(a|b)* (aa |bb)(a|b)*0a|bxyaa(a|b)* |bb(a|b)*(aa |bb)(a|b)*R=(a|b)* (aa |bb)(a|b)*2 2. .對(duì)于對(duì)于上的一個(gè)正規(guī)式上的一個(gè)正

34、規(guī)式R R，可以構(gòu)造一個(gè)，可以構(gòu)造一個(gè)上的上的NFA MNFA M，使，使得得L L( (M)=L(R)M)=L(R)。(1)R=(1)R=(3)R=a(3)R=a(2)(2)R=R= (4)R=s|t(4)R=s|txyxy xya axyNFA(s)NFA(s)NFA(t)NFA(t) xys st t或或(5)R=st(6)R=s*NFA(s)NFA(s)NFA(t)NFA(t) NFA(s)NFA(s)xy xx1yst或或xx1y s或或例：例：為為構(gòu)造構(gòu)造NFA NNFA N，使得使得L(N)=L(R)L(N)=L(R)。23a54b2354ab16解法一：解法一：2354ab162354ab1607繼續(xù)加上繼續(xù)加上abbabb即可得到結(jié)果。即可得到結(jié)果。xiy(a|b)*abbxjyabbia|bxjyabbiab繼續(xù)對(duì)繼續(xù)對(duì)abbab