陳火旺編譯原理復(fù)習重點及復(fù)習思路總結(jié)
作為考研課程中最難的科目，編譯原理的復(fù)習一直以來困擾著無數(shù)的計算機考研者，特別是本科期間沒有認真學習這門課程或者專業(yè)外的人士。由sodme寫作的這一系列文章將主要以陳火旺院士的編譯原理教材為主線，對編譯原理的復(fù)習重點和復(fù)習思路進行歸納和總結(jié)，以幫助大多數(shù)朋友盡快入門。由于絕大多數(shù)的本科編譯教材，都是在圍繞著原理性方面的知識進行介紹和展開，所以，本總結(jié)也適合于使用其它教材的朋友。anyway，希望使用各種不同教材的朋友都能從中受益并有所感悟。
與數(shù)據(jù)結(jié)構(gòu)的總結(jié)類似，對于編譯的總結(jié)都是采用我自己認為比較容易理解的語言進行描述，絕不對書上的概念和算法進行原原本本的照搬，這里，在多數(shù)情況下講的都是我自己的學習經(jīng)驗和學習心得。So，其行文寫作的style可能有些朋友不太適應(yīng)，but，Ipromise：這個總結(jié)絕不會平庸、泛泛無奇。Ok，now，let’sgo.
一、編譯原理的章節(jié)結(jié)構(gòu)及重點構(gòu)成
第1章引論：本章屬非重點章節(jié)，簡單介紹了編譯的基本知識。出題分值不會太多，如果出題（很多情況是不出題，^_^），其分值比例一般情況下不會超過5%.第2章高級語言及其語法描述：本章屬重要章節(jié)，在本章逐步引出了編譯的若干基礎(chǔ)概念和術(shù)語。如果出題，其分值比例一般在5%-20%.
第3章詞法分析：重難點章節(jié)。本章是難點章節(jié)之一，同時又是編譯原理最重要的章節(jié)和多數(shù)學校的必考章節(jié)之一，通常作為大題中的先行題考查。分值比例各有側(cè)重，一般在10%~20%不等。
第4章語法分析－自上而下分析：重難點章節(jié)。本章的難度要高于詞法分析一章，與詞法分析一章一樣，同屬編譯原理最重要的章節(jié)之一，是多校學校的必考章節(jié)之一，通常作為大題考查。如果出題，其分值在10%~20%不等（如果同一試卷中既出現(xiàn)詞法分析又出現(xiàn)語法分析，語法分析題目的分值一般比詞法分析的分值要大）。
第5章語法分析－自下而上分析：重難點章節(jié)。屬多數(shù)學校的必考章節(jié)之一，其重要性描述同上，通常作為大題考查。一般情況下，在同一學校的同一張編譯試卷內(nèi)，多數(shù)不會同時考自上而下分析和自下而上分析兩種語法分析方法，各學校會根據(jù)自身題目的難度定位選擇考查自上而下的還是自下而上的。自下而上的分析要難一點。如果本章出題，其分值比例約為：10%~20%.
第6章屬性文法和語法制導(dǎo)翻譯：重難點章節(jié)。屬多數(shù)學校的必考章節(jié)之一。多數(shù)與語義分析一章聯(lián)合出題，通常作為大題考查。如果出題，本章的分值比例約為：10%~20%左右。第7章語義分析和中間代碼生成：重難點章節(jié)，�？純�(nèi)容之一，報考名校的同學應(yīng)該多留意本章節(jié)內(nèi)容。如果出題，本章分值約為：10%左右。
第8章符號表：非重點章節(jié)，本章介紹的是編譯過程中的輔助內(nèi)容，并未緊密聯(lián)系編譯的主體思想。多數(shù)學校在本章不出題，如果出題，其分值比例約為：5%左右。
第9章運行時存儲空間組織：常考內(nèi)容之一。本章多數(shù)會聯(lián)系實際語言進行考查，如果出題，其分值比例約為：10%左右。
第10章優(yōu)化：常考內(nèi)容之一。分值比例約為：10%左右。
第11章目標代碼生成：較少考查，即使考查，分數(shù)比例一般在5%左右。第12章并行編譯基礎(chǔ)：很少考查，只作了解，了解其基本概念即可。
關(guān)于重要性標識的幾點說明：“必考內(nèi)容”：是針對于多校學校一般的出題規(guī)律而言，本章極易被考到�；蛘哒f，作為一個完整的試卷，本章是應(yīng)該被考查的，這是放在多個學校都比較適合的規(guī)律，也就是說本章是不同的學校共同關(guān)注的章節(jié)�！俺？純�(nèi)容”：雖然本章內(nèi)容重要，但是，各校根據(jù)自己的考查方式，可能選擇考，也可能不選擇考查這一章，這樣的章節(jié)常常作為對必考章節(jié)的配合和補充，以完善和形成一張完整的試卷。這些章節(jié)要求讀者自己對所報院校的歷年試題進行歸納和分析，從中找出哪些是是這一次比較容易考查到的。
注：關(guān)于分值比例的統(tǒng)計樣本來自于國防科大，中科院，上海交大，哈工大，清華等多所學校的歷年試題。
二、編譯原理各章節(jié)重點難點歸納第1章引論：本章作為編譯原理的開啟章節(jié)，其意義在于為原本對編譯一無所知的朋友撩開一條細縫，讓你從本章大致了解編譯程序工作的原理。所以，本章的考點都是象征性的。需要讀者掌握的是：清楚編譯程序的總框架，了解編譯程序工作的大致過程，能分辨清楚編譯前端與后端的區(qū)別及其相互配合的方法，要清楚編譯程序是如何生成的。請大家記憶并理解以下概念：編譯程序，解釋程序，翻譯程序，掃描器，分析器，編譯前端與后端，符號表，“遍”的概念等。說讓大家記憶并理解以上概念，并不是要大家原原本本地記住書上的解釋，而是讓大家達到這樣的一種程度：知道這些概念的含義，并且能夠按照自己的語言對其進行準確描述。一般而言，當你真正理解了一個概念之后，你是有能力對其進行精辟描述的。針對于本章的考點，多數(shù)是考查這些小概念，比如國防科大就曾經(jīng)考過“掃描器”等概念。Inaword，理解第一。
第2章高級語言及其語法描述：本章的2.1和2.2節(jié)在先期為2.3節(jié)作了很多鋪墊，其目的是為了引出2.3中的幾個重量級概念：上下文無關(guān)文法，語法分析樹和二義性，同時也引出了與此緊密聯(lián)系的其它概念：推導(dǎo)，句型，句子，最左推導(dǎo)，最右推導(dǎo)等。最后給出了另一個�？键c：喬姆斯基的方法分類。
對于本章，讀者應(yīng)該掌握：
正確理解程序設(shè)計語言中語法和語義的含義，了解書上列舉的高級語言中的一般特性。一般情況下，這兩點是不會直接考查的，如果是想考查某種高級語言的特性，也會放在后面的優(yōu)化或目標代碼生成章節(jié)中進行考查。所以，這里只要求你理解及了解。但是，下面的這些東東就是必須掌握的了，而且是必須通過大量作題掌握的：
1.上下文無關(guān)文法的定義，判斷和轉(zhuǎn)化，以及與上下文無關(guān)文法密切相關(guān)的概念。
首先，應(yīng)該掌握上下文無關(guān)文法的四個構(gòu)成要素；其次，應(yīng)該清楚對于上下文無關(guān)文法，其每個產(chǎn)生式的左部和右部必須滿足的條件。在有關(guān)上下文無關(guān)文法的考點中，有這樣幾種考查方式：給出某語言的自然語言描述方式，要求寫該語言的上下文無關(guān)文法表述形式；給出某語言的上下文無關(guān)文法，要求用自然語言描述該語言；給出某語言的上下文無法方法，要求證明該文法是否二義；給出某語言的上下文無關(guān)文法，要求給出指定句子的最左或最右推導(dǎo)；給出某語言的上下文無關(guān)文法，要求給出指定句子的語法分析樹；給出一個具有二義性的上下文無關(guān)文法，要求將其轉(zhuǎn)換成非二義性的。以上的綜合分析，幾乎含蓋了所有與上下文無關(guān)文法有關(guān)的出題角度，大家應(yīng)該全部掌握。2.喬姆斯基的文法分類。
首先，應(yīng)該非常清楚喬姆斯基對于四種文法分類的定義，并能理解其含義。幾種文法中，最基本的是0型文法，讀者可以將它理解為其它所有文法的基礎(chǔ)，它是可以表示任何語言的文法。后面的1，2,3三種文法，是分別對于0型文法產(chǎn)生式的兩邊作了不同的限制之后，形成了新的文法。比如：規(guī)定0型文法的每個產(chǎn)生式中，其左邊字符集長度小于右邊字符集長度并且同時規(guī)定開始符號只可出現(xiàn)于產(chǎn)生式的左邊，不能出現(xiàn)在任何產(chǎn)生式的右邊，這樣，就成為了1型文法(即上下文有關(guān)文法)。其它與此類似，在1型文法的基礎(chǔ)上，進一步規(guī)定該文法的任意產(chǎn)生式，其左部只允許有一個字符且必須為非終結(jié)符，這樣就構(gòu)成了上下文無關(guān)文法；再在上下文無關(guān)文法的基礎(chǔ)上進行限制：規(guī)定除了左部有且只有一個非終結(jié)符外，還特別規(guī)定右部最多只允許有兩個字符，當為兩上字符時必須一個為非終結(jié)符，另一個為終結(jié)符，而當只有一個字符時，必須為終結(jié)符，這樣的文法就成了正規(guī)文法。這樣一層套一層的限制，就形成了從0型到3型文法的定義體制，每一層都是在前一層基礎(chǔ)上進行定義的，所以說前一層一定比該層表示的范圍要廣，因為其受的限制要少。
那么，我們在判斷一個文法時應(yīng)該以什么規(guī)則來判斷呢？這個規(guī)則當然是：3->2->1->0.也就是說，我們判斷是從高到低來判斷的，比如：一旦判斷其屬于正規(guī)文法之后就沒必要再判斷其是否屬于上下文無關(guān)的了(因為它必定屬于上下文無關(guān)，我們應(yīng)該以最高規(guī)則來判定其屬于的文法類型)，其它情況與此類推。只有當我們判斷不屬于3型文法時，我們才向下判斷，其是不是屬于2型的，若不屬于2型的，則依此類推再向下判斷。最終的結(jié)果如果不屬于3，2和1三種類型，那就只有屬于0型了。
“給定一個文法，要求判斷其屬于何種文法”是一個重要考點，其出題形式可能是填空，選擇等多種題型。
第3章詞法分析：
很多人覺得編譯這個科目很難學，望而生畏，以致于舉步不前，最大的一個原因是把編譯技術(shù)看得過于神秘化了。其實，說白了，編譯這門課程無非就是對一個“大”程序的各個部分、各個模塊上升到理論化的程度進行分析和介紹。這個“大程序”就是我們所要研究的“編譯程序”。
前兩章為研究編譯技術(shù)作了一些概念和技術(shù)上的先期鋪墊，在本章的詞法分析內(nèi)容里將開始介紹編譯技術(shù)的第一個重要技術(shù)點：詞法分析。
本章最為重要的內(nèi)容是3.3節(jié)：正規(guī)式和有限自動機，對于詞法分析一章的考點，可以說80%到90%以上集中在這一節(jié)的內(nèi)容上。針對于這一節(jié)的知識點介紹和考點分析，我們將稍后給出，現(xiàn)在先來看一下學習3.3節(jié)所必須先知道和理解的基本概念：
a.詞法分析器的功能（或稱詞法分析的任務(wù)）：輸入的是源程序，輸出的是分析完成的單詞符號；
b.狀態(tài)轉(zhuǎn)換圖：是一張有向圖，用于標識在特定的輸入下詞法分析器應(yīng)該選擇的分析方向。
對于考點a，有些學校會作為選擇、判斷或填空題進行考查，而對于考點b，多數(shù)是與有限自動機一些考查，要求給出以“狀態(tài)圖”表示的確定有限自動機，也有的學校的試題中，是要求直接給出針對于某正規(guī)式的狀態(tài)轉(zhuǎn)換圖，比如中科院曾經(jīng)考到：已知某系統(tǒng)下的設(shè)備文件名的定義方式（以正規(guī)式給出），要求給出符合這種定義的狀態(tài)轉(zhuǎn)換圖。理解狀態(tài)轉(zhuǎn)換圖的含義是進行本章學習的重要前提，大家記住一句話：狀態(tài)轉(zhuǎn)換圖，就是一張當輸入不同的內(nèi)容時，選擇不同分析路徑的有向圖。
下面，我們重點看一下有關(guān)“正規(guī)式與有限自動機”這一考點的各種可能考查形式：a.題目給定一正規(guī)式，要求給出其NFA，DFA或最簡DFA形式。
b.題目給定一用狀態(tài)圖表示的NFA，要求給出其對應(yīng)的DFA或最簡DFA形式。c.題目給定一NFA，DFA或最簡DFA，要求給出其對應(yīng)的正規(guī)式。d.題目給定一正規(guī)集，要求給出其相應(yīng)的DFA。
e.題目給定一用自然語言描述的正規(guī)集，要求給出其相應(yīng)的正規(guī)式表示形式。
這些考點，綜合起來看，是在正規(guī)式，正規(guī)集，NFA和DFA之間作各種可能的轉(zhuǎn)換，當然這種轉(zhuǎn)換正確與否的判斷標準就是轉(zhuǎn)換之后的內(nèi)容是不是與轉(zhuǎn)換之前的內(nèi)容等價，如果等價，我們就認為轉(zhuǎn)換是正確的。
在考點e這類的轉(zhuǎn)換題目中，有一些是需要另外規(guī)納出來的，他們在某一方面具有共同的特征，如果掌握了其中一題，將可舉一反三解出其它題。比如有以下的幾種題目就可以作以總結(jié)：
1.求偶（奇）數(shù)個a與偶（奇）數(shù)個b構(gòu)成的語言的正規(guī)式2.求能被3（4、5、或其它任意給定的n）整除的正規(guī)式的DFA
3.求不以（或以）n（n從0到9）開頭的XXXX（符號某種條件的）奇（偶數(shù)）數(shù)的正規(guī)式
以上三種類型的考題，在每一種類型中，都是有規(guī)律可循的，也都有簡便的方法可以幫助我們快速求解其正規(guī)式，進而快速確定DFA及最簡DFA。針對于這三種類型的解題思路分析，我會在另外的文章中給出。
第4章語法分析－自上而下的分析：
說明：這一次的更新，確實有點慢了，距上次已經(jīng)有了20天的時間，這段時間主要因為sodme所在的公司在進行搬遷事宜，所以心境和環(huán)境都不太安定，讓大家久候了，以后我盡量在一到兩周左右的時間里把這個貼子更新完畢，今天是10月12日，請大家監(jiān)督，這個貼子最晚截止更新時間是10月26日。
大家在參閱編譯原理的這個重點歸納貼子時，可能會感覺與數(shù)據(jù)結(jié)構(gòu)規(guī)納貼子風格不太一致，在編譯的總結(jié)里，我較多地講解了書上的一些我認為是較難理解的內(nèi)容，而不僅僅是給出考點。因為從我接觸的網(wǎng)友反映的情況看來，大家對編譯還是比較頭疼的，所以，我希望通過這樣的規(guī)納同時幫助大家從另外一個角度或以另外一種思維來看待編譯原理課程。
當詞法分析器對源程序進行了詞法分析，獲得了一個個獨立的單詞符號后，編譯程序總控模塊就會調(diào)用語法分析子程序?qū)@些單詞符號集進行語法分析，也就是：利用該文法的產(chǎn)生式來判斷這些單詞符號是否足以構(gòu)成一個在語法上正確的程序。如果可以構(gòu)成一個在語法上正確的程序，則接著作編譯下面的工作，比如：語法制導(dǎo)翻譯，中間代碼生成、代碼優(yōu)化等工作；而如果不能構(gòu)成一個在語法上正確的程序，則給出相應(yīng)的錯誤提示并將錯誤信息記入對應(yīng)的數(shù)據(jù)記錄中。語法分析的規(guī)則主要基于兩種：自上而下分析和自下而上分析。這一章，主要講解自上而下的分析方法。自上而下分析的大致思路是：根據(jù)產(chǎn)生式規(guī)則，從產(chǎn)生式的開始符號進行推導(dǎo)，一直推導(dǎo)到可以產(chǎn)生當前要判斷的這個句子為止。如果推導(dǎo)了所有可能情況，但沒有推出這樣的句子，那么這個句子就是不符合該語言的語法規(guī)則的（產(chǎn)生式即定義了語言的語法規(guī)則）。
在陳火旺老師的編譯教材上，詳細描述了一種自上而下的分析方法：LL(1)分析法，陳老教材的這一章也是圍繞這一點而展開的。下面，我們介紹一下本章的主要�？贾R點及考查角度：
1.給定一文法，要求將其改造成可以進行自上而下分析的形式。這里面涉及到兩方面的知識點：左遞歸的去除及公因子的提取。所謂的左遞歸是指產(chǎn)生式是形如：P->Pab...的形式，即：產(chǎn)生式右邊的第一個字符就是該產(chǎn)生式左邊的那個非終結(jié)符。當一個文法中有左遞歸的產(chǎn)生式時，是無法進行自上而下推導(dǎo)的，因為只要這個產(chǎn)生式被推導(dǎo)，就勢必會使這種推導(dǎo)過程陷入一種遞歸循環(huán)無休止推導(dǎo)的情形。去除左遞歸的方法是比較簡單的，其基本思路是將左遞歸通過轉(zhuǎn)化變成與之等價的右遞歸。即將形如：P->Pa|b形式的左遞歸變成如下形式：P->bP",P"->aP"|e(注：e表示空)。這一點只要多作練習，很快就會掌握。提取公因子的目的是為了避免推導(dǎo)過程中的回溯，也就是使每一次的向下推導(dǎo)是唯一的，而不是有多個選擇，因為有多個選擇的話就可能出現(xiàn)回溯。2.給定一文法，要求判斷其是否為LL(1)文法。判斷一個文法是否為LL(1)文法主要有兩種方法：一種是判斷文法是否二義，如果二義，則文法必定不為LL(1)（注意：此命題的否合命題不真）；二是根據(jù)陳老教材P73頁：關(guān)于LL(1)文法成立的三個條件。顯然，第一種判斷方法效率是比較高的，但是，其只能判斷文法“不為”LL(1)的，并不能判定文法“是”LL(1)的，要判斷文法“是”LL(1)的，就得用第二種方法，但在考題中，如果要求你判斷某文法是否為LL(1)的，則該文法多半不是LL(1)的，而且此點可以很容易地用二義性來證明，這是一種�？夹问健�3.給定一文法，要求構(gòu)造LL(1)分析表。LL(1)分析的重點和難點內(nèi)容都在其分析表的構(gòu)造上，后面要講的LR分析也是，它的難點也在于其分析表的構(gòu)造。構(gòu)造LL(1)分析表是一個�？键c，也是大分值題的可能出題點，對于普通學校而言，相比于LR分析，他們更喜歡考LL(1)，因為LR要比LL(1)復(fù)雜得多，而名校則更喜歡考LR，當然，這只是針對于較普遍的情況作的總結(jié)，并不是一定成立的推論。LL(1)分析表構(gòu)造前，需要先弄清FIRST集和FOLLOW集的構(gòu)造方法，簡單地說，F(xiàn)IRST集是用于求非終結(jié)符推出的產(chǎn)生式中的第一個終結(jié)符的，而FOLLOW集是用于求與該非終結(jié)符后緊鄰的那個終結(jié)符的。FIRST集的構(gòu)造方法見教材P78頁，在構(gòu)造的三個規(guī)則中，前兩個規(guī)則都是比較容易理解的，第三個規(guī)則看上去就有點復(fù)雜了，我們簡單地來看第三條規(guī)則，就是：當由X推出的產(chǎn)生式中前面若干個非終結(jié)符，其FIRST集均含有空時，就取這若干個非結(jié)符的后一個字符的FIRST集，當然，這“后一個字符”可能是終結(jié)符，也可能是非終結(jié)符，只要其FIRST集不為空就行；而當X推出的右邊全是非終結(jié)符，且這些非終結(jié)符的FIRST集全含有空時，就把空加到FIRST(X)中。FOLLOW集的構(gòu)造方法很簡單，不作詳細講解了。LL(1)分析表的構(gòu)造方法見教材P79頁，構(gòu)造規(guī)則主要有3條。說到這里，大家應(yīng)該明確分析表中的各個單元到底代表什么含義，我作一下簡單的介紹：分析表中的最頂一行，是產(chǎn)生式中所有的終結(jié)符；分析表中的最左一列，是產(chǎn)生式中所有的非終結(jié)符；而產(chǎn)生式中間的諸多單元格則可以存放該文法的產(chǎn)生式或特殊標志(比如成功和錯誤標志)。這樣的二維表格構(gòu)成的單元格的含義是：當左邊的非終結(jié)符遇到最上一行中的某個終結(jié)符時應(yīng)該選擇哪個產(chǎn)生式進行向下的推導(dǎo)，這個產(chǎn)生式就是放在對應(yīng)二維坐標處的產(chǎn)生式。4.給定一文法，先要求求解其LL(1)分析表，然后要求給出針對于某一個句子的具體分析過程。這個考點的第二問主要就是考查考生對預(yù)測分析程序的工作過程的理解了，預(yù)測分析程序完全是按照分析表機械工作的，針對于考生而言，要明確何時出棧，何時入棧，以及如何入棧，這些細節(jié)信息都是要通過作題掌握的，只理解而不會熟練解答是沒有用的。
5.給定一文法，要求給出其遞歸下降分析程序。遞歸下降分析的條件也是無左遞歸及不帶回溯，其構(gòu)造的過程比較簡單，就是將每個非終結(jié)符處理成可以互相遞歸調(diào)用的過程體。詳細過程參照P74到P75的例子，你可以試著寫一下P76頁教材上未列出的F過程的實現(xiàn)。
下一次，我們會詳細講解LR分析，敬請期待。如果網(wǎng)友對講解有什么意見或建議，也歡迎跟貼指出，謝謝大家。
后續(xù)內(nèi)容：
第5章語法分析－自下而上的分析：第6章屬性文法和語法制導(dǎo)翻譯：第7章語義分析和中間代碼生成：第8章符號表：
第9章運行時存儲空間組織：第10章優(yōu)化：
第11章目標代碼生成：第12章并行編譯基礎(chǔ)：
歡迎來到免費考研網(wǎng)
擴展閱讀：陳火旺編譯原理復(fù)習重點
前言：
作為考研課程中最難的科目，編譯原理的復(fù)習一直以來困擾著無數(shù)的計算機考研者，特別是本科期間沒有認真學習這門課程或者專業(yè)外的人士。由sodme寫作的這一系列文章將主要以陳火旺院士的編譯原理教材為主線，對編譯原理的復(fù)習重點和復(fù)習思路進行歸納和總結(jié)，以幫助大多數(shù)朋友盡快入門。由于絕大多數(shù)的本科編譯教材，都是在圍繞著原理性方面的知識進行介紹和展開，所以，本總結(jié)也適合于使用其它教材的朋友。anyway，希望使用各種不同教材的朋友都能從中受益并有所感悟。
與數(shù)據(jù)結(jié)構(gòu)的總結(jié)類似，對于編譯的總結(jié)都是采用我自己認為比較容易理解的語言進行描述，絕不對書上的概念和算法進行原原本本的照搬，這里，在多數(shù)情況下講的都是我自己的學習經(jīng)驗和學習心得。So，其行文寫作的style可能有些朋友不太適應(yīng)，but，Ipromise：這個總結(jié)絕不會平庸、泛泛無奇。Ok，now，let’sgo.
一、編譯原理的章節(jié)結(jié)構(gòu)及重點構(gòu)成
第1章引論：本章屬非重點章節(jié)，簡單介紹了編譯的基本知識。出題分值不會太多，如果出題（很多情況是不出題，^_^），其分值比例一般情況下不會超過5%.第2章高級語言及其語法描述：本章屬重要章節(jié)，在本章逐步引出了編譯的若干基礎(chǔ)概念和術(shù)語。如果出題，其分值比例一般在5%-20%.
第3章詞法分析：重難點章節(jié)。本章是難點章節(jié)之一，同時又是編譯原理最重要的章節(jié)和多數(shù)學校的必考章節(jié)之一，通常作為大題中的先行題考查。分值比例各有側(cè)重，一般在10%~20%不等。
第4章語法分析－自上而下分析：重難點章節(jié)。本章的難度要高于詞法分析一章，與詞法分析一章一樣，同屬編譯原理最重要的章節(jié)之一，是多校學校的必考章節(jié)之一，通常作為大題考查。如果出題，其分值在10%~20%不等（如果同一試卷中既出現(xiàn)詞法分析又出現(xiàn)語法分析，語法分析題目的分值一般比詞法分析的分值要大）。
第5章語法分析－自下而上分析：重難點章節(jié)。屬多數(shù)學校的必考章節(jié)之一，其重要性描述同上，通常作為大題考查。一般情況下，在同一學校的同一張編譯試卷內(nèi)，多數(shù)不會同時考自上而下分析和自下而上分析兩種語法分析方法，各學校會根據(jù)自身題目的難度定位選擇考查自上而下的還是自下而上的。自下而上的分析要難一點。如果本章出題，其分值比例約為：10%~20%.
第6章屬性文法和語法制導(dǎo)翻譯：重難點章節(jié)。屬多數(shù)學校的必考章節(jié)之一。多數(shù)與語義分析一章聯(lián)合出題，通常作為大題考查。如果出題，本章的分值比例約為：10%~20%左右。第7章語義分析和中間代碼生成：重難點章節(jié)，�？純�(nèi)容之一，報考名校的同學應(yīng)該多留意本章節(jié)內(nèi)容。如果出題，本章分值約為：10%左右。
第8章符號表：非重點章節(jié)，本章介紹的是編譯過程中的輔助內(nèi)容，并未緊密聯(lián)系編譯的主體思想。多數(shù)學校在本章不出題，如果出題，其分值比例約為：5%左右。
第9章運行時存儲空間組織：�？純�(nèi)容之一。本章多數(shù)會聯(lián)系實際語言進行考查，如果出題，其分值比例約為：10%左右。
第10章優(yōu)化：常考內(nèi)容之一。分值比例約為：10%左右。
第11章目標代碼生成：較少考查，即使考查，分數(shù)比例一般在5%左右。第12章并行編譯基礎(chǔ)：很少考查，只作了解，了解其基本概念即可。關(guān)于重要性標識的幾點說明：“必考內(nèi)容”：是針對于多校學校一般的出題規(guī)律而言，本章極易被考到�；蛘哒f，作為一個完整的試卷，本章是應(yīng)該被考查的，這是放在多個學校都比較適合的規(guī)律，也就是說本章是不同的學校共同關(guān)注的章節(jié)。“�？純�(nèi)容”：雖然本章內(nèi)容重要，但是，各校根據(jù)自己的考查方式，可能選擇考，也可能不選擇考查這一章，這樣的章節(jié)常常作為對必考章節(jié)的配合和補充，以完善和形成一張完整的試卷。這些章節(jié)要求讀者自己對所報院校的歷年試題進行歸納和分析，從中找出哪些是是這一次比較容易考查到的。
注：關(guān)于分值比例的統(tǒng)計樣本來自于國防科大，中科院，上海交大，哈工大，清華等多所學校的歷年試題。
二、編譯原理各章節(jié)重點難點歸納第1章引論：
本章作為編譯原理的開啟章節(jié)，其意義在于為原本對編譯一無所知的朋友撩開一條細縫，讓你從本章大致了解編譯程序工作的原理。所以，本章的考點都是象征性的。需要讀者掌握的是：清楚編譯程序的總框架，了解編譯程序工作的大致過程，能分辨清楚編譯前端與后端的區(qū)別及其相互配合的方法，要清楚編譯程序是如何生成的。請大家記憶并理解以下概念：編譯程序，解釋程序，翻譯程序，掃描器，分析器，編譯前端與后端，符號表，“遍”的概念等。說讓大家記憶并理解以上概念，并不是要大家原原本本地記住書上的解釋，而是讓大家達到這樣的一種程度：知道這些概念的含義，并且能夠按照自己的語言對其進行準確描述。一般而言，當你真正理解了一個概念之后，你是有能力對其進行精辟描述的。針對于本章的考點，多數(shù)是考查這些小概念，比如國防科大就曾經(jīng)考過“掃描器”等概念。Inaword，理解第一。
第2章高級語言及其語法描述：
本章的2.1和2.2節(jié)在先期為2.3節(jié)作了很多鋪墊，其目的是為了引出2.3中的幾個重量級概念：上下文無關(guān)文法，語法分析樹和二義性，同時也引出了與此緊密聯(lián)系的其它概念：推導(dǎo)，句型，句子，最左推導(dǎo)，最右推導(dǎo)等。最后給出了另一個�？键c：喬姆斯基的方法分類。
對于本章，讀者應(yīng)該掌握：
正確理解程序設(shè)計語言中語法和語義的含義，了解書上列舉的高級語言中的一般特性。一般情況下，這兩點是不會直接考查的，如果是想考查某種高級語言的特性，也會放在后面的優(yōu)化或目標代碼生成章節(jié)中進行考查。所以，這里只要求你理解及了解。但是，下面的這些東東就是必須掌握的了，而且是必須通過大量作題掌握的：
1.上下文無關(guān)文法的定義，判斷和轉(zhuǎn)化，以及與上下文無關(guān)文法密切相關(guān)的概念。
首先，應(yīng)該掌握上下文無關(guān)文法的四個構(gòu)成要素；其次，應(yīng)該清楚對于上下文無關(guān)文法，其每個產(chǎn)生式的左部和右部必須滿足的條件。在有關(guān)上下文無關(guān)文法的考點中，有這樣幾種考查方式：給出某語言的自然語言描述方式，要求寫該語言的上下文無關(guān)文法表述形式；給出某語言的上下文無關(guān)文法，要求用自然語言描述該語言；給出某語言的上下文無法方法，要求證明該文法是否二義；給出某語言的上下文無關(guān)文法，要求給出指定句子的最左或最右推導(dǎo)；給出某語言的上下文無關(guān)文法，要求給出指定句子的語法分析樹；給出一個具有二義性的上下文無關(guān)文法，要求將其轉(zhuǎn)換成非二義性的。以上的綜合分析，幾乎含蓋了所有與上下文無關(guān)文法有關(guān)的出題角度，大家應(yīng)該全部掌握。
2.喬姆斯基的文法分類。
首先，應(yīng)該非常清楚喬姆斯基對于四種文法分類的定義，并能理解其含義。幾種文法中，最基本的是0型文法，讀者可以將它理解為其它所有文法的基礎(chǔ)，它是可以表示任何語言的文法。后面的1，2,3三種文法，是分別對于0型文法產(chǎn)生式的兩邊作了不同的限制之后，形成了新的文法。比如：規(guī)定0型文法的每個產(chǎn)生式中，其左邊字符集長度小于右邊字符集長度并且同時規(guī)定開始符號只可出現(xiàn)于產(chǎn)生式的左邊，不能出現(xiàn)在任何產(chǎn)生式的右邊，這樣，就成為了1型文法(即上下文有關(guān)文法)。其它與此類似，在1型文法的基礎(chǔ)上，進一步規(guī)定該文法的任意產(chǎn)生式，其左部只允許有一個字符且必須為非終結(jié)符，這樣就構(gòu)成了上下文無關(guān)文法；再在上下文無關(guān)文法的基礎(chǔ)上進行限制：規(guī)定除了左部有且只有一個非終結(jié)符外，還特別規(guī)定右部最多只允許有兩個字符，當為兩上字符時必須一個為非終結(jié)符，另一個為終結(jié)符，而當只有一個字符時，必須為終結(jié)符，這樣的文法就成了正規(guī)文法。這樣一層套一層的限制，就形成了從0型到3型文法的定義體制，每一層都是在前一層基礎(chǔ)上進行定義的，所以說前一層一定比該層表示的范圍要廣，因為其受的限制要少。
那么，我們在判斷一個文法時應(yīng)該以什么規(guī)則來判斷呢？這個規(guī)則當然是：3->2->1->0.也就是說，我們判斷是從高到低來判斷的，比如：一旦判斷其屬于正規(guī)文法之后就沒必要再判斷其是否屬于上下文無關(guān)的了(因為它必定屬于上下文無關(guān)，我們應(yīng)該以最高規(guī)則來判定其屬于的文法類型)，其它情況與此類推。只有當我們判斷不屬于3型文法時，我們才向下判斷，其是不是屬于2型的，若不屬于2型的，則依此類推再向下判斷。最終的結(jié)果如果不屬于3，2和1三種類型，那就只有屬于0型了。
“給定一個文法，要求判斷其屬于何種文法”是一個重要考點，其出題形式可能是填空，選擇等多種題型。
第3章詞法分析：
很多人覺得編譯這個科目很難學，望而生畏，以致于舉步不前，最大的一個原因是把編譯技術(shù)看得過于神秘化了。其實，說白了，編譯這門課程無非就是對一個“大”程序的各個部分、各個模塊上升到理論化的程度進行分析和介紹。這個“大程序”就是我們所要研究的“編譯程序”。
前兩章為研究編譯技術(shù)作了一些概念和技術(shù)上的先期鋪墊，在本章的詞法分析內(nèi)容里將開始介紹編譯技術(shù)的第一個重要技術(shù)點：詞法分析。
本章最為重要的內(nèi)容是3.3節(jié)：正規(guī)式和有限自動機，對于詞法分析一章的考點，可以說80%到90%以上集中在這一節(jié)的內(nèi)容上。針對于這一節(jié)的知識點介紹和考點分析，我們將稍后給出，現(xiàn)在先來看一下學習3.3節(jié)所必須先知道和理解的基本概念：
a.詞法分析器的功能（或稱詞法分析的任務(wù)）：輸入的是源程序，輸出的是分析完成的單詞符號；
b.狀態(tài)轉(zhuǎn)換圖：是一張有向圖，用于標識在特定的輸入下詞法分析器應(yīng)該選擇的分析方向。
對于考點a，有些學校會作為選擇、判斷或填空題進行考查，而對于考點b，多數(shù)是與有限自動機一些考查，要求給出以“狀態(tài)圖”表示的確定有限自動機，也有的學校的試題中，是要求直接給出針對于某正規(guī)式的狀態(tài)轉(zhuǎn)換圖，比如中科院曾經(jīng)考到：已知某系統(tǒng)下的設(shè)備文件名的定義方式（以正規(guī)式給出），要求給出符合這種定義的狀態(tài)轉(zhuǎn)換圖。理解狀態(tài)轉(zhuǎn)換圖的含義是進行本章學習的重要前提，大家記住一句話：狀態(tài)轉(zhuǎn)換圖，就是一張當輸入不同的內(nèi)容時，選擇不同分析路徑的有向圖。
下面，我們重點看一下有關(guān)“正規(guī)式與有限自動機”這一考點的各種可能考查形式：a.題目給定一正規(guī)式，要求給出其NFA，DFA或最簡DFA形式。
b.題目給定一用狀態(tài)圖表示的NFA，要求給出其對應(yīng)的DFA或最簡DFA形式。c.題目給定一NFA，DFA或最簡DFA，要求給出其對應(yīng)的正規(guī)式。d.題目給定一正規(guī)集，要求給出其相應(yīng)的DFA。
e.題目給定一用自然語言描述的正規(guī)集，要求給出其相應(yīng)的正規(guī)式表示形式。
這些考點，綜合起來看，是在正規(guī)式，正規(guī)集，NFA和DFA之間作各種可能的轉(zhuǎn)換，當然這種轉(zhuǎn)換正確與否的判斷標準就是轉(zhuǎn)換之后的內(nèi)容是不是與轉(zhuǎn)換之前的內(nèi)容等價，如果等價，我們就認為轉(zhuǎn)換是正確的。
在考點e這類的轉(zhuǎn)換題目中，有一些是需要另外規(guī)納出來的，他們在某一方面具有共同的特征，如果掌握了其中一題，將可舉一反三解出其它題。比如有以下的幾種題目就可以作以總結(jié)：
1.求偶（奇）數(shù)個a與偶（奇）數(shù)個b構(gòu)成的語言的正規(guī)式2.求能被3（4、5、或其它任意給定的n）整除的正規(guī)式的DFA
3.求不以（或以）n（n從0到9）開頭的XXXX（符號某種條件的）奇（偶數(shù)）數(shù)的正規(guī)式
以上三種類型的考題，在每一種類型中，都是有規(guī)律可循的，也都有簡便的方法可以幫助我們快速求解其正規(guī)式，進而快速確定DFA及最簡DFA。針對于這三種類型的解題思路分析，我會在另外的文章中給出。
第4章語法分析－自上而下的分析：說明：這一次的更新，確實有點慢了，距上次已經(jīng)有了20天的時間，這段時間主要因為sodme所在的公司在進行搬遷事宜，所以心境和環(huán)境都不太安定，讓大家久候了，以后我盡量在一到兩周左右的時間里把這個貼子更新完畢，今天是10月12日，請大家監(jiān)督，這個貼子最晚截止更新時間是10月26日。
大家在參閱編譯原理的這個重點歸納貼子時，可能會感覺與數(shù)據(jù)結(jié)構(gòu)規(guī)納貼子風格不太一致，在編譯的總結(jié)里，我較多地講解了書上的一些我認為是較難理解的內(nèi)容，而不僅僅是給出考點。因為從我接觸的網(wǎng)友反映的情況看來，大家對編譯還是比較頭疼的，所以，我希望通過這樣的規(guī)納同時幫助大家從另外一個角度或以另外一種思維來看待編譯原理課程。
當詞法分析器對源程序進行了詞法分析，獲得了一個個獨立的單詞符號后，編譯程序總控模塊就會調(diào)用語法分析子程序?qū)@些單詞符號集進行語法分析，也就是：利用該文法的產(chǎn)生式來判斷這些單詞符號是否足以構(gòu)成一個在語法上正確的程序。如果可以構(gòu)成一個在語法上正確的程序，則接著作編譯下面的工作，比如：語法制導(dǎo)翻譯，中間代碼生成、代碼優(yōu)化等工作；而如果不能構(gòu)成一個在語法上正確的程序，則給出相應(yīng)的錯誤提示并將錯誤信息記入對應(yīng)的數(shù)據(jù)記錄中。
語法分析的規(guī)則主要基于兩種：自上而下分析和自下而上分析。這一章，主要講解自上而下的分析方法。自上而下分析的大致思路是：根據(jù)產(chǎn)生式規(guī)則，從產(chǎn)生式的開始符號進行推導(dǎo)，一直推導(dǎo)到可以產(chǎn)生當前要判斷的這個句子為止。如果推導(dǎo)了所有可能情況，但沒有推出這樣的句子，那么這個句子就是不符合該語言的語法規(guī)則的（產(chǎn)生式即定義了語言的語法規(guī)則）。
在陳火旺老師的編譯教材上，詳細描述了一種自上而下的分析方法：LL(1)分析法，陳老教材的這一章也是圍繞這一點而展開的。下面，我們介紹一下本章的主要�？贾R點及考查角度：
1.給定一文法，要求將其改造成可以進行自上而下分析的形式。這里面涉及到兩方面的知識點：左遞歸的去除及公因子的提取。所謂的左遞歸是指產(chǎn)生式是形如：P->Pab...的形式，即：產(chǎn)生式右邊的第一個字符就是該產(chǎn)生式左邊的那個非終結(jié)符。當一個文法中有左遞歸的產(chǎn)生式時，是無法進行自上而下推導(dǎo)的，因為只要這個產(chǎn)生式被推導(dǎo)，就勢必會使這種推導(dǎo)過程陷入一種遞歸循環(huán)無休止推導(dǎo)的情形。去除左遞歸的方法是比較簡單的，其基本思路是將左遞歸通過轉(zhuǎn)化變成與之等價的右遞歸。即將形如：P->Pa|b形式的左遞歸變成如下形式：P->bP",P"->aP"|e(注：e表示空)。這一點只要多作練習，很快就會掌握。提取公因子的目的是為了避免推導(dǎo)過程中的回溯，也就是使每一次的向下推導(dǎo)是唯一的，而不是有多個選擇，因為有多個選擇的話就可能出現(xiàn)回溯。2.給定一文法，要求判斷其是否為LL(1)文法。判斷一個文法是否為LL(1)文法主要有兩種方法：一種是判斷文法是否二義，如果二義，則文法必定不為LL(1)（注意：此命題的否合命題不真）；二是根據(jù)陳老教材P73頁：關(guān)于LL(1)文法成立的三個條件。顯然，第一種判斷方法效率是比較高的，但是，其只能判斷文法“不為”LL(1)的，并不能判定文法“是”LL(1)的，要判斷文法“是”LL(1)的，就得用第二種方法，但在考題中，如果要求你判斷某文法是否為LL(1)的，則該文法多半不是LL(1)的，而且此點可以很容易地用二義性來證明，這是一種�？夹问健�3.給定一文法，要求構(gòu)造LL(1)分析表。LL(1)分析的重點和難點內(nèi)容都在其分析表的構(gòu)造上，后面要講的LR分析也是，它的難點也在于其分析表的構(gòu)造。構(gòu)造LL(1)分析表是一個�？键c，也是大分值題的可能出題點，對于普通學校而言，相比于LR分析，他們更喜歡考LL(1)，因為LR要比LL(1)復(fù)雜得多，而名校則更喜歡考LR，當然，這只是針對于較普遍的情況作的總結(jié)，并不是一定成立的推論。LL(1)分析表構(gòu)造前，需要先弄清FIRST集和FOLLOW集的構(gòu)造方法，簡單地說，F(xiàn)IRST集是用于求非終結(jié)符推出的產(chǎn)生式中的第一個終結(jié)符的，而FOLLOW集是用于求與該非終結(jié)符后緊鄰的那個終結(jié)符的。FIRST集的構(gòu)造方法見教材P78頁，在構(gòu)造的三個規(guī)則中，前兩個規(guī)則都是比較容易理解的，第三個規(guī)則看上去就有點復(fù)雜了，我們簡單地來看第三條規(guī)則，就是：當由X推出的產(chǎn)生式中前面若干個非終結(jié)符，其FIRST集均含有空時，就取這若干個非結(jié)符的后一個字符的FIRST集，當然，這“后一個字符”可能是終結(jié)符，也可能是非終結(jié)符，只要其FIRST集不為空就行；而當X推出的右邊全是非終結(jié)符，且這些非終結(jié)符的FIRST集全含有空時，就把空加到FIRST(X)中。FOLLOW集的構(gòu)造方法很簡單，不作詳細講解了。LL(1)分析表的構(gòu)造方法見教材P79頁，構(gòu)造規(guī)則主要有3條。說到這里，大家應(yīng)該明確分析表中的各個單元到底代表什么含義，我作一下簡單的介紹：分析表中的最頂一行，是產(chǎn)生式中所有的終結(jié)符；分析表中的最左一列，是產(chǎn)生式中所有的非終結(jié)符；而產(chǎn)生式中間的諸多單元格則可以存放該文法的產(chǎn)生式或特殊標志(比如成功和錯誤標志)。這樣的二維表格構(gòu)成的單元格的含義是：當左邊的非終結(jié)符遇到最上一行中的某個終結(jié)符時應(yīng)該選擇哪個產(chǎn)生式進行向下的推導(dǎo)，這個產(chǎn)生式就是放在對應(yīng)二維坐標處的產(chǎn)生式。
4.給定一文法，先要求求解其LL(1)分析表，然后要求給出針對于某一個句子的具體分析過程。這個考點的第二問主要就是考查考生對預(yù)測分析程序的工作過程的理解了，預(yù)測分析程序完全是按照分析表機械工作的，針對于考生而言，要明確何時出棧，何時入棧，以及如何入棧，這些細節(jié)信息都是要通過作題掌握的，只理解而不會熟練解答是沒有用的。
5.給定一文法，要求給出其遞歸下降分析程序。遞歸下降分析的條件也是無左遞歸及不帶回溯，其構(gòu)造的過程比較簡單，就是將每個非終結(jié)符處理成可以互相遞歸調(diào)用的過程體。詳細過程參照P74到P75的例子，你可以試著寫一下P76頁教材上未列出的F過程的實現(xiàn)。
下一次，我們會詳細講解LR分析，敬請期待。如果網(wǎng)友對講解有什么意見或建議，也歡迎跟貼指出，謝謝大家。
后續(xù)內(nèi)容：
第5章語法分析－自下而上的分析：第6章屬性文法和語法制導(dǎo)翻譯：第7章語義分析和中間代碼生成：第8章符號表：
第9章運行時存儲空間組織：第10章優(yōu)化：
第11章目標代碼生成：第12章并行編譯基礎(chǔ)：三、編譯原理的重要習題總結(jié)
友情提示：本文中關(guān)于《陳火旺編譯原理復(fù)習重點及復(fù)習思路總結(jié)》給出的范例僅供您參考拓展思維使用，陳火旺編譯原理復(fù)習重點及復(fù)習思路總結(jié)：該篇文章建議您自主創(chuàng)作。
來源：網(wǎng)絡(luò)整理 免責聲明：本文僅限學習分享，如產(chǎn)生版權(quán)問題，請聯(lián)系我們及時刪除。
公文素材庫友情提示：本網(wǎng)站所有內(nèi)容為共享上傳提供，不涉及任何商業(yè)利益，本站對此不承擔任何保證責任！
Copyright © www.seogis.com Corporation, All Rights Reserved 共享時代 共享你我他 版權(quán)所有