陳火旺編譯原理復(fù)習(xí)重點(diǎn)及復(fù)習(xí)思路總結(jié)

1、陳火旺編譯原理復(fù)習(xí)重點(diǎn)及復(fù)習(xí)思路總結(jié) 陳火旺編譯原理復(fù)習(xí)重點(diǎn)及復(fù)習(xí)思路總結(jié) 作為考研課程中最難的科目，編譯原理的復(fù)習(xí)一直以來(lái)困擾著無(wú)數(shù)的計(jì)算機(jī)考研者，特別是本科期間沒(méi)有認(rèn)真學(xué)習(xí)這門(mén)課程或者專(zhuān)業(yè)外的人士。由sodme寫(xiě)作的這一系列文章將主要以陳火旺院士的編譯原理教材為主線，對(duì)編譯原理的復(fù)習(xí)重點(diǎn)和復(fù)習(xí)思路進(jìn)行歸納和總結(jié)，以幫助大多數(shù)朋友盡快入門(mén)。由于絕大多數(shù)的本科編譯教材，都是在圍繞著原理性方面的知識(shí)進(jìn)行介紹和展開(kāi)，所以，本總結(jié)也合適于使用其它教材的朋友。anyway，希望使用各種不同教材的朋友都能從中受益并有所心得。 與數(shù)據(jù)結(jié)構(gòu)的總結(jié)類(lèi)似，關(guān)于編譯的總結(jié)都是采納我自己認(rèn)為比較容易理解的語(yǔ)言進(jìn)行描

2、述，絕不對(duì)書(shū)上的概念和算法進(jìn)行原原本本的照搬，這里，在多數(shù)狀況下講的都是我自己的學(xué)習(xí)經(jīng)驗(yàn)和學(xué)習(xí)心得。so，其行文寫(xiě)作的style可能有些朋友不太適應(yīng)，but，ipromise：這個(gè)總結(jié)絕不會(huì)平凡、泛泛無(wú)奇。ok，now，letsgo. 一、編譯原理的章節(jié)結(jié)構(gòu)及重點(diǎn)構(gòu)成 第1章引論：本章屬非重點(diǎn)章節(jié)，簡(jiǎn)單介紹了編譯的基本知識(shí)。出題分值不會(huì)太多，如果出題很多狀況是不出題，_，其分值比例一般狀況下不會(huì)超過(guò)5%.第2章高級(jí)語(yǔ)言及其語(yǔ)法描述：本章屬重要章節(jié)，在本章逐步引出了編譯的假設(shè)干基礎(chǔ)概念和術(shù)語(yǔ)。如果出題，其分值比例一般在5%-20%. 第3章詞法分析：重難點(diǎn)章節(jié)。本章是難點(diǎn)章節(jié)之一，同時(shí)又是編譯原

3、理最重要的章節(jié)和多數(shù)學(xué)校的必考章節(jié)之一，通常作為大題中的先行題考查。分值比例各有側(cè)重，一般在10%20%不等。 第4章語(yǔ)法分析自上而下分析：重難點(diǎn)章節(jié)。本章的難度要高于詞法分析一章，與詞法分析一章一樣，同屬編譯原理最重要的章節(jié)之一，是多校學(xué)校的必考章節(jié)之一，通常作為大題考查。如果出題，其分值在10%20%不等如果同一試卷中既出現(xiàn)詞法分析又出現(xiàn)語(yǔ)法分析，語(yǔ)法分析題目的分值一般比詞法分析的分值要大。 第5章語(yǔ)法分析自下而上分析：重難點(diǎn)章節(jié)。屬多數(shù)學(xué)校的必考章節(jié)之一，其重要性描述同上，通常作為大題考查。一般狀況下，在同一學(xué)校的同一張編譯試卷內(nèi)，多數(shù)不會(huì)同時(shí)考自上而下分析和自下而上分析兩種語(yǔ)法分析方法

4、，各學(xué)校會(huì)依據(jù)自身題目的難度定位選擇考查自上而下的還是自下而上的。自下而上的分析要難一點(diǎn)。如果本章出題，其分值比例約為：10%20%. 第6章屬性文法和語(yǔ)法治導(dǎo)翻譯：重難點(diǎn)章節(jié)。屬多數(shù)學(xué)校的必考章節(jié)之一。多數(shù)與語(yǔ)義分析一章聯(lián)合出題，通常作為大題考查。如果出題，本章的分值比例約為：10%20%左右。第7章語(yǔ)義分析和中間代碼生成：重難點(diǎn)章節(jié)，常考內(nèi)容之一，報(bào)考名校的同學(xué)應(yīng)該多留意本章節(jié)內(nèi)容。如果出題，本章分值約為：10%左右。 第8章符號(hào)表：非重點(diǎn)章節(jié)，本章介紹的是編譯過(guò)程中的輔助內(nèi)容，并未緊密聯(lián)系編譯的主體思想。多數(shù)學(xué)校在本章不出題，如果出題，其分值比例約為：5%左右。 第9章運(yùn)行時(shí)存儲(chǔ)空間組織

5、：?？純?nèi)容之一。本章多數(shù)會(huì)聯(lián)系實(shí)際語(yǔ)言進(jìn)行考查，如果出題，其分值比例約為：10%左右。 第10章優(yōu)化：?？純?nèi)容之一。分值比例約為：10%左右。 第11章目標(biāo)代碼生成：較少考查，即使考查，分?jǐn)?shù)比例一般在5%左右。第12章并行編譯基礎(chǔ)：很少考查，只作了解，了解其基本概念即可。 關(guān)于重要性標(biāo)識(shí)的幾點(diǎn)說(shuō)明：“必考內(nèi)容：是針關(guān)于多校學(xué)校一般的出題規(guī)律而言，本章極易被考到?；蛘哒f(shuō)，作為一個(gè)完整的試卷，本章是應(yīng)該被考查的，這是放在多個(gè)學(xué)校都比較合適的規(guī)律，也就是說(shuō)本章是不同的學(xué)校共同關(guān)注的章節(jié)?！俺？純?nèi)容：雖然本章內(nèi)容重要，但是，各校依據(jù)自己的考查方式，可能選擇考，也可能不選擇考查這一章，這樣的章節(jié)經(jīng)常作為

