如何寫一個簡單的編譯器？

01-12

初學編譯原理，想寫一個簡單的編譯器。

如果是用 Haskell 的話，三篇文章足矣。

prerequisite: 懂 state monad就行了

第一篇，《How to build a monadic interpreter in one day》http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.368.2522

跟著做，可以完成一個簡單的backend，也就是架構基本的AST 並執行的步驟。

然後到frontend，也就是parser的部分你就會發現你看不懂了，這個時候看第二篇。（因為該文的 parser 部分其實是第二篇的一個濃縮版，所以不看第二篇基本很難看懂這個部分）

第二篇，《Monadic Parser Combinator》，http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf

看了也就能對照第一篇，把 parser 寫出來了，然後就能和之前的backend 組合，完成一個基本的，完全由自己手寫的，monadic的解釋器（parser 和 backend 分別由一個自定義的 state monad 實現）。順便加深對 monad 的理解。

看第二篇的時候，回過頭對照第一篇看效果會更高，雖然邏輯一樣，但第二篇是用 monad comprehension 的形式來寫，第一篇是用 do notation 來寫。有的複雜的地方你兩種方式對照看一下，會有茅塞頓開的效果。

然後再看第三篇

第三篇，llvm的haskell 教程， Implementing a JIT Compiler with Haskell and LLVM ( Stephen Diehl ) ，把你的backend 換成llvm. （註：事先對 llvm 不熟的話，可以和 hackage 上面 llvm-general, llvm-general-pure 這兩個庫的 wiki, 以及 LLVM Language Reference Manual對照著看）

至於frontend，可以換成Parsec之類，但也可以就不斷擴充之前自己寫的版本。

齊活兒~

------

今天閑著沒事兒，擼了一個 swift 的版本，GitHub - aaaron7/swift_monadic_parser: A simple haskell-style monadic combinator-based parser written in Swift. 僅包含最基本的 parser 和 interpreter 的功能，寫法完全按照前面兩篇文章的思路實現，有興趣可以看看。

是時候亮出我的 LL 語言了，全稱：Lambda Lite Js。

LL 是一個類似 haskell 的函數式語言，使用 Javascript 實現。在線demo：Lambda-lite-js。項目地址：GitHub - moevis/lambda-lite-js: a tiny FUNCITONAL LANGUAGE implemented by javascript. 一個函數式語言，使用 js 實現。。

大概寫了兩周多，有了很多很有趣的功能了，比如可以玩 lambda 演算，可以柯里化，可以玩閉包，可以玩模式匹配，可以使用 Point-Free 風格，具有局部 lazy-evaluation 特性等等。

先給幾個階乘的示例代碼。

普通階乘

let fact = -&> if n == 1 then 1 else n * (fact n - 1); print $ fact 5;

利用模式匹配寫階乘：

let fact n@1 = 1; let fact n@Number = n * (fact n - 1); print $ fact 5;

不動點組合子階乘：

let z = f -&> (x -&> f (y -&> x x y)) (x -&> f (y -&> x x y)); let makeFact = g -&> -&> if n &< 2 then 1 else n * (g n - 1); let fact = z makeFact; print $ fact 5;

網頁版運行截圖：

是的，就是和 haskell 這麼像。

=====說正事=====

之前我寫過一個 js 代碼高亮插件，用於高亮 html、js、css 代碼，GitHub - moevis/code-lighter: a lightweight code highlighting tool, 代碼高亮工具。原理是將代碼切分成一系列 tokens，然後給這些 tokens 添加著色就好了。

至於如何切分 tokens 呢？Parser 就是負責這個事情的。我們先將輸入的代碼先分成以下幾個基本元素：

數字 Number
字面量 Literial
標點 Punctuar
空白符 White
文件結束符 EOF

我們的任務就是要區分它們，這個目標還是蠻容易的，我們使用遞歸下降法來解析，這就是一個狀態機的模型：

首先，我們的初始狀態機 State 處於默認狀態。

讀入待解析代碼，讀第一個字元 c ，這時候有五種可能：

c 屬於 "9" ~ "0"，State 轉為數字模式。
c 屬於 "a" ~ "z" 或者 "A" ~ "Z"，State 轉為字面量模式。
c 屬於 "*,;"+"... 的標點，State 轉為標點模式。
c 屬於 " " 或者 "
" 或者空格，State 轉為空白符模式。
c 為空，則到了代碼的最後，State 為文件結束模式。

