編譯原理試卷答案

1、 制卷人簽名： 制卷日期： 審核人簽名： 審核日期： 裝 訂線 200 11 年 下 學(xué)期 級 編譯原理 課程考試試卷（A卷） 適用年級專業(yè) 2009級計(jì)算機(jī)科學(xué)與技術(shù)專業(yè) 考試方式 閉卷 考試時(shí)間 120 分鐘學(xué)院 信息工程學(xué)院 專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班級 學(xué)號 姓名 題號一二三四五六七八總分閱卷教師得分得分一、填空題（每小題2 分，共12分）1、一般高級語言的翻譯程序有（ 編譯程序 ）和（ 解釋程序 ）兩種。2、有窮自動(dòng)機(jī)接受的語言是（ 正規(guī)語言 ）3、令a,b，則上所有以b為首的字符串構(gòu)成的正規(guī)集的正規(guī)式為（ b(a|b)* ）。4、下面的語義規(guī)則是某L屬性文法中的一個(gè)語義規(guī)則，從中可

2、看出：A.s是（ 綜合 ）屬性，B.x是( 繼承 )屬性。 A->BCD A.s=B.x+C.y;D.z=B.i;5、活前綴是指（ 規(guī)范句型 ） 的一個(gè)前綴，這種前綴不含（ 句柄 ） 之后的任何符號。6、局部優(yōu)化是在（ 一個(gè)基本塊 ）范圍內(nèi)進(jìn)行的一種優(yōu)化。得分二、簡答題（每小題5分，共計(jì)20分）1、 請說明什么是算符優(yōu)先文法？答：（1）在CFG中無空產(chǎn)生式，且右部無相鄰的非終極符（2）任意兩個(gè)相鄰的終極符間至多只存在一種關(guān)系2、 哪些優(yōu)化措施是主要針對于循環(huán)實(shí)現(xiàn)的？可舉例說明答：代碼外提 強(qiáng)度削弱 歸納變量刪除3、 文法GS：SàS(S)S|e，請判斷GS是否是二義文法，說明理

3、由答：是二義文法 理由：選擇一個(gè)句子，例如（）（），存在有不同的語法樹或者不同的最右推導(dǎo)4、請給出布爾表達(dá)式a or b and e<f利用規(guī)則：E ® id1 rop id2E.TC = NXQ; E.FC = NXQ + 1; Gen(jrop,Entry(id1), Entry(id2), 0); Gen(j, _, _, 0) 進(jìn)行翻譯后的四元式序列？并以此解釋什么是鏈接與回填？答：(1)(jn,a,-,0)(2)(j,-,-,3) 回填(3)(jn,b,-,5) 回填(4)(j,-,-,0)(5)(<,e,f,1) E.TC 鏈接(6)(j,-,-,4)E.FC

4、在翻譯過程中，常常會出現(xiàn)若干轉(zhuǎn)移四元式轉(zhuǎn)向同一目標(biāo)，但此目標(biāo)的具體位置又尚未確定的情況，此時(shí)我們可將這些四元式用拉鏈的辦法將它們鏈接起來，用一指針指向鏈頭，在確定了目標(biāo)四元式的位置之后，再回填這個(gè)鏈。得分三、構(gòu)造一文法，其產(chǎn)生語言集合為 uawb | u,w a, b* 且| u | = | w | ，并說明你所設(shè)計(jì)的文法是屬于喬姆斯基形式文法中的哪一類文法？（10分）答：設(shè)計(jì)GS如下: SàAb Aàa | a Aa | aAb | bAa | bAb 屬于CFG，即上下文無關(guān)文法得分四、有語言 L=w|w (0,1)+，并且 w 中至少有兩個(gè)1 ，又在任何兩個(gè)1之間有偶

5、數(shù)個(gè) 0 ，試構(gòu)造接受該語言的確定有限狀態(tài)自動(dòng)機(jī)（10分）答：得分五、請給對文法GS進(jìn)行改寫成LL（1）文法，并給出改寫后文法的預(yù)測分析表，要求計(jì)算出改寫后文法各非終極符的FIRST和FOLLOW集合。（15分）S S*aA | aA| *aA A +aA | +a 答：改寫文法如下： Sà*aAS | aAS Sà*AS | e Aà+aA AàA | eFIRSTFOLLOWS*，a#S*,e#A+*,#A+,e*,#預(yù)測分析表：*a+#Sà*aASà aASSà*ASàeAà+aAAàe&

6、#224;Aàe得分六、請構(gòu)造出文法GS識別文法活前綴的有限自動(dòng)機(jī)，請確定是否是SLR（1）文法，如果是，則構(gòu)造出其LR分析表。（12分）AaAd |aAb |答：拓廣文法（1）SàA （2）AàaAd （3）AàaA （4）AàASà.A I0Aà.aAdAà.aAbAà.SàA. I1dAaAàa.Ad I2Aàa.AbAà.aAdAà.aAbAà.AàaAd. I4AàaA.d I3AàaA.bbaAà

7、;aAb. I5在I0和I2，I3中存在有移進(jìn)歸約沖突但是FOLLOW（A）=d,b,# a Çd,b,#=F,所以文法是SLR（1）文法abd#AI0S2r4r4r41I1accI2S2r4r4r43I3S5S4I4r2r2r2I5r3r3r3得分七、為文法S ® ( L ) | aL ® L , S | S寫一個(gè)屬性翻譯文法，它輸出文法中a的個(gè)數(shù)。（10分）SàS printf(S.a)S ® ( L ) S.a=L.aSà a S.a=1L ® L , S L.a=L1.a+S.aLà S L.a=S.a得分八、考慮下面的三地址語句序列，完成下列任務(wù)。（1）在該代碼中用水平的橫線將代碼分成基本塊，并給每個(gè)基本塊一個(gè)序號。（2分）（2）畫出該代碼的控制流圖，每個(gè)基本塊就用（1）的序號表示。（3分）（3）若有循環(huán)的話，列出構(gòu)成每個(gè)循環(huán)的結(jié)點(diǎn),并指出循環(huán)的入口結(jié)點(diǎn)。（6分）解：（1） （2）124736b := 1b := 2if w <= x goto L3（1）5L1:e := bgoto L3（2）L2:c := 3b := 4c := 6 （3）L3