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

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

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

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

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

6、自上而下”傳遞信息。6-04.終結(jié)符只有綜合屬性，它們由詞法分析器提供。7-01.在使用高級(jí)語言編程時(shí)，首先可通過編譯程序發(fā)現(xiàn)源程序的全部 A 錯(cuò)誤和旦部分錯(cuò)誤.a.語法 b.語義 c.語用 d.運(yùn)行8-01.符號(hào)表中的信息欄中登記了每個(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)記錄的地址。9-02.常用的兩種動(dòng)態(tài)存貯分配辦法是棧式動(dòng)態(tài)分配和堆式動(dòng)態(tài)分配。9-03.常用的參數(shù)傳遞方式有傳地

7、址，傳值和傳名。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 表格處理和出錯(cuò)處理.其中，(2)b 中間代碼生成和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的.詞法分析器用于識(shí)別白單詞，語法分析器則可以發(fā)現(xiàn)源程序中的(4)d 語法錯(cuò)誤.1-11.程序語言的語言處理程序是一種(1)a 系統(tǒng)軟件.(2 比一解釋程序和編譯程序是兩類程序語言處理程序，他們的主要區(qū)別在于(3)d

8、是否生成目標(biāo)代碼.1-12.匯編程序是將 a_匯編語言程序翻譯成 b 機(jī)器語言程序，編譯程序是將邑高級(jí)語言程序翻譯成 ya 或者 b.1-13.下面關(guān)于解釋程序的描述正確的是 b 解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)生目標(biāo)代碼1-14.高級(jí)語言的語言處理程序分為解釋程序和編譯程序兩種.編譯程序有五個(gè)階段，而解釋程序通常缺少(1)e 代碼優(yōu)化和(1)b 目標(biāo)代碼生成.其中，(1 怛代碼優(yōu)化的目的是使最后階段產(chǎn)生的目標(biāo)代碼更為局效.與編譯系統(tǒng)相比，解釋系統(tǒng)儂比較簡單，可移植性好，執(zhí)行速度慢解釋程序處理語言時(shí)，大多數(shù)采用的是(3 比先將源程序轉(zhuǎn)化為之間代碼，再解釋執(zhí)行方法.(4)aBASIC 就是一種典型

9、的解釋型語言.1-15.用高級(jí)語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫 b 目標(biāo)程序.用不同語言編寫的程序產(chǎn)生 b 目標(biāo)程序后，可用 g 連接程序連接在一起生成機(jī)器可執(zhí)行的程序.在機(jī)器中真正執(zhí)行的是旦機(jī)器指令代碼.1-16.要在某一臺(tái)機(jī)器上為某種語言構(gòu)造一個(gè)編譯程序，必須掌握下述三方面的內(nèi)容：巳源語言，L 目標(biāo)語言,f_編譯方法.1-17.由于受到具體機(jī)器主存容量的限制，編譯程序幾個(gè)不同階段的工作往往被組合成d 遍,諸階段的工作往往是（2）d_穿插進(jìn)行的.1-18.編譯程序與具體的機(jī)器 a 有關(guān)，與具體的語言 a 有關(guān).1-19.使用解釋程序時(shí)，在程序未執(zhí)行完的情況下，a 也能重新執(zhí)行已執(zhí)行過的部分

10、.1-20.編譯過程中，語法分析器的任務(wù)就是 b（2）分析單詞串是如何構(gòu)成語句和說明的（3）分析語句和說明是如何構(gòu)成程序的（4）分析程序的結(jié)構(gòu).1-21.編譯程序是一種常用的 b 系統(tǒng)軟件.1-22.編寫一個(gè)計(jì)算機(jī)高級(jí)語言的源程序后，到正式上機(jī)運(yùn)行之前，一般要經(jīng)過 b（1）編輯（2）編譯（3）連接這幾步.1-23.編譯程序必須完成的工作有 a（1）詞法分析（2）語法分析（3）語義分析（4）代碼生成.1-24.“用高級(jí)語言書寫的源程序都必須通過編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”這種說法 a 不正確.1-25.把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由 b 匯編器完成的.1-26.編譯程序

11、生成的目標(biāo)程序 b 不一定是機(jī)器語言的程序.1-27.編譯程序生成的目標(biāo)程序 b 不一定是可執(zhí)行的程序.1-28.編譯程序是一種 B 翻譯程序。1-29.按邏輯上劃分，編譯程序第二步工作是 C 語法分析。1-30.通常一個(gè)編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括 C 表格處理和出錯(cuò)處理。2-07.文法 G 所描述的語言是 C 由文法的開始符號(hào)推出的所有終極符串的集合。2-08.喬姆斯基（Chomsky）把文法分為四種類型，即 0 型、1 型、2 型、3 型。其中 3 型文法是 B 正則文法。2-09.文法 GN=（b,N,B,N,Nfbb

12、B,B-bN）,該文法所描述的語言是 CL（GN）=b2i+1i0。2-10.一個(gè)句型中的最左 B_簡單短語稱為該句型的句柄。2-11.設(shè) G 是一個(gè)給定的文法，S 是文法的開始符號(hào)，如果 ax（其中 xCV*）,則稱 x 是文法 G 的一個(gè) B句型。2-12.一個(gè)上下文無關(guān)文法 G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組 D 產(chǎn)生式。2-13.文法 GE:E-TIE+TT-FIT*FF 一 aI（E）該文法句型 E+F*（E+T）的簡單短語是下列符號(hào)串中的 B2）E+T 和F。2-14.若一個(gè)文法是遞歸的，則它所產(chǎn)生的語言的句子 A 是無窮多個(gè)。3-0

13、2.詞法分析器用于識(shí)別 C 單詞。4-07.在語法分析處理中，F(xiàn)IRST 集合、FOLLOW 合、SELECT1 合士是 B 終極符集。4-08.編譯程序中語法分析器接收以 A 單詞為單位的輸入。5-06.在自底向上的語法分析方法中，分析的關(guān)鍵是 D 選擇候選式。5-07.在 LR 分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型 C 活前綴的 DFA 狀態(tài)。三、是非題（下列各題，你認(rèn)為正確的，請(qǐng)?jiān)陬}干的括號(hào)內(nèi)打，錯(cuò)的打“X”。）1-31.計(jì)算機(jī)高級(jí)語言翻譯成低級(jí)語言只有解釋一種方式。（X）1-32.在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。（X）1-34.甲機(jī)上的某編譯程序在乙機(jī)上能直接

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

