1、黃岡師范學院20122013學年度第一學期期末試卷參考答案 考試課程：編譯原理 考核類型：考試A卷考試形式：閉卷 出卷教師：牛冀平 考試專業：計算機科學與技術，軟件工程 考試班級：計科201001班，軟件201001班 一、填空（每空0.5分，共 10分）1、編譯程序的功能是是對(高級語言)進行翻譯，使之生成目標代碼。2、編譯程序的工作過程一般劃分為5個階段：（詞法分析）、語法分析、語義分析與中間代碼生成，（代碼優化）及目標代碼生成 。另外還有表格管理和（出錯處理）。3、一個上下文無關文法所含四個組成部分是  一組終結符號、一組（非終結符號）、一個開始符號、（一組產生式）&

2、#160; 。 4、設G是一個給定的文法，S是文法的開始符號，如果S=> x（其中xV*），則稱x是文法的一個（句型 ）。 5、規范歸約中的可歸約串是指句柄，算符優先分析中的可歸約串是指（最左素短語） 。6、在編譯過程中,可采用的中間代碼形式有（ ）、（ ）、（ ）等。（三元式、間接三元式、四元式、逆波蘭式、抽象語法樹）（任選三個即可）7、語法分析最常用的兩類方法是（ 自上而下 ）和  （自下而上）  分析法。8、表達式（a+b)*c的后綴表達式為（ab+c*）。9、符號表的結構一般有（線性表）、（

3、有序表）、（散列表或哈希表）等。 分別使用的查找方法有（順序查找）、（折半查找）和（哈希法查找）10、代碼優化的目的是（減少代碼的時空開銷）。11、寄存器是CPU內部的（存儲單元），其訪問時間小于CPU對內存的訪問時間。12、如果一個句子存在兩棵不同的語法樹就說明該句子是（二義性）的。2、 選擇題（每題1分，共 10分）1、文法的開始符號經多步推導產生的文法符號序列(僅包含終結符)是文法的（D ） 。 A.短語 B.句柄 C.句型 D.句子2、構造編譯程序應掌握（D） 。 A.源程序 B.目標語言 C.編譯方法 D.以上三項都是3、不屬于循環優化的主要方法的是（B） 。 A.強度削弱 B.刪除

4、無用賦值 C.刪除歸納變量 D.代碼外提4、使用（A） 可以定義一個程序的含義。 A.語義規則 B.詞法規則 C.產生規則 D.左結合規則5、優化可生成（D） 的目標代碼。 A運行時間較短 B占用存儲空間較小 C運行時間短但占用內存空間大 D運行時間短且占用存儲空間小6、有文法G：EE*T|T， TT+i|i ,則輸入串1+2*8+6按該文法G歸約,其值為（B）。 A.23 B.42 C.30 D.17 7、編譯技術中描述單詞符號的形成規則的常用工具有（ D ）。 A正規文法 B正規式 C有窮自動機 D以上都是8、編譯技術中常用（ B ）描述程序語言的語法。 A正規文法 B上下文無法文法 C屬

5、性文法 D上下文有關文法9、詞法分析器的輸出結果是( C )。 A單詞的種別編碼 B單詞在符號表中的位置 C單詞的種別編碼和自身值 D單詞自身值10、以下( B )不是DFA的組成部分。 A有窮字母表 B初始狀態集合 C終止狀態集合D有限狀態集合 三、簡答題（每題10分，共50分）1、有文法GS：SSA|A Aa|b 寫出句子aba的最左推導和最右推導。解： 句子aba的最左推導為：S=>SA=>SAA=>AAA=>aAA=>abA=>aba （5分）句子aba的最右推導為：S=>SA=>Sa=>SAa=>Sba=>Aba=&g

6、t;aba （5分）2、 一正規表達式為：b（b|a）| a（b|a（b|a） ，寫出上述正規式對應的DFA和狀態裝換矩陣。解答：正規式對應的DFA為： （5分）YX123aaabbbbaDFA 狀態矩陣為： （5分）狀態字符abX1312Y2YY3YYY-3、設GE: E->T|E+T|E-T, T->F|T*F|T/F , F->(E)|i 證明E+T*i*i+i 是該文法的句型 解答： E => E+T => E+T+T => E+T*F+T => E+T*F*F+T => E+T*i*F+T => E+T*i*i+T => E

7、+T*i*i+F => E+T*F*i+i （5分） 或E => E+T => E+F => E+i =>E+T+i=> E+T*F+i => E+T*i+i => E+T*F*i+i => E+T*i*i+i （5分） 即，E=>* E+T*i*i+i，所以是該文法的句型。4、下面的文法是否是左遞歸的？如果是，該如何消除？EE+T|TTT*F|FF(E)|id解答：E T 存在左遞歸， 可以用以下等價文法消除左遞歸 ETE （2分） E+TE| （2分） TFT （2分） T*FT| （2分） F(E)|id （2分） 5、設有文法

8、GS：SS/S|S-S|(S)|a，該文法是否有二義性？為什么？ 解答： 有. 該文法存在句子: a/a-a。（5分） 該句子存在兩顆不同的語法樹，如圖：（5分）四、解答題（共30分）1、對于下面的程序：Program main procedure p(x,y,z) begin y:=y+1; z:=z+x; end;begin a:=2; b:=3; p(a+b,a,a); write(a);end. 請分別按照（1）傳值 (call by value)（2）傳地址(call by reference) （3）傳名（call by name）(4)傳結果(call by result)的參數傳遞方式給出程序執行時的輸出結果。解：（1）傳名（call by name）輸出結果為：2 （5分） （2）傳地址(call by reference) 輸出結果為：8 （5分） （3）傳值 (call by value) 輸出結果為：9 （5分）(4) 傳結果(call by result) 輸出結果為：7 （5分）2、 對于文法G(S):S->bMbM->（L