編譯原理試題庫

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

2、, 號, 口亠 。 歡迎下載24 1型 F文有關(guān)文法；2型文法, .；3型文法，又稱 產(chǎn)生式 7. 文法按產(chǎn)生式的形式分為四種類型，它 們是：0型文法，又稱短語文法； 文法，又稱 又稱 F文無關(guān)文法，正規(guī)文法 8. 最右推導(dǎo)稱為 ，由規(guī)范推導(dǎo)產(chǎn)生 的句型稱為規(guī)范句型。 規(guī)范推導(dǎo) 9. 設(shè)G是一個文法，S是它的開始符q 如果S=* a，則稱a是一個_ 僅由終結(jié)符號組成的句型是一 句型，句子 10對于一個文法G而言，如果L(G)中存在 某個句子對應(yīng)兩棵不同，那么該 文法就稱為是二義的。 語法樹 11. 通常程序設(shè)計語言的單詞符號分為五 :基本字、常數(shù)、算符、界 限符。 標(biāo)識符 “可 12. 在自底

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

4、和等四種操作。 移進(jìn)、規(guī)約、錯誤處理、接受 20. 個LR分析器包括兩部分：一個總控程 序， 和分析棧。 一張分析表 21. 后綴式abc-/所代表的表達(dá)式是 a/(b-c) 范圍內(nèi)進(jìn)行的 22. 局部優(yōu)化是在 種優(yōu)化。 基本塊 23.不同的編譯程序關(guān)于數(shù)據(jù)空間的存儲分 配策略可能不同，但大部分編譯中采用的方 案有兩種：靜態(tài)存儲分配方案和動態(tài)存儲分 配方案，而后者又分為 和 棧式動態(tài)存儲分配，堆式動態(tài)存儲分配 24.規(guī)范規(guī)約是 最左規(guī)約 25.編譯程序的工作過程一般劃分為5個階 段：詞法分析、語義分析與 中間代碼生成，代碼優(yōu)化及目標(biāo)代碼生 成。另外還有和出錯處理 語法分析，表格管理 26 .表

5、達(dá)式x+y*z/(a+b)的后綴式 為 xyz*ab+/+ 27.文法符號的屬性有綜合屬性 和 繼承屬性 28.假設(shè)二位數(shù)組按行存放，而且每個元素 占用一個存儲單元，貝y數(shù)組a仁15,仁20 某個元素ai, j的地址計算公式 為 a+(i-1)*20+j-1 范圍 29.局部優(yōu)化是局限于一個 內(nèi)的一種優(yōu)化 基本塊 選擇題 1 .語言是 A.句子的集合 生式的集合 C.符號串的集合 型的集合 A 2.編譯程序前三個階段完成的工作是 A .詞法分析、 B .代碼生成、 C.詞法分析、 代碼生成 D .詞法分析、 語法分析和代碼優(yōu)化 語法分析和代碼優(yōu)化 代碼優(yōu)化和詞法分析 語法分析、語義分析和中間

6、C 3.個句型中稱為句柄的是該句型的最左 A 非終結(jié)符號 B .短語 C.句子 D .直接短語 D 4.下推自動機(jī)識別的語言是 A. 0型語言 C. 2型語言 C 5.掃描器所完成的任務(wù)是從字符串形式的 源程序中識別出一個個具有獨(dú)立含義 的最小語法單位即 字符B 單詞 C句子 D .句型 B 6 對應(yīng)Chomsky四種文法的四種語言之間 的關(guān)系是 A丄0匚L1u L2匚L3 BL3u L2U L1U L0 CL3=L2u Llu L0 D L0uLluL2=L3 B 7 詞法分析的任務(wù)是 A識別單詞B 分析句子的含義 c識別句子D 生成目標(biāo)代碼 A 8常用的中間代碼形式不含 A .三兀式B .