15、）7-02.數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。（，）8-03.在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。（X）9-04.對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRA 葉用動(dòng)態(tài)貯存分配策略。（X）9-05.在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。（X）10-03.僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無用的。（，）10-04.削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性。（X）10-05.在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。（四、名詞解釋 1-35.掃描遍指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。2-16.短語一一設(shè) GZ是給定文法，w=xuyCV+,為該文法

16、的句型，如果滿足下面兩個(gè)條件：Z,xUy;Uqu;則稱句型 xuy 中的子串 u 是句型 xuy 的短語。2-17.簡單短語一一設(shè) GZ是給定文法，w=xuyCV+,為該文法的句型，如果滿足下面兩個(gè)條件：Z,xUy;Uu;則稱句型 xuy 中的子串 u 是句型 xuy 的簡單短語（或直接短語）。2-18.短柄個(gè)句型中的最左簡單短語稱為該句型的句柄。4-11.語法分析按文法的產(chǎn)生式識(shí)別輸入的符號(hào)串是否為一個(gè)句子的分析過程。4-12.選擇符集合 SELEC給定上下文無關(guān)文法的產(chǎn)生式 Afa,ACVN,aCV*,若 a 史e,則SELECT（Aa）=FIRST（a）,其中如果 a=,貝 USELEC

17、T（Aa）=FIRST（as）UFOLLOW（A）,FIRST（as）表示 FIRST（a）的非e元素。5-14.活前綴一一若 SRACOaco 是文法 G中的一個(gè)規(guī)范推導(dǎo)，G是 G 的拓廣文法，符號(hào)串丫是 a3 的前綴，則稱丫是G 的，也是 G的一個(gè)活前綴。其中 S為文法開始符號(hào)?；颍嚎蓺w前綴的任意首部。5-15.可歸前綴一一是指規(guī)范句型的一個(gè)前綴，這種前綴不含句柄之后的任何符號(hào)。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è)有一不含產(chǎn)生式的算符文法 G,如果對(duì)任意兩個(gè)終結(jié)符對(duì) a,b 之間至多只有、和三三種關(guān)