6、對(duì)必考章節(jié)的配合和補(bǔ)充，以完善和形成一張完整的試卷。這些章節(jié)要求讀者自己對(duì)所報(bào)院校的歷年試題進(jìn)行歸納和分析，從中找出哪些是是這一次比較容易考查到的。 注：關(guān)于分值比例的統(tǒng)計(jì)樣本來(lái)自于國(guó)防科大，中科院，上海交大，哈工大，清華等多所學(xué)校的歷年試題。 二、編譯原理各章節(jié)重點(diǎn)難點(diǎn)歸納第1章引論：本章作為編譯原理的開(kāi)啟章節(jié)，其意義在于為原本對(duì)編譯一無(wú)所知的朋友撩開(kāi)一條細(xì)縫，讓你從本章大致了解編譯程序工作的原理。所以，本章的考點(diǎn)都是象征性的。需要讀者掌握的是：清楚編譯程序的總框架，了解編譯程序工作的大致過(guò)程，能分辨清楚編譯前端與后端的區(qū)別及其互相配合的方法，要清楚編譯程序是如何生成的。請(qǐng)大家記憶并理解以下

7、概念：編譯程序，解釋程序，翻譯程序，掃描器，分析器，編譯前端與后端，符號(hào)表，“遍的概念等。說(shuō)讓大家記憶并理解以上概念，并不是要大家原原本本地記住書(shū)上的解釋?zhuān)亲尨蠹疫_(dá)到這樣的一種程度：知道這些概念的含義，并且能夠按照自己的語(yǔ)言對(duì)其進(jìn)行準(zhǔn)確描述。一般而言，當(dāng)你真正理解了一個(gè)概念之后，你是有能力對(duì)其進(jìn)行精辟描述的。針關(guān)于本章的考點(diǎn)，多數(shù)是考查這些小概念，比如國(guó)防科大就曾經(jīng)考過(guò)“掃描器等概念。inaword，理解第一。 第2章高級(jí)語(yǔ)言及其語(yǔ)法描述：本章的2.1和2.2節(jié)在先期為2.3節(jié)作了很多鋪墊，其目的是為了引出2.3中的幾個(gè)重量級(jí)概念：上下文無(wú)關(guān)文法，語(yǔ)法分析樹(shù)和二義性，同時(shí)也引出了與此緊密聯(lián)

8、系的其它概念：推導(dǎo)，句型，句子，最左推導(dǎo)，最右推導(dǎo)等。最后給出了另一個(gè)?？键c(diǎn)：?jiǎn)棠匪够姆椒ǚ诸?lèi)。 關(guān)于本章，讀者應(yīng)該掌握： 正確理解程序制定語(yǔ)言中語(yǔ)法和語(yǔ)義的含義，了解書(shū)上羅列的高級(jí)語(yǔ)言中的一般特性。一般狀況下，這兩點(diǎn)是不會(huì)直接考查的，如果是想考查某種高級(jí)語(yǔ)言的特性，也會(huì)放在后面的優(yōu)化或目標(biāo)代碼生成章節(jié)中進(jìn)行考查。所以，這里只要求你理解及了解。但是，下面的這些東東就是必須掌握的了，而且是必須通過(guò)大量作題掌握的： 1.上下文無(wú)關(guān)文法的定義，判斷和轉(zhuǎn)化，以及與上下文無(wú)關(guān)文法密切相關(guān)的概念。 首先，應(yīng)該掌握上下文無(wú)關(guān)文法的四個(gè)構(gòu)成要素；其次，應(yīng)該清楚關(guān)于上下文無(wú)關(guān)文法，其每個(gè)產(chǎn)生式的左部和右部必須

9、滿足的條件。在有關(guān)上下文無(wú)關(guān)文法的考點(diǎn)中，有這樣幾種考查方式：給出某語(yǔ)言的自然語(yǔ)言描述方式，要求寫(xiě)該語(yǔ)言的上下文無(wú)關(guān)文法表述形式；給出某語(yǔ)言的上下文無(wú)關(guān)文法，要求用自然語(yǔ)言描述該語(yǔ)言；給出某語(yǔ)言的上下文無(wú)法方法，要求證實(shí)該文法是否二義；給出某語(yǔ)言的上下文無(wú)關(guān)文法，要求給出指定句子的最左或最右推導(dǎo)；給出某語(yǔ)言的上下文無(wú)關(guān)文法，要求給出指定句子的語(yǔ)法分析樹(shù)；給出一個(gè)具有二義性的上下文無(wú)關(guān)文法，要求將其轉(zhuǎn)換成非二義性的。以上的綜合分析，幾乎含蓋了所有與上下文無(wú)關(guān)文法有關(guān)的出題角度，大家應(yīng)該全部掌握。2.喬姆斯基的文法分類(lèi)。 首先，應(yīng)該非常清楚喬姆斯基關(guān)于四種文法分類(lèi)的定義，并能理解其含義。幾種文法中

10、，最基本的是0型文法，讀者可以將它理解為其它所有文法的基礎(chǔ)，它是可以表示任何語(yǔ)言的文法。后面的1，2,3三種文法，是分別關(guān)于0型文法產(chǎn)生式的兩邊作了不同的限制之后，形成了新的文法。比如：規(guī)定0型文法的每個(gè)產(chǎn)生式中，其左邊字符集長(zhǎng)度小于右邊字符集長(zhǎng)度并且同時(shí)規(guī)定開(kāi)始符號(hào)只可出現(xiàn)于產(chǎn)生式的左邊，不能出現(xiàn)在任何產(chǎn)生式的右邊，這樣，就成為了1型文法(即上下文有關(guān)文法)。其它與此類(lèi)似，在1型文法的基礎(chǔ)上，進(jìn)一步規(guī)定該文法的任意產(chǎn)生式，其左部只同意有一個(gè)字符且必須為非終結(jié)符，這樣就構(gòu)成了上下文無(wú)關(guān)文法；再在上下文無(wú)關(guān)文法的基礎(chǔ)上進(jìn)行限制：規(guī)定除了左部有且只有一個(gè)非終結(jié)符外，還特別規(guī)定右部最多只同意有兩個(gè)字

11、符，當(dāng)為兩上字符時(shí)必須一個(gè)為非終結(jié)符，另一個(gè)為終結(jié)符，而當(dāng)只有一個(gè)字符時(shí)，必須為終結(jié)符，這樣的文法就成了正規(guī)文法。這樣一層套一層的限制，就形成了從0型到3型文法的定義體制，每一層都是在前一層基礎(chǔ)上進(jìn)行定義的，所以說(shuō)前一層一定比該層表示的范圍要廣，因?yàn)槠涫艿南拗埔佟?那么，我們?cè)谂袛嘁粋€(gè)文法時(shí)應(yīng)該以什么規(guī)則來(lái)判斷呢？這個(gè)規(guī)則當(dāng)然是：3-2-1-0.也就是說(shuō)，我們判斷是從高到低來(lái)判斷的，比如：一旦判斷其屬于正規(guī)文法之后就沒(méi)必要再判斷其是否屬于上下文無(wú)關(guān)的了(因?yàn)樗囟▽儆谏舷挛臒o(wú)關(guān)，我們應(yīng)該以最高規(guī)則來(lái)判定其屬于的文法類(lèi)型)，其它狀況與此類(lèi)推。只有當(dāng)我們判斷不屬于3型文法時(shí)，我們才向下判斷，其是

