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

1、1認(rèn)識(shí)、理解認(rèn)識(shí)、理解 和和 執(zhí)行執(zhí)行 高級(jí)程序設(shè)計(jì)語(yǔ)言高級(jí)程序設(shè)計(jì)語(yǔ)言 ？李偉生李偉生信科大廈信科大廈19樓樓Tel：21、基礎(chǔ)知識(shí)：文法2、詞法分析 理論模型正規(guī)文法與有限自動(dòng)機(jī) 實(shí)現(xiàn)詞法分析程序3、語(yǔ)法分析 理論模型：自上而下分析 自下而上分析4、中間代碼生成 語(yǔ)法制導(dǎo)翻譯5、運(yùn)行時(shí)數(shù)據(jù)區(qū)的管理6、中間代碼優(yōu)化：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化7、目標(biāo)代碼生成3復(fù)習(xí)范圍：第15章、7章、911章復(fù)習(xí)方法：1、認(rèn)真理解書(shū)中的基本概念、基本原理與基本算法；2、弄懂書(shū)中的例題與習(xí)題；3、在看書(shū)時(shí)或理解例題時(shí)，一定要?jiǎng)澇鱿鄳?yīng)的細(xì)節(jié)變化過(guò)程，通過(guò)畫(huà)圖來(lái)加深理解；4、在理解的基礎(chǔ)上記憶?？荚囶}型：簡(jiǎn)答題

2、；名詞解釋?zhuān)黄溆酁榉植几髡碌姆治鲱}。4詞法詞法分析分析語(yǔ)法語(yǔ)法分析分析語(yǔ)義分語(yǔ)義分析和中析和中間代碼間代碼生成生成目標(biāo)目標(biāo)代碼代碼生成生成源源代代碼碼目目標(biāo)標(biāo)代代碼碼 錯(cuò)錯(cuò) 誤誤 處處 理理 符符 號(hào)號(hào) 表表 管管 理理優(yōu)化優(yōu)化處理處理編譯程序總體結(jié)構(gòu)編譯程序總體結(jié)構(gòu)掌握編譯程序的掌握編譯程序的五個(gè)階段，五個(gè)階段，及每個(gè)階段的輸入和輸出及每個(gè)階段的輸入和輸出單詞單詞符號(hào)符號(hào)語(yǔ)法語(yǔ)法單位單位中間中間代碼代碼中間中間代碼代碼5掌握基本概念掌握基本概念：遍遍( (趟趟) )：編譯程序?qū)υ闯绦蚧蛟闯绦虻闹虚g結(jié)果從頭編譯程序?qū)υ闯绦蚧蛟闯绦虻闹虚g結(jié)果從頭至尾掃描的次數(shù)。至尾掃描的次數(shù)。編譯前端和后端：編

3、譯前端和后端：編譯前端：由與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無(wú)關(guān)的部分組編譯前端：由與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無(wú)關(guān)的部分組成，通常包括詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間成，通常包括詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼生成。代碼生成。編譯后端：由編譯程序中與目標(biāo)機(jī)有關(guān)的部分組成，編譯后端：由編譯程序中與目標(biāo)機(jī)有關(guān)的部分組成，如與目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。通常，如與目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。通常，后端不依賴(lài)于源語(yǔ)言而僅僅依賴(lài)于中間語(yǔ)言。后端不依賴(lài)于源語(yǔ)言而僅僅依賴(lài)于中間語(yǔ)言。6文法：文法：描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則。上下文無(wú)關(guān)文法：上下文無(wú)關(guān)文法：上下文無(wú)關(guān)文法是這樣一種文法，它所定義

4、的語(yǔ)法范疇（過(guò)語(yǔ)法單位）是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的。上下文無(wú)關(guān)文法的組成上下文無(wú)關(guān)文法的組成：一個(gè)上下文無(wú)關(guān)文法G是一個(gè)四元式(VT,VN,S,P)，其中VT是一個(gè)非空有限集，它的每個(gè)元素稱(chēng)為終結(jié)符號(hào)；VN是一個(gè)非空有限集，它的每個(gè)元素稱(chēng)為非終結(jié)符號(hào)；S是一個(gè)非終結(jié)符號(hào)，稱(chēng)為開(kāi)始符號(hào)；P是一個(gè)產(chǎn)生式集合，每個(gè)產(chǎn)生式的形式是P。7例如，例如，考慮上下文無(wú)關(guān)文法： Ei|EAE A+|*其中，E、A是非終結(jié)符號(hào)，而i、+和*是終結(jié)符。注意幾個(gè)符號(hào)：注意幾個(gè)符號(hào)：定義為=：推導(dǎo)*：表示定義符號(hào)串的全體|：表示“或” ：空字。8要求掌握最左推導(dǎo)要求掌握最左推導(dǎo)并畫(huà)出語(yǔ)法樹(shù)并畫(huà)出語(yǔ)法樹(shù)：最左推

