編譯原理(模擬試卷-更新中)1

1、編譯原理（模擬試卷更新中）四川理工學(xué)院試卷(2015至2016學(xué)年第2學(xué)期) 系 專業(yè) 級(jí) 班 學(xué)號(hào) 姓名 密 封 線 密 封 線 內(nèi) 不 要 答 題 課程名稱：編譯原理（模擬試卷更新中）命題教師：黎遠(yuǎn)松適用班級(jí)：軟件2013級(jí)1-5班考試 2016年5月17日（12周二下午3:00-5:00） 共6頁(yè)題號(hào)一二三四五六七八評(píng)閱(統(tǒng)分)教師得分202018868128黎遠(yuǎn)松注意事項(xiàng)：1、 滿分100分。要求卷面整潔、字跡工整、無(wú)錯(cuò)別字。2、 考生必須將姓名、班級(jí)、學(xué)號(hào)完整、準(zhǔn)確、清楚地填寫在試卷規(guī)定的地方，否則視為廢卷。3、 考生必須在簽到單上簽到，若出現(xiàn)遺漏，后果自負(fù)。4、 如有答題紙，答案請(qǐng)

2、全部寫在答題紙上，否則不給分；考完請(qǐng)將試卷和答題卷分別一同交回，否則不給分。 試 題（模擬更新中）得分評(píng)閱教師一、 選擇題（共10個(gè)小題，每個(gè)小題2分，共20分）1詞法分析器的輸入是_。A符號(hào)串B源程序C語(yǔ)法單位D目標(biāo)程序2語(yǔ)言是_。A句子的集合B產(chǎn)生式的集合C符號(hào)串的集合D句型的集合3一個(gè)句型中稱為句柄的是該句型的最左_。A非終結(jié)符號(hào)B短語(yǔ)C句子D直接短語(yǔ)4掃描器所完成的任務(wù)是從字符串形式的源程序中識(shí)別出一個(gè)個(gè)具有獨(dú)立含義的最小語(yǔ)法單位即_。A字符B單詞C句子D句型5構(gòu)造編譯程序應(yīng)掌握_。A源程序B目標(biāo)語(yǔ)言C編譯方法D以上三項(xiàng)都是6 正規(guī)式M1和M2等價(jià)是指_。AM1和M2的狀態(tài)數(shù)相等BM1

3、和M2的有向邊條數(shù)相等CM1和M2所識(shí)別的語(yǔ)言集相等DM1和M2狀態(tài)數(shù)和有向邊條數(shù)相等7代碼優(yōu)化的目的是_。A節(jié)省時(shí)間B節(jié)省空間C節(jié)省時(shí)間和空間D把編譯程序進(jìn)行等價(jià)交換8生成中間代碼時(shí)所依據(jù)的是_。A語(yǔ)法規(guī)則B詞法規(guī)則C語(yǔ)義規(guī)則D等價(jià)變換規(guī)則9下推自動(dòng)機(jī)識(shí)別的語(yǔ)言是_。A0型語(yǔ)言B1型語(yǔ)言C2型語(yǔ)言D3型語(yǔ)言10對(duì)應(yīng)Chomsky四種文法的四種語(yǔ)言之間的關(guān)系是_。AL0ÌL1ÌL2ÌL3BL3ÌL2ÌL1ÌL0CL3=L2ÌL1ÌL0DL0ÌL1ÌL2=L3得分評(píng)閱教師二、 是非題（共10個(gè)小題

