資源描述：
《編譯原理期末a試卷》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、一、填空（每空0.5分，共10分）1、編譯程序的功能是是對(高級語言)進行翻譯，使之生成目標代碼。2、編譯程序的工作過程一般劃分為5個階段：（詞法分析）、語法分析、語義分析與中間代碼生成，（代碼優(yōu)化）及目標代碼生成。另外還有表格管理和（出錯處理）。3、一個上下文無關文法所含四個組成部分是??一組終結符號、一組（非終結符號）、一個開始符號、（一組產生式）??。4、設G是一個給定的文法，S是文法的開始符號，如果S=>?x（其中x∈V*），則稱x是文法的一個（句型?）。5、規(guī)范歸約中的可歸約串是指句柄，算符優(yōu)先分析中的可歸約串是指（最左素短語）。6、在編
2、譯過程中,可采用的中間代碼形式有（）、（）、（）等。（三元式、間接三元式、四元式、逆波蘭式、抽象語法樹）（任選三個即可）7、語法分析最常用的兩類方法是（?自上而下?）和??（自下而上）??分析法。8、表達式（a+b)*c的后綴表達式為（ab+c*）。9、符號表的結構一般有（線性表）、（有序表）、（散列表或哈希表）等。分別使用的查找方法有（順序查找）、（折半查找）和（哈希法查找）10、代碼優(yōu)化的目的是（減少代碼的時空開銷）。11、寄存器是CPU內部的（存儲單元），其訪問時間小于CPU對內存的訪問時間。12、如果一個句子存在兩棵不同的語法樹就說明該句子
3、是（二義性）的。二、選擇題（每題1分，共10分）1、文法的開始符號經多步推導產生的文法符號序列(僅包含終結符)是文法的（D）。A.短語B.句柄C.句型D.句子2、構造編譯程序應掌握（D）。A.源程序B.目標語言C.編譯方法D.以上三項都是3、不屬于循環(huán)優(yōu)化的主要方法的是（B）。A.強度削弱B.刪除無用賦值C.刪除歸納變量D.代碼外提4、使用（A）可以定義一個程序的含義。A.語義規(guī)則B.詞法規(guī)則C.產生規(guī)則D.左結合規(guī)則5、優(yōu)化可生成（D）的目標代碼。A卷【第5頁，共5頁】A．運行時間較短B．占用存儲空間較小C．運行時間短但占用內存空間大D．運行時間
4、短且占用存儲空間小6、有文法G：E→E*T
5、T，T→T+i
6、i,則輸入串1+2*8+6按該文法G歸約,其值為（B）。A.23B.42C.30D.177、編譯技術中描述單詞符號的形成規(guī)則的常用工具有（D）。A．正規(guī)文法B．正規(guī)式C．有窮自動機D．以上都是8、編譯技術中常用（B）描述程序語言的語法。A．正規(guī)文法B．上下文無法文法C．屬性文法D．上下文有關文法9、詞法分析器的輸出結果是(C)。A．單詞的種別編碼B．單詞在符號表中的位置C．單詞的種別編碼和自身值D．單詞自身值10、以下(B)不是DFA的組成部分。A．有窮字母表B．初始狀態(tài)集合C．終止狀態(tài)集
7、合 D．有限狀態(tài)集合 三、簡答題（每題10分，共50分）1、有文法G[S]：S→SA
8、AA→a
9、b寫出句子aba的最左推導和最右推導。解：句子aba的最左推導為：S=>SA=>SAA=>AAA=>aAA=>abA=>aba（5分）句子aba的最右推導為：S=>SA=>Sa=>SAa=>Sba=>Aba=>aba（5分）2、一正規(guī)表達式為：b（b
10、a）
11、a（b
12、a（b
13、a）），寫出上述正規(guī)式對應的DFA和狀態(tài)裝換矩陣。解答：正規(guī)式對應的DFA為：（5分）YX123aaabbbbaDFAA卷【第5頁，共5頁】狀態(tài)矩陣為：（5分）狀態(tài)字符aBX1312
14、Y2YY3YYY--3、設G[E]:E->T
15、E+T
16、E-T,T->F
17、T*F
18、T/F,F->(E)
19、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+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、下面的文法是否是左遞歸的？如果是，該如何消除？E→E+
20、T
21、TT→T*F
22、FF→(E)
23、id解答：ET存在左遞歸，可以用以下等價文法消除左遞歸E→TE’（2分）E’→+TE’
24、ε（2分）T→FT’（2分）T’→*FT’
25、ε（2分）F→(E)
26、id（2分）5、設有文法G[S]：S→S/S
27、S-S
28、(S)
29、a，該文法是否有二義性？為什么？解答：有.該文法存在句子:a/a-a。（5分）A卷【第5頁，共5頁】該句子存在兩顆不同的語法樹，如圖：（5分）四、解答題（共30分）1、對于下面的程序：Programmainprocedurep(x,y,z)beginy:=y+1;z:=z+x;end;begina:=2;
30、b:=3;p(a+b,a,a);write(a);end.請分別按照（1）傳值(callbyvalue)（2）傳地址(ca
