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

1、WORD格式可以任意編輯編譯原理試題 A (2003.12.4)一、回答下列問題： (30 分 )1. (6 分 ) 對(duì)于下面程序段programtest(input,output) vari,j:integer;procedureCAL(x,y:integer);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é)果。2. (6 分)計(jì)算文法 G(M)的每個(gè)非終結(jié)符的 FIRST和 FOLLOW集合，并判斷該文 法是否是

2、 LL(1) 的，請(qǐng)說明理由。G(M)：MTBTBa|BDb|eT|Dd|3. (4 分) 考慮下面的屬性文法產(chǎn)生式語義規(guī)則SABCB.u:=S.uA.u:=B.v+C.vS.v:=A.vAaA.v:=3*A.uBbB.v:=B.uCcC.v:=1(1) 畫出字符串 abc 的語法樹 ;(2) 對(duì)于該語法樹，假設(shè) S.u 的初始值為 5，屬性計(jì)算完成后， S.v 的值為多少 ?4. (4 分) 運(yùn)行時(shí)的 DISPLAY表的內(nèi)容是什么？它的作用是什么？5. (5 分) 對(duì)下列四元式序列生成目標(biāo)代碼：1A:=B*CD:=E+AG:=B+CH:=G*DR0和 R1是可用寄存器。其中， H 在基本塊出

3、口之后是活躍變量，6. (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):S bMbM (L|aLMa)1. 寫出句型 b(Ma)b 的最右推導(dǎo)并畫出語法樹。2. 寫出上述句型的短語，直接短語和句柄。五、 (12 分)對(duì)文法 G(S)：S a|(T)T T， S|S(1) 構(gòu)造各非終結(jié)符的 FIRSTVT和 LASTVT集合 ;(2) 構(gòu)造算符優(yōu)先

4、表 ;(3) 是算符優(yōu)先文法嗎 ?(4) 構(gòu)造優(yōu)先函數(shù)。六、 (8 分)設(shè)某語言的 do-while語句的語法形式為S doS(1)WhileE其語義解釋為：S(1)的代碼E 的代碼真假針對(duì)自下而上的語法分析器，按如下要求構(gòu)造該語句的翻譯模式，將該語句翻譯成四元 式：(1) 寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；(2) 寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語義動(dòng)作。七、(10 分)將語句whileC>0doifA B=0thenC:=C+DelseC:=C*D翻譯成四元式。八、(10 分) 設(shè)有基本塊如下：T1:=3T2:=A*BT3:=9+T1M:=A*BT4:=C-DL:=T3*T4T2:=C+DN:=T2

5、1. 畫出 DAG圖；2. 設(shè) L，M，N 是出基本塊后的活躍變量，請(qǐng)給出優(yōu)化后的四元式序列。九、(8分)文法 G(S)及其 LR分析表如下，請(qǐng)給出串 baba#的分析過程。(1)S DbB(2)D d(3)D(4)B a(5)B Bba(6)BLR分析表ACTIONGOTObDa#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5( 注：答案格式為步驟 狀態(tài) 符號(hào) 輸入串 )5專業(yè)資料整理分享WORD格式可以任意編輯編譯原理試題 A (2003.12.4)一、回答下列問題： (30分 )1. (6 分 ) 對(duì)于下面程序段 programtest(in

6、put,output) vari,j:integer; procedureCAL(x,y:integer);begin y:=y*y;x:=x-y;y:=y-xend;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 分)2. (6 分) 計(jì)算文法 G(M)的每個(gè)非終結(jié)符的FIRST 和 FOLLOW集合，并判斷該文法是否是LL(1) 的，請(qǐng)說明理由G(M)：MTBTBa|B Db|eT|D d|解答：計(jì)算文法的 FIRS

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

