編譯原理試題庫

1、填空題1 編譯程序首先要識別出源程序中每 個 ，然后再分析每個 并翻譯 其意義。單詞，句子2編譯器常用的語法分析方法有和兩種。自底向上，自頂向下2 通常把編譯過程分為分析與綜合兩大階段。 詞法、 語法和語義分析是對源程序的分析， 中間代碼生成、 代碼優(yōu)化與目標(biāo)代碼的生成則是對源程 序的綜合。前端，后端4程序設(shè)計語言的發(fā)展帶來了日漸多變的運行時存儲管理方案，主要分為兩大 類，即 方案和 分配方案靜態(tài)存儲分配，動態(tài)存儲5對編譯程序而言，輸入數(shù)據(jù)是，輸出結(jié)果是 。源程序，目標(biāo)程序6文法 G 包括四個組成部分：一組終結(jié)符 號，一組非終結(jié)符號，一組 ，以 及一個開始符號。產(chǎn)生式7文法按產(chǎn)生式的形式分為四

2、種類型，它們是： 0 型文法，又稱短語文法； 1 型 文法，又稱上下文有關(guān)文法； 2 型文法， 又稱；3 型文法， 又稱上下文無關(guān)文法，正規(guī)文法8最右推導(dǎo)稱為，由規(guī)范推導(dǎo)產(chǎn)生的句型稱為規(guī)范句型。規(guī)范推導(dǎo)9設(shè) G 是一個文法， S 是它的開始符號， 如果 S=>* ，則稱是一個 僅由終結(jié)符號組成的句型是一 個。句型，句子10 對于一個文法 G 而言，如果 L(G) 中存在 某個句子對應(yīng)兩棵不同 ，那么該 文法就稱為是二義的。語法樹11通常程序設(shè)計語言的單詞符號分為五 種：基本字、 、常數(shù)、算符、界 限符。標(biāo)識符12在自底向上分析法中， LR 分析法把 “可 歸約串”定義為 。句柄13編譯中

3、常用的中間代碼形式有逆波蘭 式、三元式、 和四元式等。樹代碼14對中間代碼優(yōu)化按涉及的范圍分 為 ， 和全局優(yōu)化。局部優(yōu)化，循環(huán)優(yōu)化15局部優(yōu)化主要包括、利用公共子表達式和刪除無用賦值等內(nèi)容。合并已知量16為了構(gòu)造不帶回溯的遞歸下降分析程序，我們通常要消除 和提取左遞歸，左公共因子17. 計算機執(zhí)行用高級語言編寫的程序主要 有兩種途徑： 和 。解釋執(zhí)行，編譯執(zhí)行18. 掃描器是詞法分析，它接收輸入的 ，對源程序進行詞法分析并 識別出一個個 ，供語法分析器 使用。源程序，單詞符號19. 自下而上分析法采用和 等四種操作。移進、規(guī)約、錯誤處理、接受20. 一個 LR 分析器包括兩部分： 一個總控程

4、序， 和分析棧一張分析表21. 后綴式 abc-/所代表的表達式是 a/(b-c)22. 局部優(yōu)化是在范圍內(nèi)進行的一種優(yōu)化?；緣K23. 不同的編譯程序關(guān)于數(shù)據(jù)空間的存儲分 配策略可能不同， 但大部分編譯中采用的方 案有兩種： 靜態(tài)存儲分配方案和動態(tài)存儲分 配方案，而后者又分為 和。棧式動態(tài)存儲分配，堆式動態(tài)存儲分配24. 規(guī)范規(guī)約是 。最左規(guī)約25. 編譯程序的工作過程一般劃分為 5 個階 段：詞法分析、 、語義分析與 中間代碼生成， 代碼優(yōu)化及目標(biāo)代碼生 成。另外還有 和出錯處理。語法分析，表格管理26表達式 x+y*z/(a+b) 的后綴式 為。xyz*ab+/+27文法符號的屬性有綜合

