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

1、說(shuō)明1. 這份資料的最初來(lái)源是王金偉老師給大家發(fā)的復(fù)習(xí)提綱， 我在下面會(huì)給大家附一份原版，后面的 21 面資料是在那個(gè)的基礎(chǔ)上整理和細(xì)化得到的。 最初做這份資料的目的是我本人作為班長(zhǎng)為了幫助我們班的同學(xué)順利通過(guò)考試而整理的。 聽王老師說(shuō)有想法留給學(xué)弟學(xué)妹們用，我放假后又對(duì)一些內(nèi)容進(jìn)行了修正和改進(jìn)，得到了大家看到的這個(gè)版本2. 這份資料加入了很多我個(gè)人的理解。 與原提綱相比， 我增刪了一些內(nèi)容，并對(duì)某些內(nèi)容進(jìn)行了調(diào)序與合并。3. 這份資料融入了老師平時(shí)上課的以及最后復(fù)習(xí)課給的， 更重要的是我個(gè)人的理解和猜測(cè)。 大家或許都有感受， 覺得編譯原理書上或者上說(shuō)的句子根本看不懂。 針對(duì)這個(gè)問(wèn)題， 我把很

2、多晦澀難懂的形式化的算法通過(guò)我的理解后用比較形象易懂的話表述了出來(lái)， 表述得可能并不科學(xué)嚴(yán)謹(jǐn)， 但我的目的是為了能幫助大家做題和考試4. 里面的每一個(gè)考點(diǎn)我都在最后用括號(hào)加了注釋， 方便不同起點(diǎn)不同準(zhǔn)備時(shí)間的同學(xué)進(jìn)行選擇，這里簡(jiǎn)單說(shuō)明“了解”：代表這一部分的內(nèi)容被老師列在提綱內(nèi)，但其實(shí)并不太影響大家對(duì)大題的計(jì)算； 并且據(jù)我的分析也并不太可能出小題所以時(shí)間很緊的同學(xué)可以略看就好，當(dāng)然看看還是有好處的?！靶☆}” 一類的字樣代表這一塊的知識(shí)點(diǎn)值得出填空選擇， 大家1 / 47有時(shí)間應(yīng)該理解性的記憶下來(lái) （在 2012 年的期末考試上，選擇為 1 分*10 題；填空為 1 分*10 題，判斷改錯(cuò)為 2

3、 分*5 題，小題總計(jì) 30 分）“簡(jiǎn)答”：老師在最后復(fù)習(xí)課上說(shuō)過(guò)編譯原理是有簡(jiǎn)答題的，簡(jiǎn)答不同于計(jì)算， 很可能是讓你默寫一些步驟。 所以這一塊內(nèi)容大家需要背誦，即使不理解也要背下來(lái) （在 2012 年的期末考試上，簡(jiǎn)答題的分值為 5 分*4 題=20 分“鋪墊”“大題步驟” 等代表這一塊的內(nèi)容對(duì)于綜合大題的做題是必須了解的， 或者其實(shí)就是做大題的分解步驟， 這些塊的內(nèi)容是所有人必須看懂并且記下來(lái)的“實(shí)際大題”：總共列出的有 4 道，應(yīng)該每年考察的都會(huì)是這 4中題型， 每一道的分值都在 1215 分左右， 是所有人想通過(guò)考試所必須攻克的。 這里通常我會(huì)標(biāo)出他需要用到之前的哪些哪些知識(shí)點(diǎn)（201

4、2 年期末考試 4 道題的總分值為 50 分）5. 如果大家想去打印，最好在裝有 2007 及以上的機(jī)器上打印，否則有些符號(hào)可能會(huì)顯示不出來(lái)。 建議大家去生活廣場(chǎng)找機(jī)器打，不要去景元鴻6. 由于時(shí)間倉(cāng)促， 這份資料做的并不完善和嚴(yán)謹(jǐn)， 難免有錯(cuò)漏之處，希望大家諒解。大家可以一邊看我的這份資料，一邊看老師最后給的兩套， 課本來(lái)不及就別看了。 真心希望這份資料能對(duì)大家有用，祝大家都考得好。2 / 47最后說(shuō)一句， 我們?nèi)ツ昃幾g原理考得好的人挺多的， 其實(shí)也不是很難， 沒有人掛！ 本人慚愧， 只有 89，考得比我好的多太多了。總結(jié)原因是把時(shí)間花在了研究大題上面， 小題的很多知識(shí)點(diǎn)都沒有背熟，隨便錯(cuò)了

5、幾個(gè)小題就基本和 90 無(wú)緣了。10 計(jì) 1 王成正2012/7/9（老師給的提綱原版）概述 一、1. 編譯方式與解釋方式區(qū)別：是否生成目標(biāo)代碼2. 編譯程序總框架詞法分析 二、狀態(tài)轉(zhuǎn)換圖的功能：識(shí)別（接受）一定的符號(hào)串（單詞） 1.狀態(tài)轉(zhuǎn)換圖的程序?qū)崿F(xiàn)的思路：為每個(gè)狀態(tài)結(jié)點(diǎn)都編寫一 2. 個(gè)子程序字母表的概念：一般用表示 3. 閉包的概念：閉包 V*中的每個(gè)字都是由 V中的字經(jīng)過(guò)若干 4. 3 / 47次連接而成的上所有符號(hào)串的集合正則閉包的概念：是 V 5. 定義：表示上所有字的全體， 空字也包括在其中 * 6. +空字不包含， 非7. 之間的區(qū)別， ， 8. 所對(duì)應(yīng)的正規(guī)集為 9.正規(guī)式

6、與正規(guī)集的定義：知道如何用正規(guī)式表示一個(gè)正規(guī) 10. 集簡(jiǎn)述和的定義與區(qū)別 11.的某些結(jié)點(diǎn)既是初態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)，或者存在一若 M12. 通路，那么空字條從某初態(tài)結(jié)點(diǎn)到某個(gè)終態(tài)結(jié)點(diǎn)的所識(shí)別可為 M正規(guī)式與優(yōu)先自動(dòng)機(jī)的等價(jià)性 13. ， MV2. 對(duì)于上的每一個(gè)正規(guī)式，存在一個(gè)上的定理 14. L(M)(V) 使得的化簡(jiǎn)的概念和方法：終態(tài)和非終態(tài)是可區(qū)別的，因 M 15. 為終態(tài)可以讀出空字，而非終態(tài)不能讀出空字課后作業(yè)一個(gè)例題 16.yy 上所有倒數(shù)第二個(gè)字符為， 構(gòu)造一個(gè)， 它接受 =x 17. 的字符串語(yǔ)法分析 三、（1）基本定義4 / 47上下文無(wú)關(guān)文法的定義 1.句型、句子的概念

