編譯原理復(fù)習(xí)資料檔

1、1編譯程序的框架圖與功能塊：（1）畫出編譯程序的總體結(jié)構(gòu)，并簡(jiǎn)述各部分的主要功能:七個(gè)部分 （2）編譯程序的結(jié)構(gòu)分為幾個(gè)階段，各階段的任務(wù)是什么？答編譯程序總框架（1）詞法分析器，又稱掃描器，輸入源程序，進(jìn)行詞法分析，輸出單詞符號(hào)。（2）語(yǔ)法分析器，簡(jiǎn)稱分析器，對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析（根據(jù)語(yǔ)法規(guī)則進(jìn)行推導(dǎo)或 規(guī)約），識(shí)別出各類語(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、登記源程序的各類信息，編譯各階段的進(jìn)展?fàn)顩r。出錯(cuò)管理，把錯(cuò)誤信息報(bào)告給用戶。（4）（5）（6）（7） 編譯程序的結(jié)構(gòu)分為五個(gè)階段：（1）詞法分析.任務(wù)是：輸入源程序，對(duì)構(gòu)成源程序的字 符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)的單詞（亦稱單詞符號(hào)或簡(jiǎn)稱符號(hào)），如基本字，標(biāo) 識(shí)符，常熟，算符和界符。（2）。語(yǔ)法分析，任務(wù)是：在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)串分 解成各類語(yǔ)法單位（語(yǔ)法范疇）。（3）語(yǔ)義分析與中間代碼產(chǎn)生。任務(wù)：對(duì)語(yǔ)法分析所識(shí)別出的各類語(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ǔ)言的基本組成成分，是人們理解和編寫程序的基本要素，是語(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)的“值”（稱為屬性），對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則（稱為語(yǔ) 義規(guī)則）。3.有哪些存儲(chǔ)分配策略，并敘述何時(shí)用何種存儲(chǔ)分配策略？答：有靜態(tài)與動(dòng)態(tài)

5、存儲(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)，以便用戶關(guān)于存儲(chǔ)空間的申請(qǐng)與歸還 （回收），凡申請(qǐng)者從堆中分給一塊，凡釋放者退回給堆。4.編譯過(guò)程中可進(jìn)行的優(yōu)化如何分類？最常用的代碼優(yōu)化技術(shù)有哪些？答：根據(jù)優(yōu)化涉及范圍與程序范圍可以分為：局部?jī)?yōu)化，循環(huán)優(yōu)化和全局優(yōu)化。最常用的代碼優(yōu)化技術(shù)有：刪除

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

7、 n1(2).文法 G3： SAB，AaA I a，BbB I b解：推導(dǎo)過(guò)程SnABnabSnABnaABnaAbnaabnaA2bSnABnabBnabbnabA2歸納得出 L(G3)=aAmbAn I m,n31.若已知文法G6(A)：At clAb請(qǐng)給出G6(A)的語(yǔ)言？解答:L(G6)=c，cb，cbb，.以c開頭，后繼若干個(gè)b.若已知文法 G8(S)： SaSBESaBEEBBEaBabbBbbbEbeeEee請(qǐng)給出G8(S)的語(yǔ)言？解答:Sa5BESaaBBEESaaBEESaabbEESaabbESaabbeeSaaBBE (SaBE)(EBBE)(aBab)(bBbb)(bE

8、be)(eEee)L(G8)= aAnbAneAn I n31,上下文有關(guān)文法(5)給出生成下述語(yǔ)言的上下文無(wú)關(guān)文法：(1) aAnbAnaAmbAmI n, m=0(2) 1An0Am1Am0AnI n, m=0-G1(S)SAAAaAbl-G2(S) S1S0IAA0A1IS7.有限自動(dòng)機(jī)(1) DFA 舉例 DFA M = (0,1,2,3,a,b,f,0,3)f定義如下：f(0,a)=1 f(0,b)=2f(1,a)=3 f(1,b)=2f(2,a)=1f(2,b)=3f(3,a)=3f(3,b)=3對(duì)于*中的任何字茶存專條渙態(tài)到某一終態(tài)的通路，且這條通路上所有弧的標(biāo)記符連接成的字等于

9、a,則稱a為DFA M所識(shí)別(或接受)證法一：a,b 仁 baab 仁 *f(S,baab) = f(f(S,b),aab) = f(V ,aab) = f(f(V,a),ab) = f(U,ab) = f(f(U,a),b) = f(Q,b)=Q。Q屬于終態(tài),故得證證法二：根據(jù)上述狀態(tài)轉(zhuǎn)換圖，可以構(gòu)造確定有限自動(dòng)機(jī)DFA M=S,U,V,Q, a,b,FM, S, Q其中，F(xiàn)M是DFA M的狀態(tài)轉(zhuǎn)換函數(shù)，定義如下:FM(S,a)=UFM(S,b)=VFM(U,a)=QFM(U,b)=VFM(V,a)=UFM(V,b)=QFM(Q,a)=QFM(Q,b)=Qa,b 仁 . baab e *由題

10、意可知：對(duì)于t=baab, DFA M存在一條經(jīng)過(guò)S、V、U、Q和Q的通路，使得該通路上所有弧的標(biāo)記符連接成的字等于t因此，t被DFA M所接受(2)：下圖是一個(gè)NFA的狀態(tài)轉(zhuǎn)換圖，請(qǐng)將其轉(zhuǎn)化為一個(gè)DFA。解：采用NFA確定化算法(或子集法)。狀態(tài)集合I的 -閉包表示為 -closure(I)。狀態(tài)集I中任何狀態(tài)S經(jīng)任意條弧而能到達(dá)的狀態(tài)集S -closure(I)。狀態(tài)集合I的a弧轉(zhuǎn)換表示為move(I,a)，定義為狀態(tài)集合J,其中：J是所有那些可從I 中的某一狀態(tài)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)的全體。OIa = move(I,a) = -closure(J)。lalbi，l，2123124123

