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

1、一、 概述1. 編譯方式與解釋方式區(qū)別：是否生成目標(biāo)代碼2. 編譯程序總框架二、 詞法分析1. 狀態(tài)轉(zhuǎn)換圖的功能：識別（接受）一定的符號串（單詞）2. 狀態(tài)轉(zhuǎn)換圖的程序?qū)崿F(xiàn)的思路：為每個狀態(tài)結(jié)點(diǎn)都編寫一個子程序3. 字母表的概念：一般用表示4. 閉包的概念：閉包V*中的每個字都是由V中的字經(jīng)過若干次連接而成的5. 正則閉包V+的概念：是V上所有符號串的集合6. *定義：表示上所有字的全體，空字也包括在其中7. +空字不包含，非8. ， ，之間的區(qū)別9. 所對應(yīng)的正規(guī)集為10. 正規(guī)式與正規(guī)集的定義：知道如何用正規(guī)式表示一個正規(guī)集11. 簡述NFA和DFA的定義與區(qū)別12. 若M的某些結(jié)點(diǎn)既是初

2、態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)，或者存在一條從某初態(tài)結(jié)點(diǎn)到某個終態(tài)結(jié)點(diǎn)的通路，那么空字可為M所識別13. 正規(guī)式與優(yōu)先自動機(jī)的等價性14. 定理2.對于上的每一個正規(guī)式V，存在一個上的DFA M，使得L(M)=L(V)15. DFA M的化簡的概念和方法：終態(tài)和非終態(tài)是可區(qū)別的，因?yàn)榻K態(tài)可以讀出空字，而非終態(tài)不能讀出空字16. 課后作業(yè)一個例題17. 構(gòu)造一個DFA，它接受=x，y上所有倒數(shù)第二個字符為y的字符串三、 語法分析（1）基本定義1. 上下文無關(guān)文法的定義2. 句型、句子的概念3. 文法和語言的對應(yīng)關(guān)系，給出文法構(gòu)造語言，文法G產(chǎn)生的句子的全體是該文法的語言4. 語法分析樹與二義性：判斷文法的二

3、義性方法：如果一個文法含有二義性的句子（對應(yīng)兩棵不同的語法樹），則稱該文法是二義性文法5. 3型文法是正規(guī)文法、正則文法、線性文法6. 2型文法也稱為稱為上下文無關(guān)文法7. 若一個文法是遞歸的，則由它產(chǎn)生的語言的句子個數(shù)是無限的（2）自上而下8. 文法左遞歸的定義9. 消除文法的左遞歸的方法：直接左遞歸10. 消除回溯的方法：提取公共左因子11. 遞歸下降分析法的概念，應(yīng)滿足什么條件？12. 遞歸下降法對文法的每個非終結(jié)符構(gòu)造一個相應(yīng)的子程序13. 預(yù)測分析法：給文法構(gòu)造預(yù)測分析表：消除左遞歸、消除回溯、First集、Follow集。舉例子時，便成Sa|aS|（T）（3）自下而上14. 短語、

4、直接短語的概念15. 句柄的概念（一個句型的最左直接短語）16. 規(guī)范歸約（最左）、規(guī)范推導(dǎo)（最右）、規(guī)范句型17. 規(guī)范歸約的關(guān)鍵問題是尋找句柄18. 在規(guī)范歸約中，可歸約串必出現(xiàn)在棧頂19. 算符文法、算符優(yōu)先文法的概念，如何判斷20. 構(gòu)造算符優(yōu)先關(guān)系表、Fisrtvt、lastvt集合，可不考慮#號21. 素短語：算符優(yōu)先歸約的關(guān)鍵問題是尋找最左素短語22. 算符優(yōu)先法尤其適用于表達(dá)式的分析23. 給出文法G（P） X jYjY kZ|iZ Yid 該文法是否為算符優(yōu)先文法？請根據(jù)FIRSTVT、LASTVT集合構(gòu)造算符優(yōu)先關(guān)系表說明之24. 欲構(gòu)造行之有效的自上而下分析器，則必須消除

5、文法中含有的左遞歸25. LR分析法屬于自底向上分析方法26. 從文法出發(fā)構(gòu)造LR（0）分析表的步驟四、語義分析1. 綜合屬性和繼承屬性概念五、中間代碼生成1. 中間代碼是一種面向語法，易于翻譯成目標(biāo)代碼的代碼2. 后綴式（逆波蘭式）的概念3. 逆波蘭式中各運(yùn)算法出現(xiàn)的順序與實(shí)際運(yùn)算順序一致4. 后綴式與抽象語法樹（表達(dá)式樹）的關(guān)系5. DAG的含義6. 四元式表示方法，聯(lián)系時通過臨時變量，可以翻譯各種語句7. 將賦值語句表示成后綴式和四元式六、代碼優(yōu)化1. 簡述代碼優(yōu)化的原則與優(yōu)化的級別，并列舉三種常用的優(yōu)化技術(shù)2. 基本塊、流圖的概念，如何畫、節(jié)點(diǎn)對應(yīng)基本塊3. 局部優(yōu)化的方法，DAG是對