5、屬性 和。繼承屬性28假設(shè)二位數(shù)組按行存放，而且每個元素 占用一個存儲單元， 則數(shù)組 a1.15,1.20 某個元素 ai ， j 的地址計算公式 為。a+(i-1)*20+j-129局部優(yōu)化是局限于一個范圍內(nèi)的一種優(yōu)化。基本塊二 選擇題1語言是A句子的集合 生式的集合C符號串的集合 型的集合B產(chǎn)D句A2編譯程序前三個階段完成的工作是A詞法分析、語法分析和代碼優(yōu)化B代碼生成、代碼優(yōu)化和詞法分析C詞法分析、語法分析、語義分析和中間 代碼生成D詞法分析、語法分析和代碼優(yōu)化C3一個句型中稱為句柄的是該句型的最左A 非終結(jié)符號B短語C句子D直接短語D4下推自動機識別的語言是A0 型語言C2 型語言B1

6、 型語言D3 型語言C5掃描器所完成的任務(wù)是從字符串形式的 源程序中識別出一個個具有獨立含義的最小語法單位即A 字符 B單詞 C句子D句型B6對應(yīng) Chomsky 四種文法的四種語言之間 的關(guān)系是A.L0 L1L2L3B.L3 L2L1L0C.L3=L2L1L0D L0 L1L2=L3B7詞法分析的任務(wù)是A 識別單詞B分析句子的含義C識別句子D生成目標(biāo)代碼A8常用的中間代碼形式不含 A 三元式B 四元式C逆波蘭式D語法樹DB節(jié)省空間D把編譯程9 代碼優(yōu)化的目的是 A節(jié)省時間 C節(jié)省時間和空間 序進行等價交換C10代碼生成階段的主要任務(wù)是A 把高級語言翻譯成匯編語言B把高級語言翻譯成機器語言C把

7、中間代碼變換成依賴具體機器的目標(biāo) 代碼D 把匯編語言翻譯成機器語言C11. 一個上下文無關(guān)文法 G 包括四個組成部 分：一組終結(jié)符，一組非終結(jié)符，一個（），以及一組（） 。A 字符串B 產(chǎn)生式C 開始符號D 文法C, B12. 程序的基本塊是指（ ）。A 一個子程序B 一個僅有一個入口和一個出口的語句C 一個沒有嵌套的程序段D 一組順序執(zhí)行的程序段， 僅有一個入口和一個 出口D13. 高級語言編譯程序常用的語法分析方法 中，遞歸下降分析法屬于（ ）分析方 法。A 自左向右B 自頂向下C 自底向上D 自右向左C14在通常的語法分析方法中， （ ）特別適 用于表達式的分析。A 算符優(yōu)先分析法B.

8、LR 分析法C遞歸下降分析法D. LL（ 1）分析法A15經(jīng)過編譯所得到的目標(biāo)程序是（）。A 四元式序列B 間接三元式序列C二元式序列D 機器語言程序或匯編語言程序D16 一個文法所描述的語言是（） ；描述一 個語言的文法是（） 。A 唯一的B 不唯一的C 可能唯一，也可能不唯一A, C17. 詞法分析器的輸出結(jié)果是（） 。A. 單詞的種別 ,編碼 B.單詞在符號表的位置 C.單詞的種別編碼和自身值 D. 單詞自身值C18. 正規(guī)式 M1 和 M2 等價是指（）。A. M1 和 M2 的狀態(tài)相等B. M1 和 M2 的有向邊條數(shù)相等C. M1 和 M2 所識別的語言集相等D.M1 和 M2 狀

