21分鐘學會寫編譯器_ZenDei技術網路在線

知乎上有一種說法是「編譯器、圖形學、操作系統是程式員的三大浪漫」。　　先不管這個說法是對是錯，我們假設一個程式員在國內互聯網公司寫代碼，業餘時間不看相關書籍。那麼三年之後，他的這些知識會比在校時損耗多少？很顯然，損耗的比例肯定非常高，畢竟國內互聯網公司日常開發工作中，程式員基本很少接觸... ...

　　知乎上有一種說法是「編譯器、圖形學、操作系統是程式員的三大浪漫」。

　　先不管這個說法是對是錯，我們假設一個程式員在國內互聯網公司寫代碼，業餘時間不看相關書籍。那麼三年之後，他的這些知識會比在校時損耗多少？

很顯然，損耗的比例肯定非常高，畢竟國內互聯網公司日常開發工作中，程式員基本很少接觸這三塊知識。大部分程式員工作幾年後對編譯原理相關的概念只能生理上起反應，腦海裡很難再串聯起相關概念了。

　　編譯原理的概念有讓人看到就頭痛的特質，學校里要死記硬背，考試過了巴不得趕緊全忘掉，相信不少同學現在看到下麵概念還會覺得蛋疼：

非確定性有限自動機/確定性有限自動機
四元式序列
上下文無關文法/BNF
終結符/非終結符
LL(1)/LR(1)
特設語法制導轉換
局部優化

　　如果要按照課程來，光是背下這些名詞和釋義別說21分鐘了，21天都有難度。更何況背下來這些名詞之後如何寫編譯器又是另一個問題。

　　我們很多時候，都只是想快速上手寫一個編譯器，有可能是因為好奇，有可能是想實現自己的玩具DSL（領域特定語言），或者有可能是為了在約架時候防身。

　　今天的主題就是如何用21分鐘的時間學會寫編譯器，上面的廢話大概花費1分鐘，接下來還剩20分鐘。

　　正式開始做編譯器之前，先以問答的形式對接下來的內容做個簡單介紹：

什麼是編譯器？

　　廣義的編譯器可以指任意把一種語言代碼轉為另一種語言代碼的程式。

做編譯器實際上都需要做什麼？

　　編譯器是一整套工具鏈，從前端的詞法分析、語法分析，到中間表示生成、檢查、分析、優化，再到代碼生成。

　　如果是編譯器從業者，大部分時間在做中間這塊；如果是業餘愛好者，大部分時間在做前端和代碼生成。

那我們今天做的是個什麼編譯器？

　　既然是21分鐘，那學會寫個gcc肯定是不可能的，就算拿來學Flex+Bison都只能入個門。

　　我們接下來會先確定一下源語言的語法集，然後設計一下抽象語法樹（AST）結構，寫一個Parser，把源語言轉換成一棵抽象語法樹，再寫一個CodeGenerator，把語法樹轉換為目標語言。

　　也就是說，相比於一個正常的編譯器，我們省去了類型檢查和中間表示的分析優化，並且為了能21分鐘內學會，我們會把源語言定義得特別蠢。

　　接下來開始正文。

　　先確定源語言：

　　這是一門看起來像lisp的四則運算語言，四個雙目運算符分別是「add」「sub」「mul」「div」。

　　多項四則運算可以這樣寫：

(mul (sub 5 (add 1 2)) 4)

　　再來確定目標語言：

　　同樣是一門四則運算語言，但是看起來可讀性更強，對應的四個雙目運算符分別是「+」「-」「*」「/」。

　　上面源語言的例子編譯完後應該是這樣：

((5 - (1 + 2)) * 4)

　　最後確定我們寫編譯器要用的語言：

　　我選擇Haskell，有兩個原因，一是寫Haskell有大名鼎鼎的ParseC，寫Parser非常方便；二是Haskell的代數數據類型的定義本身就是AST。

　　ParseC的全稱是Parser組合子。Parser，抽象理解就是一個輸入為字元串輸出為類型T的值的函數。ParseC庫實現了大量基礎Parser和Parser組合子，Parser組合子可以將庫自帶的基礎Parser和用戶定義的Parser隨意組合成新的更強大的Parser。

　　舉個例子，你實現了一個Parser，功能是根據輸入文本返回解析到的標識符名稱。ParseC庫實現了一個名叫many的parser組合子，跟你自己的Parser組合起來就產生了一個新的Parser：可以根據輸入文本返回解析到的標識符名稱list。

　　為什麼要用ParseC呢？因為用ParseC定義Parser具有PEG（解析表達式文法，原理不細講，不影響接下來學習）的所有好處，同時還不用再學習語言之外的知識（比如用flex和bison前要先學習這兩者自己的「DSL」）。

　　當然，其他語言也有類似的庫，比如c++有boost::spirit，Java/C#/F#/JS有Haskell的ParseC的工業級實現。這些語言跟Haskell的區別無非在於要寫一些額外的邏輯把Parser的解析結果轉成AST。

　　如果沒有接觸過Haskell的話也沒關係，接下來的示例代碼都非常declarative，非常self-descriptive，請放心食用。

　　接下來就開始寫代碼了，首先我們要定義AST的結構，目的是為了能用這個結構描述一切源語言表達式。

　　簡單分析一下源語言，我們可以直接得出表達式這個概念的遞歸定義：一個表達式要麼是一個字面值，要麼是一個雙目運算符和兩個表達式的求值結果。

　　然後是字面值這個概念的遞歸定義：一個字面值要麼是一個整型值，要麼是一個浮點型值。