6、基本塊進(jìn)行優(yōu)化的有效工具4. 不變運(yùn)算的代碼外提的條件5. 循環(huán)優(yōu)化中的強(qiáng)度削弱的含義七、目標(biāo)代碼生成1. 編譯程序生成的目標(biāo)程序種類(309)一：概述1. 編譯方式與解釋方式區(qū)別在于是否生成目標(biāo)代碼，編譯方式生成了目標(biāo)代碼。2. 編譯程序總框架二：詞法分析1. 狀態(tài)轉(zhuǎn)換圖的功能：識別（接受）一定的符號串（單詞）上圖是一個很簡單的狀態(tài)轉(zhuǎn)換圖。上圖代表：狀態(tài)0通過X弧可以轉(zhuǎn)換到狀態(tài)1，通過Y弧可以轉(zhuǎn)換到狀態(tài)22.字母表的概念：一個由有限元素組成的集合，每個元素稱為一個符號或一個字，一般用表示一個字母表例： = a , b , c元素：a，b，c 字母表中的字可拼接在一起構(gòu)成一個序列，如aa,ab

7、,bc,bbc等，符號的順序不同所代表的序列也不同。不包含任何字符的序列稱為空字，用來表示另外有幾個概念必須先了解：字(符號串)的連接設(shè)x和y是兩個字(符號串)，則定義xy為他們的連接例：ab和ba連接是abba注: (1)（空字）是連結(jié)運(yùn)算的恒等元素x = x= x (2)字(符號串)的n次連接xn = xxxx規(guī)定x0 = x1= x，x2=xx，x3= xxx集合的(連接)積設(shè)U和V是兩個“字(符號串)的集合”，則定義UV為他們的(連接)積 UV=xy|xU且yV例：設(shè)U=a, ab, V=b, ba, 則UV=ab, aba, abb, abba集合V的n次(連接)積記為： Vn =

8、V V VV n個 規(guī)定 V0= 例：設(shè)V=a, b，那么V0= V1= a,bV2=VV=aa,ab,ba,bbV3=VVV=V2V=aaa,aba,baa,bba,aab,abb,bab,bbb3.閉包的概念：設(shè)V是一個字（符號串）的集合，則V的閉包定義為V*， V* = V0V1V2注：閉包V* 中的每個字都是由V中的字經(jīng)過有限次連接而成的正則閉包V+的定義為V+ = VV* 閉包與正則閉包的差別在于，閉包里是含有的，因?yàn)殚]包里有集合V0 ，而正則閉包由于在閉包的基礎(chǔ)上又連接了一個V，所以正則閉包里是沒有空字的。*定義：表示上所有字的全體，空字也包括在其中+表示上所有字的全體，但不包括4

9、.， ，之間的區(qū)別（小題） 空字：表不包含任示何字符的序列稱 ：表示一個空集： 表示含有空字的集合5.正規(guī)式與正規(guī)集的定義：我們可以把具有相同特征的字放在一起組成一個集合，即所謂的正規(guī)集然后使用一種形式化的方法來表示正規(guī)集，即所謂的正規(guī)式正規(guī)式是描述單詞結(jié)構(gòu)的一種形式；正規(guī)集是該類單詞的全集。舉例對于下面的例子，大家應(yīng)該好好思考一下后面4個的含義，對做大題是很有幫助的。做大題時，題目通常會給你一個實(shí)際問題，你需要先把他要實(shí)現(xiàn)的功能抽象成一個正規(guī)集，再用正規(guī)式表達(dá)出來，才能繼續(xù)做后面的步驟。所對應(yīng)的正規(guī)集為6. 簡述有限自動機(jī)NFA和DFA的定義與區(qū)別NFA代表非確定的有限自動機(jī)；DFA代表確定

10、的有限自動機(jī)所謂的有限自動機(jī)，其實(shí)他并不代表任何實(shí)體的機(jī)器，只是一種數(shù)學(xué)模型而已。就像函數(shù)、數(shù)列是一種數(shù)學(xué)模型一樣。函數(shù)通過函數(shù)表達(dá)式實(shí)現(xiàn)他的功能：你給他一個自變量，他能根據(jù)表達(dá)式求出因變量的值。而有限自動機(jī)是通過狀態(tài)轉(zhuǎn)換圖來實(shí)現(xiàn)功能，你給他一個初始狀態(tài)和一個輸入符號，他能根據(jù)你輸入的這個符號將原狀態(tài)轉(zhuǎn)換到另一個狀態(tài)，用他來模擬計算機(jī)的識別功能。下面簡單介紹一下DFA（確定的有限自動機(jī)）的五元式表示法：(重要)定義：一個確定有限自動機(jī)（DFA）M是一個五元式：M = (S, , f, s0, F)，其中1) S是一個有限的狀態(tài)集合，它的每個元素我們稱為一個狀態(tài)2) 是一個有窮的輸入符號的字母表

11、，它的每個元素我們稱為一個輸入字符3) f是從 S× S的單值部分映射4) s0是S的一個元素，為初始狀態(tài)，它是唯一的5) 狀態(tài)集合F是終止?fàn)顟B(tài)的集合，它是S的子集(可空)一個非確定有限自動機(jī)（NFA）M是一個五元式M = (S, , f, S0, F)，其中S是一個有限的狀態(tài)集合，它的每個元素我們稱為一個狀態(tài)是一個有限的輸入符號的字母表，它的每個元素我們稱為一個輸入字符f是從S×*2S 的部分映射，其中，2S表示S的冪集合（所有S的子集組成的集合）（f是非單值的àM是非確定）狀態(tài)集合S0是初始狀態(tài)集合，它是S的子集狀態(tài)集合F是終止?fàn)顟B(tài)的集合，它是S的子集注：DF