7、2. 文法和語(yǔ)言的對(duì)應(yīng)關(guān)系，給出文法構(gòu)造語(yǔ)言，文法 G產(chǎn)生 3. 的句子的全體是該文法的語(yǔ)言語(yǔ)法分析樹與二義性：判斷文法的二義性方法：如果一個(gè) 4.文法含有二義性的句子（對(duì)應(yīng)兩棵不同的語(yǔ)法樹） ，則稱該文法是二義性文法3 型文法是正規(guī)文法、正則文法、線性文法 5. 2 型文法也稱為稱為上下文無(wú)關(guān)文法 6. 若一個(gè)文法是遞歸的， 則由它產(chǎn)生的語(yǔ)言的句子個(gè)數(shù)是無(wú) 7.限的（2）自上而下8. 文法左遞歸的定義9. 消除文法的左遞歸的方法：直接左遞歸10. 消除回溯的方法：提取公共左因子11. 遞歸下降分析法的概念，應(yīng)滿足什么條件？12. 遞歸下降法對(duì)文法的每個(gè)非終結(jié)符構(gòu)造一個(gè)相應(yīng)的子程序13. 預(yù)測(cè)

8、分析法：給文法構(gòu)造預(yù)測(cè)分析表：消除左遞歸、消除回溯、集、集。舉例子時(shí)，便成 S（T）（3）自下而上14. 短語(yǔ)、直接短語(yǔ)的概念5 / 4715. 句柄的概念（一個(gè)句型的最左直接短語(yǔ)）16. 規(guī)范歸約（最左） 、規(guī)范推導(dǎo)（最右） 、規(guī)范句型17. 規(guī)范歸約的關(guān)鍵問(wèn)題是尋找句柄18. 在規(guī)范歸約中，可歸約串必出現(xiàn)在棧頂19. 算符文法、算符優(yōu)先文法的概念，如何判斷20. 構(gòu)造算符優(yōu)先關(guān)系表、 、集合，可不考慮 #號(hào)21. 素短語(yǔ)：算符優(yōu)先歸約的關(guān)鍵問(wèn)題是尋找最左素短語(yǔ)22. 算符優(yōu)先法尤其適用于表達(dá)式的分析23. 給出文法 G（P）X Y Z 24. 該文法是否為算符優(yōu)先文法？請(qǐng)根據(jù)、集合構(gòu)造算符

9、優(yōu)先關(guān)系表說(shuō)明之（ 12 分）25. 優(yōu)先函數(shù)的優(yōu)點(diǎn)：便于比較，節(jié)省空間26. 優(yōu)先函數(shù)的構(gòu)造方法27. 欲構(gòu)造行之有效的自上而下分析器， 則必須消除文法中含有的左遞歸28. 分析法屬于自底向上分析方法29. 從文法出發(fā)構(gòu)造（ 0）分析表的步驟四、語(yǔ)義分析1. 綜合屬性和繼承屬性概念6 / 47五、中間代碼生成1. 中間代碼是一種面向語(yǔ)法，易于翻譯成目標(biāo)代碼的代碼2. 后綴式（逆波蘭式）的概念3. 逆波蘭式中各運(yùn)算法出現(xiàn)的順序與實(shí)際運(yùn)算順序一致4. 后綴式與抽象語(yǔ)法樹（表達(dá)式樹）的關(guān)系5. 的含義6. 四元式表示方法， 聯(lián)系時(shí)通過(guò)臨時(shí)變量， 可以翻譯各種語(yǔ)句7. 將賦值語(yǔ)句表示成后綴式和四元式

10、六、代碼優(yōu)化1. 簡(jiǎn)述代碼優(yōu)化的原則與優(yōu)化的級(jí)別， 并列舉三種常用的優(yōu)化技術(shù)2. 基本塊、流圖的概念，如何畫、節(jié)點(diǎn)對(duì)應(yīng)基本塊3. 局部?jī)?yōu)化的方法，是對(duì)基本塊進(jìn)行優(yōu)化的有效工具4. P285 中間注意5. 不變運(yùn)算的代碼外提的條件6. 循環(huán)優(yōu)化中的強(qiáng)度削弱的含義七、目標(biāo)代碼生成1. 編譯程序生成的目標(biāo)程序種類一：概述 編譯方式與解釋方式區(qū)別（小題） 1.7 / 47在于是否生成目標(biāo)代碼，編譯方式生成了目標(biāo)代碼。）2. 編譯程序總框架（簡(jiǎn)答題，背！二：詞法分析 1. 狀態(tài)轉(zhuǎn)換圖的功能： （較重要鋪墊）識(shí)別（接受）一定的符號(hào)串（單詞）上圖是一個(gè)很簡(jiǎn)單的狀態(tài)轉(zhuǎn)換圖。 上圖代表： 狀態(tài) 0 通過(guò) X弧可

11、以轉(zhuǎn)換到狀態(tài) 1，通過(guò) Y弧可以轉(zhuǎn)換到狀態(tài) 2（較重要鋪墊）2. 字母表的概念： 一個(gè)由有限元素組成的集合，每個(gè)元素稱為一個(gè)符號(hào)或一個(gè)字，一般用表示一個(gè)字母表例： = a , b , c元素： a，b，c字母表中的字可拼接在一起構(gòu)成一個(gè)序列， 如等， 符號(hào)的順序不同所代表的序列也不同。8 / 47不包含任何字符的序列稱為空字，用來(lái)表示另外有幾個(gè)概念必須先了解：字( 符號(hào)串 ) 的連接設(shè) x 和 y 是兩個(gè)字 ( 符號(hào)串) ，則定義為他們的連接例：和連接是注: (1) （空字）是連結(jié)運(yùn)算的恒等元素 x = x =x(2) 字( 符號(hào)串 ) 的 n 次連接= x0= 規(guī)定 x321= x x= x

12、 ，x，集合的( 連接) 積，( 符號(hào)串 ) 的集合”設(shè) U和 V是兩個(gè)“字積)( 連接則定義為他們的Vy U且a, , b, , 例：設(shè), , , 則積記為：次 )( 連接 V集合的 n= V V V Vn 個(gè)0= V 規(guī)定，那么a, b 例：設(shè)9 / 470= V1= V2V32, V（較重要鋪墊）閉包的概念： 3.是一個(gè)字（符號(hào)串）的集合， V設(shè)*，的閉包定義為 V 則 V21*0 V = V VV*中的字經(jīng)過(guò)有限次連接中的每個(gè)字都是由 VV 注：閉包而成的正則閉包的定義為*=因?yàn)殚]的，閉包與正則閉包的差別在于，閉包里是含有0而正則閉包由于在閉包的基礎(chǔ)上又連接了包里有集合 V，的。，所以

13、正則閉包里是沒有空字 V一個(gè)* 定義： 表示上所有字的全體， 空字也包括在其中表示上所有字的全體，但不包括 +之間的區(qū)別（小題） ， 4. ，空字：表不包含任示何字符的序列稱 ：表示一個(gè)空集 的集合 ：表示含有空字10 / 47（較重要鋪墊）正規(guī)式與正規(guī)集的定義： 5.我們可以把具有相同特征的字放在一起組成一個(gè)集合， 即所謂的正規(guī)集然后使用一種形式化的方法來(lái)表示正規(guī)集，即所謂的正規(guī)式正規(guī)式是描述單詞結(jié)構(gòu)的一種形式；正規(guī)集是該類單詞的全集。舉例個(gè)的含義， 4 對(duì)于下面的例子，大家應(yīng)該好好思考一下后面對(duì)做大題是很有幫助的。 做大題時(shí)， 題目通常會(huì)給你一個(gè)你需要先把他要實(shí)現(xiàn)的功能抽象成一個(gè)正規(guī)集，

