編譯原理學(xué)習(xí)方法

1、PAGE 編譯原理學(xué)習(xí)導(dǎo)論大學(xué)課程為什么要開設(shè)編譯原理呢？這門課程關(guān)注的是編譯器方面的產(chǎn)生原理和技術(shù)問題，似乎和計(jì)算機(jī)的基礎(chǔ)領(lǐng)域不沾邊，可是編譯原理卻一直作為大學(xué)本科的必修課程，同時(shí)也成為了研究生入學(xué)考試的必考內(nèi)容。編譯原理及技術(shù)從本質(zhì)上來講就是一個(gè)算法問題而已，當(dāng)然由于這個(gè)問題十分復(fù)雜，其解決算法也相對(duì)復(fù)雜。我們學(xué)的數(shù)據(jù)結(jié)構(gòu)與算法分析也是講算法的，不過講的基礎(chǔ)算法，換句話說講的是算法導(dǎo)論，而編譯原理這門課程講的就是比較專注解決一種的算法了。在20世紀(jì)50年代，編譯器的編寫一直被認(rèn)為是十分困難的事情，第一個(gè)Fortran的編譯器據(jù)說花了18年的時(shí)間才完成。在人們嘗試編寫編譯器的同時(shí)，誕生了許多

2、跟編譯相關(guān)的理論和技術(shù)，而這些理論和技術(shù)比一個(gè)實(shí)際的編譯器本身價(jià)值更大。就猶如數(shù)學(xué)家們?cè)诮鉀Q著名的哥德巴赫猜想一樣，雖然沒有最終解決問題，但是其間誕生不少名著的相關(guān)數(shù)論。推薦參考書雖然編譯理論發(fā)展到今天，已經(jīng)有了比較成熟的部分，但是作為一個(gè)大學(xué)生來說，要自己寫出一個(gè)像Turboc C，Java那樣的編譯器來說還是太難了。不僅寫編譯器困難，學(xué)習(xí)編譯原理這門課程也比較困難。正是因?yàn)榫幾g原理學(xué)習(xí)相對(duì)困難，那么就要求有好的教師和好的教材。教師方面不是我們能自己更改的，而在教材方面我們卻可以按自己的意愿來閱讀。我下面推薦幾本好的編譯原理的教材。我推薦的書籍都是國外的經(jīng)典教材，因?yàn)樵趪鴥?nèi)的教材中，確實(shí)還沒

3、發(fā)現(xiàn)什么讓人滿意的。第一本書的原名叫Compilers Principles,Techniques,and Tools，另外一個(gè)響亮的名字就是龍書。原因是這本書的封面上有條紅色的龍，也因?yàn)樗院芏鄧獾膶W(xué)者都直接取名為龍書。最近機(jī)械工業(yè)出版社已經(jīng)出版了此書的中文版，名字就叫編譯原理。該書出得比較早，大概是在85或86年編寫完成的，作者之一還是著名的貝爾實(shí)驗(yàn)室的科學(xué)家。里面講解的核心編譯原理至今都沒有變過，所以一直到今天，它的價(jià)值都非凡。這本書最大的特點(diǎn)就是一開始就通過一個(gè)實(shí)際的小例子，把編譯原理的大致內(nèi)容羅列出來，讓很多編譯原理的初學(xué)者很快心里有了個(gè)底，也知道為什么會(huì)有這些理論，怎么運(yùn)用這些理

4、論。而這一點(diǎn)是我感覺國內(nèi)的教材缺乏的東西，所以國內(nèi)的教材都不是寫給愿意自學(xué)的讀者，總之讓人看了半天，卻不知道里面的東西有什么用。第二本書的原名叫Modern Compiler Design，中文名字叫做現(xiàn)代編譯程序設(shè)計(jì)。該書由人民郵電出版社所出。此書比較關(guān)注的是編譯原理的實(shí)踐，書中給出了不少的實(shí)際程序代碼，還有很多實(shí)際的編譯技術(shù)問題等等。此書另外一個(gè)特點(diǎn)就是其“現(xiàn)代”二字。在傳統(tǒng)的編譯原理教材中，你是不可能看到如同Java中的“垃圾回收”等算法的。因?yàn)镴ava這樣的解釋執(zhí)行語言是在近幾年才流行起來的東西。如果你想深入學(xué)習(xí)編譯原理的理論知識(shí)，那么你肯定得看前面那本龍書，如果你想自己動(dòng)手做一個(gè)先進(jìn)

