編譯原理復(fù)習(xí)題2017含試卷

1、編譯原理復(fù)習(xí)題一簡(jiǎn)答題：1) 什么是句子？ 什么是語(yǔ)言?*Þ解答：句子設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果S x（其中xVT*），則稱x是文法的一個(gè)句子。語(yǔ)言語(yǔ)言是句子的集合?；蛟O(shè)GS是給定文法，則由文法G所定義的語(yǔ)言L(G)可描述為：L(G)xSx,xVT* 。2) DFA與NFA有何區(qū)別 ? 解答:DFA與NFA的區(qū)別表現(xiàn)為兩個(gè)方面:一是NFA可以有若干個(gè)開(kāi)始狀態(tài)，而DFA僅只有一個(gè)開(kāi)始狀態(tài)。另一方面，DFA的映象M是從K×到K，而NFA的映象M是從K×到K的子集，即映象M將產(chǎn)生一個(gè)狀態(tài)集合（可能為空集），而不是單個(gè)狀態(tài)。3) 自頂向下的語(yǔ)法分析方法

2、的基本思想是什么?解答:從文法的開(kāi)始符號(hào)開(kāi)始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行直接推導(dǎo)，試圖推導(dǎo)出文法的句子，使之與給定的輸入串匹配。4) 自底向上的語(yǔ)法分析方法的基本思想是什么?解答:從給定的輸入串（終結(jié)符串）開(kāi)始，根據(jù)文法的規(guī)則一步一步的向上進(jìn)行直接歸約，試圖歸約到文法的開(kāi)始符號(hào)。5) 一個(gè)上下文無(wú)關(guān)文法G包括哪四個(gè)組成部分？解答:一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組產(chǎn)生式。6) 在自底向上的語(yǔ)法分析方法中，分析的關(guān)鍵是什么？解答:關(guān)鍵是尋找句柄。7) 在自頂向下的語(yǔ)法分析方法中，分析的關(guān)鍵是什么？解答:關(guān)鍵是選擇候選式。8）什么是屬性文法？答：是在上下

3、文無(wú)關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)(含終結(jié)符和非終結(jié)符)配備若干個(gè)屬性值，對(duì)文法的每個(gè)產(chǎn)生式都配備了一組屬性計(jì)算規(guī)則(稱為語(yǔ)義規(guī)則)。在語(yǔ)法分析過(guò)程中，完成語(yǔ)義規(guī)則所描述的動(dòng)作，從而實(shí)現(xiàn)語(yǔ)義處理。一個(gè)屬性文法形式的定義為一個(gè)三元組AG，AG=（G，V，E）。 其中G為一個(gè)上下文無(wú)關(guān)文法；V為屬性的有窮集；E為一組語(yǔ)義規(guī)則。9）語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯：定義翻譯所必須的語(yǔ)義屬性和語(yǔ)義規(guī)則，一般不涉及計(jì)算順序。語(yǔ)法制導(dǎo)翻譯(Syntax-Directed Translations)： 一個(gè)句子的語(yǔ)義翻譯過(guò)程與語(yǔ)法分析過(guò)程同時(shí)進(jìn)行。 在文法中，文法符號(hào)有明確的意義，文法符號(hào)之間有確定的語(yǔ)義關(guān)系。屬性

4、描述語(yǔ)義信息，語(yǔ)義規(guī)則描述屬性間的的關(guān)系，將語(yǔ)義規(guī)則與語(yǔ)法規(guī)則相結(jié)合，在語(yǔ)法分析的過(guò)程中計(jì)算語(yǔ)義屬性值。10）詞法分析的主要任務(wù)是什么？ 目標(biāo)代碼靜態(tài)數(shù)據(jù)棧âá堆解答:詞法分析器的任務(wù)是對(duì)構(gòu)成源程序的字符串從左到右逐個(gè)字符逐個(gè)字符地進(jìn)行掃描，依次把它們識(shí)別為一個(gè)一個(gè)具有獨(dú)立意義的單詞，并確定其屬性，再轉(zhuǎn)換為長(zhǎng)度統(tǒng)一的屬性字并輸出。 11)圖示運(yùn)行時(shí)存儲(chǔ)空間的劃分（分為哪幾個(gè)區(qū)）。 解答: 一般分為靜態(tài)區(qū)和動(dòng)態(tài)區(qū)： 程序代碼區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)12)常用的中間語(yǔ)言種類有哪幾種？解答: 常用的中間語(yǔ)言種類有逆波蘭表示、三元式、四元式和樹(shù)形表示。13）文法G所描述的語(yǔ)言是什