12、A和NFA的區(qū)別在于（3）和（4），其他幾點(diǎn)都差不多，這是有可能出簡答題的，大家要記住他們的區(qū)別和聯(lián)系7.DFA的識別功能對于*中任何字，如果存在一條從初態(tài)結(jié)點(diǎn)到某個終態(tài)結(jié)點(diǎn)的道路，這條路上所有的標(biāo)識符連成的字等于 ，則可被DFA M所識別(接受，讀出)若M的某些結(jié)點(diǎn)既是初態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)，或者存在一條從某初態(tài)結(jié)點(diǎn)到某個終態(tài)結(jié)點(diǎn)的通路，那么空字可為M所識別8.狀態(tài)轉(zhuǎn)換圖的分裂規(guī)則（大題步驟）例子：(這里Y有兩個圈圈代表他是最終狀態(tài)的點(diǎn))劃到最后要求每條弧上都只有一個字母或者數(shù)字9._CLOSURE(I) 和Ia =_CLOSURE(J)的構(gòu)造方法（大題步驟）這里先需要了解幾個定義我們假設(shè)有某

13、個狀態(tài)集I，這個集合中含有不同的狀態(tài)。定義1 狀態(tài)集I的a弧轉(zhuǎn)換：move( I, a ) ¨ 是一個狀態(tài)集，是從I中的狀態(tài)出發(fā)經(jīng)過一條a弧到達(dá)的狀態(tài)的全體。定義2 狀態(tài)集I的(空字)閉包：_CLOSURE( I ) 是一個狀態(tài)集，由兩部分組成:n 狀態(tài)集I中的所有原狀態(tài)。n 從I中的狀態(tài)出發(fā)經(jīng)過任意條弧，所能到達(dá)的狀態(tài)的全體。定義3 Ia =_CLOSURE( move( I, a ) )¨ 是一個狀態(tài)集。下面給出一個實(shí)例：例：有如下一個狀態(tài)轉(zhuǎn)換圖假定 I=1, 2，求Ia = ？J=move(I,a)=5,4,3Ia=_CLOSURE(J) = 5,4,3,6,2,7,

14、8（即先做a弧轉(zhuǎn)換，將求得的狀態(tài)再求空字閉包）本知識點(diǎn)旨在讓大家掌握在知道了I這個狀態(tài)集合后，怎樣求Ia10.如何用子集法將非確定的有限自動機(jī)確定化（大題步驟）方法：先畫一張表IIaIb_CLOSURE(S0)ABCBDECFG1.這張表的首行上首列上固定是大寫字母I2.表格后面有幾列，取決于這個有限自動機(jī)的輸入符號數(shù)量，有幾個輸入符號就有幾列，這里假設(shè)Ia Ib 的下標(biāo)a b代表這個有限自動機(jī)的輸入符號3.第二行的第一列也是固定的，S0代表的是這個有限自動機(jī)的初始狀態(tài),即求S0的空字閉包，我們假設(shè)求出來的狀態(tài)集合是A4.將A所對應(yīng)的Ia Ib 分別求出來，我們假設(shè)是B和C5.如果B和C都分別

15、于A不同，需要將B，C作為新的狀態(tài)集合加入到第一列中6.繼續(xù)求出B和C所對應(yīng)的Ia Ib ，再檢驗(yàn)：對于DEFG這四個狀態(tài)集合，有沒有與ABC是不同的，如果有，加入到第一列的下面，再繼續(xù)計算，如果與前面的ABC相同就不再需要加入了。7.按照這樣的方法一直進(jìn)行下去，知道第一列不再有新的狀態(tài)集合加入了，這個表就構(gòu)造好了。8.再畫一張表，與上面的表相對應(yīng)Sab01234134224319.對于上面這種表的構(gòu)造方法很簡單，大家也可以不另外畫表，而直接標(biāo)在原來的表中這種表來源是，在原來表的第一列上分別表上s01234···，a和b不變，然后按照第一列中數(shù)字所對應(yīng)的狀態(tài)集，依

16、次對應(yīng)在后面的列上標(biāo)上相應(yīng)數(shù)字。例如第一列中B對應(yīng)1，C對應(yīng)2，那么將第二列第二行中的B也標(biāo)上1，第三列第二行中的C標(biāo)上2，等等。10.畫出下面的這個表或在原表中標(biāo)好后，就可以按照這個表畫出狀態(tài)轉(zhuǎn)換圖了，例如，0狀態(tài)通過a弧轉(zhuǎn)換成1狀態(tài)，通過b弧轉(zhuǎn)換成2狀態(tài)；1狀態(tài)通過a弧轉(zhuǎn)換成3狀態(tài)，通過b弧轉(zhuǎn)換成4狀態(tài)，等等。畫出這個狀態(tài)轉(zhuǎn)換圖后，就完成了一個非確定有限自動機(jī)的確定化。11.有限自動機(jī)DFA的化簡整體的思路如下： 1.將第10步中得到的已經(jīng)確定的DFA中的所有狀態(tài)分為兩組，一組為終態(tài)節(jié)點(diǎn)，一組為非終態(tài)節(jié)點(diǎn)。需要補(bǔ)充的是，在上一步構(gòu)造的表格中，s那一列的節(jié)點(diǎn)哪些是終態(tài)哪些是非終態(tài)呢？這需要看

