04-05第二學期編譯原理試題.doc

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