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

1、編譯原理復(fù)習(xí)題一.簡答題：1） 什么是句子？什么是語言？.*解答：句子一一設(shè) G 是一個給定的文法，S 是文法的開始符號，如果 S*x（其中 xCW）,則稱 x 是文法的一個句子。語言一一語言是句子的集合?；蛞灰辉O(shè) GS是給定文法，則由文法 G 所定義的語言 L（G）可描述為：L（G）=x一*4Sx,xeVT。2） DFA 與 NFA 有何區(qū)別？解答:DFA 與 NFA 的區(qū)別表現(xiàn)為兩個方面：一是 NFA 可以有若干個開始狀態(tài)，而 DFA 僅只有一個開始狀態(tài)。另一方面，DFA 的映象 M 是從 KX 匯到 K,而 NFA 的映象 M 是從 KX 匯到 K 的子集，即映象 M 將產(chǎn)生一個狀態(tài)集合

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

3、答：關(guān)鍵是選擇候選式。8）什么是屬性文法？答：是在上下文無關(guān)文法的基礎(chǔ)上，為每個文法符號（含終結(jié)符和非終結(jié)符）配備若干個屬性值，對文法的每個產(chǎn)生式都配備了一組屬性計算規(guī)則（稱為語義規(guī)則）。在語法分析過程中，完成語義規(guī)則所描述的動作，從而實(shí)現(xiàn)語義處理。一個屬性文法形式的定義為一個三元組 AGAG=（G,V,E）。其中 G 為一個上下文無關(guān)文法；V 為屬性的有窮集；E 為一組語義規(guī)則。9）語法制導(dǎo)翻譯語法制導(dǎo)翻譯：定義翻譯所必須的語義屬性和語義規(guī)則，一般不涉及計算順序。語法制導(dǎo)翻譯（Syntax-DirectedTranslations）:-一個句子的語義翻譯過程與語法分析過程同時進(jìn)行。在文法中，

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

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

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

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

8、而增加了空間開銷。第三種：折衷方式是根據(jù)符號屬性相似程度分類組織成若干張表，每張表中記錄的符號都有比較多的相同屬性。這種折衷的組織方式在管理復(fù)雜性及時空效率方面都取得折衷的效果，并且對復(fù)雜性和效率的取舍可由設(shè)計者根據(jù)自己的經(jīng)驗(yàn)和要求及目標(biāo)系統(tǒng)的客觀環(huán)境和需求進(jìn)行選擇和調(diào)整。21） .在整個編譯期間，對于符號表的操作有哪些？答：在整個編譯期間，對于符號表的操作大致可歸納為五類： 對給定名字，查詢此名是否已在表中； 往表中填入一個新的名字； 對給定名字，訪問它的某些信息； 對給定名字，往表中填寫或更新它的某些信息； 刪除一個或一組無用的項(xiàng)。22） .符號表的作用有哪些？答：在編譯程序中符號表用來存

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

10、優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？答：優(yōu)化：對程序進(jìn)行各種等價變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。26）、編譯程序目標(biāo)代碼運(yùn)行時的存儲區(qū)通常被劃分為幾部分？答：目標(biāo)代碼區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)、堆區(qū)。27）、數(shù)組的內(nèi)情向量包含哪些內(nèi)容？在編譯程序?qū)?shù)組說明進(jìn)行語義處理時，須把數(shù)組的類型 type、維數(shù) n、各維的上、下界lk,uk等有關(guān)信息記錄下來。此外，如果數(shù)組是常界的，還可將各維的界差dk以及計算數(shù)組元素地址的常量 C 記錄下來。為了便于引用，通常是把上述信息存放于數(shù)組相應(yīng)的“內(nèi)情向量”之中.對數(shù)組內(nèi)情向量的訪問，可通過數(shù)組在符

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

