1、介紹

我總是對編譯器和語言非常感興趣，但是興趣并不會讓你走的更遠。大量的編譯器的設計概念可以搞的任何一個程序員迷失在這些概念之中。不用說，我也曾 今嘗試過，但是并沒有取得太大的成功，我以前的嘗試都停留在語義分析階段。本文的靈感主要來源于我最近一次的嘗試，并且在這一次中我取得一點成就。

幸運的是，最近的幾年，我參加了一些項目，這些項目給了我在建立編譯器上很多有用的經驗和觀點。另外一件事是，我非常幸運得到LLVM的幫助。對于這個工具，我不知道改怎么去形容它，但是他給我的這個編譯器的確帶來非常大的幫助。

1.1、你為什么要閱讀本文

你也許想看看我正在做的事情，但是更有可能的是，你也是和我一樣對編譯器和語言非常感興趣，并且也可能遇到了一些在探索的過程中遇到了一些難題，你 可能正打算解決這些難題，但是卻沒有發現好的資源。本文的目標就是提供這些資源，并以一種手把手的方式教你從頭到尾的去創建一個具有基本功能的語言編譯 器。

在本文，我不會去解釋一些編譯器基本理論，所以你要在開始本文前去了解什么是BNF語法，什么是抽象語法樹數據結構 AST data structure，什么是基礎編譯器流水線 complier pipline。就是說，我會把本文描述的盡量簡單。本文的目的就是以一種簡單易懂的方式來介紹相關編譯器資源的方式來幫助那些從來沒有編譯器經驗的人。

1.2、達到的成果

如果你根據文章內容一步步來，你將會得到一個能定義函數，調用函數，定義變量，給變量賦值執行基本數學操作的語言。這門語言支持兩種基本類 型，double和integer類型。還有一些功能還未實現，因此，你可以通過自己去實現這些功能得到你滿意的功能并且能為你理解編寫一個編譯器提供不 少的幫助。

1.3 問題解答

1.3.1 我需要了解什么樣的語言

我們使用的工具是基于C/C++的。LLVM是基于C++的，我們的這個語言也基于C++，因為C++具有很多面向對象的優點和可以被重用的 STL。此外對于C，Lex和Bison都具有那些初看起來令人迷惑的語法，但是我將盡可能的去解釋他。我們需要處理的語法非常小，最多就100行，因此 它是比較容易理解的。

1.3.2 很復雜嗎？

是或否，這里面有很多的東西你需要了解，甚至多的讓人感覺到害怕，但是老實說，其實這些都非常簡單，我們同樣會使用很多工具分解這些層次的復雜性，并使得這些內容可管理。

1.3.3 完成它需要多長時間

我們將要完成的編譯器花了我三天的時間。但是如果你按“follow me”的方式來完成這個編譯器的話，你將會花費更少的時間。如果要全部理解這里面的內容可能會花去稍微長一點的時間，但是你至少應該在一個下午就將整個編譯器運行起來。

好，如果你已經準備好，我們開始吧。

2、準備開始

2.1 構成編譯器的最基本的要素

一個編譯器是由一組有三個到四個組件(還有一些子組件)構成，數據以管道的方式從一個組件輸入并流向下一個組件。在我們這個編譯器中，可能會用到一些稍微不同的工具。下面這個圖展示了我們構造一個編譯器的步驟，和每個步驟中將使用的工具。

從上圖你可以看到在Linking這一步是灰掉的。我們的語言將不支持編譯器的連接(很多的語言都不支持編譯器的連接)。在文法分析階段，我們將使用開源工具Lex，即如今的Flex，文法分析一般都伴隨者語法分析，我們使用的語法分析工具將會是Yacc，或者說是Bison，最后一旦語義分析完成，我們將遍歷我們的抽象語法樹，并生成我們的”bytecode 字節碼”，或”機器碼 matchine code”。做這一步，我們將使用LLVM，它能生成快速字節碼，我們將使用LLVM的JIT(Just In Tinme)來在我們的機器上編譯執行它

總結一下，步驟如下：

1. 文法分析用Flex:將數據分隔成一個個的標記token (標示符identifiers，關鍵字keywords，數字numbers, 中括號brackets, 大括號braces, 等等etc.)
2. 語法分析用Bison: 在分析標記的時候生成抽象語法樹. Bison 將會做掉幾乎所有的這些工作, 我們定義好我們的抽象語法樹就OK了.
3. 組裝用LLVM: 這里我們將遍歷我們的抽象語法樹，并未每一個節點生成字節/機器碼。 這聽起來似乎很瘋狂，但是這幾乎就是最簡單的 一步了.

