編譯練習(xí)題答案

1、一、填空題:1-01.編譯程序的工作過程一般可以劃分為 詞法分析,語法分析,語義分析，之間代碼生成,代碼優(yōu)化 等幾個(gè)基本階段,同時(shí)還會(huì)伴有 表格處理 和 出錯(cuò)處理 .1-02.若源程序是用高級語言編寫的,目標(biāo)程序是 機(jī)器語言程序或匯編程序 ,則其翻譯程序稱為編譯程序.1-03.編譯方式與解釋方式的根本區(qū)別在于 是否生成目標(biāo)代碼 .1-04.翻譯程序是這樣一種程序,它能夠?qū)?用甲語言書寫的程序 轉(zhuǎn)換成與其等價(jià)的 用乙語言書寫的程序 .1-05.對編譯程序而言,輸入數(shù)據(jù)是 源程序 ,輸出結(jié)果是 目標(biāo)程序 .1-06.如果編譯程序生成的目標(biāo)程序是機(jī)器代碼程序,則源程序的執(zhí)行分為兩大階段: 編譯階段

2、和 運(yùn)行階段 .如果編譯程序生成的目標(biāo)程序是匯編語言程序,則源程序的執(zhí)行分為三個(gè)階段: 編譯階段 , 匯編階段 和 運(yùn)行階段 .1-07.若源程序是用高級語言編寫的，目標(biāo)程序是機(jī)器語言程序或匯編程序 ，則其翻譯程序稱為 編譯程序 。1-08.一個(gè)典型的編譯程序中，不僅包括詞法分析、語法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。其中，詞法分析器用于識(shí)別 單詞 。1-09.編譯方式與解釋方式的根本區(qū)別為是否生成目標(biāo)代碼。2-01.所謂最右推導(dǎo)是指： 任何一步都是對中最右非終結(jié)符進(jìn)行替換的 。2-02.一個(gè)上下文無關(guān)文法所含四個(gè)組成部分是 一組終結(jié)符號、一組非

3、終結(jié)符號、一個(gè)開始符號、一組產(chǎn)生式 。2-03.產(chǎn)生式是用于定義 語法成分 的一種書寫規(guī)則。2-04.設(shè)GS是給定文法，則由文法G所定義的語言L(G)可描述為： L(G)xSx,xVT* 。2-05.設(shè)G是一個(gè)給定的文法，S是文法的開始符號，如果Sx（其中xV*），則稱x是文法的一個(gè)句型 。2-06.設(shè)G是一個(gè)給定的文法，S是文法的開始符號，如果Sx(其中xVT*),則稱x是文法的一個(gè)句子。3-01.掃描器的任務(wù)是從源程序中識(shí)別出一個(gè)個(gè) 單詞符號 。4-01.語法分析最常用的兩類方法是 自上而下 和 自下而上 分析法。4-02.語法分析的任務(wù)是識(shí)別給定的終極符串是否為給定文法的句子。4-03.

4、遞歸下降法不允許任一非終極符是直接 左 遞歸的。4-04.自頂向下的語法分析方法的關(guān)鍵是 如何選擇候選式 的問題。4-05.遞歸下降分析法是自 頂向上 分析方法。4-06.自頂向下的語法分析方法的基本思想是：從文法的 開始符號 開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行直接推導(dǎo)，試圖推導(dǎo)出文法的 句子 ，使之與給定的輸入串匹配。5-01.自底向上的語法分析方法的基本思想是：從給定的終極符串開始，根據(jù)文法的規(guī)則一步一步的向上進(jìn)行直接歸約，試圖歸約到文法的 開始符號 。5-02.自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行 直接歸約 ，力求

5、歸約 到文法的 開始符號 。5-03.簡單優(yōu)先方法每次歸約當(dāng)前句型的 句柄 ，算符優(yōu)先方法每次歸約當(dāng)前句型的 最左素短語 ，二者都是不斷移進(jìn)輸入符號，直到符號棧頂出現(xiàn) 可歸約串 的尾，再向前找到 可歸約串 的頭，然后歸約。5-04.在LR（0）分析法的名稱中，L的含義是 自左向右的掃描輸入串 ，R的含義是 最左歸約 ，0 的含義是 向貌似句柄的符號串后查看0個(gè)輸入符號 。5-05.在SLR（1）分析法的名稱中，S的含義是 簡單的 。6-01.所謂屬性文法是 一個(gè)屬性文法是一個(gè)三元組：A（G，V，F(xiàn)），一個(gè)上下文無關(guān)文法G；一個(gè)屬性的有窮集V和關(guān)于屬性的斷言或謂詞的有窮集F。每個(gè)斷言與文法的某產(chǎn)

