編譯原理全復(fù)習(xí)

1、1編譯程序的框架圖與功能塊：（1）畫出編譯程序的總體結(jié)構(gòu)，并簡述各部分的主要功能: 七個部分 （2）編譯程序的結(jié)構(gòu)分為幾個階段，各階段的任務(wù)是什么？答編譯程序總框架（1）詞法分析器，又稱掃描器，輸入源程序，進(jìn)行詞法分析，輸出單詞符號。（2）語法分析器，簡稱分析器，對單詞符號串進(jìn)行語法分析（根據(jù)語法規(guī)則進(jìn)行推導(dǎo)或 規(guī)約），識別出各類語法單位，最終判斷輸入串是否構(gòu)成語法上正確的“程序”。（3）語義分析與中間代碼產(chǎn)生器，按照語義規(guī)則對語法分析器歸約出（或推導(dǎo)出）的語 法單位進(jìn)行語義分析并把它們翻譯成一定形式的中間代碼。優(yōu)化器，對中間代碼進(jìn)行優(yōu)化處理。目標(biāo)代碼生成器，把中間代碼翻譯成目標(biāo)程序。表格管理

2、，登記源程序的各類信息，編譯各階段的進(jìn)展?fàn)顩r。出錯管理，把錯誤信息報告給用戶。（4）（5）（6）（7） 編譯程序的結(jié)構(gòu)分為五個階段：（1）詞法分析.任務(wù)是：輸入源程序，對構(gòu)成源程序的字 符串進(jìn)行掃描和分解，識別出一個個的單詞（亦稱單詞符號或簡稱符號），如基本字，標(biāo) 識符，常熟，算符和界符。（2）。語法分析，任務(wù)是：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把單詞符號串分 解成各類語法單位（語法范疇）。（3）語義分析與中間代碼產(chǎn)生。任務(wù)：對語法分析所識別出的各類語法范疇，分析其含 義，并進(jìn)行初步翻譯（產(chǎn)生中間代碼）。（4）優(yōu)化。任務(wù)在于對前段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出更 為

3、高效（省時間和空間）的目標(biāo)代碼。（5）目標(biāo)代碼生成。任務(wù)是：把中間代碼（或優(yōu)化出理之后）變換成特定機(jī)械上的低級 語言代碼。2.重要概念：編譯程序：是指能夠把源語言程序轉(zhuǎn)換成邏輯上等價的目標(biāo)語言程序的一個程序。單詞符號：是語言的基本組成成分，是人們理解和編寫程序的基本要素，是語言中具有 獨立意義的最基本結(jié)構(gòu)，它一般包括：基本字、標(biāo)識符、常數(shù)、運算符和界符等中間代碼：是一種含義明確，便于處理的記號系統(tǒng)，它通常獨立于具體的硬件。遍：就是對源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成 新的中間結(jié)果或目標(biāo)程序。上下文無關(guān)文法(CFG)：它所定義的語法范疇(或語法單位)完全獨立于這種

4、范疇可能 出現(xiàn)的環(huán)境之外，不宜描述自然語言。自然語言中，句子和詞等往往與上下文緊密相關(guān)LL(K)分析法：第一個L表示從左到右掃描輸入串，第二個L表示最左推導(dǎo)，K表示 分析時每一步需要向前查看K個符號。LR分析法：L表示從左到右掃描輸入串,R表示構(gòu)造一個最右推導(dǎo)的逆過程。算符優(yōu)先法：就是定義算符之間的某種優(yōu)先關(guān)系，借助于這種關(guān)系尋找“可歸約串”和進(jìn) 行歸約。屬性文法：是在上下文無關(guān)文法的基礎(chǔ)上，為每個文法符號(終結(jié)符或非終結(jié)符)配備若 干相關(guān)的“值”(稱為屬性)，對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則(稱為語 義規(guī)則)。3.有哪些存儲分配策略，并敘述何時用何種存儲分配策略？答：有靜態(tài)與動

5、態(tài)存儲分配策略。動態(tài)的存儲分配策略包括棧式動態(tài)分配策略與堆式動 態(tài)分配策略。靜態(tài)分配策略在編譯時對所有數(shù)據(jù)對象分配固定的存儲單元，且在運行時始 終保持不變。棧式動態(tài)分配策略在運行時把存儲器作為一個棧進(jìn)行管理，運行時，每當(dāng)調(diào)用 一個過程，它所需要的存儲空間就動態(tài)地分配于棧頂，一旦退出，她所占空間就予以釋放。 堆式動態(tài)分配策略在運行時把存儲器組織成堆結(jié)構(gòu)，以便用戶關(guān)于存儲空間的申請與歸還 (回收)，凡申請者從堆中分給一塊，凡釋放者退回給堆。4.編譯過程中可進(jìn)行的優(yōu)化如何分類？最常用的代碼優(yōu)化技術(shù)有哪些？答：根據(jù)優(yōu)化涉及范圍與程序范圍可以分為：局部優(yōu)化，循環(huán)優(yōu)化和全局優(yōu)化。最常用的代碼優(yōu)化技術(shù)有：刪

