編譯原理整理資料

《編譯原理整理資料》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、名詞解釋編譯：編譯程序的翻譯過(guò)程。詞法分析,語(yǔ)法分析,語(yǔ)義分析,中間代碼生成,代碼優(yōu)化,目標(biāo)代碼生成.語(yǔ)言：由文法G生成的語(yǔ)言記為L(zhǎng)(G),它是文法G的一切句子的集合:L(G)={x

2、S=>*x，其中S為文法的開(kāi)始符號(hào)，且x∈VT*}二義文法：若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱(chēng)這個(gè)文法是二義的?；蛘撸粢粋€(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則稱(chēng)這個(gè)文法是二義的。二義語(yǔ)言：如果產(chǎn)生上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則說(shuō)此語(yǔ)言是先天二義的。屬性文法：屬性文法(attributegrammar)是一個(gè)三元組：A=(G,V,F),其中G:是一個(gè)上

3、下文無(wú)關(guān)文法,V:有窮的屬性集,F:關(guān)于屬性的屬性斷言或一組屬性的計(jì)算規(guī)則(稱(chēng)為語(yǔ)義規(guī)則)。活動(dòng)記錄：一個(gè)過(guò)程的一次執(zhí)行所需要的信息，使用一個(gè)連續(xù)的存儲(chǔ)區(qū)來(lái)管理這個(gè)區(qū)（塊），叫做一個(gè)活動(dòng)記錄AR。詞法：規(guī)定什么是正確的單詞，boy不能寫(xiě)成byo等等。語(yǔ)法（文法）：是指一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合適的程序。（定義什么樣的符號(hào)序列是合法的）語(yǔ)義：自然語(yǔ)言中詞語(yǔ)的意義，邏輯形式系統(tǒng)中符號(hào)的解釋。（定義什么樣的符號(hào)序列是有含義的）句子：有文法G[s]，若S=>*x，且x∈VT*，則稱(chēng)x是文法G的句子。句型：有文法G[s]，若S=>*x，則稱(chēng)x是文法G的句型。語(yǔ)法樹(shù)：設(shè)

4、G=(VN,VT,P,S)為一cfg，若一棵樹(shù)滿足下列4個(gè)條件，則此樹(shù)稱(chēng)作G的語(yǔ)法樹(shù)。最左/最右推導(dǎo)：在推導(dǎo)的任何一步αTβ，其中α、β是句型，都是對(duì)α中的最左（右）非終結(jié)符進(jìn)行替換。自上而下分析：從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號(hào)串匹配的推導(dǎo)，或者說(shuō)，為輸入串尋找一個(gè)最左推導(dǎo)。自下而上分析：從輸入符號(hào)串開(kāi)始，逐步進(jìn)行歸約，直至歸約到文法的開(kāi)始符號(hào)。短語(yǔ)：存在文法G[s],S=>*αAδ且A=>+β，則稱(chēng)β是句型αβδ相對(duì)于非終結(jié)符A的短語(yǔ)。句柄：一個(gè)句型的最左直接短語(yǔ)稱(chēng)為該句型的句柄項(xiàng)目：在右端某一位置有圓點(diǎn)的G的產(chǎn)生式語(yǔ)法制導(dǎo)翻譯：在語(yǔ)法

5、分析的同時(shí)，執(zhí)行語(yǔ)義規(guī)則描述的動(dòng)作：16回填：一旦真假出口確定下來(lái)之后,用順著真鏈和假鏈把真假出口補(bǔ)上.拉鏈：為了記錄需回填地址的四元式,把需要回填的真出口的四元式拉成鏈,把需要回填家出口的四元式拉成一鏈,分別稱(chēng)作真鏈假鏈.目標(biāo)程序運(yùn)行時(shí)存儲(chǔ)區(qū)劃分圖：簡(jiǎn)答題：一．給出一個(gè)句子的最左，最右推導(dǎo)，語(yǔ)法樹(shù)。例:G[S]:S→aASA→SbAA→SSS→aA→ba最右推導(dǎo)：STaASTaAaTaSbAaTaSbbaaTaabbaa最左推導(dǎo)：STaASTaSbASTaabASTaabbaSTaabbaa任意推導(dǎo)：STaASTaSbASTaSbAaTaabAaTaabbaa語(yǔ)法

6、樹(shù)：二.判定文法的類(lèi)型（0，1，2，3型）：運(yùn)用知識(shí)：文法的類(lèi)型：通過(guò)對(duì)產(chǎn)生式施加不同的限制，Chomsky將文法分為四種類(lèi)型：0型文法：對(duì)任一產(chǎn)生式α→β，都有α∈(VN∪VT)+，β∈(VN∪VT)*1型文法：對(duì)任一產(chǎn)生式α→β，都有

7、β

8、≥

9、α

10、，僅僅S→ε除外162型文法：對(duì)任一產(chǎn)生式α→β，都有α∈VN3型文法：任一產(chǎn)生式α→β的形式都為A→aB或A→a，其中A∈VN，B∈VN，a∈VT*1型文法例：1型（上下文有關(guān)）文法文法G[S]：S→CDAb→bAC→aCABa→aBC→bCBBb→bBAD→aDC→aBD→bDD→bAa→bD2型文法例：2型（上下

11、文無(wú)關(guān)）文法文法G[S]：S→ABA→BS

12、0B→SA

13、13型文法例子G[S]：S→0A

14、1B

15、0A→0A

16、1B

17、0SB→1B

18、1

19、0三．正規(guī)式，正規(guī)文法，自動(dòng)機(jī)之間的轉(zhuǎn)換正規(guī)式到正規(guī)文法的轉(zhuǎn)換運(yùn)用知識(shí)：對(duì)?上的正規(guī)式r,存在一個(gè)RG=(VN,VT,P,S)：L(G)=L(r)(R.0)VT=?,S?VN,生成正規(guī)產(chǎn)生式：S?r(R.1)對(duì)形如A?r1r2的正規(guī)產(chǎn)生式：A?r1BB?r2B?VN(R.2)對(duì)形如A?r*r1的正規(guī)產(chǎn)生式：A?rAA?r1(R.3)對(duì)形如A?r1?r2的正規(guī)產(chǎn)生式:A?r1A?r2不斷應(yīng)用(R.x)做變換，直到每個(gè)產(chǎn)生式右端至多有一個(gè)V

20、N例子r=a(a?d)*解：(1)S?a(a?d)*(S?r)(2)S?aAA?(a?d)*(A?r1B,B?r2)(3)A?(a?d)A(A?rA,A?r1)A?eG[s]:S?aAAe?VT={a,d}A?aBVN={S,A}A?dB16正規(guī)文法到正規(guī)式的轉(zhuǎn)換運(yùn)用知識(shí)：對(duì)G=(VN,VT,P,S),存在一個(gè)?=VT上的正規(guī)式r:L(r)=L(G)A?xB,B?y形成正規(guī)式A=xyA?xA?y形成正規(guī)式A=x*yA?x?y形成正規(guī)式A=x?y例子：由NFAM構(gòu)造正規(guī)式r運(yùn)用知識(shí)：從Σ上的一個(gè)NFAM，構(gòu)造Σ上的,一個(gè)正規(guī)式r，使得L(M)=L(r)的方法。由N