編譯原理練習(xí)題答案

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

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

3、.產(chǎn)生式是用于定義語(yǔ)法成分的一種書(shū)寫(xiě)規(guī)則。2-04.設(shè)G網(wǎng)是給定文法，則由文法G所定義的語(yǔ)言L（G）可描述為：L（G） = x 當(dāng)C *。2-05.設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果 當(dāng)（其中xCV*）,則稱(chēng)x是文法的一個(gè)句型。2-06.設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果=（其中xC *）,則稱(chēng)x是文法的一個(gè)句子。3-01.掃描器的任務(wù)是從源程序中識(shí)別出一個(gè)個(gè)單詞符號(hào)。4-01.語(yǔ)法分析最常用的兩類(lèi)方法是自上而下 和 自下而上 分析法。4-02.語(yǔ)法分析的任務(wù)是識(shí)別給定的終極符串是否為給定文法的句子。4-03.遞歸下降法不允許任一非終極符是直接左 遞歸的。4-04.自頂

4、向下的語(yǔ)法分析方法的關(guān)鍵是如何選擇候選式 的問(wèn)題。4-05.遞歸下降分析法是自頂向上分析方法。4-06.自頂向下的語(yǔ)法分析方法的基本思想是：從文法的開(kāi)始符號(hào)開(kāi)始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行直接推導(dǎo)，試圖推導(dǎo)出文法的句子，使之與給定的輸入串匹配。5-01.自底向上的語(yǔ)法分析方法的基本思想是：從給定的終極符串開(kāi)始，根據(jù)文法的規(guī)則一步一步的向上 進(jìn)行直接歸約，試圖歸約到文法的開(kāi)始符號(hào)。5-02.自底向上的語(yǔ)法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行直接歸約,力求歸約到文法的開(kāi)始符號(hào) 。5-03.簡(jiǎn)單優(yōu)先方法每次歸約當(dāng)前句型的句柄，算符優(yōu)先方法每

5、次歸約當(dāng)前句型的最左素短語(yǔ)，二者都是不斷移進(jìn)輸入符號(hào)，直到符號(hào)棧頂出現(xiàn)可歸約串 的尾,再向前找到可歸約串 的頭,然后歸約。5-04.在（0）分析法的名稱(chēng)中，L的含義是 自左向右的掃描輸入串，R的含義是 最左歸約，0的含義是向貌似句柄的符號(hào)串后查看0個(gè)輸入符號(hào) 。5-05.在(1)分析法的名稱(chēng)中，S的含義是 簡(jiǎn)單的。6-01.所謂屬性文法是一個(gè)屬性文法是一個(gè)三元組：A= ( G V, F), 一個(gè)上下文無(wú)關(guān)文法G; 一個(gè)屬性的有窮集V和關(guān)于屬性的斷言或謂詞的有窮集F。每個(gè)斷言與文法的某產(chǎn)生式相聯(lián)。6-02.綜合屬性是用于“自下而上”傳遞信息。6-03.繼承屬性是用于“自上而下”傳遞信息。6-04

6、.終結(jié)符只有綜合屬性，它們由詞法分析器提供。7-01.在使用高級(jí)語(yǔ)言編程時(shí)，首先可通過(guò)編譯程序發(fā)現(xiàn)源程序的全部A 錯(cuò)誤和B部分錯(cuò)誤.a.語(yǔ)法 b.語(yǔ)義 c.語(yǔ)用d.運(yùn)行8-01.符號(hào)表中的信息欄中登記了每個(gè)名字的屬性和特征等有關(guān)信息，如類(lèi)型、種屬、所占單元大小、8-02.一個(gè)過(guò)程相應(yīng)的表的內(nèi)容為現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址。9-01.一個(gè)過(guò)程相應(yīng)的表的內(nèi)容為現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址。9-02.常用的兩種動(dòng)態(tài)存貯分配辦法是 棧式動(dòng)態(tài)分配和堆式動(dòng)態(tài)分配。9-03.常用的參數(shù)傳遞方式有傳地址 ，傳值和傳名。10-01.局部?jī)?yōu)化是局限于一個(gè)基本塊 范圍內(nèi)的一種優(yōu)化。

