想裸寫編譯器，除了編譯原理外還有那些資料可以參考？應該從什麼開始寫起？（用c/c++）？

01-12

編譯器

可以先寫一個簡單的腳本語言，只支持函數和int 數組。只支持棧空間內存，無垃圾收集。語法直接參考pascal（因為pascal的parser手寫起來容易）

先看書，學習手寫遞歸下降語法分析，然後自己定義一個簡單的中間指令集。其他的東西都可以自己先瞎寫。寫完之後結合自己的經驗再去看書，然後再寫一個更高級的編譯器。。

作為入門，還是要再推薦一下《遊戲腳本高級編程》這本書。

相對於在座各位大牛們更為專業老道的答案，我本人的答案也許對於題主而言有另一種參考價值。

因為我也正在寫一個編譯器，而且我之前沒有寫過編譯器，我也不知道怎麼寫編譯器，我準備走一步看一步，然後逐步寫完這個編譯器。

某種意義上說，我本人的情況更接近題主的情況。題主既然用了「裸寫」一詞，也許可以說明題主應該之前沒有寫過編譯器的經歷，那就和我的情況類似啦。

另外，我打算把我寫編譯器的過程全程直播（實際上就是開個博客，不斷更新內容）。因此，題主可以來看看我的直播哦。相對於那些高屋建瓴的指教，也許我這種可能會磕磕碰碰的直播也有其參考價值。

附上專欄系列：從零開始寫個編譯器吧系列 - 平凡與非凡 - 知乎專欄

（之前在網易博客上，不過既然現在已經開通了專欄，還是在專欄上寫吧）

-------------------------------------引用分割線-------------------------------------

是的，這個系列將呈現一個完整的編譯器從無到有的過程。當然，為了保證該系列內容的簡潔（也為了降低難度），僅僅保證編譯器的最低要求，即僅能用。但在寫這個編譯器的過程中，我可不會偷工減料，該有的一定會寫上的。

編譯器將用於編譯一門我所創的語言，暫時命名為 tao 語言。該語言是動態語言，面向對象，原型繼承。支持用 lambda 表達式寫函數閉包，此外，也不會出現（討厭的）花括弧。好吧，我目前腦海中這門語言的印象就是如此了。

該語言的虛擬機將運行於 JVM 之上，同時編譯器將使用 Java 實現。

最後說明一下本人的情況吧。我早有寫編譯器的想法（之前沒寫過），故希望一邊寫編譯器一邊完成這個系列。一來作為學習筆記，二來公之於眾以督促自己不中途偷懶。寫此系列還是抱著學習的態度，雖然之後內容寫得會像教程一樣，但讀者若有指教，請勿吝惜。不求無錯，但求有所長進。

從零開始寫個編譯器吧（目錄）

從零開始寫個編譯器吧 - 從何處下手
從零開始寫個編譯器吧 - 編譯器的結構
從零開始寫個編譯器吧 - 單詞化簡述（Tokenization）
從零開始寫個編譯器吧 - tao語言的詞法分析器（Tokenizer）的類型定義
從零開始寫個編譯器吧 - Token.java 文件的編寫
從零開始寫個編譯器吧 - 詞法分析器是一個狀態機
從零開始寫個編譯器吧 - 開始寫詞法分析器（1）
從零開始寫個編譯器吧 - 開始寫詞法分析器（2）
從零開始寫個編譯器吧 - 符號分析，編寫 SignParser.java 文件
從零開始寫個編譯器吧 - 開始寫詞法分析器（3）
從零開始寫個編譯器吧 - Parser 語法分析器
從零開始寫個編譯器吧 - 文法簡介
從零開始寫個編譯器吧 - LL(1)
從零開始寫個編譯器吧 - 分析非終結符
從零開始寫個編譯器吧 - 數量詞符號
從零開始寫個編譯器吧 - TerminalSymbol.java 與 NonTerminalSymbol.java
從零開始寫個編譯器吧 - tao 語言的文法定義（上）
從零開始寫個編譯器吧 - tao 語言的文法定義（下）
從零開始寫個編譯器吧 - 程序流控制
從零開始寫個編譯器吧 - 函數的定義與 Lambda 表達式
從零開始寫個編譯器吧 - 難題
從零開始寫個編譯器吧 - 如何生成一棵語法樹
從零開始寫個編譯器吧 - Parser 啟動前的準備
從零開始寫個編譯器吧 - SELECT 集的用途
從零開始寫個編譯器吧 - 文法預處理

（未完待續）

對於編譯器來說，編譯原理是基礎，只有了解了才會知道如何寫編譯器。那麼也就是說你若真的理解了編譯原理，我想你就知道從何寫起了。所以，我想你現在應該再次仔細閱讀編譯原理，理解了整個編譯流程再思考下一步吧。:)

