編譯原理第五章答案

1、第5章 自頂向下語(yǔ)法分析方法第1題對(duì)文法GSSt a|(T) AT,S|S(1) 給出(a,(a,a)和(a,a),(a),a) A 的最左推導(dǎo)。(2) 對(duì)文法G,進(jìn)行改寫(xiě)，然后對(duì)每個(gè)非終結(jié)符寫(xiě)出不帶回溯的遞歸子程序。(3) 經(jīng)改寫(xiě)后的文法是否是 LL(1)的？給出它的預(yù)測(cè)分析表。(4) 給出輸入串(a,a)#的分析過(guò)程，并說(shuō)明該串是否為G的句子。答案：(1)對(duì)(a.(a.a)的最左推導(dǎo)為;S=(T)=(T5)=(S.S)=(a.S)=(乩(功=(a.(T.S)二(乩(心)=(aXa.a)對(duì)(a.a).A.(a).a)的最左推導(dǎo)為: sn(T)=(T.S)=(S.S)=(T).S)d(TS).

2、S)=(T.S.S).S)二(SSS)、S)=(T).S.S).S)=(T.S).S.S).S)=(S.S).S.S).S)=(a.S).S.S).S) =(a.a).S.S),S)=(a,a)人S),S) 二(3)人(T)$) =(a.a),A.(S).S)=(a.a).A.(a),S)=(a,a),/,(a),a)(2)改寫(xiě)文法為：0) S-a1) St/2) S-( T )3) T-*S N4) NS N5) Nt非終結(jié)符FIRST 集FOLLOW 集Sa.A,(Tr)N)燉左部為N的產(chǎn)主成町知；FIRSTSN) FIRST JG)所用產(chǎn)生式(OPERATION)(”T(#)TaT-*S

3、N#)K5a.a)#S#)Xaa,a)#qa)#Nf SNpNS,a)#杯NSa胖Sa)#Nf)#可見(jiàn)輸入串(a,a) #是文法的句子。第3題已知文法GS:St MH|a3 LSo| &Kt dML| Lt eHfMT K|bLM判斷G是否是LL(1)文法，如果是，構(gòu)造 LL(1)分析表。文法展開(kāi)為：0)M H1)S*32)H7 S o3)Hr4)Kd M L5)Ke6)Le H f7)M-K8)Mb L M非終結(jié)符FIRST 集FOLLOW 集sa,d,b.e,eMdXbe.#.oH,L何Ke.#.o對(duì)相同店部的產(chǎn)臨武町知：SELECTfSM H)nSE匚町= d.b .e+ #,o D a

4、 =0 SELECT(H-L S o)nSELECT(He) = e 仃 #,f=& SELECT(Kd M L)ASELECT(K) =d fl eJ.o 卜它 SELECT(MK)ASELECT(Mb LM)=d, e,#.o )0 b =2! 所以立法LL(1)的。預(yù)測(cè)分析表za0defb# Ts證MHMHtIHMH一 MHMKKtKb 匸 14-KHLScELeHfKdMLE宙預(yù)測(cè)分析表中無(wú)參乘入口也可判定文法LL(l)的.第7題對(duì)于一個(gè)文法若消除了左遞歸，提取了左公共因子后是否一定為L(zhǎng)L(1)文法？試對(duì)下面文法進(jìn)行改寫(xiě)，并對(duì)改寫(xiě)后的文法進(jìn)行判斷。(1 )A t baB| Bt Abb

5、|a A t aABe|a Bt Bb|d(3) S t Aa|b At SBBt ab答案：(1 )先改寫(xiě)文法為:0) A t baB1) A t 2) B t baBbb3) B t bb4) B t a再改寫(xiě)文法為：0) A t baB1) A T 2) B t bN3) B t a4) N t aBbb5) N t bFIRSTFOLLOWAb#Ba俄bNb.a#.b 預(yù)測(cè)分析表;ab#A-baBB-*bNN-aBbb一 b由預(yù)測(cè)分析表屮無(wú)多丑入I I判定文法是1X(1)的。(2) 文法：At aABela B t Bb|d提取左公共因子和消除左遞歸后文法變?yōu)椋?) A t a N1)

6、 N t a B e2) N T&3) B t d N14) N1 t b N15) N1 f非終結(jié)符FIRST 集FOLLOW 集Aa燦BdJNa-0燦nN1咲對(duì)相同左部的產(chǎn)生式叮知：SELECTtNA B e)PSELECT(N) = a )0 #.d SELECT(Nl-b Nl)nSELECT(Nl-)= b M e 所以文法堆LL(1)的。偵測(cè)分折表 Predictina Aiialy 山 Table)aebd#A-*aNBdNlN1&bNlNABe也可由預(yù)測(cè)分析表中無(wú)多重入口判定文法ft LL(1)的“(3)文法：St Aa|b A 宀 SBab第1種改寫(xiě)：用A的產(chǎn)生式右部代替 S的產(chǎn)生式右部的 A得：St SBa|b B t ab消除左遞歸后文法變?yōu)椋?) S t b N1) N t b a N2) N t3) B t a b非終結(jié)符FIRST 集F