12、不是屬于2型的，假設(shè)不屬于2型的，則依此類(lèi)推再向下判斷。最終的結(jié)果如果不屬于3，2和1三種類(lèi)型，那就只有屬于0型了。 “給定一個(gè)文法，要求判斷其屬于何種文法是一個(gè)重要考點(diǎn)，其出題形式可能是填空，選擇等多種題型。 第3章詞法分析： 很多人覺(jué)得編譯這個(gè)科目很難學(xué)，望而生畏，以致于舉步不前，最大的一個(gè)原因是把編譯技術(shù)看得過(guò)于神秘化了。其實(shí)，說(shuō)白了，編譯這門(mén)課程無(wú)非就是對(duì)一個(gè)“大程序的各個(gè)部分、各個(gè)模塊上升到理論化的程度進(jìn)行分析和介紹。這個(gè)“大程序就是我們所要研究的“編譯程序。 前兩章為研究編譯技術(shù)作了一些概念和技術(shù)上的先期鋪墊，在本章的詞法分析內(nèi)容里將開(kāi)始介紹編譯技術(shù)的第一個(gè)重要技術(shù)點(diǎn)：詞法分析。

13、本章最為重要的內(nèi)容是3.3節(jié)：正規(guī)式和有限自動(dòng)機(jī)，關(guān)于詞法分析一章的考點(diǎn)，可以說(shuō)80%到90%以上集中在這一節(jié)的內(nèi)容上。針關(guān)于這一節(jié)的知識(shí)點(diǎn)介紹和考點(diǎn)分析，我們將稍后給出，現(xiàn)在先來(lái)看一下學(xué)習(xí)3.3節(jié)所必須先知道和理解的基本概念： a.詞法分析器的功能或稱詞法分析的任務(wù)：輸入的是源程序，輸出的是分析完成的單詞符號(hào)； b.狀態(tài)轉(zhuǎn)換圖：是一張有向圖，用于標(biāo)識(shí)在特定的輸入下詞法分析器應(yīng)該選擇的分析方向。 關(guān)于考點(diǎn)a，有些學(xué)校會(huì)作為選擇、判斷或填空題進(jìn)行考查，而關(guān)于考點(diǎn)b，多數(shù)是與有限自動(dòng)機(jī)一些考查，要求給出以“狀態(tài)圖表示確實(shí)定有限自動(dòng)機(jī)，也有的學(xué)校的試題中，是要求直接給出針關(guān)于某正規(guī)式的狀態(tài)轉(zhuǎn)換圖，比

14、如中科院曾經(jīng)考到：已知某系統(tǒng)下的設(shè)備文件名的定義方式以正規(guī)式給出，要求給出符合這種定義的狀態(tài)轉(zhuǎn)換圖。理解狀態(tài)轉(zhuǎn)換圖的含義是進(jìn)行本章學(xué)習(xí)的重要前提，大家記住一句話：狀態(tài)轉(zhuǎn)換圖，就是一張當(dāng)輸入不同的內(nèi)容時(shí)，選擇不同分析路徑的有向圖。 下面，我們重點(diǎn)看一下有關(guān)“正規(guī)式與有限自動(dòng)機(jī)這一考點(diǎn)的各種可能考查形式：a.題目給定一正規(guī)式，要求給出其nfa，dfa或最簡(jiǎn)dfa形式。 b.題目給定一用狀態(tài)圖表示的nfa，要求給出其對(duì)應(yīng)的dfa或最簡(jiǎn)dfa形式。c.題目給定一nfa，dfa或最簡(jiǎn)dfa，要求給出其對(duì)應(yīng)的正規(guī)式。d.題目給定一正規(guī)集，要求給出其相應(yīng)的dfa。 e.題目給定一用自然語(yǔ)言描述的正規(guī)集，要求

15、給出其相應(yīng)的正規(guī)式表示形式。 這些考點(diǎn)，綜合起來(lái)看，是在正規(guī)式，正規(guī)集，nfa和dfa之間作各種可能的轉(zhuǎn)換，當(dāng)然這種轉(zhuǎn)換正確與否的判斷標(biāo)準(zhǔn)就是轉(zhuǎn)換之后的內(nèi)容是不是與轉(zhuǎn)換之前的內(nèi)容等價(jià)，如果等價(jià)，我們就認(rèn)為轉(zhuǎn)換是正確的。 在考點(diǎn)e這類(lèi)的轉(zhuǎn)換題目中，有一些是需要另外規(guī)納出來(lái)的，他們?cè)谀骋环矫婢哂泄餐奶卣?，如果掌握了其中一題，將可舉一反三解出其它題。比如有以下的幾種題目就可以作以總結(jié)： 1.求偶奇數(shù)個(gè)a與偶奇數(shù)個(gè)b構(gòu)成的語(yǔ)言的正規(guī)式2.求能被34、5、或其它任意給定的n整除的正規(guī)式的dfa 3.求不以或以nn從0到9開(kāi)頭的xxxx符號(hào)某種條件的奇偶數(shù)數(shù)的正規(guī)式 以上三種類(lèi)型的考題，在每一種類(lèi)型中，

16、都是有規(guī)律可循的，也都有簡(jiǎn)便的方法可以幫助我們快速求解其正規(guī)式，進(jìn)而快速確定dfa及最簡(jiǎn)dfa。針關(guān)于這三種類(lèi)型的解題思路分析，我會(huì)在另外的文章中給出。 第4章語(yǔ)法分析自上而下的分析： 說(shuō)明：這一次的更新，確實(shí)有點(diǎn)慢了，距上次已經(jīng)有了20天的時(shí)間，這段時(shí)間主要因?yàn)閟odme所在的公司在進(jìn)行搬遷事宜，所以心境和環(huán)境都不太安定，讓大家久候了，以后我盡量在一到兩周左右的時(shí)間里把這個(gè)貼子更新完畢，今天是10月12日，請(qǐng)大家監(jiān)督，這個(gè)貼子最晚截止更新時(shí)間是10月26日。 大家在參閱編譯原理的這個(gè)重點(diǎn)歸納貼子時(shí)，可能會(huì)感覺(jué)與數(shù)據(jù)結(jié)構(gòu)規(guī)納貼子風(fēng)格不太一致，在編譯的總結(jié)里，我較多地講解了書(shū)上的一些我認(rèn)為是較難

