1、編譯原理課程論文編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分之一，而且多數(shù)計(jì)算機(jī)系統(tǒng)都配有不止一個(gè)高級語言的編譯程序，對有些高級語言甚至配置了幾個(gè)不同性能的編譯程序。從功能上講，一個(gè)編譯程序就是一個(gè)語言翻譯程序。語言翻譯程序把一種源語言書寫 的程序翻譯成另一種目標(biāo)語言的等價(jià)程序，所以總的說編譯程序是一種翻譯程序，其 源程序是高級語言，目標(biāo)語言程序是低級語言。編譯程序完成從源程序到目標(biāo)程序的翻譯工作，是一個(gè)復(fù)雜的整體的過程。從概念上來講，一個(gè)編譯程序的整個(gè)工作過程是劃分成幾個(gè)階段進(jìn)行的，每個(gè)階段將源程 序的一種表示形式轉(zhuǎn)換成另一種表示形式，各個(gè)階段進(jìn)行的操作在邏輯上是緊密連接 在一起的。一般一個(gè)編譯過

2、程是詞法分析、語法分析、語義分析、中間代碼生成、代 碼優(yōu)化和目標(biāo)代碼生成。編寫編譯器的原理和技術(shù)具有十分普遍的意義，以至于在每個(gè)計(jì)算機(jī)工作者的職業(yè)生涯中，本書中的原理和技術(shù)都會(huì)反復(fù)用到。在這本書中，向我們介紹了文法的概 念，在講詞法分析的章節(jié)中講述了構(gòu)造一個(gè)有窮自動(dòng)機(jī)的方法，以及如何將一個(gè)不確 定的有窮自動(dòng)機(jī)轉(zhuǎn)化成確定的有窮自動(dòng)機(jī)和有窮自動(dòng)機(jī)的最小化等方法。詞法分析相對來說比較簡單。可能是詞法分析程序本身實(shí)現(xiàn)起來很簡單吧，很多沒有學(xué)過編譯原理的人也同樣可以寫出各種各樣的詞法分析程序。不過編譯原理在講 解詞法分析的時(shí)候，重點(diǎn)把正則表達(dá)式和自動(dòng)機(jī)原理加了進(jìn)來，然后以一種十分標(biāo)準(zhǔn) 的方式來講解詞法分

3、析程序的產(chǎn)生。這樣的做法道理很明顯，就是要讓詞法分析從程 序上升到理論的地步。詞法分析中的重點(diǎn)是有窮自動(dòng)機(jī)DFA 的生成以及DFA 和正規(guī)式與正規(guī)文法的關(guān)系。還要熟練掌握NFA轉(zhuǎn)換為DFA勺方法及DFA勺化簡。詞法分析的核心應(yīng)該是構(gòu)建DFA最后維護(hù)一個(gè)狀態(tài)轉(zhuǎn)移表。通過轉(zhuǎn)態(tài)轉(zhuǎn)移的結(jié)果來識別詞性。DFA的思想和字典樹很像。NFA通過求每個(gè)狀態(tài)的閉包后構(gòu)造出的自動(dòng) 機(jī)與DFA等價(jià)。正則表達(dá)式閉包，連接，或三種操作都有相應(yīng)的NFA與其等價(jià)。所以正則表達(dá)式=NFA=DFADFA犬態(tài)最小化算法化簡 DFA LL(1)文法主要就是根據(jù)FIRST 集 判斷向哪條路徑走，來避免回溯； LR(0) 文法構(gòu)造項(xiàng)集閉

4、包構(gòu)成的自動(dòng)機(jī)，通過有 窮自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換來判斷該規(guī)約還是該移進(jìn)來做出相應(yīng)的操作并且更改堆棧和Buffer的狀態(tài)，注意此時(shí)有可能發(fā)生移進(jìn)規(guī)約沖突，并且如果不運(yùn)用FOLLO濂的話有些出錯(cuò)狀態(tài)無法識別，只能當(dāng)規(guī)約處理。SLR(0)文法是再LR(0)的基礎(chǔ)上運(yùn)用FOLLOWS來判斷出錯(cuò)狀態(tài)？ SLR(0)文法 的無法處理移近規(guī)約沖突。LR(1) 文法是在 LR(0) 文法的基礎(chǔ)上構(gòu)建LR(0) 的增廣項(xiàng)集，其他與LR(0) 相似，通過增廣項(xiàng)集可以解決移近規(guī)約沖突問題，但無法解決部分規(guī)約規(guī)約沖突問題。LALR貌似只是將LR文法中的一些等價(jià)狀態(tài)合并構(gòu)成一個(gè)更小的自動(dòng)機(jī)，有 點(diǎn)像DFA犬態(tài)最小化方法。 算