12、局部變量、保存機(jī)器狀態(tài)、存取鏈、控制鏈、實(shí)參，也稱形式單元、返回地址，保存該被調(diào)過程返回后的地址。31)、有人認(rèn)為編譯程序的五個組成部分缺一不可，這種看法正確嗎？為什么？答：不正確詞法分析，語法分析，語義分析和目標(biāo)代碼生成是必須的，代碼優(yōu)化是為了提高目標(biāo)代碼的質(zhì)量而引入的，不是必須的，沒有代碼優(yōu)化編譯程序同樣生成目標(biāo)代碼。二、應(yīng)用題1)寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以 0 開頭。解：文法 G(N):NRAB|BZAC|DB-1|3|5|7|9AB|2|4|6|8g0|D2)寫一個文法，使其語言是無符號二進(jìn)制實(shí)數(shù)(不含指數(shù))。解答：文法 G(N):NRL.L|LLfLB|BB-0|1

13、3)給出上下文無關(guān)文法的定義。一個上下文無關(guān)文法 G 是一個四元式(VT,VN,S,P),其中：VT是一個非空有限集，它的每個元素稱為終結(jié)符號；VN是一個非空有限集，它的每個元素稱為非終結(jié)符號，VTUX=；S 是一個非終結(jié)符號，稱為開始符號；P 是一個廣生式集合(有限)，每個廣生式的形式是 Pf”，其中，PCVN,aC(VTUVN)。開始符號 S 至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。4).給出正規(guī)式與正規(guī)集的遞歸定義。(1) e 和都是匯上的正規(guī)式，它們所表示的正規(guī)集分別為和；(2)任彳 sjaE,a 是匯上的一個正規(guī)式，它所表示的正規(guī)集為a;(3)假定 U 和 V 都是匯上的正規(guī)式，它們所表

14、示的正規(guī)集分別記為 L(U)和 L(V)，那么，(U|V)、(UV)和(U)*也都是正規(guī)式，它們所表示的正規(guī)集分別為 L(U)UL(V)、L(U)L(V)(連接積)和(L(U)*(閉包)。僅由有限次使用上述三步驟而得到的表達(dá)式才是匯上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是匯上的正規(guī)集。5).設(shè)文法 G 為:SfaAcB|BdSA 一 BaB|aBc|aB 一 aScA|cAB|b對于輸入串 aacabccb,給出最左推導(dǎo)。答：S=aAcB=aaBccB=aacABccB=aacaBccB=aacabccB=aacabccb6)設(shè)文法 G 為:S 一 BAAfBS|dBfaA|bS|c對于輸入

15、串 adccd,給出最左推導(dǎo)。答：S=BA=aAA=adA=adBS=adcS=adcBA=adccA=adccd7).給定正規(guī)文法 G:SfaS|bA|bA 一 aS請構(gòu)造與之等價的有限自動機(jī)。8).給定正規(guī)文法 G:S 一 aAAfbA|aB|bB一 aA9).對下面給出的 NFA 確定化。10).將文法 GS改寫為等價的GS,使GS不含左遞歸和左公共因子。GS:SfbSAe|bAZAb|d答：文法 GS改寫為等價的不含左遞歸和左公共因子的 GS為：SfbBBfSAe|AZdAA一 bA|11)消除下列文法 GA的左遞歸。ZAaBIBBfBbCICC-eDIDA(A)Id解答：消除文法 G

16、A的左遞歸后得到：A 一 BA，A/一 aBA，IB 一 CB，B-bcB，ICfeDIDA(A)Id12)正規(guī)式(a|b)*a(a|b)構(gòu)造一個等價的有限自動機(jī)。13）將下圖的 NFA 確定化為 DFA答：用子集法確定化如下表IIaIb狀態(tài)X,1,2)1,2.1,2,3X1,2.1,2.1,2,311,2,31,2,Y1,2,321,2,Y1,2.1,2,33確定化后如下圖:解答:14).已知文法 G(E)E 一 T|E+TT-F|T*FF 一(E)|i(1)給出句型(T*F+i)的最右推導(dǎo)；(2)給出句型(T*F+i)的短語、簡單短語、句柄、素短語、最左素短語。解：(1)最右推導(dǎo)：E-T-