7、四兀式 D 9.代碼優(yōu)化的目的是 A節(jié)省時間 B.節(jié)省空間 C.節(jié)省時間和空間 D .把編譯程 序進(jìn)行等價交換 C.逆波蘭式 D .語法樹 C 10.代碼生成階段的主要任務(wù)是 A .把高級語言翻譯成匯編語言 B .把高級語言翻譯成機(jī)器語言 間代碼變換成依賴具體機(jī)器的目標(biāo) C.把中 代碼 D .把匯編語言翻譯成機(jī)器語言 C 組非終結(jié)符 11. 一個上下文無關(guān)文法 G包括四個組成部 分：一組終結(jié)符， （）,以及一組（）。 產(chǎn)生式 D. 文法 A. 字符串B. C, B 12.程序的基本塊是指（ A. ）。 一個僅有一個入 C.開始符號 一個子程序B. C. 口和一個出口的語句 一個沒有嵌套的程序段

8、D. 一組順 序執(zhí)行的程序段，僅有一個入口和一個 出口 D 13. 高級語言編譯程序常用的語法分析方法 中，遞歸下降分析法屬于（ 法。 自左向右 C.自底向 ）分析方 B.自頂向下 D. 自右向左 C 14.在通常的語法分析方法中，（）特別適 用于表達(dá)式的分析。 A .算符優(yōu)先分析法B. LR分析法 C.遞歸下降分析法D. LL （1）分析法 A ）。 間接三元式序列 B. D.機(jī)器語言程序或 15.經(jīng)過編譯所得到的目標(biāo)程序是（ A .四元式序列 C.二元式序列 匯編語言程序 D 16. 一個文法所描述的語言是（） 個語言的文法是（）。 唯一的 B .不唯一的 能唯一，也可能不唯一 ;描述 C

9、. 可 A, C 17.詞法分析器的輸出結(jié)果是（）。 A.單詞的種別，編碼B.單詞在符號表的位置 C.單詞的種別編碼和自身值D.單詞自身值 C A. M1 B. M1 C. M1 D. M1 18.正規(guī)式M1和M2等價是指（）。 和M2的狀態(tài)相等 和M2的有向邊條數(shù)相等 和M2所識別的語言集相等 和M2狀態(tài)數(shù)和有向邊條數(shù)相等 C 19. 文法G:S7xSx|y所識別的語言是() A. xyxB.(xyx)*C.xn yx D.x*yx* C 20. 如果文法G是二義的，則它的任何句子 a （） A. 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定 相同 B. 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能 不同 C.

10、 最左推導(dǎo)和最右推導(dǎo)必定相同 D. 可能存在兩個不同的最左推導(dǎo)但是他們 對應(yīng)的語法樹相同。 A 21. 構(gòu)造編譯程序應(yīng)掌握（） G編譯方 A.編譯程序B. 目標(biāo)語言 法D.以上三項(xiàng)都是 D 22. 四元式之間的聯(lián)系是通過（）實(shí)現(xiàn)的。 A.指示器B.臨時變量 C.符號表D.程序變量 B 23. 程序的基本塊是指（） B. 一個 D. 一組 個入口和一 A. 個子程序 僅有一個入口和一個出口 C. 一個沒有嵌套的程序段 順序執(zhí)行的程序段，僅有 個出口 D 24. 優(yōu)化可生成（）的目標(biāo)代碼。 A. 運(yùn)行時間較短 B. 占用存儲空間較小 C. 運(yùn)行時間短但占用內(nèi)存空間大 D. 運(yùn)行時間短且占用存儲空間

11、小 D 25. 下列（）優(yōu)化方法不是針對循環(huán)優(yōu)化進(jìn)行 的。 A.強(qiáng)度削弱 C刪除多余運(yùn)算 B. 刪除歸納變量 D代碼外提 C 26. 編譯程序使用（）區(qū)別標(biāo)識符的作用域 A. 說明標(biāo)識符的過程或者函數(shù)名 B. 說明標(biāo)識符的過程或函數(shù)的靜態(tài)層次 C. 說明標(biāo)識符的過程或函數(shù)的動態(tài)層次 D. 標(biāo)示符的行號 名詞解釋 1.詞法分析 詞法分析的主要任務(wù)是從左向右掃描每行 源程序的符號，按照詞法規(guī)則從構(gòu)成源程序 的字符串中識別出一個個具有獨(dú)立意義的 最小語法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示 (toke n)，送給語法分析程序。 2LL(1)文法 |卩都滿 若文法的任何兩個產(chǎn)生式 A 足下面兩個條件： (1)