18、系中的一種成立，則稱 G 是一個(gè)算符優(yōu)先文法。5-18.最左素短語一一設(shè)有文法 GS,其句型的素短語是一個(gè)短語，它至少包含一個(gè)終結(jié)符，并除自身外不包含其它素短語，最左邊的素短語稱最左素短語。6-05.語義規(guī)則一一對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為語義規(guī)則。6-06.翻譯方案一一將屬性文法中的語義規(guī)則用花括號(hào)括起來，插在產(chǎn)生式右部的合適地方，指明語義規(guī)則的計(jì)算次序，陳述一些細(xì)節(jié)，得到一種語義動(dòng)作與語法分析交錯(cuò)的表示方法，以表述語義動(dòng)作在語法分析過程中的執(zhí)行時(shí)刻，稱之為翻譯方案。7-03,后綴式一一一種把運(yùn)算量(操作數(shù))寫在前面把算符寫在后面(后綴)的表示法。即一個(gè)表達(dá)式 E 的

19、后綴形式可以如下定義：(1)如果弱一個(gè)變量或常量，則 E 的后綴式是 E 自身。(2)如果弱 EiopE2形式的表達(dá)式，這里 op 是任何二元操作符，則 E 的后綴式為 EiEop,這里 Ei和 E2分別為 B和 Ez的后綴式。(3)如果弱(Ei)形式的表達(dá)式，則 Ei的后綴式就是 E 的后綴式。7-04.四元式一一一個(gè)四元式是一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱為 op、argi、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)記錄答：為了管理過程在一

20、次執(zhí)行中所需要的信息，使用一個(gè)連續(xù)的存儲(chǔ)塊，這樣一個(gè)連續(xù)的存儲(chǔ)塊稱為活動(dòng)記錄。9-08,活動(dòng)的生存期答：指的是從執(zhí)行某過程體第一步操作到最后一步操作之間的操作序，包括執(zhí)行過程時(shí)調(diào)用其它過程花費(fèi)的時(shí)間。i0-06.基本塊的 DAG答：一個(gè)基本塊的 DAG 是一種其結(jié)點(diǎn)帶有下述標(biāo)記或附加信息的 DAG(i)圖的葉結(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)記，表

21、示該結(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)所代表的值。五、簡答題：2-i9 什么是句子？什么是語言答：設(shè) G 是一個(gè)給定的文法，S 是文法的開始符號(hào)，如果 S 當(dāng) x(其中 xVT*),則稱 x 是文法的一個(gè)句子。設(shè) GS是給定文法，則由文法 G 所定義的語言 L(G)可描述為：L(G)=xS=x,xVT*o2-20.已知文法 GE為：E-T|E+T|E-TT-F|T*F|T/FF-(E)|i該文法的開始符號(hào)(識(shí)別符號(hào))是什么？請(qǐng)給出該文法的終結(jié)符號(hào)集合 W 和非終結(jié)符號(hào)集合 VNO找出句型 T+T*F+i

22、 的所有短語、簡單短語和句柄。解：該文法的開始符號(hào)(識(shí)別符號(hào))是 E。該文法的終結(jié)符號(hào)集合 VT=+、-、*、/、(、)、i。非終結(jié)符號(hào)集合 VN=E、T、F。句型 T+T*F+I 的短語為 i、T*F、第一個(gè) T、T+T*F+i;簡單短語為 i、T*F、第一個(gè) T;句柄為第一個(gè) To2-21.已知文法 GS為：SfdABZaA|aBfBb|GS產(chǎn)生的語言是什么？GS能否改寫為等價(jià)的正規(guī)文法？解：GS產(chǎn)生的語言是 L(GS)=danbmn1,m0oGS能改寫為等價(jià)的正規(guī)文法，其改寫后的等價(jià)的正規(guī)文法 GS/為：S-dAZaA|aB|aBfbB|b2-22.設(shè)有語言 L(G)=adaR|aC(a

23、,b):aR為 a 之逆，試構(gòu)造產(chǎn)生此語言的上下文無關(guān)文法 G。解：根據(jù)題義，可知 aR為 a 之逆的含義就是句子中的符號(hào) a、b 以 d 為中心呈左右對(duì)稱出現(xiàn)；由于 aC(a,b)*,所以 a、b 的個(gè)數(shù)可以為零。所以可構(gòu)造產(chǎn)生此語言的上下文無關(guān)文法 GS為：S-aSa|bSb|d3-03.簡述 DFA 與 NFA 有何區(qū)別答：DFA 與 NFA 的區(qū)別表現(xiàn)為兩個(gè)方面：一是 NFA 可以若干個(gè)開始狀態(tài)，而 DFA 僅只一個(gè)開始狀態(tài)。另一方面，DFA 的映象 M 是從 KX 匯到 K,而 NFA 的映象 M 是從 KX 匯到 K 的子集，即映象 M 將產(chǎn)生一個(gè)狀態(tài)集合(可能為空集)，而不是單個(gè)