17、理解的內(nèi)容，而不僅僅是給出考點(diǎn)。因?yàn)閺奈医佑|的網(wǎng)友反映的狀況看來(lái)，大家對(duì)編譯還是比較頭疼的，所以，我希望通過(guò)這樣的規(guī)納同時(shí)幫助大家從另外一個(gè)角度或以另外一種思維來(lái)看待編譯原理課程。 當(dāng)詞法分析器對(duì)源程序進(jìn)行了詞法分析，獲得了一個(gè)個(gè)獨(dú)立的單詞符號(hào)后，編譯程序總控模塊就會(huì)調(diào)用語(yǔ)法分析子程序?qū)@些單詞符號(hào)集進(jìn)行語(yǔ)法分析，也就是：利用該文法的產(chǎn)生式來(lái)判斷這些單詞符號(hào)是否足以構(gòu)成一個(gè)在語(yǔ)法上正確的程序。如果可以構(gòu)成一個(gè)在語(yǔ)法上正確的程序，則接著作編譯下面的工作，比如：語(yǔ)法治導(dǎo)翻譯，中間代碼生成、代碼優(yōu)化等工作；而如果不能構(gòu)成一個(gè)在語(yǔ)法上正確的程序，則給出相應(yīng)的錯(cuò)誤提示并將錯(cuò)誤信息記入對(duì)應(yīng)的數(shù)據(jù)記錄中。語(yǔ)

18、法分析的規(guī)則主要基于兩種：自上而下分析和自下而上分析。這一章，主要講解自上而下的分析方法。自上而下分析的大致思路是：依據(jù)產(chǎn)生式規(guī)則，從產(chǎn)生式的開(kāi)始符號(hào)進(jìn)行推導(dǎo)，一直推導(dǎo)到可以產(chǎn)生當(dāng)前要判斷的這個(gè)句子為止。如果推導(dǎo)了所有可能狀況，但沒(méi)有推出這樣的句子，那么這個(gè)句子就是不符合該語(yǔ)言的語(yǔ)法規(guī)則的產(chǎn)生式即定義了語(yǔ)言的語(yǔ)法規(guī)則。 在陳火旺老師的編譯教材上，具體描述了一種自上而下的分析方法：ll(1)分析法，陳老教材的這一章也是圍繞這一點(diǎn)而展開(kāi)的。下面，我們介紹一下本章的主要?？贾R(shí)點(diǎn)及考查角度： 1.給定一文法，要求將其改造成可以進(jìn)行自上而下分析的形式。這里面涉及到兩方面的知識(shí)點(diǎn)：左遞歸的去除及公因子的

19、提取。所謂的左遞歸是指產(chǎn)生式是形如：p-pab.的形式，即：產(chǎn)生式右邊的第一個(gè)字符就是該產(chǎn)生式左邊的那個(gè)非終結(jié)符。當(dāng)一個(gè)文法中有左遞歸的產(chǎn)生式時(shí)，是無(wú)法進(jìn)行自上而下推導(dǎo)的，因?yàn)橹灰@個(gè)產(chǎn)生式被推導(dǎo)，就勢(shì)必會(huì)使這種推導(dǎo)過(guò)程陷入一種遞歸循環(huán)無(wú)休止推導(dǎo)的情形。去除左遞歸的方法是比較簡(jiǎn)單的，其基本思路是將左遞歸通過(guò)轉(zhuǎn)化變成與之等價(jià)的右遞歸。馬上形如：p-pa|b形式的左遞歸變成如下形式：p-bp",p"-ap"|e(注：e表示空)。這一點(diǎn)只要多作學(xué)習(xí)，很快就會(huì)掌握。提取公因子的目的是為了避免推導(dǎo)過(guò)程中的回溯，也就是使每一次的向下推導(dǎo)是唯一的，而不是有多個(gè)選擇，因?yàn)橛卸鄠€(gè)選

20、擇的話就可能出現(xiàn)回溯。2.給定一文法，要求判斷其是否為ll(1)文法。判斷一個(gè)文法是否為ll(1)文法主要有兩種方法：一種是判斷文法是否二義，如果二義，則文法必定不為ll(1)注意：此命題的否合命題不真；二是依據(jù)陳老教材p73頁(yè)：關(guān)于ll(1)文法成立的三個(gè)條件。顯然，第一種判斷方法效率是比較高的，但是，其只能判斷文法“不為ll(1)的，并不能判定文法“是ll(1)的，要判斷文法“是ll(1)的，就得用第二種方法，但在考題中，如果要求你判斷某文法是否為ll(1)的，則該文法多半不是ll(1)的，而且此點(diǎn)可以很容易地用二義性來(lái)證實(shí)，這是一種?？夹问健?.給定一文法，要求構(gòu)造ll(1)分析表。ll

21、(1)分析的重點(diǎn)和難點(diǎn)內(nèi)容都在其分析表的構(gòu)造上，后面要講的lr分析也是，它的難點(diǎn)也在于其分析表的構(gòu)造。構(gòu)造ll(1)分析表是一個(gè)?？键c(diǎn)，也是大分值題的可能出題點(diǎn)，關(guān)于一般學(xué)校而言，相比于lr分析，他們更喜愛(ài)考ll(1)，因?yàn)閘r要比ll(1)復(fù)雜得多，而名校則更喜愛(ài)考lr，當(dāng)然，這只是針關(guān)于較普遍的狀況作的總結(jié)，并不是一定成立的推論。ll(1)分析表構(gòu)造前，需要先弄清first集和follow集的構(gòu)造方法，簡(jiǎn)單地說(shuō)，first集是用于求非終結(jié)符推出的產(chǎn)生式中的第一個(gè)終結(jié)符的，而follow集是用于求與該非終結(jié)符后緊鄰的那個(gè)終結(jié)符的。first集的構(gòu)造方法見(jiàn)教材p78頁(yè)，在構(gòu)造的三個(gè)規(guī)則中，前兩

22、個(gè)規(guī)則都是比較容易理解的，第三個(gè)規(guī)則看上去就有點(diǎn)復(fù)雜了，我們簡(jiǎn)單地來(lái)看第三條規(guī)則，就是：當(dāng)由x推出的產(chǎn)生式中前面假設(shè)干個(gè)非終結(jié)符，其first集均含有空時(shí)，就取這假設(shè)干個(gè)非結(jié)符的后一個(gè)字符的first集，當(dāng)然，這“后一個(gè)字符可能是終結(jié)符，也可能是非終結(jié)符，只要其first集不為空就行；而當(dāng)x推出的右邊全是非終結(jié)符，且這些非終結(jié)符的first集全含有空時(shí)，就把空加到first(x)中。follow集的構(gòu)造方法很簡(jiǎn)單，不作具體講解了。ll(1)分析表的構(gòu)造方法見(jiàn)教材p79頁(yè)，構(gòu)造規(guī)則主要有3條。說(shuō)到這里，大家應(yīng)該明確分析表中的各個(gè)單元到底代表什么含義，我作一下簡(jiǎn)單的介紹：分析表中的最頂一行，是產(chǎn)生

