大 學課程為什么要開設編譯原理呢？這門課程關注的是編譯器方面的產生原理和技術問題，似乎和計算機的基礎領域不沾邊，可是編譯原理卻一直作為大學本科的必修 課程，同時也成為了研究生入學考試的必考內容。編譯原理及技術從本質上來講就是一個算法問題而已，當然由于這個問題十分復雜，其解決算法也相對復雜。我們 學的數據結構與算法分析也是講算法的，不過講的基礎算法，換句話說講的是算法導論，而編譯原理這門課程講的就是比較專注解決一種的算法了。在20世紀50 年代，編譯器的編寫一直被認為是十分困難的事情，第一Fortran的編譯器據說花了18年的時間才完成。在人們嘗試編寫編譯器的同時，誕生了許多跟編譯 相關的理論和技術，而這些理論和技術比一個實際的編譯器本身價值更大。就猶如數學家們在解決著名的哥德巴赫猜想一樣，雖然沒有最終解決問題，但是其間誕生 不少名著的相關數論。
推薦參考書
雖然編譯理論發展到今天，已經有了比較成熟的部分，但是作為一個大學生來說，要自己寫出一個像Turboc C,Java那樣的編譯器來說還是太難了。不僅寫編譯器困難，學習編譯原理這門課程也比較困難。
正是因為編譯原理學習相對困難，那么就要求有好的教師和好的教材。教師方面不是我們能自己更改的，而在教材方面我們卻可以按自己的意愿來閱讀。我下面推薦幾本好的編譯原理的教材。我推薦的書籍都是國外的經典教材，因為在國內的教材中，確實還沒發現什么讓人滿意的。
第 一本書的原名叫《Compilers Principles,Techniques,and Tools》,另外一個響亮的名字就是龍書。原因是這本書的封面上有條紅色的龍，也因為獗臼樵詒嘁朐 砘 ×煊蛉肥堤 忻 ?所以很多國外的學者都直接 取名為龍書。最近機械工業出版社已經出版了此書的中文版，名字就叫《編譯原理》。該書出的比較早，大概是在85或86年編寫完成的，作者之一還是著名的貝 爾實驗室的科學家。里面講解的核心編譯原理至今都沒有變過，所以一直到今天，它的價值都非凡。這本書最大的特點就是一開始就通過一個實際的小例子，把編譯 原理的大致內容羅列出來，讓很多編譯原理的初學者很快心里有了個底,也知道為什么會有這些理論，怎么運用這些理論。而這一點是我感覺國內的教材缺乏的東 西，所以國內的教材都不是寫給愿意自學的讀者，總之讓人看了半天，卻不知道里面的東西有什么用。
第二本書的原名叫《Modern Compiler Design》,中文名字叫做《現代編譯程序設計》。該書由人民郵電出版社所出。此書比較關注的是編譯原理的實踐，書中給出了不少的實際程序代碼，還有很 多實際的編譯技術問題等等。此書另外一個特點就是其“現代”而字。在傳統的編譯原理教材中，你是不可能看到如同Java中的“垃圾回收”等算法的。因為 Java這樣的解釋執行語言是在近幾年才流行起來的東西。如果你想深入學習編譯原理的理論知識，那么你肯定得看前面那本龍書，如果你想自己動手做一個先進 的編譯器，那么你得看這本《現代編譯程序設計》。
第三本書就是很多國內的編譯原理學者都推薦的那本《編譯原理及實踐》。或許是這本書引入 國內比較早吧，我記得我是在高中就買了這本書，不過也是在前段時間才把整本書看完。此書作為入門教程也的確是個不錯的選擇。書中給出的編譯原理講解也相當 細致，雖然不如前面的龍書那么深入，但是很多地方都是點到為止，作為大學本科教學已經是十分深入了。該書的特點就是注重實踐，不過感覺還不如前面那本《現 代編譯程序設計》的實踐味道更重。此書的重點還是在原理上的實踐，而非前面那本那樣的技術實踐。《編譯原理及實踐》在講解編譯原理的各個部分的同時，也在 逐步實踐一個現代的編譯器Tiny C.等你把整本書看完，差不多自己也可以寫一個Tiny C了。作者還對Lex和Yacc這兩個常用的編譯相關的工具進行了很詳細的說明，這一點也是很難在國內的教材中看到的。
推薦了這三本教材，都有英文版和中文版的。很多英文好的同學只喜歡看原版的書，不我的感覺是這三本書的翻譯都很不錯，沒有必要特別去買英文版的。理解理論的實質比理解表面的文字更為重要。
編譯原理的實質
前面已經說過，學習編譯原理其實也就是學習算法而已，沒什么特別的。只不過這些算法的產生已經形成了一套理論。下面我來看看編譯原理里面到底有什么高深的理論吧。
幾 乎每本編譯原理的教材都是分成詞法分析，語法分析（LL算法，遞歸下降算法，LR算法），語義分析，運行時環境，中間代碼，代碼生成，代碼優化這些部分。 其實現在很多編譯原理的教材都是按照85,86出版的那本龍書來安排教學內容的，所以那本龍書的內容格式幾乎成了現在編譯原理教材的定式，包括國內的教材 也是如此。一般來說，大學里面的本科教學是不可能把上面的所有部分都認真講完的，而是比較偏重于前面幾個部分。像代碼優化那部分東西，就像個無底洞一樣， 如果要認真講，就是單獨開一個學期的課也不可能講得清楚。所以，一般對于本科生，對詞法分析和語法分析掌握要求就相對要高一點了。
詞法分 析相對來說比較簡單。可能是詞法分析程序本身實現起來很簡單吧，很多沒有學過編譯原理的人也同樣可以寫出各種各樣的詞法分析程序。不過編譯原理在講解詞法 分析的時候，重點把正則表達式和自動機原理加了進來，然后以一種十分標準的方式來講解詞法分析程序的產生。這樣的做法道理很明顯，就是要讓詞法分析從程序 上升到理論的地步。
語法分析部分就比較麻煩一點了。現在一般有兩種語法分析算法，LL自頂向下算法和LR自底向上算法。LL算法還好說， 到了LR算法的時候，困難就來了。很多自學編譯原理的都是遇到LR算法的理解成問題后就放棄了自學。其實這些東西都是只要大家理解就可以了，又不是像詞法 分析那樣非得自己寫出來才算真正的會。像LR算法的語法分析器，一般都是用工具Yacc來生成，實踐中完全沒有比較自己來實現。對于LL算法中特殊的遞歸 下降算法，因為其實踐十分簡單，那么就應該要求每個學生都能自己寫。當然，現在也有不少好的LL算法的語法分析器，不過要是換在非C平臺，比如Java, Delphi,你不能運用YACC工具了，那么你就只有自己來寫語法分析器。
等學到詞法分析和語法分析時候，你可能會出現這樣的疑問： “詞法分析和語法分析到底有什么？”就從編譯器的角度來講，編譯器需要把程序員寫的源程序轉換成一種方便處理的數據結構（抽象語法樹或語法樹）,那么這個 轉換的過程就是通過詞法分析和語法分析的。其實詞法分析并非一開始就被列入編譯器的必備部分，只是我們為了簡化語法分析的過程，就把詞法分析這種繁瑣的工 作單獨提取出來，就成了現在的詞法分析部分。除了編譯器部分，在其它地方，詞法分析和語法分析也是有用的。比如我們在DOS,Unix,Linux下輸入 命令的時候，程序如何分析你輸入的命令形式，這也是簡單的應用。總之，這兩部分的工作就是把不“規則”的文本信息轉換成一種比較好分析好處理的數據結構。 那么為什么編譯原理的教程都最終把要分析的源分析轉換成“樹”這種數據結構呢？數據結構中有Stack, Line,List…這么多數據結構，各自都有各自的特點。但是Tree這種結構有很強的遞歸性，也就是說我們可以把Tree的任何結點Node提取出來 后，它依舊是一顆完整的Tree。這一點符合我們現在編譯原理分析的形式語言，比如我們在函數里面使用函樹，循環中使用循環，條件中使用條件等等，那么就 可以很直觀地表示在Tree這種數據結構上。同樣，我們在執行形式語言的程序的時候也是如此的遞歸性。在編譯原理后面的代碼生成的部分，就會介紹一種堆棧 式的中間代碼，我們可以根據分析出來的抽象語法樹，很容易，很機械地運用遞歸遍歷抽象語法樹就可以生成這種指令代碼。而這種代碼其實也被廣泛運用在其它的 解釋型語言中。像現在流行的Java,.NET，其底層的字節碼bytecode,可以說就是這中基于堆棧的指令代碼的。
關于語義分析， 語法制導翻譯，類型檢查等等部分，其實都是一種完善前面得到的抽象語法樹的過程。比如說，我們寫C語言程序的時候，都知道，如果把一個浮點數直接賦值給一 個整數，就會出現類型不匹配，那么C語言的編譯器是怎么知道的呢？就是通過這一步的類型檢查。像C++語言這中支持多態函數的語言，這部分要處理的問題就 更多更復雜了。大部編譯原理的教材在這部分都是講解一些比較好的處理策略而已。因為新的問題總是在發生，舊的辦法不見得足夠解決。
本來 說，作為一個編譯器，起作用的部分就是用戶輸入的源程序到最終的代碼生成。但是在講解最終代碼生成的時候，又不得不講解機器運行環境等內容。因為如果你不 知道機器是怎么執行最終代碼的，那么你當然無法知道如何生成合適的最終代碼。這部分內容我自我感覺其意義甚至超過了編譯原理本身。因為它會把一個計算機的 程序的運行過程都通通排在你面前，你將來可能不會從事編譯器的開發工作，但是只要是和計算機軟件開發相關的領域,都會涉及到程序的執行過程。運行時環境的 講解會讓你更清楚一個計算機程序是怎么存儲，怎么裝載，怎么執行的。關于部分的內容，我強烈建議大家看看龍書上的講解，作者從最基本的存儲組織，存儲分配 策略，非局部名字的訪問，參數傳遞，符號表到動態存儲分配(malloc,new)都作了十分詳細的說明。這些東西都是我們編寫平常程序的時候經常要做的 事情，但是我們卻少去探求其內部是如何完成。
關于中間代碼生成，代碼生成,代碼優化部分的內容就實在不好說了。國內很多教材到了這部分都 會很簡單地走馬觀花講過去，學生聽了也只是作為了解，不知道如何運用。不過這部分內容的東西如果要認真講，單獨開一學期的課程都講不完。在《編譯原理及實 踐》的書上，對于這部分的講解就恰到好處。作者主要講解的還是一種以堆棧為基礎的指令代碼，十分通俗易懂，讓人看了后，很容易模仿，自己下來后就可以寫自 己的代碼生成。當然，對于其它代碼生成技術，代碼優化技術的講解就十分簡單了。如果要仔細研究代碼生成技術，其實另外還有本叫做《Advance Compiler Desgin and Implement》,那本書現在由機械工業出版社引進的，十分厚重，而且是英文原版。不過這本書我沒有把它列為推薦書給大家，畢竟能把龍書的內容搞清 楚，在中國已經就算很不錯的高手了，到那個時候再看這本《Advance Compiler Desgin and Implement》也不遲。代碼優化部分在大學本科教學中還是一個不太重要的部分，就是算是實踐過程中，相信大家也不太運用得到。畢竟，自己做的編譯器 能正確生成執行代碼已經很不錯了，還談什么優化呢？
關于實踐
編譯原理的課程畢竟還只是講解原理的課程，不 是專門的編譯技術課程。這兩門課程是有很大的區別的。編譯技術更關注實際的編寫編譯器過程中運用到的技術，而原理的課關注講解其基本理論。但是計算機科學 本身就是一門實踐性很強的課程，如果能夠學以致用，那才叫真正的學會。李陽在講解瘋狂英語的時候就說到，只要當你會實際中運用一個單詞一個詞組的時候你才 能叫學會了這個單詞或者詞組，而不是只是知道了它的拼寫和意思。其實任何學習都是一樣的，如果缺少了實踐的結合，你不能算學會。
編譯原理 的課程主要就是講解編譯器產生的理論和原理，那么很簡單，自己寫個編譯器就是最好的實踐過程了。不過你得小心，編譯系統可能是所有軟件系統中最復雜的系統 之一,不然為什么大學里面還會把編譯器的編寫開成一門叫做編譯原理的課程來講？我很佩服那些學了操作系統原理就開始自己寫操作系統，學了編譯原理就開始自 己寫編譯器的人們，確實，在中國，敢這么做的學生太少了。且不管你這樣做能不能做成功，至少有了這個嘗試，會讓你的程序設計，系統規劃安排的功底增進不 少。我下面給出一些關于實踐過程中可能會遇到的困難，希望能夠在你陷入困境的前幫你一把。
1. Lex和Yacc. 這兩工具是作為詞法分析很語法分析的工具。如果你自己寫一個編譯器，我十分不建議你連詞法分析這種事情都親手來寫。Lex和Yacc應該是作為每本編譯原 理的教材的必備內容，可是在國內的教材中缺很少看到。這兩個工具是Unix系統下的小東西，如果你要在Windows中運用，那么你最好去下在 cygwin這個軟件。它是個在Windows下模擬Unix的東東，里面就包含了flex.exe和bison.exe(yacc)這兩個工具.這兩個 工具使用起來還挺麻煩的(其實unix 下的很多十分有用的工具都是這樣), 不過在《編譯原理與實踐》這本書上對于這兩個工具的講解十分詳細,還列舉了不少實際的例子。
2. 做解釋型語言比做生成機器代碼的編譯器簡單。雖然說，做解釋型的編譯器，像Java那樣的，你還得自己去寫解釋器，不過這樣你就不必去查找機器代碼的資料 了。如果你做生成的最終機器代碼編譯器可能會遇到問題還有就是寄存器為基礎的代碼生成方法。前面說過，如果你生成的是以堆棧為基礎的代碼，那么其代碼生成 過程十分簡單，需要考慮的東西也不多，如果你考慮最終的機器代碼生成的話，你必須考慮機器的寄存器如何分配等麻煩的問題。
3. 考慮用別人已經生成的語法文件，盡量不要自己動手寫詞法文件和語法文件.以前一個朋友曾經說過,寫出一個好的程序語言的語法定義,就幾乎完成了一個編譯器 的一半.確實是這樣,語法文件的編寫是個很難的事情.現在網上到處都可以找到比如C語言,C++,Java, Tiny C,Minus C等語言的詞法文件和語法文件,你完全可以自己下下來來用.
在《編譯原理及實踐》的書中，作者給出了一個Tiny C的全部代碼.我自我感覺作者的這個編譯器做得很不錯,相對于其它php,perl等語言的源代碼來說,簡單得多,容易看懂,而且很清晰地展現了一個完成的編譯系統的實現過程.其源代碼可以在作者的網站上下載.
后話
編譯原理的學習可能算是一個困難的歷程,特別是對于那些不對編譯系統感興趣的同學來說.既然它已經作為了大學本科的必修課程,那么就說明的它引申出來的一套理論在整個計算機科學領域還是占有相對重要的地位.
如果我們考究一下歷史,就會發現很多被稱為程序設計大師的人都是編譯領域的高手.寫出第一個微型機上運行的Basic語言的比爾蓋茨,設計出Delphi的Borland的”世界上最厲害的程序員”, Sun的J***A之父, 貝爾實驗室的C++之父…
芳兒寶貝.我愛你