14、實(shí)際問(wèn)題， 再用正規(guī)式表達(dá)出來(lái)，才能繼續(xù)做后面的步驟。所對(duì)應(yīng)的正規(guī)集為 6. 簡(jiǎn)述有限自動(dòng)機(jī)和的定義與區(qū)別（重要鋪墊）代表非確定的有限自動(dòng)機(jī)；代表確定的有限自動(dòng)機(jī)11 / 47所謂的有限自動(dòng)機(jī)， 大家一定覺得這個(gè)概念坑爹死了。 其實(shí)他并不代表任何實(shí)體的機(jī)器，只是一種數(shù)學(xué)模型而已。就像函數(shù)、數(shù)列是一種數(shù)學(xué)模型一樣。 函數(shù)通過(guò)函數(shù)表達(dá)式實(shí)現(xiàn)他的功能： 你給他一個(gè)自變量， 他能根據(jù)表達(dá)式求出因變量的值。 而有限自動(dòng)機(jī)是通過(guò)狀態(tài)轉(zhuǎn)換圖來(lái)實(shí)現(xiàn)功能， 你給他一個(gè)初始狀態(tài)和一個(gè)輸入符號(hào)，他能根據(jù)你輸入的這個(gè)符號(hào)將原狀態(tài)轉(zhuǎn)換到另一個(gè)狀態(tài)，用他來(lái)模擬計(jì)算機(jī)的識(shí)別功能。下面簡(jiǎn)單介紹一下（確定的有限自動(dòng)機(jī)）的五元式

15、表示法： ( 重要)定義：一個(gè)確定有限自動(dòng)機(jī)（） M是一個(gè)五元式：M = (S, , f, s, F) ，其中 0S 是一個(gè)有限的狀態(tài)集合，它的每個(gè)元 1) 素我們稱為一個(gè)狀態(tài)是一個(gè)有窮的輸入符號(hào)的字母表， 2) 它的每個(gè)元素我們稱為一個(gè)輸入字符f 是從 S× S的單值部分映射 3) s 是 S的一個(gè)元素， 為初始狀態(tài)， 它是 4) 0唯一的狀態(tài)集合 F 是終止?fàn)顟B(tài)的集合，它是 S5) 的子集( 可空)一個(gè)非確定有限自動(dòng)機(jī)（） M是一個(gè)五元式12 / 47，其中 M = (S, , f, S0, F)它的每個(gè)元素我們稱為一個(gè)狀 S是一個(gè)有限的狀態(tài)集合，態(tài)是一個(gè)有限的輸入符號(hào)的字母表，

16、 它的每個(gè)元素我們稱為一個(gè)輸入字符的冪 表示 S*2S 的部分映射， 其中，2S是從 fS× 是非 M是非單值的的子集組成的集合） （f à集合（所有 S確定）的子集 S狀態(tài)集合 S0是初始狀態(tài)集合，它是的子集 S狀態(tài)集合 F 是終止?fàn)顟B(tài)的集合，它是這是 4），其他幾點(diǎn)都差不多，注：和的區(qū)別在于（ 3）和（，大家要記住他們的區(qū)別和聯(lián)系 有可能出簡(jiǎn)答題的的識(shí)別功能（小題） 7如果存在一條從初態(tài)結(jié)點(diǎn)到某個(gè)終態(tài)中任何字，對(duì)于 *則，結(jié)點(diǎn)的道路，這條路上所有的標(biāo)識(shí)符連成的字等于) 所識(shí)別( 接受，讀出可被 M的某些結(jié)點(diǎn)既是初態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)， 或者存在一 M若通路，那么空字條從某