17、你最初構(gòu)造的正規(guī)式中的哪個是終態(tài)節(jié)點(diǎn)了。例如在下面的12中，Y為終態(tài)節(jié)點(diǎn)，那么在以上的表格中只要是含有Y元素的狀態(tài)集合都將成為終態(tài)集。2.將每個分組檢驗(yàn)，看他們是否還能分割，檢驗(yàn)的方法實(shí)在難以用文字描述清楚，請大家看下面的實(shí)際例題，自己領(lǐng)會。3.每個分組都不能再分割后，若還含有大于2個元素的分組，則這個分組中的所有狀態(tài)都是等價的，可以用其中的一個代替他們，代替的方法是：假設(shè)用狀態(tài)1代替狀態(tài)2，則把狀態(tài)2及其引出去的弧全部刪去，并把原來指向狀態(tài)2的弧指向狀態(tài)1下面是老師復(fù)習(xí)PPT上的一個例子，這是一個較為復(fù)雜的例子，可能會看不懂，大家多問一問周圍會的同學(xué)，期末考試時，肯定不會出這么復(fù)雜，通常在將

18、終態(tài)節(jié)點(diǎn)和非終態(tài)節(jié)點(diǎn)區(qū)分開后，剩下的就已經(jīng)快分好了，所以大家不用太擔(dān)心，化簡也是有可能不考察的，大家看清題目要求。例：12.例題：構(gòu)造一個DFA，它接受=x，y上所有倒數(shù)第二個字符為y的字符串說明一下這道題的解題思路和步驟，希望大家能真正明白整個解題的過程，讓大家真正明白這樣的一道大題是應(yīng)該怎么做的.上面這道題的分析思路是1.根據(jù)他所描述的功能，構(gòu)造出一個正規(guī)式，正規(guī)式先給大家：（x|y）*y (x|y)（其實(shí)對于這樣的大題最關(guān)鍵就是構(gòu)造對正規(guī)式，大家一定把老師最后的PPT上所有的例題是如何構(gòu)造正規(guī)式的都記下來！這一步做不出來后面的都沒分了！）2.構(gòu)造一個初始狀態(tài)X和和最終狀態(tài)Y，將正規(guī)式寫在

19、他們的轉(zhuǎn)換弧上。3.按照第8點(diǎn)中的分裂規(guī)則對他進(jìn)行分裂，分裂直到每一條轉(zhuǎn)換弧上都只含有一個字符4.分裂結(jié)束得到的一個狀態(tài)轉(zhuǎn)換圖實(shí)際上就是一個NFA（非確定的有限自動機(jī)）5.在掌握了第9點(diǎn)知識的前提下，就可以按照第10點(diǎn)說的步驟，將求得的NFA確定化6.得到確定化之后的狀態(tài)轉(zhuǎn)換圖，剩下的事情就是化簡了。也就是第11點(diǎn)當(dāng)中的只是看到這里強(qiáng)烈建議大家先動筆試一試上面這道例題，相信只要你認(rèn)真學(xué)習(xí)了前面的知識，做出來是沒有問題的，祝大家成功！三：語法分析（1）基本定義1.上下文無關(guān)文法的定義文法：是描述語言的語法結(jié)構(gòu)的形式規(guī)則（或稱語法規(guī)則）上下文無關(guān)文法概念:它所定義的語法范疇（或語法單位）是完全獨(dú)立

20、于這種范疇可能出現(xiàn)的環(huán)境的（與它所在的上下文無關(guān)）（重要！以下的概念一定要理解熟知?。┥舷挛臒o關(guān)文法G可定義為一個四元式(VT，VN，S，P) VT是終結(jié)符號集合，它的每個元素稱為終結(jié)符號，用小寫字母表示。VN是非終結(jié)符號集合，它的每個元素稱為非終結(jié)符號，用大寫字母表示。S是一個開始符號，是一個非終結(jié)符，至少在一個產(chǎn)生式作為左部出現(xiàn)P是一個產(chǎn)生式的集合，它的每個元素稱為一條產(chǎn)生式，可以表示為：P| b，其中P 是非終結(jié)符，叫做產(chǎn)生式的左部，和b分別叫做這個產(chǎn)生式的一個侯選式，他們既可以是終結(jié)符，也可以是非終結(jié)符，也可以是他們的組合。2.句型、句子的概念（小題）設(shè)G是一個文法，S是它的開始符號，

21、如果S，且(VNVT) * 則稱是G的一個句型；如果S ，且 VT* ，則稱是G的一個句子；句子實(shí)際上是僅含有終結(jié)符號的句型3.文法和語言的對應(yīng)關(guān)系：（了解）一個文法G所產(chǎn)生的句子的全體就是一個語言。給定一個文法，就能從結(jié)構(gòu)上唯一確定其語言；給定一種語言，能找到其文法，但該文法不是唯一的4.語法分析樹與二義性：（了解）用一棵樹來表示句型的推導(dǎo)，簡稱語法樹。若一個文法的一個句子對應(yīng)兩棵不同的語法樹，則稱該句子是二義性句子如果一個文法含有二義性的句子，則稱該文法是二義性文法。（5,6,7均可能出填空判斷選擇等小題）5. 3型文法是正規(guī)文法、正則文法、線性文法（用于詞法分析）6. 2型文法也稱為上下