在我們開始下一步之前，你應該準備安裝好Flex,Bison和LLVM。因為我們馬上就要使用到它們。

2.2 定義我們的語法

我們語法是我們語言中最核心的部分，我們的語法使用類似標準C的語法，因為這樣的語法非常熟悉，而且簡單。我們語法的一個典型的例子如下：

看起來很簡單。它和C非常相似，但是它沒有使用分號做語句的分隔，同時你也會注意到我們的語法中沒有return語句。這就是你可以自己實現的部分。

現在我們還沒有任何機制來驗證結果。我們將通過檢查我們編譯之后LLVM打印出的字節碼驗證我們程序的正確性。

3、 第一步，使用Flex進行文法分析

這是最簡單的一步，給定語法之后，我們需要將我們的輸入轉換一系列內部標記token。如前所述，我們的語法具有非常基礎的標記token:標示符 identifier ，數字常量(整型和浮點型)，數學運算符號，括號，中括號，我們的文法定義文件稱為token.l，它具有一些固定的語法。定義如下：

%{
#include 
#include "node.h"
#include "parser.hpp"
#define SAVE_TOKEN yylval.string = new std::string(yytext, yyleng)
#define TOKEN(t) (yylval.token = t)
extern "C" int yywrap() { }
%}

%%

[ \t\n]                 ;
[a-zA-Z_][a-zA-Z0-9_]*  SAVE_TOKEN; return TIDENTIFIER;
[0-9]+\.[0-9]*          SAVE_TOKEN; return TDOUBLE;
[0-9]+                  SAVE_TOKEN; return TINTEGER;
"="                     return TOKEN(TEQUAL);
"=="                    return TOKEN(TCEQ);
"!="                    return TOKEN(TCNE);
"<"                     return TOKEN(TCLT);
"<="                    return TOKEN(TCLE);
">"                     return TOKEN(TCGT);
">="                    return TOKEN(TCGE);
"("                     return TOKEN(TLPAREN);
")"                     return TOKEN(TRPAREN);
"{"                     return TOKEN(TLBRACE);
"}"                     return TOKEN(TRBRACE);
"."                     return TOKEN(TDOT);
","                     return TOKEN(TCOMMA);
"+"                     return TOKEN(TPLUS);
"-"                     return TOKEN(TMINUS);
"*"                     return TOKEN(TMUL);
"/"                     return TOKEN(TDIV);
.                       printf("Unknown token!\n"); yyterminate();

%%

在第一節(譯者注：即%{%}中定義的部分)聲明了一些特定的C代碼。由于Bison不會去訪問我門的yytext變量，我們使用 宏”SAVE_TOKEN”來保證標示符的文本和文本長度是安全的(而不是靠標記本身來保證)。第一個token告訴我們要忽略掉那些空白字符。你會注意 到我們有些一些等價性比較的標記和其他。還有一些標記還沒有實現，你可以非常自由的將這些標記加到你自己的編譯器中去。

現在我們在這里做的是定義這些標記和他們的符號名。符號(比如TIDENTFIER)將成為我們語法中的終結符。我們只是返回它，我們從未定義它， 他們是在什么地方定義的？當然是在bison語法文件中。我們包含的parser.hpp頭文件將會被bison所生成，并且里面的所有符號都將被生成， 并被我們在這里使用。

我們對這個token.l運行flex命令，并生成tokens.cpp文件，這個程序將會和我們的語法分析器一起編譯并提供yylex()函數來識別這些標記。我們將在稍后運行這個命令，因為現在我們需要從bison那里生成頭文件。

4、第2步 使用Bison進行語法分析

這是我們工作中最富有挑戰性的一部分。生成一個正確的無二義的語法并不是一項簡單的工作，要經過很多實踐努力。慶幸的是，我們例子中的語法是簡單而完整的。在我們實現我們的語法之前，我們需要詳細的講解一下我們的設計。

4.1、設計AST(抽象語法樹)

語法分析的最終結果是抽象語法樹AST，正如我們將看到的，Bison生成抽象語法樹的最優工具；我們唯一需要做的事情就是將我們的代碼插入到語法中去。

文本形式字符串，例如”int x”代表了我們語言的文本形式，和這個類似，抽象語法樹AST則代表了我們語言在內存中的表現形式一樣(在語言在組裝成而進程碼之前)。正因如此，我們要 在把這些插入在語法分析中的數據結構首先設計好。這個過程是非常直接的，因為我們為語法中的每個語義單元創建了一個結構。方法聲明、方法調用，變量聲明， 引用，這些都構成了抽象語法樹的節點。我們語言的抽象語法樹的節點如下圖：