17、初態(tài)結(jié)點(diǎn)到某個(gè)終態(tài)結(jié)點(diǎn)的可為 M所識(shí)別8. 狀態(tài)轉(zhuǎn)換圖的分裂規(guī)則（大題步驟）13 / 47這里 Y有兩個(gè)圈圈代表他是最終狀態(tài)的點(diǎn) ) 例子：(14 / 47劃到最后要求每條弧上都只有一個(gè)字母或者數(shù)字=(J) 的構(gòu)造方法（大題步驟） 9. (I) 和這里先需要了解幾個(gè)定義，這個(gè)集合中含有不同的 I 我們假設(shè)有某個(gè)狀態(tài)集狀態(tài)。( I, a ) 弧轉(zhuǎn)換：狀態(tài)集定義 1 I 的 a一是一個(gè)狀態(tài)集， 是從 I 中的狀態(tài)出發(fā)經(jīng)過(guò) ? 弧到達(dá)的狀態(tài)的全體。條 a閉包： ( I ) ( 空字的定義 2 狀態(tài)集 I)是一個(gè)狀態(tài)集，由兩部分組成 :狀態(tài)集 I 中的所有原狀態(tài)。 ?15 / 47弧，所中的狀態(tài)出發(fā)經(jīng)

18、過(guò) 任意條 從 I ?能到達(dá)的狀態(tài)的全體。3 = ( ( I, a ) ) 定義是一個(gè)狀態(tài)集。 ?下面給出一個(gè)實(shí)例：？求 2 例：有如下一個(gè)狀態(tài)轉(zhuǎn)換圖假定 1, = ，()=5,4,35,4,3,6,2,7,8 (J) =弧轉(zhuǎn)換，將求得的狀態(tài)再求空字閉包） （即先做 a這個(gè)狀態(tài)集合后， I 本知識(shí)點(diǎn)旨在讓大家掌握在知道了怎樣求如何用子集法將非確定的有限自動(dòng)機(jī)確定化（大題步驟） 10.方法：先畫一張表I 16 / 47(S0)B C A E DBI 這張表的首行上首列上固定是大寫字母 1.表格后面有幾列，取決于這個(gè)有限自動(dòng)機(jī)的輸入符號(hào)數(shù) 2. 代 b的下標(biāo) a 量，有幾個(gè)輸入符號(hào)就有幾列，這里假

19、設(shè)表這個(gè)有限自動(dòng)機(jī)的輸入符號(hào)代表的是這個(gè)有限自動(dòng) S03.第二行的第一列也是固定的，的空字閉包，我們假設(shè)求出來(lái)的狀即求 S0 機(jī)的初始狀態(tài) ,A 態(tài)集合是C和 B所對(duì)應(yīng)的 分別求出來(lái)，我們假設(shè)是 4. 將 A作為新的狀態(tài) CB，C和都分別于 A不同，需要將 5. 如果 B 集合加入到第一列中，再檢驗(yàn)：對(duì)于這四個(gè)狀態(tài) 所對(duì)應(yīng)的 B和 C繼續(xù)求出 6.加入到第一列的下面，如果有，集合，有沒有與是不同的，再繼續(xù)計(jì)算，如果與前面的相同就不再需要加入了。按照這樣的方法一直進(jìn)行下去，知道第一列不再有新的 7. 狀態(tài)集合加入了，這個(gè)表就構(gòu)造好了。再畫一張表，與上面的表相對(duì)應(yīng) 8.Sab17 / 4720 1

20、 1 43 4 321234 對(duì)于上面這種表的構(gòu)造方法很簡(jiǎn)單，大家也可以不另外 9.畫表，而直接標(biāo)在原來(lái)的表中，···這種表來(lái)源是， 在原來(lái)表的第一列上分別表上 s01234 不變，然后按照第一列中數(shù)字所對(duì)應(yīng)的狀態(tài)集，依 ba 和對(duì)應(yīng)次對(duì)應(yīng)在后面的列上標(biāo)上相應(yīng)數(shù)字。例如第一列中 B，第三也標(biāo)上 1 對(duì)應(yīng)2，那么將第二列第二行中的 B 1，C，等等。2 標(biāo)上列第二行中的C就可以按照這個(gè)畫出下面的這個(gè)表或在原表中標(biāo)好后， 10. 狀 1a弧轉(zhuǎn)換成 0 表畫出狀態(tài)轉(zhuǎn)換圖了，例如，狀態(tài)通過(guò)狀弧轉(zhuǎn)換成 3狀態(tài)；1 狀態(tài)通過(guò) a 弧轉(zhuǎn)換成態(tài)，通過(guò) b2 狀態(tài)，等等。畫出這個(gè)狀

21、態(tài)轉(zhuǎn)換圖 4 態(tài)，通過(guò) b 弧轉(zhuǎn)換成后， 就完成了一個(gè)非確定有限自動(dòng)機(jī)的確定化。有限自動(dòng)機(jī)的化簡(jiǎn)（大題步驟） 11.分析：這是一塊用文字很難表述清楚的內(nèi)容， 并且在實(shí)際的化簡(jiǎn)中如果題目難度大是很容易出錯(cuò)的， 但是期末考試通常不會(huì)太復(fù)雜，整體的思路如下：步中得到的已經(jīng)確定的中的所有狀態(tài)分為將第 1.10 兩組，一組為終態(tài)節(jié)點(diǎn)，一組為非終態(tài)節(jié)點(diǎn)。需要補(bǔ)那一列的節(jié)點(diǎn)哪充的是，在上一步構(gòu)造的表格中， s18 / 47些是終態(tài)哪些是非終態(tài)呢？這需要看你最初構(gòu)造的正規(guī)式中的哪個(gè)是終態(tài)節(jié)點(diǎn)了。例如在下面的 12 中，Y為終態(tài)節(jié)點(diǎn)，那么在以上的表格中只要是含有 Y 元素的狀態(tài)集合都將成為終態(tài)集。2. 將每個(gè)分

22、組檢驗(yàn)， 看他們是否還能分割， 檢驗(yàn)的方法實(shí)在難以用文字描述清楚，請(qǐng)大家看下面的實(shí)際例題，自己領(lǐng)會(huì)。3. 每個(gè)分組都不能再分割后， 若還含有大于 2 個(gè)元素的分組， 則這個(gè)分組中的所有狀態(tài)都是等價(jià)的， 可以用其中的一個(gè)代替他們，代替的方法是：假設(shè)用狀態(tài) 1 代替狀態(tài) 2，則把狀態(tài) 2 及其引出去的弧全部刪去，并把原來(lái)指向狀態(tài) 2 的弧指向狀態(tài) 1下面是老師復(fù)習(xí)上的一個(gè)例子， 這是一個(gè)較為復(fù)雜的例子， 可能會(huì)看不懂，大家多問(wèn)一問(wèn)周圍會(huì)的同學(xué)，期末考試時(shí)，肯定不會(huì)出這么復(fù)雜， 通常在將終態(tài)節(jié)點(diǎn)和非終態(tài)節(jié)點(diǎn)區(qū)分開后， 剩下的就已經(jīng)快分好了， 所以大家不用太擔(dān)心， 化簡(jiǎn)也是有可能不考察的，大家看清題目

23、要求。例：19 / 4720 / 47實(shí)際大題 12.yy 上所有倒數(shù)第二個(gè)字符為例題：構(gòu)造一個(gè)，它接受 =x ，的字符串希望大家能在這里還是想先說(shuō)明一下這道題的解題思路和步驟，讓大家真正明白這樣的一道大題是應(yīng)真正明白整個(gè)解題的過(guò)程，2012 該怎么做的（具體的完整解答過(guò)程這里不貼出來(lái)了，這是但是本以為會(huì)考原題，年考試之前老師復(fù)習(xí)課上給的一道題目，*的題，0|10 ）最后考的是一個(gè)（也大家也可以看老師復(fù)習(xí)上給出的例題，都是非常經(jīng)典的例題！是有可能出原題的）上面這道題的分析思路是根據(jù)他所描述的功能，構(gòu)造出一個(gè)正規(guī)式，正規(guī)式先給 1.*y ()（）大家：（其實(shí)對(duì)于這樣的大題最關(guān)鍵就是構(gòu)造對(duì)正規(guī)式，

24、 大家一定把老師最后的上所有的例題是如何構(gòu)造正規(guī)式的都記下） 來(lái)！這一步做不出來(lái)后面的都沒分了！，將正規(guī)式寫在他 Y和和最終狀態(tài) 2. 構(gòu)造一個(gè)初始狀態(tài) X 們的轉(zhuǎn)換弧上。點(diǎn)中的分裂規(guī)則對(duì)他進(jìn)行分裂，分裂直到每一 8 按照第 3. 條轉(zhuǎn)換弧上都只含有一個(gè)字符21 / 474. 分裂結(jié)束得到的一個(gè)狀態(tài)轉(zhuǎn)換圖實(shí)際上就是一個(gè) （非確定的有限自動(dòng)機(jī)）5. 在掌握了第 9 點(diǎn)知識(shí)的前提下， 就可以按照第 10 點(diǎn)說(shuō)的步驟，將求得的確定化6. 得到確定化之后的狀態(tài)轉(zhuǎn)換圖， 剩下的事情就是化簡(jiǎn)了。 也就是第 11 點(diǎn)當(dāng)中的只是看到這里強(qiáng)烈建議大家先動(dòng)筆試一試上面這道例題， 相信只要你認(rèn)真學(xué)習(xí)了前面的知識(shí)，做

25、出來(lái)是沒有問(wèn)題的，祝大家成功！三：語(yǔ)法分析 ）基本定義 1（1. 上下文無(wú)關(guān)文法的定義 ( 重要鋪墊)文法：是描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則（或稱語(yǔ)法規(guī)則）上下文無(wú)關(guān)文法概念 :它所定義的語(yǔ)法范疇 （或語(yǔ)法單位） 是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的（與它所在的上下文無(wú)關(guān)）（重要！以下的概念一定要理解熟知！ ）上下文無(wú)關(guān)文法 G可定義為一個(gè)四元式 ( ，S，P)是終結(jié)符號(hào)集合， 它的每個(gè)元素稱為終結(jié)符號(hào)， 用小寫字母表示。是非終結(jié)符號(hào)集合， 它的每個(gè)元素稱為非終結(jié)符號(hào)， 用大寫字母表示。S是一個(gè)開始符號(hào)，是一個(gè)非終結(jié)符，至少在一個(gè)產(chǎn)生式作為左22 / 47部出現(xiàn)P是一個(gè)產(chǎn)生式的集合，它的每個(gè)元素

26、稱為一條產(chǎn)生式，可以表示為：P| b ，其中 P 是非終結(jié)符 ，叫做 產(chǎn)生式的左部 ，和 b 分別叫做這個(gè)產(chǎn)生式的一個(gè)侯選式， 他們既可以是終結(jié)符， 也可以是非終結(jié)符，也可以是他們的組合。2. 句型、句子的概念（小題）S是它的開始符號(hào)，如果， G設(shè)是一個(gè)文法， S * ，G的一個(gè)句型；如果 S( ) 則稱是且 *且 ，則稱是 G的一個(gè)句子； 句子實(shí)際上是僅含有終結(jié)符號(hào)的句型3. 文法和語(yǔ)言的對(duì)應(yīng)關(guān)系： （了解）一個(gè)文法 G所產(chǎn)生的句子的全體就是一個(gè)語(yǔ)言。給定一個(gè)文法，就能從結(jié)構(gòu)上唯一確定其語(yǔ)言；給定一種語(yǔ)言，能找到其文法，但該文法不是唯一的4. 語(yǔ)法分析樹與二義性： （了解）用一棵樹來(lái)表示句型

27、的推導(dǎo)， 簡(jiǎn)稱語(yǔ)法樹。 若一個(gè)文法的一個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹， 則稱該句子是二義性句子如果一個(gè)文法含有二義性的句子，則稱該文法是二義性文法。（5,6,7 均可能出填空判斷選擇等小題）7. 3 型文法是正規(guī)文法、 正則文法、 線性文法 （用于詞法 分析）23 / 478. 2 型文法也稱為上下文無(wú)關(guān)文法（用于語(yǔ)法分析）9. 1 型文法也稱為上下文有關(guān)文法若一個(gè)文法是遞歸的，則由它產(chǎn)生的語(yǔ)言的句子個(gè)數(shù)是無(wú)限的。（2）自上而下（以下 812 均為 13 的大題鋪墊）10. 文法左遞歸的定義一個(gè)文法中如果存在某個(gè)產(chǎn)生式 PP（即有某個(gè)侯選式的最左邊的符號(hào)是這個(gè)產(chǎn)生式左部非終結(jié)符本身） ，則此文法是

28、有左遞歸的。11. 消除文法的左遞歸的方法：只要求消除直接左遞歸，方法見下面的例子。設(shè)有產(chǎn)生式 P P| 其中不以 P開頭，不為，那么，我們可以把 P的規(guī)則改為如下的非直接左遞歸形式：P P'P' P'| 這樣就消除了 PP| 這個(gè)式子的左遞歸。（提示：在做題時(shí)，要把整個(gè)文法的每個(gè)產(chǎn)生式都逐一檢驗(yàn)，有時(shí)含有左遞歸的產(chǎn)生式是不只一個(gè)的，需要逐個(gè)消除。 ）10 集合集的構(gòu)造方法（較抽象）集的構(gòu)造方法：對(duì)于任意一個(gè)符號(hào) X，構(gòu)造他的集的方法是：24 / 47(1) 若 X（終結(jié)符），則(X)=X.(2) 若 X（非終結(jié)符） ，且有產(chǎn)生式 Xa（小寫 a 代表任意一個(gè)終結(jié)符號(hào)，

29、 他是侯選式左邊的第一個(gè)字符 ），則把 a 加入到(X) 中；若 X也是一條產(chǎn)生式，則把也加到 (X) 中。若有產(chǎn)生式 XY（大寫 Y代表任意一個(gè)非終結(jié)符號(hào)， 他 是侯選式左邊的第一個(gè)字符 ），則把 (Y) 中所有非元素都加到 (X)中；集的構(gòu)造方法：（ 書上的表述很難懂， 這里我用自己的水話表述）(1) 對(duì)于文法中給定的開始符號(hào) S，置#與(S) 中；(2) 將所有產(chǎn)生式侯選式中的非終結(jié)符都標(biāo)出來(lái)，并從前往后挨個(gè)檢查為方便討論，我們假設(shè) A是一個(gè)產(chǎn)生式， （這里 B和 C代表非終結(jié)符，代表終結(jié)符）3. 先檢驗(yàn)這個(gè)非終結(jié)符的右邊還有沒有別的符號(hào) （不管這個(gè)符號(hào)是終結(jié)符還是非終結(jié)符） ，在這是我

30、們檢查的第一個(gè)非終結(jié)符，它右邊是有符號(hào) C的，如果檢驗(yàn)到的某個(gè)非終結(jié)符右邊有別的符號(hào)，例如這里的 B，那么檢驗(yàn)他右邊符號(hào)的集合，這里是（ C）。先將（ C）中非空字的元素加入到 (B) 中；注意，如果（C）中含有空字， 還要把（A）中的元素也加入到（ B）中（如果不含空字就不這么做）4. 如果檢驗(yàn)到的終結(jié)符右邊沒有別的符號(hào)了，例如這里的 C，25/ 47那么，直接將（ A）中的元素加入到（ C）中。在這里，的存在是無(wú)關(guān)痛癢的。也就是說(shuō)，我們?cè)跈z驗(yàn)?zāi)硞€(gè)非終結(jié)符時(shí)只要看他的右邊就好了， 左邊有沒有有什么都是無(wú)所謂的。 大家按照上面的方法， 將每一個(gè)侯選式中的非終結(jié)符都這樣檢查一遍，最后就能求得所有