22、文無關(guān)文法（用于語法分析）7. 1型文法也稱為上下文有關(guān)文法若一個文法是遞歸的，則由它產(chǎn)生的語言的句子個數(shù)是無限的。（2）自上而下8. 文法左遞歸的定義一個文法中如果存在某個產(chǎn)生式 PP（即有某個侯選式的最左邊的符號是這個產(chǎn)生式左部非終結(jié)符本身），則此文法是有左遞歸的。9. 消除文法的左遞歸的方法：只要求消除直接左遞歸，方法見下面的例子。設(shè)有產(chǎn)生式PP|其中不以P開頭，不為，那么，我們可以把P的規(guī)則改為如下的非直接左遞歸形式：PPPP|這樣就消除了PP|這個式子的左遞歸。（提示：在做題時，要把整個文法的每個產(chǎn)生式都逐一檢驗(yàn)，有時含有左遞歸的產(chǎn)生式是不只一個的，需要逐個消除。）10.First集

23、合Follow集的構(gòu)造方法（較抽象）First集的構(gòu)造方法：對于任意一個符號X，構(gòu)造他的frist集的方法是：(1)若XVT （終結(jié)符），則FIRST(X)=X.(2)若XVN（非終結(jié)符），且有產(chǎn)生式Xa（小寫a代表任意一個終結(jié)符號，他是侯選式左邊的第一個字符），則把a(bǔ)加入到FIRST(X)中；若X也是一條產(chǎn)生式，則把也加到FIRST(X)中。若有產(chǎn)生式XY（大寫Y代表任意一個非終結(jié)符號，他是侯選式左邊的第一個字符），則把FIRST(Y)中所有非元素都加到FIRST(X)中；FOLLOW集的構(gòu)造方法：（書上的表述很難懂，這里我用自己的水話表述）(1)對于文法中給定的開始符號S，置#與FOLLO

24、W(S)中；(2)將所有產(chǎn)生式侯選式中的非終結(jié)符都標(biāo)出來，并從前往后挨個檢查為方便討論，我們假設(shè)ABC是一個產(chǎn)生式，（這里B和C代表非終結(jié)符，代表終結(jié)符）1.先檢驗(yàn)這個非終結(jié)符的右邊還有沒有別的符號（不管這個符號是終結(jié)符還是非終結(jié)符），在這,B是我們檢查的第一個非終結(jié)符，它右邊是有符號C的，如果檢驗(yàn)到的某個非終結(jié)符右邊有別的符號，例如這里的B，那么檢驗(yàn)他右邊符號的FIRST集合，這里是FIRST（C）。先將FIRST（C）中非空字的元素加入到FOLLOW(B)中；注意，如果FIRST（C）中含有空字，還要把FOLLOW（A）中的元素也加入到FOLLOW（B）中（如果不含空字就不這么做）2.如果

25、檢驗(yàn)到的終結(jié)符右邊沒有別的符號了，例如這里的C，那么，直接將FOLLOW（A）中的元素加入到FOLLOW（C）中。 在這里，的存在是無關(guān)痛癢的。也就是說，我們在檢驗(yàn)?zāi)硞€非終結(jié)符時只要看他的右邊就好了，左邊有沒有有什么都是無所謂的。大家按照上面的方法，將每一個侯選式中的非終結(jié)符都這樣檢查一遍，最后就能求得所有非終結(jié)符的FOLLOW集了11. 遞歸下降分析法的概念，應(yīng)滿足什么條件？大家不必知道概念，只須知道能夠用遞歸下降分析法分析的文法是LL（1）文法，要成為這種文法，必須滿足以下條件： (1)文法不含左遞歸（在這里提一句：欲構(gòu)造行之有效的自上而下分析器，則必須消除文法中含有的左遞歸，請大家記住這

26、句話，有可能考小題）(2)對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的候選式的FIRST集兩兩不相交。即，若A1|2|n則FIRST(i)FIRST(j)= (ij)(3)對于文法中的每個非終結(jié)符A，若它的某個候選式的FIRST集中包含,則必須滿足FIRST(A)FOLLOW(A)=12. 預(yù)測分析表的構(gòu)造構(gòu)造預(yù)測分析表的算法是：（這里需要先畫一張表格，代入題中很容易理解，光看步驟比較抽象，大家可以看第13中的大題，邊看邊理解）（1）先畫一張表格，表的首行是文法中所有的終結(jié)符號，首列是所有產(chǎn)生式的左部） (2)檢驗(yàn)文法中每個產(chǎn)生式的每一個侯選式。我們先假設(shè)這里有一個產(chǎn)生式為A|b，若FIRST()

27、中含有終結(jié)符a，則把“A”寫入（1）中構(gòu)造的表中的MA,a項（MA,a表示以產(chǎn)生式左部A為行，終結(jié)符a為列所對應(yīng)的表格）；若FIRST(b)中含有終結(jié)符，則把“A”寫入（1）中構(gòu)造的表中的MA,項（MA,表示以產(chǎn)生式左部A為行，終結(jié)符為列所對應(yīng)的表格）；按照這樣的方法依次執(zhí)行下去，直到把每一個產(chǎn)生式的每一個侯選式都檢驗(yàn)完并對應(yīng)填入表格。(3)特別地，若某個產(chǎn)生式侯選式的FIRST集中包含有空子：我們接著引用上例進(jìn)行說明。在A|b中，假設(shè)FIRST()里還包含有，則找出 FOLLOW(A)中的所有終結(jié)符元素，我們假設(shè)其中一個是,那么把“A”寫入MA,中，按照此方法將FOLLOW(A)中的所有元素

