大家好，好久沒看到喵了，是不是想我了。
這是本喵看到的一篇好文章，所以忍不住想要拿過來。
知乎上有一種說法是「編譯器、圖形學、操作系統(tǒng)是程序員的三大浪漫」。
先不管這個說法是對是錯，我們假設(shè)一個程序員在國內(nèi)互聯(lián)網(wǎng)公司寫代碼，業(yè)余時間不看相關(guān)書籍。那么三年之后，他的這些知識會比在校時損耗多少？
很顯然，損耗的比例肯定非常高，畢竟國內(nèi)互聯(lián)網(wǎng)公司日常開發(fā)工作中，程序員基本很少接觸這三塊知識。大部分程序員工作幾年后對編譯原理相關(guān)的概念只能生理上起反應(yīng)，腦海里很難再串聯(lián)起相關(guān)概念了。
編譯原理的概念有讓人看到就頭痛的特質(zhì)，學校里要死記硬背，考試過了巴不得趕緊全忘掉，相信不少同學現(xiàn)在看到下面概念還會覺得蛋疼：
非確定性有限自動機/確定性有限自動機
四元式序列
上下文無關(guān)文法/BNF
終結(jié)符/非終結(jié)符
LL(1)/LR(1)
特設(shè)語法制導轉(zhuǎn)換
局部優(yōu)化
其實本喵在學習這門課的時候也很煩腦，畢竟這是號稱最難學的一門學科之一。本喵是在大四的時候?qū)W的這門課，經(jīng)過半個學期死命的看書，也還是懵懵懂懂，不怎么明白。但好在考試的時候過了。
什么是編譯器？
廣義的編譯器可以指任意把一種語言代碼轉(zhuǎn)為另一種語言代碼的程序
做編譯器實際上都需要做什么？
編譯器是一整套工具鏈，從前端的詞法分析、語法分析，到中間表示生成、檢查、分析、優(yōu)化，再到代碼生成。
如果是編譯器從業(yè)者，大部分時間在做中間這塊；如果是業(yè)余愛好者，大部分時間在做前端和代碼生成。
先確定源語言：
這是一門看起來像lisp的四則運算語言，四個雙目運算符分別是「add」「sub」「mul」「div」。
多項四則運算可以這樣寫：
(mul(sub5(add12))4
再來確定目標語言：
同樣是一門四則運算語言，但是看起來可讀性更強，對應(yīng)的四個雙目運算符分別是「+」「-」「*」「/」。
上面源語言的例子編譯完后應(yīng)該是這樣：
((5 -(1 +2))* 4)
最后確定我們寫編譯器要用的語言：
喵選擇Haskell，有兩個原因，一是寫Haskell有大名鼎鼎的ParseC，寫Parser非常方便；二是Haskell的代數(shù)數(shù)據(jù)類型的定義本身就是AST。
ParseC的全稱是Parser組合子。Parser，抽象理解就是一個輸入為字符串輸出為類型T的值的函數(shù)。ParseC庫實現(xiàn)了大量基礎(chǔ)Parser和Parser組合子，Parser組合子可以將庫自帶的基礎(chǔ)Parser和用戶定義的Parser隨意組合成新的更強大的Parser。
舉個例子，你實現(xiàn)了一個Parser，功能是根據(jù)輸入文本返回解析到的標識符名稱。ParseC庫實現(xiàn)了一個名叫many的parser組合子，跟你自己的Parser組合起來就產(chǎn)生了一個新的Parser：可以根據(jù)輸入文本返回解析到的標識符名稱list。
為什么要用ParseC呢？因為用ParseC定義Parser具有PEG（解析表達式文法，原理不細講，不影響接下來學習）的所有好處，同時還不用再學習語言之外的知識（比如用flex和bison前要先學習這兩者自己的「DSL」）。
當然，其他語言也有類似的庫，比如c++有boost::spirit，Java/C#/F#/JS有Haskell的ParseC的工業(yè)級實現(xiàn)。這些語言跟Haskell的區(qū)別無非在于要寫一些額外的邏輯把Parser的解析結(jié)果轉(zhuǎn)成AST。
如果沒有接觸過Haskell的話也沒關(guān)系，接下來的示例代碼都非常declarative，非常self-descriptive，請放心食用。
接下來就開始寫代碼了，首先我們要定義AST的結(jié)構(gòu)，目的是為了能用這個結(jié)構(gòu)描述一切源語言表達式。
簡單分析一下源語言，我們可以直接得出表達式這個概念的遞歸定義：一個表達式要么是一個字面值，要么是一個雙目運算符和兩個表達式的求值結(jié)果。
然后是字面值這個概念的遞歸定義：一個字面值要么是一個整型值，要么是一個浮點型值。
在Haskell里面這兩個定義寫成下面這樣：
跟前面的文字定義對應(yīng)一下：
表達式Exp，要么是一個字面值表達式ConstExp，由一個Val組成；要么是一個雙目運算表達式BinOpExp，由一個操作符和兩個Exp組成。
值Val，要么是一個整型值IntVal，由一個Integer組成；要么是一個浮點型值FloatVal，由一個Float組成。
接下來開始寫Parser。流程是先為AST中的每個節(jié)點類型寫一個parser，然后再把這些parser組合起來形成能parse出整棵AST的parser。
我們先給自己定個小目標，比如先實現(xiàn)一個int_parser。
p_int是能從文本中Parse出Integer的Parser定義。而p_int_val改造了p_int，定義了能從文本中Parse出IntVal的Parser。
然后我們把int和float的parser組合起來成為一個val_parser。
listplus可以簡單理解為并，在具體實現(xiàn)上會做回溯。
同理，我們先分別實現(xiàn)ConstExp的parser和BinOpExp的parser，再把兩者組合為exp_parser。
到目前為止，我們的parser部分就完工了。
對Haskell有興趣的同學，可以安裝下ghci，是haskell的REPL，然后加載剛才寫好的Parser.hs，在命令行里試一下
可以看到輸出結(jié)果。稍微排版下，輸出結(jié)果變成了我們熟悉的樹形結(jié)構(gòu)，Op為「mul」的BinOpExp就是樹的根節(jié)點。整個輸出就是一棵AST。
有了這棵AST，我們就可以開始做后續(xù)的代碼生成了。
CodeGenerator的主體是把Exp轉(zhuǎn)換成目標語言代碼的函數(shù)：
利用模式匹配這個語言特性實現(xiàn)多態(tài)既容易又優(yōu)雅。
最后再套個殼，比如讀源文件，寫目標文件，整個編譯器就大功告成了
好了，到了和大家說再見的時候了。如果有興趣可以去：http://mp.weixin.qq.com/s?__biz=MzIwNDU2MTI4NQ==&mid=2247483679&idx=1&sn=8df4b40386fb6182051f4926ab043636#rd這個網(wǎng)址看看。