5、導(dǎo)：任何一步推導(dǎo)=都是對(duì)中的最左終結(jié)符進(jìn)行替換的。如文法E E+E|E*E|(E)|i，推導(dǎo)句子(i+i)： E (E) (E+E) (i+E) (i+i)句子和句型句子和句型假定G是一個(gè)文法，S是它的開(kāi)始符號(hào)。如果S=，則稱(chēng)是一個(gè)句型。僅含終結(jié)符的句型是一個(gè)句子。9要求：掌握將正規(guī)式構(gòu)造為最小要求：掌握將正規(guī)式構(gòu)造為最小DFA的過(guò)程。的過(guò)程。步驟步驟：1.構(gòu)造其構(gòu)造其N(xiāo)FA；2.將構(gòu)造的NFA確定化；3.將確定的NFA(DFA)最小化。ijABijABijA|BijA*ij ijABA10例：例：正則表達(dá)式A(A|B)*B的NFA構(gòu)造過(guò)程XYA(A|B)*BXYA(A|B)*X12YAB A

6、BB3112.將構(gòu)造的將構(gòu)造的NFA確定化確定化 注意注意：遇到空字()需要忽略該轉(zhuǎn)移狀態(tài)。確定化后得到新的轉(zhuǎn)移轉(zhuǎn)換矩陣。理解書(shū)上的例子：（a|b)*(aa|bb)(a|b)*對(duì)應(yīng)的DFA 。4Y32615XaaaabbbbIaIbX,5,15,3,15,4,15,3,15,3,1,2,6,Y5,4,15,4,15,3,15,4,1,2,6,Y5,3,1,2,6,Y5,3,1,2,6,Y5,4,1,6,Y5,4,1,6,Y5,3,1,6,Y5,4,1,2,6,Y5,4,1,2,6,Y5,3,1,6,Y5,4,1,2,6,Y5,3,1,6,Y5,3,1,2,6,Y5,4,1,6,Y0121322

7、14335464564635123.最小化最小化把一個(gè)DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的?；?jiǎn)過(guò)程：將狀態(tài)分為兩組(終態(tài)組和非終態(tài)組)，分別將兩組進(jìn)行狀態(tài)轉(zhuǎn)換，如果轉(zhuǎn)換后的狀態(tài)屬于確定組，則該組狀態(tài)不可再劃分（歸結(jié)到一組）。13 判斷某給定文法是否為L(zhǎng)L(1)文法其條件為： (1)文法不含左遞歸。 (2)對(duì)于文法中每個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若 A 1 | 2 |。| n 則： FIRST(i) FIRST(j) = （i j ) (3) 對(duì)文法中每一個(gè)終結(jié)符A，若它存在某個(gè)候選首符集包含，則

8、 FIRST(A) FLLOW(A)= 一個(gè)文法若滿(mǎn)足以上條件，則稱(chēng)該文法G為L(zhǎng)L(1)文法文法.141.消除左遞歸消除左遞歸假定關(guān)于非終結(jié)符P的規(guī)則為 PP|其中, 不以P開(kāi)頭,則P的規(guī)則可改為下面的非直接左遞歸形式： PP PP|一般而言，假定P關(guān)于的全部產(chǎn)生式是 PP1| P2| Pm| 1| 2 | | n其中，每個(gè)都不等于，而每個(gè)都不以P開(kāi)頭，那末，消除P的直接左遞歸性就是把這些規(guī)則改寫(xiě)成： P | 1P| 2P| nP P1P| 2P| | mP| 例子，將文法例子，將文法 SS+aB|aB|+aB B *aB|*a 消除左遞歸？消除左遞歸？ SaBS|+aBS S +aBS| 1

9、52.2.消除回溯消除回溯( (提左公因子提左公因子) )如，對(duì)上例提取公共左因子， 將產(chǎn)生式改寫(xiě)成： B *aC C B|3.求first集合和follow集合求follow集方法：1)對(duì)文法開(kāi)始符號(hào)S，將#加入到Follow(S)中；2)若B A是文法G的一個(gè)產(chǎn)生式，則將First()-加入到Follow(A)中;3)若B A是文法G的一個(gè)產(chǎn)生式,或B A是文法G的一個(gè)產(chǎn)生式,且 ，則將Follow(B)加入到Follow(A)中；164.構(gòu)造預(yù)測(cè)分析表：構(gòu)造預(yù)測(cè)分析表：先求出first集和follow集， 1）假定A 是一個(gè)產(chǎn)生式，a First(),那么當(dāng)A是棧頂符號(hào)且將讀入a時(shí)， A