進入另一個模式後，我們會用不同的策略來接收下一個字元。比如，在數字模式假如下一個字元是 "0" ~ "9"，那麼讀入數字，並拼接到之前的數字後；直到接收到一個非數字的字元（這裡我們就不考慮小數了）。當退出數字模式，我們就能得到一個數字的 token 啦。同理我們可以得到標點，字面量等等。

關於字面量，我們還需要做一些分類，字面量包括變數名，關鍵字，所以我們實現要有一個關鍵字表，當字面量不再關鍵字表裡面，我們視為一個變數或者是函數名，否則就是有語法意義的字元比如 if else 。

初步的 tokens 切分結束後，去除空白 tokens，我們就得到一個 token 數組。

這時候我們要建立抽象語法樹（Abstract syntax tree）了。先設計幾個基本語法，比如聲明一個函數或者變數時，使用`let`關鍵字，`if...else...then...`做分支判斷，聲明匿名函數使用類似"
-&> n + 1"的語法（有且只有一個參數 n ，n + 1 為返回值），表達式採用中綴 `1 + 2 + a`。

這時候我們可以定義幾個樹節點類型了：

聲明節點, defineNode (let x = 5)
匿名函數節點, lambdaNode (
-&> n + 1)
分支節點，conditionNode (if ... then ... else ...)
引用節點，代表某一個已聲明的變數值或者函數名 objectNode
數位元組點，代表一個數字，numberNode
表達式節點, 代表某一中綴表達式，其本身儲存運算符，比如 a + b，節點儲存 `+`，expressNode
函數調用節點，表示對函數的調用，比如 print x，callNode

我們的任務就是將 tokens 轉為這些節點的相互關係。

首先還是讀入第一個 token，判斷 token 類型，如果是`let`，那麼就按照聲明節點來解析; 如果是``則是一個匿名函數聲明節點，如果是`if`，則解析一個分支節點…… 解析表達式節點會難一點，因為有運算符的優先順序，我參照了 llvm 教程中的 kaleidoscope 語言來寫（傳送門，Kaleidoscope: 實現解析器和抽象語法樹）。

總之這是需要你認真理解的一步，這一步完後，就可以根據語法樹來得到代碼運行結果了。每一種節點的結果計算方式都不同，但是有統一的介面 getValue()。比如聲明節點無返回值，匿名函數返回一個函數，分支節點先對 condition 求值，當 condition 為 true，返回第一個分支的 value，否則是第二個……

當這一切結束後，你的第一個語言就完成了。當然，現在我的語言已經比較複雜了，比如加入了模式匹配節點，聲明多參數函數的語法糖，改變結合方向等等。

你可以看我的 commit log 來看到我是如何一步一步添加這些功能的。

編譯原理這個方向，龍書虎書是經典，若要深入學習，一定要看。不過我也沒有時間啃下來，不過有一本書也是簡單有趣，叫做《計算的本質》，O『REILY 出的，值得信賴。

說了那麼多，我這個只能算是解釋器，並沒有真正編譯，當然對於初級已經夠了。你不滿足的話我再給你指條路，llvm 教程中有一個小語言叫做 kaleidoscope，你按照這個教程來，https://github.com/moevis/Kaleidoscope-LLVM-tutorial-zh-cn，這是我當年留下的中文翻譯坑，當時翻了一些後就去做實驗室任務了。這個從 parser 到 ast 到 ir 到各種優化都很全。

這個題目有點久了，現在才想起來答，主要還是因為暑假才找到空閑的時間，把我的C11編譯器寫完了。

這個編譯器，(GitHub - wgtdkp/wgtcc: a tiny C compiler in C++) 一方面是為了學習 C11, 一方面為了練習C++。

在約11k代碼中實現了：

幾乎完整的C11語法解析(除去變長數組);
語義與類型檢查(仿gcc的錯誤提示)
預處理器
x86-64彙編代碼生成，多謝 @RednaxelaFX 的回答寄存器分配問題？ - 編譯器，把我從無休止的手動優化中拯救回來
精簡的x86-64 ABI

心形很流行嘛，wgtcc編譯的M大( @Milo Yip ) 在如何用C語言畫一個「心形」？ - C（編程語言）回答里的代碼：

