編譯原理第五章-課后題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第五章1.1考慮下面表格結(jié)構(gòu)文法G2S->a|(T)T->T,S|S指出(a,a), ,(a),a)的規(guī)范規(guī)約及每一步規(guī)約的句柄。根據(jù)這個規(guī)范規(guī)約，給出“移進(jìn)-規(guī)約”的過程，并給出它的語法樹自下而上構(gòu)造的過程。答:： 規(guī)范規(guī)約 該步規(guī)約時的句柄(a,a), ,(a),a) a=> (S,a), ,(a) ,a) S=> (T,a), ,(a) ,a) a=> (T,S), ,(a) ,a) T,S=> (T), ,(a) ,a) （T）=> (S, ,(a) ,a) S=> (T, ,(a) ,a) => (T,

2、S,(a) ,a) T, S => (T,(a) ,a) a=> (T,(S) ,a) S=> (T,(T) ,a) (T)=> (T,S) ,a) T, S=> (T) ,a) (T)=> (S,a) S=> (T, a) a=> (T, S) T, S=> (T) (T)=> S“移進(jìn)-規(guī)約”的過程：符號棧 輸入串 動作# (a,a), ,(a),a) # 預(yù)備#( (a,a), ,(a),a) # 進(jìn)#( (a,a), ,(a),a) # 進(jìn)#( a,a), ,(a),a) # 進(jìn)#(a ,a), ,(a),a) # 進(jìn)#(S

3、,a), ,(a),a) # 歸，用S->a#(T ,a), ,(a),a) # 歸，用T->S#(T, a), ,(a),a) # 進(jìn)#(T,a ), ,(a),a) # 進(jìn)#(T,S ), ,(a),a) # 歸，用S->a#(T ), ,(a),a) # 歸，T->T,S#(T) , ,(a),a) # 進(jìn)#(S , ,(a),a) # 歸，用S->(T)#(T , ,(a),a) # 歸，用T -> S #( T, ,(a),a) # 進(jìn)#( T, ,(a),a) # 進(jìn)#( T, S ,(a),a) # 歸，用S->#( T ,(a),a)

4、# 歸，用T->T,S#( T, (a),a) # 進(jìn)#( T, ( a),a) # 進(jìn)#( T, (a ),a) # 進(jìn)#( T, (S ),a) # 歸，用S->a#( T, (T ),a) # 歸，用T -> S#( T, (T) ),a) # 進(jìn)#( T, S ),a) # 歸，用S->(T)#( T ),a) # 歸，用T->T,S#( T) ,a) # 進(jìn)#(S ,a) # 歸，用S->(T)#(T ,a) # 歸，用T ->S #(T, a) # 進(jìn)#(T, a ) # 進(jìn)#(T, S ) # 歸，用S->a#(T )# 歸，用T-

5、>T,S#(T) # 進(jìn)#S # 歸，用S->(T)接受。語法樹（略）3 （1）計算練習(xí)2的文法G2S->a|(T)T->T,S|S的FIRSTVT和LASTVT。 （2）計算G2的優(yōu)先關(guān)系。G2是一個算符優(yōu)先文法嗎？ （3）給出輸入串(a,(a,a)的算符優(yōu)先分析過程。答：（1）(2) GS的算符優(yōu)先關(guān)系表：  a ( ) , # a       (     )       ,         #      

6、因為該文法是OP，同時任意兩個終結(jié)符的優(yōu)先關(guān)系唯一，所以該文法為OPG。（3）句子(a, (a, a)分析過程如下：4.對下面文法： S->AS | b A->SA | a(1) 列出該文法所有的LR(0)項目。(2) 構(gòu)造這個文法的LR(0)項目集規(guī)范族及識別活前綴的DFA答：文法拓廣：S->SS->AS | b A->SA | aLR（0）項目：S->SS->SS->ASS->ASS->ASS-> bS-> b A->SA A->SA A->SAA->aA->aLR(0)項目集規(guī)范族及識別

7、活前綴的DFA如下圖所示：FOLLOW(S)=#,a,b FOLLOW(A)=a,bS->SS->ASS-> bA->SAA->aS->SA->SAS->ASS-> bA->SAA->aSS->ASS->ASS-> bA->SAA->aAS-> bbA->aaS->ASA->SAA->SAA->aS->ASS-> bSAababA->SAS->ASA->SAA->aS-> bS->ASAA->SAA->S

8、AA->aS->ASS-> bSabASbaSAbaAS7.證明文法是SLR(1)的但不是LR(0)的：S->AA->Ab|bBaB->aAc|a|aAb答：(1) 證明不是LR(0):因為項目集規(guī)范族的I3 中，有移進(jìn)和歸約的沖突。所以不是LR(0)的(2)證明是SLR(1)的提示：上圖繼續(xù)畫完，找出所有沖突的情況，根據(jù)SLR(1)解決辦法可以解決，(過程略)所以為SLR(1)的或構(gòu)造出SLR分析表，無多重定義入口，所以是SLR的證明文法：ABaBb|DbDaBD是LR(1)但不是SLR(1)。（說明：書中的S為這里的A；書中的A為這里的B；書中的B為這里

9、的D；）答： 拓廣文法為G，增加產(chǎn)生式SA若產(chǎn)生式排序為：0 S'A1 A BaBb 2 A DbDa3 B 4 D 由產(chǎn)生式知： First (S' ) = a,b First (A ) = a,bFirst (B ) = First (D ) = Follow(S' ) = #Follow(A ) = # Follow(B ) = a,bFollow(D ) = a,bG的LR(1)項目集族及識別活前綴的DFA如下圖所示： (修正:上圖里左上角的I1應(yīng)為:S->A，圖里把向前搜索符漏掉了，因為是插入的圖片不好修改，這里更正一下)在I0中：B ,a和D ，b為歸約項目，但它們的搜索符不同，若當(dāng)前輸入符為a時用產(chǎn)生式B 歸約，為b時用產(chǎn)生式D 歸約，所以該文法是LR(1)文法。若不看搜索符，在I0中項目B 和D為歸約-歸約沖突，而Follow(B ) Follow(D ) = a,b a,b，沖突不能用Follow集解決