5、么的集合？解答:是由文法的開(kāi)始符號(hào)推出的所有終結(jié)符串的集合?；蛘f(shuō)是句子的集合。14）喬姆斯基把文法分為四種類型，即0型、1型、2型、3型。其中2型文法叫什么？解答: 2型文法叫上下文無(wú)關(guān)文法。15）常見(jiàn)的動(dòng)態(tài)存貯分配策略有哪兩種？解答:常見(jiàn)的兩種動(dòng)態(tài)存貯分配策略是棧式動(dòng)態(tài)分配策略和堆式動(dòng)態(tài)分配策略。16）語(yǔ)法分析的任務(wù)是什么？解答:語(yǔ)法分析的任務(wù)是識(shí)別給定的終結(jié)符串是否為給定文法的句子。17）局部?jī)?yōu)化是局限于一個(gè)什么范圍內(nèi)的一種優(yōu)化？解答: 是局限于一個(gè)基本塊范圍內(nèi)的一種優(yōu)化。18）通常一個(gè)編譯程序中應(yīng)包括哪七個(gè)部分？解答: 通常一個(gè)編譯程序中應(yīng)包含詞法分析，語(yǔ)法分析，語(yǔ)義分析與中間代碼生成，

6、代碼優(yōu)化，目標(biāo)代碼生成以及表格處理和出錯(cuò)處理等七個(gè)部分。19）代碼優(yōu)化的主要目標(biāo)是什么？解答: 代碼優(yōu)化的主要目標(biāo)是如何提高目標(biāo)程序的運(yùn)行速度和如何減少目標(biāo)程序運(yùn)行時(shí)所需的空間。20）.符號(hào)表的組織方式有哪幾種？答：一個(gè)編譯程序?qū)Ψ?hào)表的總體組織可有三種選擇：第一種： 把屬性種類完全相同的那些符號(hào)組織在一起，構(gòu)造出表項(xiàng)是分別為等長(zhǎng)的多個(gè)符號(hào)表。這樣組織的最大優(yōu)點(diǎn)是每個(gè)符號(hào)表的屬性個(gè)數(shù)和結(jié)構(gòu)完全相同。則表項(xiàng)是等長(zhǎng)的，并且表項(xiàng)中的每個(gè)屬性欄都是有效的，對(duì)于單個(gè)符號(hào)表示來(lái)說(shuō)，這樣使得管理方便一致，空間效率高。但這樣組織的主要缺點(diǎn)是一個(gè)編譯程序?qū)⑼瑫r(shí)管理若干個(gè)符號(hào)表，增加了總體管理的工作量和復(fù)雜度。而

7、且對(duì)各類符號(hào)共同屬性的管理必須設(shè)置重復(fù)的運(yùn)行機(jī)制。使得符號(hào)表的管理顯得臃腫。第二種： 把所有語(yǔ)言中的符號(hào)都組織在一張符號(hào)表中。組成一張包括了所有屬性的龐大的符號(hào)表。這樣組織方式的最大優(yōu)點(diǎn)是總體管理非常集中單一，且不同種類符號(hào)的共同屬性可一致地管理和處理。這樣組織所帶來(lái)的缺點(diǎn)是，由于屬性的不同，為完整表達(dá)各類符號(hào)的全部屬性必將出現(xiàn)不等長(zhǎng)的表項(xiàng)，以及表項(xiàng)中屬性位置的交錯(cuò)重疊的復(fù)雜情況，這就極大地增加了符號(hào)表管理的復(fù)雜度。為使表項(xiàng)等長(zhǎng)且實(shí)現(xiàn)屬性位置的唯一性，可以把所有符號(hào)的可能屬性作為符號(hào)表項(xiàng)屬性。這種組織方法可能有助于降低符號(hào)表管理復(fù)雜性，但對(duì)某個(gè)具體符號(hào)，可能增加了無(wú)用的屬性空間，從而增加了空間

8、開(kāi)銷。第三種：折衷方式是根據(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)整。21）. 在整個(gè)編譯期間，對(duì)于符號(hào)表的操作有哪些？答：在整個(gè)編譯期間，對(duì)于符號(hào)表的操作大致可歸納為五類：·對(duì)給定名字，查詢此名是否已在表中；·往表中填入一個(gè)新的名字；·對(duì)給定名字，訪問(wèn)它的某些信息；·對(duì)給定名字，往表中填寫(xiě)或更新它的某些信息；·刪除一個(gè)或一組無(wú)用的項(xiàng)。22）.符號(hào)表的作用

