編譯原理試題庫(kù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、e可由文法開始 符S經(jīng)過(guò)規(guī)范推導(dǎo)產(chǎn)生，推導(dǎo)過(guò)程如 下：S = SaQ = SaR = Sae = Qae = QbRae (2)、 所以句型QbRae是規(guī)范句型（2分） 語(yǔ)法樹（1分） S S 句柄: QbR NFA (A,0) (C, 定的有限自動(dòng)機(jī) ，1/,A,C）其中： （B，1）=C柱 2.設(shè)有非 M=（A,B,C,0 =C, $（A,1）=A,B, 5 1）=C。請(qǐng)畫出狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換 圖。 解答：狀態(tài)轉(zhuǎn)換距陣為: 符號(hào) 狀態(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è)基本塊出口時(shí)只有 A, B還被引用, 請(qǐng)寫出優(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) 說(shuō)明所得的文法是 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. 試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和 傳值時(shí)，程序執(zhí)行后輸出a的值是什么？ 解答：傳值 a=5 傳地址a=12 7.證明下述文法 G : St aSbS|aS|d是二義 性文法。 證明： 個(gè)文法，如果存在某個(gè)句子有不只

23、棵語(yǔ)法分析樹與之對(duì)應(yīng)，那么稱這 義性文法。 個(gè)文法是 句子 aadbd 有 兩棵語(yǔ)法樹。如下圖： (2) 構(gòu)造相應(yīng)的 FIRST和FOLLOW合; (3) 構(gòu)造預(yù)測(cè)分析表。 解答： 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對(duì)句子aabbbb對(duì)應(yīng) 的兩棵語(yǔ)法樹為： 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. 試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和 傳值時(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.什么是句柄？什么是素短語(yǔ)？ 一個(gè)句型的最左直接短語(yǔ)稱為該句型的句 柄。 素短語(yǔ)是這樣的一個(gè)短語(yǔ)，它至少包含一個(gè) 終結(jié)符并且不包含更小的素短語(yǔ)。 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 .對(duì)于文法 GS : S AB, A Aa|bB , B a|Sb求句型baSb的全部短語(yǔ)、直接短語(yǔ) 和句柄？ 句型baSb的語(yǔ)法樹如圖五（2）所示。 圖：句型baSb的的語(yǔ)法樹 解： a為句 baSb為句型baSb的相對(duì)于S的短語(yǔ)，ba為 句型baSb的相對(duì)于A的短語(yǔ)，Sb為句型baSb 的相對(duì)于B的短語(yǔ)，且為直接短語(yǔ)， 型baSb的相對(duì)于B的短語(yǔ)，且為直接短語(yǔ) 和句柄。 17.已知文法G(S) S f aAcBe A f Ab| b B f d (1)給出句子abbcde的最左推導(dǎo)及畫出 語(yǔ)法樹； (2)給出句型aAbcde的短語(yǔ)、素短語(yǔ)。 解答： (1) S=

27、aAcBe=aAbcBe=abbcBe=abbcde (2) 短語(yǔ)：aAbcde, Ab, d 素短語(yǔ):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)及 畫出語(yǔ)法樹； (2)給出句型(E+T)*i+F 的短語(yǔ)，素短 語(yǔ)和最左素短語(yǔ)。 解答： (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)短語(yǔ) i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F 素短語(yǔ)i, E+T 最左素短語(yǔ)E+T 19. 何謂優(yōu)化？按所涉及的程序范圍可分 為哪幾級(jí)優(yōu)化？ 優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使得從變 換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代 碼。 三種級(jí)別：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化 20. 目標(biāo)代碼有哪幾種形式？生成目標(biāo)代 碼時(shí)通常應(yīng)考慮哪幾個(gè)問(wèn)題？ 目標(biāo)代碼通常采用三種形式：機(jī)器語(yǔ)言，匯 編語(yǔ)言，待裝配機(jī)器語(yǔ)言模塊。 應(yīng)著重考慮的問(wèn)題： (1)如何使生成的目標(biāo)代碼較短； 如何充分利用寄存器，以減少訪問(wèn)內(nèi)存 次數(shù)； (3) 如何充分利用指令系統(tǒng)的特點(diǎn)。 21. 一字母表 Z =a, b，試寫出Z上所有 以a為首的字組成的正規(guī)集相對(duì)應(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