編譯原理與技術(shù)5

1、第第 頁（共8頁）對應(yīng)的DFA如下圖所示:(3)最小化過程如下：初始劃分為：ni=ABE,CD考查狀態(tài)轉(zhuǎn)移，由于：TOC o 1-5 h zm(A,a)=Bm(A,b)=-m(B,c)=-m(B,a)=-m(B,b)=Cm(B,c)=Dm(E,a)=-m(E,b)=Cm(E,c)=D因此，B和E不可區(qū)分，用B代表B,E得到劃分口2=AB,CD再考查狀態(tài)轉(zhuǎn)移：m(A,a)=Bm(A,b)=-m(A,c)=-m(B,a)=-m(B,b)=Cm(B,c)=D因此，A和B可區(qū)分，得到劃分口2=A,B,CD再考查狀態(tài)轉(zhuǎn)移：m(C,a)=Em(C,b)=Cm(C,c)=Dm(D,a)=Em(D,b)=-m

2、(D,c)=-因此，C、D是可區(qū)分的狀態(tài)，因此得到最終劃分：nfinal=A,B,C,D最小DFA如下圖所示：解釋：用算法2.2Thompson算法從正規(guī)式構(gòu)造出與其對應(yīng)的NFA；用子集法（算法2.3）將NFA轉(zhuǎn)換為DFA。其中需要用算法2.4計(jì)算狀態(tài)集T的-閉包（T）。利用狀態(tài)可區(qū)分的概念球最小化DFA。對于任何兩個(gè)狀態(tài)t和s,若從一狀態(tài)出發(fā)接受輸入字符串3,而從另一狀態(tài)出發(fā)不接受3,或者從t出發(fā)和從s出發(fā)到達(dá)不同的接受狀態(tài)，則稱3對狀態(tài)t和s是可區(qū)分的。反方向思考以上定義，設(shè)想任何輸入序列3對S和t均是不可區(qū)分的，則說明從S出發(fā)和從t出發(fā)，分析任何輸入序列3均得到相同結(jié)果。因此，S和t可以

3、合并成一個(gè)狀態(tài)。4.2(15分)設(shè)文法G：SaAAAbcIc(9分)拓廣該文法并構(gòu)造基于1區(qū)(0)項(xiàng)目的、能識別其所有活前綴的DFA。(6分)該文法是否是LR(0)文法？是否為SLR(1)文法？為什么？答案：(1答案：(1)拓廣文法為G:S-SS-aAA-AbcIc,DFA如下:(2)不是LR(0),是SLR(1),因?yàn)榧哟猪?xiàng)目集中存在移進(jìn)/歸約沖突，且Follow(S)和First(bc)不相交，即沖突可通過簡單向前看一個(gè)終結(jié)符解決。解釋：用算法3.9計(jì)算文法基于10)項(xiàng)目的識別活前綴的DFA。當(dāng)DFA的一個(gè)項(xiàng)目集中同時(shí)存在：A-B1.B2和B-B.：說明下一步既可以移進(jìn)又可以歸約，引起移進(jìn)/歸約沖突。A-a.和B-B.：說明二者均可以指導(dǎo)下一步分析，引起歸約/歸約沖突。解決沖突的方法是簡單向前看一個(gè)終結(jié)符a：.對于移進(jìn)/歸約沖突：若FIRST(B2)nFOLLOW(B)=中，沖突可以解決。.對于歸約/歸約沖突：若FOLLOW(A)nFOLLOW(B)=中，沖突可以解決。若沖突可以解決，