6、除公共子表達(dá)式，復(fù)寫傳播，刪除無用代碼，代碼外提，強(qiáng)度 削弱和刪除歸納變量。5.一個編譯程序的代碼生成要著重考慮哪些問題？答：代碼生成器的設(shè)計要著重考慮目標(biāo)代碼的質(zhì)量問題，而衡量目標(biāo)代碼的質(zhì)量主要從 占用空間和執(zhí)行效率兩個方面綜合考慮。【代碼生成要著重考慮兩個問題：1).如何使生成的目標(biāo)代碼較短2.)如何充分利用 計算機(jī)的寄存器。(減少目標(biāo)代碼中訪問存儲單元的次數(shù)。)這兩個問題都直接影響目標(biāo) 代碼的執(zhí)行速度】6.語言和文法的轉(zhuǎn)換的例題. 文法 G2： S-bA，A-aA I a解：推導(dǎo)過程SnbAnbaS nbAnbaAnbaaS nbAnbaAn nba a歸納得出：L(G2)=baAn I

7、 nN1.文法 G3： S-AB，A-aA I a，B-bB I b解：推導(dǎo)過程 SnABnabSnABnaABnaAbnaabnaA2bSnABnabBnabbnabA2歸納得出 L(G3)=aAmbAn I m,nN1. 若已知文法G6(A)：At clAb請給出G6(A)的語言？解答:L(G6)=c，cb， cbb，. 以c開頭，后繼若干個b.若已知文法 G8(S)： S-aSBES-aBEEB-BEaB-abbB-bbbE-be eE-ee請給出G8(S)的語言？解答:Sa5BESaaBBEESaaBEESaabbEESaabbESaabbeeSaaBBE (SaBE)(EBBE)(a

8、Bab)(bBbb)(bEbe)(eEee)L(G8)= aAnbAneAn I nN1,上下文有關(guān)文法(5)給出生成下述語言的上下文無關(guān)文法：(1) aAnbAnaAmbAmI n, m=0(2) 1An0Am1Am0AnI n, m=0-G1(S)-G2(S)SAAAaAbI S1S0IAA0A1I 7.有限自動機(jī)(1) DFA 舉例 DFA M = (0,1,2,3,a,b,f,0,3)f定義如下：孔夫二土g 公 1235 門1,2,3 點 1 .2.4.6 X因此得出上表。根據(jù)上述NFA的狀態(tài)轉(zhuǎn)換圖及其確定化過程，可以構(gòu)造與它等價的DFA M。DFA M=S,A,B,C,D,E,F,

9、a,b, FM, S, C,D,E,F這 個 DFA M的狀態(tài)轉(zhuǎn)換圖見下圖所示其中S=i,1,2A=1,2,3B=1,2,4C=1,2,3,5,6,fD=1,2,4,5,6,fE=1,2,4,6,fF=1,2,3,6,fFM是DFA M的狀態(tài)轉(zhuǎn)換函數(shù)，定義如下：FM (S,a)=AFM (S,b)=BFM (A,a)=CFM (A,b)=BFM (B,a)=AFM (B,b)=DFM (C,a)=CFM (C,b)=EFM (D,a)=FFM (D,b)=DFM (E,a)=FFM (E,b)=DFM (F,a)=CFM (F,b)=E8.語法分析1.文法 GV：VN | NE EV| V+E

10、 Ni是否為LL(1)文法？若不是，如何改造成LL(1)文法?解：LL(1)文法的基本條件是不含左遞歸和回溯(公共左因子)，而GV中含有回溯，所以先消 除回溯得到文法 GV：GV：V-NVV一 8|EVEVEEf |+EENi由LL(1)文法的充要條件可證G V是LL(1)文法2.文法 Gs:SBAABS|dBaA|bS|c證明文法G是LL(1)文法，構(gòu)造LL(1)分析表，寫出句子adccd的分析過程解：一個LL(1)文法的充要條件是對每一個非終結(jié)符A的任何兩個不同產(chǎn)生式Aa田，有下 面的條件成立：FIRST(a)CFIRST(B)=中，若B* ,則有 FIRST( a ) n FOLLOW(

11、A)=O 對 于文法 Gs: SBAABS|dBaA|bS|cFIRST 集 FIRST(B)=a, b, c; FIRST(A)=a, b, c, d;FIRST(S)=a, b, c。FOLLOW 集 FOLLOW(S)=#對 SBA 有 FIRST(A) 加入 FOLLOW(B)，即 FOLLOW(B)=a, b, c, d 對 ABS 有 FIRST(S) 加入 FOLLOW(B)，即 FOLLOW(B)=a, b, c, d 對 BaA 有 FOLLOW(B)加入 FOLLOW(A)，即 FOLLOW(A)=a, b, c, d 對 BbS 有 FOLLOW(B)加入 FOLLOW(

12、S)，即 FOLLOW(S)=#, a, b, c, d 由 ABS|d 得 FIRST(BS) n FIRST(d) = a, b, c n d=中由 BaA|bS|c 得 FIRST(aA) n FIRST(bS) n FIRST(c)=a n b n c=中由于文法Gs 不存在形如B一的產(chǎn)生式，故無需求解形如FIRST( a ) n FOLLOW(A)的值也即，文法 GS是一個 LL(1)文法 由 Gs： SBA ABS|d BaA|bS|c 的FIRST(B)=a, b, c;FOLLOW(B)=a, b, c, d ;FIRST(A)=a, b, c, d;FOLLOW(A)=a,

13、b, c, d ;FIRST(S)=a, b, c。FOLLOW(S)=#, a, b, c, d 可構(gòu)造LL(1)預(yù)測分析表如下：abcd#SS-BAS-BAS-BAAA-BSA-BSA-BSA-dBB-aAB-bSB-c在分析表的控制下，句子adccd的分析過程如下:棧當(dāng)前輸入符號輸入串說明#Sadccd#SBA#ABadccd#BaA#AAaadccd#AAdccd#Ad#Addccd#Accd#ABS#SBccd#Bc#Scccd#Scd#SBA#ABcd#Bc#Accd#Ad#Ad#dd#分析成功3.對于文法 G(E)： ETE Ef+TE I & TFT Tf*FT I 8F(E)

14、 I i構(gòu)造每個非終結(jié)符的 FIRST 和 FOLLOW 集合 FIRST(E) = (, i FOLLOW(E) = ), # FIRST(E)=+,8 FOLLOW(E)= ), # FIRST(T) = (, i FOLLOW(T) = +, ), # FIRST(T)=*,8 FOLLOW(T)= +, ), # FIRST(F) = (, i FOLLOW(F) = *, +, ), # i+*()#EE TE出錯標(biāo)志出錯標(biāo)志E TEsynchsynchE出錯標(biāo)志E +TE 出錯標(biāo)志出錯標(biāo) 志E 8E 8TT FT synch出錯標(biāo)志T FT synchsynchT出錯標(biāo)志T 8T

15、*FT 出錯標(biāo) 志T 8T 8FF isynchsynchF (E)synchsynch把FOLLOW(A)中的所有符號作為A的同步符號4.已知文法 GS： S eT I RT T DR I 8R dR I 8D a I bd構(gòu)造該文法的LL(1)分析表。FIRST(S), FIRST(T), FIRST(R), FIRST(D)FOLLOW(S),FOLLOW (T),FOLLOW (R),FOLLOW (D)LL(1)分析表FOLLOW(S) = # 解：FIRST(S) = a, b, d, e, 8 .Lil 1irtl I JIC1 IV., 11句機(jī)1 FIRST(T) = a,

16、b, 8 FOLLOW(T) = # FIRST(R) = d, 8 FOLLOW(R) = a, b, # FIRST(D) = a, b FOLLOW(D) = d, # 該文法的LL(1)分析表如下:abde#SSRTSRTSRTSeTTTDRTDR8R88TDR8DDf aDbd5.例：文法GE： E f E+T IT T f T*F I F F (E) I id考慮文法GE上的句子id1+id2*id3。給出其最右推導(dǎo)和分析樹，并根據(jù)分析樹指出句 子中的短語、直接短語和句柄1 i I 11-I：=UK I TOC o 1-5 h z :-HAT-H耳=*讓1耳點- _LM I* iJ

17、2S一二JI7)-1-1I：=i0 A (8+z) 3 的逆波蘭表示為 xy+zWa08z+3AV 表達(dá)式一A V (C V D)的逆波蘭表示為ACD V V表達(dá)式 a A b V c A (b V x=0 A c) 的逆波蘭表示為ab Acbx0=c AVAV表達(dá)式 (AVB)A(CV-DAE)的逆波蘭表示為ABVCDEAVA一個帶有四個域的記錄結(jié)構(gòu)，這四個域分別稱為op, arg1, arg2及result例：a:=b*-c+b*-c的四元式resultoparg1arg2(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4+T2T4T5:=T5a2.例：a

18、:=b*-c+b*-c的三元式oparg1arg2(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+(1)(3)assigna(4)3.例如，語句X:=(A+B)*C;三個域：op、arg1和arg2Y:=D f (A+B)的間接三元式表示如右圖(1)(3)(1)(4)間接代碼ARG2(1)(2)(3)(4)(5)三元式表OP ARG1+ A B TOC o 1-5 h z *(1)C:=X(2)f D (1):=Y(4)表達(dá)式-a+b*c+d+(e*f)/d*e,如果優(yōu)先級由高到低依次為-、+、*、/,且均為左結(jié)合，則其后綴式為 a-b+cd+ef*+*de*/如果優(yōu)先級由高到低依次為-、+、*、$ (乘冪)，且均為右結(jié)合，則表達(dá)式2+3-2+2*2*1$2$3-3-2+1 的后綴式為 232-2+21*2332-1+$ 如果某表達(dá)式的后綴式為ab+cd+*,則其中綴形式的表達(dá)式為(a+b) * (c+d)請將表達(dá)式-(a+b)*(c+d)-(a+b)分別表示成三元式、間接三元式和四元式序列解：三元式間接三元式(1) (+a, b)間接三元式序列間接碼表(2) (+c, d)(1) (+ a, b) (1)(3) (*(1), (2)(2) (+ c, d) (2)(4) (-(3)