#include & int main() { for (float y = 1.5f; y &> -1.5f; y -= 0.1f) { for (float x = -1.5f; x &< 1.5f; x += 0.05f) { float a = x * x + y * y - 1; putchar(a * a * a - x * x * y * y * y &<= 0.0f ? "*" : " "); } putchar(" "); } }

C11 中有一些非常實用或者好玩的新特性，如 compound literal. 一個典型的用途是當我們想獲得一個數據的另一種表示的時候，我們可能會這麼做：

float f = 1.5; int i = *(int*)f;

然而gcc 在開 -O2 時會報 break strict-aliasing rules 的warning。有了 compound literal，我們可以這麼做：

#define CAST(s_t, d_t, sv) (union {s_t sv; d_t dv;}){sv}.dv float f = 1.5; int i = CAST(float, int, f);

而且這是一個模板呢～

C11 也支持在identifier 中使用unicode字元了，中文編程很exciting：

#define 整型 int #define 輸出 printf #define 面函數 main #define 返回 return #define 定義 typedef #define 不可變 const #define 字元 char #define 指針 * #define 為


定義 不可變 字元 指針 為 字面值;

整型面函數() { 字面值蛤蛤 = "u82dfu5229u56fdu5bb6u751fu6b7bu4ee5uff0c" "u5c82u56e0u7978u798fu907fu8d8bu4e4b"; 輸出("%s ", 蛤蛤); 返回 0; }

這些例子在example/目錄下可以找到。

說說寫這個小編譯器總結的方法吧：

以最快的速度做到能夠解析下面這段代碼：

int main(int argc, char** argv) { int i; return 0; }

以最快的速度看到hello，world。
開始對照語言標準一個一個實現特性，並同步做單元測試。因為已經看到hello world,這一步雖然工作量有點大，但是因為有了前面的經驗，可以很快。
解析聲明是最複雜的，所以先寫解析聲明。
龍書是必需的，一個好的參考也非常重要（如GitHub - rui314/8cc: A Small C Compiler）。
嘗試自舉(因為我用的C++，所以沒法自舉)。

寫一個編譯器的壞處是，以後寫一段代碼都試圖在腦子裡面翻譯成彙編。。。

// Update_1

// Date: 09/20/2016

匆忙寫的回答，感覺僅僅是拋出結果和小結，實在是太不負責任了=-=。沒有實現過的同學可能還是不知如何入手，下面就寫寫我是如何一步一步做的吧(某些內容只限於C編譯器)

1. 初始狀態，你必須有一本第二版的龍書。其它的答案可能會推薦《編譯器實現》或者《編程語言實現模式》。《編譯器實現》因為中文翻譯的比較生硬，讀了幾章，發現還是龍書比較好，後來基本沒有看《編譯器實現》了。如果你是直接讀原版，那麼還是推薦龍書，畢竟都有決心讀原版了，乾脆徹底一點讀龍書原版好了^_^。其實龍書並沒有那麼難，公式記不住，不理解，跳過就好了。《編程語言實現模式》其實很好的，各種實現方法都有所涉及。唯一不足的是，作者沒有向《代碼大全》的作者那樣，對我耳提面命 ----- 直接告訴我怎麼做就好了(相信這是新手最需要的...)。

2. 你必須有C11 standard。open-std 上面的draft就夠了(http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf)。(如果是其他語言的編譯器，對應之。如果是自己設計，那麼應該學著standard那樣，將grammar，constraints等寫下來)

3. 一個簡單的不帶優化的編譯器，基本只需要3個步驟：詞法分析，語法分析，代碼生成；對應到代碼裡面，就是3個class：Scanner, Parser, Generator;

4. 對於C語言編譯器，支持預處理器，相當於又支持了一門新的簡單語言了。所以一開始不必去支持預處理器。在測試時，只使用不包含預處理器的代碼就好了。或者，用gcc進行預處理，將其輸出作為你的編譯器的輸入。

5. 在真的動手開始寫Scanner之前，有必要讀n1548的5.1節，對C源程序的編譯步驟有基本的了解。其實ad-hoc的詞法解析一點也不比寫一個split()函數更複雜，尤其是開始的時候不必去記錄 Source Location(當然後面如果寫錯誤提示，可以再加進來)。實現的時候，也不要吝惜內存了，直接將所有的token一次解析掉存起來就好。因為這對於後面Parser要回溯的時候會方便一點。