5、的編譯器，那么你得看這本現(xiàn)代編譯程序設(shè)計(jì)。第三本書就是很多國內(nèi)的編譯原理學(xué)者都推薦的那本編譯原理及實(shí)踐?；蛟S是這本書引入國內(nèi)比較早吧，我記得我是在高中就買了這本書，不過也是在前段時(shí)間才把整本書看完。此書作為入門教程也的確是個(gè)不錯(cuò)的選擇。書中給出的編譯原理講解也相當(dāng)細(xì)致，雖然不如前面的龍書那么深入，但是很多地方都是點(diǎn)到為止，作為大學(xué)本科教學(xué)已經(jīng)是十分深入了。該書的特點(diǎn)就是注重實(shí)踐，不過感覺還不如前面那本現(xiàn)代編譯程序設(shè)計(jì)的實(shí)踐味道更重。此書的重點(diǎn)還是在原理上的實(shí)踐，而非前面那本那樣的技術(shù)實(shí)踐。編譯原理及實(shí)踐在講解編譯原理的各個(gè)部分的同時(shí)，也在逐步實(shí)踐一個(gè)現(xiàn)代的編譯器Tiny C。等你把整本書看完，

6、差不多自己也可以寫一個(gè)Tiny C了。作者還對(duì)Lex和Yacc這兩個(gè)常用的編譯相關(guān)的工具進(jìn)行了很詳細(xì)的說明。這一點(diǎn)也是很難在國內(nèi)的教材中看到的。推薦了這三本教材，都有英文版和中文版的。很多英文好的同學(xué)只喜歡看原版的書，不過我的感覺是這三本書的翻譯都很不錯(cuò)，沒有必要特別去買英文版的。理解理論的實(shí)質(zhì)比理解表面的文字更為重要。編譯原理的實(shí)質(zhì)前面已經(jīng)說過，學(xué)習(xí)編譯原理其實(shí)也就是學(xué)習(xí)算法而已，沒什么特別的。只不過這些算法的產(chǎn)生已經(jīng)形成了一套理論。下面我來看看編譯原理里面到底有什么高深的理論吧。幾乎每本編譯原理的教材都是分成詞法分析、語法分析（LL算法，遞歸下降算法，LR算法）、語義分析、運(yùn)行時(shí)環(huán)境、中間

7、代碼、代碼生成、代碼優(yōu)化這些部分。其實(shí)現(xiàn)在很多編譯原理的教材都是按照85，86出版的那本龍書來安排教學(xué)內(nèi)容的，所以那本龍書的內(nèi)容格式幾乎成了現(xiàn)在編譯原理教材的定式，包括國內(nèi)的教材也是如此。一般來說，大學(xué)里面的本科教學(xué)是不可能把上面的所有部分都認(rèn)真講完的，而是比較偏重于前面幾個(gè)部分。像代碼優(yōu)化那部分東西，就像個(gè)無底洞一樣，如果要認(rèn)真講，就是單獨(dú)開一個(gè)學(xué)期的課也不可能講得清楚。所以，一般對(duì)于本科生，對(duì)詞法分析和語法分析掌握要求就相對(duì)要高一點(diǎn)了。詞法分析相對(duì)來說比較簡單。可能是詞法分析程序本身實(shí)現(xiàn)起來很簡單吧，很多沒有學(xué)過編譯原理的人也同樣可以寫出各種各樣的詞法分析程序。不過編譯原理在講解詞法分析的

8、時(shí)候，重點(diǎn)把正則表達(dá)式和自動(dòng)機(jī)原理加了進(jìn)來，然后以一種十分標(biāo)準(zhǔn)的方式來講解詞法分析程序的產(chǎn)生。這樣的做法道理很明顯，就是要讓詞法分析從程序上升到理論的地步。語法分析部分就比較麻煩一點(diǎn)了?，F(xiàn)在一般有兩種語法分析算法：LL自頂向下算法和LR自底向上算法。LL算法還好說，到了LR算法的時(shí)候，困難就來了。很多自學(xué)編譯原理的都是遇到LR算法的理解成問題后就放棄了自學(xué)。其實(shí)這些東西都是只要大家理解就可以了，又不是像詞法分析那樣非得自己寫出來才算真正的會(huì)。像LR算法的語法分析器，一般都是用工具Yacc來生成，實(shí)踐中完全沒有比較自己來實(shí)現(xiàn)。對(duì)于LL算法中特殊的遞歸下降算法，因?yàn)槠鋵?shí)踐十分簡單，那么就應(yīng)該要求每

9、個(gè)學(xué)生都能自己寫。當(dāng)然，現(xiàn)在也有不少好的LL算法的語法分析器，不過要是換在非C平臺(tái)，比如Java，Delphi，你不能運(yùn)用YACC工具了，那么你就只有自己來寫語法分析器。等學(xué)到詞法分析和語法分析時(shí)候，你可能會(huì)出現(xiàn)這樣的疑問：“詞法分析和語法分析到底有什么？”就從編譯器的角度來講，編譯器需要把程序員寫的源程序轉(zhuǎn)換成一種方便處理的數(shù)據(jù)結(jié)構(gòu)（抽象語法樹或語法樹），那么這個(gè)轉(zhuǎn)換的過程就是通過詞法分析和語法分析的。其實(shí)詞法分析并非一開始就被列入編譯器的必備部分，只是我們?yōu)榱撕喕Z法分析的過程，把詞法分析這種繁瑣的工作單獨(dú)提取出來，就成了現(xiàn)在的詞法分析部分。除了編譯器部分，詞法分析和語法分析在其它地方也是

