《編譯原理》樣卷及答案

1、編譯原理樣卷及答案一、簡(jiǎn)答題(每題4分，共24分)1、構(gòu)造一個(gè)文法G,使得：L (G) = (,n),n | m0解答： GS : s- () I (S)2、構(gòu)造一個(gè)正規(guī)式，它接受S=0, 1上符合 以下規(guī)則的字符串：串內(nèi)有且只有2個(gè)1的 0、1字符串全體。解答： 0*10*10*3、消除文法GS中的直接左遞歸和回溯Sf (L) I aS I aLf L, SIS解答：s- (L)laS*SJ SlL SLLf SLl4、文法GS是喬姆斯基幾型文法?S-ABS|ABAB-BAA-0解答：1型文法/上下文有關(guān)文法5、按Thmopson算法構(gòu)造與正則表達(dá)式(1*|0)*等價(jià) 的 NFAo解答6、如

2、t甘一個(gè)狀態(tài) 以a ;如a、b組成的任意符p中。解答二、(本題10分)對(duì)于文法GE：E-ET+|TT-TF* | FF-FA | a(1) 給出句子FF的最左推導(dǎo)和語(yǔ)法樹；(2) 給出句子Fi的短語(yǔ)、直接短語(yǔ)和句柄。(1) 2分：句子 句子的語(yǔ)法樹PPA 人* 的最左推導(dǎo)E=T=TF*=FF*=FFA*=FFAA*(2) 3分：句子FF*的短語(yǔ)ff“*、FF*、F、Fa Faa 2分:句子 FF* 的直接短語(yǔ)F、FA1分:句子FF*的句柄三、(本題15分)構(gòu)造與下列NFA等價(jià)的最小 化 DFA。iI.(SAB0JC11221nwq3RB2冏12(D,E 刀3(H.454554S解答：（1） 1

3、0分：構(gòu)造與NFA 等價(jià)的DFA（2） 5分：對(duì)DFA最小化首先，將所有的狀態(tài)集合分成子集: kl=0,lz2z4k2=3z5在Kt=0, 1 2, 4中，因?yàn)闋顟B(tài)1、4沒有a輸人，而其它狀態(tài)均有a輸人, 折以將狀態(tài)K1分割成Ku=0, 2和 Kir=K 4在狀態(tài)2中.有O.=1eK22產(chǎn)1心2t）=2eK|j 所以狀態(tài)0與狀態(tài)2等價(jià)，在狀態(tài)集K薩1, 4中，有Ib=3Kj弘書丘所以狀態(tài)1與狀態(tài)4是否等價(jià)取決于狀態(tài)3和狀杰5是否竽價(jià).在狀杰集Kr=3, 5中，有3t=4Ki25a=4eKn3b=5eK25b=5GK2折以狀態(tài)3與狀杰5等價(jià)，從而狀恚I與狀態(tài)4等價(jià).最終將K分割戍三個(gè)不相交的子集

4、 （0.為、I, 4、3, 5.選0, 2中的0作為代表.，原來由狀態(tài)2導(dǎo)入（出）體余狀態(tài)的孤改為由狀 態(tài)0導(dǎo)人（出：逸】，4中的丨作為代埶 原來由狀態(tài)4導(dǎo)人（tfa）其余狀態(tài)的 炎改為由狀態(tài)1導(dǎo)入（出）：選3, 5中的3作為代表，原來由狀態(tài)5導(dǎo)人（出） 其余狀態(tài)的弧改為由狀態(tài)3導(dǎo)入（岀）；然后洎去其余伏態(tài).最小化后的狀態(tài)圖如 圖所示四、（本題15分）對(duì)下列文法GS：eT I RTT DR I R dR I wD a I bd(1) 寫出文法GS每個(gè)非終結(jié)符的FIRST 集和FOLLOW集；(2) 判斷文法GS是否LL(1)文法(注：必 須給出判斷過程，否則不得分)；(3) 寫出文法文法GS的

5、預(yù)測(cè)分析表。解答：(1) 8分：每個(gè)First集合和FOLLOW 集合各1分FIRST 集6FOLLOW集s eTIRTe a, b, d, e#Tt DRa,b#1 ERdRda,b,#1 打D aaD,#Ibdb(2) 2 分:判斷文法G S是LL文法。對(duì)于產(chǎn)生式 st eT I RT： FIRST (eT) Cl FIRST (RT) - =e D a, b, d二FIRST (eT)PIFOLLOW(S)=e D #二對(duì)于產(chǎn)生式 Tt DR I e： FIRST (DR) Cl FOLLOW(T)=a,b D # = 對(duì)于產(chǎn)生式 Rt dR I ： FIRST (dR) Cl FOLL

6、OW (R)=d Cl a, b, #二對(duì)于產(chǎn)生式 D- a I bd： FIRST (a) Cl FIRST(bd)=a Cl b二所以，對(duì)于文法GS是LL(1)文法。(3) 5分:文法GS的預(yù)測(cè)分析表。abdc#SRTRTRTeTRTTDRDRR8dREDabd五、(本題18分)已知文法GS：S-rD(1)畫出識(shí)別文法活前綴的完整DFA,并判斷該文法是否LR(O)文法(必須說明判斷依據(jù))； 構(gòu)造該文法的SLR分析表，并判斷該文 法是否SLR(1)文法(必須說明判斷依據(jù))o 解答：(1) 8分：畫出識(shí)別文法活前綴的完整DFA文法拓展并對(duì)產(chǎn)生式編號(hào):D i(O) S JS (1) S-rD(2

7、) 2分：判斷該文法不是LR(O)文法 對(duì)于狀態(tài)3,項(xiàng)目集中存在“移進(jìn)-規(guī)約”沖突，所以該文法不是LR(O)文法。(3) 6分：構(gòu)造該文法的SLR(1)分析表狀態(tài)ACTIONGOTOr91#SD0S211acc2S433S5rl4r3r35S66r2r2(4) 2分:判斷文法是SLR分析表回答1：因?yàn)镾LR (1)分析表不存在沖 突，所以文法是SLR(l)分析表。回答2： 對(duì)于狀態(tài)3, FOLLOWCI 移進(jìn)-規(guī)約”沖突可以用SLR (1)方法解決，所以文法是SLR分析表。六二(本題8分)文法Ge的LR分析表如下圖(1)E E+T(2)E T(3)TT*F(4)T F(5)F (E)(6)F寫

8、出對(duì)輸入備i*i + i的LR分析過程(即狀 態(tài)，符號(hào)，輸入串的變化過程)。解答:狀態(tài)符號(hào)輸入串(1)0#i*i+i#(2)05#i*i+l#(3)03#F* i + i #(4)02#T*i + i#(5)027#T*i + i#(6)0275#T*i+ i#(7)02710#T*FH#(8)02#T+ j#(9)01#E+ i#狀態(tài)ACTION(動(dòng)作)GOTO(轉(zhuǎn)換)/+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5七、(本題10分)寫出下列語(yǔ)句的四元式序列if(yz & (cn)while(ab)x=x+y*a;elsem=m+n;解答:2345678910111213141516(j， 厶 3) (j，丁，13)