6. 已經得到Token List 之後，就可以開始做Parser部分了。暫時不做錯誤恢復，即遇到錯誤即exit。這裡有一個很實用的設計建議：準備好下面這四個函數：

a. Peek() 返回下一個Token(只測試該Token，不向前移動Token List的offset指針)

b. Next() 消費下一個Token

c. Expect(expectedToken) , 這代替了下面的這段錯誤處理：

if (Peek() != expectedToken) { Error("expect %s, but got %s ", expectedToken, Peek()); }

d. Try(expectedToken), 這代替了下面這段代碼：

if (Peek() == expectedToken) { Next(); // 消費之 }

這很有用，因為Parser裡面可能會有上百個這段代碼，在我的Parser裡面，有84個Expect()調用，81個Peek()(Peek和Test), 39個Next()，62個Try()。相信我，這4個函數會讓你的代碼乾淨一倍。

7. C的語言組成，大致可以分為 Expression, Declaration, Statement and Block 三個部分。這裡面Statement and Block是最簡單的，Declaration難一點。按照我前面的心得體驗，應該從簡單的入手，但是我們非先做Declaration不可。因為Statements都是在函數內的啊，不搞定Declaration就沒法繼續了呢～其實，Declaration也好做，對著n1548的7.A.2.2節一個一個將grammar翻譯為Parser裡面的邏輯就好了(是的，除去語義和類型檢查，Parser就是這麼簡單)。做完Declaration，你還沒有往AST上添加任何node，是的，僅僅是Declaration，是沒有一行代碼需要生成的。所有的成就都在符號表裡面。這裡又有tip：暫時不要做Initializer，它有一點煩人的(C標準把它搞得好繁瑣)。

8. struct/union 類型；如果只是支持一個小小的子集，那麼大可以跳過這一部分不做。struct會引入一些工作量，一方面，需要為tag(tag 和普通的identifier不在同一個命名空間)另開一個符號表(我使用一個小trick避免了這個麻煩)；另一方面，它也是使Initializer變複雜的原因之一，尤其是匿名struct/union。tip：對struct/union的支持步驟是：普通嵌套的結構，匿名無tag的 struct成員，位域，union；這裡把union放到最後是因為，它和struct除去存儲布局之外，別無二致(所以你甚至不必區分這兩個類型)；你也可以在任何一步就開始支持union。

9. 數組和函數；除去作為sizeof關鍵字的操作數，數組總是會被cast成一個指針；你一定寫過這樣的代碼：

typedef void (*func_t)(void); func_t f = func; f(); // 難道不應該是 (*f)(); ?

其實函數也是被cast成指針了，所以上面的調用方式都對，更微妙的是，任何一個函數調用都會被先cast成指針，再解引用(至少我的實現是這樣的)；

10. storage 和 linkage；起初只實現所有的對象分配在棧空間；這會大大簡化代碼生成部分，因此對於「以最快速度看到hello world」是非常重要的；linkage對於前向聲明是重要的，如果你沒有打算支持，那麼也可以跳過，等你看到hello world再回來支持，或者等你的函數和標準庫的衝突了。

11. expression；這個最簡單，該怎麼樣就怎麼樣=-=。tip：聯合賦值運算符：

a *= 5; a = a * 5;

是不是總是被告知效果和下面那行效果相等？那麼不要害羞，就這麼翻譯！(嗯，這麼做是會產生bug（如果左值表達式有副作用），但是可以通過額外的檢查規避掉；對於帶優化的編譯器，這根本不是問題，因為它們怎麼會對公共子表達式求兩遍值呢？)

12. statement；這是我最喜歡的部分，不僅僅是因為它簡單，而且讓我明白那些控制語句是怎麼生成到彙編代碼的(對應請看龍書6.6和6.7節)；如最簡單的while循環的展開：

/* * while (expression) statement * 展開後： * cond: * if (expression) then * empty * else * goto end * statement * goto cond * end: */

這裡，我將 if 語句保留為基本的翻譯單元，因為將其他的控制結構翻譯為 if 語句會帶來很大的便利。tip:支持順序：if-else, while/do-while, for, switch-case;

這些基本是一個C語言Parser的動手步驟了，現在你可以parse這段代碼了：

int main() { puts("hello world "); return 0; }

你可以手動將 puts插入到符號表以應付過去(某些builtin的函數還真就是這麼乾的)，也可以在這個hello.c文件中聲明puts:

extern int puts(const char* str);

或者你就要實現對struct/union的支持，不然是沒有辦法 #include & 的了。這裡沒有使用 printf，因為暫時沒有必要實現變參函數。

這樣，你與hello world只有一步之遙了：彙編代碼生成。

// TODO(wgtdkp): 彙編代碼生成

// End of update_1

// Update_2

// Date: 09/21/2016

因為按照"以最快的速度看到hello world"來做的話，語義檢查和類型檢查可以暫且放一放，或者只是實現parse過程中必不可少的一部分。下面是以x86-64 彙編代碼生成為例，說說代碼生成。這裡又可以跳過中間代碼生成，直接由AST生成彙編代碼～

1. intel x86-64 手冊；顯然這是必需的，雖然我拿到這3000多頁的手冊時，也是虎軀一震的。不過，實實在在地講，我只看了大概30頁的內容；更多的時候，我是對照著gcc生成的彙編代碼照虎畫貓; tip：對於某些指令，如乘除法，移位，對照gcc進行翻譯是非常有效的；但你不應該企圖生成像gcc那麼高效的代碼！(具體方法見下面)

2. System V x64 ABI；你必須至少看chapter 3(chapter 3就夠用了，不過只有30多頁，放心吧)；至少掌握stack frame的結構和對齊。注意x86-64的調用規約會稍微複雜一點，不過你可以做一些大膽的簡化：

a. scalar type (除去struct/union,剩下的都是)按照 ABI裡面的就好；

b. struct/union 是比較複雜的，這裡可以直接按照stack傳參(而不是寄存器傳參去做)，畢竟又有多少代碼會直接傳遞struct/union 呢？等到你決意要做一個full featured的編譯器時，再來考慮它吧。

可以參考這裡Introduction to X86-64 Assembly for Compiler Writers

3. visitor 模式；相信這個不必贅述，取決於怎麼使用它，可以有很多作用；比如Parser中會需要做常量表達式求值，我們會用到它；獲得一個表達式的左值地址時，我們又需要用到它；(考慮你該如何翻譯賦值表達式)

4. 數據類型；在代碼生成這一步，我們的數據類型只有3種：整型，浮點型，struct/union(集合)；我將能夠用通用寄存器存儲的數據稱為整型，包括指針；struct/union的處理比較特殊，對於一個類型為struct/union的表達式，visit該表達式，總是得到此struct/union對象的地址值(存儲於%rax寄存器中)；只要我們在所有代碼中遵守這一規則，那麼它確實很管用，即使會有一些冗餘的拷貝；

5. 翻譯函數定義；一個函數的翻譯可以分為下面幾個步驟：

保存棧指針；
確定函數參數的位置(在哪個寄存器或者stack上的位置)，將它們複製到當前stack frame的上，更新每個參數(object)的offset成員(object的地址)。更新當前stack frame的偏移量；
確定當前作用域內的object的地址，這隻需要掃描當前scope內的所有object，併線性地分配到stack frame上面就好；注意不包括內層scope內定義的object。這是一種優化，能夠充分利用棧空間，而且實現更簡單。更新當前的stack frame偏移量。
翻譯函數體；
在return 語句和函數結尾處，恢復棧指針並退出函數；

6. 翻譯函數調用；也可以分為下面幾個步驟：

確定函數地址；這可能是函數的名字，也可能是一個寄存器；這裡就需要一個能夠計算表達式左值地址的 evaluator 了（後面會講到)；
對函數參數求值，暫存之(push到stack上)；
確定函數參數的位置，即，應該在哪個寄存器或stack的位置；拷貝參數值到對應位置；
調整棧指針以正確地對齊(這個很重要，不然會有segment fault的，都是淚)；
調用之～