9、有哪些？答：在編譯程序中符號(hào)表用來(lái)存放語(yǔ)言程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息，這些信息集中反映了標(biāo)識(shí)符的語(yǔ)義特征屬性。起主要作用是： 收集符號(hào)屬性； 上下文語(yǔ)義的合法性檢查的依據(jù)； 作為目標(biāo)代碼生成階段地址分配的依據(jù)。23）. 簡(jiǎn)述優(yōu)化的原則是什么？ 答：編譯程序提供的對(duì)代碼優(yōu)化必須遵循的原則是：（1） 等價(jià)原則。經(jīng)過(guò)優(yōu)化后不應(yīng)改變程序運(yùn)行的結(jié)果。（2） 有效原則。使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時(shí)間較短，占用的存儲(chǔ)空間較小。（3） 合算原則。應(yīng)盡可能以較低的代價(jià)取得較好的優(yōu)化效果。24）簡(jiǎn)述常用的優(yōu)化技術(shù)有哪些？答：編譯程序中常用的優(yōu)化技術(shù)有：刪除公共子表示式；復(fù)寫(xiě)傳播；刪除無(wú)用代碼；代碼外提；強(qiáng)

10、度削弱；刪除歸納變量；合并常量。25）.何謂優(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)化。26)、編譯程序目標(biāo)代碼運(yùn)行時(shí)的存儲(chǔ)區(qū)通常被劃分為幾部分？答： 目標(biāo)代碼區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)、堆區(qū)。27)、數(shù)組的內(nèi)情向量包含哪些內(nèi)容？在編譯程序?qū)?shù)組說(shuō)明進(jìn)行語(yǔ)義處理時(shí)，須把數(shù)組的類型type、維數(shù)n、各維的上、下界lk,uk等有關(guān)信息記錄下來(lái)。此外,如果數(shù)組是常界的,還可將各維的界差dk以及計(jì)算數(shù)組元素地址的常量C記錄下來(lái)。為了便于引用，通常是把上述信息存放于數(shù)組相應(yīng)的“內(nèi)情向量”之

11、中.對(duì)數(shù)組內(nèi)情向量的訪問(wèn),可通過(guò)數(shù)組在符號(hào)表中相應(yīng)登記項(xiàng)的ADDR域以間接尋址方式進(jìn)行（即將其ADDR域作為指針用于存放內(nèi)情向量的首地址）。28)、文法分為幾種類型？其分類依據(jù)是什么？答：分為四類：短語(yǔ)文法（0型文法）、前后文有關(guān)文法（1型文法）、前后文無(wú)關(guān)文法（2型文法）、正規(guī)文法（3型文法）。分類依據(jù)：對(duì)產(chǎn)生式家約束。29)、一般來(lái)說(shuō)編譯程序至少包含哪幾部分？各部分的作用是什么？答：詞法分析，語(yǔ)法分析，語(yǔ)義分析和目標(biāo)代碼生成是必須的，代碼優(yōu)化是為了提高目標(biāo)代碼的質(zhì)量而引入的，不是必須的，沒(méi)有代碼優(yōu)化編譯程序同樣生成目標(biāo)代碼。各部分的作用參見(jiàn)教材30）、分程序結(jié)構(gòu)的棧式存儲(chǔ)管理中的活動(dòng)記錄包

12、括哪些內(nèi)容？答：臨時(shí)工作單元、局部變量、保存機(jī)器狀態(tài)、存取鏈、控制鏈、實(shí)參，也稱形式單元、返回地址，保存該被調(diào)過(guò)程返回后的地址。31）、有人認(rèn)為編譯程序的五個(gè)組成部分缺一不可，這種看法正確嗎？為什么？答：不正確 詞法分析，語(yǔ)法分析，語(yǔ)義分析和目標(biāo)代碼生成是必須的，代碼優(yōu)化是為了提高目標(biāo)代碼的質(zhì)量而引入的，不是必須的，沒(méi)有代碼優(yōu)化編譯程序同樣生成目標(biāo)代碼。二、 應(yīng)用題1） 寫(xiě)一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以0開(kāi)頭。 解：文法G(N)： NAB|B AAC|D B1|3|5|7|9 DB|2|4|6|8 C0|D2）寫(xiě)一個(gè)文法，使其語(yǔ)言是無(wú)符號(hào)二進(jìn)制實(shí)數(shù)（不含指數(shù)）。解答:文法