6、生式相聯(lián)。 6-02.綜合屬性是用于 “自下而上”傳遞信息。6-03.繼承屬性是用于 “自上而下”傳遞信息。6-04.終結(jié)符只有 綜合屬性 ，它們由詞法分析器提供。7-01.在使用高級語言編程時(shí),首先可通過編譯程序發(fā)現(xiàn)源程序的全部 A 錯(cuò)誤和 B 部分錯(cuò)誤.a.語法 b.語義 c.語用 d.運(yùn)行8-01.符號表中的信息欄中登記了每個(gè)名字的 屬性和特征等有關(guān)信息 ，如類型、種屬、所占單元大小、地址等等。8-02.一個(gè)過程相應(yīng)的DISPLAY表的內(nèi)容為 現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址 。9-01.一個(gè)過程相應(yīng)的DISPLAY表的內(nèi)容為 現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址 。

7、9-02.常用的兩種動(dòng)態(tài)存貯分配辦法是 棧式 動(dòng)態(tài)分配和 堆式 動(dòng)態(tài)分配。9-03.常用的參數(shù)傳遞方式有 傳地址 ，傳值和傳名。10-01.局部優(yōu)化是局限于一個(gè) 基本塊 范圍內(nèi)的一種優(yōu)化。10-02.代碼優(yōu)化的主要目標(biāo)是如何提高 目標(biāo)程序的運(yùn)行速度 和如何減少 目標(biāo)程序運(yùn)行時(shí)所需的空間 。二、單選題:1-10.一個(gè)編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括 (1)c .其中, (2)b 和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的.詞法分析器用于識(shí)別 (3)c ,語法分析器則可以發(fā)現(xiàn)源程序中的 (4)d . (1) a.模擬執(zhí)行器 b.解釋器 c

8、.表格處理和出錯(cuò)處理 d.符號執(zhí)行器 (2) a.語法分析 b.中間代碼生成 c.詞法分析 d.目標(biāo)代碼生成 (3) a.字符串 b.語句 c.單詞 d.標(biāo)識(shí)符 (4) a.語義錯(cuò)誤 b.語法和語義錯(cuò)誤 c.錯(cuò)誤并校正 d.語法錯(cuò)誤1-11.程序語言的語言處理程序是一種 (1)a . (2)b 是兩類程序語言處理程序,他們的主要區(qū)別在于 (3)d . (1) a.系統(tǒng)軟件 b.應(yīng)用軟件 c.實(shí)時(shí)系統(tǒng) d.分布式系統(tǒng) (2) a.高級語言程序和低級語言程序 b.解釋程序和編譯程序 c.編譯程序和操作系統(tǒng) d.系統(tǒng)程序和應(yīng)用程序 (3) a.單用戶與多用戶的差別 b.對用戶程序的查錯(cuò)能力c.機(jī)器執(zhí)

9、行效率 d.是否生成目標(biāo)代碼1-12.匯編程序是將 a 翻譯成 b ,編譯程序是將 c 翻譯成 d .a.匯編語言程序 b.機(jī)器語言程序 c.高級語言程序d. a 或者 b e. a 或者 c f. b 或者 c1-13.下面關(guān)于解釋程序的描述正確的是 b . (1) 解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)生目標(biāo)代碼 (2) 解釋程序適用于COBOL 和 FORTRAN 語言 (3) 解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的 a. (1)(2) b. (1) c. (1)(2)(3) d.(2)(3)1-14.高級語言的語言處理程序分為解釋程序和編譯程序兩種.編譯程序有五個(gè)階段，而解釋程序通常缺少

10、(1)e 和 (1)b .其中， (1)e 的目的是使最后階段產(chǎn)生的目標(biāo)代碼更為高效. 與編譯系統(tǒng)相比，解釋系統(tǒng) (2)d .解釋程序處理語言時(shí),大多數(shù)采用的是 (3)b 方法. (1): a. 中間代碼生成 b.目標(biāo)代碼生成 c.詞法分析 d.語法分析 e.代碼優(yōu)化 (2): a.比較簡單,可移植性好,執(zhí)行速度快 b.比較復(fù)雜,可移植性好,執(zhí)行速度快 c.比較簡單,可移植性差,執(zhí)行速度慢 d.比較簡單,可移植性好,執(zhí)行速度慢 (3): a.源程序命令被逐個(gè)直接解釋執(zhí)行 b.先將源程序轉(zhuǎn)化為之間代碼,再解釋執(zhí)行c.先將源程序解釋轉(zhuǎn)化為目標(biāo)程序,在執(zhí)行 d.以上方法都可以1-15.用高級語言編寫

11、的程序經(jīng)編譯后產(chǎn)生的程序叫 b .用不同語言編寫的程序產(chǎn)生 b 后,可用 g 連接在一起生成機(jī)器可執(zhí)行的程序.在機(jī)器中真正執(zhí)行的是 e .a. 源程序 b. 目標(biāo)程序 c. 函數(shù) d. 過程 e. 機(jī)器指令代碼 f. 模塊 g. 連接程序 h.程序庫1-16.要在某一臺(tái)機(jī)器上為某種語言構(gòu)造一個(gè)編譯程序,必須掌握下述三方面的內(nèi)容: c , d , f .a. 匯編語言 b. 高級語言 c. 源語言 d. 目標(biāo)語言e. 程序設(shè)計(jì)方法 f. 編譯方法 g. 測試方法 h. 機(jī)器語言1-17.由于受到具體機(jī)器主存容量的限制,編譯程序幾個(gè)不同階段的工作往往被組合成 (1)d ,諸階段的工作往往是 (2)

