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

1、編譯原理試題 A (2003.12.4)一、回答下列問題：（30分）1. （6分）對(duì)于下面程序段P rogram test （input, out put） var i, j: in teger;p rocedureCAL（x, y: in teger）;beginy:=y*y;x:=x-y; y:=y-xen d;begini:=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在基本塊出口之后是活躍變量，R0和R1是可用寄存器。6.

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

4、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 C0 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)化后的四元式序列。九、(8分)文法G

5、(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);beginy:=y*y; x:=x-y; y:=

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

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

8、= 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的值為多 少。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)行層、直接外層、 直至最外層（主程序，0層）等每層過程的最新活動(dòng)記錄的起始地址。通過DISPLAY表可以訪問其外層過

9、程的變量。5. （5分）對(duì)下列四元式序列生成目標(biāo)代碼:A:=B*CD:=E+AG:=B+CH:=G*DRO和R1是可用寄存器。其中，H在基本塊出口之后是活躍變量, 答：目標(biāo)代碼序列6. （5分）寫出表達(dá)式答：逆波蘭式：（abcd-*+）a+b*（c-d）對(duì)應(yīng)的逆波蘭式、三元式序列和抽象語法樹。三元式序列：（2分）OPARG1ARG2(1)-cd(2) *b(1)(3)+a抽象語法樹：（2分）(1分)LDR0BMULR0CLDR1EADDR1R0LDR0BADDR0CMULR0R1STR0H二、（8分）構(gòu)造一個(gè)DFA，它接受=a，b上所有包含ab的字符串。答：(2分)構(gòu)造相應(yīng)的正規(guī)式：b)*ab

10、(a|b)*（3分）aOb*（2yx37xz）a5bbb(3分)確定化:I1。I10,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最小化：0, 1 , 2 3 , 4, 53 , 4, 5aab30 , 2 , 1 ,V、(6分)寫一個(gè)文法使其語言為L(G)= anbncm| m,n 1 , n為奇數(shù)，m為偶數(shù)。答：文法G(S):ACaaAbb | ab ccCcc | cc四、(8分)對(duì)于文法G(S):SMLbMb

11、(L|aMa)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 T a | A | (T) T T, S | S 構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合; 構(gòu)造算符優(yōu)先表； 是算符優(yōu)先文法嗎？ 構(gòu)造優(yōu)先函數(shù)。(1)答：(1) (4 分)FIRSTVT (S)a,八,(FIRSTVT 仃), ,a,A,(LASTVT(S)a,A,)LASTVT(T), ,a,A,)(2)

12、 (4 分)A()aaA(=(1分)(3) 是算符優(yōu)先文法，因?yàn)槿魏蝺蓚€(gè)終結(jié)符之間至多只有一種優(yōu)先關(guān)系。(4)優(yōu)先函數(shù)(3分)aA()F44244G55523六、(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)作。答：(1).適合語法制導(dǎo)翻譯的文法(4分)G(S):doR S WhileU ERUS(2). (4 分)R do R.QUAD:=NXQ U R S(1) While U.QUAD:=R.

13、QUAD;BACKPATCH(S.CHAIN, NXQ) BACKPATCH(E.TC, U.QUAD);S.CHAIN:=E.FC 答案二：(1) SM(2) MSdodoM 1 S(1) While(4 分 ) M.QUAD := NXQ M 1 S(1) WhileM2M2(4 分)EBACKPATCH(S(1).CHAIN, M 2.QUAD);BACKPATCH(E.TC, M 1.QUAD); S.CHAIN:=E. FC七、 （10 分）將語句while C0 do if AB=0 then翻譯成四元式。答：100(j ， C，0， 102)101(j ， -， -， 112)1

14、02(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)C:=C+D else C:=C*D111(j,100)112八、(10分)設(shè)有基本塊如下:T1:=3T2:=A*BT3:=9+T1M:=A*BT4:=C-DL:=T3*T4T2:=C+DN:=T23. 畫出DAG圖；4. 設(shè)L, M , N是出基本塊后的活躍變量，請(qǐng)給出優(yōu)化后的四元式序列。 答：1. (6 分)(3T2,Nn2T1T3122. (4 分)M:=A*BS1:=C-DL:=12*S1N:=C+Dbaba