13、G(N)： NL.L|L LLB|B B0|13）給出上下文無(wú)關(guān)文法的定義。一個(gè)上下文無(wú)關(guān)文法G是一個(gè)四元式(VT，VN，S，P)，其中： VT是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號(hào)； VN是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號(hào)，VTVN=； S是一個(gè)非終結(jié)符號(hào)，稱為開(kāi)始符號(hào)； P是一個(gè)產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式的形式是P，其中，PVN，(VTVN)*。開(kāi)始符號(hào)S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。4）給出正規(guī)式與正規(guī)集的遞歸定義。(1)和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和；(2)任何a，a是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為a；(3)假定U和V都是上的正規(guī)式，它們所表示

14、的正規(guī)集分別記為L(zhǎng)(U)和L(V)，那么，(U|V)、(U·V)和(U)*也都是正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(U)L(V)、L(U)L(V)(連接積)和(L(U)*(閉包)。僅由有限次使用上述三步驟而得到的表達(dá)式才是上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。5）設(shè)文法G為： SaAcB|BdS ABaB|aBc|a BaScA|cAB|b 對(duì)于輸入串a(chǎn)acabccb，給出最左推導(dǎo)。答： S=>aAcB=>aaBccB=>aacABccB=>aacaBccB=>aacabccB=>aacabccb6） 設(shè)文法G為： SBA ABS|

15、d BaA|bS|c 對(duì)于輸入串a(chǎn)dccd，給出最左推導(dǎo)。答： S=>BA=>aAA=>adA=>adBS=>adcS=>adcBA=>adccA=>adccdSFDAabab7）給定正規(guī)文法G: SaS|bA|b AaS請(qǐng)構(gòu)造與之等價(jià)的有限自動(dòng)機(jī)。8）給定正規(guī)文法G: SaA AbA|aB|b BaAABDFbbaaSa請(qǐng)構(gòu)造與之等價(jià)的有限自動(dòng)機(jī)。24D3abaa1ba9）對(duì)下面給出的NFA確定化。SFDAababa10）.將文法GS 改寫(xiě)為等價(jià)的GS，使GS不含左遞歸和左公共因子。GS： SbSAe | bA AAb | d答：文法GS 改寫(xiě)

16、為等價(jià)的不含左遞歸和左公共因子的G'S為：SbB BSAe | AAd A' A' bA' | 11） 消除下列文法GA的左遞歸。AAaBBBBbCCCeDDD(A)d解答：消除文法GA的左遞歸后得到：A BA AaBAB CBBbcBCeDDD(A)d12） 正規(guī)式（a|b）*a(a|b) 構(gòu)造一個(gè)等價(jià)的有限自動(dòng)機(jī)。a,baabÞ012解答：13）將下圖的NFA確定化為DFA。答：用子集法確定化如下表IIaIb狀態(tài)X,1,21,2.1,2,31,2,Y1,2.1,2.1,2,Y1,2.1,2,31,2,31,2,31,2,3X123確定化后如下圖：1

17、4）. 已知文法 G(E)E T|ETTF|T *FF (E)|i(1)給出句型(T *Fi)的最右推導(dǎo)；(2)給出句型(T *Fi)的短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄、素短語(yǔ)、最左素短語(yǔ)。解： (1) 最右推導(dǎo)：E ->T->F->(E)->(E T)->(E F)->(E i)->(Ti)->(T*Fi)(2) 短語(yǔ)：(T*Fi) ，T*Fi ，T*F，i簡(jiǎn)單短語(yǔ)：T*F,i句柄：T*F素短語(yǔ)：T*F,i最左素短語(yǔ)：T*F15）. 構(gòu)造正規(guī)式 1(0|1)*101 相應(yīng)的 DFA 。解：先構(gòu)造 NFA ：確定化：重新命名，令 AB 為 B、AC 為 C、

18、ABY 為 D 得：所以，可得 DFA 為：16）. 文法：S->MH|a H ->LSo| K ->dML| L ->eHfM->K|bLM判斷 G 是否為 LL(1) 文法，如果是，構(gòu)造 LL(1) 分析表。 解：各符號(hào)的 FIRST 集和 FOLLOW集為： 預(yù)測(cè)分析表由于預(yù)測(cè)分析表中無(wú)多重入口，所以可判定文法是 LL(1)的17）. 對(duì)下面的文法 G ：E ->TE'E'->+E| T ->FT'T' ->T| F-> PF'F'-> *F'| P->(E)|

19、a|b|(1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的 FIRST 集和 FOLLOW 集。 (4 分)(2)證明這個(gè)方法是 LL(1) 的。(4 分) (3)構(gòu)造它的預(yù)測(cè)分析表。(2 分) 解：（1）計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的 FIRST 集和 FOLLOW集。FIRST 集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(E')=+, FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(T')=FIRST(T)U=(,a,b, ;FIRST(F)=FIRST(P)=(,a,b,;FIRST(F'

20、)=FIRST(P)=*, ;FIRST(P)=(,a,b,;FOLLOW 集合有：FOLLOW(E)=),#;FOLLOW(E')=FOLLOW(E)=),#; FOLLOW(T)=FIRST(E')UFOLLOW(E)=+,),#;/不包含F(xiàn)OLLOW(T')=FOLLOW(T)=FIRST(E')UFOLLOW(E)=+,),#; FOLLOW(F)=FIRST(T')UFOLLOW(T)=(,a,b,+,),#;/不包含F(xiàn)OLLOW(F')=FOLLOW(F)=FIRST(T')UFOLLOW(T)=(,a,b,+,),#; FO

21、LLOW(P)=FIRST(F')UFOLLOW(F)=*,(,a,b,+,),#;/不包含(2)證明這個(gè)方法是 LL(1)的。各產(chǎn)生式的 SELECT 集合有：E->TE'： FIRST(T)=(,a,b,;E'->+E: FIRST(+E ) =+;E'->: FOLLOW(E')=),#T->FT': FIRST(F)=(,a,b,;T'->T: FIRST(T)=(,a,b,;T'->: FOLLOW(T/)=+,),#;F->PF': FIRST(P)=(,a,b,;F&

22、#39;->*F': FIRST(*F)=*;F'-> : FOLLOW(F')=(,a,b,+,),#;P->(E) FIRST(E) =(P->a FIRST(a )=aP->b FIRST(b)=bP-> FIRST()=可見(jiàn)，相同左部產(chǎn)生式 若不能推出為空，其產(chǎn)生式右部的交集均為空，相同左部產(chǎn)生式，若其中有一個(gè)能推出為空，其不能推出為空的產(chǎn)生式右部FIRST集合和左部的FOLLOW交集均為空，所以文法 GE是 LL(1)文法。(3)構(gòu)造它的預(yù)測(cè)分析表。 文法 GE的預(yù)測(cè)分析表如下：18）設(shè)有文法G: SS*F|F FFP|P

23、P(S)|i 完成下列算符優(yōu)先關(guān)系表，并判斷是否為算符優(yōu)先文法（請(qǐng)說(shuō)明理由）。*()i#*············(····)····i····#····由于該文法的任何產(chǎn)生的右部都不含兩個(gè)相繼的非終結(jié)符，故屬于算符文法。從上表可以看出，任何兩個(gè)終結(jié)符之間至少滿足、· 、·三種關(guān)系之一，故G為算符優(yōu)

24、先文法。 給出句型S*P(S)對(duì)應(yīng)的語(yǔ)法樹(shù)，指出該句型的短語(yǔ)、句柄SSF*FP()SP短語(yǔ)：S*P(S) P(S) P (S)句柄: P19） 已知文法G(S) ST | S-T TF | T / F F(S) | i （1）給出句型 T/ F-i 的最右推導(dǎo)；（2）畫(huà)出句型 T/F-i 規(guī)范規(guī)約的語(yǔ)法樹(shù)及算符優(yōu)先分析規(guī)約的語(yǔ)法樹(shù)框架；（3）給出句型 T / F-i 的短語(yǔ)、素短語(yǔ)。答：(1) 最右推導(dǎo)：ETF(E) (ET) (EF) (Ei) (Ti) (T*Fi) (2) 略(3) 短語(yǔ)：(T*Fi)，T*Fi，T*F，i 素短語(yǔ)：T*F, i 20) 某語(yǔ)言的拓廣文法G為：(0) SS

25、(1) S Db|B(2) D d|(3) B Ba|證明G不是LR(0)文法而是SLR(1)文法，請(qǐng)給出SLR(1)分析表。答：拓廣文法G'，增加產(chǎn)生式S'S在項(xiàng)目集I0中：有移進(jìn)項(xiàng)目D ·d 歸約項(xiàng)目D ·和B ·存在移進(jìn)-歸約和歸約-歸約沖突，所以G不是LR(0)文法。若產(chǎn)生式排序?yàn)椋?0) S'S(1) S Db(2) S B(3) D d(4) D (5) B Ba(6) B G的LR(0)項(xiàng)目集族及識(shí)別活前綴的DFA如下圖：由產(chǎn)生式知Follow(S)=# Follow(D)= bFollow(B)= a ,#在I0中:Foll

26、ow(D) d= b d=Follow(B) d= a ,# d=Follow(D) Follow(B)= ba ,# =在I3中:Follow(S) a=#a=所以在I0，I3中的移進(jìn)-歸約和歸約-歸約沖突可以由Follow集解決,所以G是SLR(1)文法, 構(gòu)造的SLR(1)分析表如下表：狀態(tài)ACTIONGOTObda#SDB0r4S4r6r61231   acc   2S5      3  S6r2   4r3 

27、;     5   r1   6  r5r5   21)、下面文法G 為:（0）E® E（1）E® r B （2）B® B ; d（3）B® d判斷G 是SLR(1)還是LR(1)，說(shuō)明理由，并構(gòu)造相應(yīng)的分析表 I0:E EE rBI2: E rBB B;dB dI3: E rB B B ;dI4: B d I5: B B;dI1: E E I6: B B;d ÞErdB;d狀態(tài)I3中含

28、項(xiàng)目： ErB· 為歸約項(xiàng)目 BB· i為移進(jìn)項(xiàng)目所以 不是LR(0)文法FOLLOW(S)=# FOLLOW(S):為空，所以該文法是SLR(1)文法。狀態(tài)ACTIONGOTOr;d#EB0S211acc2S433S5r14r3r35S66r2r222)、設(shè)文法G(S)： S(F) |d S |d FF ; S | S (1) 消除左遞歸和回溯； (2) 列出第一小題完成后的文法，并計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW； (3) 構(gòu)造預(yù)測(cè)分析表。解： (1) S(F) SdS SS S 2分 FSF F ，S F F 2分評(píng)分細(xì)則：消除左遞歸2分，提公共因子2分。

29、(2) FIRST(S)(，d FOLLOW(S) # , ，, ) FIRST(S)d , FOLLOW(S) # , ，, ) FIRST(L)(，d FOLLOW(L) ) FIRST(L)，, FOLLOW(L ) 3分因?yàn)椋?FIRST (S(F)FIRST (SdS)=FIRST (SS)FOLLOW (S )=FIRST (F ，S F)FIRST (F )=所以，此文法是LL(1)文法 (4) 預(yù)測(cè)分析表 d，()#SdS(F)SS S FSFSFF，S F23）. 設(shè)有基本塊：(1) a:=b-c (6) c:=b-f(2) d:=a+4 (7) b:=b-c(3) e:=a

30、-b (8) f:=b+f(4) f:=a+4 (9) a:=a-f(5) b:=b+c (1) 畫(huà)出DAG圖；(2) 假設(shè)基本塊出口時(shí)只有a，b還被引用，請(qǐng)寫(xiě)出優(yōu)化后的三地址代碼序列。解答：(1)給出DAG如右：(2)重寫(xiě)三地址代碼如下： a:=b-cd:=a+4 e:=a-bf:=db:=b+c c:=b-fb:=b-cf:=b+fa:=a-f24）.設(shè)有基本塊 T1：2T2：10/T1T3：SRT4：SRA：T2 * T4B：AT5：SRT6：T3 * T5B：T6(1) 畫(huà)出DAG圖；(2) 假設(shè)基本塊出口時(shí)只有A，B還被引用，請(qǐng)寫(xiě)出優(yōu)化后的三地址代碼序列。解：(1)DAG：見(jiàn)右圖 (

31、2) 優(yōu)化后的四元式 T3：SR T4：SR A：5*T4 B：T3T425） 將下面的條件語(yǔ)句表示成四元式序列： if a>b then x:=a+b*c else x:=b-a;答：(1) ( j>, a, b, (3) (2) ( j, , , (7) ) (3) ( *, b, c, T1) (4) ( +, a, T1, T2) (5) ( :=, T2, , x) (6) ( j, , , (9) (7) ( -, b, a, T3) (8) ( :=, T3, , x) (9) ( )26） 翻譯成四元式序列。Whilea0 b0do Begin X：X1； if a

32、0 then a：a1 else b：b1 End； 答：(1) (j，a，0，5) (2) (j，3) (5) (，×，1，T1) (6) (：，T1，×) (7) (j，a，0，9) (8) (j，12)(9) (，a，1，T2) (10) (：，T2，a) (11) (j，1) (12) (，b，1， T3) (13) (：，T3，b) (14) (j，1) (15)27） 設(shè)有基本塊： t1:=3*At2:=2*Ct3:=t1+t2t4:=t3+5t5:=2*Ct6:=3*At7:=t6+t5E:=t7-1F:=t4-Ea)畫(huà)出DAG圖；b)假設(shè)基本塊出口時(shí)只有E，

33、F還被引用，請(qǐng)寫(xiě)出優(yōu)化后的三地址代碼序列。解答：5+*+*t4t1,t62A3n11n2n3n5n6n8En7F1n4t2,t5t3,t7n9Cn10n11n12a)構(gòu)造DAG：見(jiàn)右圖。b)優(yōu)化后的三地址代碼序列為：t1:=3*At2:=2*Ct3:=t1+t2t4:=t3+5E:=t3-1F:=t4-E五、填空題:1.編譯程序的工作過(guò)程一般可以劃分為 詞法分析,語(yǔ)法分析,語(yǔ)義分析，之間代碼生成,代碼優(yōu)化 等幾個(gè)基本階段,同時(shí)還會(huì)伴有 表格處理 和 出錯(cuò)處理 .2.若源程序是用高級(jí)語(yǔ)言編寫(xiě)的,目標(biāo)程序是 機(jī)器語(yǔ)言程序或匯編程序 ,則其翻譯程序稱為編譯程序.3.對(duì)編譯程序而言,輸入數(shù)據(jù)是 源程序

34、 ,輸出結(jié)果是 目標(biāo)程序 .4.一個(gè)典型的編譯程序中，不僅包括詞法分析、語(yǔ)法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。其中，詞法分析器用于識(shí)別 單詞 。5.所謂最右推導(dǎo)是指： 任何一步Þ都是對(duì)中最右非終結(jié)符進(jìn)行替換的 。6.一個(gè)上下文無(wú)關(guān)文法所含四個(gè)組成部分是 一組終結(jié)符號(hào)、一組非終結(jié)符號(hào)、一個(gè)開(kāi)始符號(hào)、一組產(chǎn)生式 。7.產(chǎn)生式是用于定義 語(yǔ)法成分 的一種書(shū)寫(xiě)規(guī)則。8.設(shè)GS是給定文法，則由文法G所定義的語(yǔ)言L(G)可描述為： L(G)xSx,xVT* 。9.設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果Sx（其中xV*），則稱x是文法的一個(gè)句

35、型 。10.設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果Sx(其中xVT*),則稱x是文法的一個(gè)句子。11.語(yǔ)法分析最常用的兩類方法是 自上而下 和 自下而上 分析法。12.語(yǔ)法分析的任務(wù)是識(shí)別給定的終極符串是否為給定文法的句子。13.自頂向下的語(yǔ)法分析方法的關(guān)鍵是 如何選擇候選式 的問(wèn)題。14.自頂向下的語(yǔ)法分析方法的基本思想是：從文法的 開(kāi)始符號(hào) 開(kāi)始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行直接推導(dǎo)，試圖推導(dǎo)出文法的 句子 ，使之與給定的輸入串匹配。15.自底向上的語(yǔ)法分析方法的基本思想是：從給定的終極符串開(kāi)始，根據(jù)文法的規(guī)則一步一步的向上進(jìn)行直接歸約，試圖歸約到文法的 開(kāi)

36、始符號(hào) 。16.自底向上的語(yǔ)法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行 直接歸約 ，力求 歸約 到文法的 開(kāi)始符號(hào) 。17.在LR（0）分析法的名稱中，L的含義是 自左向右的掃描輸入串 ，R的含義是 最左歸約 ，0 的含義是 向貌似句柄的符號(hào)串后查看0個(gè)輸入符號(hào) 。18.在SLR（1）分析法的名稱中，S的含義是 簡(jiǎn)單的 。19.所謂屬性文法是 一個(gè)屬性文法是一個(gè)三元組：A（G，V，F(xiàn)），一個(gè)上下文無(wú)關(guān)文法G；一個(gè)屬性的有窮集V和關(guān)于屬性的斷言或謂詞的有窮集F。每個(gè)斷言與文法的某產(chǎn)生式相聯(lián)。 19.綜合屬性是用于 “自下而上”傳遞信息。20.繼承屬性是用于 “自上而

37、下”傳遞信息。21.符號(hào)表中的信息欄中登記了每個(gè)名字的 屬性和特征等有關(guān)信息 ，如類型、種屬、所占單元大小、地址等等。22.常用的兩種動(dòng)態(tài)存貯分配辦法是 棧式 動(dòng)態(tài)分配和 堆式 動(dòng)態(tài)分配。23.局部?jī)?yōu)化是局限于一個(gè) 基本塊 范圍內(nèi)的一種優(yōu)化。24.代碼優(yōu)化的主要目標(biāo)是如何提高 目標(biāo)程序的運(yùn)行速度 和如何減少 目標(biāo)程序運(yùn)行時(shí)所需的空間 。編譯原理期末考試試卷（A卷）一、簡(jiǎn)述編譯程序的工作過(guò)程。（10） 編譯程序的工作過(guò)程，是指從輸入源程序開(kāi)始到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)過(guò)程，是非常復(fù)雜的，就其過(guò)程而言，一般可以劃分為五個(gè)工作階段：詞法分析，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)的單詞；語(yǔ)法