7、10-02.代碼優(yōu)化的主要目標(biāo)是如何提高目標(biāo)程序的運(yùn)行速度和如何減少 目標(biāo)程序運(yùn)行時(shí)所需的空間 。、單選題：1-10. 一個(gè)編譯程序中，不僅包含詞法分析，語(yǔ)法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括c .其中，(2)b和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的詞法分析器用于識(shí)別 (3)c ,語(yǔ)法分析器則可以發(fā)現(xiàn)源程序中的(4)d .(1) a.模擬執(zhí)行器b.解釋器 c.表格處理和出錯(cuò)處理d.符號(hào)執(zhí)行器d.目標(biāo)代碼生成(2) a.語(yǔ)法分析 b.中間代碼生成c.詞法分析 a.字符串b.語(yǔ)句c.單詞d.標(biāo)識(shí)符(4) a.語(yǔ)義錯(cuò)誤b.語(yǔ)法和語(yǔ)義錯(cuò)誤c.錯(cuò)誤并校正d.語(yǔ)法錯(cuò)誤1-11.

8、程序語(yǔ)言的語(yǔ)言處理程序是一種(1)a . (2)b 是兩類(lèi)程序語(yǔ)言處理程序，他們的主要區(qū)別在于(3)d .(1) a.系統(tǒng)軟件 b.應(yīng)用軟件c.實(shí)時(shí)系統(tǒng)d.分布式系統(tǒng)(2) a.高級(jí)語(yǔ)言程序和低級(jí)語(yǔ)言程序b.解釋程序和編譯程序c.編譯程序和操作系統(tǒng)d.系統(tǒng)程序和應(yīng)用程序(3) a.單用戶(hù)與多用戶(hù)的差別b.對(duì)用戶(hù)程序的查錯(cuò)能力c.機(jī)器執(zhí)行效率d.是否生成目標(biāo)代碼1-12.匯編程序是將 a 翻譯成b ,編譯程序是將 c 翻譯成d .a.匯編語(yǔ)言程序b.機(jī)器語(yǔ)言程序c.高級(jí)語(yǔ)言程序d. a 或者b e. a 或者c f. b 或者c1-13.下面關(guān)于解釋程序的描述正確的是b .(1)解釋程序的特點(diǎn)是

9、處理程序時(shí)不產(chǎn)生目標(biāo)代碼(2) 解釋程序適用于和語(yǔ)言(3)解釋程序是為打開(kāi)編譯程序技術(shù)的僵局而開(kāi)發(fā)的a. (1)(2)b. (1)c. (1)(2)(3)d.(2)(3)1-14.高級(jí)語(yǔ)言的語(yǔ)言處理程序分為解釋程序和編譯程序兩種.編譯程序有五個(gè)階段，而解釋程序通常缺少e 和(1)b . 其中,(1)e的目的是使最后階段產(chǎn)生的目標(biāo)代碼更為高效與編譯系統(tǒng)相比，解釋系統(tǒng)(2)d .解釋程序處理語(yǔ)言時(shí)，大多數(shù)采用的是(3)b 方法.(4)a 就是一種典型的解釋型語(yǔ)言.(1): a.中間代碼生成b.目標(biāo)代碼生成c.詞法分析d.語(yǔ)法分析e.代碼優(yōu)化(2): a.比較簡(jiǎn)單，可移植性好，執(zhí)行速度快b. 比較復(fù)

10、雜，可移植性好，執(zhí)行速度快c. 比較簡(jiǎn)單，可移植性差，執(zhí)行速度慢d. 比較簡(jiǎn)單，可移植性好，執(zhí)行速度慢(3): a.源程序命令被逐個(gè)直接解釋執(zhí)行b.先將源程序轉(zhuǎn)化為之間代碼，再解釋執(zhí)行c.先將源程序解釋轉(zhuǎn)化為目標(biāo)程序，在執(zhí)行d.以上方法都可以(4) : a. b. C c. d.1-15.用高級(jí)語(yǔ)言編寫(xiě)的程序經(jīng)編譯后產(chǎn)生的程序叫b .用不同語(yǔ)言編寫(xiě)的程序產(chǎn)生b 后，可用 g連接在一起生成機(jī)器可執(zhí)行的程序.在機(jī)器中真正執(zhí)行的是e .a.源程序b.目標(biāo)程序 c.函數(shù)d.過(guò)程e.機(jī)器指令代碼f.模塊g.連接程序h.程序庫(kù)1-16.要在某一臺(tái)機(jī)器上為某種語(yǔ)言構(gòu)造一個(gè)編譯程序，必須掌握下述三方面的內(nèi)容：