11、123,5,6,f12412412312436,f123,5,6,fl,2,3,5,6,fl,2f因此得霹45,6,fl,2,3,6,fl,2,4,5,6,f。根據(jù)上述nFA的狀態(tài)轉(zhuǎn)換圖及其確定化過(guò)程，可以構(gòu)造與它等價(jià)的DFA 3爪L2,4,5,6,f123,6,f12,3,5,6,0124,6,fDFA M=S,A,B,C,D,E,F，a,b，F(xiàn)M，S，C,D,E,F這個(gè) 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

12、,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 Ni是否為L(zhǎng)L(1)文法？若不是，如何改造成LL(1)文法?解：LL(1)文法的基本條件是不含左遞歸和回溯(公共左因子)，而GV中含有回溯，所以先消 除回溯得到文法 GV：GV：V-NVV一 lEV圖所示EVEE l+EENi由LL(1)文法的充要條件可證G V是LL(

13、1)文法2.文法 Gs:SBAABSIdBaAlbSIc證明文法G是LL(1)文法，構(gòu)造LL(1)分析表，寫出句子adccd的分析過(guò)程解：一個(gè)LL(1)文法的充要條件是對(duì)每一個(gè)非終結(jié)符A的任何兩個(gè)不同產(chǎn)生式Aa |p，有下 面的條件成立：FIRST(a ) n FIRST(P )=0，若8 * ,則有 FIRST(a ) n FOLLOW(A)=0 對(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

14、) 加入 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(S)，即 FOLLOW(S)=#, a, b, c, d 由 ABS|d 得 FIRST(BS) n FIRST(d) = a, b, c n d = 0由 BaA|bS|c 得 FIRST(aA) n FIRST(bS) n FIRST(c)=a n b

15、n c= 0由于文法Gs不存在形如8 的產(chǎn)生式，故無(wú)需求解形如FIRST(a ) n FOLLOW(A)的值也FIRST(B)=a, b, c;FOLLOW(B)=a, b, c, d ;即，文法 GS是一個(gè) LL(1)文法 由 Gs： SBA ABS|d BaA|bS|c 的FIRST(A)=a, b, c, d;FOLLOW(A)=a, 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

16、的分析過(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 F(E) I i構(gòu)造每個(gè)非終結(jié)符的 FIRST 和 FOLLOW 集合 FIRST(E) = (, i FOLLOW(E) = ), # FIRST(E)=+, FOLLOW(E)= ), # FIRST(T) = (, i FOLLOW(T) = +, ), # FI

17、RST(T)=*聲 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 E TT FT synch出錯(cuò)標(biāo)志T FT synchsynchT出錯(cuò)標(biāo)志T T *FT 出錯(cuò)標(biāo) 志T T FF isynchsynchF (E)synchsynch把FOLLOW(A)中的所有符號(hào)作為A的同步符號(hào)4.已知文法 GS： S eT | RT T DR | R dR | D a | bd構(gòu)造該文法的LL(1)分析表。FIRST(S), FI

18、RST(T), FIRST(R), FIRST(D)FOLLOW(S),FOLLOW (T),FOLLOW (R),FOLLOW (D)LL(1)分析表解：FIRST(S) = a, b, d, e, FOLLOW(S) = # FIRST(T) = a, b, FOLLOW(T) = # FIRST(R) = d, abde#SSfRTSfRTSfRTSfeTTTfDRTfDRRTfDRDDf aDfdFOLLOW(R) = a, b, # FIRST(D) = a, b FOLLOW(D) = d, # 該文法的LL(1)分析表如下：5.例：文法GE： E f E+T IT T f T*F

19、 I F F f (E) I id考慮文法GE上的句子id1+id2*id3。給出其最右推導(dǎo)和分析樹，并根據(jù)分析樹指出句 子中的短語(yǔ)、直接短語(yǔ)和句柄E1=a E2 + T3 * F2 3) =a E2 + T3 * id3 =a E2 + F3 * id3 (5)=a E2 + id2 * id3 6) =a T2 + id2 * id3=a Fl + id2 * id3 S) =a idl + id2 * id3 ElE2 + T1I hT2 T3 * F2Fl F3 id3idl id2短起 idl+id2*id3(El id2*id3(Tl) idl id3F2)直接短咨 iaiFi).

20、id2F3). id3 句柄：idl從 E1 推導(dǎo)可得到 id1+id2*id3O)0 A (8+z) 3 的逆波蘭表示為 xy+zWa08z+3AV表達(dá)式一A V (C VD)的逆波蘭表示為ACD V V表達(dá)式a A b V c A (b V x=0 A c) 的逆波蘭表示為abAcbx0=cAVAV表達(dá)式 (AVB)A(CV-DAE )的逆波蘭表示為ABVCDEAVA一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱為op, arg1, arg2及result例：a:=b*-c+b*-c的四元式oparg1arg2result(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4+T2T4T5:=T5a2.例：a:=b*-c+b*-c的三元式 三個(gè)域：op、arg1和 arg2oparg1arg2(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+(1)(3)assigna(4)3.例如，語(yǔ)句X:=(A+B)*C;Y:=D f (A+B)的間接三元式表示如右圖(1)(3)(1)(4)間接代碼ARG2(1)(2)(3)(4)(5)三元式表