38、分析，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)串分解成各類語(yǔ)法單位；語(yǔ)義分析與中間代碼產(chǎn)生，即對(duì)各類語(yǔ)法單位，分析其漢一并進(jìn)行初步翻譯；代碼優(yōu)化，以期產(chǎn)生更高效的代碼；目標(biāo)代碼生成，把中間代碼變換成特定機(jī)器上的低級(jí)語(yǔ)言指令形式。二、給出下面的正規(guī)表達(dá)式（15）（1） 以01結(jié)尾的二進(jìn)制數(shù)串；（2） 能被5整除的十進(jìn)制整數(shù)；（3） 包含偶數(shù)個(gè)1或偶數(shù)個(gè)0的二進(jìn)制數(shù)串。（1）（0|1）*01（2）digit=0|1|2|3|4|5|6|7|8|9digit*（0|5）（3）（0*10*1）*0*）|（1*01*0）*1*）三、對(duì)下面的文法G： Sa | b | （T）TT，S | S(1) 消去文法的左遞歸

39、，得到等價(jià)的文法G2；(2) 判斷文法G2是否LL（1）文法，如果是，給出其預(yù)測(cè)分析表。（15） G2： Sa | b | （T） T ST T，S T | G2是LL（1）文法。ab（），#SSa Sb S（T）TT STT STT STTT T，S T 四、對(duì)下面的文法G： SABAA00 | 0BB11 | 1 (1) 消去文法的左遞歸，得到等價(jià)的文法G2；(2) 判斷文法G2是否LL（1）文法，如果是，給出其預(yù)測(cè)分析表。（15）G： SAB A0A A00A | B1B B11B |文法GS是LL(1)文法。預(yù)測(cè)分析表：01#SSABAA0AAA00AABB1BBB11B B五、設(shè)有文