28、逐一檢驗(yàn)，并將“A”填入對應(yīng)的表格中去即可。13.實(shí)際大題 給出一個文法，要你最終構(gòu)造出他的預(yù)測分析表，整個過程的步驟如下:1.消除文法左遞歸 2.構(gòu)造每個產(chǎn)生式左部（即->符號左邊的非終結(jié)符）的First集、Follow集 3.構(gòu)造每個產(chǎn)生式的每個侯選式的first集4.證明文法是一個LL(1)文法 5.構(gòu)造出預(yù)測分析表。 在812點(diǎn)當(dāng)中，已經(jīng)介紹了這些步驟的實(shí)現(xiàn)方法，以下是老師給的復(fù)習(xí)用的PPT上的例題，我對步驟做了一些補(bǔ)充說明例：設(shè)有文法G(VT，VN，S，P)，其中VT=a， ，, ，(，) ；VN=S,T；S = S P:S a | | (T)T T,S | S(1)消除其產(chǎn)生

29、式的左遞歸.(2)經(jīng)改寫后的文法是否是LL(1)的？給出它的預(yù)測分析表解：(1)消除其產(chǎn)生式的直接左遞歸對于T T,S | S (按照第9點(diǎn)中介紹的知識，這里P=T，=,S ，=S)所以變成TSTT,ST|所以文法改寫后變?yōu)椋篠 a | | (T)TSTT,ST|(2)經(jīng)改寫后的文法是否是LL(1)的？給出它的預(yù)測分析表。（這里的整體思路是按照第十點(diǎn)的知識構(gòu)造出相應(yīng)的FIRST集 和FOLLOW集 再按照第十一點(diǎn)的知識證明他是一個LL（1）文法，最后再用第十二點(diǎn)中知識求出預(yù)測分析表）解： （先求所有產(chǎn)生式左部那個非終結(jié)符號的FIRST集，用的是第十點(diǎn)中關(guān)于FIRST集求法的（2）中的方法）FI

30、RST( S )= a ( ; FIRST( T )= a ( ; FIRST( T)= , ;（緊接著求所有的侯選式的FIRST集，方法是：如果這個侯選式的開頭字符是終結(jié)符，也就是某個小寫字母，又或者是空字，那么這個侯選式的FIRST集就是那個小寫字母或者空字；如果侯選式開頭是非終結(jié)符，就將那個非終結(jié)符的FIRST集中除空字以外的元素變?yōu)楹钸x式本身FIRST集的元素）FIRST(ST)= a ( ; （S的FIRST集中除空字以外的元素） FIRST(,ST)= , ; （, 本身） FIRST(a)= a ; （a 本身） FIRST()= ; FIRST(T)= ( ;FIRST（）=

31、（本身）（接著求所有產(chǎn)生式左部那個非終結(jié)符號的FOLLOW集，方法在第十點(diǎn)中已經(jīng)說得很清楚了，這里我再說明一下。大家做題時，可以在所有的侯選式中把出現(xiàn)非終結(jié)符的位置都標(biāo)出來，然后挨個按照規(guī)則檢查，就不會錯了。有時在求某個非終結(jié)符的FOLLOW集時，發(fā)現(xiàn)其中還包含著其他非終結(jié)符FOLLOW集的元素，但那個FOLLOW集卻還沒有求出來，此時可先記下來，接著往下做，做到最后一定會找到某個終結(jié)符的FOLLOW集時與其他非終結(jié)符是無關(guān)的，把他寫出來后，再回頭把前面空出來的填完就好了。）FOLLOW(T)= ) ; FOLLOW (T)= ) ;FOLLOW (S)= # , ;完事之后要證明他是LL（1

32、）文法，用到第十一點(diǎn)中的知識。證明：S a | | (T)TSTT,ST|（1）文法已經(jīng)消除了左遞歸（2）FIRST(a)FIRST() FIRST(T)=a (=FIRST(,ST) FIRST（）=（3）在T,ST|中，F(xiàn)IRST（）=，里面含有空字，所以需要檢驗(yàn)：FIRST( T)FOLLOW (T)= ，, ) =接下來構(gòu)造他的預(yù)測分析表a()，#SS aS S (T)TTSTTSTTSTTT T,ST（3）自下而上14. 短語、直接短語的概念在這里請大家了解一下歸約的概念：歸約是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號。實(shí)際上，我們在（2）中研究的自上而下是從產(chǎn)生式左部推

33、導(dǎo)到右部的過程。也就是說，推導(dǎo)和歸約其實(shí)是兩個相逆的過程15. 句柄的概念一個句型的最左直接短語是這個句型的句柄16. 規(guī)范歸約、規(guī)范推導(dǎo)、規(guī)范句型規(guī)范歸約（最左歸約）是一個關(guān)于規(guī)范推導(dǎo)（最右推導(dǎo)）的逆過程（提示：在（2）自上而下的討論中，事實(shí)上我們一直使用的是最左推導(dǎo)，即總是先把侯選式最左邊的非終結(jié)符推導(dǎo)為終結(jié)符，請大家回想FIRST集的求法，事實(shí)上就是最左推導(dǎo)的過程）由規(guī)范推導(dǎo)推出的句型稱為規(guī)范句型。由于規(guī)范句型是由規(guī)范推導(dǎo)推出的句型，故該句型的句柄右邊只含有終結(jié)符號（因?yàn)樗亲钣彝茖?dǎo)，右邊的非終結(jié)符一定被推導(dǎo)成終結(jié)符了）規(guī)范歸約的關(guān)鍵問題是尋找句柄在規(guī)范歸約中，可歸約串必出現(xiàn)在棧頂19.