31、非終結(jié)符的集了遞歸下降分析法的概念，應(yīng)滿足什么條件？ 11.大家不必知道概念， 只須知道能夠用遞歸下降分析法分析的文法是（1）文法，要成為這種文法，必須滿足以下條件：(1) 文法不含左遞歸（在這里提一句： 欲構(gòu)造行之有效的自上而下分析器，則必須消除文法中含有的左遞歸 ，請(qǐng)大家記住這句話，有可能考 小題）(2) 對(duì)于文法中每一個(gè)非終結(jié)符 A的各個(gè)產(chǎn)生式的候選式的集兩兩不相交。即，若A | | | n12(i j) ) ()= 則 ( ji (3) 對(duì)于文法中的每個(gè)非終結(jié)符 A，若它的某個(gè)候選式的集中包含 , 則必須滿足(A)=(A) 30. 預(yù)測(cè)分析表的構(gòu)造構(gòu)造預(yù)測(cè)分析表的算法是： （這里需要先

32、畫一張表格，代入題中很容易理解，光看步驟比較抽象，大家可以看第 13 中的大題，邊看邊理解）26 / 47（1）先畫一張表格，表的首行是文法中所有的終結(jié)符號(hào)，首列是所有產(chǎn)生式的左部）(2) 檢驗(yàn)文法中每個(gè)產(chǎn)生式的每一個(gè)侯選式。 我們先假設(shè)這里有一個(gè)產(chǎn)生式為 A，若 ( ) 中含有終結(jié)符 a，則把“A”寫入（1）中構(gòu)造的表中的 M 項(xiàng)（M 表示以產(chǎn)生式左部 A為行，終結(jié)符 a 為列所對(duì)應(yīng)的表格） ；若(b) 中含有終結(jié)符，則把“ A”寫入（ 1）中構(gòu)造的表中的 MA, 項(xiàng)（MA, 表示以產(chǎn)生式左部 A為行，終結(jié)符為列所對(duì)應(yīng)的表格） ；按照這樣的方法依次執(zhí)行下去， 直到把每一個(gè)產(chǎn)生式的每一個(gè)侯選式

33、都檢驗(yàn)完并對(duì)應(yīng)填入表格。(3) 特別地，若某個(gè)產(chǎn)生式侯選式的集中包含有空子：我們接著引用上例進(jìn)行說(shuō)明。在 A中，假設(shè) ( ) 里還包含有，則找出 (A) 中的所有終結(jié)符元素，我們假設(shè)其中一個(gè)是 , 那么把“A”寫入 MA, 中，按照此方法將 (A) 中的所有元素逐一檢驗(yàn)，并將“ A”填入對(duì)應(yīng)的表格中去即可。31. 實(shí)際大題（ 812 點(diǎn)的綜合知識(shí)， 15 分左右?。┍绢}會(huì)出一個(gè)綜合性的大題。 題目會(huì)給出一個(gè)文法， 要你最終構(gòu)造出他的預(yù)測(cè)分析表，整個(gè)過(guò)程的步驟如下2. 消除文法左遞歸 2. 構(gòu)造每個(gè)產(chǎn)生式左部（即 ->符號(hào)左邊的非終結(jié)符）的集、集 3. 構(gòu)造每個(gè)產(chǎn)生式的每個(gè)侯選式 27 /