9、態(tài)數(shù)和有向邊條數(shù)相等C19. 文法 G:S xSx|y 所識別的語言是()A. xyx B.(xyx)* C.x n yxD. x*yx*C20. 如果文法 G 是二義的，則它的任何句子（）A. 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定 相同B. 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能 不同C. 最左推導(dǎo)和最右推導(dǎo)必定相同D. 可能存在兩個不同的最左推導(dǎo)但是他們 對應(yīng)的語法樹相同。A21. 構(gòu)造編譯程序應(yīng)掌握（）A. 編譯程序B.目標(biāo)語言C.編譯方法D. 以上三項都是D22. 四元式之間的聯(lián)系是通過（）實現(xiàn)的 A. 指示器B.臨時變量C.符號表D. 程序變量B23. 程序的基本塊是指（）A. 一個子程序

10、B.一個僅有一個入口和一個出口C.一個沒有嵌套的程序段D. 一組順序執(zhí)行的程序段， 僅有一個入口和一 個出口D24. 優(yōu)化可生成（）的目標(biāo)代碼。 A.運行時間較短B. 占用存儲空間較小C. 運行時間短但占用內(nèi)存空間大 D.運行時間短且占用存儲空間小D25. 下列（）優(yōu)化方法不是針對循環(huán)優(yōu)化進行 的。A.強度削弱C.刪除多余運算B. 刪除歸納變量D. 代碼外提C26. 編譯程序使用（）區(qū)別標(biāo)識符的作用域A.說明標(biāo)識符的過程或者函數(shù)名B.說明標(biāo)識符的過程或函數(shù)的靜態(tài)層次C. 說明標(biāo)識符的過程或函數(shù)的動態(tài)層次D. 標(biāo)示符的行號B三 名詞解釋1詞法分析詞法分析的主要任務(wù)是從左向右掃描每行 源程序的符號

11、，按照詞法規(guī)則從構(gòu)成源程序 的字符串中識別出一個個具有獨立意義的最小語法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。2 LL(1) 文法若文法的任何兩個產(chǎn)生式 A | 都滿 足下面兩個條件：( 1) FIRST( ) FIRST( ) = ； ( 2)若* ，那么 FIRST( )FOLLOW( A ) = 。我們把滿足這兩個條件的文法叫做 LL(1) 文法，其中的第一個 L 代表從左向右掃描輸 入，第二個 L 表示產(chǎn)生最左推導(dǎo)， 1 代表在 決定分析器的每步動作時向前看一個輸入 符號。除了沒有公共左因子外， LL(1) 文法 還有一些明顯的性質(zhì)，它不是二義的，也不 含左遞歸

12、。3語言和文法文法就是語言結(jié)構(gòu)的定義和描述， 是有窮非 空的產(chǎn)生式集合。文法 G 定義為四元組的形式： G=（VN ，VT ， P，S）其中： VN 是非空有窮集合，稱為非終結(jié)符 號集合； VT 是非空有窮集合，稱為終結(jié)符 號集合； P是產(chǎn)生式的集合 （非空 ）；S是開始 符號 （或識別符號 ）。這里，VNVT= ，S VN。 V=V NVT，稱為文法 G 的字母表，它是出 現(xiàn)文法產(chǎn)生式中的一切符號的集合。文法 G 所描述的語言用 L（G）表示，它由文法 G 所 產(chǎn)生的全部句子組成，即 L（G）=x| S *x ， 其中 S為文法開始符號， 且 x VT 簡單的說， 文法描述的語言是該文法一切

13、句子的集合。4簡述代碼優(yōu)化的目的和意義。代碼優(yōu)化是盡量生成 “好 ”的代碼的編譯 階段。也就是要對程序代碼進行一種等價變 換，在保證變換前后代碼執(zhí)行結(jié)果相同的前 提下，盡量使目標(biāo)程序運行時所需要的時間 短，同時所占用的存儲空間少。5. 編譯過程通常分為哪幾個階段？ 每個過 程的主要功能？ 編譯過程通常分為詞法分析、語法分析、語 義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代 碼生成六個主要階段。 各個階段的主要功能如下： 詞法分析階段：讀入源程序，對構(gòu)成源程序 的字符流進行掃描和分解， 識別出一個個單 詞，并表示成計算機內(nèi)部的形式。 語法分析階段：在詞法分析的基礎(chǔ)上，將單 詞序列分解成各類語法短語，如