12、d 進(jìn)行的. (1) a. 過程 b. 程序 c. 批量 d.遍 (2) a. 順序 b. 并行 c. 成批 d.穿插1-18.編譯程序與具體的機(jī)器 a , 與具體的語言 a .a. 有關(guān) b.無關(guān)1-19.使用解釋程序時(shí),在程序未執(zhí)行完的情況下， a 重新執(zhí)行已執(zhí)行過的部分.a. 也能 b.不可能1-20.編譯過程中,語法分析器的任務(wù)就是 b . (1) 分析單詞是怎樣構(gòu)成的 (2) 分析單詞串是如何構(gòu)成語句和說明的 (3) 分析語句和說明是如何構(gòu)成程序的 (4) 分析程序的結(jié)構(gòu)a. (2)(3) b. (2)(3)(4) c. (1)(2)(3) d.(1)(2)(3)(4)1-21.編譯

13、程序是一種常用的 b 軟件.a. 應(yīng)用 b. 系統(tǒng)1-22.編寫一個(gè)計(jì)算機(jī)高級語言的源程序后,到正式上機(jī)運(yùn)行之前，一般要經(jīng)過 b 這幾步. (1) 編輯 (2) 編譯 (3) 連接 (4) 運(yùn)行a. (1)(2)(3)(4) b. (1)(2)(3) c. (1)(3) d.(1)(4)1-23.編譯程序必須完成的工作有 a . (1) 詞法分析 (2) 語法分析 (3) 語義分析 (4) 代碼生成 (5) 之間代碼生成 (6) 代碼優(yōu)化a. (1)(2)(3)(4) b. (1)(2)(3)(4)(5) c. (1)(2)(3)(4)(5)(6) d. (1)(2)(3)(4)(6) e.

14、(1)(2)(3)(5)(6)1-24.“用高級語言書寫的源程序都必須通過編譯,產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”這種說法 a .a. 不正確 b.正確1-25.把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由 b 完成的.a. 編譯器 b. 匯編器 c. 解釋器 d. 預(yù)處理器1-26.編譯程序生成的目標(biāo)程序 b 是機(jī)器語言的程序.a. 一定 b. 不一定1-27.編譯程序生成的目標(biāo)程序 b 是可執(zhí)行的程序.a. 一定 b. 不一定1-28編譯程序是一種 B 。A. 匯編程序 B. 翻譯程序 C. 解釋程序 D. 目標(biāo)程序1-29按邏輯上劃分，編譯程序第二步工作是 C 。A. 語義分析 B. 詞

15、法分析 C. 語法分析 D. 代碼優(yōu)化1-30通常一個(gè)編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括 C 。A.模擬執(zhí)行器 B.解釋器 C.表格處理和出錯(cuò)處理 D.符號執(zhí)行器2-06已知語言L= xnyyn | n=1，則下述文法中， D 可以產(chǎn)生語言L。A 1.ZxZy|xAy|y B 1.AxAy2. AxAy|x 2.Ax C 1.ZAyB D 1.ZxAy 2.AxA|x 2.AxAy|y 3.ByB|y 2-07文法G所描述的語言是 C 的集合。A.文法G的字母表V中所有符號組成的符號串B.文法G的字母表V的閉包V*中的所有符號串C.

16、由文法的開始符號推出的所有終極符串D.由文法的開始符號推出的所有符號串2-08喬姆斯基（Chomsky）把文法分為四種類型，即0型、1型、2型、3型。其中3型文法是 B 。A.短語文法 B.正則文法 C.上下文有關(guān)文法 D.上下文無關(guān)文法2-09.文法GN=（b，N，B，N，NbbB，BbN），該文法所描述的語言是 C 。A. L(GN)=bii0 B. L(GN)=b2ii0C. L(GN)=b2i+1i0 D. L(GN)=b2i+1i12-10一個(gè)句型中的最左 B 稱為該句型的句柄?？蛇x項(xiàng)有：A. 短語 B. 簡單短語 C. 素短語 D. 終結(jié)符號2-11設(shè)G是一個(gè)給定的文法，S是文法的

17、開始符號，如果Sx(其中xV*),則稱x是文法G的一個(gè) B 。A. 候選式 B. 句型 C. 單詞 D. 產(chǎn)生式2-12一個(gè)上下文無關(guān)文法G包括四個(gè)組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個(gè)開始符號，以及一組 D 。A. 句子 B. 句型 C. 單詞 D. 產(chǎn)生式2-13.文法GE：ETETTFTF Fa（E）該文法句型EF(ET)的簡單短語是下列符號串中的 B 。（ET） ET F F(ET)可選項(xiàng)有：A) 和 B) 和 C) 和 D) 2-14若一個(gè)文法是遞歸的，則它所產(chǎn)生的語言的句子 A 。A.是無窮多個(gè) B.是有窮多個(gè) C.是可枚舉的 D.個(gè)數(shù)是常量2-15文法的二義性和語言