34、 47的集 4. 證明文法是一個(gè) (1) 文法 5. 構(gòu)造出預(yù)測(cè)分析表。在 812 點(diǎn)當(dāng)中，已經(jīng)介紹了這些步驟的實(shí)現(xiàn)方法，以下是老師給的復(fù)習(xí)用的上的例題，我對(duì)步驟做了一些補(bǔ)充說(shuō)明例：設(shè)有文法 G(，S，P)，其中 a ， ，, ，( ，) ； ；S = SP:S a | | (T)T | S(1) 消除其產(chǎn)生式的左遞歸 .(2) 經(jīng)改寫后的文法是否是 (1) 的？給出它的預(yù)測(cè)分析表解：(1) 消除其產(chǎn)生式的直接左遞歸對(duì)于 T | S ( 按照第 9 點(diǎn)中介紹的知識(shí)，這里， ，)所以變成T'T' '| 所以文法改寫后變?yōu)椋篠 a | | (T)T 'T'

35、'| 28 / 47(2) 經(jīng)改寫后的文法是否是 (1) 的？給出它的預(yù)測(cè)分析表。（這里的整體思路是按照第十點(diǎn)的知識(shí)構(gòu)造出相應(yīng)的集 和集再按照第十一點(diǎn)的知識(shí)證明他是一個(gè)（ 1）文法，最后再用第十二點(diǎn)中知識(shí)求出預(yù)測(cè)分析表）解： （先求所有產(chǎn)生式左部那個(gè)非終結(jié)符號(hào)的集，用的是第十點(diǎn)中關(guān)于集求法的（ 2）中的方法）( S )= a ( ;( T )= a ( ;( T')= , ;（緊接著求所有的侯選式的集， 方法是： 如果這個(gè)侯選式的開頭字符是終結(jié)符，也就是某個(gè)小寫字母，又或者是空字，那么這個(gè)侯選式的集就是那個(gè)小寫字母或者空字； 如果侯選式開頭是非終結(jié)符，就將那個(gè)非終結(jié)符的集中除空