23、式中所有的終結(jié)符；分析表中的最左一列，是產(chǎn)生式中所有的非終結(jié)符；而產(chǎn)生式中間的諸多單元格則可以存放該文法的產(chǎn)生式或特別標(biāo)志(比如成功和錯(cuò)誤標(biāo)志)。這樣的二維表格構(gòu)成的單元格的含義是：當(dāng)左邊的非終結(jié)符碰到最上一行中的某個(gè)終結(jié)符時(shí)應(yīng)該選擇哪個(gè)產(chǎn)生式進(jìn)行向下的推導(dǎo)，這個(gè)產(chǎn)生式就是放在對(duì)應(yīng)二維坐標(biāo)處的產(chǎn)生式。4.給定一文法，先要求求解其ll(1)分析表，然后要求給出針關(guān)于某一個(gè)句子的具體分析過(guò)程。這個(gè)考點(diǎn)的第二問(wèn)主要就是考查考生對(duì)猜測(cè)分析程序的工作過(guò)程的理解了，猜測(cè)分析程序完全是按照分析表機(jī)械工作的，針關(guān)于考生而言，要明確何時(shí)出棧，何時(shí)入棧，以及如何入棧，這些細(xì)節(jié)信息都是要通過(guò)作題掌握的，只理解而不會(huì)

24、熟練解答是沒(méi)有用的。 5.給定一文法，要求給出其遞歸下降分析程序。遞歸下降分析的條件也是無(wú)左遞歸及不帶回溯，其構(gòu)造的過(guò)程比較簡(jiǎn)單，就是將每個(gè)非終結(jié)符處理成可以互相遞歸調(diào)用的過(guò)程體。具體過(guò)程參照p74到p75的例子，你可以試著寫(xiě)一下p76頁(yè)教材上未列出的f過(guò)程的實(shí)現(xiàn)。 下一次，我們會(huì)具體講解lr分析，敬請(qǐng)期待。如果網(wǎng)友對(duì)講解有什么看法或建議，也歡迎跟貼指出，謝謝大家。 后續(xù)內(nèi)容： 第5章語(yǔ)法分析自下而上的分析：第6章屬性文法和語(yǔ)法治導(dǎo)翻譯：第7章語(yǔ)義分析和中間代碼生成：第8章符號(hào)表： 第9章運(yùn)行時(shí)存儲(chǔ)空間組織：第10章優(yōu)化： 第11章目標(biāo)代碼生成：第12章并行編譯基礎(chǔ)： 歡迎來(lái)到免費(fèi)考研網(wǎng) 擴(kuò)大

25、閱讀：陳火旺編譯原理復(fù)習(xí)重點(diǎn) 前言： 作為考研課程中最難的科目，編譯原理的復(fù)習(xí)一直以來(lái)困擾著無(wú)數(shù)的計(jì)算機(jī)考研者，特別是本科期間沒(méi)有認(rèn)真學(xué)習(xí)這門(mén)課程或者專(zhuān)業(yè)外的人士。由sodme寫(xiě)作的這一系列文章將主要以陳火旺院士的編譯原理教材為主線，對(duì)編譯原理的復(fù)習(xí)重點(diǎn)和復(fù)習(xí)思路進(jìn)行歸納和總結(jié)，以幫助大多數(shù)朋友盡快入門(mén)。由于絕大多數(shù)的本科編譯教材，都是在圍繞著原理性方面的知識(shí)進(jìn)行介紹和展開(kāi)，所以，本總結(jié)也合適于使用其它教材的朋友。anyway，希望使用各種不同教材的朋友都能從中受益并有所心得。 與數(shù)據(jù)結(jié)構(gòu)的總結(jié)類(lèi)似，關(guān)于編譯的總結(jié)都是采納我自己認(rèn)為比較容易理解的語(yǔ)言進(jìn)行描述，絕不對(duì)書(shū)上的概念和算法進(jìn)行原原本本

26、的照搬，這里，在多數(shù)狀況下講的都是我自己的學(xué)習(xí)經(jīng)驗(yàn)和學(xué)習(xí)心得。so，其行文寫(xiě)作的style可能有些朋友不太適應(yīng)，but，ipromise：這個(gè)總結(jié)絕不會(huì)平凡、泛泛無(wú)奇。ok，now，letsgo. 一、編譯原理的章節(jié)結(jié)構(gòu)及重點(diǎn)構(gòu)成 第1章引論：本章屬非重點(diǎn)章節(jié)，簡(jiǎn)單介紹了編譯的基本知識(shí)。出題分值不會(huì)太多，如果出題很多狀況是不出題，_，其分值比例一般狀況下不會(huì)超過(guò)5%.第2章高級(jí)語(yǔ)言及其語(yǔ)法描述：本章屬重要章節(jié)，在本章逐步引出了編譯的假設(shè)干基礎(chǔ)概念和術(shù)語(yǔ)。如果出題，其分值比例一般在5%-20%. 第3章詞法分析：重難點(diǎn)章節(jié)。本章是難點(diǎn)章節(jié)之一，同時(shí)又是編譯原理最重要的章節(jié)和多數(shù)學(xué)校的必考章節(jié)之一

27、，通常作為大題中的先行題考查。分值比例各有側(cè)重，一般在10%20%不等。 第4章語(yǔ)法分析自上而下分析：重難點(diǎn)章節(jié)。本章的難度要高于詞法分析一章，與詞法分析一章一樣，同屬編譯原理最重要的章節(jié)之一，是多校學(xué)校的必考章節(jié)之一，通常作為大題考查。如果出題，其分值在10%20%不等如果同一試卷中既出現(xiàn)詞法分析又出現(xiàn)語(yǔ)法分析，語(yǔ)法分析題目的分值一般比詞法分析的分值要大。 第5章語(yǔ)法分析自下而上分析：重難點(diǎn)章節(jié)。屬多數(shù)學(xué)校的必考章節(jié)之一，其重要性描述同上，通常作為大題考查。一般狀況下，在同一學(xué)校的同一張編譯試卷內(nèi)，多數(shù)不會(huì)同時(shí)考自上而下分析和自下而上分析兩種語(yǔ)法分析方法，各學(xué)校會(huì)依據(jù)自身題目的難度定位選擇考