哎喲，其實我真有特別的編譯器技巧，來，坐下聽我慢慢講

你不想看編譯原理嘛，也不是不可以。。。。

這樣吧，你設計一個語言，以換行符為token分割線，這樣你就直接得到了一個tokenizer誒。。。。

然後你把這個語言編譯成c語言。。。

什麼你說這個方案太弱智了？我敢說50年代你拿這個方案出來肯定可以進ibm寫大型機

那咱就換種方案吧。。。

你規定各種限制長度，和語言的寫法，然後用這個寫法去寫程序，編譯器就用這個寫法來解析程序，這個發明也可以進50年代的ibm寫大型機誒

你如果想好好學，還是好好看編譯原理吧。。別想多了

前端的部分，看Bryan Ford的Parsing Expression Grammars和Packrat Parsing就可以開寫了，不用折騰LL(k)之類的文法，效果好，帶記憶化的遞歸下降也很好寫。當然，需要消掉左遞歸，龍書和Parsing Techniques上都有具體方法。

不在意語法的話就用S表達式好了。先寫個算術表達式的解釋器，再寫個Scheme的解釋器，最後給語言再加上類型系統和類型推導。寫解釋器推薦Norvig的用Python寫Lisp的教程。另外還有經典之作Essentials of Programming Languages專門教寫支持各種語言特性的各種解釋器，不過需要有一點lisp基礎。關於類型系統當然首推Pierce的Types and Programming Languages。

會寫正確的解釋器了，可以考慮做代碼生成了。用LLVM/JVM皆可，甚至編譯到C/ASM。。。有很多文檔。自己做bytecode虛擬機的話，Springer出版社有一本標題為Virtual Machines的書專講如何寫虛擬機。做JIT的話，我沒讀到過專門講JIT的書，但原理很簡單，運行時分配一塊可執行的內存，把編譯好的機器碼寫進去，然後調用。記得LuaJIT有個JIT庫叫DynASM，似乎實現得不錯，可以去看看。

至於編譯優化，面向過程/面向對象的優化，龍書總結得很全。至於函數式語言，可以看Compiling with Continuations里提出的CPS(Continuation Passing Style)，還有Implementing Functional Languages: A Tutorial里的幾種抽象機器，包括G machine，TIM等。

總之如果是造新語言的話，盡量語法弄簡單點，精力集中在理清楚語義細節和做好各種優化之類的事情上唄。S表達式不好看但是parser好寫啊，要不然折騰運算符優先順序和左結合/右結合消歧義、文法消左遞歸之類的活多累啊，一大票人就倒這兒了，可做語言/編譯器最好玩/有意義的顯然不是parser啊。。另外細節是魔鬼，什麼表達式求值順序之類的，稍有不慎就教做人了。

======UPDATE: 2014/11/04======

關於PEG和Packrat：鏈接Packrat Parsing and
Parsing Expression Grammars。PEG是一種與CFG神似但嚴格保證無歧義的文法，其語義直接對應到一個遞歸下降parser。藉助lazy evaluation的技巧可以避免回溯造成指數時間複雜度，當然用C++來寫的話就是手工維護一個表，用OI黨的說法就是動態規劃/記憶化搜索。

關於寫解釋器：開坑設計語言和做編譯器，我覺得先把解釋器寫出來比較好，作為語言原型，如果能扛住各種奇怪邊緣情況的程序不出錯，說明語義理清楚了。不介意開hard模式的話，Springer社還有本Abstract Computing Machines: Werner Kluge: 0003540211462: Amazon.com: Books，把裡面的抽象機器都寫一遍解釋器。。。

關於JIT：一篇簡短的入門文http://blog.reverberate.org/2012/12/hello-jit-world-joy-of-simple-jits.html

另外撤回對Implementing Functional Languages: A Tutorial的推薦，除非有一定Haskell基礎，對lazy evaluation有經驗。至於Compiling with Continuations，需要Standard ML基礎，不過我覺得SML比Haskell好學多了。

我覺得這是完成一個編譯器最簡單的方式了：LLVM Tutorial: Table of Contents

很開心看到第二個有興趣回答的問題。於是放下自己手頭compiler里的bug不管，也想要來回答這個問題。我覺得在回答這個問題之前呢，需要問自己兩個問題。一個是，為什麼要寫編譯器？另一個是，編譯器寫來做什麼？

這看起來是兩個很相似（實際上也確實很相關），但是其實還有一點點不同。對於第一個問題，為什麼要寫編譯器？是要學習編譯器的知識（寫來玩）？應付課業要求？項目里有個實際的工作，直接用target language寫太吃力？或者其它我沒有想到的需求？我覺得如果是要應付實際的項目呢，那麼是會有一個goal在drive你思考如何設計這個語言。這樣第二個問題又要分為是寫給自己的，還是寫給別人用的？那麼我的建議是儘可能把語言設計得簡單，比鑽研高超的編譯器編寫技巧可能更有效率一些。這點我在後面一點再來討論。