11、c , d , jLa.匯編語(yǔ)言b.高級(jí)語(yǔ)言c. 源語(yǔ)言d. 目標(biāo)語(yǔ)言e.程序設(shè)計(jì)方法f.編譯方法g.測(cè)試方法 h.機(jī)器語(yǔ)言1-17.由于受到具體機(jī)器主存容量的限制，編譯程序幾個(gè)不同階段的工作往往被組合成d ,諸階段的工作往往是d 進(jìn)行的.a.過(guò)程b.程序c.批量d.遍(2) a.順序b.并行c.成批d.穿插1-18.編譯程序與具體的機(jī)器a ,與具體的語(yǔ)言 a.9 / 15a 重新執(zhí)行已執(zhí)行過(guò)的部分(2)分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的(3)分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的a. (2)(3)b. (2)(3)(4)1-21.編譯程序是一種常用的b 軟件.a. 應(yīng)用b.系統(tǒng)1-22.編寫(xiě)一個(gè)計(jì)算機(jī)

12、高級(jí)語(yǔ)言的源程序后a. 有關(guān) b.無(wú)關(guān)1-19.使用解釋程序時(shí)，在程序未執(zhí)行完的情況下，a.也能b.不可能1-20.編譯過(guò)程中，語(yǔ)法分析器的任務(wù)就是b .(1)分析單詞是怎樣構(gòu)成的(4)分析程序的結(jié)構(gòu)c. (1)(2)(3)d.(1)(2)(3)(4)，到正式上機(jī)運(yùn)行之前，一般要經(jīng)過(guò)b 這幾步.編輯 (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)語(yǔ)法分析(3)語(yǔ)義分析(4) 代碼生成(5)之間代碼生成(6)代碼優(yōu)化a.(2)(3)(4)b.(2)(3)(4

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

14、程序第二步工作是C 。A.語(yǔ)義分析B.詞法分析C.語(yǔ)法分析D.代碼優(yōu)化1-30.通常一個(gè)編譯程序中，不僅包含詞法分析，語(yǔ)法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等 五個(gè)部分，還應(yīng)包括 C。A.模擬執(zhí)行器B.解釋器 C.表格處理和出錯(cuò)處理D.符號(hào)執(zhí)行器 2-07 .文法G所描述的語(yǔ)言是 C 的集合。A.文法G的字母表V中所有符號(hào)組成的符號(hào)串. . 一 * 、B.又法G的字母表V的閉包V中的所有符號(hào)串C.由文法的開(kāi)始符號(hào)推出的所有終極符串D.由文法的開(kāi)始符號(hào)推出的所有符號(hào)串2-08 .喬姆斯基()把文法分為四種類(lèi)型，即 0型、1型、2型、3型。其中3型文法是B 。A.短語(yǔ)文法B. 正則文法 C

15、.上下文有關(guān)文法D.上下文無(wú)關(guān)文法2-09.文法GN= (b , N, B, N, N-b , B-),該文法所描述的語(yǔ)言是C 。A. L(GN)= i >0 B. L(GN)=b2i i >0C. L(GN)=b 21 i >0 D. L(GN)=b21 i > 12-10 . 一個(gè)句型中的最左B稱(chēng)為該句型的句柄?？蛇x項(xiàng)有：A.短語(yǔ) B.簡(jiǎn)單短語(yǔ)C. 素短語(yǔ) D.終結(jié)符號(hào) * 一、 * . .、 .2-11 .設(shè)G是一個(gè)給定的又法，S是又法的開(kāi)始符號(hào)，如果 =>(其中xCV),則稱(chēng)x是文法G的一個(gè) BA.候選式 B. 句型 C. 單詞 D. 產(chǎn)生式2-12 .

16、一個(gè)上下文無(wú)關(guān)文法 G包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組 D。A.句子 B. 句型 C. 單詞 D. 產(chǎn)生式2-13.文法 GE:EfT I E+ TT- F I T * F該文法句型（E+ T）F 一 a I ( E)E+ T F F * (E + T)E+ F * （E + T）的簡(jiǎn)單短語(yǔ)是下列符號(hào)串中的B可選項(xiàng)有：A）和 B） 和 C） 和 D） 2-14 .若一個(gè)文法是遞歸的，則它所產(chǎn)生的語(yǔ)言的句子A。A.是無(wú)窮多個(gè)B.是有窮多個(gè)C.是可枚舉的D.個(gè)數(shù)是常量3-02 .詞法分析器用于識(shí)別 C 。A.句子 B. 句型 C. 單詞 D. 產(chǎn)生式4

17、-07.在語(yǔ)法分析處理中，集合、集合、集合均是B。A.非終極符集 B. 終極符集 C. 字母表 D. 狀態(tài)集4-08.編譯程序中語(yǔ)法分析器接收以A 為單位的輸入。A.單詞 B. 表達(dá)式 C. 產(chǎn)生式 D. 句子5-06 .在自底向上的語(yǔ)法分析方法中，分析的關(guān)鍵是D。A.尋找句柄B.尋找句型C.消除遞歸D.選擇候選式5-07.在分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型C 的狀態(tài)。A.句柄 B.前綴 C. 活前綴 D. （0） 項(xiàng)目三、是非題（下列各題，你認(rèn)為正確的，請(qǐng)?jiān)陬}干的括號(hào)內(nèi)打“，”，錯(cuò)的打“X”。）1-31.計(jì)算機(jī)高級(jí)語(yǔ)言翻譯成低級(jí)語(yǔ)言只有解釋一種方式。（X）1-32.在編譯中進(jìn)行語(yǔ)法

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