14、“表達式” “語句”、“程序”等，確定整個輸入串是否 構(gòu)成語法上正確的程序。 語義分析階段：審查源程序有無語義錯誤， 為代碼生成階段收集類型信息。 中間代碼生成階段： 將源程序翻譯成一種復(fù) 雜性介于源程序與目標(biāo)程序之間的內(nèi)部形 式（中間代碼） 。代碼優(yōu)化： 對前階段產(chǎn)生的中間代碼進行等 價變換， 目的是使將來生成的目標(biāo)代碼更為 高效。目標(biāo)代碼生成：把中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼 或匯編指令代碼。6. 簡述代碼優(yōu)化的原則和目標(biāo) 原則：對中間代碼進行等價變換，使代碼變 換后功能不變。目標(biāo)：變換后的代碼運行速度更快，占用的 存儲空間更少。7. 試為表達式 w+(a+b)

15、*(c+d/(e-10)+8) 寫出相 應(yīng)的逆波蘭表示。wab+cde10-/+8+*+8. 寫出表達式 a b*(c-d)/e 的逆波蘭式和三 元序列。逆波蘭式 : abcd-*e/+三元序列 : oparg1arg2(1) -cd(2) *b(1)(3) /(2)e(4) +a(3)四判斷題請在括號內(nèi)，正確的劃 ，錯誤 的劃 ×）1. 編譯程序是對高級語言程序的解釋執(zhí)行。（）×2. 一個有限狀態(tài)自動機中，有且僅有一個 唯一的終態(tài)（）×3. 目標(biāo)代碼生成時，應(yīng)考慮如何充分利用 計算機的寄存器的問題。（ ）4. 語法分析時必須先消除文法中的左遞歸（）×自

16、頂向下5. LR 分析法在自左至右掃描輸入串時就能 發(fā)現(xiàn)錯誤，但不能準(zhǔn)確的指出出錯地點 （）6. 逆波蘭表示法表示表達式時無需使用括 號。（）7. 靜態(tài)數(shù)組的存儲空間可以在編譯時確靜態(tài)鏈接的情況下 , 鏈接器可以確定 , 編譯只是把文本文件編譯成為 obj 文件并不確定地址8. 進行代碼優(yōu)化時應(yīng)該著重考慮循環(huán)的代 碼優(yōu)化，這對提高代碼的效率將起更大作 用。（ ）×9. 兩個正規(guī)集相等的必要條件是他們對應(yīng) 的正規(guī)式等價。（）×應(yīng)該說正規(guī)式等價的必要條件是正規(guī)集相等10. 一個語義子程序描述了一個文法所對 應(yīng)的翻譯工作。（）1 審查每個語法結(jié)構(gòu)的靜態(tài)語義， 2 進行制導(dǎo)翻譯11

17、. 一個上下文無關(guān)文法的開始符，可以是 終結(jié)符或非終結(jié)符。（）×12. 已經(jīng)證明文法的二義性是可判定的（）×13. 每個基本塊可用一個 DAG表示 （）14. 一個句型一定是句子 （ ）15. 算符優(yōu)先分析法每次都是對句柄進行歸 約。( )16. 采用三元式實現(xiàn)三地址代碼時，不利于 對中間代碼進行優(yōu)化。()17. 編譯過程中，語法分析器的任務(wù)是分析 單詞是怎樣構(gòu)成的。( )×18. 目標(biāo)代碼生成時，應(yīng)考慮如何充分利用 計算機的寄存器的問題。19. 并不是每個文法都能改寫成 LL(1) 文法 ( )20. 一個 LL(1) 文法一定是無二義的()四簡單題1設(shè)有文法G