12、 FIRST(a ) C FIRST(P ) = ； (2) 若卩-* g，那么 FIRSTS ) c FOLLOW( A ) = *。 LL(1) 中的第一個L代表從左向右掃描輸 LL(1)文法 我們把滿足這兩個條件的文法叫做 文法， 入，第二個L表示產(chǎn)生最左推導(dǎo)，1代表在 決定分析器的每步動作時向前看一個輸入 符號。除了沒有公共左因子外， 還有一些明顯的性質(zhì)，它不是二義的，也不 含左遞歸。 3 .語言和文法 文法就是語言結(jié)構(gòu)的定義和描述，是有窮非空的產(chǎn)生式集合。 文法G定義為四元組的形式：G=（VN，VT， P，S） 其中：Vn是非空有窮集合，稱為非終結(jié)符 號集合；Vt是非空有窮集合，稱為

13、終結(jié)符 號集合；P是產(chǎn)生式的集合（非空）；S是開始 符號（或識別符號）。這里，VN QVt=0 ，S Vn。 V=Vn U Vt，稱為文法G的字母表，它是出 現(xiàn)文法產(chǎn)生式中的一切符號的集合。文法G 口 號, 比中S為文法開始符 所描述的語言用L（G）表示，它由文法G所 產(chǎn)生的全部句子組成，即 L（G）=x| S= *x， -vt+ 簡單的說， 文法描述的語言是該文法一切句子的集合。 4. 簡述代碼優(yōu)化的目的和意義。 代碼優(yōu)化是盡量生成 好”的代碼的編譯 階段。也就是要對程序代碼進(jìn)行一種等價變 換，在保證變換前后代碼執(zhí)行結(jié)果相同的前 提下，盡量使目標(biāo)程序運(yùn)行時所需要的時間 短，同時所占用的存儲空

14、間少。 5. 編譯過程通常分為哪幾個階段？每個過 間代碼生成、代碼優(yōu)化和目標(biāo)代 程的主要功能？ 編譯過程通常分為詞法分析、語法分析、語 義分析、中 碼生成六個主要階段。 各個階段的主要功能如下： 詞法分析階段：讀入源程序，對構(gòu)成源程序 的字符流進(jìn)行掃描和分解， 識別出一個個單 詞，并表示成計算機(jī)內(nèi)部的形式。 語法分析階段：在詞法分析的基礎(chǔ)上，將單 詞序列分解成各類語法短語，如“表達(dá)式”、 “語句”、“程序”等，確定整個輸入串是否 構(gòu)成語法上正確的程序。 語義分析階段：審查源程序有無語義錯誤， 為代碼生成階段收集類型信息。 中間代碼生成階段：將源程序翻譯成一種復(fù) 雜性介于源程序與目標(biāo)程序之間的內(nèi)

15、部形 式（中間代碼）。 代碼優(yōu)化：對前階段產(chǎn)生的中間代碼進(jìn)行等 價變換，目的是使將來生成的目標(biāo)代碼更為 咼效。 間代碼變換成特定機(jī)器 目標(biāo)代碼生成：把中 上的絕對指令代碼或可 或匯編指令代碼。 可重定位的指令代碼 6. 簡述代碼優(yōu)化的原則和目標(biāo) 原則：對中間代碼進(jìn)行等價變換，使代碼變 換后功能不變。 目標(biāo)：變換后的代碼運(yùn)行速度更快，占用的 存儲空間更少。 7. 試為表達(dá)式w+(a+b)*(c+d/(e-10)+8)寫出相 應(yīng)的逆波蘭表示。 wab+cde10-/+8+*+ 8. 寫出表達(dá)式a+ b*(c-d)/e的逆波蘭式和 元序列。 精品文庫 逆波蘭式：abcd-*e/+ 三元序列：op 四

