2023年編譯模擬試題及答案

《編譯原理》模擬試題班級學號姓名評分填空1.文法G涉及四個組成部分:一組終結(jié)符號，，一組產(chǎn)生式,以及。2.文法按產(chǎn)生式的形式分為四種類型，它們是：0型文法,又稱短語文法;1型文法，又稱上下文有關(guān)文法;2型文法，又稱文法;３型文法,又稱文法。3.推導稱為規(guī)范推導，由產(chǎn)生的句型稱為規(guī)范句型。4．設(shè)G是一個文法,S是它的開始符號，假如Ｓα，則稱α是一個句型。的句型是一個句子。5對于一個文法G而言，假如L(Ｇ)中相應(yīng)，那么該文法就稱為是二義的。6.通常程序設(shè)計語言的單詞符號分為五種:基本字、、常數(shù)、、界線符。7．在自底向上分析法中，ＬR分析法把“可歸約串”定義為。８．編譯中常用的中間代碼形式有逆波蘭式、、和四元式等。9.對中間代碼優(yōu)化按涉及的范圍分為局部優(yōu)化,和。１0．局部優(yōu)化重要涉及合并已知量、和等內(nèi)容。二、編譯過程通常分為哪幾個重要階段?每個階段的重要功能?三、設(shè)有文法G1G１:S→SaＱ1.證明句型QｂRae是規(guī)范句型Ｑ→ＱｂＲ∣RR→ｃSd∣e2．給出句型QbRae的短語,直接短語和句柄:短語:直接短語:句柄:四、對于文法G2,填寫各產(chǎn)生式的選擇集合和G2的預測分析表。Ｇ2:①E→TE'SELEＣT(①）＝{}②E'→+TE’ＳELECT（②)＝{}③E'→εSEＬEＣT(③)={}④T→FT＇SEＬECT(④)＝｛｝⑤T'→*FT’SELECＴ(⑤)＝｛}⑥Ｔ'→εSＥＬECT(⑥)＝{}⑦F→(E)ＳELECT(⑦）={}⑧Ｆ→iSＥＬＥCT(⑧）=｛｝＋*()ｉ#EE'ＴT'F五、把下面的語句翻譯成四元式序列。(只給出最后結(jié)果，設(shè)nextstaｔ當前值為10０）whｉｌeA<ＣdoiｆA＜0ｔｈｅnA:=Ａ+1elｓeA:＝A＋2六、用基本塊代碼生成算法生成目的代碼。(假定允許使用R1和R2寄存器，臨時變量Ｔi出基本塊后都不活躍）四元式選?。夷康拇aRVALUEAＶＡLUEＴ1：=A+BT２：＝C-Ｔ1T3:=Ｄ*EＴ4：＝F+ＧT5:=Ｔ3－T4W：＝T2/T5《編譯原理》模擬試題班級學號姓名評分填空1.文法G涉及四個組成部分：一組終結(jié)符號，一組非終結(jié)符號，一組產(chǎn)生式,以及一個開始符號。2．文法按產(chǎn)生式的形式分為四種類型,它們是：0型文法,又稱短語文法；1型文法,又稱上下文有關(guān)文法;2型文法,又稱上下文無關(guān)文法;３型文法，又稱正規(guī)文法。3.最右推導稱為規(guī)范推導,由規(guī)范推導產(chǎn)生的句型稱為規(guī)范句型。4．設(shè)G是一個文法，S是它的開始符號,假如Ｓ＝*>α，則稱α是一個句型。僅由終結(jié)符號組成的句型是一個句子。5對于一個文法G而言,假如L(G)中存在某個句子相應(yīng)兩棵不同的語法樹，那么該文法就稱為是二義的。6．通常程序設(shè)計語言的單詞符號分為五種:基本字、標記符、常數(shù)、算符、界線符。7．在自底向上分析法中,LＲ分析法把“可歸約串”定義為句柄。８．編譯中常用的中間代碼形式有逆波蘭式、三元式、樹代碼和四元式等。9.對中間代碼優(yōu)化按涉及的范圍分為局部優(yōu)化，循環(huán)優(yōu)化和全局優(yōu)化。１0．局部優(yōu)化重要涉及合并已知量、運用公共子表達式和刪除無用賦值等內(nèi)容。１1.為了構(gòu)造不帶回溯的遞歸下降分析程序，我們通常要消除左遞歸和提取左公共因子二、編譯過程通常分為哪幾個重要階段?每個階段的重要功能？（1５分）答:編譯過程通常分為詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目的代碼生成六個重要階段。各個階段的重要功能如下：詞法分析階段:讀入源程序,對構(gòu)成源程序的字符流進行掃描和分解,辨認出一個個單詞,并表達成計算機內(nèi)部的形式（ＴＯＫＥＮ字)。語法分析階段:在詞法分析的基礎(chǔ)上,將單詞序列分解成各類語法短語,如“表達式”、“語句”、“程序”等，擬定整個輸入串是否構(gòu)成語法上對的的程序。語義分析階段:審查源程序有無語義錯誤,為代碼生成階段收集類型信息。中間代碼生成階段：將源程序翻譯成一種復雜性介于源程序與目的程序之間的內(nèi)部形式(中間代碼)。代碼優(yōu)化:對前階段產(chǎn)生的中間代碼進行等價變換,目的是使將來生成的目的代碼更為高效。目的代碼生成:把中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。三、設(shè)有文法G1G1:S→SaQ∣Ｑ1．證明句型QｂＲａe是規(guī)范句型Q→QbR∣RR→cSd∣e證：由于句型QｂRaｅ可由文法開始符S通過規(guī)范推導產(chǎn)生，推導過程如下:S=R>SａQ=R＞SaR=Ｒ>Sae＝R>Ｑａe=R＞QbRae所以句型ＱbＲae是規(guī)范句型。２.給出句型QbRaｅ的語法樹和句柄:語法樹:句柄:QbＲ四、考慮以下文法:D→ＴVＴ→int|floatV→id,V|id在該文法中提取左公因子。為所得的文法的非終結(jié)符構(gòu)造Fｉrsｔ集合和Ｆollｏｗ集合。說明所得的文法是LL（1)文法。為所得的文法構(gòu)造LL(1)分析表假設(shè)有輸入串intx,ｙ，z寫出相應(yīng)的LL(1）分析程序的動作。答：a.文法存在左公因子,提取左公因子后的文法為：D→ＴVT→iｎt|fｌoaｔV→idV'V'→,V|εb.非終結(jié)符Fｉrst集合Folloｗ集合D{int,fｌｏat}{＄}T｛int,float}{id}V{id}{$}V'｛,,ε｝{$}ｃ.（1)Firsｔ(TV)=｛int,floａt(yī)｝Ｆiｒｓｔ(int)∩Firsｔ(flｏaｔ）={int}∩{floaｔ}=φ;First(idV')={id｝;First（,V）∩Firｓt(ε)={,}∩{ε｝}=φ;(2)V'＝>ε，F(xiàn)irst（Ｖ')∩Folｌoｗ(V')={，,ε｝∩{＄}=φ根據(jù)LＬ（１)文法的定義判斷,此文法是LL(1)文法;d．ＬL(1）分析表為:ｉｎtfloａt(yī)id,$ＤD→TVD→TVTT→ｉntＴ→floatVV→idV＇Ｖ'Ｖ＇→,ＶＶ'→εe.輸入串ｉntx,y,z的LL(1)分析:環(huán)節(jié)分析棧輸入串分析程序的動作1$Ｄinｔx,ｙ,z$D→TV2＄VTinｔx,y,z$Ｔ→ｉnt3$Vintinｔx,ｙ,z＄inｔ匹配4$Ｖｘ,y，z＄V→iｄＶ'5$V'xx,y,z$x匹配6＄V＇,y,z$V＇→,V７$V,,y，z$，匹配８$Ｖy,z$V→ｉdＶ'9＄V'yy，ｚ$ｙ匹配10$V＇,z$Ｖ'→,V１1$Ｖ,,z$,匹配１2$Vｚ$V→iｄV'13$V'zｚ$z匹配1４＄$接受五、考慮以下的文法:E→(Ｌ)｜ａL→L,Ｅ|Ｅa.為這個文法構(gòu)造LR(0)項目的DFA。b．判斷這個文法是否是LR（0)文法?若不是,請描述出ＬR(0）沖突,假如是，則構(gòu)造LR(0）分析表。ｃ.判斷這個文法是否為SＬR(1)文法?若是,構(gòu)造SＬR（１)分析表。d.顯示分析棧和輸入串((a),a,(a,ａ)）的SLＲ（1)分析程序的工作。答:拓廣文法：(0）E’→E(１)E→(L)(2）E→a(３)Ｌ→L,Ｅ(4）L→Eaa(I0：E’→·EE→·(L)E→·aI2：E→(·L)L→·L,EL→·EE→·(L)E→·aA→·dI3：E→a·I1：E’→E·I4：E→(L·)L→L·,EI5：L→E·E(aELI6：E→(L)·),I7：L→L,·EE→·(L)E→·a(aI8：L→L,E·E是LR(0)文法,LR（0)分析表為：ACＴIＯNGOTＯa(),$ＥL0S３S２11ａcc2Ｓ3S２s4543r2r2ｒ２r2ｒ24S6S7５r４r４r４r4r46r1r1ｒ1r1r17S3S288r3r3ｒ３r3ｒ３非終結(jié)符Foｌｌｏｗ集合E’{＄}E｛)，,,$}L｛),,}是SLR(1)文法,ＳLＲ（1)分析表為：ＡＣＴIOＮGOTＯa(),$EＬ0S３S211acc2S3Ｓ2s454３r2r２r24S6S75r4r46r1ｒ1r１７S3S288ｒ3r3環(huán)節(jié)分析棧輸入ＡＣTIONＧOＴO(shè)1$０（（a),a,(a,a))$S2２$0(2(a）,a,(ａ,a）)$S２3$０（２(２ａ),a，(a,a)）$S34$０（2(2a）,a,(a,ａ)）$r255$0(2（２E5),ａ,（a，a）)＄ｒ44６$0(2(2L4)，a,（a,a））$S67$０(2(2L4)6，a,(a,a）)$r158$0(2E5,a,（a,ａ))$r４49＄０（2Ｌ4,ａ,(a,a)）$S710$０(２L４,7ａ,(a,ａ))$S31１＄0(2Ｌ4，7a３,(a,ａ))$ｒ2８12＄0(2L4,７E８,(a，ａ)）$ｒ3413$0(2L４,(a，a))$Ｓ71４$0(2Ｌ４,７(a,ａ))$S２15$0（2L4,7(2a,ａ))$Ｓ316$0(2L4，7(2a3,a)）$r2517$0(2L4,7(2Ｅ5,ａ)）$r4418$0(2L4,7(2L4,a）)$S７19$0(2Ｌ4,7(2Ｌ４,7ａ))$S320$0（2L4，7(２L4,７a3))$ｒ２821$0(2L4,７（2L4,7Ｅ8)）＄ｒ342２$０(2L4,７(2Ｌ4))$Ｓ623＄0(2L4，7（2L4)６)$ｒ1８24＄０(2L4,７E８)$r３425$０(2L4)$S６2６$０（2L4)6$r１１27$0E1$ａcｃ六、把下面的語句翻譯成四元式序列。（只給出最后結(jié)果，設(shè)LABEL當前值為１00）whileA＜CdoiｆA<０thenA:=A+1elseA:=A+２1００:? ｊ＜， A,?Ｃ,?１0210１: ?ｊ, -, -, 11０102: ?ｊ<,?A, 0， 1０4１03: ｊ, －, -, 107１0４: ?＋，?A， 1, T110５:??:=