18、1: S SaQ QQQbRRR cSd e( 1)證明句型 QbRae 是規(guī)范句型( 2)給出句型 QbRae 的語法樹和句柄：解答： 證明：（ 1）因為句型 QbRae 可由文法開始 符 S 經(jīng)過規(guī)范推導(dǎo)產(chǎn)生，推導(dǎo)過程如 下： S => SaQ => SaR => Sae => Qae => QbRaeSQ所以句型 QbRae 是規(guī)范句型（ 2 分） （2）、語法樹（ 1 分）SQQ b句柄： QbR2. 設(shè) 有 非 確 定 的 有 限 自 動 機 NFA M=（A,B,C,0 ，1, ,A,C） 其中： （A,0） =C, （A,1）=A,B, （B ， 1

19、）=C（C，1）=C 。請畫出狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換 圖。解答：狀態(tài)轉(zhuǎn)換距陣為：符號狀態(tài)01ACA，BBCCC狀態(tài)轉(zhuǎn)換圖為：3. 構(gòu)造正規(guī)式 1（0|1） *101 相應(yīng)的 DFA.解：4.設(shè)有基本塊：T1：2T2： 10/T1T3： SRT4： SRA： T2 * T4B：AT5： S RT6 ： T3 * T5B： T6(1) 畫出 DAG 圖(2) 假設(shè)基本塊出口時只有 A，B 還被引用， 請寫出優(yōu)化后的四元序列。4、(1) DAG 圖T1 210(2)優(yōu)化后的四元式序列：T3:=S-RT4:=S+RA:=5 * T4B:=T4*T35. 考慮一下文法： D T V T int | fl

20、oatV id ,V | id（1）在該文法中提取左公共因子。 （ 2）為所得的文法的非終結(jié)符構(gòu)造First集合和 Follow 集合。（ 3）說明所得的文法是 LL（1） 文法。（ 4）為所得的文法構(gòu)造 LL（1） 分析表。解答：（1）文法存在左公因子，提取左公因子后的文法為：D T VT int | float V id V'V' ,V | (2)非終結(jié)符First 集合Follow 集合D int , float #T int , float idV id #V' , , #(3)(a) First (T int ) First (T float )=;(b) V

21、'=>First(V ' ,V) Follow(V)= , , # = 根據(jù) LL(1) 文法的定義判斷，此文法是 LL(1) 文法；LL(1) 分析表為：intfloatid#DD TVD TVTT intTfloatVVidV'V'V' ,VV' 6. 考慮下面的程序：procedure p(x, y, z) ；beginy:=y+2;z:=z+x;endbegina:=5;b:=2;p(a+b, a-b, a);print aend. 試問，若參數(shù)傳遞的方式分別采用傳地址和 傳值時，程序執(zhí)行后輸出 a 的值是什么 ?解答：傳值 a=5

22、傳地址 a=127證明下述文法 G： S aSbS|aS|d 是二義 性文法。證明：一個文法，如果存在某個句子有不只 一棵語法分析樹與之對應(yīng)，那么稱這 個文法是二義性文法。句子 aadbd 有兩棵語法樹。如下圖：(2)8. 設(shè)有基本塊如下：T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6（ 1）畫出 DAG 圖；（ 2）設(shè) A,B 是出基本塊后的活躍變量，請 給出優(yōu)化后的四元式序列。解答：（ 1） DAG 如右圖：T3(2) 四元式序列：T1:=S+RT4:=S/RA: =T1-T4B: =T1*4 9. 設(shè)文法