34、 算符文法、算符優(yōu)先文法的概念，如何判斷一個文法，如果它的任一產(chǎn)生式的右部都不含兩個相繼(并列)的非終結(jié)符，即不含如下形式的產(chǎn)生式右部：QR 則我們稱該文法為算符文法，也稱OG文法算符之間的優(yōu)先關(guān)系表示：（重要）1. a =. b 當(dāng)且僅當(dāng)文法G中含有形如Pab或PaQb的產(chǎn)生式；2.a <. b 當(dāng)且僅當(dāng)G中含有形如PaR的產(chǎn)生式， 而R -> b或R->Qb；3.a>.b 當(dāng)且僅當(dāng)G中含有形如PRb的產(chǎn)生式，而 R->a或R->aQ（這里大家先不必記住三種情況需要滿足的條件，在后面求FIRSTVT和LASTVT集合時大家自然會看到是和這些規(guī)則對應(yīng)上的。這

35、里需要注意的是，算符之間的優(yōu)先級關(guān)系有三種，請注意=.<.>. 這三個符號右下角的那一點(diǎn)是不能少的，（正確的寫法應(yīng)該是將點(diǎn)寫在那三個符號的里面，word不好弄，大家可以看看課本上的正確寫法）這不同等于數(shù)學(xué)上簡單的等于大于和小于，出現(xiàn)a<.a的情況都是可能的，而且即使有a <. b，卻并不意味著有b>.a，這看起來很荒謬，但是做題時卻非常重要，這里大家一定要記住，以后如果求得算符之間的優(yōu)先關(guān)系是a <. b，千萬不要自作聰明寫成b>.a，否則就全錯了，切記切記?。┤绻粋€算符文法G中的任何終結(jié)符對(a，b)至多只滿足下述三關(guān)系之一：a=.ba>.b

36、a<.b 則稱G是一個算符優(yōu)先文法(OPG文法)。如果有某兩個算符之間的關(guān)系不只一種，那么它就不是一個算符優(yōu)先文法20. 素短語素短語是指一個句型的短語，它至少包括有一個終結(jié)符號且除去它本身之外不再含任何更小的素短語（了解）最左素短語：處在句型最左端那個素短語成為最左素短語（了解）請大家記下面兩句話，有可能出小題：算符優(yōu)先歸約的關(guān)鍵問題是尋找最左素短語算符優(yōu)先法尤其適用于表達(dá)式的分析21. Firstvt集合和lastvt集合的構(gòu)造方法Firstvt集合構(gòu)造方法：（1） 若有產(chǎn)生式Pa或PQa，則aÎFIRSTVT(P)；（2）若aÎFIRSTVT(Q)，且有產(chǎn)生式P

37、Q，則aÎFIRSTVT(P)。lastvt集合的構(gòu)造方法（1） 若有產(chǎn)生式P a或P aQ ，則aÎ LASTVT(P)；（2）若aÎ LASTVT(Q)，且有產(chǎn)生式P Q ，則aÎ LASTVT(P)。（解析：個人認(rèn)為這兩個集合的構(gòu)造方法要比FIRST和FOLLOW集合簡單得多。針對以上的書面說法，說一些我個人的理解和方法。構(gòu)造某個產(chǎn)生式左部的Fisrtvt或者lastvt集合，其實(shí)都是從他的產(chǎn)生式里去找。對于firstvt,無非兩種情況，1.他的某個侯選式的第一個字母就是終結(jié)符，如Pa，或者第一個字母是非終結(jié)符而第二個字母是終結(jié)符如PQa，那么就把

38、這個a加入到P的firstvt集合中去；2.他的某個侯選式中的第一個字母就是非終結(jié)符，如PQ，那么就把Q的firstvt中的元素加入到P中去（請注意，這里沒有除去這一說，與FIRST集的構(gòu)造方法是不同的）。對應(yīng)的LASTVT集的構(gòu)造其實(shí)是和firstvt是剛好相反的，大家想想就很容易明白，這里不贅述了。需要注意的是，當(dāng)某個侯選式只有一個字符時，如Pa或PQ，a和Q既算第一個也算最后一個，在構(gòu)造兩個集合時都應(yīng)該予以考慮）22.算符優(yōu)先關(guān)系表的構(gòu)造方法這個方法是建立在你已經(jīng)學(xué)會了上面所說的兩個集合的構(gòu)造方法基礎(chǔ)上的，有了那兩個集合，我們就可以根據(jù)他們計算出文法當(dāng)中所有終結(jié)符之間的優(yōu)先關(guān)系了，方法如

39、下：（1）假定有個產(chǎn)生式的一個候選形為···ab····或aPb····，有a=.b(2)假定有個產(chǎn)生式的一個候選形為(a代表終結(jié)符，P代表非終極符)aP 那么，對任何bÎFIRSTVT(P)，有a <. b。(3)假定有個產(chǎn)生式的一個候選形為Pb那么，對任何aÎLASTVT(P)，有a >. B（解析：(1)的情況很簡單，對（2）和（3），這里的方法概括起來說就是，找到侯選式中所有一個終結(jié)符緊挨著一個非終結(jié)符的情況，如aP或者Pa,如果是前者，那么得出

40、a<.P的所有FIRSTVT集合中的元素；如果是后者,那么得出P的所有LASTVT集合中的元素>.a 只要把所有候選式里的這兩種情況都考慮完，所有算符之間的優(yōu)先關(guān)系也就找到了。還是請大家注意，a<.P的所有FIRSTVT集合中的元素這句話，并不等同于P的所有FIRSTVT集合中的元素>.a,千萬別反過來寫，一定把兩種情況的順序記清楚，a是在前面還是在后面。）當(dāng)把所有終結(jié)符的優(yōu)先關(guān)系找出來后，就可以構(gòu)造一張算符優(yōu)先關(guān)系表了。表的首行首列分別都是文法的所有終結(jié)符，請注意，首行和首列寫出來終結(jié)符的順序一定要是一致的。（請看下面的表）將算法優(yōu)先關(guān)系的三個符號>.<.