19、柄。（X）5-13. 一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。（，）7-02.數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。（，）8-03.在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。（X）9-04.對(duì)于數(shù)據(jù)空間的存貯分配，采用動(dòng)態(tài)貯存分配策略。（X）9-05.在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。（X）四、名詞解釋1-35.掃描遍指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。2-16.短語(yǔ)一一設(shè)GZ是給定文法,C,為該文法的句型,如果滿(mǎn)足下面兩個(gè)條件：Z當(dāng)；U當(dāng)u ;則稱(chēng)句型中的子串u是句型的短語(yǔ)。2-17.簡(jiǎn)單短語(yǔ)一一設(shè) GZ是給定文法，C,為該文法的句型，如果滿(mǎn)足下面兩個(gè)條件：Z當(dāng)； U n u ;則稱(chēng)

20、句型中的子串u是句型的簡(jiǎn)單短語(yǔ)(或直接短語(yǔ))。2-18.句柄個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱(chēng)為該句型的句柄。4-11.語(yǔ)法分析-按文法的產(chǎn)生式識(shí)別輸入的符號(hào)串是否為一個(gè)句子的分析過(guò)程。4-12.選擇符集合給定上下文無(wú)關(guān)文法的產(chǎn)生式A- a , A C , a C V*,若a3e ,則(A- a )( a ),其中如果 a =' e ,則(A一 a )( a e ) U (A)( a e )表不' (a )的非 e 兀素。5-14.活前綴一一若S'寺a Aco =R a 3 co是文法G'中的一個(gè)規(guī)范推導(dǎo)，G'是 G的拓廣文法，符號(hào)串 丫是a 3的前綴，則稱(chēng) 丫是