18、的二義性是兩個(gè) A 的概念。A 不同 B 相同 C 無法判斷 D 不存在3-02詞法分析器用于識(shí)別 C 。A. 句子 B. 句型 C. 單詞 D. 產(chǎn)生式4-07.在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是 B 。A. 非終極符集 B.終極符集 C. 字母表 D. 狀態(tài)集4-08.編譯程序中語法分析器接收以 A 為單位的輸入。A. 單詞 B. 表達(dá)式 C. 產(chǎn)生式 D. 句子5-06在自底向上的語法分析方法中，分析的關(guān)鍵是 D 。A. 尋找句柄 B. 尋找句型 C. 消除遞歸 D. 選擇候選式5-07. 在LR分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型 C 的DF

19、A狀態(tài)。A.句柄 B. 前綴 C. 活前綴 D. LR(0)項(xiàng)目6. DFA和NFA的區(qū)別在于 C 。A初始狀態(tài)個(gè)數(shù)要求不同 B轉(zhuǎn)換函數(shù)要求不同 CA和B兩個(gè)的合并10.對于允許過程遞歸調(diào)用的語言，在它的目標(biāo)程序的運(yùn)行環(huán)境中至少應(yīng)該使用 B 。 A.靜態(tài)分配 B.動(dòng)態(tài)分配 C.存儲(chǔ)分配 D 內(nèi)存分配11. 文法GZ：ZBb, AAe, Ae, BAf,其中e和f為終極符，#是輸入串的結(jié)束符，F(xiàn)OLLOW（A）為 A 。Ae,f Be Cf D#12. 在編譯中，中間代碼生成的常用方法有 D 。ALR法 B遞歸法 C最優(yōu)匹配法 D語法制導(dǎo)翻譯方法 13. 下列關(guān)于標(biāo)識(shí)符和名字的敘述中，正確的為

20、C 。A. 標(biāo)識(shí)符有一定的含義 B. 名字是一個(gè)沒有意義的字符序列 C. 名字有確切的屬性 D. 都不對 14. 已知語言L= anbbn | n=1，則下述文法中， B 可以產(chǎn)生語言L。A 1.ZaZb|aAb|b B 1.AaAb2. AaAb|b 2.Ab C 1.ZAbB D 1.ZaAb 2.AaA|a 2.AaAb|b 3.BbB|b 15 文法的二義性和語言的二義性是兩個(gè) C 的概念。A不存在 B相同 C不同 D無法判斷三、是非題(下列各題，你認(rèn)為正確的，請?jiān)陬}干的括號內(nèi)打“ ”，錯(cuò)的打“”。)1-31.計(jì)算機(jī)高級語言翻譯成低級語言只有解釋一種方式。 （）1-32.在編譯中進(jìn)行語

21、法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。 （）1-34.甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。 （）2-15.正則文法其產(chǎn)生式為Aa，ABb, A,BVN，a、bVT。 （）4-09.每個(gè)文法都能改寫為LL(1)文法。 （）4-10.遞歸下降法允許任一非終極符是直接左遞歸的。 （）5-08.算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。 （）5-09.自底而上語法分析方法的主要問題是候選式的選擇。 （）5-10.LR法是自頂向下語法分析方法。 （）5-11.簡單優(yōu)先文法允許任意兩個(gè)產(chǎn)生式具有相同右部。 （）5-12.若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部

22、一定是該句型的句柄。 （）5-13.一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。 （）7-02.數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。 （）8-03.在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。 （）9-04.對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略。 （）9-05.在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。 （）10-03.僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無用的。 （）10-04.削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性。 （）10-05.在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。 （）()6.活前綴不包含句柄中的任何符號。()9.對任一編譯程序

23、來說，產(chǎn)生中間代碼不一定是必要的。 ()13.若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。 ()16.活前綴就是任何句型的有用前綴。 ()17.編譯程序在優(yōu)化時(shí)可能要用到源程序中的注釋。 ()18.目標(biāo)代碼就只有可立即執(zhí)行的機(jī)器語言代碼一種。 ()19.任何句型都存在一個(gè)規(guī)范推導(dǎo)，任何句子也都存在一個(gè)規(guī)范推導(dǎo)。()22.中間代碼優(yōu)化的目的是檢查源語言的各種錯(cuò)誤。 ()23.解釋與編譯方式的區(qū)別是解釋沒有生成目標(biāo)代碼。()24.目標(biāo)代碼的生成與目標(biāo)機(jī)無關(guān)，與宿主機(jī)有關(guān)。四、名詞解釋1-35. 掃描遍_指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。2-16.短語設(shè)GZ是給定文