41、=.按照前面找到的各算符之間的優(yōu)先關(guān)系依次填入表格就可以了。填入時要注意，一定要先讀列，再讀行。即首列上的終結(jié)符對應(yīng)的應(yīng)該是符號左邊的那個元素，首行上的終結(jié)符對應(yīng)的應(yīng)該是符號右邊的那個元素。a%<>!a>.<.<.<. %>.>.<.<.>.<>.>. >.> <.<.<.=. !>.>. >.當(dāng)列完表格后，需要進(jìn)行判斷：如果在上面的表格中任意一個空里都至多只有一個符號，那么寫：由于本文法中任意兩個終結(jié)符之間都至多只滿足>.<.=.中的一個，由此可以看

42、出本文法是一個算符優(yōu)先文法；如果有任意一個空多余一個符號，那么寫：由于本文法中任意某兩個終結(jié)符之間有兩種優(yōu)先級關(guān)系，由此可以看出本文法不是一個算符優(yōu)先文法例：給出文法G（P） X jYjY kZ|iZ Yid 該文法是否為算符優(yōu)先文法？請根據(jù)FIRSTVT、LASTVT集合構(gòu)造算符優(yōu)先關(guān)系表說明之25. LR分析法屬于自底向上分析方法26. 26. 從文法出發(fā)構(gòu)造LR（0）分析表的步驟（簡答題！背?。?1)構(gòu)造文法G的拓廣文法G(2)構(gòu)造LR(0)項目(3)構(gòu)造G的項目集規(guī)范族(CLOSURE和GO函數(shù))(畫出一個確定的有限自動機(jī)DFA)(4)構(gòu)造分析表四、語義分析(小題)綜合屬性用于“自下而

43、上”傳遞信息在語法樹中，一個結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)的屬性值確定。因此，通常使用自底向上的方法在每一個結(jié)點(diǎn)處使用語義規(guī)則計算綜合屬性的值。僅僅使用綜合屬性的屬性文法稱S屬性文法五、中間代碼生成繼承屬性用于“自上而下”傳遞信息。在語法樹中，一個結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的某些屬性確定。用繼承屬性來表示程序語言結(jié)構(gòu)中的上下文依賴關(guān)系很方便。五、中間代碼生成1. 中間代碼：是一種面向語法，易于翻譯成目標(biāo)代碼的代碼中間語言的形式有三種：后綴式、圖表示法（包括抽象語法樹和有向無環(huán)圖（DAG）兩種）、三地址代碼2. 后綴式（逆波蘭式）的概念把運(yùn)算量(操作數(shù))寫在前面，把算符寫在后面。

44、例如：a+b，寫成ab+逆波蘭式中各運(yùn)算法出現(xiàn)的順序與實(shí)際運(yùn)算順序一致這一塊沒什么好講的，大家自己看看題，相信能悟出來其中的道理（下面是老師復(fù)習(xí)PPT上的題）(1)a*(-b+c)(2)a+b*(c+d/e)(3)-a+b*(-c+d)(4)not A or not (C or not D)(5)(A and B) or (not C or D)(6)(A or B) and (C or not D and E)解：(1)ab-c+*(2)abcde/+*+(3)a-bc-d+*+(4)A not C D or not or not(5) A B and C not D or or(6) A

45、B or C D not E and or and3. 后綴式與抽象語法樹（表達(dá)式樹）的關(guān)系后綴式其實(shí)是抽象語法書的線性表示形式，并且是按后根序遍歷得到的。4. 將賦值語句表示成后綴式和四元式這里不介紹什么方法了，后綴式的求法已經(jīng)在上面介紹過，關(guān)于四元式，大家看看這個例子相信自然就能夠明白。將表達(dá)式a:=(b+c)*e+(b+c)/f分別表示成后綴式、四元式（這道題2012年考的是原題）解：1.后綴式：a b c + e * b c + f / + :=2. 四元式(1)( +, b, c, T1 )(2)( *, T1, e, T2 )(3)( +, b, c, T3 )(4)( /, T3

46、, f, T4 )(5)( +, T2, T4, T5 )(6)( :=, T5, , a ) 再給一個例子：表達(dá)式-(a+b)*(c+d)-(a+b+c)分別表示成四元式解：1. 四元式(1)( +, a, b, T1 )(2)(-, T1, , T2 )(3)( +, c, d, T3 )(4)( *, T2, T3, T4 )(5)( +, a, b, T5 )(6)( +, T5, c, T6 )(7)( -, T4, T6, T7) 六、代碼優(yōu)化1. 簡述代碼優(yōu)化的原則與優(yōu)化的級別，并列舉三種常用的優(yōu)化技術(shù)(小題)三個原則：¨ 等價原則：經(jīng)過優(yōu)化后不應(yīng)改變程序運(yùn)行的結(jié)果；¨ 有效原則：使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時間較短，占用的存儲空間較??；¨ 合算原則：應(yīng)盡可能以較低的代價取得較好的優(yōu)化效果 優(yōu)化級別：¨ 局部優(yōu)化¨ 循環(huán)優(yōu)化