兔子的技術(shù)博客

1、介紹

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

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

1.1、你為什么要閱讀本文

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

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

1.2、達到的成果

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

1.3 問題解答

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

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

1.3.2 很復(fù)雜嗎？

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

1.3.3 完成它需要多長時間

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

好，如果你已經(jīng)準備好，我們開始吧。

2、準備開始

2.1 構(gòu)成編譯器的最基本的要素

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

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

總結(jié)一下，步驟如下：

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

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

2.2 定義我們的語法

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

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

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

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

這是最簡單的一步，給定語法之后，我們需要將我們的輸入轉(zhuǎn)換一系列內(nèi)部標記token。如前所述，我們的語法具有非常基礎(chǔ)的標記token:標示符 identifier ，數(shù)字常量(整型和浮點型)，數(shù)學(xué)運算符號，括號，中括號，我們的文法定義文件稱為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();

%%

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

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

我們對這個token.l運行flex命令，并生成tokens.cpp文件，這個程序?qū)臀覀兊恼Z法分析器一起編譯并提供yylex()函數(shù)來識別這些標記。我們將在稍后運行這個命令，因為現(xiàn)在我們需要從bison那里生成頭文件。

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

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

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

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

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

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

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

4.2、Bison介紹

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

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

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

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

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

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

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

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

6、組裝AST和LLVM

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

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

6.1、關(guān)于LLVM要注意的一些信息

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

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

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

codegen.h的內(nèi)容。

codegen.cpp的內(nèi)容。

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

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

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

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

7.1、編譯我們的語言

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

現(xiàn)在我們需要這樣來編譯這些代碼
$ 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、運行我們的語言

假設(shè)上述所有工作都圓滿完成，那么現(xiàn)在你將有一個名為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、結(jié)論

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

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

轉(zhuǎn)自：http://coolshell.cn/articles/1547.html

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