36、字以外的元素變?yōu)楹钸x式本身集的元素）(')= a ( ; （S的集中除空字以外的元素）(')= , ; （, 本身）(a)= a ; （a 本身）( )= ;(T)= ( ;（）= （本身）29 / 47（接著求所有產(chǎn)生式左部那個(gè)非終結(jié)符號(hào)的集， 方法在第十點(diǎn)中已經(jīng)說(shuō)得很清楚了，這里我再說(shuō)明一下。大家做題時(shí)，可以在所有的侯選式中把出現(xiàn)非終結(jié)符的位置都標(biāo)出來(lái)， 然后挨個(gè)按照規(guī)則檢查，就不會(huì)錯(cuò)了。有時(shí)在求某個(gè)非終結(jié)符的集時(shí)，發(fā)現(xiàn)其中還包含著其他非終結(jié)符集的元素， 但那個(gè)集卻還沒有求出來(lái)， 此時(shí)可先記下來(lái)， 接著往下做， 做到最后一定會(huì)找到某個(gè)終結(jié)符的集時(shí)與其他非終結(jié)符是無(wú)關(guān)的， 把

37、他寫出來(lái)后， 再回頭把前面空出來(lái)的填完就好了。 ）(T)= ) ;(T')= ) ;(S)= # , ;完事之后要證明他是（ 1）文法，用到第十一點(diǎn)中的知識(shí)。證明：S a | | (T)T 'T' '| （1）文法已經(jīng)消除了左遞歸）(a) ( ) (T)=a (=2 （=（） (')（3）在 T' '| 中，（）= ，里面含有空字，所以需要檢驗(yàn)：30 / 47=( T') (T')= ，, )以上，證明該文法是 (1) 文法（這一步證明別忘了寫，不然 會(huì)扣分的，我考試時(shí)這一步就給忘了· ··

38、哎 ···）接下來(lái)構(gòu)造他的預(yù)測(cè)分析表 （方法是第十二點(diǎn)的知識(shí)， 我感覺我已經(jīng)說(shuō)得非常明白了，這里不再贅述了）a()#SS S S (TTTTTT'' T' T' ）自下而上 3（14. 短語(yǔ)、 直接短語(yǔ)的概念 （很難懂， 對(duì)于書上的概念我也 不太理解，這塊知識(shí)會(huì)出兩道小題）在這里請(qǐng)大家了解一下歸約的概念：歸約是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號(hào)。實(shí)際上，我們?cè)冢?2）中研究的自上而下是從產(chǎn)生式左部推導(dǎo)到右部的過(guò)程。 也就是說(shuō)， 推導(dǎo)和歸約其實(shí)是兩個(gè)相逆的過(guò)程8. 句柄的概念（小題）一個(gè)句型的 最左直接短語(yǔ) 是這個(gè)句

39、型的句柄9. 規(guī)范歸約、規(guī)范推導(dǎo)、規(guī)范句型（小題）規(guī)范歸約 （最左歸約）是一個(gè)關(guān)于 規(guī)范推導(dǎo)（ 最右推導(dǎo)）的 31 /47逆過(guò)程（提示：在（ 2）自上而下的討論中，事實(shí)上我們一直使用的是最左推導(dǎo)，即總是先把侯選式最左邊的非終結(jié)符推導(dǎo)為終結(jié)符，請(qǐng)大家回想集的求法，事實(shí)上就是最左推導(dǎo)的過(guò)程）由規(guī)范推導(dǎo)推出的句型稱為規(guī)范句型 。由于規(guī)范句型是由規(guī)范推導(dǎo)推出的句型， 故該句型的句柄右邊只含有終結(jié)符號(hào) （因?yàn)樗亲钣彝茖?dǎo)， 右邊的非終結(jié)符一定被推導(dǎo)成終結(jié)符了）規(guī)范歸約的關(guān)鍵問(wèn)題是尋找句柄 （對(duì)應(yīng)第 15 點(diǎn)）在規(guī)范歸約中，可歸約串必出現(xiàn)在棧頂7. 算符文法、 算符優(yōu)先文法的概念，如何判斷（大題鋪墊）一個(gè)

40、文法，如果它的任一產(chǎn)生式的右部都不含兩個(gè)相繼 ( 并列)的非終結(jié)符，即不含如下形式的產(chǎn)生式右部： 則我們稱該文法為算符文法，也稱文法算符之間的優(yōu)先關(guān)系表示： （重要）2. a =. b 當(dāng)且僅當(dāng)文法 G中含有形如 P或 P的產(chǎn)生式；2 <. b 當(dāng)且僅當(dāng) G中含有形如 P的產(chǎn)生式， 而 R ->b或>；3> 當(dāng)且僅當(dāng) G中含有形如 P的產(chǎn)生式，而 > a 或>（這里大家先不必記住三種情況需要滿足的條件， 在后面求 32 /47和集合時(shí)大家自然會(huì)看到是和這些規(guī)則對(duì)應(yīng)上的。 這里需要注意的是，算符之間的優(yōu)先級(jí)關(guān)系有三種，請(qǐng)注意 =.<.>. 這三個(gè)符

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

42、那么它就不是一個(gè)算符優(yōu)先文法7. 素短語(yǔ)（小題）素短語(yǔ)是指一個(gè)句型的短語(yǔ)， 它至少包括有一個(gè)終結(jié)符號(hào)且除去它本身之外不再含任何更小的素短語(yǔ) （了解）最左素短語(yǔ)： 處在句型最左端那個(gè)素短語(yǔ)成為最左素短語(yǔ) （了解）請(qǐng)大家記下面兩句話，有可能出 小題：33 / 47算符優(yōu)先歸約的關(guān)鍵問(wèn)題是尋找最左素短語(yǔ)算符優(yōu)先法尤其適用于表達(dá)式的分析8. 集合和集合的構(gòu)造方法（大題步驟）集合構(gòu)造方法：（1） 若有產(chǎn)生式 Pa或 P，則 a(P) ；(Q) ，且有產(chǎn)生式 PQ，（2）若 a則 a(P) 。集合的構(gòu)造方法（1） 若有產(chǎn)生式 P a 或 P ，則 a (P) ；(Q) ，且有產(chǎn)生式 P Q ，（2）若 a

43、則 a (P) 。（解析：個(gè)人認(rèn)為這兩個(gè)集合的構(gòu)造方法要比和集合簡(jiǎn)單得多。針對(duì)以上的書面說(shuō)法， 說(shuō)一些我個(gè)人的理解和方法。 構(gòu)造某個(gè)產(chǎn)生式左部的或者集合，其實(shí)都是從他的產(chǎn)生式里去找。對(duì)于 , 無(wú)非兩種情況， 1. 他的某個(gè)侯選式的第一個(gè)字母就是終結(jié)符，如 Pa，或者第一個(gè)字母是非終結(jié)符而第二個(gè)字母是終結(jié)符如 P， 那么就把這個(gè) a 加入到 P的集合中去； 2. 他的某個(gè)侯選式中的第一個(gè)字母就是非終結(jié)符，如 PQ，那么就把 Q的中的元素加入到 P中去（請(qǐng)注意，這里沒有除去這一說(shuō)，與集的34 / 47構(gòu)造方法是不同的） 。對(duì)應(yīng)的集的構(gòu)造其實(shí)是和是剛好相反的，大家想想就很容易明白，這里不贅述了。需要

44、注意的是，當(dāng)某個(gè)侯選式只有一個(gè)字符時(shí)，如 Pa 或 PQ，a 和 Q既算第一個(gè)也算最后一個(gè)，在構(gòu)造兩個(gè)集合時(shí)都應(yīng)該予以考慮）9. 算符優(yōu)先關(guān)系表的構(gòu)造方法（大題步驟）這個(gè)方法是建立在你已經(jīng)學(xué)會(huì)了上面所說(shuō)的兩個(gè)集合的構(gòu)造方法基礎(chǔ)上的， 有了那兩個(gè)集合， 我們就可以根據(jù)他們計(jì)算出文法當(dāng)中所有終結(jié)符之間的優(yōu)先關(guān)系了，方法如下：（1）假定有個(gè)產(chǎn)生式的一個(gè)候選形為· ······ 或 ····， 有(2) 假定有個(gè)產(chǎn)生式的一個(gè)候選形為 (a 代表終結(jié)符， P代表非終極符)那么，對(duì)任何 b(P)

45、，有 a <. b。(3) 假定有個(gè)產(chǎn)生式的一個(gè)候選形為那么，對(duì)任何 a(P) ，有 a >. B（解析： (1) 的情況很簡(jiǎn)單，對(duì)（ 2）和（3），這里的方法概括起來(lái)說(shuō)就是， 找到侯選式中所有一個(gè)終結(jié)符緊挨著一個(gè)非終結(jié)符的情況，如或者 , 如果是前者，那么得出 a<的所有集合中的元素；如果是后者 , 那么得出 P 的所有集 35 / 47合中的元素 > 只要把所有候選式里的這兩種情況都考慮完， 所有算符之間的優(yōu)先關(guān)系也就找到了。 還是請(qǐng)大家注意， a<的所有集合中的元素這句話， 并不等同于 P的所有集合中的元素 >, 千萬(wàn)別反過(guò)來(lái)寫，一定把兩種情況的順序記

46、清楚， a 是在前面還是在后面。）當(dāng)把所有終結(jié)符的優(yōu)先關(guān)系找出來(lái)后， 就可以構(gòu)造一張算符優(yōu)先關(guān)系表了。表的首行首列分別都是文法的所有終結(jié)符，請(qǐng)注意，首行和首列寫出來(lái)終結(jié)符的順序一定要是一致的。 （請(qǐng)看下面的表）將算法優(yōu)先關(guān)系的三個(gè)符號(hào) >.<. 按照前面找到的各算符之間的優(yōu)先關(guān)系依次填入表格就可以了。 填入時(shí)要注意， 一定要先讀列，再讀行。 即首列上的終結(jié)符對(duì)應(yīng)的應(yīng)該是符號(hào)左邊的那個(gè)元素，首行上的終結(jié)符對(duì)應(yīng)的應(yīng)該是符號(hào)右邊的那個(gè)元素。a%< >!a >. <. <. <.% >. >. <. <. >.< &g

47、t;. >. >.> <. <. <. =.!>. >. >.36 / 47當(dāng)列完表格后， 需要進(jìn)行判斷： 如果在上面的表格中任意一個(gè)空里都至多只有一個(gè)符號(hào)， 那么寫： 由于本文法中任意兩個(gè)終結(jié)符之間都至多只滿足 >.<. 中的一個(gè)，由此可以看出本文法是一個(gè)算符優(yōu)先文法；如果有任意一個(gè)空多余一個(gè)符號(hào)，那么寫：由于本文法中任意某兩個(gè)終結(jié)符之間有兩種優(yōu)先級(jí)關(guān)系， 由此可以看出本文法不是一個(gè)算符優(yōu)先文法10. 優(yōu)先函數(shù)的構(gòu)造方法（可能單獨(dú)考簡(jiǎn)答，也可能加入計(jì)算）優(yōu)先函數(shù)的優(yōu)點(diǎn)：便于比較，節(jié)省空間（ 2012 年只考察了這樣一道小題，并

48、未單獨(dú)考察別的大題）優(yōu)先函數(shù)的構(gòu)造方法： （建議大家熟記以下的步驟，是有可能考簡(jiǎn)答題的）如果優(yōu)先函數(shù)存在， 則可以通過(guò)以下三個(gè)步驟從優(yōu)先表構(gòu)造優(yōu)先函數(shù):(1) 對(duì)于每個(gè)終結(jié)符 a，令其對(duì)應(yīng)兩個(gè)符號(hào)和，畫一張以所有符號(hào)和為結(jié)點(diǎn)的方向圖。如果 a>，則從畫一條弧至如果 a<，則從畫一條弧至 。(2) 對(duì)每個(gè)結(jié)點(diǎn)都賦予一個(gè)數(shù)，此數(shù)等于從該結(jié)點(diǎn)出發(fā)所能到達(dá)的結(jié)點(diǎn)( 包括出發(fā)點(diǎn)自身 ) 。賦給的數(shù)作為 f(a)37 / 47賦給的數(shù)作為 g(a) 。(3) 檢查所構(gòu)造出來(lái)的函數(shù) f 和 g 是否與原來(lái)的關(guān)系矛盾。若沒有矛盾，則 f 和 g 就是要求的優(yōu)先函數(shù)，若有矛盾，則不存在優(yōu)先函數(shù)。這里

49、所指的有沒有矛盾是指是否滿足下面的關(guān)系若，則 f(a) g(b) ；若 a<，則 f(a)< g(b) ；若 a>，則 f(a)> g(b)例：分）的綜合知識(shí)， 1222、21、2319 24. 實(shí)際大題（ 這道大題會(huì)給你一個(gè)文法， 問(wèn)你該文法是否為算符優(yōu)先文法？請(qǐng)根據(jù)、 集合構(gòu)造算符優(yōu)先關(guān)系表說(shuō)明之， 有可能還會(huì)讓你構(gòu)造他的優(yōu)先函數(shù)。老師的復(fù)習(xí)提綱里給出了一道題，沒有答案，事實(shí)證明 2012 年的考題中并沒有考這道題，請(qǐng)大家先做一做，希望大 38 / 47家能先自己親手動(dòng)筆試一試， 按照我上面說(shuō)的方法算一下， 并不難，個(gè)人認(rèn)為是目前的三道計(jì)算題中最簡(jiǎn)單的一道例：給出文

50、法 G（P）X Y Z 該文法是否為算符優(yōu)先文法？請(qǐng)根據(jù)、 集合構(gòu)造算符優(yōu)先關(guān)系表說(shuō)明之（答案是：不是算符優(yōu)先文法）9. 分析法屬于自底向上分析方法（小題）10. 從文法出發(fā)構(gòu)造（ 0）分析表的步驟（簡(jiǎn)答題！背！ ）(1) 構(gòu)造文法 G的拓廣文法 G'(2) 構(gòu)造(0) 項(xiàng)目(3) 構(gòu)造 G'的項(xiàng)目集規(guī)范族 ( 和函數(shù) )( 畫出一個(gè)確定的有限自動(dòng)機(jī) )(4) 構(gòu)造分析表四、語(yǔ)義分析 ( 小題) 綜合屬性用于“自下而上”傳遞信息在語(yǔ)法樹中， 一個(gè)結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)的屬性值確定。因此，通常使用自底向上的方法在每一個(gè)結(jié)點(diǎn)處使用語(yǔ) 39 / 47義規(guī)則計(jì)算綜合屬性的值。僅僅