如果是前面兩種呢，那我可以從學院派的角度來粗淺的給出一個我所能給出的解答。我個人寫過大概3-4個編譯器。第一個是本科時的大作業，完全是學習如何寫一個編譯器。之後呢，在寫paper的過程中會陸續有遇到需要寫compiler的需求，所以也寫過一些。我先來就學習的角度講一講如何學寫compiler，然後講一講我自己在寫paper過程中寫compiler的體會。這個回答大體上由一小段講第一次寫compiler的high level introduction和一些reference pointer，而後更多的討論是關於為什麼要寫compiler，如何分配engineering amout，以及如何應對工作中的需求。

我個人覺得在寫compiler之前，是一定要有一個sense，為什麼要寫compiler。這個東西是要讓機器可以去處理人寫出來的unstructural language pieces，以方便機器去理解人所要表達的語義。所以算是人和機器之間的橋樑。有了這個idea就大概比較可以理解compiler的工作原理了：首先有個語法分析器來把character sequence轉化為token；然後詞法分析器來在token sequence上加入一個上下文無關的靜態的語義；然後根據上下文，更深層次的理解靜態的語義（type checking，data flow analysis，abstract interpretation等）；在完全理解了語義之後，試圖理解出來的語義以最精鍊的方式(optimization)，翻譯到某個特定的機器可以講的語言（code generation）。

好了，那我上面已經大致把compiler分割成幾個小部分了，那麼作為初學者來說呢，可以單獨的學習每一個部分。一本非常好的教科書就是虎書

Modern Compiler Implementation

那麼如果覺得follow這個還是嫌麻煩呢，可以找一些美國學校裡面的compiler course來follow。比如，我在12年做過一門課的助教，就有分布的教怎麼寫compiler的每一部分。只不過這門課是用ocaml來寫lua的一個解釋器。14年的版本可以在這裡找到：

CMSC 430, Fall 2014

同時resource里的一些資源也非常好

CMSC 430, Fall 2014

那麼問題中有特別提到要用C/C++來寫，所以我也不太清楚ocaml這個能不能滿足需求。不過我覺得呢，同一個意思總可以在不同的語言之中表達得很清楚，只不過哪個方便哪個不方便的問題。C的compiler呢，就比較少的會提供檢查bug的功能，但是非常efficient。而高級的語言呢，比如Java甚至OCaml，就會bug相對較少，而且在編譯不是很大的程序的時候，也不會有特別大的性能差。比如我自己除了在MSRA和MSR的時候是用C#和F#寫編譯器，其它時間都是用Java寫，因為用得比較習慣，而對於性能也沒有那麼苛刻的要求。

另外看到上面有在講lexer和parser的問題。我覺得作為初學者，知道lex和yacc怎麼玩，並且大概知道它們後面的工作原理也就夠了。比如我自己要寫C的compiler，那麼我從來都是從網上download一個別人寫好的JavaCC的C Parser，然後在這個基礎上把它改得面目全非的。我的建議是不需要特別多的糾結於front-end compiler，先理解整體，然後有興趣再去鑽研每個部分會比較好一些。

那麼接著來講講我自己寫compiler的經歷。那麼我來讀PhD做的第一個compiler呢，13年初發了一篇paper，然後拿了當年的一個best paper of the best papers一類的獎（赤裸裸的bso，哈哈哈）。好了，正經講故事。我們當時是希望把C program compile到一個變種的RISC V hardware上面，使得target code滿足一些security property。那麼我們最初的想法呢就是找clang和llvm來改一改，比如在clang上面加幾個keyword，再在llvm上寫加一個optimization pass這種。不過我當時看了一段時間它們的source code感覺實在是頭大，不知道為什麼我們的project需要用到這麼heavy的tool。於是就自己花了一周時間實現了一個5000來行java code的compiler。實現了我要實現的一切靜態分析器（一個security type checker和一個optimized code generator），當然很多optimization比如peephole optimizations，dead code elimination之類的我都沒有做。不過寫paper來說夠了。我講這個故事出來就是想要說，並不要總是想我要實現一個compiler (C/C++ -&> whatever) 就去參考已經有的很成功的案例(gcc or llvm)，因為它們對於你希望要的結果來說，可能是over-engineered (and thus over complicated)。所以我們回到開始的兩個問題，如果目的是想要學習寫compiler，或者只是想要用於自己的一些research purpose的話，那麼build from scratch（可能就是所謂的裸寫）可能是最快速省力的。