　　在Haskell裡面這兩個定義寫成下麵這樣：

type BinOp = String
data Val =
    IntVal Integer
    | FloatVal Float
        deriving (Eq, Ord, Show)
data Exp = 
    ConstExp Val
    | BinOpExp BinOp Exp Exp
        deriving (Eq, Ord, Show)

　　跟前面的文字定義對應一下：

表達式Exp，要麼是一個字面值表達式ConstExp，由一個Val組成；要麼是一個雙目運算表達式BinOpExp，由一個操作符和兩個Exp組成。
值Val，要麼是一個整型值IntVal，由一個Integer組成；要麼是一個浮點型值FloatVal，由一個Float組成。

　　接下來開始寫Parser。流程是先為AST中的每個節點類型寫一個parser，然後再把這些parser組合起來形成能parse出整棵AST的parser。

　　我們先給自己定個小目標，比如先實現一個int_parser。

p_int :: Parser Integer
p_int  = do s <- getInput
            case readSigned readDec s of
                [(n, s')] -> n <$ setInput s'
                _         -> empty        <?> "p_int"

p_int_val :: Parser Val
p_int_val =  IntVal <$> p_int 
            <?> "p_int_val"

　　p_int是能從文本中Parse出Integer的Parser定義。而p_int_val改造了p_int，定義了能從文本中Parse出IntVal的Parser。

　　然後我們把int和float的parser組合起來成為一個val_parser。

p_val :: Parser Val
p_val =  listplus [p_int_val,p_float_val]

　　listplus可以簡單理解為並，在具體實現上會做回溯。

　　同理，我們先分別實現ConstExp的parser和BinOpExp的parser，再把兩者組合為exp_parser。

p_const_exp :: Parser Exp
p_const_exp =  ConstExp <$> p_parse p_val
            <?> "p_const_exp"

p_bin_op_exp :: Parser Exp
p_bin_op_exp =  p_between '(' ')' inner <?> "p_bin_op_exp"
    where
        inner = BinOpExp
                <$> p_parse (listplus [string "add", 
                                string "sub", string "mul", string "div"])
                <*> p_parse p_exp
                <*> p_parse p_exp
                <?> "p_bin_op_exp_inner"

p_exp :: Parser Exp
p_exp =  listplus [p_const_exp, p_bin_op_exp]
        <?> "p_exp"

　　到目前為止，我們的parser部分就完工了。

　　對Haskell有興趣的同學，可以安裝下ghci，是haskell的REPL，然後載入剛纔寫好的Parser.hs，在命令行里試一下：

Prelude> parse p_exp "" "(mul (sub 5 (add 1 2)) 4)"

　　可以看到輸出結果。稍微排版下，輸出結果變成了我們熟悉的樹形結構，Op為「mul」的BinOpExp就是樹的根節點。整個輸出就是一棵AST。

Right (BinOpExp 
            "mul" 
            (BinOpExp 
                "sub" 
                (ConstExp (IntVal 5)) 
                (BinOpExp 
                    "add" 
                    (ConstExp (IntVal 1)) 
                    (ConstExp (IntVal 2)))) 
            (ConstExp (IntVal 4)))

　　有了這棵AST，我們就可以開始做後續的代碼生成了。

　　CodeGenerator的主體是把Exp轉換成目標語言代碼的函數：

exp_gen :: Exp -> Maybe String
exp_gen (BinOpExp op e1 e2) = do
    s1 <- exp_gen e1
    sop <- op_gen op
    s2 <- exp_gen e2
    return (format "({0} {1} {2})" [s1, sop, s2])
exp_gen (ConstExp val) = do
    case val of 
        IntVal int_val -> return (show int_val)
        FloatVal float_val -> return (show float_val)

　　利用模式匹配這個語言特性實現多態既容易又優雅。

　　最後再套個殼，比如讀源文件，寫目標文件，整個編譯器就大功告成了。

　　好了，看到這裡，相信你對怎麼快速寫一個編譯器已經有了比較充分的瞭解。

　　當然，我並不否認，「21分鐘學會寫編譯器」有標題黨的嫌疑，如果想按本文介紹的方法從零開始寫編譯器，即使不用學flex和bison，不用回憶編譯原理課程內容，也還是需要瞭解PEG，瞭解自己熟悉語言的ParseC庫用法。

　　但是，這仍然是個人認為的最快上手寫編譯器的方法。遠離痛苦的抽象概念，從動手開始，不正是很多同學喜歡上寫代碼的初心嗎？

　　如之前所說，我們雖然實現了一個編譯器，但是這個編譯器非常蠢，比如BinOp的存在本身就有問題：

BinOp在AST中用字元串表示，我們就沒辦法檢查兩個操作數的類型。
BinOp成了特殊概念，而不是普通的函數。

　　如果有同學有興趣解決這些問題，可以直接在我的代碼基礎上做修改，擴展成自己的編譯器。代碼放在github上，鏈接在這裡。

　　文章中的一些背景知識由於篇幅原因我沒辦法一一解釋，這裡簡單列個reference，對相關話題感興趣的可以去搜索引擎搜索對應的關鍵字：

haskell的相關概念，看real world haskell即可。
ParseC的相關概念，可以找這幾篇文獻，「the essence of fp」「monads for fp」「monadic parser combinator」。
編譯原理相關概念，不建議看《龍書》，有興趣的可以翻翻看《Engineering a Compiler》。

　　公眾號：gamedev101「說給開發游戲的你」新開通，專註游戲開發技術分享，歡迎關註。