8、屬性文法產(chǎn)生式語義規(guī)則SABCB.u:=S.uA.u:=B.v+C.vS.v:=A.vAaA.v:=3*A.uBbB.v:=B.uCcC.v:=1(3) 畫出字符串 abc 的語法樹 ;(4) 對(duì)于該語法樹，假設(shè) S.u 的初始值為 5，屬性計(jì)算完成后， S.v 的值為多少 答： (1)(2分)a b c(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

9、 表含有 i+1 個(gè)單元，自頂向下 每個(gè)單元依次存放著現(xiàn)行層、直接外層、?、直至最外層 (主程序， 0 層)等每層過程的最新活動(dòng)記錄的起始地址。通過 DISPLAY表可以訪問其外層過程的變量。5. （5 分） 對(duì)下列四元式序列生成目標(biāo)代碼：A:=B*CD:=E+AG:=B+CR0和 R1是可用寄存器。H:=G*D其中， H 在基本塊出口之后是活躍變量，答 : 目標(biāo)代碼序列LDR0BMULR0CLDR1EADDR1R0LDR0BADDR0CMULR0R1STR0H11專業(yè)資料整理分享6.（5 分） 寫出表達(dá)式 a+b*（c-d）對(duì)應(yīng)的逆波蘭式、三元式序列和抽象語法樹。答：逆波蘭式： （abcd-

10、*+）（1分 ）三元式序列:(2分）OPARG1ARG2(1)-cd(2)*b(1)(3)+a(2)抽象語法樹： （2 分 ）+答：（8 分） 構(gòu)造一個(gè) DFA，它接受=a ，b上所有包含 ab 的字符串6WORD格式可以任意編輯（2 分） 構(gòu)造相應(yīng)的正規(guī)式： （a|b）*ab（a|b）*13專業(yè)資料整理分享(3 分 )（3分 ） 確定化：b最小化：0 ，1，23，4，50 ，2，1，3，4，5baaba(6分） 寫一個(gè)文法使其語言為m為偶數(shù) nnmL(G)=abc|m,n 1， n 為奇數(shù)，答：文法 G(S):WORD格式可以任意編輯19專業(yè)資料整理分享S ACA aaAbb|abCccCc

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

12、 a,) LASTVT(T) ,a,)(2)(4分)a ( )a>>>>(<<<<)>><<<>>(3) 是算符優(yōu)先文法，因?yàn)槿魏蝺蓚€(gè)終結(jié)符之間至多只有一種優(yōu)先關(guān)系。 (1 分 )六、 (8 分)設(shè)某語言的 do-while語句的語法形式為S doS(1)WhileE(4) 優(yōu)先函數(shù) (3 分 )a()F44244G55523其語義解釋為：S(1)的代碼E 的代碼真假針對(duì)自下而上的語法分析器，按如下要求構(gòu)造該語句的翻譯模式，將該語句翻譯成四元 式：(1) 寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；(2) 寫出每個(gè)產(chǎn)生

13、式對(duì)應(yīng)的語義動(dòng)作。答：(1). 適合語法制導(dǎo)翻譯的文法(4 分 )G(S):RdoURS(1)WhileSUE(2).(4分)RdoR.QUAD:=NXQURS（1）WhileU.QUAD:=R.QUAD;BACKPATCH（S.CHAIN,NXQ）S UEBACKPATCH（E.TC,U.QUAD）;S.CHAIN:=E.FC答案二：（1）S doM 1 S（1）WhileM 2 EM （4 分 ）（2） M M.QUAD:=NXQ （ 4 分）S doM 1 S（1）WhileM 2 EBACKPATCH（1S） .CHAIN,M2.QUAD）;BACKPATCH（E.TC,M 1.QUA

14、D）;S.CHAIN:=E.FC七、（10 分） 將語句whileC>0doifA翻譯成四元式。答：100（j> ，C， 0，102）101（j ，- ，- ，112）102（jnz ，A，- ，106103（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）B=0thenC:=C+DelseC:=C*DWORD格式可以任意編輯專業(yè)資料整理分享112111 (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 是出基本塊后的活躍變量，請(qǐng)給出優(yōu)化后的四元式序列。答：1.(6分 )32. (4 分)M:=A*BS1 :=C- DL:=12*S1N: =C+D九、（8分）文法 G（S）及其 LR分析表如下，請(qǐng)給出串 baba#的分析過程。(1)S DbB(4