1、編譯原理試題A (2003.12.4)一、 回答下列問題：(30分)1. (6分)對于下面程序段program test (input, output)var i, j: integer;procedure CAL(x, y: integer); begin y:=y*y; x:=x-y; y:=y-x end; begin i:=2; j:=3; CAL(i, j) writeln(j)end. 若參數傳遞的方法分別為(1)傳值、(2)傳地址，(3)傳名，請寫出程序執(zhí)行的輸出結果。2. (6分)計算文法G(M)的每個非終結符的FIRST和FOLLOW集合，并判斷該文法是否是LL(1)的，請說

2、明理由。G(M)：M TBT Ba | eB Db | eT | eD d | e3. (4分)考慮下面的屬性文法 產 生 式 語 義 規(guī) 則 SABC Aa Bb Cc B.u := S.u A.u := B.v + C.v S.v := A.v A.v :=3*A.u B.v := B.u C.v := 1 (1) 畫出字符串abc的語法樹;(2) 對于該語法樹，假設S.u的初始值為5，屬性計算完成后，S.v的值為多少?4. (4分)運行時的DISPLAY表的內容是什么？它的作用是什么？5. (5分)對下列四元式序列生成目標代碼： A:=B*CD:=E+AG:=B+CH:=G*D其中，H在

3、基本塊出口之后是活躍變量， R0和R1是可用寄存器。6. (5分)寫出表達式a+b*(c-d)對應的逆波蘭式、三元式序列和抽象語法樹。二、 (8分)構造一個DFA，它接受S=a，b上所有包含ab的字符串。三、 (6分)寫一個文法使其語言為L(G)=anbncm| m,n1，n為奇數，m為偶數。四、 (8分)對于文法G(S):1. 寫出句型b(Ma)b的最右推導并畫出語法樹。2. 寫出上述句型的短語，直接短語和句柄。五、 (12分)對文法G(S)：S a | | (T)T T，S | S(1) 構造各非終結符的FIRSTVT和LASTVT集合;(2) 構造算符優(yōu)先表;(3) 是算符優(yōu)先文法嗎?(

4、4) 構造優(yōu)先函數。六、 (8分)設某語言的do-while語句的語法形式為 S ® do S(1) While E其語義解釋為：真假S(1)的代碼E的代碼針對自下而上的語法分析器，按如下要求構造該語句的翻譯模式，將該語句翻譯成四元式：(1) 寫出適合語法制導翻譯的產生式；(2) 寫出每個產生式對應的語義動作。七、 (10分)將語句while C>0 do if A Ú B=0 then C:=C+D else C:=C*D翻譯成四元式。八、 (10分)設有基本塊如下：T1:=3T2:=A*BT3:=9+T1M:=A*BT4:=C-DL:=T3*T4T2:=C+DN:

5、=T21. 畫出DAG圖；2. 設L，M，N 是出基本塊后的活躍變量，請給出優(yōu)化后的四元式序列。九、 (8分)文法G(S)及其LR分析表如下，請給出串baba#的分析過程。(1) S DbB(2) D d(3) D (4) B a(5) B Bba(6) B LR分析表ACTIONGOTObDa#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5(注：答案格式為 步驟狀態(tài)符號輸入串)編譯原理試題A (2003.12.4)一、 回答下列問題：(30分)1. (6分)對于下面程序段program test (input, output)var i, j:

6、integer;procedure CAL(x, y: integer); begin y:=y*y; x:=x-y; y:=y-x end; begin i:=2; j:=3; CAL(i, j) writeln(j)end. 若參數傳遞的方法分別為(1)傳值、(2)傳地址，(3)傳名，請寫出程序執(zhí)行的輸出結果。答： (1) 3 (2) 16(3) 16 (每個值2分)2. (6分)計算文法G(M)的每個非終結符的FIRST和FOLLOW集合，并判斷該文法是否是LL(1)的，請說明理由。G(M)：M TBT Ba | eB Db | eT | eD d | e解答：計算文法的FIRST和FO

7、LLOW集合：(4分)FIRST(M) = a，b，e，d，e FIRST(T) = a，b，e，d，e FIRST(B) = b，e，d，e FIRST(D) = d，eFOLLOW (M) = #FOLLOW (T) = a，b，e，d，#FOLLOW (B) = a，# FOLLOW (D) = b檢查文法的所有產生式，我們可以得到：1. 該文法不含左遞歸，2. 該文法中每一個非終結符M，T，B，D的各個產生式的候選首符集兩兩不相交。3. 該文法的非終結符T、B和D，它們都有e候選式，而且FIRST(T)FOLLOW(T)= a，b，e，d f所以該文法不是LL(1)文法。(2分)3.

8、(4分)考慮下面的屬性文法 產 生 式 語 義 規(guī) 則 SABC Aa Bb Cc B.u := S.u A.u := B.v + C.v S.v := A.v A.v :=3*A.u B.v := B.u C.v := 1 (3) 畫出字符串abc的語法樹;(4) 對于該語法樹，假設S.u的初始值為5，屬性計算完成后，S.v的值為多少。SABCabc答：(1) (2分)(2) S.v的值為18 (2分)4. (4分)運行時的DISPLAY表的內容是什么？它的作用是什么？答：DISPLAY表是嵌套層次顯示表。每當進入一個過程后，在建立它的活動記錄區(qū)的同時建立一張嵌套層次顯示表diaplay.假