24、法, w=xuyV+，為該文法的句型,如果滿足下面兩個(gè)條件: Z xUy； U u； 則稱句型xuy 中的子串u是句型xuy的短語。2-17.簡單短語設(shè)GZ是給定文法, w=xuyV+，為該文法的句型,如果滿足下面兩個(gè)條件: Z xUy； U u； 則稱句型xuy 中的子串u是句型xuy的簡單短語（或直接短語）。2-18.句柄一個(gè)句型中的最左簡單短語稱為該句型的句柄。2-19.答：規(guī)范推導(dǎo)如果在任一步推導(dǎo)vw中，都是對符號串v的最右非終結(jié)符進(jìn)行替換，則稱其為規(guī)范推導(dǎo)。*2-21.答：語言 L（GZ）=x| Z x， xVT* 。4-11.語法分析按文法的產(chǎn)生式識(shí)別輸入的符號串是否為一個(gè)句子的分

25、析過程。4-12.選擇符集合SELECT給定上下文無關(guān)文法的產(chǎn)生式A, AVN,V*, 若,則SELECT(A)=FIRST(),其中如果，則SELECT(A)=FIRST()FOLLOW(A),FIRST()表示FIRST()的非元素。RR5-14.活前綴若S A 是文法G中的一個(gè)規(guī)范推導(dǎo)，G是G的拓廣文法，符號串是的前綴，則稱是G的，也是G的一個(gè)活前綴。其中 S為文法開始符號。或：可歸前綴的任意首部。5-15.可歸前綴是指規(guī)范句型的一個(gè)前綴，這種前綴不含句柄之后的任何符號。5-16.LR(0)項(xiàng)目把產(chǎn)生式右部某位置上標(biāo)有圓點(diǎn)的產(chǎn)生式稱為相應(yīng)文法的一個(gè)LR(0)項(xiàng)目。5-17.算符優(yōu)先文法設(shè)

26、有一不含產(chǎn)生式的算符文法G，如果對任意兩個(gè)終結(jié)符對a，b之間至多只有 、 和 三種關(guān)系中的一種成立，則稱G是一個(gè)算符優(yōu)先文法。5-18.最左素短語設(shè)有文法GS,其句型的素短語是一個(gè)短語,它至少包含一個(gè)終結(jié)符，并除自身外不包含其它素短語，最左邊的素短語稱最左素短語。6-05.語義規(guī)則對于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為語義規(guī)則。6-06.翻譯方案將屬性文法中的語義規(guī)則用花括號 括起來，插在產(chǎn)生式右部的合適地方，指明語義規(guī)則的計(jì)算次序，陳述一些細(xì)節(jié)，得到一種語義動(dòng)作與語法分析交錯(cuò)的表示方法，以表述語義動(dòng)作在語法分析過程中的執(zhí)行時(shí)刻，稱之為翻譯方案。6-07.語法制導(dǎo)翻譯為文法中每個(gè)

27、產(chǎn)生式配備一組語義規(guī)則，并且在語法分析過程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)產(chǎn)生式所對應(yīng)的語義子程序（或語義規(guī)則描述的語義動(dòng)作）進(jìn)行翻譯的辦法稱作語法制導(dǎo)翻譯。7-03.后綴式 一種把運(yùn)算量（操作數(shù)）寫在前面把算符寫在后面（后綴）的表示法。即 一個(gè)表達(dá)式E的后綴形式可以如下定義：(1) 如果E是一個(gè)變量或常量，則E的后綴式是E自身。(2) 如果E是E1 op E2形式的表達(dá)式，這里op是任何二元操作符，則E的后綴式為E1 E2op，這里E1和E2分別為E1和E2的后綴式。(3) 如果E是（E1）形式的表達(dá)式，則E1的后綴式就是E的后綴式。7-04.四元式 一個(gè)四元式是一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這

28、四個(gè)域分別稱為op、arg1、arg2及result。域op包含一個(gè)代表運(yùn)算符的內(nèi)部碼。9-06.活動(dòng)答：一個(gè)過程的活動(dòng)指的是該過程的一次執(zhí)行。就是說，每次執(zhí)行一個(gè)過程體，產(chǎn)生該過程體的一個(gè)活動(dòng)。9-07.活動(dòng)記錄答：為了管理過程在一次執(zhí)行中所需要的信息，使用一個(gè)連續(xù)的存儲(chǔ)塊，這樣一個(gè)連續(xù)的存儲(chǔ)塊稱為活動(dòng)記錄。9-08.活動(dòng)的生存期答：指的是從執(zhí)行某過程體第一步操作到最后一步操作之間的操作序，包括執(zhí)行過程時(shí)調(diào)用其它過程花費(fèi)的時(shí)間。10-02.答：基本塊源程序中只有一個(gè)入口和一個(gè)出口的順序執(zhí)行的代碼段。10-07. 基本塊的DAG。答：一個(gè)基本塊的DAG是一種其結(jié)點(diǎn)帶有下述標(biāo)記或附加信息的DAG