24、狀態(tài)。3-04.試給出非確定自動(dòng)機(jī)的定義。答：一個(gè)非確定的有窮自動(dòng)機(jī)(NFAM 是一個(gè)五元組：M=(K,2,f,S,Z)。其中：1 .K 是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2 .2 是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱 2 為輸入符號(hào)表；3 .f 是狀態(tài)轉(zhuǎn)換函數(shù)，是在 KX2*fK 的子集的映射，即，f:KX2*f2K;表明在某狀態(tài)下對(duì)于某輸入符號(hào)可能有多個(gè)后繼狀態(tài)；4 .S(K 是一一個(gè)非空初態(tài)集；5.Z(K 是一一個(gè)終態(tài)集(可空)。3-05.為正規(guī)式(a|b)*a(a|b)構(gòu)造一個(gè)等價(jià)的確定的有限自動(dòng)機(jī)。解答：E-TEITfFT一/FTIF 一(E)Ii4-14.

25、在 LL(1)分析法中,LL 分別代表什么含義答：第一個(gè) L 代表從左到右的掃描，第二個(gè) L 代表每次進(jìn)行最左推導(dǎo)。4-15.自頂向下分析思想是什么?定的自動(dòng)3-07.給定下列自動(dòng)機(jī):(1)把此自動(dòng)機(jī)(2)空解答：(2)此 DFA 的正則表達(dá)4-13.消除下列文法 GaE-E-TITaT-T/FIF 一(E)Ii解答：消除文法 GEEfTEbb)(kb出題域010-212a也(ba2解答：(1)消除邊，得到 NFABd+(2)確定他彳S81dHDFAcb212臺(tái)狀態(tài);態(tài)從而可得DFA如圖0012,將箕轉(zhuǎn)段2da注：帶十號(hào)的結(jié)點(diǎn)為初始狀態(tài);帶一號(hào)的結(jié)點(diǎn)為終止?fàn)顟B(tài)其中：開始狀態(tài)：0終止?fàn)顟B(tài)：2注：

26、 帶十號(hào)的結(jié)點(diǎn)為初始狀態(tài);帶一號(hào)的結(jié)點(diǎn)為終止?fàn)顟B(tài)b_40013-06.給霍 b*2b(aa遞歸。bb0_*ab)。0答：從開始符出發(fā)導(dǎo)出句型并一個(gè)符號(hào)一個(gè)符號(hào)地與給定終結(jié)符串進(jìn)行匹配。如果全部匹配成功，則表示開始符號(hào)可推導(dǎo)出給定的終結(jié)符串。因此判定給定終結(jié)符號(hào)串是正確句子。4-16.自頂向下的缺點(diǎn)是什么？答：在推導(dǎo)過程中，如果對(duì)文法不做限制。那么產(chǎn)生式的選擇成為無根據(jù)的，只好一一去試所有可能的產(chǎn)生式，直至成功為止。這種方法的致命弱點(diǎn)是不斷地回溯，大大影響速度。4-17.LL(1)文法的定義是什么？答：一個(gè)上下文無關(guān)文法是 LL(1)文法的充分必要條件是每個(gè)非終結(jié)符 A 的兩個(gè)不同產(chǎn)生式，A-a

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

28、的句柄(最左簡單短語)，并使用文法的產(chǎn)生式把句柄歸約成相應(yīng)的非終極符來一步步地進(jìn)行分析的。最終把輸入串歸約成文法的開始符號(hào)，表明分析成功。5-20.簡單優(yōu)先方法基本思想是什么？答：簡單優(yōu)先方法基本思想是首先規(guī)定文法符號(hào)之間的優(yōu)先關(guān)系和結(jié)合性質(zhì)，然后在利用這種關(guān)系，通過比較兩個(gè)相鄰的符號(hào)之間的優(yōu)先順序來確定句型的“句柄”并進(jìn)行歸約。5-21.三種優(yōu)先關(guān)系的定義是什么?答：三種優(yōu)先關(guān)系的定義是:1.si，sj 當(dāng)且僅當(dāng)存在形如下面的產(chǎn)生式 U-SSj-2.siqsj 當(dāng)且僅當(dāng)存在形如下面的產(chǎn)生式 U-SiW的生產(chǎn)式，且有庇 S3.sisj 當(dāng)且僅當(dāng)存在形如下面的產(chǎn)生式 UfVW的生產(chǎn)式，且有心 S

29、 和消 S5-22.如何確定簡單優(yōu)先文法的句柄？答：設(shè) SSr-S 是簡單優(yōu)先文法的規(guī)范句型，其子串 SS+1S是滿足下列條件的最左子串:S-1,SS_LS+1_1SS+1貝 USiS+1S 定是 SQ$的句柄。5-23.給定文法 GZ:1.ZfCSa)構(gòu)造此文法的 LR(0)項(xiàng)!集 CsZS6EA)0S3JJ1OKzu2&453&784r15S6r6r6r6r67S10S118r5r5r59&12810r211&1312S11313r4r4r4V=,#,V,thenSLR(1)分析表為:Follow(A)則可構(gòu)造5-24.設(shè)有文法 GS:S一aA求識(shí)別該文法麻