9、定現在進入的過程層次為i，則它的diaplay表含有i+1個單元，自頂向下每個單元依次存放著現行層、直接外層、直至最外層(主程序，0層)等每層過程的最新活動記錄的起始地址。通過DISPLAY表可以訪問其外層過程的變量。5. (5分)對下列四元式序列生成目標代碼： A:=B*CD:=E+AG:=B+CH:=G*D其中，H在基本塊出口之后是活躍變量， R0和R1是可用寄存器。答: 目標代碼序列LDR0BMULR0CLDR1EADDR1R0LDR0BADDR0CMULR0R1STR0H6. (5分)寫出表達式a+b*(c-d)對應的逆波蘭式、三元式序列和抽象語法樹。答：逆波蘭式：(abcd-*+)

10、(1分)三元式序列: (2分) OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2)adc-b*+抽象語法樹：(2分)二、 (8分)構造一個DFA，它接受S=a，b上所有包含ab的字符串。答：(2分)構造相應的正規(guī)式：(a|b)*ab(a|b)*(3分)0123645 a a e e a b e e b b(3分)確定化：I0,1,21,2,31,21,2,31,2,31,2,4,5,61,21,2,31,21,2,4,5,61,2,3,5,61,2,5,61,2,3,5,61,2,3,5,61,2,4,5,61,2,5,61,2,3,5,61,2,5,

11、6 b b b a543210 a a a a a b b b 最小化：0，1，2 3，4，50， 2，1， 3，4，5baa01b3ba三、 (6分)寫一個文法使其語言為L(G)=anbncm| m,n1，n為奇數，m為偶數。答：文法G(S):四、 (8分)對于文法G(S): 1. 寫出句型b(Ma)b的最右推導并畫出語法樹。2. 寫出上述句型的短語，直接短語和句柄。SbM(TMabL)答：1. (4分) 2. (4分)短語: Ma)， (Ma)， b(Ma)b直接短語: Ma)句柄: Ma)五、 (12分)對文法G(S)：S a | | (T)T T，S | S(1) 構造各非終結符的FI

12、RSTVT和LASTVT集合;(2) 構造算符優(yōu)先表;(3) 是算符優(yōu)先文法嗎?(4) 構造優(yōu)先函數。答：(1) (4分) (2) (4分)a(),a>>>>(<<<=<)>>,<<<>>(3) 是算符優(yōu)先文法，因為任何兩個終結符之間至多只有一種優(yōu)先關系。 (1分)(4) 優(yōu)先函數(3分)a(),F44244G55523六、 (8分)設某語言的do-while語句的語法形式為 S ® do S(1) While E其語義解釋為：真假S(1)的代碼E的代碼針對自下而上的語法分析器，按如下要求構造該

13、語句的翻譯模式，將該語句翻譯成四元式：(1) 寫出適合語法制導翻譯的產生式；(2) 寫出每個產生式對應的語義動作。答：(1). 適合語法制導翻譯的文法(4分) G(S): R® do U®R S(1) While S®U E (2). (4分) R® do R.QUAD:=NXQ U®R S(1) While U.QUAD:=R.QUAD; BACKPATCH(S.CHAIN, NXQ) S®U E BACKPATCH(E.TC, U.QUAD); S.CHAIN:=E.FC 答案二：(1) S ® do M1 S(1) W

14、hile M2 E M ® (4分)(2) M ® M.QUAD := NXQ (4分)S ® do M1 S(1) While M2 EBACKPATCH(S(1).CHAIN, M2.QUAD);BACKPATCH(E.TC, M1.QUAD); S.CHAIN:=E. FC七、 (10分)將語句while C>0 do if A Ú B=0 then C:=C+D else C:=C*D翻譯成四元式。答：100 (j>， C， 0， 102)101 (j， -， -， 112)102 (jnz， A， -， 106)103 (j， -，

15、 -， 104)104 (j=， B， 0， 106)105 (j， -， -， 109)106 (+， C， D， T1)107 (:=， T1， -， C)108 (j， -， -， 100)109 (*， C， D， T2)110 (:=， T2， -， C)111 (j， -， -， 100)112 八、 (10分)設有基本塊如下：T1:=3T2:=A*BT3:=9+T1M:=A*BT4:=C-DL:=T3*T4T2:=C+DN:=T23. 畫出DAG圖；4. 設L，M，N 是出基本塊后的活躍變量，請給出優(yōu)化后的四元式序列。答：n91. (6分) L n8n4n10 * T2,M T4 T2,N * - +n6n5n3n2n1n7 T1 T3 3 A B 12 C D2. (4分)M:=A*BS1:=C-DL:=12*S1N:=C+D九、 (8分)文法G(S)及其LR分析