編譯原理考試 陳火旺(含答案)

編譯原理考試陳火旺(含答案)編譯原理考試陳火旺(含答案)編譯原理考試陳火旺(含答案)資料僅供參考文件編號(hào)：2022年4月編譯原理考試陳火旺(含答案)版本號(hào)：A修改號(hào)：1頁(yè)次：1.0審核：批準(zhǔn):發(fā)布日期：編譯原理試題A(2003.12.4)回答下列問(wèn)題：(30分)(6分)對(duì)于下面程序段programtest(input,output) vari,j:integer; procedureCAL(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.若參數(shù)傳遞的方法分別為(1)傳值、(2)傳地址，(3)傳名，請(qǐng)寫出程序執(zhí)行的輸出結(jié)果。(6分)計(jì)算文法G(M)的每個(gè)非終結(jié)符的FIRST和FOLLOW集合，并判斷該文法是否是LL(1)的，請(qǐng)說(shuō)明理由。G(M)：M→TBT→Ba|B→Db|eT|D→d|(4分)考慮下面的屬性文法產(chǎn)生式語(yǔ)義規(guī)則S→ABCA→aB→bC→cB.u:=S.uA.u:=B.v+C.vS.v:=A.vA.v:=3*A.uB.v:=B.uC.v:=1畫出字符串a(chǎn)bc的語(yǔ)法樹(shù);對(duì)于該語(yǔ)法樹(shù)，假設(shè)S.u的初始值為5，屬性計(jì)算完成后，S.v的值為多少

(4分)運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么它的作用是什么

(5分)對(duì)下列四元式序列生成目標(biāo)代碼：A:=B*CD:=E+AG:=B+CH:=G*D其中，H在基本塊出口之后是活躍變量，R0和R1是可用寄存器。(5分)寫出表達(dá)式a+b*(c-d)對(duì)應(yīng)的逆波蘭式、三元式序列和抽象語(yǔ)法樹(shù)。(8分)構(gòu)造一個(gè)DFA，它接受={a，b}上所有包含ab的字符串。(6分)寫一個(gè)文法使其語(yǔ)言為L(zhǎng)(G)={anbncm|m,n≥1，n為奇數(shù)，m為偶數(shù)}。(8分)對(duì)于文法G(S):1.寫出句型b(Ma)b的最右推導(dǎo)并畫出語(yǔ)法樹(shù)。2.寫出上述句型的短語(yǔ)，直接短語(yǔ)和句柄。(12分)對(duì)文法G(S)：S→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ù)。(8分)設(shè)某語(yǔ)言的do-while語(yǔ)句的語(yǔ)法形式為SdoS(1)WhileE其語(yǔ)義解釋為：真真假S(1)的代碼E的代碼針對(duì)自下而上的語(yǔ)法分析器，按如下要求構(gòu)造該語(yǔ)句的翻譯模式，將該語(yǔ)句翻譯成四元式：(1)寫出適合語(yǔ)法制導(dǎo)翻譯的產(chǎn)生式；(2)寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。(10分)將語(yǔ)句whileC>0doifAB=0thenC:=C+DelseC:=C*D翻譯成四元式。(10分)設(shè)有基本塊如下：T1:=3T2:=A*BT3:=9+T1M:=A*BT4:=C-DL:=T3*T4T2:=C+DN:=T2畫出DAG圖；設(shè)L，M，N是出基本塊后的活躍變量，請(qǐng)給出優(yōu)化后的四元式序列。(8分)文法G(S)及其LR分析表如下，請(qǐng)給出串baba#的分析過(guò)程。(1)S→DbB (2)D→d (3)D→ε(4)B→a (5)B→Bba (6)B→εLR分析表ACTIONGOTObDa#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5(注：答案格式為步驟 狀態(tài) 符號(hào) 輸入串)