23、G（S）:S （T） | aS | aT T,S | S（1）消除左遞歸和提公共左因子；2）構(gòu)造相應(yīng)的 FIRST和 FOLLOW集合；3）構(gòu)造預(yù)測分析表。解答： (1) S (T) | aS 'S'S |T ST'T' ,ST ' | (2) FIRST(S)= a, ( FIRST(S')=a, (, FIRST(T)=a, ( FIRST(T ' )=, FOLLOW(S)=, ), # FOLLOW(S ')=, ), # FOLLOW(T)= ) FOLLOW(T')= )(3)()a#SS (T)S aS

24、9;S'S' SS'S' SS'S'TTST'TST'T' ,ST 'T'T'11.已知文法 GS 為 S aSb|Sb|b ，試證明文法 GS 為二義文法。證明：由文法 GS：SaSb|Sb|b，對句子 aabbbb 對應(yīng) 的兩棵語法樹為：因此，文法 GS為二義文法12. 考慮下面的程序：procedure p(x, y, z) ； beginy:=y+2;z:=z+x;endbegina:=5;b:=2;p(a+b, a-b, a);print aend.試問，若參數(shù)傳遞的方式分別采用傳地址和

25、傳值時，程序執(zhí)行后輸出 a 的值是什么 ?答案： 傳值 a=2 傳地址 a=1513. 寫出表達式 a:=(b+c)*e+(b+c)/f 的逆波蘭式和三 元序列。逆波蘭式 abc+e*bc+f/+:= 三元序列 op arg1 arg2(1) +bc(2) *(1)e(3) +bc(4) /(3)f(5) +(2)(4)(6) :=a(5)14什么是句柄？什么是素短語？ 一個句型的最左直接短語稱為該句型的句 柄。素短語是這樣的一個短語， 它至少包含一個 終結(jié)符并且不包含更小的素短語。15. 已知文法 GSSS*aF | aF | *aFF +aF | +a 消除文法左遞歸和提公共左因子。解答：

26、消除左遞歸SaFS' | *aFS ' S' *aFS' | F +aF | +a 提公共左因子 , 文法 G'(S) SaFS' | *aFS 'S' *aFS' | F+aF'F'F |16對于文法 GS ： S AB， A Aa|bB ， B a|Sb 求句型 baSb 的全部短語、 直接短語 和句柄？句型 baSb 的語法樹如圖五 (2) 所示。a圖: 句型 baSb 的的語法樹解：baSb 為句型 baSb的相對于 S的短語， ba 為 句型 baSb的相對于 A的短語，Sb為句型 baSb 的相

27、對于 B的短語，且為直接短語， a 為句 型 baSb 的相對于 B 的短語，且為直接短語 和句柄。17. 已知文法 G(S)S aAcBeA Ab| bB d(1) 給出句子 abbcde 的最左推導(dǎo)及畫出 語法樹；(2) 給出句型 aAbcde 的短語、素短語。解答： (1)S=>aAcBe=>aAbcBe=>abbcBe=>abbcde(2) 短語: aAbcde, Ab, d素短語 : Ab, d18. 已知文法 G(S)E E+T | TT T*F| FF (E)| i(1) 給出句型 (i+i)*i+i 的最左推導(dǎo)及畫出語法樹；(2) 給出句型 (E+T)*

28、i+F 的短語， 素短 語和最左素短語。解答： (1)E=>E+T=>T+T=>T*F+T=>F*F+T=>(E)*F+T =>(E+T)*F+T=>(T+T)*F+T=>(F+T)*F+T=>(i+T)*F+T=>(i+F)*F+T=>(i +i)*F+T=>(i+i)*i+T=>(i+i)*i+F=>(i+i)*i+i(2) 短語 i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F 素短語 i, E+T 最左素短語 E+T19. 何謂優(yōu)化？按所涉及的程序范圍可分 為哪幾級優(yōu)化？ 優(yōu)化：對程序進行各種等價變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化20. 目標(biāo)代碼有哪幾種形式？生成目標(biāo)代 碼時通常應(yīng)考慮哪幾個問題？目標(biāo)代碼通常采用三種形式：機器語言，匯 編語言，待裝配機器語言模塊。 應(yīng)著重考慮的問題：(1) 如何使生成的目標(biāo)代碼較短；(2) 如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；(3) 如何充分利用指令系統(tǒng)的特點。21. 一字母表 =a, b ，試寫出 上所有 以 a 為首的字組成的正規(guī)集相對應(yīng)的正規(guī) 式。解答：正規(guī)式 a ( a | b )*。22. 設(shè)有基本塊D:=A-CE:=A*CF:=D*ES:=2T:=A-