之後大致到了13年底的時候，I got involved into another research project。所以需要寫另一個compiler。這兩個compiler在某種程度上來說非常非常的像，因為它們的security property幾乎是一樣的。但是呢，從source language，到AST，到IR，到type checker，再到code generation都有一定程度的不同。所以我幾乎完全沒有辦法重用我上半年寫的code，於是只好再次重新的build from scratch to write a compiler。當然這也沒花我太多時間。但是這種感覺很annoying，因為這意味著幾乎一樣的work你需要完全重新做一遍。之前已經證明過的你的compiler的正確性，以及你的compiler可以產生安全的代碼，現在都要再次重新證明一遍。這是非常tedious的。所以在今年夏天的時候我們就想說，那麼能不能把這兩個有相似性的語言整合到一起，這樣的話相似的工作可以只做一次就好了。那麼我們在有了這個想法之後，我們就認真的去思考這想做的可能性，發現難度非常大，但也並不是完全不可能。而且如果一定要做的話，不只在理論上會有挑戰，那麼會有遠超paper所能容納的engineering work在前面。當然在這個時候，當你希望你做一個東西，被儘可能多的人去用的時候，你才會去想要在engineering上面花時間，在你的compiler里加入各種各樣在formalization的時候被簡化掉的feature和syntactic sugar。所以這一點是非常困難的，但是對於製造影響力又是非常重要的。以我個人的淺見，近年來最成功的兩個學院派出來的影響力很大的language產品呢，一個就是EPFL出品的scala，另一個就是UIUC出品的llvm。

可能一段比較不相關的話，只是我個人有感而發寫到這裡。在PL領域呢，大家都很重視logic，非常重視新的idea可以怎麼樣讓compiler可以reason about the program。理論的魅力是如此之大，讓我等研究者不禁沉迷其中。不過雖然大家做了很多很漂亮的理論上的結果出來，但是能應用到產品中的並不多。而做出有影響力的產品又是如此的迷人。這是為什麼在Rust出來之後，所有做affine type system的人會看到希望。這也是為什麼MSR的Don Syme突然有一天決定說以後再也不寫一條typing rule，於是不久之後我們有了F#。

說了這麼多，最後我覺得是時候講的一點建議就是，如果是在實際中有真實的需求，那麼請思考要寫的compiler會被多少人用。因為compiler的意義在於，一次寫完，後人獲益。所以如果只是要寫一個compiler來compile一個程序，那麼寫compiler+寫程序的時間可能還超過了直接用target language來寫code的時間。如果只是把一些特定的用target language來寫非常sophisticated的logic來用比較好寫的方式來寫，那麼是不是compiler的source syntax也不需要設計的特別複雜，就可以很好的完成所需要做的工作呢。如果是想要把自己做的東西給別人用（比如給公司用），那麼就要思考別人用起來怎麼方便的問題了。不過希望第一次「裸寫」 compiler不要用到這個方面的內容吧。

繼續debug去了。。。

Language Implementation Patterns，比較詳細的教你如何寫LL編譯器，另外可關注vczh的博客。

看完編譯原理……的第一章，你就知道從哪寫起了。

然後，我推薦你實現個簡單的 lisp 方言，解釋執行的（不推薦一開始就上 CEK，最簡單的樹解釋就行）。

然後提高它的速度。

如果你只是想玩個前端有個type checking生成簡單的中間代碼，然後後段上llvm，或者直接生成簡單stack machine類似的機器指令，龍書夠了，但你要是想搞後端,把代碼優化寄存器分配都幹了像llvm那樣，我只能說孩子路還很長，那個不是單單看幾本書就能搞定的。

不需要其它材料了，而且龍書也只不過是用作理論的了解（注意是了解，並不需要深入理解）。既然是C/C++寫編譯器，那麼可以找lex/yacc把parsing做完，剩下的其實就是沒什麼難度的大模擬了。

別的不提，C/C++其實不適合做編譯器的原型，或者做toy，因為你需要考慮的玩意太多。

建議用內帶正則表達式的腳本語言來做toy編譯器，比如Perl。

github參考:https://github.com/whps/Tiger

書籍參考: 虎書

個人能力就要看你的理解力了。

(不難）

https://github.com/Mookel/tiger

虎書是必須要看的。

編譯原理＋彙編

編譯原理：詞法分析，語法分析

彙編：能把分析出來的表達式轉義成彙編的形式

建議開始階段不用支持所有的文法，基本語句支持了就可以了，最主要的是學習設計思想。

蕭大怎麼不回一句：看sicp。。。。。

可以閱讀gcc的源代碼。然後改它。

基本原理心裡有數就不必裸寫。

若不必要不寫也可以。別人寫的用用也無不可。