30、侑活前綴的 DFA解答：Ab(1).首先拓廣文法：在 G 中加入產(chǎn)生式 0.S-S,然后得到新的文法 G:0.S一 S(2).再求 G的識(shí)足耳機(jī)綴的 DFA6-07.語法制導(dǎo)翻譯 3AH本思想是什么答：在語法分析過程中，每當(dāng)使用一條產(chǎn)生式進(jìn)行推行屬性計(jì)算，完成對(duì)輸入符號(hào)串的翻譯。6-08.何謂“語法制導(dǎo)翻譯”I1:S一S.S-aA.ZA.bI0:Sf.SS一.aA或歸約時(shí),就執(zhí)行I2:Sfa.AZ.AbZ.bA立的語義動(dòng)作進(jìn)I4:A-Ab.A一b.該產(chǎn)生式所對(duì)答：在語法分析過程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語義子程序(或語義規(guī)則描述的語義動(dòng)作)進(jìn)行翻譯的辦法稱作語法制導(dǎo)翻譯。6

31、-09.在一個(gè)屬性文法中，又應(yīng)于每個(gè)產(chǎn)生式 A-a 都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的形式為b:=f(c1,c2，ck),其中對(duì)于 b 的要求是什么？答：語義規(guī)則中的左部屬性變量 b 被規(guī)定為只能是下述兩種變量：對(duì)應(yīng)產(chǎn)生式左部符號(hào)的綜合屬性變量；對(duì)應(yīng)產(chǎn)生式右部符號(hào)的繼承屬性變量。6-10.給定文法及相應(yīng)的翻譯方案：SfbTcprint(0)為該文用勢 apr店上案#1使乂型 bR/bTc/bSc/ac 經(jīng)該翻譯方案翻譯后，輸出串:(+,a,t1,t2)(+,a,b,t3(/,t2,t3,t4)(-,t4at5)(2)x+y0解：后綴式：xy+zWa0V四元式：(+,x,y,t1)TfRp

32、rint(2)解：給出句型R小跚端就姓“3的獷法樹如右圖：則對(duì)于句型 bR/S麻 c/ac,4娥完該句型后輸出是:6-10.給定文法及相應(yīng)的翻譯方案：)E-E+Tprint(5”)EWpffit(T+(Q(F+T)*i),解： TWWrint+(T*(F3+T)i)則對(duì)grint+(T*(F+T)i),處理完該句型后輸出是什么?的語法樹如右圖:R處理完該句型后輸出7-05F衰俱岫陣W 語言沛況哪幾種？答：Ff!郎磔、三配 M 弋碼、抽象語法樹和DAG7-06.給定下列中綴式，分別寫出等價(jià)的逆波蘭表示(1)-a0VbAb0vV，(2)a(a*bd)*(ab*d)/d解答：逆波蘭表示為：aab*d

33、abd*d/(3)-a+b0Va2解答：逆波蘭表示為:ab+0wa0Vab2/V。(4)a*(b*ca)wb+c/d解答：逆波蘭表示為：abc*a*bc+,a,0,t3(V,t2,t3,t4)(3)x+y2解：后綴式：xy+0V四元式：(+,x,y,t1)(w,t1,0,t2)(-,x,y,t3(,t32t4)(V,t2,t4,t5)(4)a:=(b*ca)*a解：后綴式：abc*a-a*:=四元式：(*,b,c,t1)(-,t1,a,t2)(*,t2,a,t3(：=,t3,a)8-04.符號(hào)表的組織方式有哪幾種？答：一個(gè)編譯程序?qū)Ψ?hào)表的總體組織可有三種選擇：第一種：把屬性種類完全相同的那些

34、符號(hào)組織在一起，構(gòu)造出表項(xiàng)是分別為等長的多個(gè)符號(hào)表。這樣組織的最大優(yōu)點(diǎn)是每個(gè)符號(hào)表的屬性個(gè)數(shù)和結(jié)構(gòu)完全相同。則表項(xiàng)是等長的，并且表項(xiàng)中的每個(gè)屬性欄都是有效的，對(duì)于單個(gè)符號(hào)表示來說，這樣使得管理方便一致，空間效率高。但這樣組織的主要缺點(diǎn)是一個(gè)編譯程序?qū)⑼瑫r(shí)管理若干個(gè)符號(hào)表，增加了總體管理的工作量和復(fù)雜度。而且對(duì)各類符號(hào)共同屬性的管理必須設(shè)置重復(fù)的運(yùn)行機(jī)制。使得符號(hào)表的管理顯得臃腫。第二種：把所有語言中的符號(hào)都組織在一張符號(hào)表中。組成一張包括了所有屬性的龐大的符號(hào)表。這樣組織方式的最大優(yōu)點(diǎn)是總體管理非常集中單一，且不同種類符號(hào)的共同屬性可一致地管理和處理。這樣組織所帶來的缺點(diǎn)是，由于屬性的不同，為