21、G的，也是G'的一個(gè)活前綴。其中 S'為文法開(kāi)始符號(hào)?；颍嚎蓺w前綴 的任意首部。5-15.簡(jiǎn)歸前綴一一是指規(guī)范句型的一個(gè)前綴，這種前綴不含句柄之后的任何符號(hào)。5-16(0)項(xiàng)目一一把產(chǎn)生式右部某位置上標(biāo)有圓點(diǎn)的產(chǎn)生式稱(chēng)為相應(yīng)文法的一個(gè)(0)項(xiàng)目。5-17.最左素短語(yǔ)一一設(shè)有文法GS,其句型的素短語(yǔ)是一個(gè)短語(yǔ) ，它至少包含一個(gè)終結(jié)符，并除自身外不包含其它素短語(yǔ)，最左邊的素短語(yǔ)稱(chēng)最左素短語(yǔ)。6-05.語(yǔ)義規(guī)則一一對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱(chēng)為語(yǔ)義規(guī)則。6-06.翻譯方案一一將屬性文法中的語(yǔ)義規(guī)則用花括號(hào) 括起來(lái)，插在產(chǎn)生式右部的合適地方，指明語(yǔ)義規(guī)則的計(jì)算次序

22、，陳述一些細(xì)節(jié)，得到一種語(yǔ)義動(dòng)作與語(yǔ)法分析交錯(cuò)的表示方法，以表述語(yǔ)義動(dòng)作在語(yǔ)法 分析過(guò)程中的執(zhí)行時(shí)刻，稱(chēng)之為翻譯方案。7-03.后綴式一一一種把運(yùn)算量(操作數(shù))寫(xiě)在前面把算符寫(xiě)在后面(后綴)的表示法。即一個(gè)表達(dá)式E的后綴形式可以如下定義：(1)如果 弱一個(gè)變量或常量，則 E的后綴式是E自身。(2)如果弱Ei E 2形式的表達(dá)式，這里是任何二元操作符，則E的后綴式為Ei' E2',這里E1'和E'分別為E1和E的后綴式。(3)如果弱(E1)形式的表達(dá)式，則 E1的后綴式就是E的后綴式。答：一個(gè)過(guò)程的活動(dòng)指的是該過(guò)程的一次執(zhí)行。就是說(shuō)，每次執(zhí)行一個(gè)過(guò)程體， 產(chǎn)生該過(guò)

23、程體的一個(gè)活動(dòng)。9-07.活動(dòng)記錄答：為了管理過(guò)程在一次執(zhí)行中所需要的信息，使用一個(gè)連續(xù)的存儲(chǔ)塊，這樣一個(gè)連續(xù)的存儲(chǔ)塊稱(chēng)為活動(dòng) 記錄。9-08.活動(dòng)的生存期答：指的是從執(zhí)行某過(guò)程體第一步操作到最后一步操作之間的操作序，包括執(zhí)行過(guò)程時(shí)調(diào)用其它過(guò)程花費(fèi) 的時(shí)間。10-06. 基本塊的。答：一個(gè)基本塊的是一種其結(jié)點(diǎn)帶有下述標(biāo)記或附加信息的。(1)圖的葉結(jié)點(diǎn)(沒(méi)有后繼的結(jié)點(diǎn))以一標(biāo)識(shí)符(變量名)或常數(shù)作為標(biāo)記，表示該結(jié)點(diǎn)代表該變量或常數(shù)的值。如果葉結(jié)點(diǎn)用來(lái)代表某變量A的地址，則用(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)