28、查自上而下的還是自下而上的。自下而上的分析要難一點(diǎn)。如果本章出題，其分值比例約為：10%20%. 第6章屬性文法和語(yǔ)法治導(dǎo)翻譯：重難點(diǎn)章節(jié)。屬多數(shù)學(xué)校的必考章節(jié)之一。多數(shù)與語(yǔ)義分析一章聯(lián)合出題，通常作為大題考查。如果出題，本章的分值比例約為：10%20%左右。第7章語(yǔ)義分析和中間代碼生成：重難點(diǎn)章節(jié)，?？純?nèi)容之一，報(bào)考名校的同學(xué)應(yīng)該多留意本章節(jié)內(nèi)容。如果出題，本章分值約為：10%左右。 第8章符號(hào)表：非重點(diǎn)章節(jié)，本章介紹的是編譯過(guò)程中的輔助內(nèi)容，并未緊密聯(lián)系編譯的主體思想。多數(shù)學(xué)校在本章不出題，如果出題，其分值比例約為：5%左右。 第9章運(yùn)行時(shí)存儲(chǔ)空間組織：?？純?nèi)容之一。本章多數(shù)會(huì)聯(lián)系實(shí)際語(yǔ)言

29、進(jìn)行考查，如果出題，其分值比例約為：10%左右。 第10章優(yōu)化：常考內(nèi)容之一。分值比例約為：10%左右。 第11章目標(biāo)代碼生成：較少考查，即使考查，分?jǐn)?shù)比例一般在5%左右。第12章并行編譯基礎(chǔ)：很少考查，只作了解，了解其基本概念即可。關(guān)于重要性標(biāo)識(shí)的幾點(diǎn)說(shuō)明：“必考內(nèi)容：是針關(guān)于多校學(xué)校一般的出題規(guī)律而言，本章極易被考到。或者說(shuō)，作為一個(gè)完整的試卷，本章是應(yīng)該被考查的，這是放在多個(gè)學(xué)校都比較合適的規(guī)律，也就是說(shuō)本章是不同的學(xué)校共同關(guān)注的章節(jié)?！俺？純?nèi)容：雖然本章內(nèi)容重要，但是，各校依據(jù)自己的考查方式，可能選擇考，也可能不選擇考查這一章，這樣的章節(jié)經(jīng)常作為對(duì)必考章節(jié)的配合和補(bǔ)充，以完善和形成一張

30、完整的試卷。這些章節(jié)要求讀者自己對(duì)所報(bào)院校的歷年試題進(jìn)行歸納和分析，從中找出哪些是是這一次比較容易考查到的。 注：關(guān)于分值比例的統(tǒng)計(jì)樣本來(lái)自于國(guó)防科大，中科院，上海交大，哈工大，清華等多所學(xué)校的歷年試題。 二、編譯原理各章節(jié)重點(diǎn)難點(diǎn)歸納第1章引論： 本章作為編譯原理的開(kāi)啟章節(jié)，其意義在于為原本對(duì)編譯一無(wú)所知的朋友撩開(kāi)一條細(xì)縫，讓你從本章大致了解編譯程序工作的原理。所以，本章的考點(diǎn)都是象征性的。需要讀者掌握的是：清楚編譯程序的總框架，了解編譯程序工作的大致過(guò)程，能分辨清楚編譯前端與后端的區(qū)別及其互相配合的方法，要清楚編譯程序是如何生成的。請(qǐng)大家記憶并理解以下概念：編譯程序，解釋程序，翻譯程序，掃

31、描器，分析器，編譯前端與后端，符號(hào)表，“遍的概念等。說(shuō)讓大家記憶并理解以上概念，并不是要大家原原本本地記住書(shū)上的解釋?zhuān)亲尨蠹疫_(dá)到這樣的一種程度：知道這些概念的含義，并且能夠按照自己的語(yǔ)言對(duì)其進(jìn)行準(zhǔn)確描述。一般而言，當(dāng)你真正理解了一個(gè)概念之后，你是有能力對(duì)其進(jìn)行精辟描述的。針關(guān)于本章的考點(diǎn)，多數(shù)是考查這些小概念，比如國(guó)防科大就曾經(jīng)考過(guò)“掃描器等概念。inaword，理解第一。 第2章高級(jí)語(yǔ)言及其語(yǔ)法描述： 本章的2.1和2.2節(jié)在先期為2.3節(jié)作了很多鋪墊，其目的是為了引出2.3中的幾個(gè)重量級(jí)概念：上下文無(wú)關(guān)文法，語(yǔ)法分析樹(shù)和二義性，同時(shí)也引出了與此緊密聯(lián)系的其它概念：推導(dǎo)，句型，句子，最左

32、推導(dǎo)，最右推導(dǎo)等。最后給出了另一個(gè)?？键c(diǎn)：?jiǎn)棠匪够姆椒ǚ诸?lèi)。 關(guān)于本章，讀者應(yīng)該掌握： 正確理解程序制定語(yǔ)言中語(yǔ)法和語(yǔ)義的含義，了解書(shū)上羅列的高級(jí)語(yǔ)言中的一般特性。一般狀況下，這兩點(diǎn)是不會(huì)直接考查的，如果是想考查某種高級(jí)語(yǔ)言的特性，也會(huì)放在后面的優(yōu)化或目標(biāo)代碼生成章節(jié)中進(jìn)行考查。所以，這里只要求你理解及了解。但是，下面的這些東東就是必須掌握的了，而且是必須通過(guò)大量作題掌握的： 1.上下文無(wú)關(guān)文法的定義，判斷和轉(zhuǎn)化，以及與上下文無(wú)關(guān)文法密切相關(guān)的概念。 首先，應(yīng)該掌握上下文無(wú)關(guān)文法的四個(gè)構(gòu)成要素；其次，應(yīng)該清楚關(guān)于上下文無(wú)關(guān)文法，其每個(gè)產(chǎn)生式的左部和右部必須滿足的條件。在有關(guān)上下文無(wú)關(guān)文法的考

33、點(diǎn)中，有這樣幾種考查方式：給出某語(yǔ)言的自然語(yǔ)言描述方式，要求寫(xiě)該語(yǔ)言的上下文無(wú)關(guān)文法表述形式；給出某語(yǔ)言的上下文無(wú)關(guān)文法，要求用自然語(yǔ)言描述該語(yǔ)言；給出某語(yǔ)言的上下文無(wú)法方法，要求證實(shí)該文法是否二義；給出某語(yǔ)言的上下文無(wú)關(guān)文法，要求給出指定句子的最左或最右推導(dǎo)；給出某語(yǔ)言的上下文無(wú)關(guān)文法，要求給出指定句子的語(yǔ)法分析樹(shù)；給出一個(gè)具有二義性的上下文無(wú)關(guān)文法，要求將其轉(zhuǎn)換成非二義性的。以上的綜合分析，幾乎含蓋了所有與上下文無(wú)關(guān)文法有關(guān)的出題角度，大家應(yīng)該全部掌握。 2.喬姆斯基的文法分類(lèi)。 首先，應(yīng)該非常清楚喬姆斯基關(guān)于四種文法分類(lèi)的定義，并能理解其含義。幾種文法中，最基本的是0型文法，讀者可以將它

