04-05第二學(xué)期編譯原理試題.doc

20042005年度第2學(xué)期 計(jì)算機(jī)學(xué)院02級(jí)【編譯原理】考試題（A）考試形式： 開(kāi)卷 考試時(shí)間：2005年 6月24日9:55-11:30學(xué)號(hào)姓名1234567附加題總分分?jǐn)?shù)1. （6分）回答下列問(wèn)題1） 在存儲(chǔ)管理中，為什么在活動(dòng)記錄內(nèi)為臨時(shí)變量分配空間？答：在棧式存儲(chǔ)管理方式中，以活動(dòng)記錄的形式為一次過(guò)程調(diào)用（函數(shù)調(diào)用）中的局部數(shù)據(jù)提供存儲(chǔ)空間，該活動(dòng)記錄隨過(guò)程調(diào)用被分配，隨過(guò)程調(diào)用的結(jié)束而釋放；臨時(shí)變量通常用于保存表達(dá)式計(jì)算中的中間結(jié)果，在活動(dòng)記錄中為臨時(shí)變量分配空間，可以保證該空間隨過(guò)程調(diào)用被分配，隨活動(dòng)記錄的釋放被自動(dòng)釋放。2） 在符號(hào)表管理中，為什么將變量名保存在符號(hào)表中？答：符號(hào)表中將保存變量名及其各種屬性，變量名將用于變量的識(shí)別、涉及變變量名與存儲(chǔ)空間的綁定、以及類(lèi)型、作用域、存儲(chǔ)地址等各種變量屬性的設(shè)置、獲取等各種維護(hù)功能。2. (8分)試消除下列文法中的左遞歸。 S SaA|Se|BA BbA|BB cSd|e解： 消除左遞歸 提取左因子 改寫(xiě)后的文法 S SaA|Se|B A BbA | B S BS S（aA | e ）| B B ( bA | e) S aA S | e S | e 引進(jìn)非終結(jié)符S 引進(jìn)非終結(jié)符A A B A S BS A B A A bA | eS（aA | e ）S | e A bA | e B cSd|e3. (15分)寫(xiě)出下列文法中各候選式的FIRST集和各非終結(jié)符的FOLLOW集,構(gòu)造該文法的LL（1）分析表，并說(shuō)明它是否為L(zhǎng)L（1）文法。 S aA|BAA cB|eB bB|e各候選式的FIRST集 (4分) FIRST（aA）=a FIRST（BA）= b，c，e FIRST（cB）=cFIRST（e）=e FIRST（bB）= b FIRST（e）=e各非終結(jié)符的FOLLOW集 (4分)FOLLOW(S)= # FOLLOW(A)= # FOLLOW(B)= c，#LL（1）分析表 (5分) a b c # S S aA S BA S BA S BA A A cB A e B B bB B e B e 說(shuō)明它是否為L(zhǎng)L（1）文法 (2分) 判斷1分，理由1分因?yàn)長(zhǎng)L（1）分析表無(wú)沖突，所以該文法是LL（1）文法。4.（18分）給定文法GS S L + L L L LB|BB 0|1(1) 構(gòu)造拓廣文法，按LR(0)分析的需要畫(huà)出識(shí)別這個(gè)拓廣文法的所有規(guī)范句型活前綴的DFA。解1：相應(yīng)的DFA如下圖所示。0SI0:S.SS .L+ LS .L L .LBL .BB .0B .1I8:S L + L. L L.BB .0B .1I2:S L.+ LS L.L L.BB .0B .1I3:L B.I1:S S.LL01B0BB01+BI7:L LB.I6:S L + .LL .LBL .BB .0B .1I5:B 1.I4:B 0.11解2：0 S0 S 11S 0 L 2 + 6 L 82S 0 L 23L 0，6 L 2，8 B 74L 0，6 B 35B 0，2，6，8 0 46B 0，2，6，8 1 5I0：（0，0），（1，0），（2，0），（3，0），（4，0），（5，0），（6，0）I1：（0，1）I2：（1，1），（2，1），（3，1），（5，0），（6，0）I3：（4，1）I4：（5，1）I5：（6，1）I6：（1，2），（3，0），（4，0），（5，0），（6，0）I7：（3，2）I8：（1，3），（3，1），（5，0），（6，0）0SI0:（0，0），（1，0），（2，0），（3，0），（4，0），（5，0），（6，0）I8:（1，3），（3，1），（5，0），（6，0）I2:（1，1），（2，1），（3，1），（5，0），（6，0）I3:（4，1）I1:（0，1）LL01B0BB01+BI7:（3，2）I6:（1，2），（3，0），（4，0），（5，0），（6，0）I5:（6，1）I4:（5，1）11(2) 求出這個(gè)文法的SLR（1）分析表。解：給產(chǎn)生式編號(hào)：SL + L SL LLB LB B 0 B1FOLLOW(S)=#FOLLOW(L)=0,1,+,# FOLLOW(B)=0,1,+,#狀態(tài)ACTIONGOTO01+#SLB0S4S51231acc2S4S5S6r273r4r4r4r44r5r5r5r55r6r6r6r66S4S5837r3r3r3r38S4S5r175.（7分）寫(xiě)出能產(chǎn)生字母表x,y上的不含兩個(gè)相鄰的x,且不含兩個(gè)相鄰的的全體符號(hào)串的有限狀態(tài)自動(dòng)機(jī)。解：6.（16分）設(shè)文法GE:E RP|P P (E)|i R RP+| RP* |P+|P*畫(huà)出句子i+i*(i+i)的語(yǔ)法分析樹(shù)，給出其最右推導(dǎo)和最左歸約，并指出它的句柄。解：(1)語(yǔ)法分析樹(shù)：（2）最右推導(dǎo)：E RP R(E) R(RP) R(Ri) R(P+i) R(i+i) RP*(i+i) Ri*(i+i) P+i*(i+i) i+i*(i+i)最左歸約：i+i*(i+i) P + i*(i+i)P+i*(i+i) Ri*(i+i)Ri*(i+i) RP*(i+i)RP*(i+i) R(i+i)R(i+i) R(P+i)R(P+i) R(Ri)R(Ri) R(RP)R(RP) R(E)R(E) RPRP E句子i+i*(i+i)的句柄為：i；7. (10分)下面是關(guān)于文法S xYS|yXS|e X yXX|xY xYY|y的一個(gè)語(yǔ)法制導(dǎo)定義，S xYS1S.nx := Y.nx + S1.nx + 1 S.ny := Y.ny + S1.nyS yXS1 S.nx := X.nx + S1.nx S.ny := X.ny + S1.ny + 1S eS.nx := 0 S.ny := 0X yX1 X2 X.nx := X1.nx + X2.nx X.ny := X1.ny + X2.ny + 1X x X.nx := 1 X.ny := 0Y xY1 Y2 Y.nx := Y1.nx + Y2.nx + 1Y.ny := Y1.ny + Y2.nyY yY.nx := 0 Y.ny := 1 (1) 請(qǐng)說(shuō)明上述語(yǔ)法制導(dǎo)定義的作用是什么。(2) 按照此語(yǔ)法指導(dǎo)定義給出句子xxxyyyxy的語(yǔ)義分析過(guò)程或畫(huà)出帶注釋的語(yǔ)法分析樹(shù)解：（1）該語(yǔ)法制導(dǎo)定義的作用是統(tǒng)計(jì)句子中的x和y的個(gè)數(shù)；（4分）（2）按照該語(yǔ)法制導(dǎo)定義對(duì)句子xxxyyyxy進(jìn)行語(yǔ)義分析的結(jié)果為：S.nx = 4；S.ny = 4；（6分）附加題將左線(xiàn)性文法G=(VN,VT,P,S)轉(zhuǎn)換成等價(jià)的有限狀態(tài)自動(dòng)機(jī)M=(Q,VT, ,q0,F)的一種等價(jià)變換中認(rèn)為“對(duì)產(chǎn)生式ABaP則M中用移動(dòng)A(B，a)與之對(duì)應(yīng)”，請(qǐng)問(wèn)這種對(duì)應(yīng)使用的是自頂向下的分析思想還是自底向上的分析思想？為什么？（本題第一問(wèn)最高獎(jiǎng)勵(lì)3分，第二問(wèn)最高獎(jiǎng)勵(lì)7分）解：使用的是自底向上的分析方法歸約。A(B，a)表示在狀態(tài)B遇到輸入a時(shí)，到達(dá)狀態(tài)A，將狀態(tài)看成是目前已經(jīng)分析出來(lái)的中間結(jié)果，這樣就相當(dāng)于目前的分析已經(jīng)得到了前綴B，加上a后相當(dāng)于獲得前綴A，也就是相當(dāng)于B和緊接著的a可以歸約成A，這與產(chǎn)生式ABa所表示出來(lái)