29、。 (1)圖的葉結(jié)點(diǎn)（沒有后繼的結(jié)點(diǎn)）以一標(biāo)識(shí)符（變量名）或常數(shù)作為標(biāo)記，表示該結(jié)點(diǎn)代表該變量或常數(shù)的值。如果葉結(jié)點(diǎn)用來代表某變量A的地址，則用addr（A）作為該結(jié)點(diǎn)的標(biāo)記。通常把葉結(jié)點(diǎn)上作為標(biāo)記的標(biāo)識(shí)符加上下標(biāo)0，以表示它是該變量的初值。 (2)圖的內(nèi)部結(jié)點(diǎn)（有后繼的結(jié)點(diǎn)）以一運(yùn)算符作為標(biāo)記，表示該結(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對其后繼結(jié)點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果。 (3)圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)識(shí)符，表示這些變量具有該結(jié)點(diǎn)所代表的值。五、簡答題：2-19什么是句子？ 什么是語言? 答：設(shè)G是一個(gè)給定的文法，S是文法的開始符號，如果Sx(其中xVT*),則稱x是文法的一個(gè)句子。設(shè)GS是給定

30、文法，則由文法G所定義的語言L(G)可描述為： L(G)xSx,xVT* 。2-20.已知文法GE為：ET|E+T|E-TTF|T*F|T/FF（E）|i 該文法的開始符號（識(shí)別符號）是什么？請給出該文法的終結(jié)符號集合VT和非終結(jié)符號集合VN。 找出句型T+T*F+i的所有短語、簡單短語和句柄。解： 該文法的開始符號（識(shí)別符號）是E。該文法的終結(jié)符號集合VT=+、-、*、/、（、）、i。非終結(jié)符號集合VN=E、T、F。句型T+T*F+I的短語為i、T*F、第一個(gè)T、T+T*F+i;簡單短語為i、T*F、第一個(gè)T;句柄為第一個(gè)T。2-21.已知文法GS為：SdABAaA|aBBb| GS產(chǎn)生的語

31、言是什么？ GS能否改寫為等價(jià)的正規(guī)文法？解： GS產(chǎn)生的語言是L(GS)=danbmn1,m0。 GS能改寫為等價(jià)的正規(guī)文法,其改寫后的等價(jià)的正規(guī)文法GS為： SdA A aA|aB|a B bB|b2-22.設(shè)有語言L(G)=adaR | a(a,b)*,aR 為a之逆，試構(gòu)造產(chǎn)生此語言的上下文無關(guān)文法G。解：根據(jù)題義，可知aR 為a之逆的含義就是句子中的符號a、b以d為中心呈左右對稱出現(xiàn)；由于a(a,b)*，所以a、b的個(gè)數(shù)可以為零。所以可構(gòu)造產(chǎn)生此語言的上下文無關(guān)文法GS為：SaSa|bSb|d2-23.證明下面文法GN是二義性文法。 GN： N SEE S SDD E 0210D 0

32、12答：10是文法GN的一個(gè)句子，并且有兩個(gè)不同的最右推導(dǎo)。（1）1S = E = 10 （2）S = SE = S0 = D0 = 10因此說明此文法有二義性。3-03簡述DFA與NFA有何區(qū)別 ? 答：DFA與NFA的區(qū)別表現(xiàn)為兩個(gè)方面:一是NFA可以若干個(gè)開始狀態(tài)，而DFA僅只一個(gè)開始狀態(tài)。另一方面，DFA的映象M是從K到K，而NFA的映象M是從K到K的子集，即映象M將產(chǎn)生一個(gè)狀態(tài)集合（可能為空集），而不是單個(gè)狀態(tài)。3-04.試給出非確定自動(dòng)機(jī)的定義。答：一個(gè)非確定的有窮自動(dòng)機(jī)（NFA）M是一個(gè)五元組：M=（K，f，S ，Z）。其中:1. K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2.

33、是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號，所以也稱為輸入符號表；3. f是狀態(tài)轉(zhuǎn)換函數(shù)，是在K*K的子集的映射，即，f: K*2K ；表明在某狀態(tài)下對于某輸入符號可能有多個(gè)后繼狀態(tài)；4. SK是一個(gè)非空初態(tài)集； 5. ZK是一個(gè)終態(tài)集（可空）。3-05. 為正規(guī)式（a|b）*a(a|b) 構(gòu)造一個(gè)等價(jià)的確定的有限自動(dòng)機(jī)。解答：a,baab0123-06. 給定下列自動(dòng)機(jī)，將其轉(zhuǎn)換為確定的自動(dòng)機(jī)。dddddddstartdSADBCEGH注：帶號的結(jié)點(diǎn)為初始狀態(tài)； 帶號的結(jié)點(diǎn)為終止?fàn)顟B(tài)解答：(1)消除邊，得到NFA：ddddddddddddSADBCEGH注：帶號的結(jié)點(diǎn)為初始狀態(tài)； 帶號的