34、理解為其它所有文法的基礎(chǔ)，它是可以表示任何語(yǔ)言的文法。后面的1，2,3三種文法，是分別關(guān)于0型文法產(chǎn)生式的兩邊作了不同的限制之后，形成了新的文法。比如：規(guī)定0型文法的每個(gè)產(chǎn)生式中，其左邊字符集長(zhǎng)度小于右邊字符集長(zhǎng)度并且同時(shí)規(guī)定開(kāi)始符號(hào)只可出現(xiàn)于產(chǎn)生式的左邊，不能出現(xiàn)在任何產(chǎn)生式的右邊，這樣，就成為了1型文法(即上下文有關(guān)文法)。其它與此類(lèi)似，在1型文法的基礎(chǔ)上，進(jìn)一步規(guī)定該文法的任意產(chǎn)生式，其左部只同意有一個(gè)字符且必須為非終結(jié)符，這樣就構(gòu)成了上下文無(wú)關(guān)文法；再在上下文無(wú)關(guān)文法的基礎(chǔ)上進(jìn)行限制：規(guī)定除了左部有且只有一個(gè)非終結(jié)符外，還特別規(guī)定右部最多只同意有兩個(gè)字符，當(dāng)為兩上字符時(shí)必須一個(gè)為非終結(jié)

35、符，另一個(gè)為終結(jié)符，而當(dāng)只有一個(gè)字符時(shí)，必須為終結(jié)符，這樣的文法就成了正規(guī)文法。這樣一層套一層的限制，就形成了從0型到3型文法的定義體制，每一層都是在前一層基礎(chǔ)上進(jìn)行定義的，所以說(shuō)前一層一定比該層表示的范圍要廣，因?yàn)槠涫艿南拗埔佟?那么，我們?cè)谂袛嘁粋€(gè)文法時(shí)應(yīng)該以什么規(guī)則來(lái)判斷呢？這個(gè)規(guī)則當(dāng)然是：3->2->1->0.也就是說(shuō)，我們判斷是從高到低來(lái)判斷的，比如：一旦判斷其屬于正規(guī)文法之后就沒(méi)必要再判斷其是否屬于上下文無(wú)關(guān)的了(因?yàn)樗囟▽儆谏舷挛臒o(wú)關(guān)，我們應(yīng)該以最高規(guī)則來(lái)判定其屬于的文法類(lèi)型)，其它狀況與此類(lèi)推。只有當(dāng)我們判斷不屬于3型文法時(shí)，我們才向下判斷，其是不是屬于2

36、型的，假設(shè)不屬于2型的，則依此類(lèi)推再向下判斷。最終的結(jié)果如果不屬于3，2和1三種類(lèi)型，那就只有屬于0型了。 “給定一個(gè)文法，要求判斷其屬于何種文法是一個(gè)重要考點(diǎn)，其出題形式可能是填空，選擇等多種題型。 第3章詞法分析： 很多人覺(jué)得編譯這個(gè)科目很難學(xué)，望而生畏，以致于舉步不前，最大的一個(gè)原因是把編譯技術(shù)看得過(guò)于神秘化了。其實(shí)，說(shuō)白了，編譯這門(mén)課程無(wú)非就是對(duì)一個(gè)“大程序的各個(gè)部分、各個(gè)模塊上升到理論化的程度進(jìn)行分析和介紹。這個(gè)“大程序就是我們所要研究的“編譯程序。 前兩章為研究編譯技術(shù)作了一些概念和技術(shù)上的先期鋪墊，在本章的詞法分析內(nèi)容里將開(kāi)始介紹編譯技術(shù)的第一個(gè)重要技術(shù)點(diǎn)：詞法分析。 本章最為重

37、要的內(nèi)容是3.3節(jié)：正規(guī)式和有限自動(dòng)機(jī)，關(guān)于詞法分析一章的考點(diǎn)，可以說(shuō)80%到90%以上集中在這一節(jié)的內(nèi)容上。針關(guān)于這一節(jié)的知識(shí)點(diǎn)介紹和考點(diǎn)分析，我們將稍后給出，現(xiàn)在先來(lái)看一下學(xué)習(xí)3.3節(jié)所必須先知道和理解的基本概念： a.詞法分析器的功能或稱詞法分析的任務(wù)：輸入的是源程序，輸出的是分析完成的單詞符號(hào)； b.狀態(tài)轉(zhuǎn)換圖：是一張有向圖，用于標(biāo)識(shí)在特定的輸入下詞法分析器應(yīng)該選擇的分析方向。 關(guān)于考點(diǎn)a，有些學(xué)校會(huì)作為選擇、判斷或填空題進(jìn)行考查，而關(guān)于考點(diǎn)b，多數(shù)是與有限自動(dòng)機(jī)一些考查，要求給出以“狀態(tài)圖表示確實(shí)定有限自動(dòng)機(jī)，也有的學(xué)校的試題中，是要求直接給出針關(guān)于某正規(guī)式的狀態(tài)轉(zhuǎn)換圖，比如中科院曾

38、經(jīng)考到：已知某系統(tǒng)下的設(shè)備文件名的定義方式以正規(guī)式給出，要求給出符合這種定義的狀態(tài)轉(zhuǎn)換圖。理解狀態(tài)轉(zhuǎn)換圖的含義是進(jìn)行本章學(xué)習(xí)的重要前提，大家記住一句話：狀態(tài)轉(zhuǎn)換圖，就是一張當(dāng)輸入不同的內(nèi)容時(shí)，選擇不同分析路徑的有向圖。 下面，我們重點(diǎn)看一下有關(guān)“正規(guī)式與有限自動(dòng)機(jī)這一考點(diǎn)的各種可能考查形式：a.題目給定一正規(guī)式，要求給出其nfa，dfa或最簡(jiǎn)dfa形式。 b.題目給定一用狀態(tài)圖表示的nfa，要求給出其對(duì)應(yīng)的dfa或最簡(jiǎn)dfa形式。c.題目給定一nfa，dfa或最簡(jiǎn)dfa，要求給出其對(duì)應(yīng)的正規(guī)式。d.題目給定一正規(guī)集，要求給出其相應(yīng)的dfa。 e.題目給定一用自然語(yǔ)言描述的正規(guī)集，要求給出其相應(yīng)

