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

《編譯原理復(fù)習(xí)》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理復(fù)習(xí)（26頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,編譯原理總復(fù)習(xí),Click to edit Master title style,Click to edit Master te

2、xt styles,Second level,Third level,Fourth level,Fifth level,*,編譯原理,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,編譯原理總復(fù)習(xí),Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fif

3、th level,*,編譯原理,期末總復(fù)習(xí),考試題型,一單項(xiàng)選擇,(2,10=20,),二簡(jiǎn)答題,(,6,3,=,18,),三自動(dòng)機(jī)轉(zhuǎn)換題,(15,),四中綴式轉(zhuǎn)化后綴式和四元式,(,6,2=1,2,),五用,DAG,進(jìn)行局部?jī)?yōu)化,(10,),六綜合題,(25,),編譯原理總復(fù)習(xí),知識(shí)要點(diǎn),第,1,章,編譯程序:,compiler,能將一種計(jì)算機(jī),高級(jí)語(yǔ)言,程序(,源語(yǔ)言,程序)轉(zhuǎn)換成另一種等價(jià)的計(jì)算機(jī),低級(jí)語(yǔ)言,程序(,目標(biāo)語(yǔ)言,程序),編譯原理總復(fù)習(xí),編譯程序工作過程的各個(gè)階段：,詞法分析器,語(yǔ)法分析器,語(yǔ)義分析器,源程序,中間代碼生成器,代碼優(yōu)化器,目標(biāo)代碼生成器,目標(biāo)程序,出錯(cuò)管理器,

4、符號(hào)表管理器,編譯原理總復(fù)習(xí),第,3,章,文法,G=,（,V,N,，,V,T,，,P,，,Z,）,V,N,：非終結(jié)符號(hào)集,V,T,：終結(jié)符號(hào)集,P,：產(chǎn)生式或規(guī)則的集合,Z,：開始符號(hào)（識(shí)別符號(hào)）,ZV,N,規(guī)范推導(dǎo)：,即最,右,推導(dǎo),若符號(hào)串,中有兩個(gè)以上的非終結(jié)符時(shí)，對(duì)推導(dǎo)的每一步堅(jiān)持把,中的最右非終結(jié)符進(jìn)行替換。,編譯原理總復(fù)習(xí),文法,GZ,所產(chǎn)生的,所有句子的集合,文法,GZ,（,1,）,句型,：,x,是句型,Z,x,且,x,V*,；,*,*,（,2,）,句子,：,x,是句子,Z,x,且,x,V,T,*,；,*,（,3,）,語(yǔ)言,：,L,（,GZ,）,=x|Z,x,，,x,V,T,*,

5、；,即：句型是由文法開始符號(hào)推導(dǎo)出來的,由終結(jié)符和非終結(jié)符組成的符號(hào)串。,即：句子是由文法開始符號(hào)推導(dǎo)出來的,由終結(jié)符組成的符號(hào)串。,編譯原理總復(fù)習(xí),給定文法，判斷給定輸入串是否為該文法的句子或句型。并指出該句子或句型的：,短語(yǔ),簡(jiǎn)單短語(yǔ),句柄,編譯原理總復(fù)習(xí),第,4,章,詞法分析程序的主要任務(wù)：,對(duì)構(gòu)成源程序的字符串從左到右的掃描，逐個(gè)字符地讀入源程序字符，按照構(gòu)詞規(guī)則切分成一個(gè)一個(gè)具有獨(dú)立意義的單詞，并識(shí)別其正確性，再交給下一階段進(jìn)行語(yǔ)法分析。,描述詞法的機(jī)制是,正則表達(dá)式,識(shí)別機(jī)制是,有窮狀態(tài)自動(dòng)機(jī),編譯原理總復(fù)習(xí),為正規(guī)式,(0|1),*,0(0|1),構(gòu)造一個(gè)等價(jià)的有窮自動(dòng)機(jī)。,將此

