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

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

3、和M2的有向邊條數相等CM1和M2所識別的語言集相等DM1和M2狀態數和有向邊條數相等7代碼優化的目的是_。A節省時間B節省空間C節省時間和空間D把編譯程序進行等價交換8生成中間代碼時所依據的是_。A語法規則B詞法規則C語義規則D等價變換規則9下推自動機識別的語言是_。A0型語言B1型語言C2型語言D3型語言10對應Chomsky四種文法的四種語言之間的關系是_。AL0ÌL1ÌL2ÌL3BL3ÌL2ÌL1ÌL0CL3=L2ÌL1ÌL0DL0ÌL1ÌL2=L3得分評閱教師二、 是非題（共10個小題

4、，每個小題2分，共20分。下列各題，你認為正確的，請在題干的括號內打“”，錯的打“×”)1. 一個上下文無關文法的開始符， 可以是終結符或非終結符。 (×) 2. 一個句型的直接短語是唯一的。 (×) 3. 已經證明文法的二義性是可判定的。 （ ×） 4. 每個基本塊可用一個 DAG 表示。 （ ） 5. 每個過程的活動記錄的體積在編譯時可靜態確定。 （） 6. 2 型文法一定是 3 型文法。 （ ×） 7. 一個句型一定句子。 () 8. 算符優先分析法每次都是對句柄進行歸約。 (×) 9. 采用三元式實現三地址代碼時， 不利于對中

5、間代碼進行優化。 （ ） 10. 編譯過程中， 語法分析器的任務是分析單詞是怎樣構成的。 ()得分評閱教師三、 回答下列問題：（共3個小題，每個小題6分，共18分）1. 對于下面程序段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. 若參數傳遞的方法分別為(1)傳值、(2)傳地址，(3)傳名，請寫出程序執行的輸出結果。答： (1) 3 (2)

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

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

8、 (2分)（2） S.v的值為18 (2分)得分評閱教師四、 (8分)構造一個DFA，它接受S=a，b上所有包含ab的字符串。答案： (2分)構造相應的正規式：(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得分評閱教師五、 (6分)寫一個文法使其語言為L(G)=anbncm| m,n1，n為奇數，m為偶數。文法G(S):得分評閱教師六、 (8分)對于文法G(S):1. 寫出句型b(Ma)b的最右推導并畫出語法樹。2. 寫出上述句型的短語，直接短語和句柄。SbM(TMabL)答：1. (4分) 2. (4分)短語: Ma)， (Ma)， b(Ma)b直接短語: Ma)句柄: Ma)得分評閱教師七、 (12分)對文法G(S)：Sa | | (T)TT，S | S(1) 構造各非終結符的FIRSTVT和LASTVT集合;(2) 構造算符優先表;(3) 是算符優先

10、文法嗎?(4) 構造優先函數。答：(1) (4分) (2) (4分)a(),a>>>>(<<<=<)>>,<<<>>(3) 是算符優先文法，因為任何兩個終結符之間至多只有一種優先關系。 (1分)(4) 優先函數(3分)a(),F44244G55523得分評閱教師八、 (8分)文法G(S)及其LR分析表如下，請給出串baba#的分析過程。(1) SDbB(2) Dd(3) D(4) Ba(5) BBba(6) BLR分析表ACTIONGOTObda#SBD0r3s3121acc2s43r24r6S5r665r4r46s