35、完整表達(dá)各類符號(hào)的全部屬性必將出現(xiàn)不等長的表項(xiàng)，以及表項(xiàng)中屬性位置的交錯(cuò)重疊的復(fù)雜情況，這就極大地增加了符號(hào)表管理的復(fù)雜度。為使表項(xiàng)等長且實(shí)現(xiàn)屬性位置的唯一性，可以把所有符號(hào)的可能屬性作為符號(hào)表項(xiàng)屬性。這種組織方法可能有助于降低符號(hào)表管理復(fù)雜性，但對(duì)某個(gè)具體符號(hào)，可能增加了無用的屬性空間，從而增加了空間開銷。第三種：折衷方式是根據(jù)符號(hào)屬性相似程度分類組織成若干張表，每張表中記錄的符號(hào)都有比較多的相同屬性。這種折衷的組織方式在管理復(fù)雜性及時(shí)空效率方面都取得折衷的效果，并且對(duì)復(fù)雜性和效率的取舍可由設(shè)計(jì)者根據(jù)自己的經(jīng)驗(yàn)和要求及目標(biāo)系統(tǒng)的客觀環(huán)境和需求進(jìn)行選擇和調(diào)整。8-05.在整個(gè)編譯期間，對(duì)于符號(hào)

36、表的操作有哪些？答：在整個(gè)編譯期間，對(duì)于符號(hào)表的操作大致可歸納為五類： 對(duì)給定名字，查詢此名是否已在表中； 往表中填入一個(gè)新的名字； 對(duì)給定名字，訪問它的某些信息； 對(duì)給定名字，往表中填寫或更新它的某些信息； 刪除一個(gè)或一組無用的項(xiàng)。8-06.符號(hào)表的作用有哪些？答：在編譯程序中符號(hào)表用來存放語言程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息，這些信息集中反映了標(biāo)識(shí)符的語義特征屬性。起主要作用是：收集符號(hào)屬性；上下文語義的合法性檢查的依據(jù)；作為目標(biāo)代碼生成階段地址分配的依據(jù)。9-09.運(yùn)行時(shí)存儲(chǔ)器的劃分是怎樣的？答：運(yùn)行時(shí)存儲(chǔ)器的劃分如下圖所示。目標(biāo)代碼有效原則。使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時(shí)間較短,占用的存儲(chǔ)空間較小。(3)合算原則。應(yīng)盡可能以較低的代價(jià)取得較好的優(yōu)化效果。10-08,簡述常用的優(yōu)化技術(shù)有哪些？答：編譯程序中常用的優(yōu)化技術(shù)有：(1)刪除公共子表示式；(2)復(fù)寫傳播；(3)刪除無用代碼；(4)代碼外提；(5)強(qiáng)度削弱；(6)刪除歸納變量；(7)合并常量。10-09.設(shè)有基本塊：(1)a:=b-c(2)d:=a+4(3)e:=a-b(4)f:=a+4(5)b:=b+c(6)c:=b-f(7)b:=b