34、結(jié)點(diǎn)為終止?fàn)顟B(tài)(2)確定化，得到DFA：ddSABCDEGHAABCEBCEBCDEHHGDG+SAABCEGDGHDHAABCEBCEBCEHDHHDHGGDGdddddddSAAAHBCEADGADHA注：帶號的結(jié)點(diǎn)為初始狀態(tài)； 帶號的結(jié)點(diǎn)為終止?fàn)顟B(tài)G3-07. 給定下列自動(dòng)機(jī)：其中：開始狀態(tài)：0 終止?fàn)顟B(tài)：2aaa0bbb12(1)把此自動(dòng)機(jī)轉(zhuǎn)換為確定自動(dòng)機(jī)DFA。 (2)給出此DFA的正則表達(dá)式。解答：（1）： 有狀態(tài)矩陣如圖： a b0 01 201 01 22 1 2 1 2a b 0 0,1 2 1 2 2 1 2從而可得DFA如圖：-02aaba101bbb極小化后：02bab

35、b1a（2）此DFA的正則表達(dá)式為： (aa*bb)(bab)* 或 a*b（bab）*。4-13.消除下列文法GE的左遞歸。EE-TTTT/FFF( E )i解答：消除文法GE的左遞歸后得到：ETEE -TETFTT/FTF( E )i4-14.在LL(1)分析法中,LL分別代表什么含義?答:第一個(gè)L代表從左到右的掃描，第二個(gè)L代表每次進(jìn)行最左推導(dǎo)。4-15.自頂向下分析思想是什么？答：從開始符出發(fā)導(dǎo)出句型并一個(gè)符號一個(gè)符號地與給定終結(jié)符串進(jìn)行匹配。如果全部匹配成功，則表示開始符號可推導(dǎo)出給定的終結(jié)符串。因此判定給定終結(jié)符號串是正確句子。4-16.自頂向下的缺點(diǎn)是什么？答：在推導(dǎo)過程中，如果

36、對文法不做限制。那么產(chǎn)生式的選擇成為無根據(jù)的，只好一一去試所有可能的產(chǎn)生式，直至成功為止。這種方法的致命弱點(diǎn)是不斷地回溯，大大影響速度。4-17.LL（1）文法的定義是什么？答：一個(gè)上下文無關(guān)文法是LL(1)文法的充分必要條件是每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式，A,A；滿足SELECT(A )SELECT(A )=。其中，、不能同時(shí)。4-18.什么是文法的左遞歸？答：一個(gè)文法含有下列形式的產(chǎn)生式之一時(shí)：1)AA，AVN，V*2)AB，BA，A、BVN，、V* 則稱該文法是左遞歸的。4-19.遞歸下降法的主要思想是什么？答：對每個(gè)非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫出相應(yīng)語法分析子程序。因?yàn)槲姆ㄟf歸相應(yīng)子程序

37、也遞歸，子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎一致。所以稱此種方法稱為遞歸子程序法或遞歸下降法。5-19.自底向上分析法的原理是什么？答：在采用自左向右掃描，自底向上分析的前提下，該類分析方法是從輸入符號串入手，通過反復(fù)查找當(dāng)前句型的句柄（最左簡單短語），并使用文法的產(chǎn)生式把句柄歸約成相應(yīng)的非終極符來一步步地進(jìn)行分析的。最終把輸入串歸約成文法的開始符號，表明分析成功。5-20.簡單優(yōu)先方法基本思想是什么？答：簡單優(yōu)先方法基本思想是首先規(guī)定文法符號之間的優(yōu)先關(guān)系和結(jié)合性質(zhì)，然后在利用這種關(guān)系，通過比較兩個(gè)相鄰的符號之間的優(yōu)先順序來確定句型的“句柄”并進(jìn)行歸約。5-21.三種優(yōu)先關(guān)系的定義是什么？答：三種優(yōu)

38、先關(guān)系的定義是：1. si（1）sisj sj 當(dāng)且僅當(dāng)存在形如下面的產(chǎn)生式USiSj2. sisj 當(dāng)且僅當(dāng)存在形如下面的產(chǎn)生式USiW的生產(chǎn)式，且有 WSj3. sisj 當(dāng)且僅當(dāng)存在形如下面的產(chǎn)生式UVW的生產(chǎn)式,且有 VSi和WSj5-22.如何確定簡單優(yōu)先文法的句柄？答：設(shè)S1S2Sn是簡單優(yōu)先文法的規(guī)范句型，其子串SiSi+1Sj是滿足下列條件的最左子串：Si-1 SiSi Si+1 Sj-1 SjSj Sj+1則SiSi+1Sj定是S1S2Sn的句柄。1 ZC S2 Cif E then3 SAE4 EEA5 EA6 Ai其中：Z、C、S、A、EVN ； if、then、iVT5

