編譯基本知識(shí)考試陳火旺含答案解析

1、編譯原理試題 A (2003.12.4)一、回答下列問題：（30分）1. （6分）對(duì)于下面程序段program test （in put, output）var i, j: in teger;procedure CAL（x, y: in teger）;beg iny:=y*y;x:=x-y; y:=y-xend;begi ni:=2;j:=3; CAL（i, j）write ln（j）end.若參數(shù)傳遞的方法分別為（1）傳值、（2）傳地址，（3）傳名，請(qǐng)寫出程序執(zhí)行的輸 出結(jié)果。2. (6分)計(jì)算文法G(M)的每個(gè)非終結(jié)符的FIRST和FOLLOW集合，并判斷該文法 是否是LL(1)的，請(qǐng)說明

2、理由。G(M):M TBT Ba |B Db|eT |D d |3. (4分)考慮下面的屬性文法產(chǎn)生式語義規(guī)則S ABCB.u :=S.uA.u :=B.v + C.vS.v :=A.vA aA.v :=3*A.uB bB.v :=B.uC cC.v :=1(1) 畫出字符串a(chǎn)bc的語法樹； 對(duì)于該語法樹，假設(shè)S.u的初始值為5，屬性計(jì)算完成后，S.v的值為多少？4. (4分)運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么？它的作用是什么?5. (5分)對(duì)下列四元式序列生成目標(biāo)代碼:A:=B*CD:=E+AG:=B+CH:=G*D其中，H在基本塊出口之后是活躍變量，RO和R1是可用寄存器。6. (5分)

3、寫出表達(dá)式a+b*(c-d)對(duì)應(yīng)的逆波蘭式、三元式序列和抽象語法樹。二、(8分)構(gòu)造一個(gè)DFA，它接受=a，b上所有包含ab的字符串。三、(6分)寫一個(gè)文法使其語言為L(zhǎng)(G)= anbncm| m,n > 1，n為奇數(shù)，m為偶數(shù)四、(8分)對(duì)于文法G(S):S bMbM (L |aL Ma)1. 寫出句型b(Ma)b的最右推導(dǎo)并畫出語法樹。2. 寫出上述句型的短語，直接短語和句柄。五、(12分)對(duì)文法G(S):S - a | A | (T)T T，S | S(1) 構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合；(2) 構(gòu)造算符優(yōu)先表；(3) 是算符優(yōu)先文法嗎？(4) 構(gòu)造優(yōu)先函數(shù)。六

4、、(8分)設(shè)某語言的do-while語句的語法形式為S doS While E其語義解釋為：直/、針對(duì)自下而上的語法分析器，按如下要求構(gòu)造該語句的翻譯模式，將該語句翻 譯成四元式：(1) 寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；(2) 寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語義動(dòng)作。七、(10分)將語句while C>0 do if A B=0 then C:=C+D else C:=C*D翻譯成四元式。八、(10分)設(shè)有基本塊如下：T1:=3T2:=A*BT3:=9+T1M:=A*BT4:=C-DL:=T3*T4T2:=C+DN:=T21. 畫出DAG圖；2. 設(shè)L, M，N是出基本塊后的活躍變量，請(qǐng)給出優(yōu)化后的

5、四元式序列。九、(8分)文法G(S)及其LR分析表如下，請(qǐng)給出串baba#的分析過程。(1) S DbB D d D & B a (5) B Bba B &LR分析表ACTIONGOTObDa#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5（注：答案格式為步驟 狀態(tài) 符號(hào) 輸入串）編譯原理試題 A (2003.12.4)一、回答下列問題： (30 分 )1. (6 分 )對(duì)于下面程序段program test (input, output)var i, j: integer;procedure CAL(x, y: integer);

6、beginy:=y*y; x:=x-y; y:=y-xend;begini:=2; j:=3; CAL(i, j) writeln(j)end.若參數(shù)傳遞的方法分別為 (1)傳值、 (2)傳地址， (3)傳名，請(qǐng)寫出程序執(zhí)行的輸 出結(jié)果。答： (1) 3 (2) 16 (3) 16 (每個(gè)值 2 分)2. (6分)計(jì)算文法G(M)的每個(gè)非終結(jié)符的FIRST和FOLLOW集合，并判斷該文法 是否是LL(1)的，請(qǐng)說明理由。G(M) ：M TBT Ba |B Db | eT |D d |解答：計(jì)算文法的 FIRST 和 FOLLOW 集合： (4 分)FIRST(M) = a ， b， e， d，

7、FIRST(B) = b ， e， d，F(xiàn)OLLOW (M) = #FOLLOW (B) = a ， # FIRST(T) = a ， b， e， d，F(xiàn)IRST(D) = d ， FOLLOW (T) = a ， b， e， d， #FOLLOW (D) = b檢查文法的所有產(chǎn)生式，我們可以得到：1該文法不含左遞歸，2該文法中每一個(gè)非終結(jié)符 M, T, B, D的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。3該文法的非終結(jié)符T、B和D，它們都有 候選式，而且,b, e, d 豐（2分）FIRST（T） G FOLLOW（T）= a所以該文法不是LL（1）文法3. （4分）考慮下面的屬性文法產(chǎn)生式語義規(guī)