5、符優(yōu)先文法 構(gòu)造語法樹的結(jié)構(gòu)找到相應(yīng)的優(yōu)先級構(gòu)成一個(gè)優(yōu)先級表，兩個(gè)棧，一個(gè)用來存O屋個(gè)用來存操作數(shù)，當(dāng)兩個(gè)算符相遇時(shí)判斷兩個(gè)算符的優(yōu)先級， 做出相應(yīng)的操作：進(jìn)棧或計(jì)算。語法分析包括自上而下和自下而上分析。自上而下分析著重掌握LL(1) 文法，自下而上分析重點(diǎn)掌握算符優(yōu)先文法和LR(0) 、 SLR( 1)文法。語法分析部分就比較麻煩一點(diǎn)了。 現(xiàn)在一般有兩種語法分析算法， LL 自頂向下算法和LR自底向上算法。LL算法還好說，到了 LR算法的時(shí)候，困難就來了。很多自學(xué) 編譯原理的都是遇到LR算法的理解成問題后就放棄了自學(xué)。其實(shí)這些東西都是只要大 家理解就可以了，又不是像詞法分析那樣非得自己寫出來

6、才算真正的會(huì)。像 LR算法的 語法分析器， 一般都是用工具Yacc 來生成， 實(shí)踐中完全沒有比較自己來實(shí)現(xiàn)。 對于 LL算法中特殊的遞歸下降算法，因?yàn)槠鋵?shí)踐十分簡單，那么就應(yīng)該要求每個(gè)學(xué)生都能自己寫。當(dāng)然，現(xiàn)在也有不少好的LL算法的語法分析器，不過要是換在非 C平臺，比如 Java,Delphi,你不能運(yùn)用YACC：具了，那么你就只有自己來寫語法分析器。等學(xué)到詞法分析和語法分析時(shí)候，你可能會(huì)出現(xiàn)這樣的疑問： “詞法分析和語法分析到底有什么？”就從編譯器的角度來講，編譯器需要把程序員寫的源程序轉(zhuǎn)換成一種方便處理的數(shù)據(jù)結(jié)構(gòu)(抽象語法樹或語法樹) , 那么這個(gè)轉(zhuǎn)換的過程就是通過詞法分析和語法分析的。

7、其實(shí)詞法分析并非一開始就被列入編譯器的必備部分，只是我們?yōu)榱撕喕Z法分析的過程，就把詞法分析這種繁瑣的工作單獨(dú)提取出來，就成了現(xiàn)在的詞法分析部分。除了編譯器部分，在其它地方，詞法分析和語法分析也是有用的。比如我們在DOS,Unix,Linux 下輸入命令的時(shí)候，程序如何分析你輸入的命令形式，這也是簡單的應(yīng)用。總之，這兩部分的工作就是把不“規(guī)則”的文本信息轉(zhuǎn)換成一種比較好分析好處理的數(shù)據(jù)結(jié)構(gòu)。那么為什么編譯原理的教程都最終把要分析的源分析轉(zhuǎn) 換成“樹”這種數(shù)據(jù)結(jié)構(gòu)呢？數(shù)據(jù)結(jié)構(gòu)中有 Stack, Line,List 這么多數(shù)據(jù)結(jié)構(gòu)，各自都有各自的特點(diǎn)。但是Tree 這種結(jié)構(gòu)有很強(qiáng)的遞歸性，也就是說

8、我們可以把Tree的任何結(jié)點(diǎn)Node提取出來后，它依舊是一顆完整的Tree。這一點(diǎn)符合我們現(xiàn)在編譯原理分析的形式語言，比如我們在函數(shù)里面使用函樹，循環(huán)中使用循環(huán)，條件中使用條件等等，那么就可以很直觀地表示在Tree 這種數(shù)據(jù)結(jié)構(gòu)上。同樣，我們在執(zhí)行形式語言的程序的時(shí)候也是如此的遞歸性。在編譯原理后面的代碼生成的部分，就會(huì)介紹一種堆棧式的中間代碼，我們可以根據(jù)分析出來的抽象語法樹，很容易，很機(jī)械地運(yùn)用遞歸遍歷抽象語法樹就可以生成這種指令代碼。而這種代碼其實(shí)也被廣泛運(yùn)用在其它的解釋型語言中。像現(xiàn)在流行的 Java,.NET ，其底層的字節(jié)碼bytecode, 可以說就是這中基于堆棧的指令代碼的。在