10、 就應(yīng)作為選用的侯選式， A 應(yīng)填入 MA,a中。 2）若A ，而 First() ,對(duì)每個(gè)a Follow(A), 在MA,a元素中應(yīng)填A(yù) (一般填A(yù) ).175.掌握輸入串的分析過(guò)程掌握輸入串的分析過(guò)程熟悉書(shū)上例子的預(yù)測(cè)分析過(guò)程。41注意：反向進(jìn)棧18給定文法，要求掌握：證明給定符號(hào)串是該文法的一個(gè)句型，并指出這個(gè)句型的短語(yǔ)、直接短語(yǔ)和句柄（通過(guò)語(yǔ)法樹(shù)確定）。短語(yǔ)：一顆子樹(shù)的樹(shù)葉全體；簡(jiǎn)單短語(yǔ)：一顆簡(jiǎn)單子樹(shù)的樹(shù)葉全體；句柄：最左邊的簡(jiǎn)單短語(yǔ)。要求掌握算符優(yōu)先文法。19句型：句型：E+F-T/F*i短語(yǔ)短語(yǔ): E+F-T/F*i，E+F，F(xiàn)，T/F*i，T/F，i 簡(jiǎn)單短語(yǔ)簡(jiǎn)單短語(yǔ): F，T

11、/F，i 句柄句柄: F E E - T E + T T * F F T / F i E+F-T/FE+F-T/F* *I I 的語(yǔ)法樹(shù)的語(yǔ)法樹(shù)注：先由給定的句型畫(huà)出語(yǔ)法樹(shù)20求各非終結(jié)符P的首終結(jié)符集和尾終結(jié)符集通過(guò)檢查G的每個(gè)產(chǎn)生式的每個(gè)候選式，可以找出滿(mǎn)足a=b的終結(jié)符對(duì)。為了找出所有滿(mǎn)足關(guān)系的終結(jié)符對(duì)，我們需要對(duì)G的每個(gè)非終結(jié)符P 構(gòu)造兩個(gè)集合首終結(jié)符集FIRSTVT(P)和尾終結(jié)符集LASTVT(P): FIRSTVT(P)=a | P+a或P +Qa,aVT而 Q VN LASTVT(P)=a | P+a或P +aQ,aVT而 Q VN 有了這兩個(gè)集合后，就可以通過(guò)檢查每個(gè)產(chǎn)生式的

12、候選式確定滿(mǎn)足關(guān)系的所有終結(jié)符對(duì)。例如：假定有個(gè)產(chǎn)生式的一個(gè)候選式為aP 那么，對(duì)任何bFISTVT(P),我們有ab.21例：構(gòu)造下面文法的算符優(yōu)先表。 S if Eb then E else E E E+T|T T T*F|F F i Eb b解：1）求各非終結(jié)符的首終結(jié)符集和尾終結(jié)符集。為了考慮語(yǔ)句的開(kāi)始和結(jié)束符號(hào)“”，對(duì)文法拓廣，加一個(gè)產(chǎn)生式SS FIRSTVT(S)=if LASTVT(S)=else,+,*,i FIRSTVT(E)=+,*,i LASTVT(E)=+,*,i FIRSTVT(T)=*,i LASTVT(T)=*,i FIRSTVT(F)=i LASTVT(F)=i

13、 FIRSTVT(Eb )=b LASTVT(Eb)=b22 2)填寫(xiě)算符優(yōu)先表# b i*+ else then if # bi*+elsethen if 左 右23掌握概念：語(yǔ)法制導(dǎo)翻譯的概念語(yǔ)法制導(dǎo)翻譯：對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析，構(gòu)造語(yǔ)法分析樹(shù)，然后根據(jù)需要遍歷語(yǔ)法樹(shù)并在語(yǔ)法樹(shù)的各結(jié)點(diǎn)處按語(yǔ)義規(guī)則進(jìn)行計(jì)算。這種由源程序的語(yǔ)法結(jié)構(gòu)得到翻譯結(jié)果的處理方法稱(chēng)為語(yǔ)法制導(dǎo)翻譯。24 要求掌握：寫(xiě)出表達(dá)式的后綴式、三元式、四元式、間接三元式。 布爾表達(dá)式的翻譯。 控制語(yǔ)句的翻譯。 25寫(xiě)出程序段運(yùn)行結(jié)果：寫(xiě)出程序段運(yùn)行結(jié)果：參數(shù)傳遞的方式分別采用傳值、傳地址、傳結(jié)果、傳名 。1)傳地址：把實(shí)在參數(shù)的