上圖的C++代碼如下：
node.h文件

非常的清晰明了，我們省略了getter和setter方法，這里只列出了共有成員；這些類也不需要影藏私有數據，并省略了codeGen方法。在我們導出AST成LLVM的字節碼時，就需要使用到這個方法。

4.2、Bison介紹

bison的語法定義文件同樣是由這些標記構成的最復雜的部分。這并不是說技術上有多復雜，但是我也會花一些時間來討論一下Bison的語法細節， 好，現在讓我們立刻來熟悉一下Bison的語法。我們將使用基于類似于BNF的語法，使用定義的好終結符和非終結符來組成我們有效的每一個語句和表達式 (這些語句和表達式就代表我們之前定義的AST節點)。例如：

if_stmt : IF '(' condition ')' block { /* do stuff when this rule is encountered */ }
        | IF '(' condition ')'       { ... }
        ;

在上面例子中，我們定義了一個if語句(如果我們支持if語句話)，它和BNF不同之處在于，每個語法后面都跟了一系列動作(在’{‘和’}'之間 的內容)。這個動作將在此條語法被識別(譯者注：歸約)的時候被執行。這個過程將會遞歸地按從葉子符號到根節點符號的次序執行，在這個過程，每一個非終結 符最終會被合并為一棵大的語法樹。你將會看到的’$$’符號代表著當前樹的跟節點(譯者注：’$$’代表本條語法規則中冒號左邊的部分的語義內容)。此 外’$1′代表了本條規則葉子中的第一個符號(譯者注：’$1′代表了本條語法規則冒號右邊的內容，$1代表冒號右邊的第一個符號的語義值)。在上面的例 子中，當’condition’有效時我們將會把$3 賦值給$$。這個例子可以解釋如何將我們AST和語法規則關聯起來。我們將在每一條規則中通常賦值一個節點到$$，最后這些規則會合并成一個大的抽象語法 樹。Bison的部分是我們語言最復雜的部分，你需要花一點時間去理解它。此外到此為止，你還沒有看到完整的代碼。下面就是完整的Bison部分的代碼：
parser.y

%{
    #include "node.h"
    NBlock *programBlock; /* the top level root node of our final AST */

    extern int yylex();
    void yyerror(const char *s) { printf("ERROR: %s\n", s); }
%}

/* Represents the many different ways we can access our data */
%union {
    Node *node;
    NBlock *block;
    NExpression *expr;
    NStatement *stmt;
    NIdentifier *ident;
    NVariableDeclaration *var_decl;
    std::vector *varvec;
    std::vector *exprvec;
    std::string *string;
    int token;
}

/* Define our terminal symbols (tokens). This should
   match our tokens.l lex file. We also define the node type
   they represent.
 */
%token  TIDENTIFIER TINTEGER TDOUBLE
%token  TCEQ TCNE TCLT TCLE TCGT TCGE TEQUAL
%token  TLPAREN TRPAREN TLBRACE TRBRACE TCOMMA TDOT
%token  TPLUS TMINUS TMUL TDIV

/* Define the type of node our nonterminal symbols represent.
   The types refer to the %union declaration above. Ex: when
   we call an ident (defined by union type ident) we are really
   calling an (NIdentifier*). It makes the compiler happy.
 */
%type  ident
%type  numeric expr
%type  func_decl_args
%type  call_args
%type  program stmts block
%type  stmt var_decl func_decl
%type  comparison

/* Operator precedence for mathematical operators */
%left TPLUS TMINUS
%left TMUL TDIV

%start program

%%

program : stmts { programBlock = $1; }
        ;

stmts : stmt { $$ = new NBlock(); $$->statements.push_back($1); }
      | stmts stmt { $1->statements.push_back($2); }
      ;

stmt : var_decl | func_decl
     | expr { $$ = new NExpressionStatement(*$1); }
     ;

block : TLBRACE stmts TRBRACE { $$ = $2; }
      | TLBRACE TRBRACE { $$ = new NBlock(); }
      ;

var_decl : ident ident { $$ = new NVariableDeclaration(*$1, *$2); }
         | ident ident TEQUAL expr { $$ = new NVariableDeclaration(*$1, *$2, $4); }
         ;

func_decl : ident ident TLPAREN func_decl_args TRPAREN block
            { $$ = new NFunctionDeclaration(*$1, *$2, *$4, *$6); delete $4; }
          ;

func_decl_args : /*blank*/  { $$ = new VariableList(); }
          | var_decl { $$ = new VariableList(); $$->push_back($1); }
          | func_decl_args TCOMMA var_decl { $1->push_back($3); }
          ;

ident : TIDENTIFIER { $$ = new NIdentifier(*$1); delete $1; }
      ;

numeric : TINTEGER { $$ = new NInteger(atol($1->c_str())); delete $1; }
        | TDOUBLE { $$ = new NDouble(atof($1->c_str())); delete $1; }
        ;

expr : ident TEQUAL expr { $$ = new NAssignment(*$1, *$3); }
     | ident TLPAREN call_args TRPAREN { $$ = new NMethodCall(*$1, *$3); delete $3; }
     | ident { $$ = $1; }
     | numeric
     | expr comparison expr { $$ = new NBinaryOperator(*$1, $2, *$3); }
     | TLPAREN expr TRPAREN { $$ = $2; }
     ;

call_args : /*blank*/  { $$ = new ExpressionList(); }
          | expr { $$ = new ExpressionList(); $$->push_back($1); }
          | call_args TCOMMA expr  { $1->push_back($3); }
          ;

comparison : TCEQ | TCNE | TCLT | TCLE | TCGT | TCGE
           | TPLUS | TMINUS | TMUL | TDIV
           ;

%%

5、生成Flex和Bison代碼

現在我們有了Flex的token.l文件和Bison的parser.y文件。我們需要將這兩個文件傳遞給工具，并由工具來生成c++代碼文件。 注意Bison同時會為Flex生成parser.hpp頭文件；這樣做是通過-d開關實現的，這個開關是的我們的標記聲明和源文件分開，這樣就是的我們 可以讓這些token標記被其他的程序使用。下面的命令創建parser.cpp，parser.hpp和tokens.cpp源文件。

$ bison -d -o parser.cpp parser.y
$ lex -o tokens.cpp tokens.l

如果上述工作都沒有出錯的話，我們現在位置已經完成了我們編譯器工作總量的2/3。如果你現在想測試一下我們的代碼，你可以編譯一個簡單的main.cpp程序：

你可以編譯這些文件：
$ g++ -o parser parser.cpp tokens.cpp main.cpp
現在你需要安裝LLVM了，因為llvm::Value被node.h引用了。如果你不想這么做，只是想測試一下Flex和Bison部分，你可以注釋掉node.h中codeGen()方法。

如果上述工作都完成了，你現在將有一個語法分析器，這個語法分析器將從標準輸入讀入，并打出在內存中代表抽象語法樹跟節點的內存非零地址。

6、組裝AST和LLVM

編譯器的下一步很自然地是應該將AST轉換成機器碼。這意味著將每一個語義節點轉換成等價的機器指令。LLVM將幫助我們把這步變得非常簡單，因為LLVM將真實的指令抽象成類似AST的指令。這意味著我們真正要做的事就是將AST轉換成抽象指令。
你可以想象這個過程是從抽象語法樹的根節點開始遍歷每一個樹上節點并產生字節碼的過程。現在就是使用我們在Node中定義的codeGen方法的時候了。 例如，當我們遍歷NBlock代碼的時候(語義上NBlock代表一組我們語言的語句的集合)，我們將調用列表中每條語句的codeGen方法。上面步驟 代碼類似如下的形式：

我們將實現抽象語法樹上所有節點的codeGen方法，然后在向下遍歷樹的時候調用它，并隱式的遍歷我們整個抽象語法樹。在這個過程中，我們在CodeGenContext類來告訴我們生成字節碼的位置。

6.1、關于LLVM要注意的一些信息

LLVM最大的一個確定就是，你很難找到LLVM的相關文檔。在線手冊、教程、或其他的文檔都沒有及時的得到相關維護，這些文檔大部分都是過期的文檔。除非你去深入研究，否則你很難找到關于C++ API的信息。如果你自己安裝LLVM，docs
是最新的文檔。

我發現最好學習LLVM的方法就是通過LLVM的例子去學習。在LLVM的壓縮包的’example’目錄下有很多快速生成字節碼的例子。在LLVM demo site上可以將C做輸入，然后生成C++ API的例子。以這些例子提供的方法，我找到了類似于int x = 5 ;的指令的生成方法。我使用這些工具實現大部分的節點。

關于LLVM的問題描述到此為止，我將在下面羅列出codegen.h和codegen.cpp的源代碼

codegen.h的內容。

codegen.cpp的內容。

上述羅列很多的代碼，然而這部份代碼的含義需要你自己去探索。我在這里只會提及一下你需要注意的內容：

• 我們在CodeGenContext類中使用一個語句塊的棧來保存最后進入的block(因為語句都被增加到blocks中)
• 我們同樣用個堆棧來保存每組語句塊中的符號表
• 我們設計的語言只會知道他當前范圍內的內容.要支持“全局”上下的做法，你必須向上搜索整個堆棧中每一個語句塊，知道你最后發現你匹配的符號(現在我們只是簡單地搜索堆棧中最頂層的符號表)。
• 在我們進入一個語句塊之前，我們需要將語句塊壓棧，離開語句塊時將語句塊出棧

剩下的內容都LLVM相關了，在這個主題上我并不是專家。但是迄今為止，我們已經有了編譯和運行我們語言的所有代碼。

7、編譯和運行我們的語言

7.1、編譯我們的語言

我們已經有了代碼，現在我們怎么運行它？LLVM有著非常復雜的聯接link，幸運的是，如果你是自己安裝的LLVM，那么你就應該有一個llvm-config二進制程序，這個程序返回你需要的所有編譯和聯接選項。
我們也要同時更新我們的main.cpp的內容使之可以編譯和運行我們的代碼，這次我們main.cpp的內容如下：

現在我們需要這樣來編譯這些代碼
$ g++ -o parser `llvm-config –libs core jit native –cxxflags –ldflags` *.cpp
你也可以編寫一個Makefile來進行編譯

all: parser

clean:
	rm parser.cpp parser.hpp parser tokens.cpp

parser.cpp: parser.y
	bison -d -o $@ $^

parser.hpp: parser.cpp

tokens.cpp: tokens.l parser.hpp
	lex -o $@ $^

parser: parser.cpp codegen.cpp main.cpp tokens.cpp
	g++ -o $@ `llvm-config --libs core jit native --cxxflags --ldflags` *.cpp

7.2、運行我們的語言

假設上述所有工作都圓滿完成，那么現在你將有一個名為parser的二進制程序。運行它，還記得我們那個典型例子嗎？讓我們看看我們的編譯器工作的如何。

$ echo 'int do_math(int a) { int x = a * 5 + 3 } do_math(10)' | ./parser
0x100a00f10
Generating code...
Generating code for 20NFunctionDeclaration
Creating variable declaration int a
Generating code for 20NVariableDeclaration
Creating variable declaration int x
Creating assignment for x
Creating binary operation 276
Creating binary operation 274
Creating integer: 3
Creating integer: 5
Creating identifier reference: a
Creating block
Creating function: do_math
Generating code for 20NExpressionStatement
Generating code for 11NMethodCall
Creating integer: 10
Creating method call: do_math
Creating block
Code is generated.
; ModuleID = 'main'

define internal void @main() {
entry:
	%0 = call i64 @do_math(i64 10)		;  [#uses=0]
	ret void
}

define internal i64 @do_math(i64) {
entry:
	%a = alloca i64		;  [#uses=1]
	%x = alloca i64		;  [#uses=1]
	%1 = add i64 5, 3	;  [#uses=1]
	%2 = load i64* %a	;  [#uses=1]
	%3 = mul i64 %2, %1	;  [#uses=1]
	store i64 %3, i64* %x
	ret void
}
Running code...
Code was run.

8、結論

是不是非常的酷？我同意如果你只是從這篇文章中拷貝粘貼的話，你可能會對運行得到的結果感覺有點失望，但是這點結果可能也會激發你更大的興趣。此 外，這就是本文的意義，這不是本篇指導文章的結束，這只是一個開始。因為有了這篇文章的介紹，你可以在文法分析，語法分析和裝配語言的時候附加上一些瘋狂 的特性，然后創造出一個你自己命名的語言。你現在已經可以編譯語句塊了，那么你現在應該已經有如何繼續下去的基本想法。
本文完整的代碼在Github這里。我一直都在避免提到這個代碼，因為這個代碼不是本文的重點，而僅僅是帶過這部分代碼。

我意識到這是一篇非常長的文章，并且這篇文章中難免會有出錯的地方，如果你找到了任何問題，在你覺得有空的時候，歡迎你給我發電子郵件，我將會調整我的文章。你如果向想我們共享一些信息，你也可以在你覺得有空的時候寫信給我們。

轉自：http://coolshell.cn/articles/1547.html

英文原文：http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/