9、學(xué)習(xí)文法時(shí)，對文法的組成，用法都較為明了，而在真正做題時(shí)卻感到十分吃力。例如給出了一個(gè)語言，要求寫出它的上下文無關(guān)文法，就感到十分棘手，所以今后在這方面要加大練習(xí)量，以熟練掌握。而在之后的詞法分析和語法分析中，我感到在看基本原理時(shí)十分困難，通常要長時(shí)間鉆研才能夠有所了解，而一旦掌握了基本原理，做題時(shí)就感到十分順暢了。例如，在剛接觸到 LR( 0) 文法時(shí)， 我用了大量的時(shí)間去學(xué)習(xí)它的原理， 掌握之后， 在列 LR(0)分析表和寫分析過程時(shí)，只要思路清晰，就會(huì)比較順暢，而且不會(huì)犯錯(cuò)。該門課中主要講述的是兩種分析方法， 即自上而下分析的方法和自下而上分析的方法。自上而下分析法是從文法的開始符號出發(fā)

10、，反復(fù)使用各種產(chǎn)生式，尋找“匹配”于輸入符號串的推導(dǎo)。自下而上的分析方法是從輸入符號串開始，逐步進(jìn)行“歸約”到文法的開始符號。自上而下的分析法主要的就是LL(1) 文法， 首先要判斷某個(gè)文法是否是LL(1) 文法，如果是就可以按照 LL(1) 文法分析的方法去判斷某一個(gè)輸入串是否為該文法的句子。LL(1)f 分析方法是，首先根據(jù)判斷是否為 LL(1) 文法求出每一個(gè)非終結(jié)符的 SELECTE集合來構(gòu)造該文法的預(yù)測分析表，然后根據(jù)預(yù)測分析表去分析輸入串得出結(jié)果；如果不是 LL(1) 文法， 比如說文法產(chǎn)生式中含有左遞歸和相同的因子， 就要消去左遞歸或公共因子，再根據(jù)每一個(gè)非終結(jié)符的SELECT!

11、合來判斷是否為LL文法。利用LL(1)文法分析一個(gè)輸入串是不是某一個(gè)文法的句子，根據(jù)預(yù)測分析表是比較直觀的，而且分析的效率也是比較高的。自下而上的分析方法主要是算符優(yōu)先分析方法。 算符優(yōu)先分析的基本思想是只規(guī)定算符之間的優(yōu)先關(guān)系，也就是只考慮終結(jié)符之間的優(yōu)先關(guān)系，由于算符優(yōu)先分析不考慮非終結(jié)符之間的優(yōu)先關(guān)系，在歸約的過程中只要找到可歸約串就歸約，沒有考慮非終結(jié)符之間的優(yōu)先關(guān)系，所以說算符優(yōu)先歸約不是規(guī)范規(guī)約。算符優(yōu)先分析首先是要構(gòu)造算符優(yōu)先關(guān)系矩陣；然后就是分析輸入串，根據(jù)關(guān)系矩陣進(jìn)行移進(jìn)或歸約操作；最后分析得出判斷的結(jié)果。算符優(yōu)先分析是有缺點(diǎn)的， 由于算符優(yōu)先分析方法在分析的過程中不知道如何

12、確定句柄。 下面要說的就是LR(0) 文法， 這種方法能夠根據(jù)當(dāng)前分析棧中的符號串就可以惟一的確定分析器的動(dòng)作是移進(jìn)還是歸約， 并且是用哪一個(gè)產(chǎn)生式。 根據(jù)規(guī)則寫出 LR(0)的分析的項(xiàng)目集， 再由項(xiàng)目集構(gòu)造LR(0) 的分析表， 其次根據(jù)分析棧的元素和狀態(tài)， 查看分析表，找出相關(guān)的句柄，是歸約還是移進(jìn)，最后就是分析得出結(jié)果了。SLR(0)文法是以LR(0)文法為基礎(chǔ)的文法，是為了解決程序設(shè)計(jì)語言的文法不能夠滿足LR(0)文法條件的另一種文法分析的方法， 大致的與 LR(0) 的分析過程相似， 只是在項(xiàng)目集的組合上有些區(qū)別。編譯原理 這門課程主要是向我們講述是如何將一些語言編寫的源程序翻譯成計(jì)算機(jī)能夠識別的機(jī)器語言的原理。編譯原理課程是一門理論性比較強(qiáng)的課程，其中的文法，語言等概念到LL(1)文法、算符優(yōu)先文法、LR(0文法)以及SLR(1)文法等的分析，基本上都是對具體問題的抽象，是需要更多的時(shí)間去理解和掌握的。通過這學(xué)期的對編譯原理課程的學(xué)習(xí)， 這么課程讓我學(xué)會(huì)了如何去編譯程序的一個(gè)理論知識，知道編譯程序是通過怎樣