本文由趙锟翻譯，酷殼釋出，轉載請注明譯者和出處，請勿用于商業用途
原文出處：http://gnuu.org/2009/09/18/writing-your-own-toy-compiler
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的文法，因為這樣的文法非常熟悉，而且簡單。我們文法的一個典型的例子如下：
檢視源代碼
列印幫助
1.int
do_math(int
a) {
2. int
x = a * 5 + 3
3.}
4.
5.do_math(10)
看起來很簡單。它和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檔案
#include <iostream>
#include <vector>
#include <llvm/Value.h>
class
CodeGenContext;
class NStatement;
class
NExpression;
class NVariableDeclaration;
typedef std::vector<NStatement*> StatementList;
typedef
std::vector<NExpression*> ExpressionList;
typedef std::vector<NVariableDeclaration*> VariableList;
class Node {
public
:
virtual ~Node() {}
virtual
llvm::Value* codeGen(CodeGenContext& context) { }
};
class NExpression : public Node {
};
class
NStatement :
public
Node {
};
class NInteger : public NExpression {
public
:
long
long
value;
NInteger(
long
long
value) : value(value) { }
virtual llvm::Value* codeGen(CodeGenContext& context);
};
class
NDouble :
public
NExpression {
public:
double
value;
NDouble(
double
value) : value(value) { }
virtual
llvm::Value* codeGen(CodeGenContext& context);
};
class NIdentifier : public NExpression {
public
:
std::string name;
NIdentifier(
const
std::string& name) : name(name) { }
virtual llvm::Value* codeGen(CodeGenContext& context);
};
class
NMethodCall :
public
NExpression {
public:
const
NIdentifier& id;
ExpressionList arguments;
NMethodCall(
const
NIdentifier& id, ExpressionList& arguments) :
id(id), arguments(arguments) { }
NMethodCall(
const
NIdentifier& id) : id(id) { }
virtual llvm::Value* codeGen(CodeGenContext& context);
};
class
NBinaryOperator :
public
NExpression {
public:
int
op;
NExpression& lhs;
NExpression& rhs;
NBinaryOperator(NExpression& lhs,
int
op, NExpression& rhs) :
lhs(lhs), rhs(rhs), op(op) { }
virtual llvm::Value* codeGen(CodeGenContext& context);
};
class
NAssignment :
public
NExpression {
public:
NIdentifier& lhs;
NExpression& rhs;
NAssignment(NIdentifier& lhs, NExpression& rhs) :
lhs(lhs), rhs(rhs) { }
virtual
llvm::Value* codeGen(CodeGenContext& context);
};
class NBlock : public NExpression {
public
:
StatementList statements;
NBlock() { }
virtual llvm::Value* codeGen(CodeGenContext& context);
};
class
NExpressionStatement :
public
NStatement {
public:
NExpression& expression;
NExpressionStatement(NExpression& expression) :
expression(expression) { }
virtual llvm::Value* codeGen(CodeGenContext& context);
};
class
NVariableDeclaration :
public
NStatement {
public:
const
NIdentifier& type;
NIdentifier& id;
NExpression *assignmentExpr;
NVariableDeclaration(const NIdentifier& type, NIdentifier& id) :
type(type), id(id) { }
NVariableDeclaration(const NIdentifier& type, NIdentifier& id, NExpression *assignmentExpr) :
type(type), id(id), assignmentExpr(assignmentExpr) { }
virtual llvm::Value* codeGen(CodeGenContext& context);
};
class
NFunctionDeclaration :
public
NStatement {
public:
const
NIdentifier& type;
const NIdentifier& id;
VariableList arguments;
NBlock& block;
NFunctionDeclaration(
const
NIdentifier& type,
const
NIdentifier& id,
const VariableList& arguments, NBlock& block) :
type(type), id(id), arguments(arguments), block(block) { }
virtual llvm::Value* codeGen(CodeGenContext& context);
};
非常的清晰明了，我們省略了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程式：
#include <iostream>
#include "node.h"
extern NBlock* programBlock;
extern
int
yyparse();
int
main(
int
argc,
char
**argv)
{
yyparse();
std::cout << programBlock << endl;
return 0;
}
你可以編譯這些檔案：
$ 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方法。上面步驟代碼類似如下的形式：
Value* NBlock::codeGen(CodeGenContext& context)
{
StatementList::const_iterator it;
Value *last = NULL;
for (it = statements.begin(); it != statements.end(); it++) {
std::cout <<
"Generating code for "
<< typeid(**it).name() << endl;
last = (**it).codeGen(context);
}
std::cout <<
"Creating block"
<< endl;
return last;
}
我們将實作抽象文法樹上所有節點的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的内容。
#include <stack>
#include <llvm/Module.h>
#include <llvm/Function.h>
#include <llvm/PassManager.h>
#include <llvm/CallingConv.h>
#include <llvm/Bitcode/ReaderWriter.h>
#include <llvm/Analysis/Verifier.h>
#include <llvm/Assembly/PrintModulePass.h>
#include <llvm/Support/IRBuilder.h>
#include <llvm/ModuleProvider.h>
#include <llvm/ExecutionEngine/GenericValue.h>
#include <llvm/ExecutionEngine/JIT.h>
#include <llvm/Support/raw_ostream.h>
using namespace llvm;
class NBlock;
class CodeGenBlock {
public:
BasicBlock *block;
std::map<std::string , Value*> locals;
};
class CodeGenContext {
std::stack<codegenblock *> blocks;
Function *mainFunction;
public:
Module *module;
CodeGenContext() { module = new Module(
"main"
); }
void generateCode(NBlock& root);
GenericValue runCode();
std::map<std::string , Value*>& locals() { return blocks.top()->locals; }
BasicBlock *currentBlock() { return blocks.top()->block; }
void pushBlock(BasicBlock *block) { blocks.push(new CodeGenBlock()); blocks.top()->block = block; }
void popBlock() { CodeGenBlock *top = blocks.top(); blocks.pop(); delete top; }
};
codegen.cpp的内容。
#include "node.h"
#include "codegen.h"
#include "parser.hpp"
using namespace std;
void CodeGenContext::generateCode(NBlock& root)
{
std::cout <<
"Generating code...\n"
;
vector<const type*> argTypes;
FunctionType *ftype = FunctionType::get(Type::VoidTy, argTypes, false);
mainFunction = Function::Create(ftype, GlobalValue::InternalLinkage,
"main"
, module);
BasicBlock *bblock = BasicBlock::Create(
"entry"
, mainFunction, 0);
pushBlock(bblock);
root.codeGen(*this);
ReturnInst::Create(bblock);
popBlock();
std::cout <<
"Code is generated.\n"
;
PassManager pm;
pm.add(createPrintModulePass(&outs()));
pm.run(*module);
}
GenericValue CodeGenContext::runCode() {
std::cout <<
"Running code...\n"
;
ExistingModuleProvider *mp = new ExistingModuleProvider(module);
ExecutionEngine *ee = ExecutionEngine::create(mp, false);
vector<genericvalue> noargs;
GenericValue v = ee->runFunction(mainFunction, noargs);
std::cout <<
"Code was run.\n"
;
return v;
}
static const Type *typeOf(const NIdentifier& type)
{
if (type.name.compare(
"int"
) == 0) {
return Type::Int64Ty;
}
else if (type.name.compare(
"double"
) == 0) {
return Type::FP128Ty;
}
return Type::VoidTy;
}
Value* NInteger::codeGen(CodeGenContext& context)
{
std::cout <<
"Creating integer: "
<< value << endl;
return ConstantInt::get(Type::Int64Ty, value, true);
}
Value* NDouble::codeGen(CodeGenContext& context)
{
std::cout <<
"Creating double: "
<< value << endl;
return ConstantFP::get(Type::FP128Ty, value);
}
Value* NIdentifier::codeGen(CodeGenContext& context)
{
std::cout <<
"Creating identifier reference: "
<< name << endl;
if (context.locals().find(name) == context.locals().end()) {
std::cerr <<
"undeclared variable "
<< name << endl;
return NULL;
}
return new LoadInst(context.locals()[name],
""
, false, context.currentBlock());
}
Value* NMethodCall::codeGen(CodeGenContext& context)
{
Function *function = context.module->getFunction(id.name.c_str());
if (function == NULL) {
std::cerr <<
"no such function "
<< id.name << endl;
}
std::vector<value *> args;
ExpressionList::const_iterator it;
for (it = arguments.begin(); it != arguments.end(); it++) {
args.push_back((**it).codeGen(context));
}
CallInst *call = CallInst::Create(function, args.begin(), args.end(),
""
, context.currentBlock());
std::cout <<
"Creating method call: "
<< id.name << endl;
return call;
}
Value* NBinaryOperator::codeGen(CodeGenContext& context)
{
std::cout <<
"Creating binary operation "
<< op << endl;
Instruction::BinaryOps instr;
switch (op) {
case TPLUS: instr = Instruction::Add; goto math;
case TMINUS: instr = Instruction::Sub; goto math;
case TMUL: instr = Instruction::Mul; goto math;
case TDIV: instr = Instruction::SDiv; goto math;
}
return NULL;
math:
return BinaryOperator::Create(instr, lhs.codeGen(context),
rhs.codeGen(context),
""
, context.currentBlock());
}
Value* NAssignment::codeGen(CodeGenContext& context)
{
std::cout <<
"Creating assignment for "
<< lhs.name << endl;
if (context.locals().find(lhs.name) == context.locals().end()) {
std::cerr <<
"undeclared variable "
<< lhs.name << endl;
return NULL;
}
return new StoreInst(rhs.codeGen(context), context.locals()[lhs.name], false, context.currentBlock());
}
Value* NBlock::codeGen(CodeGenContext& context)
{
StatementList::const_iterator it;
Value *last = NULL;
for (it = statements.begin(); it != statements.end(); it++) {
std::cout <<
"Generating code for "
<< typeid(**it).name() << endl;
last = (**it).codeGen(context);
}
std::cout <<
"Creating block"
<< endl;
return last;
}
Value* NExpressionStatement::codeGen(CodeGenContext& context)
{
std::cout <<
"Generating code for "
<< typeid(expression).name() << endl;
return expression.codeGen(context);
}
Value* NVariableDeclaration::codeGen(CodeGenContext& context)
{
std::cout <<
"Creating variable declaration "
<< type.name <<
" "
<< id.name << endl;
AllocaInst *alloc = new AllocaInst(typeOf(type), id.name.c_str(), context.currentBlock());
context.locals()[id.name] = alloc;
if (assignmentExpr != NULL) {
NAssignment assn(id, *assignmentExpr);
assn.codeGen(context);
}
return alloc;
}
Value* NFunctionDeclaration::codeGen(CodeGenContext& context)
{
vector<const type*> argTypes;
VariableList::const_iterator it;
for (it = arguments.begin(); it != arguments.end(); it++) {
argTypes.push_back(typeOf((**it).type));
}
FunctionType *ftype = FunctionType::get(typeOf(type), argTypes, false);
Function *function = Function::Create(ftype, GlobalValue::InternalLinkage, id.name.c_str(), context.module);
BasicBlock *bblock = BasicBlock::Create(
"entry"
, function, 0);
context.pushBlock(bblock);
for (it = arguments.begin(); it != arguments.end(); it++) {
(**it).codeGen(context);
}
block.codeGen(context);
ReturnInst::Create(bblock);
context.popBlock();
std::cout <<
"Creating function: "
<< id.name << endl;
return function;
}
上述羅列很多的代碼，然而這部份代碼的含義需要你自己去探索。我在這裡隻會提及一下你需要注意的内容：
· 我們在CodeGenContext類中使用一個語句塊的棧來儲存最後進入的block(因為語句都被增加到blocks中)
· 我們同樣用個堆棧來儲存每組語句塊中的符号表
· 我們設計的語言隻會知道他目前範圍内的内容.要支援“全局”上下的做法，你必須向上搜尋整個堆棧中每一個語句塊，知道你最後發現你比對的符号(現在我們隻是簡單地搜尋堆棧中最頂層的符号表)。
· 在我們進入一個語句塊之前，我們需要将語句塊壓棧，離開語句塊時将語句塊出棧
剩下的内容都LLVM相關了，在這個主題上我并不是專家。但是迄今為止，我們已經有了編譯和運作我們語言的所有代碼。
7、編譯和運作我們的語言
7.1、編譯我們的語言
我們已經有了代碼，現在我們怎麼運作它？LLVM有着非常複雜的聯接link，幸運的是，如果你是自己安裝的LLVM，那麼你就應該有一個llvm-config二進制程式，這個程式傳回你需要的所有編譯和聯接選項。
我們也要同時更新我們的main.cpp的内容使之可以編譯和運作我們的代碼，這次我們main.cpp的内容如下：
#include <iostream>
#include "codegen.h"
#include "node.h"
using namespace std;
extern
int
yyparse();
extern NBlock* programBlock;
int
main(
int
argc,
char
**argv)
{
yyparse();
std::cout << programBlock << endl;
CodeGenContext context;
context.generateCode(*programBlock);
context.runCode();
return 0;
}
現在我們需要這樣來編譯這些代碼
$ 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://gnuu.org/2009/09/18/writing-your-own-toy-compiler