17、F-(E)-(E+T)-(E+F)-(E+i)-(T+i)-(T*F+i)(2)短語：(T*F+i),T*F+i,T*F,i簡單短語：T*F,i句柄：T*F素短語：T*F,i最左素短語：T*F15).構(gòu)造正規(guī)式 1(0|1)*101 相應(yīng)的 DFA。解：先構(gòu)造 NFA:01XAAAABABACABACAABYABYACAB所以，可得 DFA 為:16).文法：S-MH|aH-LSo|K-dML|L-eHfM-K|bLM判斷 G 是否為 LL(1)文法，如果是，構(gòu)造 LL(1)分析表。解：各符號的FIRSTFOLLOWS彳曲廠用怖 6MMs-Jb)住斷!H匕聞便 3:L制寓 g 眄料K(黨松確定

18、化:Q1XAAABBCBCADDCBAB 為 B、AC 為 C、ABY 為 D 得:重新命名，令FIRST 集和 FOLLO 碌為:ai;$,3 心-AH局莊-射隰涔籃酶fa:bLM郤Hp前K由j預(yù)測分析君1翻口無多重,入口， 所以塞以可判兄k?去是,LL-(1)的17).對下面的文法 GE-TEE-+E|工T-FTT-T|工F-PFF-*F|P-(E)|a|b|A(1)計算這個文法的每個非終結(jié)符的 FIRST 集和 FOLLOW 集。(4 分)(2)證明這個方法是 LL(1)的。(4 分)(3)構(gòu)造它的預(yù)測分析表。(2 分)解：(1)計算這個文法的每個非終結(jié)符的 FIRST 集和 FOLLO

19、WSFIRST 集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,A;FIRST(E)=+,FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,A;FIRST(T)=FIRST(T)U_=(,a,b,A,;FIRST(F)=FIRST(P)=(,a,b,A;FIRST(F)=FIRST(P)=*,;FIRST(P)=(,a,b,A;FOLLOW合有：FOLLOW(E)=),#;FOLLOW(E)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E)UFPLLOW(E)=+,),#;/不包含 sFOLLOW(T)=FOLLOW(

20、T)=FIRST(E)UFOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T)UFOLLOW(T)=(,a,b,A,+,),#;/不包含 sFOLLOW(F)=FOLLOW(F)=FIRST(T)UFOLLOW(T)=(,a,b,A,+,),#;FOLLOW(P)=FIRST(F)UFOLLOW(F)=*,(,a,b,A,+,),#;/不包含(2)證明這個方法是 LL(1)的。各產(chǎn)生式的 SELECT 集合有：E-TE:FIRST(T)=(,a,b,A;E-+E:FIRST(+E)=+;E-之：FOLLOW(E)=),#T-FT:FIRST(F)=(,a,b,A;T-T:FIRS

21、T(T)=(,a,b,A;T-:FOLLOW(T/)=+,),#;F-PF:FIRST(P)=(,a,b,A;F-*F:FIRST(*F)=*;F-旦：FOLLOW(F)=(,a,b,A,+,),#;P-(E)FIRST(E)=(P-aFIRST(a)=aP-bFIRST(b)=bP-AFIRST(A)=A可見，相同左部產(chǎn)生式若不能推出為空，其產(chǎn)生式右部的交集均為空，相同左部產(chǎn)生式，若其中有一個能推出為空，其不能推出為空的產(chǎn)生式右部 FIRST 集合和左部的 FOLLOW!集均為空，所以文法 GE是 LL(1)文法。+*()abAETIE-1,TTE-TE今+E-今sTFTTF丁TFTTFT丁

22、Te嶺T-TTTriT法G:TFFTPF-c.TeTTtT1Te一7sPF|FTOE)-b(3)構(gòu)造它的預(yù)測分析表。文法 GE的預(yù)測分析表如下：18).設(shè)有文SF 一 FTP|PP 一(S)|i完成下列算符優(yōu)先關(guān)系表，并判斷是否為算符優(yōu)先文法(請說明理由)。*T()i#*,v-v-,v-,v-v-(v-v-v-=v-),i,#v-v-v-v-=由于該文法的任何產(chǎn)生的右部都不含兩個相繼的非終結(jié)符，故屬于算符文法。從上表可以看出，任何兩個終結(jié)符之間至少滿足=、,、三種關(guān)系之一,故符優(yōu)先文法。給出句型 S*PT(S)對應(yīng)的語法樹，指出該句型的短語、句柄短語：S*PT(S)PT(S)P(S)句柄：P1

23、9)已知文法 G(S)S-T|S-TT 一 F|T/FF-(S)|i(1)給出句型 T/F-i 的最右推導(dǎo)；(2)畫出句型 T/F-i 規(guī)范規(guī)約的語法樹及算符優(yōu)先分析規(guī)約的語法樹框架；(3)給出句型 T/F-i 的短語、素短語。答：(1)最右推導(dǎo)：T 一 F 一(E)一(E+T)一(E+F)一(E+i)一(T+i)一(T*F+(2)略G 為算i)(3)短語：(T*F+i),T*F+i,T*F,i素短語：T*F,i20)某語言的拓廣文法 G為：(0)Sf(1) S-Db|B(2) Dfd|s(3) B-Ba|s證明 G 不是 LR(0)文法而是 SLR(1)文法，請給出 SLR(1)分析表。答：

24、拓廣文法 G,增加產(chǎn)生式 S-S在項(xiàng)目集 I。中：有移進(jìn)項(xiàng)目 D-d歸約項(xiàng)目 Df和 Bf存在移進(jìn)-歸約和歸約-歸約沖突，所以 G 不是 LR(0)文法。若產(chǎn)生式排序?yàn)椋?0)Sf(1) S-Db(2) SfBDfd(4)DfeBfBa(6)B7&G白 LR(0)項(xiàng)目集族及識別活前綴的 DFA 如下圖：由產(chǎn)生式知Follow(S)=#Follow(D)=bFollow(B)=a,#在 I0中：nd=Follow(B)nd=a,#nd=在 I3中:na=#na=所以在 I0,13中的移進(jìn)-歸約和歸約-歸約沖突可以由 Follow 集解決，所以 G 是 SLR(1)文法,構(gòu)造的 SLR(1

25、)分析表如下表：狀態(tài)ACTIONGOTObda#SDB0r4S4r6r61231acc2S53S6r24r35r16r5r521)、下面文法 G 為：(0)E，E(1)ErB(2)BB;d(3)Bd判斷 G 是 SLR(1)還是 LR(1),說明理由，并構(gòu)造相應(yīng)的分析表為移進(jìn)項(xiàng)目所以不是 LR(0)文法FOLLOW(S)=#FOLLOW(S)n:為空，所以該文法是 SLR(1)文法。狀態(tài)ACTIONGOTOr;d#EB0S21狀態(tài) I3 中含項(xiàng)目:一 rB為歸約項(xiàng)目1acc2S433r14r3r35S662r222)、設(shè)文法 G(S):Sf(F)|dS|dF-F;S|S(1)消除左遞歸和回溯；

26、(2)列出第一小題完成后的文法，并計算每個非終結(jié)符的 FIRST 和 FOLLOW(3)構(gòu)造預(yù)測分析表。解：(1)Sf(F)S-dSSfS-e2 分FfFF一，SFF一 e2 分評分細(xì)則：消除左遞歸 2 分，提公共因子 2 分。(2)FIRST(S)=(,dFOLLOW(S 尹#,)FIRST(S)=d,sFOLLOW(S)=#,)FIRST(L)=(,dFOLLOW(L)=)FIRST(L)=,sFOLLOW(L=)3 分因?yàn)椋篎IRST(Sf(F)nFIRST(SfdS)=AFIRST(Sf)AFOLLOWS一 e)=AFIRST(F一，SF)AFIRST(F一)=A所以，此文法是 LL(

27、1)文法(4)預(yù)測分析表d()#S一 dS一(F)S，ffFfFfFF，一，SF，23).設(shè)有基本塊：(1) a:=b-c(6)c:=b-f(2) d:=a+4b:=b-ce:=a-b(8)f:=b+ff:=a+4(9)a:=a-f(5)b:=b+c(1)畫出 DAG 圖；(2)假設(shè)基本塊出口時只有 a,b 還被引用，請寫出優(yōu)化后的三地址代碼序歹 U。解答：(1)給出 DAGfe 右:(2)重寫三地址代碼如下：a:=b-cd:=a+4e:=a-bf:=db:=b+cc:=b-fb:=b-cf:=b+fa:=a-f24).設(shè)有基本塊 TI：=2T2：=10/TIT3：=SRT4：=S+RA：=T

28、2*T4B:=AT5：=S+RT6：=T3*T5B:=T6(1)畫出 DAG 圖；(2)假設(shè)基本塊出口時只有A,B 還被引用,解：(1)DAG:見右圖(2)優(yōu)化后的四元式T3：=S-RT4：=S+RA:=5*T425)將下面的條件語句表示成四元式序列:ifabthenx:=a+b*celsex:=b-a;答：(1) (j,a,b,(3)(2) (j,)(3) (*,b,c,T1)(4)(+,a,T1,T2)(5) (:=,T2,x)(6) (j,(9)(7) (-,b,a,T3)(8) (:=,T3,x)(9)()26)翻譯成四元式序列。Whilea0Vb0thena：=a1elseb：=b+

29、1End;答：請寫出優(yōu)化后的三地址代碼序列。(1) (j,a,0,5)(2) (j，,一,3)(5) (+,x,1,T1)(6) (：=,T1,X)(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)畫出 DAG 圖；b)假設(shè)基本塊出口時只有 E,F 還被引用，請寫出優(yōu)化后的三地址

30、代碼序列。解答：a)構(gòu)造 DAG 見右圖。n7t3,t7b）優(yōu)化后的三地址代碼序列為:t1:=3*At2:=2*Ct3:=t1+t2t4:=t3+5E:=t3-1F:=t4-E五、填空題：1 .編譯程序的工作過程一般可以劃分為詞法分析，語法分析，語義分析，之間代碼生成，代碼優(yōu)化等幾個基本階段，同時還會伴有表格處理和出錯處理.2 .若源程序是用高級語言編寫的，目標(biāo)程序是機(jī)器語言程序或匯編程序，則其翻譯程序稱為編譯程序.3 .對編譯程序而言，輸入數(shù)據(jù)是源程序，輸出結(jié)果是目標(biāo)程序.4 .一個典型的編譯程序中，不僅包括詞法分析、語法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等五個部分，還應(yīng)包括表格處理

31、和出錯處理。其中,詞法分析器用于識別單詞。5 .所謂最右推導(dǎo)是指：任何一步a3都是對a中最右非終結(jié)符進(jìn)行替換的。6 .一個上下文無關(guān)文法所含四個組成部分是一組終結(jié)符號、一組非終結(jié)符號、一個開始符號、一組產(chǎn)生式。7 .產(chǎn)生式是用于定義語法成分的一種書寫規(guī)則。8 .設(shè) GS是給定文法，則由文法 G 所定義的語言 L(G)可描述為：L(G)=x*.Sx,xeVTo9 .設(shè) G 是一個給定的文法，S 是文法的開始符號，如果Sx（其中 xCV*）,則稱 x 是文法的一個句型。10 .設(shè) G 是一個給定的文法，S 是文法的開始符號，如果Sx(其中 xeVT*),則稱 x 是文法的一個句子。11 .語法分析

32、最常用的兩類方法是自上而下和自下而上分析法。12 .語法分析的任務(wù)是識別給定的終極符串是否為給定文法的句子。13 .自頂向下的語法分析方法的關(guān)鍵是如何選擇候選式的問題。14 .自頂向下的語法分析方法的基本思想是：從文法的開始符號開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行直接推導(dǎo)，試圖推導(dǎo)出文法的句子，使之與給定的輸入串匹配。15 .自底向上的語法分析方法的基本思想是：從給定的終極符串開始，根據(jù)文法的規(guī)則一步一步的向上進(jìn)行直接歸約，試圖歸約到文法的開始符號。16 .自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行直接歸約,力求歸約到文法的開始符

33、號。17 .在 LR(0)分析法的名稱中，L 的含義是自左向右的掃描輸入串，R 的含義是最左歸約，0 的含義是向貌似句柄的符號串后查看 0 個輸入符號。18 .在 SLR(1)分析法的名稱中，S 的含義是簡單的。19 .所謂屬性文法是一個屬性文法是一個三元組：A=(GV,F),一個上下文無關(guān)文法 G;一個屬性的有窮集 V 和關(guān)于屬性的斷言或謂詞的有窮集 F。每個斷言與文法的某產(chǎn)生式相聯(lián)。20 .綜合屬性是用于“自下而上”傳涕信息。21 .繼承屬性是用于“自上而下”傳遞信息。22 .符號表中的信息欄中登記了每個名字的屬性和特征等有關(guān)信息，如類型、種屬、所占單元大小、地址等等。23 .常用的兩種動

34、態(tài)存貯分配辦法是棧式動態(tài)分配和堆式動態(tài)分配。24 .局部優(yōu)化是局限于一個基本塊范圍內(nèi)的一種優(yōu)化。25 .代碼優(yōu)化的主要目標(biāo)是如何提高目標(biāo)程序的運(yùn)行速度和如何減少目標(biāo)程序運(yùn)行時所需的空間。編譯原理期末考試試卷(A 卷)一、簡述編譯程序的工作過程。(10)編譯程序的工作過程，是指從輸入源程序開始到輸出目標(biāo)程序?yàn)橹沟恼麄€過程,是非常復(fù)雜的，就其過程而言，一般可以劃分為五個工作階段：詞法分析，對構(gòu)成源程序的字符串進(jìn)行掃描和分解，識別出一個個的單詞；語法分析，根據(jù)語言的語法規(guī)則，把單詞符號用分解成各類語法單位；語義分析與中間代碼產(chǎn)生，即對各類語法單位，分析其漢一并進(jìn)行初步翻譯；代碼優(yōu)化，以期產(chǎn)生更高效的

35、代碼；目標(biāo)代碼生成，把中間代碼變換成特定機(jī)器上的低級語言指令形式。二、給出下面的正規(guī)表達(dá)式(15)(1)以 01 結(jié)尾的二進(jìn)制數(shù)串；(2)能被 5 整除的十進(jìn)制整數(shù)；(3)包含偶數(shù)個 1 或偶數(shù)個 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*)三、對下面的文法 G:S-a|b|(T)T-T,S|S(1)消去文法的左遞歸，得到等價的文法 G2;(2)判斷文法 G2 是否 LL(1)文法，如果是，給出其預(yù)測分析表。(15)G2:S-a|b|(T)T 一 STT一，ST|e

36、G2 是 LL(1)文法。ab()#SS 一 aSfbS 一(T)T一 ST-STT-STT，T，一一，ST，四、對下面的文法 G:S-ABA-A00|0B一B11|1(1)消去文法的左遞歸，得到等價的文法 G2;(2)判斷文法 G2 是否 LL(1)文法，如果是，給出其預(yù)測分析表。(15)G:SfABA-0AA一 00A|eB-1BB一 11B|文法 GS是 LL(1)文法預(yù)測分析表：01#S飛入 ABAA-0A，A，A-00AA-eBB-1BB，B一 11BB-e五、設(shè)有文法 GA:AfBCc|gDBBfbCDE|C-DaB|caD-dD|E 一 gAf|c(1)計算該文法的每一個非終結(jié)符

37、的 FIRST 集和 FOLLOW 集;(2)試判斷該文法是否為 LL(1)文法。(15)FIRSTFOLLOWAA,b,c,d,gBbA,c,dCA,c,dC,d,gDDA,b,c,gEC,g(2)是 LL(1)文法。編譯原理期末考試試卷(B 卷)三、應(yīng)用題(1、4、5 每題 10 分，2、3 每題 15 分，共 60 分)*1、為正規(guī)式(a|b)a(a|b)構(gòu)造等價且狀態(tài)最少的確定有限自動機(jī)。(要求給出主要步驟)2、有文法如下：S 一 BAA 一 BS|dB 一 aA|bS|c(1),計算文法的每個非終結(jié)符的 FIRST 和 FOLLO 碌合；(2).判斷文法是否 LL(1)文法，如果是，給出其預(yù)測分析表，否則說明理由。4、有文法如下：T 一 T*F|FF 一 PF|PP 一(T)|i證明 T*iP 是該文法的一個句型，但不是規(guī)范句型;指出 T*iP 的所有短語、直接短語、素短語、句柄。三、應(yīng)用題(1、4、5