6、自動(dòng)機(jī)轉(zhuǎn)換為確定自動(dòng)機(jī),DFA,。,例：,編譯原理總復(fù)習(xí),S,A,B,C,Z,0,1,0,0,1,第,5,章,語(yǔ)法分析的主要工作：,識(shí)別由詞法分析給出的單詞序列是否為給定文法的正確句子（程序）。,語(yǔ)法分析常用的方法：,自頂向下的語(yǔ)法分析和自底向上的語(yǔ)法分析兩大類。,編譯原理總復(fù)習(xí),三個(gè)重要集合：,First,集,Follow,集,Select,集,注：三,種集合均為,終結(jié)符集,編譯原理總復(fù)習(xí),SELECT(,A,)=,(FIRST(),),FOLLOW,(A),，,否則,FIRST(),，,當(dāng),時(shí),*,確定的自頂向下語(yǔ)法分析：,要求文法必須是,LL(1),文法,LL(1),文法的判別,若非終結(jié)

7、符,A,的兩個(gè)不同產(chǎn)生式，,A,A,；,滿足：,SELECT(A,)SELECT(A,)=,編譯原理總復(fù)習(xí),第,7,章,LR,分析法,前綴：,一個(gè)符號(hào)串的前綴是指該串的任意首部（包括,）。,可歸前綴：,是指規(guī)范句型的一個(gè)前綴，這種前綴,包含句柄且不含句柄之后的任何符號(hào),。,活前綴：,可歸前綴的任意首部。,編譯原理總復(fù)習(xí),移進(jìn)項(xiàng)目：,A,.,b,其中,b,為終結(jié)符,，,可為,待約項(xiàng)目：,A,.,B,其中,B,為非終結(jié)符,，,可為,歸約項(xiàng)目：,A,.,接受項(xiàng)目：,SS,.,LR(0),分析和,SLR(1),分析,編譯原理總復(fù)習(xí),分析法過程步驟：,拓廣文法,G,：引起一個(gè)新的開始符號(hào),S,，且將,S

8、,S,作為第,0,個(gè)產(chǎn)生式添加到文法,G,中，并對(duì)所有產(chǎn)生式進(jìn)行編號(hào)。,構(gòu)造識(shí)別活前綴的,DFA,。,判斷是否存在,移進(jìn)歸約,沖突或,歸約歸約,沖突。,若無沖突，則為,LR(0),文法，構(gòu)造,LR(0),分析表；,若有沖突，判斷是否為,SLR(1),文法,編譯原理總復(fù)習(xí),SLR(1),文法判定：,存在如下項(xiàng)目集,(,狀態(tài),)I:,I=,X,.,b,A,.,B,.,其中,bV,T,I,中含有,移進(jìn)歸約,和,歸約歸約,沖突。,若滿足：,FOLLOW(A),FOLLOW,(B)b=,則為,SLR(1),文法。,編譯原理總復(fù)習(xí),SLR(1),分析表的構(gòu)造規(guī)則：,(1),項(xiàng)目集,Ii,中若有形如,A.X

9、,的項(xiàng)目，且有,GO(,Ii,X,),=Ij,若,X,為一終結(jié)符號(hào),a,時(shí)，則置,ACTION,I,a,=Sj,;,若,X,為一非終結(jié)符號(hào)時(shí)，則置,GOTO,i,X,=j,；,(2),若有歸約項(xiàng)目,A,.,屬于,Ii,設(shè),A,為文法第,j,個(gè)行產(chǎn)生式，則對(duì)任何,屬于,FOLLOW(A),的,輸入符號(hào),a,，置,ACTION,i,a,=Rj,；,(3),若有接受項(xiàng)目,SS,.,屬于,Ii,則置,ACTIONi,#,=acc,。,(4),在分析表,凡不能按上述規(guī)則填入信息的元素,均置為“出錯(cuò)”。,編譯原理總復(fù)習(xí),第,8,章,語(yǔ)義分析的任務(wù),對(duì)于所寫的源程序，在詞法分析和語(yǔ)法分析的基礎(chǔ)上，進(jìn)一步分析