40、法GA：ABCc | gDBBbCDE |CDaB | caDdD |EgAf | c(1) 計(jì)算該文法的每一個(gè)非終結(jié)符的FIRST集和FOLLOW集；(2) 試判斷該文法是否為L(zhǎng)L（1）文法。（15）FIRSTFOLLOWABCDEA,b,c,d,gbA,c,dDC,gA,c,dC,d,gA,b,c,g（2） 是LL（1）文法。編譯原理期末考試試卷（B卷）三、應(yīng)用題（1、4、5每題10分，2、3每題15分，共60分）1、為正規(guī)式(a|b)*a(a|b)構(gòu)造等價(jià)且狀態(tài)最少的確定有限自動(dòng)機(jī)。（要求給出主要步驟）2、有文法如下： S BAA BS | dB aA | bS | c(1). 計(jì)算文法的每個(gè)非終結(jié)符的FIRST和FOLLOW集合；(2). 判斷文法是否LL（1）文法，如果是，給出其預(yù)測(cè)分析表，否則說(shuō)明理由。4、有文法如下：T T*F | F F P­F | PP (T) | i 證明T*i­P是該文法的一個(gè)句型，但不是規(guī)范句型；指出T*i­P的所有短語(yǔ)、直接短語(yǔ)、素短語(yǔ)、句柄。三、應(yīng)用題（1、4、5每題10分，2、3每題15分，共60分）1、對(duì)于符號(hào)串T*i