編譯原理試題A(2003.12.4)回答下列問(wèn)題：(30分)(6分)對(duì)于下面程序段programtest(input,output) vari,j:integer; procedureCAL(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.若參數(shù)傳遞的方法分別為(1)傳值、(2)傳地址，(3)傳名，請(qǐng)寫出程序執(zhí)行的輸出結(jié)果。答：(1)3(2)16 (3)16 (每個(gè)值2分)(6分)計(jì)算文法G(M)的每個(gè)非終結(jié)符的FIRST和FOLLOW集合，并判斷該文法是否是LL(1)的，請(qǐng)說(shuō)明理由。G(M)：M→TBT→Ba|B→Db|eT|D→d|解答：計(jì)算文法的FIRST和FOLLOW集合：(4分)FIRST(M)={a，b，e，d，} FIRST(T)={a，b，e，d，}FIRST(B)={b，e，d，} FIRST(D)={d，}FOLLOW(M)={#} FOLLOW(T)={a，b，e，d，#}FOLLOW(B)={a，#} FOLLOW(D)=檢查文法的所有產(chǎn)生式，我們可以得到：1.該文法不含左遞歸，2.該文法中每一個(gè)非終結(jié)符M，T，B，D的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。3.該文法的非終結(jié)符T、B和D，它們都有候選式，而且FIRST(T)∩FOLLOW(T)={a，b，e，d}≠ 所以該文法不是LL(1)文法。(2分)(4分)考慮下面的屬性文法產(chǎn)生式語(yǔ)義規(guī)則S→ABCA→aB→bC→cB.u:=S.uA.u:=B.v+C.vS.v:=A.vA.v:=3*A.uB.v:=B.uC.v:=1畫出字符串a(chǎn)bc的語(yǔ)法樹(shù);對(duì)于該語(yǔ)法樹(shù)，假設(shè)S.u的初始值為5，屬性計(jì)算完成后，S.v的值為多少。SABSABCabc (2)S.v的值為18(2分)(4分)運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么它的作用是什么

答：DISPLAY表是嵌套層次顯示表。每當(dāng)進(jìn)入一個(gè)過(guò)程后，在建立它的活動(dòng)記錄區(qū)的同時(shí)建立一張嵌套層次顯示表diaplay.假定現(xiàn)在進(jìn)入的過(guò)程層次為i，則它的diaplay表含有i+1個(gè)單元，自頂向下每個(gè)單元依次存放著現(xiàn)行層、直接外層、…、直至最外層(主程序，0層)等每層過(guò)程的最新活動(dòng)記錄的起始地址。通過(guò)DISPLAY表可以訪問(wèn)其外層過(guò)程的變量。(5分)對(duì)下列四元式序列生成目標(biāo)代碼：A:=B*CD:=E+AG:=B+CH:=G*D其中，H在基本塊出口之后是活躍變量，R0和R1是可用寄存器。答:目標(biāo)代碼序列LD R0 BMUL R0 CLD R1 EADD R1 R0LD R0 BADD R0 CMUL R0 R1ST R0 H(5分)寫出表達(dá)式a+b*(c-d)對(duì)應(yīng)的逆波蘭式、三元式序列和抽象語(yǔ)法樹(shù)。答：逆波蘭式：(abcd-*+)(1分)三元式序列:(2分)OPARG1ARG2(1)-cd(2)*b(1)(3)+a(2)adadc-b*+(8分)構(gòu)造一個(gè)DFA，它接受={a，b}上所有包含ab的字符串。答：(2分)構(gòu)造相應(yīng)的正規(guī)式：(a|b)*ab(a|b)*(3分)0120123645abbb(3分)確定化：I{0,1,2}{1,2,3}{1,2}{1,2,3}{1,2,3}{1,2,4,5,6}{1,2}{1,2,3}{1,2}{1,2,4,5,6}{1,2,3,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,3,5,6}{1,2,4,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,5,6}bbba543210aaaa543210abbb最小化：{0，1，2}{3，4，5}{0，2}，1，{3，4，5}bbaa01b3ba(6分)寫一個(gè)文法使其語(yǔ)言為L(zhǎng)(G)={anbncm|m,n≥1，n為奇數(shù)，m為偶數(shù)}。答：文法G(S):(8分)對(duì)于文法G(S):1.寫出句型b(Ma)b的最右推導(dǎo)并畫出語(yǔ)法樹(shù)。2.寫出上述句型的短語(yǔ)，直接短語(yǔ)和句柄。SbSbM(TMabL)1.(4分)2.(4分)短語(yǔ):Ma)，(Ma)，b(Ma)b直接短語(yǔ):Ma)句柄:Ma)(12分)對(duì)文法G(S)：S→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分)(2)(4分)a^(),a>>^>>(<<<=<)>>,<<<>>(3)是算符優(yōu)先文法，因?yàn)槿魏蝺蓚€(gè)終結(jié)符之間至多只有一種優(yōu)先關(guān)系。(1分)(4)優(yōu)先函數(shù)(3分)a^(),F44244G55523(8分)設(shè)某語(yǔ)言的do-while語(yǔ)句的語(yǔ)法形式為SdoS(1)WhileE其語(yǔ)義解釋為：真真假S(1)的代碼E的代碼針對(duì)自下而上的語(yǔ)法分析器，按如下要求構(gòu)造該語(yǔ)句的翻譯模式，將該語(yǔ)句翻譯成四元式：(1)寫出適合語(yǔ)法制導(dǎo)翻譯的產(chǎn)生式；(2)寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。答：(1).適合語(yǔ)法制導(dǎo)翻譯的文法(4分)G(S):RdoURS(1)WhileSUE(2).(4分)Rdo{R.QUAD:=NXQ}URS(1)While{U.QUAD:=R.QUAD;BACKPATCH(S.CHAIN,NXQ)}SUE{BACKPATCH(E.TC,U.QUAD);S.CHAIN:=E.FC}答案二：(1)SdoM1S(1)WhileM2EMε(4分)(2) Mε{M.QUAD:=NXQ}(4分) SdoM1S(1)WhileM2E {BACKPATCH(S(1).CHAIN,M2.QUAD);BACKPATCH(E.TC,M1.QUAD);S.CHAIN:=E.FC }(10分)將語(yǔ)句whileC>0doifAB=0thenC:=C+DelseC:=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)111(j，-，-，100)112(10分)設(shè)有基本塊如下：T1:=3T2:=A*BT3:=9+T1M:=A*BT4:=C-DL:=T3*T4T2:=C+DN:=T2畫出DAG圖；設(shè)L，M，N是出基本塊后的活躍變量，請(qǐng)給出優(yōu)化后的四元式序列。答：n91.(6分)n9Ln8n4n10*n8n4n10