7. 翻譯賦值表達式；對左值表達式的賦值，需要獲得左值表達式的地址，而不是值；因此我們需要一個 LValGenerator 來取得左值表達式的地址，然後將右操作數的值load到該地址中；

8. 翻譯表達式；建議採用1-TOSCA方法，不懂的可以看看R大的回答寄存器分配問題？ - 編譯器；這裡的tip：不要被gcc生成的各種高效代碼蠱惑了而去做大量的手動優化，那是一個很大的坑，尤其是我們沒有生成中間代碼，是做不到全局寄存器分配的效果的。

// End of update_2

用Haskell擼的C89解釋器。本來想控制在千行以內的，語法分析部分倒是只有三百多行，但是虛擬機的實現控制不住了（捂臉熊.jpg

另外我的變數起名是相當爛orz 狀態慣用名s, newS, newNewS, newNewNewS...

sqd/haskell-C89-interpreter · GitHub

現在類型系統還是一團糟...大概這幾天補完吧

類型系統補完啦

http://llvm-tutorial-cn.readthedocs.org/en/latest/index.html

你可以先看看這個_(:з」∠)_……llvm官方教程讓人翻譯成中文了……不過好像翻譯的不全，你自己可以看英文原版……嫌寫詞法分析語法解析程序麻煩可以找找lex+yacc的教程，網上到處都是，或者直接拿ply上……反正初學整那麼麻煩也沒啥意思