39、-23. 給定文法GZ：a) 構(gòu)造此文法的LR(0)項(xiàng)目集規(guī)范族，并給出識(shí)別活前綴的DFA。b) 構(gòu)造其SLR（1）分析表。解答：1.首先拓廣文法：在G中加入產(chǎn)生式0ZZ，然后得到新的文法G，再求G的識(shí)別全部活前綴的DFA：I0：Z.ZZ.C SC.if E thenI1：ZZ.I2：ZC .SS.AEA.iI3：Cif .E thenE.EAE.AA.iI4：ZC S.I5：SA.EI6：Ai.I7：Cif E .thenEE.AI9：SA.EE.EAE.AA.iI10：Cif E then.I11：EE.AA.iI12：SAE.EE.AI13：EEA.CSiAiiEAZI0I1I6I5I2

40、I3I7I9I12I13I11I10I8I4AtheniifEA2 Follow(Z)#Follow(C)iFollow(S)#Follow(E)#,thenFollow(A),# ,then 則可構(gòu)造SLR（1）分析表為：ACTIONGOTO0iftheni#ZCSEA0S3121OK2S6453S6784r15S96r6r6r6r67S10S118r5r5r59S612810r211S61312S11r313r4r4r45-24. 設(shè)有文法GS：SaAAAbAbI1:SS.I0:S.S S.aAI2:Sa.AA.AbA.baI3:SaA.AA.bAI4:AAb.Ab.bbS 求識(shí)別該文法所

41、有活前綴的DFA。解答：(1).首先拓廣文法： 在G中加入產(chǎn)生式0.SS，然后得到新的文法G: 0.SS 1.SaA2.AAb3.Ab(2).再求G的識(shí)別全部活前綴的DFA：6-07.語法制導(dǎo)翻譯方法的基本思想是什么?答：在語法分析過程中，每當(dāng)使用一條產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，就執(zhí)行該產(chǎn)生式所對應(yīng)的語義動(dòng)作進(jìn)行屬性計(jì)算，完成對輸入符號串的翻譯。6-08.何謂“語法制導(dǎo)翻譯”?答：在語法分析過程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)產(chǎn)生式所對應(yīng)的語義子程序（或語義規(guī)則描述的語義動(dòng)作）進(jìn)行翻譯的辦法稱作語法制導(dǎo)翻譯。6-09.在一個(gè)屬性文法中，對應(yīng)于每個(gè)產(chǎn)生式Aa都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的形

42、式為b：f（c1,c2，ck），其中對于b的要求是什么？答：語義規(guī)則中的左部屬性變量b被規(guī)定為只能是下述兩種變量： 對應(yīng)產(chǎn)生式左部符號的綜合屬性變量； 對應(yīng)產(chǎn)生式右部符號的繼承屬性變量。6-10.給定文法及相應(yīng)的翻譯方案：SbTc print(“0”)Sa print(“1”)TR print(“2”)RR/S print(“3”)RS print(“4”)為該文法設(shè)計(jì)翻譯方案，使句型bR/bTc/bSc/ac經(jīng)該翻譯方案翻譯后,輸出串：SbcRRS/SaRSRSRbcT/TbcT0342031320解：給出句型bR/bTc/bSc/ac的語法樹如右圖：則對于句型bR/bTc/bSc/ac,處

43、理完該句型后輸出是：4245130341246-10.給定文法及相應(yīng)的翻譯方案：)EE+T print(“5”)ET print(“4”)TT*F print(“3”)TF print(“2”)F( E ) print(“1”)Fi print(“0”)EETF()ETiTTFFTFT()+*EET+對于句型T+(T*(F+T)*i),處理完該句型后輸出是什么？解：給出句型T+(T*(F+T)*i)的語法樹如右圖：則對于句型T+(T*(F+T)*i),處理完該句型后輸出是：4245130341247-05.常用的中間語言種類有哪幾種？答：有逆波蘭式、三地址代碼、抽象語法樹和DAG。7-06.給

44、定下列中綴式，分別寫出等價(jià)的逆波蘭表示(運(yùn)算符優(yōu)先級按常規(guī)理解)。(1)aba0b0解答：逆波蘭表示為：aba0b0。(2)a(a*bd)*(ab*d)/d解答：逆波蘭表示為：aab*dabd*d/。(3)ab0a0(ab)2解答：逆波蘭表示為：ab0a0ab2。(4)a*(b*ca)bcd解答：逆波蘭表示為：abc*a*bcd。7-07給定下列中綴式，分別寫出等價(jià)的后綴式和四元式(運(yùn)算符優(yōu)先級按常規(guī)理解)。(1)(ab*c)/(ab)d解：后綴式：abc*+ab+/d- 四元式：（*，b, c, t1） (+, a, t1, t2) (+, a, b, t3 (/, t2,t3, t4) (-, t4,d, t5)(2)x+yza0解：后綴式：xy+za0 四元式：（+，x, y, t1） (,t1,z, t2) (, a, 0, t3 (,t2,t3, t4)(3)xy0 (xy)2解：后綴式：xy+0xy-2 四元式：（+，x, y, t1） (,t1,0, t2) (-, x, y, t3 (, t3,2, t4) (,t2,t4,t5)(4)a: