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

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

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

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

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

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

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

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

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

9、a,b, FM, S, C,D,E,F這 個(gè) DFA M的狀態(tài)轉(zhuǎn)換圖見(jià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.語(yǔ)法分析1.文法 GV：VN | NE EV| V+E

10、 Ni是否為L(zhǎng)L(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)分析表，寫(xiě)出句子adccd的分析過(guò)程解：一個(gè)LL(1)文法的充要條件是對(duì)每一個(gè)非終結(jié)符A的任何兩個(gè)不同產(chǎn)生式Aa田，有下 面的條件成立：FIRST(a)CFIRST(B)=中，若B* ,則有 FIRST( a ) n FOLLOW(

11、A)=O 對(duì) 于文法 Gs: SBAABS|dBaA|bS|cFIRST 集 FIRST(B)=a, b, c; FIRST(A)=a, b, c, d;FIRST(S)=a, b, c。FOLLOW 集 FOLLOW(S)=#對(duì) SBA 有 FIRST(A) 加入 FOLLOW(B)，即 FOLLOW(B)=a, b, c, d 對(duì) ABS 有 FIRST(S) 加入 FOLLOW(B)，即 FOLLOW(B)=a, b, c, d 對(duì) BaA 有 FOLLOW(B)加入 FOLLOW(A)，即 FOLLOW(A)=a, b, c, d 對(duì) 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)生式，故無(wú)需求解形如FIRST( a ) n FOLLOW(A)的值也即，文法 GS是一個(gè) 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ù)測(cè)分析表如下：abcd#SS-BAS-BAS-BAAA-BSA-BSA-BSA-dBB-aAB-bSB-c在分析表的控制下，句子adccd的分析過(guò)程如下:棧當(dāng)前輸入符號(hào)輸入串說(shuō)明#Sadccd#SBA#ABadccd#BaA#AAaadccd#AAdccd#Ad#Addccd#Accd#ABS#SBccd#Bc#Scccd#Scd#SBA#ABcd#Bc#Accd#Ad#Ad#dd#分析成功3.對(duì)于文法 G(E)： ETE Ef+TE I & TFT Tf*FT I 8F(E)

14、 I i構(gòu)造每個(gè)非終結(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出錯(cuò)標(biāo)志出錯(cuò)標(biāo)志E TEsynchsynchE出錯(cuò)標(biāo)志E +TE 出錯(cuò)標(biāo)志出錯(cuò)標(biāo) 志E 8E 8TT FT synch出錯(cuò)標(biāo)志T FT synchsynchT出錯(cuò)標(biāo)志T 8T

15、*FT 出錯(cuò)標(biāo) 志T 8T 8FF isynchsynchF (E)synchsynch把FOLLOW(A)中的所有符號(hào)作為A的同步符號(hào)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)和分析樹(shù)，并根據(jù)分析樹(shù)指出句 子中的短語(yǔ)、直接短語(yǔ)和句柄1 i I 11-I：=UK I TOC o 1-5 h z :-HAT-H耳=*讓1耳點(diǎn)- _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一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱(chēng)為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.例如，語(yǔ)句X:=(A+B)*C;三個(gè)域：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)先級(jí)由高到低依次為-、+、*、/,且均為左結(jié)合，則其后綴式為 a-b+cd+ef*+*de*/如果優(yōu)先級(jí)由高到低依次為-、+、*、$ (乘冪)，且均為右結(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)請(qǐng)將表達(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)