10、其含義，在理解含義的基礎(chǔ)上，為生成相應(yīng)的目標(biāo)代碼做好準(zhǔn)備或直接生成目標(biāo)代碼。,語(yǔ)義描述方法,屬性文法,語(yǔ)義的處理方法,語(yǔ)法制導(dǎo)翻譯,編譯原理總復(fù)習(xí),屬性文法,屬性文法形式的定義為一個(gè)三元組,AG,，,AG=,（,G,，,V,，,E,）。其中,G,為一個(gè)上下文無關(guān)文法；,V,為屬性的有窮集；,E,為一組語(yǔ)義規(guī)則。,語(yǔ)法制導(dǎo)翻譯,語(yǔ)法制導(dǎo)翻譯就是在語(yǔ)法分析的過程中，當(dāng)進(jìn)行推導(dǎo)或歸約時(shí)同步完成附加在所使用的產(chǎn)生式上的語(yǔ)義規(guī)則描述的動(dòng)作，從而實(shí)現(xiàn)語(yǔ)義處理。,屬性分為兩類：綜合屬性和繼承屬性,綜合屬性,：,如果,b,是,A,的屬性，,c,1,c,2,c,k,是產(chǎn)生式右部文法符號(hào)的屬性或,A,的其它屬性。

11、,繼承屬性,：如果,b,是產(chǎn)生式右部某個(gè)文法符號(hào),X,的屬性。,編譯原理總復(fù)習(xí),給定文法,S,及相應(yīng)翻譯方案為：,(0),S,S,print:“a,”,(1),S,r,D,print:“b,”,(2),D,D,i,print:“c,”,(3),D,i,print:“d,”,1.,符號(hào)串,ri,i,i,是不是該文法的一個(gè)句子，請(qǐng)證實(shí)。,2.,若是句子，寫出其所有的短語(yǔ)、簡(jiǎn)單短語(yǔ)，以及句柄。,3.,構(gòu)造識(shí)別該文法的活前綴的,DFA,，并判斷該文法是,LR(0),還是,SLR(1),。,4.,對(duì)于,ri,i,i,這個(gè)輸入符號(hào)串，該翻譯方案的輸出是什么？,編譯原理總復(fù)習(xí),例：,S,r,S,D,D,i,

12、，,i,D,i,，,中間代碼的形式,幾種常用的中間表示,：,后綴表示：逆波蘭記號(hào),三地址代碼：三元式、四元式,圖形表示：樹形表示,編譯原理總復(fù)習(xí),（,b*cd/c)*a,a,cc,+e,d,例：,第,9,章,符號(hào)表的作用和地位,語(yǔ)義檢查的依據(jù),目標(biāo)代碼生成階段地址分配的依據(jù),編譯原理總復(fù)習(xí),第,11,章,基本塊,：是指程序中一順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句。,基本塊的,DAG,：,無環(huán)路有向圖,編譯原理總復(fù)習(xí),t1,S,R,t2,S,R,A,t1*t2,B,A,t3,S,R,t4,t2*t3,B,t4,(1),畫出,DAG,圖；,(2),假設(shè)基本塊出口時(shí)只有,A,、,B,還被引用，請(qǐng)寫出優(yōu)化后的三地址代碼序列。,編譯原理總復(fù)習(xí),有基本塊：,例：,編譯原理總復(fù)習(xí),1.,編譯程序的主要組成部分有哪些？,2.,詞法分析的主要任務(wù)是什么？,3.,簡(jiǎn)述,DFA,與,NFA,有何區(qū)別？,4.,自底向上的語(yǔ)法分析方法的基本思想是什么,?,5.,何謂語(yǔ)法制導(dǎo)翻譯？,6.,常用的中間語(yǔ)言表示形式有哪些？（至少寫出三種）,簡(jiǎn)答題,