10、有用的。比如我們?cè)贒OS,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)的遞歸性，也就是說我們可以把Tree的任何結(jié)點(diǎn)Node提取出來后，它依舊是一顆完整的Tree。這一點(diǎn)符合我們現(xiàn)在編譯原理分析的形式語言，比如我們?cè)诤瘮?shù)里面使用函數(shù)，循環(huán)中使用循環(huán)，條件中使用條件等等，那么就可以很直觀地表示在

11、Tree這種數(shù)據(jù)結(jié)構(gòu)上。同樣，我們?cè)趫?zhí)行形式語言的程序的時(shí)候也是如此的遞歸性。在編譯原理后面的代碼生成的部分，就會(huì)介紹一種堆棧式的中間代碼，我們可以根據(jù)分析出來的抽象語法樹，很容易，很機(jī)械地運(yùn)用遞歸遍歷抽象語法樹就可以生成這種指令代碼。而這種代碼其實(shí)也被廣泛運(yùn)用在其它的解釋型語言中。像現(xiàn)在流行的Java, .NET，其底層的字節(jié)碼bytecode，可以說就是這種基于堆棧的指令代碼。關(guān)于語義分析、語法制導(dǎo)翻譯、類型檢查等等部分，其實(shí)都是一種完善前面得到的抽象語法樹的過程。比如說，我們寫C語言程序的時(shí)候，都知道，如果把一個(gè)浮點(diǎn)數(shù)直接賦值給一個(gè)整數(shù)，就會(huì)出現(xiàn)類型不匹配，那么C語言的編譯器是怎么知道的

12、呢？就是通過這一步的類型檢查。像C+語言這種支持多態(tài)函數(shù)的語言，這部分要處理的問題就更多更復(fù)雜了。大部編譯原理的教材在這部分都是講解一些比較好的處理策略而已。因?yàn)樾碌膯栴}總是在發(fā)生，舊的辦法不見得足夠解決。本來說，作為一個(gè)編譯器，起作用的部分就是用戶輸入的源程序到最終的代碼生成。但是在講解最終代碼生成的時(shí)候，又不得不講解機(jī)器運(yùn)行環(huán)境等內(nèi)容。因?yàn)槿绻悴恢罊C(jī)器是怎么執(zhí)行最終代碼的，那么你當(dāng)然無法知道如何生成合適的最終代碼。這部分內(nèi)容我自我感覺其意義甚至超過了編譯原理本身。因?yàn)樗鼤?huì)把一個(gè)計(jì)算機(jī)的程序的運(yùn)行過程都通通排在你面前，你將來可能不會(huì)從事編譯器的開發(fā)工作，但是只要是和計(jì)算機(jī)軟件開發(fā)相關(guān)的領(lǐng)

13、域，都會(huì)涉及到程序的執(zhí)行過程。運(yùn)行時(shí)環(huán)境的講解會(huì)讓你更清楚一個(gè)計(jì)算機(jī)程序是怎么存儲(chǔ)，怎么裝載，怎么執(zhí)行的。關(guān)于這部分的內(nèi)容，我強(qiáng)烈建議大家看看龍書上的講解。作者從最基本的存儲(chǔ)組織，存儲(chǔ)分配策略，非局部名字的訪問，參數(shù)傳遞，符號(hào)表到動(dòng)態(tài)存儲(chǔ)分配(malloc，new)都作了十分詳細(xì)的說明。這些東西都是我們編寫平常程序的時(shí)候經(jīng)常要做的事情，但是我們卻少去探求其內(nèi)部是如何完成。關(guān)于中間代碼生成、代碼生成、代碼優(yōu)化部分的內(nèi)容就實(shí)在不好說了。國內(nèi)很多教材到了這部分都會(huì)很簡單地走馬觀花講過去，學(xué)生聽了也只是作為了解，不知道如何運(yùn)用。不過這部分內(nèi)容的東西如果要認(rèn)真講，單獨(dú)開一學(xué)期的課程都講不完。在編譯原理及