51、使用綜合屬性的屬性文法稱 S屬性文法五、中間代碼生成繼承屬性用于“自上而下”傳遞信息。在語(yǔ)法樹中，一個(gè)結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和 / 或兄弟結(jié)點(diǎn)的某些屬性確定。用繼承屬性來(lái)表示程序語(yǔ)言結(jié)構(gòu)中的上下文依賴關(guān)系很方便。五、中間代碼生成 1. 中間代碼：（小題）是一種面向語(yǔ)法，易于翻譯成目標(biāo)代碼的代碼中間語(yǔ)言的形式有三種：后綴式、圖表示法（包括抽象語(yǔ)法樹和有向無(wú)環(huán)圖（） 兩種）、三地址代碼7. 后綴式（逆波蘭式）的概念（和 4 組成簡(jiǎn)答）把運(yùn)算量 ( 操作數(shù)) 寫在前面，把算符寫在后面。例如：，寫成逆波蘭式中各運(yùn)算法出現(xiàn)的順序與實(shí)際運(yùn)算順序一致這一塊沒什么好講的， 大家自己看看題， 相信能悟出

52、來(lái)其中的道理（下面是老師復(fù)習(xí)上的題）(1) a*()(2) *()40 / 47(3) *()(4) A (C D)(5) (A B) ( C D)(6) (A B) (C D E)解：(1) *(2) *+(3) *+(4) A C D(5) A B C D(6) A B C D E8. 后綴式與抽象語(yǔ)法樹（表達(dá)式樹）的關(guān)系（小題）后綴式其實(shí)是抽象語(yǔ)法書的線性表示形式， 并且是按后根序遍歷得到的。9. 將賦值語(yǔ)句表示成后綴式和四元式（簡(jiǎn)答題）這里不介紹什么方法了， 后綴式的求法已經(jīng)在上面介紹過(guò)， 關(guān)于四元式，大家看看這個(gè)例子相信自然就能夠明白。將表達(dá)式 ()*() 分別表示成后綴式、 四元式

53、 （這道題 2012 年考的是原題）解：5. 后綴式： a b c + e * b c + f / +6. 四元式41 / 47(1) ( +, b, c, T1 )(2) ( *, T1, e, T2 )(3) ( +, b, c, T3 )(4) ( /, T3, f, T4 )(5) ( +, T2, T4, T5 )(6) ( , T5, , a )再給一個(gè)例子：表達(dá)式-()*()-() 分別表示成四元式解：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. 簡(jiǎn)述代碼優(yōu)化的原則與優(yōu)化的級(jí)別，并列舉三種常用的優(yōu)化技術(shù) ( 小題)三個(gè)原則：等價(jià)原則：經(jīng)過(guò)優(yōu)化后不應(yīng)改變程序運(yùn)行的結(jié)果； ?有效原則