39、的正規(guī)式表示形式。 這些考點(diǎn)，綜合起來(lái)看，是在正規(guī)式，正規(guī)集，nfa和dfa之間作各種可能的轉(zhuǎn)換，當(dāng)然這種轉(zhuǎn)換正確與否的判斷標(biāo)準(zhǔn)就是轉(zhuǎn)換之后的內(nèi)容是不是與轉(zhuǎn)換之前的內(nèi)容等價(jià)，如果等價(jià)，我們就認(rèn)為轉(zhuǎn)換是正確的。 在考點(diǎn)e這類(lèi)的轉(zhuǎn)換題目中，有一些是需要另外規(guī)納出來(lái)的，他們?cè)谀骋环矫婢哂泄餐奶卣?，如果掌握了其中一題，將可舉一反三解出其它題。比如有以下的幾種題目就可以作以總結(jié)： 1.求偶奇數(shù)個(gè)a與偶奇數(shù)個(gè)b構(gòu)成的語(yǔ)言的正規(guī)式2.求能被34、5、或其它任意給定的n整除的正規(guī)式的dfa 3.求不以或以nn從0到9開(kāi)頭的xxxx符號(hào)某種條件的奇偶數(shù)數(shù)的正規(guī)式 以上三種類(lèi)型的考題，在每一種類(lèi)型中，都是有規(guī)律

40、可循的，也都有簡(jiǎn)便的方法可以幫助我們快速求解其正規(guī)式，進(jìn)而快速確定dfa及最簡(jiǎn)dfa。針關(guān)于這三種類(lèi)型的解題思路分析，我會(huì)在另外的文章中給出。 第4章語(yǔ)法分析自上而下的分析：說(shuō)明：這一次的更新，確實(shí)有點(diǎn)慢了，距上次已經(jīng)有了20天的時(shí)間，這段時(shí)間主要因?yàn)閟odme所在的公司在進(jìn)行搬遷事宜，所以心境和環(huán)境都不太安定，讓大家久候了，以后我盡量在一到兩周左右的時(shí)間里把這個(gè)貼子更新完畢，今天是10月12日，請(qǐng)大家監(jiān)督，這個(gè)貼子最晚截止更新時(shí)間是10月26日。 大家在參閱編譯原理的這個(gè)重點(diǎn)歸納貼子時(shí)，可能會(huì)感覺(jué)與數(shù)據(jù)結(jié)構(gòu)規(guī)納貼子風(fēng)格不太一致，在編譯的總結(jié)里，我較多地講解了書(shū)上的一些我認(rèn)為是較難理解的內(nèi)容，

41、而不僅僅是給出考點(diǎn)。因?yàn)閺奈医佑|的網(wǎng)友反映的狀況看來(lái)，大家對(duì)編譯還是比較頭疼的，所以，我希望通過(guò)這樣的規(guī)納同時(shí)幫助大家從另外一個(gè)角度或以另外一種思維來(lái)看待編譯原理課程。 當(dāng)詞法分析器對(duì)源程序進(jìn)行了詞法分析，獲得了一個(gè)個(gè)獨(dú)立的單詞符號(hào)后，編譯程序總控模塊就會(huì)調(diào)用語(yǔ)法分析子程序?qū)@些單詞符號(hào)集進(jìn)行語(yǔ)法分析，也就是：利用該文法的產(chǎn)生式來(lái)判斷這些單詞符號(hào)是否足以構(gòu)成一個(gè)在語(yǔ)法上正確的程序。如果可以構(gòu)成一個(gè)在語(yǔ)法上正確的程序，則接著作編譯下面的工作，比如：語(yǔ)法治導(dǎo)翻譯，中間代碼生成、代碼優(yōu)化等工作；而如果不能構(gòu)成一個(gè)在語(yǔ)法上正確的程序，則給出相應(yīng)的錯(cuò)誤提示并將錯(cuò)誤信息記入對(duì)應(yīng)的數(shù)據(jù)記錄中。 語(yǔ)法分析的規(guī)

42、則主要基于兩種：自上而下分析和自下而上分析。這一章，主要講解自上而下的分析方法。自上而下分析的大致思路是：依據(jù)產(chǎn)生式規(guī)則，從產(chǎn)生式的開(kāi)始符號(hào)進(jìn)行推導(dǎo)，一直推導(dǎo)到可以產(chǎn)生當(dāng)前要判斷的這個(gè)句子為止。如果推導(dǎo)了所有可能狀況，但沒(méi)有推出這樣的句子，那么這個(gè)句子就是不符合該語(yǔ)言的語(yǔ)法規(guī)則的產(chǎn)生式即定義了語(yǔ)言的語(yǔ)法規(guī)則。 在陳火旺老師的編譯教材上，具體描述了一種自上而下的分析方法：ll(1)分析法，陳老教材的這一章也是圍繞這一點(diǎn)而展開(kāi)的。下面，我們介紹一下本章的主要?？贾R(shí)點(diǎn)及考查角度： 1.給定一文法，要求將其改造成可以進(jìn)行自上而下分析的形式。這里面涉及到兩方面的知識(shí)點(diǎn)：左遞歸的去除及公因子的提取。所謂

43、的左遞歸是指產(chǎn)生式是形如：p->pab.的形式，即：產(chǎn)生式右邊的第一個(gè)字符就是該產(chǎn)生式左邊的那個(gè)非終結(jié)符。當(dāng)一個(gè)文法中有左遞歸的產(chǎn)生式時(shí)，是無(wú)法進(jìn)行自上而下推導(dǎo)的，因?yàn)橹灰@個(gè)產(chǎn)生式被推導(dǎo)，就勢(shì)必會(huì)使這種推導(dǎo)過(guò)程陷入一種遞歸循環(huán)無(wú)休止推導(dǎo)的情形。去除左遞歸的方法是比較簡(jiǎn)單的，其基本思路是將左遞歸通過(guò)轉(zhuǎn)化變成與之等價(jià)的右遞歸。馬上形如：p->pa|b形式的左遞歸變成如下形式：p->bp",p"->ap"|e(注：e表示空)。這一點(diǎn)只要多作學(xué)習(xí)，很快就會(huì)掌握。提取公因子的目的是為了避免推導(dǎo)過(guò)程中的回溯，也就是使每一次的向下推導(dǎo)是唯一的，而不是有多個(gè)選擇，因?yàn)橛卸鄠€(gè)選擇的話就可能出現(xiàn)回溯。2.給定一文法，要求判斷其是否為ll(1)文法。判斷一個(gè)文法是否為ll(1)文法主要有兩種方法：一種是判斷文法是否二義，如果二義，則文法必定不為ll(1)注意：此命題的否合命題不真；二是依據(jù)陳老教材p73頁(yè)：關(guān)于ll(1)文法成立的三個(gè)條件。顯然，第一種判斷方法效率是比較高的，