看了前面的答案，我都沒臉發我的 BlxScript 了 …… 簡直寫得太爛了。最後瀉藥 /w

先放 GayHub 的地址吧 GitHub - bramblex/BlxScript: 自己造的簡單腳本語言

因為我這裡都只寫了 Parser ，所以就只談談第一次寫 Parser 的建議。

1. 扔掉龍書虎書鯨魚書。這些書都有一個問題，就是在自己手寫完一個自己的 Parser 之前，書上寫的那些鬼東西完全都不知道該怎麼用，用在哪裡。

2. 大膽地擼。不要在意性能啊，擴展性，復用啊這些鬼東西，先把東西做出來再說。

3. 記住代碼只不過是格式化文本。不要覺得代碼是什麼複雜的東西，它跟 Json / XML 這些東西沒啥太大區別。Parser 的意義就是把人能看懂的格式化數據編程計算機能看懂的格式數據。

後端我自己都沒折騰好，等折騰好了再補上。 /w

給你個 tip：想實現宏展開的話，建議用文法閉包做，你會發現它比原版 KFFD 演算法簡單多了，但是依舊好用。

define-macro items-of : syntax-rules `[items-of @obj] : return `[let [t @obj] [[lambda [] [begin [local n t.length] [for [local i 0] (i &< n) (i = i + 1) [yield t.(i)]] ]]]]

http://github.com/larva-lang/larva-lang

我來一發我四不像lang的快排代碼以及編譯結果跟swift的速度對比

func printf(let fmt: *char, ...) -&> int;


