編譯原理試題庫(kù)

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

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

3、常用的中間代碼形式有逆波蘭 式、三元式、 和四元式等。樹(shù)代碼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ǔ)言編寫(xiě)的程序主要 有兩種途徑： 和 。解釋執(zhí)行，編譯執(zhí)行18. 掃描器是詞法分析，它接收輸入的 ，對(duì)源程序進(jìn)行詞法分析并 識(shí)別出一個(gè)個(gè) ，供語(yǔ)法分析器 使用。源程序，單詞符號(hào)19. 自下而上分析法采用和 等四種操作。移進(jìn)、規(guī)約、錯(cuò)誤處理、接受20. 一個(gè) LR 分析器包括兩部分： 一個(gè)總控程

4、序， 和分析棧一張分析表21. 后綴式 abc-/所代表的表達(dá)式是 a/(b-c)22. 局部?jī)?yōu)化是在范圍內(nèi)進(jìn)行的一種優(yōu)化?；緣K23. 不同的編譯程序關(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表達(dá)式 x+y*z/(a+b) 的后綴式 為。xyz*ab+/+27文法符號(hào)的屬性有綜合

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

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

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

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

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

10、B.一個(gè)僅有一個(gè)入口和一個(gè)出口C.一個(gè)沒(méi)有嵌套的程序段D. 一組順序執(zhí)行的程序段， 僅有一個(gè)入口和一 個(gè)出口D24. 優(yōu)化可生成（）的目標(biāo)代碼。 A.運(yùn)行時(shí)間較短B. 占用存儲(chǔ)空間較小C. 運(yùn)行時(shí)間短但占用內(nèi)存空間大 D.運(yùn)行時(shí)間短且占用存儲(chǔ)空間小D25. 下列（）優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行 的。A.強(qiáng)度削弱C.刪除多余運(yùn)算B. 刪除歸納變量D. 代碼外提C26. 編譯程序使用（）區(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)B三 名詞解釋1詞法分析詞法分析的主要任務(wù)是從左向右掃描每行 源程序的符號(hào)

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

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

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

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

15、*(c+d/(e-10)+8) 寫(xiě)出相 應(yīng)的逆波蘭表示。wab+cde10-/+8+*+8. 寫(xiě)出表達(dá)式 a b*(c-d)/e 的逆波蘭式和三 元序列。逆波蘭式 : abcd-*e/+三元序列 : oparg1arg2(1) -cd(2) *b(1)(3) /(2)e(4) +a(3)四判斷題請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃 ，錯(cuò)誤 的劃 ×）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)題。（ ）4. 語(yǔ)法分析時(shí)必須先消除文法中的左遞歸（）×自

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

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

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

19、）=C（C，1）=C 。請(qǐng)畫(huà)出狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換 圖。解答：狀態(tài)轉(zhuǎn)換距陣為：符號(hào)狀態(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) 畫(huà)出 DAG 圖(2) 假設(shè)基本塊出口時(shí)只有 A，B 還被引用， 請(qǐng)寫(xiě)出優(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）說(shuō)明所得的文法是 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. 試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和 傳值時(shí)，程序執(zhí)行后輸出 a 的值是什么 ?解答：傳值 a=5

22、傳地址 a=127證明下述文法 G： S aSbS|aS|d 是二義 性文法。證明：一個(gè)文法，如果存在某個(gè)句子有不只 一棵語(yǔ)法分析樹(shù)與之對(duì)應(yīng)，那么稱(chēng)這 個(gè)文法是二義性文法。句子 aadbd 有兩棵語(yǔ)法樹(shù)。如下圖：(2)8. 設(shè)有基本塊如下：T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6（ 1）畫(huà)出 DAG 圖；（ 2）設(shè) A,B 是出基本塊后的活躍變量，請(qǐng) 給出優(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ù)測(cè)分析表。解答： (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，對(duì)句子 aabbbb 對(duì)應(yīng) 的兩棵語(yǔ)法樹(shù)為：因此，文法 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.試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和

25、傳值時(shí)，程序執(zhí)行后輸出 a 的值是什么 ?答案： 傳值 a=2 傳地址 a=1513. 寫(xiě)出表達(dá)式 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什么是句柄？什么是素短語(yǔ)？ 一個(gè)句型的最左直接短語(yǔ)稱(chēng)為該句型的句 柄。素短語(yǔ)是這樣的一個(gè)短語(yǔ)， 它至少包含一個(gè) 終結(jié)符并且不包含更小的素短語(yǔ)。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對(duì)于文法 GS ： S AB， A Aa|bB ， B a|Sb 求句型 baSb 的全部短語(yǔ)、 直接短語(yǔ) 和句柄？句型 baSb 的語(yǔ)法樹(shù)如圖五 (2) 所示。a圖: 句型 baSb 的的語(yǔ)法樹(shù)解：baSb 為句型 baSb的相對(duì)于 S的短語(yǔ)， ba 為 句型 baSb的相對(duì)于 A的短語(yǔ)，Sb為句型 baSb 的相

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

28、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(2) 短語(yǔ) i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F 素短語(yǔ) i, E+T 最左素短語(yǔ) E+T19. 何謂優(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)代碼較短；(2) 如何充分利用寄存器，以減少訪問(wèn)內(nèi)存次數(shù)；(3) 如何充分利用指令系統(tǒng)的特點(diǎn)。21. 一字母表 =a, b ，試寫(xiě)出 上所有 以 a 為首的字組成的正規(guī)集相對(duì)應(yīng)的正規(guī) 式。解答：正規(guī)式 a ( a | b )*。22. 設(shè)有基本塊D:=A-CE:=A*CF:=D*ES:=2T:=A-