4、，每個(gè)小題2分，共20分。下列各題，你認(rèn)為正確的，請(qǐng)?jiān)陬}干的括號(hào)內(nèi)打“”，錯(cuò)的打“×”)1. 一個(gè)上下文無(wú)關(guān)文法的開(kāi)始符， 可以是終結(jié)符或非終結(jié)符。 (×) 2. 一個(gè)句型的直接短語(yǔ)是唯一的。 (×) 3. 已經(jīng)證明文法的二義性是可判定的。 （ ×） 4. 每個(gè)基本塊可用一個(gè) DAG 表示。 （ ） 5. 每個(gè)過(guò)程的活動(dòng)記錄的體積在編譯時(shí)可靜態(tài)確定。 （） 6. 2 型文法一定是 3 型文法。 （ ×） 7. 一個(gè)句型一定句子。 () 8. 算符優(yōu)先分析法每次都是對(duì)句柄進(jìn)行歸約。 (×) 9. 采用三元式實(shí)現(xiàn)三地址代碼時(shí)， 不利于對(duì)中

5、間代碼進(jìn)行優(yōu)化。 （ ） 10. 編譯過(guò)程中， 語(yǔ)法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。 ()得分評(píng)閱教師三、 回答下列問(wèn)題：（共3個(gè)小題，每個(gè)小題6分，共18分）1. 對(duì)于下面程序段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. 若參數(shù)傳遞的方法分別為(1)傳值、(2)傳地址，(3)傳名，請(qǐng)寫出程序執(zhí)行的輸出結(jié)果。答： (1) 3 (2)

6、 16(3) 16 (每個(gè)值2分)2. 計(jì)算文法G(M)的每個(gè)非終結(jié)符的FIRST和FOLLOW集合，并判斷該文法是否是LL(1)的，請(qǐng)說(shuō)明理由。G(M)：MTBTBa | eBDb | eT | eDd | e解答：計(jì)算文法的FIRST和FOLLOW集合：(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檢查文法的所有產(chǎn)生式，我們可以得到：1. 該文法不

7、含左遞歸，2. 該文法中每一個(gè)非終結(jié)符M，T，B，D的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。3. 該文法的非終結(jié)符T、B和D，它們都有e候選式，而且FIRST(T)FOLLOW(T)= a，b，e，d f所以該文法不是LL(1)文法。(2分)3. 考慮下面的屬性文法 產(chǎn) 生 式 語(yǔ) 義 規(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) 畫出字符串a(chǎn)bc的語(yǔ)法樹(shù);(2) 對(duì)于該語(yǔ)法樹(shù)，假設(shè)S.u的初始值為5，屬性計(jì)算完成后，S.v的值為多少?SABCabc答：(1)

8、 (2分)（2） S.v的值為18 (2分)得分評(píng)閱教師四、 (8分)構(gòu)造一個(gè)DFA，它接受S=a，b上所有包含ab的字符串。答案： (2分)構(gòu)造相應(yīng)的正規(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,6 b b b a543210 a a a a a b b b 最小化：0，1，2 3，4，50，

9、 2，1， 3，4，5baa01b3ba得分評(píng)閱教師五、 (6分)寫一個(gè)文法使其語(yǔ)言為L(zhǎng)(G)=anbncm| m,n1，n為奇數(shù)，m為偶數(shù)。文法G(S):得分評(píng)閱教師六、 (8分)對(duì)于文法G(S):1. 寫出句型b(Ma)b的最右推導(dǎo)并畫出語(yǔ)法樹(shù)。2. 寫出上述句型的短語(yǔ)，直接短語(yǔ)和句柄。SbM(TMabL)答：1. (4分) 2. (4分)短語(yǔ): Ma)， (Ma)， b(Ma)b直接短語(yǔ): Ma)句柄: Ma)得分評(píng)閱教師七、 (12分)對(duì)文法G(S)：Sa | | (T)TT，S | S(1) 構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合;(2) 構(gòu)造算符優(yōu)先表;(3) 是算符優(yōu)先

10、文法嗎?(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得分評(píng)閱教師八、 (8分)文法G(S)及其LR分析表如下，請(qǐng)給出串baba#的分析過(guò)程。(1) SDbB(2) Dd(3) D(4) Ba(5) BBba(6) BLR分析表ACTIONGOTObda#SBD0r3s3121acc2s43r24r6S5r665r4r46s