func testInternal(let x: *char, y: int, z: double) {

    printf("argv[%d] = %s, %f

", y, x, z);

}
func test(let x: *char, y: int, fn: (let x: *char, y: int, z: double) -&> void) {

    fn(x, y, 10.0);

}
func dump(let xs: *int, let len: int) {

    printf("(");

    for (var i = 0; i &< len; ++i) {
        printf("%d", xs[i]);
        if (i + 1 != len) {
            printf(", ");
        }
    }
    printf(")
");
}

func _sort(xs: *int, let left: int, let right: int) {
    if (left &>= right) return;

    var i = left;

    var j = right;

    var key = xs[left];

    for (; i &< j; ) {
        for (; i &< j  key &<= xs[j]; j--);
        xs[i] = xs[j];
        for (; i &< j  key &>= xs[i]; i++);

        xs[j] = xs[i];

    }

    xs[i] = key;

    _sort(xs, left, i - 1);

    _sort(xs, i + 1, right);

}
func sort(xs: *int, let len: int) {

    _sort(xs, 0, len - 1);

}

func dumpArgs(argc: int, let argv: ** char) { for (var i = 0; i &< argc; ++i) { test(argv[i], i, testInternal); } } func main(argc: int, let argv: ** char) -&> int { dumpArgs(argc, argv); var xs: [int] = {42, 12, 88, 62, 63, 56, 1, 77, 88, 97, 97, 20, 45, 91, 62, 2, 15, 31, 59, 5}; let size = 20; dump(xs, size); sort(xs, size); dump(xs, size); return 0; }

後面是swift 快排

import Foundation func partition(inout dataList: [Int], low: Int, high: Int) -&> Int { var pivotPos = low let pivot = dataList[low]

for var i = low + 1; i &<= high; i++ { if dataList[i] &< pivot ++pivotPos != i { (dataList[pivotPos], dataList[i]) = (dataList[i], dataList[pivotPos]) } } (dataList[low], dataList[pivotPos]) = (dataList[pivotPos], dataList[low]) return pivotPos } func quickSort(inout dataList: [Int], left: Int, right: Int) { if left &< right { let pivotPos = partition(dataList, low: left, high: right) quickSort(dataList, left: left, right: pivotPos - 1) quickSort(dataList, left: pivotPos + 1, right: right) } } var dataList = [42, 12, 88, 62, 63, 56, 1, 77, 88, 97, 97, 20, 45, 91, 62, 2, 15, 31, 59, 5] print(dataList) quickSort(dataList, left: 0, right: dataList.count - 1) print(dataList)

編譯後比swift2.1開最高優化等級的結果速度基本一樣,

一萬個隨機數排序（swift版本編譯器掛了，沒法比了 2333）

LLVM官方自帶一個叫做kaleidoscope的教程，教你短時間內用LLVM擼一個玩具編譯器。

可以來看看這個，一步一步用 C 寫一個 Lisp : Strace.co

可以先從簡單的計算器出發

Brainfuck

其實編譯器的原理一點都不複雜。就兩部分，scanner和parser，前者附則tokenization後者負責parsing。

難點在於你怎樣設計你的語言。要想簡單，那就設計一個只能算加減乘除的計算機就是了。要想複雜...你去試著編譯一下scala...聽說官方編譯器編譯scala用了21步，我估計這應該是最複雜的編譯器了吧。

補充，忘了一步，就是最後的代碼生成。這一步簡單說，就是把parse完的代碼，變數stack，heap啥的處理一下，生產最終結果。

ANSI C grammar (Lex)

ANSI C grammar (Yacc)

這是c的文法和語法，在linux下裝上yacc和lex（flex），然後lex文件不需要改動，yacc文件需要增加一些語句來編譯。

然後你用yacc處理後可以得到一個c程序，編譯c程序就能完成簡單的c編譯器。

我當年編譯原理的那堆破銅爛鐵找不到了……不然應該還是能給點示範。。

作為一名本科生，當時學習編譯原理還是有點迷茫的，因為課本的知識總是偏向於理論。為了能夠加深對編譯原理的理解，當然要能夠實實在在的做出一個編譯器來。但是不是很推薦初學者一上來就寫C語言（或者C語言子集）的編譯器。

首先我推薦一個公開課項目NandToTetris這個公開課的大體內容就是從最基本的與非門和D觸發器開始，搭建一個簡單而又完整的「計算機」，這個公開課涉及面很廣，難度也不是很大，因此我在做完了這個項目之後，就到處安利(^_^)。

這個搭建計算機的過程就是先實現一個簡單的16位CPU，設計一種彙編語言Hack，然後實現一個簡單的編譯器，最後使用高級語言開發俄羅斯方塊的遊戲，這也是項目的名稱Nand To Tetris（從與非門到俄羅斯方塊）的來源。

如果對這個項目感興趣的話，可以做一做。Cousera上有兩部分內容 https://www.coursera.org/courses?languages=enquery=from+nand+to+tetris ，如果您覺的這還不好理解，還有一本配套中文翻譯教材，叫做計算機系統要素。

======言歸正傳======

有趣的是後半部分，從第七章到第十一章就是在講如何實現一個編譯器，這個編譯器的語言是一門經過巧妙的設計的類似Java的有點面向對象意味的編程語言。其中我們比較關注的是前端的實現（第10章和第11章），這裡生成的中間代碼也是經過巧妙設計的一種類似堆棧機的一種抽象機代碼的格式。

（上面涉及到的所有的語言格式，都會在NandToteris相關公開課以及材料中找到詳細說明。）

因此，我首先按照課程的內容實現了一個編譯器的前端大概800行核心代碼左右（可以暫時忽略各種錯誤處理，類型檢查等等）。然後用200行左右寫一個虛擬機模擬器，主要用途就是對前端的實現進行調試。

以上所有內容都依賴於NandTotetris項目的後半部分內容，基本不需要太多的理論基礎。

=============================

當確保了前端實現沒有問題之後，就開始著手實現後端，原來的項目後端的目標是一種叫做hack的彙編語言，這種彙編語言運行在我們自己實現的CPU上，但是如果想移植到x86平台上，就得將類似堆棧機的中間代碼翻譯成x86彙編，推薦ATT格式。

這一部分需要一點點x86彙編的基礎，其實只要認真閱讀完《CSAPP》的第三章就夠了。

然後最基礎的函數比如IO操作可以採用unix的系統調用int指令實現，但是這裡我偷懶了直接使用的C語言的部分標準庫函數，malloc，free，putchar，getchar，這四個最基本的函數（基本原理就是鏈接的時候鏈接到一起就好了）。

剩下的過程，除了注意個別寄存器的使用之外，基本都是照著翻譯了。

=============================

最後生成了ATT的彙編，使用gcc的as彙編器以及ld鏈接器就能生成可執行文件了。

這個是我的一個C++版本的實現，目前前後端是分離的，最後拿Python粘了一下就開始使用了。=.=

以上信息僅僅是我學習編譯原理過程中的一些經驗總結，希望對初學者有所幫助，也歡迎一起交流 (^_^)

3先感謝@Leviathan

鏈接

編譯器https://github.com/Xiang1993/jack-compiler

正則引擎https://github.com/Xiang1993/My-RegexEngine

可以先看看readme裡面的幾個Demo

說下過程:

首先我是在網易雲課堂上報了華老師的編譯原理課，然後在qq群里看到了@Laviathan寫了個編譯器和正則引擎，一看鏈接，就知道這貨是1995年出生的，比我還小兩歲，我就不服了，我下定決心我也要寫個正則引擎和編譯器！

於是我就開了個github賬號，就連賬號名也是模仿他的！

主要還是華老師講得非常好，深入淺出，不啰嗦，很容易理解！

華老師布置的作業很棒，很有引導性作用。

認真學完前面的詞法分析和語法分析部分之後，再把老師布置的作業做完，我對詞法分析和語法分析就有了一定的理解，然後再在考試提供的作業代碼的基礎上做一些擴展，一個正則引擎就寫好了！

寫正則引擎我花了大概5天時間

學完了華老師的課程之後，我就買了本《編譯原理與實踐》，這裡面有用c語言寫的一個很小的編譯器，書裡面還有個擴展項目，我是打算把這個項目做一下的，把詞法和語法分析寫得差不多了之後，感覺很多地方不夠完善，越寫越亂，就暫時放下了！

到暑假的時候，我買了本《計算機系統要素》，這本書裡面有一個jack編譯器項目以及虛擬機項目，我覺得這個jack語言有很多有趣的功能，最大的特點就是支持面向對象特性了

雖然這本書並沒有提供完整的代碼實現，指導內容頁不到30頁，但是書上提供了語言的完整規範以及測試數據

但是我還是覺得書裡面的有些語法不符合我的要求，就重新整理了一下，然後再寫出BNF，再結合之前學的編譯原理的知識，花了我暑假一個月的時間，終於算是完成了！

當然，只有一些基本的功能，還存在很多bug。當時剛學c++，代碼寫得比較亂，我現在都不忍心看了！

總之，編譯器很難，一般人只能當做興趣研究研究，也許花了很多時間都不見得有什麼太大的收穫。想做真正的編譯器開發，不是一般人能做的！

個人認為最簡單的方式就是使用Flex（Lex改版）+Bison（yacc改版）+LLVM實現。

希望語法嚴格就學LLVM官方教程裡面的編譯器實現做法，或者這篇文章（使用Flex Bison 和LLVM編寫自己的編譯器）中教的方法，自己用C++實現一套語法樹，裡面寫好各個語法結構的具體實現，進行代碼生成工作。

如果希望語法靈活一些，可以參考我設計的一套宏翻譯驅動模式：編譯器架構的王者LLVM——（6）多遍翻譯的宏翻譯系統

其實就目前的技術條件來說，編譯器開發及新語言開發入門門檻已經降低太多了，編譯器前端詞法分析、語法分析有Flex+Bison實現，後端優化又有強大的LLVM框架實現，編譯器開發者只需要根據自己語言的需要，定製個性化的語法，調用LLVM的介面即可。當然，要熟悉LLVM-IR還是需要一定的耐心的，否則代碼生成後不易調試。

Brainfuck 簡單，但是是圖靈完備的計算機語言

https://github.com/mono/llvm/tree/master/examples/BrainF 這是它的LLVM實現

既然是初學編譯原理，那就別著急，大作業就完全由自己獨立完成，不懂的地方多問。

如果你是自學，都自學了，那就規規矩矩沿著書走下來，書上的習題別偷懶。