14、地址傳遞給相應(yīng)的形式參數(shù)。2)傳值：把實(shí)在參數(shù)的值計(jì)算出來(lái)傳遞給相應(yīng)的形式參數(shù)。3)傳名：把形參替換為相應(yīng)的實(shí)參。4)傳結(jié)果：每個(gè)形參有兩個(gè)單元，第一個(gè)單元存放實(shí)參地址，第二個(gè)單元存放實(shí)參的值。在過(guò)程體中對(duì)形參的引用看成是對(duì)第二個(gè)單元的直接訪問(wèn)，但在工作完成返回前必須把第二個(gè)單元的內(nèi)容存放到第一個(gè)單元所指的實(shí)參單元中。26值結(jié)果傳遞與地址傳遞的唯一區(qū)別在于別名的表現(xiàn)不同。例如，在以下的代碼中：void p (int x, int y)+x;+y;main()int a=1;p(a,a);return 0;在調(diào)用p之后，若使用了地址傳遞，則a的值為3；若使用了得結(jié)果傳遞，則a的值為2。27掌握概

15、念：靜態(tài)鏈和動(dòng)態(tài)鏈(P259)靜態(tài)鏈：從一個(gè)過(guò)程的當(dāng)前活動(dòng)記錄指向其直接外層的最新活動(dòng)記錄的地址（指針）。動(dòng)態(tài)鏈：指向當(dāng)前正在活動(dòng)的過(guò)程的活動(dòng)記錄的基地址，即指向調(diào)用該過(guò)程前正在運(yùn)行的過(guò)程的最新活動(dòng)記錄的基地址。28優(yōu)化分類(lèi)優(yōu)化分類(lèi)1、局部?jī)?yōu)化1）含義：局部?jī)?yōu)化是針對(duì)一段順序執(zhí)行語(yǔ)句序列的優(yōu)化。2）主要方法合并已知量刪除公共子表達(dá)式變量傳播與無(wú)用賦值刪除2、循環(huán)優(yōu)化1）含義：對(duì)程序中可能反復(fù)執(zhí)行的代碼序列的優(yōu)化2）主要方法：代碼外提；(哪些情況下可以外提？P290)強(qiáng)度削弱；刪除歸納變量29哪些情況下循環(huán)中的代碼可以外提？對(duì)于循環(huán)L中的每一不變運(yùn)算(運(yùn)算結(jié)果不改變)s：A:=B op C或A:

16、=B，檢查是否滿(mǎn)足兩個(gè)條件P290，則代碼s可以外提。30要求掌握基本塊的要求掌握基本塊的DAG圖的構(gòu)造：圖的構(gòu)造：理解講過(guò)的例子理解講過(guò)的例子例如：為下列四元式程序段構(gòu)造DAG.(1)T0:=3.14 (2) T1 :=2*T0 (3)T2:=R+r(4)A:= T1 *T2 (5)B:=A (6)T3:=2*T0(7)T4:=R+r (8)T5:=T3*T4 (9)T6:=R-r(10)B:=T5*T6n3Rn4rn8B*n13.14n26.28T1+n5T2n7-T6n6A*,T3,T4,T5T031DAG圖可以做到3種優(yōu)化：合并已知量;刪除無(wú)用賦值;檢查公共表達(dá)式。 利用DAG圖還原成

17、四元式序列：得四元式序列為：1)T0:=3.142) T1 :=6.283)T3:=6.284)T2:=R+r5)T4:=T26)A:=6.28*T27)T5:=A8)T6:=R-r9)B:=A*T6n2n3n66.28RA,T5+n8Bn4r*n13.14T1,T3n5n7T2,T4-T6*T032進(jìn)一步優(yōu)化根據(jù)有關(guān)變量在基本塊后面被引用的情況，可以進(jìn)一步刪除四元式序列中的無(wú)用賦值。情況1：若DAG中某結(jié)點(diǎn)上附加的標(biāo)識(shí)符，在該基本塊后面不會(huì)被引用，則不生成對(duì)該標(biāo)識(shí)符賦值的四元式。情況2：若某結(jié)點(diǎn)上不附有任何標(biāo)識(shí)符或者附加的標(biāo)識(shí)符在基本塊后面不會(huì)被引用，而且它沒(méi)有父結(jié)點(diǎn)，即基本塊內(nèi)和基本塊后都不會(huì)引用該結(jié)點(diǎn)的值，則不生成計(jì)算該結(jié)點(diǎn)的值的四元式。情況3：若有兩個(gè)相鄰的四元式A:=C op D和B:=A，其中第一個(gè)四元式計(jì)算出來(lái)的A值僅僅在第二個(gè)四元式中引用，則重寫(xiě)四元式時(shí)寫(xiě)為：B:=C op D。33設(shè)在基本塊后只有B被引用，經(jīng)進(jìn)一步優(yōu)化后DAG可重寫(xiě)為：1)S1:=R+r2)A:=6.28*S13)S2:=R-r4)B:=A*S2其中S1和S2是用來(lái)