14、實(shí)踐的書上，對(duì)于這部分的講解就恰到好處。作者主要講解的還是一種以堆棧為基礎(chǔ)的指令代碼，十分通俗易懂，讓人看了后，很容易模仿，自己下來后就可以寫自己的代碼生成。當(dāng)然，對(duì)于其它代碼生成技術(shù)，代碼優(yōu)化技術(shù)的講解就十分簡單了。如果要仔細(xì)研究代碼生成技術(shù)，其實(shí)另外還有本叫做Advance Compiler Desgin and Implement，那本書現(xiàn)在由機(jī)械工業(yè)出版社引進(jìn)的，十分厚重，而且是英文原版。不過這本書我沒有把它列為推薦書給大家，畢竟能把龍書的內(nèi)容搞清楚，在中國已經(jīng)就算很不錯(cuò)的高手了，到那個(gè)時(shí)候再看這本Advance Compiler Desgin and Implement也不遲。代碼優(yōu)

15、化部分在大學(xué)本科教學(xué)中還是一個(gè)不太重要的部分，就是算是實(shí)踐過程中，相信大家也不太運(yùn)用的到。畢竟，自己做的編譯器能正確生成執(zhí)行代碼已經(jīng)很不錯(cuò)了，還談什么優(yōu)化呢？關(guān)于實(shí)踐編譯原理的課程畢竟還只是講解原理的課程，不是專門的編譯技術(shù)課程。這兩門課程是有很大的區(qū)別的。編譯技術(shù)更關(guān)注實(shí)際的編寫編譯器過程中運(yùn)用到的技術(shù)，而原理的課關(guān)注講解其基本理論。但是計(jì)算機(jī)科學(xué)本身就是一門實(shí)踐性很強(qiáng)的課程，如果能夠?qū)W以致用，那才叫真正的學(xué)會(huì)。李陽在講解瘋狂英語的時(shí)候就說到，只要當(dāng)你會(huì)實(shí)際中運(yùn)用一個(gè)單詞一個(gè)詞組的時(shí)候你才能叫學(xué)會(huì)了這個(gè)單詞或者詞組，而不是只是知道了它的拼寫和意思。其實(shí)任何學(xué)習(xí)都是一樣的，如果缺少了實(shí)踐的結(jié)合

16、，你不能算學(xué)會(huì)。編譯原理的課程主要就是講解編譯器產(chǎn)生的理論和原理，那么很簡單，自己寫個(gè)編譯器就是最好的實(shí)踐過程了。不過你得小心，編譯系統(tǒng)可能是所有軟件系統(tǒng)中最復(fù)雜的系統(tǒng)之一，不然為什么大學(xué)里面還會(huì)把編譯器的編寫開成一門叫做編譯原理的課程來講？我很佩服那些學(xué)了操作系統(tǒng)原理就開始自己寫操作系統(tǒng)，學(xué)了編譯原理就開始自己寫編譯器的人們。確實(shí)，在中國，敢這么做的學(xué)生太少了。且不管你這樣做能不能做成功，至少有了這個(gè)嘗試，會(huì)讓你的程序設(shè)計(jì)，系統(tǒng)規(guī)劃安排的功底增進(jìn)不少。我下面給出一些關(guān)于實(shí)踐過程中可能會(huì)遇到的困難，希望能夠在你陷入困境前幫你一把。1. Lex和Yacc。 這兩工具是作為詞法分析和語法分析的工具

17、。如果你自己寫一個(gè)編譯器，我十分不建議你連詞法分析這種事情都親手來寫。Lex和Yacc應(yīng)該是作為每本編譯原理的教材的必備內(nèi)容，可是在國內(nèi)的教材中缺很少看到。這兩個(gè)工具是Unix系統(tǒng)下的小東西，如果你要在Windows中運(yùn)用，那么你最好去下在cygwin這個(gè)軟件。它是個(gè)在Windows下模擬Unix的東東，里面就包含了flex.exe和bison.exe(Yacc)這兩個(gè)工具。這兩個(gè)工具使用起來還挺麻煩的(其實(shí)unix下的很多十分有用的工具都是這樣)，不過在編譯原理與實(shí)踐這本書上對(duì)于這兩個(gè)工具的講解十分詳細(xì)，還列舉了不少實(shí)際的例子。2. 做解釋型語言比做生成機(jī)器代碼的編譯器簡單。雖然說，做解釋型的編譯器，像Java那樣的，你還得自己去寫解釋器，不過這樣你就不必去查找機(jī)器代碼的資料了。如果你做生成的最終機(jī)器代碼編譯器可能會(huì)遇到問題，還有就是寄存器為基礎(chǔ)的代碼生成方法。前面說過，如果你生成的是以堆棧為基礎(chǔ)的代碼，那么其代碼生成過程十分簡單，需要考慮的東西也不多，如果你考慮最終的機(jī)器代碼生成的話，你必須考慮機(jī)器的寄存器如何分配等麻煩的問題。3. 考慮用別人已經(jīng)生成的語法文件，盡量不要自己動(dòng)手寫詞法文件和語法文件。以前一個(gè)朋友曾經(jīng)說