16、.判斷 的劃X） (1) - c d * b (1) / (2) e + a (3) 募在括 號號內(nèi)， 正確的劃 V,錯誤 arg1 arg2 1.編譯程序是對高級語言程序的解釋執(zhí) 行。 （） 2. 個有限狀態(tài)自動機(jī)中，有且僅有一個 唯一的終態(tài) （） 3. 目標(biāo)代碼生成時，應(yīng)考慮如何充分利用 歡迎下載 計算機(jī)的寄存器的問題。 () V 4. 語法分析時必須先消除文法中的左遞歸 () X自頂向下 5. LR分析法在自左至右掃描輸入串時就能 發(fā)現(xiàn)錯誤，但不能準(zhǔn)確的指出出錯地點(diǎn) ( V 6. 口 號 ( 逆波蘭表示法表示表達(dá)式時無需使用括 V 7. 靜態(tài)數(shù)組的存儲空間可以在編譯時確 X 靜態(tài)鏈接的情

17、況下，鏈接器可以確定，編譯只是把文本文件編譯成為 obj文件并不確定地址 8.進(jìn)行代碼優(yōu)化時應(yīng)該著重考慮循環(huán)的代 碼優(yōu)化，這對提高代碼的效率將起更大作 用。（） X 9. 兩個正規(guī)集相等的必要條件是他們對應(yīng) 的正規(guī)式等價。 （） X應(yīng)該說正規(guī)式等價的必要條件是正規(guī)集相等 10. 一個語義子程序描述了一個文法所對 應(yīng)的翻譯工作。 （） X 1審查每個語法結(jié)構(gòu)的靜態(tài)語義，2進(jìn)行制導(dǎo)翻譯 11. 一個 F文無關(guān)文法的開始符，可以是 終結(jié)符或非終結(jié)符。 ( ) X 12.已經(jīng)證明文法的二義性是可判定的。 ( ) X 13.每個基本塊可用一個 DAG表示。 ( ) V 14. 一個句型一定是句子。 ()

18、 X 15.算符優(yōu)先分析法每次都是對句柄進(jìn)行歸 約。 () 16. 采用三元式實(shí)現(xiàn)三地址代碼時，不利于 對中間代碼進(jìn)行優(yōu)化。 ( ) V 17. 編譯過程中，語法分析器的任務(wù)是分析 單詞是怎樣構(gòu)成的。 () X 18. 目標(biāo)代碼生成時，應(yīng)考慮如何充分利用 計算機(jī)的寄存器的問題。 V 19. 并不是每個文法都能改寫成LL(1)文法。 () V 20. ( 個LL(1)文法一定是無二義的 歡迎下載55 設(shè)有文法G1: S f SaQ Qf QbR Rf cSd 1. 簡單題 e (1) 證明句型 QbRae是規(guī)范句型 (2) 給出句型QbRae的語法樹和句柄: 解答：證明: （1）因?yàn)榫湫蚎bRa

19、e可由文法開始 符S經(jīng)過規(guī)范推導(dǎo)產(chǎn)生，推導(dǎo)過程如 下：S = SaQ = SaR = Sae = Qae = QbRae (2)、 所以句型QbRae是規(guī)范句型（2分） 語法樹（1分） S S 句柄: QbR NFA (A,0) (C, 定的有限自動機(jī) ，1/,A,C）其中： （B，1）=C柱 2.設(shè)有非 M=（A,B,C,0 =C, $（A,1）=A,B, 5 1）=C。請畫出狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換 圖。 解答：狀態(tài)轉(zhuǎn)換距陣為: 符號 狀態(tài) 0 1 A C A, B B 0 C C 0 C 狀態(tài)轉(zhuǎn)換圖為: 3.構(gòu)造正規(guī)式1 (0 1) *101 相應(yīng)的DFA. 解: 4. 設(shè)有基本塊: T1

20、 := 2 T2 : = 10/T1 T3 : = S R T4 : = S A: = T2 * T4 B:= A T5 : = S T6 : = T3 * T5 B:= T6 畫出DAG圖 假設(shè)基本塊出口時只有 A, B還被引用, 請寫出優(yōu)化后的四元序列。 4、(1) DAG 圖 Ti2 10 (2)優(yōu)化后的四元式序列: T3:=S-R T4:=S+R A:=5 * T4 B:=T4*T3 5. 考慮一下文法：D f T V Tf int | float Vf id ,V | id (1) 在該文法中提取左公共因子。 First (2) 為所得的文法的非終結(jié)符構(gòu)造 集合和Follow集合。

21、(3) 說明所得的文法是 LL 文法。 (4) 為所得的文法構(gòu)造 LL(1)分析表。 解答： (1) 文法存在左公因子，提取左公因子后 的文法為： T V int | float id V ,V | e D f T f V f V f 非終結(jié)符 First集合 Follow集合 D int , float # T int , float id V id # V ，e # (3) (a) First (T int ) n First (T float ) =0 ； (b)V= First(V ,V) n Follow(V)= , 根據(jù)LL(1)文法的定義判斷，此文法是LL(1)文法; LL(1)

22、分析表為: int float id # D D T TV D T TV T T Tint Tt float V Vt idV V V T ,V V T e 6. 考慮下面的程序: P rocedure p(x, y, z); begin y:=y+2; z:=z+x; end begin a:=5; b:=2; p (a+b, a-b, a); p rint a end. 試問，若參數(shù)傳遞的方式分別采用傳地址和 傳值時，程序執(zhí)行后輸出a的值是什么？ 解答：傳值 a=5 傳地址a=12 7.證明下述文法 G : St aSbS|aS|d是二義 性文法。 證明： 個文法，如果存在某個句子有不只

23、棵語法分析樹與之對應(yīng)，那么稱這 義性文法。 個文法是 句子 aadbd 有 兩棵語法樹。如下圖： (2) 構(gòu)造相應(yīng)的 FIRST和FOLLOW合; (3) 構(gòu)造預(yù)測分析表。 解答： S f (T) | aS Sf S (2) FIRST( S)=a, ( FIRST(S )=a,(, FIRST(T)=a, ( FIRST(T )=， e FOLLOW(S)=, ), # FOLLOW(S )=,), # FOLLOW(T)= ) FOLLOW(T )= ) ( ) a # S S f (T) S f aS S Sf S Sf Sf S Sf Sf T Tf ST Tf ST Tf ,ST T

24、 Tf 11.已知文法 GS為S T aSb|Sb|b，試證明文法 GS為二義文法。 證明： 由文法GS: StaSblSblb對句子aabbbb對應(yīng) 的兩棵語法樹為： S /K a S b /t a S b 因此，文法 GS為二義文法。 12.考慮下面的程序: procedure p(x, y, z) ; beg in y:=y+2; z:=z+x; end begi n a:=5; b:=2; p(a+b, a-b, a); print a end. 試問，若參數(shù)傳遞的方式分別采用傳地址和 傳值時，程序執(zhí)行后輸出 a的值是什么？ 答案： 傳值 a=2 傳地址a=15 13.寫出表達(dá)式a:=

25、(b+c)*e+(b+c)/f的逆波蘭式和 元序列。 op b arg1 arg2 逆波蘭式 abc+e*bc+f/+:= 三元序列 (1) + (2) * (5) (6) (5) 14.什么是句柄？什么是素短語？ 一個句型的最左直接短語稱為該句型的句 柄。 素短語是這樣的一個短語，它至少包含一個 終結(jié)符并且不包含更小的素短語。 15.已知文法GS Sf S*aF | aF | Ff +aF | +a 消除文法左遞歸和提公共左因子。 *aF 解答：消除左遞歸 Sf aFS *aFS Sf *aFS Ff+aF | +a 提公共左因子，文法G (S) Sf aFS *aFS Sf *aFS Ff

26、+aF Ff F | 16 .對于文法 GS : S AB, A Aa|bB , B a|Sb求句型baSb的全部短語、直接短語 和句柄？ 句型baSb的語法樹如圖五（2）所示。 圖：句型baSb的的語法樹 解： a為句 baSb為句型baSb的相對于S的短語，ba為 句型baSb的相對于A的短語，Sb為句型baSb 的相對于B的短語，且為直接短語， 型baSb的相對于B的短語，且為直接短語 和句柄。 17.已知文法G(S) S f aAcBe A f Ab| b B f d (1)給出句子abbcde的最左推導(dǎo)及畫出 語法樹； (2)給出句型aAbcde的短語、素短語。 解答： (1) S=

27、aAcBe=aAbcBe=abbcBe=abbcde (2) 短語：aAbcde, Ab, d 素短語:Ab, d 18. 已知文法G(S) E f E+T | T T f T*F| F F f (E)| i (1)給出句型(i+i)*i+i的最左推導(dǎo)及 畫出語法樹； (2)給出句型(E+T)*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 (

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