編譯原理整理資料

《編譯原理整理資料》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

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

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

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

4、列4個條件，則此樹稱作G的語法樹。最左/最右推導(dǎo)：在推導(dǎo)的任何一步αTβ，其中α、β是句型，都是對α中的最左（右）非終結(jié)符進(jìn)行替換。自上而下分析：從文法的開始符號出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號串匹配的推導(dǎo)，或者說，為輸入串尋找一個最左推導(dǎo)。自下而上分析：從輸入符號串開始，逐步進(jìn)行歸約，直至歸約到文法的開始符號。短語：存在文法G[s],S=>*αAδ且A=>+β，則稱β是句型αβδ相對于非終結(jié)符A的短語。句柄：一個句型的最左直接短語稱為該句型的句柄項目：在右端某一位置有圓點(diǎn)的G的產(chǎn)生式語法制導(dǎo)翻譯：在語法分析的同時，執(zhí)行語義規(guī)則描述的動作：16回填：一旦真假出口確定下來之后,用順著

5、真鏈和假鏈把真假出口補(bǔ)上.拉鏈：為了記錄需回填地址的四元式,把需要回填的真出口的四元式拉成鏈,把需要回填家出口的四元式拉成一鏈,分別稱作真鏈假鏈.目標(biāo)程序運(yùn)行時存儲區(qū)劃分圖：簡答題：一．給出一個句子的最左，最右推導(dǎo)，語法樹。例:G[S]:S→aASA→SbAA→SSS→aA→ba最右推導(dǎo)：STaASTaAaTaSbAaTaSbbaaTaabbaa最左推導(dǎo)：STaASTaSbASTaabASTaabbaSTaabbaa任意推導(dǎo)：STaASTaSbASTaSbAaTaabAaTaabbaa語法樹：二.判定文法的類型（0，1，2，3型）：運(yùn)用知識：文法的類型：通過對產(chǎn)生式施加不同的限制，Choms

6、ky將文法分為四種類型：0型文法：對任一產(chǎn)生式α→β，都有α∈(VN∪VT)+，β∈(VN∪VT)*1型文法：對任一產(chǎn)生式α→β，都有

7、β

8、≥

9、α

10、，僅僅S→ε除外162型文法：對任一產(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型（上下文無關(guān)）文法文法G[S]：S→ABA→BS

11、0B→SA

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

13、1B

14、0A→0A

15、1B

16、0SB→1B

17、1

18、

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

20、1)A?eG[s]:S?aAAe?VT={a,d}A?aBVN={S,A}A?dB16正規(guī)文法到正規(guī)式的轉(zhuǎn)換運(yùn)用知識：對G=(VN,VT,P,S),存在一個?=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)用知識：從Σ上的一個NFAM，構(gòu)造Σ上的,一個正規(guī)式r，使得L(M)=L(r)的方法。由N