24、)以一運(yùn)算符作為標(biāo)記，表示該結(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對(duì)其后繼結(jié) 點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果。(3)圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)識(shí)符，表示這些變量具有該結(jié)點(diǎn)所代表的值。五、簡(jiǎn)答題：2-19什么是句子？什么是語(yǔ)言？答：設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果 當(dāng)(其中xb),則稱(chēng)x是文法的一個(gè)句子。 設(shè)GS是給定文法，則由文法G所定義的語(yǔ)言L(G)可描述為：L(G) =x => *。2-20.已知文法 GE為：E 一T-*F 一( E該文法的開(kāi)始符號(hào)(識(shí)別符號(hào))是什么？請(qǐng)給出該文法的終結(jié)符號(hào)集合和非終結(jié)符號(hào)集合。 找出句型*的所有短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。解：該文法的開(kāi)始符號(hào)(識(shí)別符號(hào))

25、是 E。該文法的終結(jié)符號(hào)集合+、-、*、/、(、)、 i。非終結(jié)符號(hào)集合E、T、F。句型*的短語(yǔ)為i、T*F、第一個(gè)T、*;簡(jiǎn)單短語(yǔ)為i、T*F、第一個(gè)T;句柄為第一個(gè)To2-21.已知文法 GS為:S 一A一B 一 £GS產(chǎn)生的語(yǔ)言是什么？GS能否改寫(xiě)為等價(jià)的正規(guī)文法？解：GS產(chǎn)生的語(yǔ)言是L(GS)= n>1>00GS能改寫(xiě)為等價(jià)的正規(guī)文法，其改寫(xiě)后的等價(jià)的正規(guī)文法GS '為：S / 一A 一 B 一2-22.設(shè)有語(yǔ)言L(G)= | a C ()*為a之逆，試構(gòu)造產(chǎn)生此語(yǔ)言的上下文無(wú)關(guān)文法G解：根據(jù)題義，可知 為a之逆的含義就是句子中的符號(hào)a、b以d為中心呈左右

26、對(duì)稱(chēng)出現(xiàn)；由于 aC () *,所以a、b的個(gè)數(shù)可以為零。所以可構(gòu)造產(chǎn)生此語(yǔ)言的上下文無(wú)關(guān)文法GS為：S-3-03 .簡(jiǎn)述與有何區(qū)別 ？答：與的區(qū)別表現(xiàn)為兩個(gè)方面：一是可以若干個(gè)開(kāi)始狀態(tài)，而僅只一個(gè)開(kāi)始狀態(tài)。另一方面，的映象M是從KX匯到K,而的映象 M是從KX匯到K的子集，即映象 M將產(chǎn)生一個(gè)狀態(tài)集合(可能為空集)，而不是單個(gè)狀態(tài)。3-04.試給出非確定自動(dòng)機(jī)的定義。答：一個(gè)非確定的有窮自動(dòng)機(jī)()M是一個(gè)五元組：(K, 2, f, S , Z)。其中：1. K是一個(gè)有窮集，它的每個(gè)元素稱(chēng)為一個(gè)狀態(tài)；2. 2是一個(gè)有窮字母表，它的每個(gè)元素稱(chēng)為一個(gè)輸入符號(hào)，所以也稱(chēng)2為輸入符號(hào)表；3. f是狀態(tài)

27、轉(zhuǎn)換函數(shù)，是在 KX 2* - K的子集的映射，即，f： KXN* - 2K ;表明在某狀態(tài)下對(duì)于某 輸入符號(hào)可能有多個(gè)后繼狀態(tài)；4. S ( K 是一一個(gè)非空初態(tài)集；5. Z( K 是一一個(gè)終態(tài)集(可空)。3-05.為正規(guī)式()*a()構(gòu)造一個(gè)等價(jià)的確定的有限自動(dòng)機(jī)。解答：ab3-06.給定下列自動(dòng)機(jī)，將其轉(zhuǎn)換為確定的自動(dòng)機(jī)。注：帶十號(hào)的結(jié)點(diǎn)為初始狀態(tài)；帶一號(hào)的結(jié)點(diǎn)為終止?fàn)顟B(tài)解答：消除e邊，得到:注：帶十號(hào)的結(jié)點(diǎn)為初始狀態(tài)；帶一號(hào)的結(jié)點(diǎn)為終止?fàn)顟B(tài)(2)確定化，得到:十一d十一d+注：帶十號(hào)的結(jié)點(diǎn)為初始狀態(tài)； 帶一號(hào)的結(jié)點(diǎn)為終止?fàn)顟B(tài)SAAG+AAGAAGBBCCDGHDDEEGHHGHHH13

28、 / 153-07.給定下列自動(dòng)機(jī):其中：開(kāi)始狀態(tài)：0終止?fàn)顟B(tài)：2(1)把此自動(dòng)機(jī)轉(zhuǎn)換為確定自動(dòng)機(jī)。(2)給出此的正則表達(dá)式。解答：(1)：有狀態(tài)矩陣如圖：二00,1 212-21 2二 0012101 201 2122從而可得如圖:極小化后:b 此的正則表達(dá)式為：(%b)(b |)*或a *b (b|)4-13.消除下列文法 GE的左遞歸。F-( E) i解答：消除文法GE的左遞歸后得到：E-'E' f ' I £IT' f ' I £F-( E) i4-14.在(1)分析法中分別代表什么含義 ？答：第一個(gè)L代表從左到右的寸3描，第

29、二個(gè)L代表每次進(jìn)行最左推導(dǎo)。4-15.自頂向下分析思想是什么？答：從開(kāi)始符出發(fā)導(dǎo)出句型并一個(gè)符號(hào)一個(gè)符號(hào)地與給定終結(jié)符串進(jìn)行匹配。如果全部匹配成功，則表示開(kāi)始符號(hào)可推導(dǎo)出給定的終結(jié)符串。因此判定給定終結(jié)符號(hào)串是正確句子。4-16.自頂向下的缺點(diǎn)是什么？答：在推導(dǎo)過(guò)程中，如果對(duì)文法不做限制。那么產(chǎn)生式的選擇成為無(wú)根據(jù)的，只好一一去試所有可能的產(chǎn) 生式，直至成功為止。這種方法的致命弱點(diǎn)是不斷地回溯，大大影響速度。4-17 (1)文法的定義是什么？答：一個(gè)上下文無(wú)關(guān)文法是(1)文法的充分必要條件是每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式，A- “ 一 3 ;滿(mǎn)足(A 一 a)ri(A - 3)=。其中，a、3

30、不能同時(shí)為' £ °4-18.什么是文法的左遞歸？答：一個(gè)文法含有下列形式的產(chǎn)生式之一時(shí)：1)A-A3 , AC , 3 e v*2)A - B3 , Bf Aa , A、B , a、3 V*則稱(chēng)該文法是左遞歸的。4-19.遞歸下降法的主要思想是什么？答：對(duì)每個(gè)非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫(xiě)出相應(yīng)語(yǔ)法分析子程序。因?yàn)槲姆ㄟf歸相應(yīng)子程序也遞歸，子程序 的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎一致。所以稱(chēng)此種方法稱(chēng)為遞歸子程序法或遞歸下降法。5-19.自底向上分析法的原理是什么？答：在采用自左向右掃描，自底向上分析的前提下，該類(lèi)分析方法是從輸入符號(hào)串入手，通過(guò)反復(fù)查找當(dāng) 前句型的句柄(最左簡(jiǎn)單

31、短語(yǔ))，并使用文法的產(chǎn)生式把句柄歸約成相應(yīng)的非終極符來(lái)一步步地進(jìn)行 分析的。最終把輸入串歸約成文法的開(kāi)始符號(hào)，表明分析成功。ZfC S C 一 E A A = E EfE V A EfA A-i1.2.3.4.5-23.給定文法GZ:其中：Z、C、S A、EC ；、=、V、 i Ca）構(gòu)造此文法的（0）項(xiàng)目集規(guī)范族，并給出識(shí)別活前綴的。b）構(gòu)造其（1）分析表。G',再求G'的識(shí)別全部活前解答：1.首先拓廣文法：在 G中加入產(chǎn)生式0. Z' -Z,然后得到新的文法綴的:Io： Z一Z 一 S C 一 EIi： Z- Z.I 2： Z-C S-= E A 一I 3： C一

32、EfV A E 一 A 一I4： Z - C S.I 5: S 一 A. = E16： A-i.I7： C- EEfE. V AI9： AA =EfV A E 一 A 一Iio: C一 E .I11： E - EVA 一112: S一 A = E.EfE. V AI13： E-EVA.2. (Z) =#(C) = i(S) =#(E) = #，V(A) =，V 則可構(gòu)造(1)分析表為:0=Vi#ZCSEA0S31212S453S784r 15S96r6r 6r6r 67S10S118r5r5r 59S612810r 211S61312S1131344r 4求識(shí)別該文法所有活前綴的。解答：5-24.設(shè)有文法GS:(1) .首先拓廣文法：在G中加入產(chǎn)生式0' -S,然后得到新的文法 G0' 一 S1 一2 一(2).再求G的識(shí)別全部活前綴的:3一 b6-07.語(yǔ)法制導(dǎo)翻譯方法的基本思想是什么答：在語(yǔ)法分析過(guò)程中，每當(dāng)使用一條產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，就執(zhí)行該產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義動(dòng)作進(jìn)行 屬性計(jì)算，完成對(duì)輸入