8、則St ABCB.u :=S.uA.u :=B.v + C.vS.v :=A.vA t aA.v :=3*A.uB t bB.v :=B.uCt cC.v :=1畫出字符串a(chǎn)bc的語法樹；對(duì)于該語法樹，假設(shè)S.u的初始值為5,屬性計(jì)算完成后，S.v的值為多 少。答:（2分）S.v的值為18（2分）4. （4分）運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么？它的作用是什么？答：DISPLAY表是嵌套層次顯示表。每當(dāng)進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄區(qū) 的同時(shí)建立一張嵌套層次顯示表diaplay.假定現(xiàn)在進(jìn)入的過程層次為i，則它的diaplay表含有i+1個(gè)單元，自頂向下每個(gè)單元依次存放著現(xiàn)行層、直接外層

9、、 直至最外層（主程序，0層）等每層過程的最新活動(dòng)記錄的起始地址。通過DISPLAY表可以訪問其外層過程的變量。5. （5分）對(duì)下列四元式序列生成目標(biāo)代碼：A:=B*CD:=E+AG:=B+CH:=G*D其中，H在基本塊出口之后是活躍變量，R0和R1是可用寄存器答：目標(biāo)代碼序列LDROBMULROCLDR1EADDR1R0LDR0BADDR0CMULR0R1STR0H6. （5分）寫出表達(dá)式a+b*（c-d）對(duì)應(yīng)的逆波蘭式、三元式序列和抽象語法樹。答：逆波蘭式：（abcd-*+）（1分）三兀式序列：（2分）OPARG1ARG2(1)-cd*b(1)(3)+a抽象語法樹：（2分）bcd二、（8分

10、）構(gòu)造一個(gè)DFA，它接受=a，b上所有包含ab的字符串答：aa12356babbbaaaa5234bbabaaa答m為偶數(shù)。b農(nóng)三、(6分)寫一個(gè)文法使其語言為L(zhǎng)(G)= anbncm| m,n > 1 , n為奇數(shù),文法G(S):(2分)構(gòu)造相應(yīng)的正規(guī)式：(a|b)*ab(a|b)*最小化:0，1，23，4，5(3分)0，2，1，3，4，5II 0丨10,1,21,2,31,21,2,31,2,31,2,4,5,61,21,2,31,2124,5,61,2,3,5,61,2,5,6123,5,61,2,3,5,61,2,4,5,61,2,5,61,2,3,5,61,2,5,6(3分)確

11、定化:S ACA aaAbb | abC ccCcc | cc四、(8分)對(duì)于文法G(S):S bMbM (L |aL Ma)1. 寫出句型b(Ma)b的最右推導(dǎo)并畫出語法樹2. 寫出上述句型的短語，直接短語和句柄。答：1. (4 分)S bMb b(Lb b(Ma)b2. (4 分)短語：Ma)， (Ma)， b(Ma)b 直接短語：Ma)句柄：Ma) 五、(12分)對(duì)文法G(S):S - a | A | (T)T T, S | S(1) 構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合;(2) 構(gòu)造算符優(yōu)先表；(3) 是算符優(yōu)先文法嗎？(4) 構(gòu)造優(yōu)先函數(shù)。答：(1) (4 分)FIRST

12、VT (S)a,八,(FIRSTVT(T), ,a,A,(LASTVT(S) a/,) LASTVT(T) , ,a,A,)(4分)aA()Ja>>A>>(<<<=<)>><<<>>(3)是算符優(yōu)先文法，因?yàn)槿魏蝺蓚€(gè)終結(jié)符之間至多只有一種優(yōu)先關(guān)系。(1分)(4)優(yōu)先函數(shù)(3分)aA()JF44244G55523六、(8分)設(shè)某語言的do-while語句的語法形式為S doS(1) While E其語義解釋為:直/、假針對(duì)自下而上的語法分析器，按如下要求構(gòu)造該語句的翻譯模式，將該語句翻 譯成四元式：(1)

13、寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；(2) 寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語義動(dòng)作。答：(1).適合語法制導(dǎo)翻譯的文法(4分)G(S):R doU R S WhileSUE(2). (4 分)R do R.QUAD:=NXQ U R S(1) While U.QUAD:=R.QUAD;BACKPATCH(S.CHAIN, NXQ) S U EBACKPATCH(E.TC, U.QUAD);S.CHAIN:=E.FC 答案二：(1) SdoM 1 S(1)WhileM2EM£(4 分 )(2) M£ M.QUAD:= NXQ (4 分)SdoM 1 S(1)WhileM2EBACKPATCH

14、(S(1).CHAIN, M 2.QUAD);BACKPATCH(E.TC, M 1.QUAD); S.CHAIN:=E. FC七、（10 分）將語句while C>0 do if AB=0 then C:=C+D else C:=C*D翻譯成四元式。答：100 （j> ， C， 0， 102）101(j ， -， -112)102(jnz ， A ，-， 106)103(j ， -， -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)111112(j ,100)八、（10分）設(shè)有基本塊如下:T1:=3T2:=A*BT3:=9+T1M:=A*BT4:=C-DL:=T3*T4T2:=C+DN:=T23. 畫出DAG圖；4. 設(shè)L, M , N是出基本塊后的活躍變量, 答：1. (6 分)請(qǐng)給出優(yōu)化后的四元式序列n1n2 : : n3n5n6n7T1T3AB122. (4 分)M:=A*BS1:=C-DL:=12*S1N:=C+Dbaba#的分析過程九、(8分戊法G