簡(jiǎn)單的說(shuō) 編譯器 就是語(yǔ)言翻譯器，它一般將高級(jí)語(yǔ)言翻譯成更低級(jí)的語(yǔ)言，如 GCC 可將 C/C++ 語(yǔ)言翻譯成可執(zhí)行機(jī)器語(yǔ)言，Java 編譯器可以將 Java 源代碼翻譯成 Java 虛擬機(jī)可以執(zhí)行的字節(jié)碼。

成都創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),大連企業(yè)網(wǎng)站建設(shè),大連品牌網(wǎng)站建設(shè),網(wǎng)站定制,大連網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,大連網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

編譯器如此神奇，那么它到底是如何工作的呢?本文將簡(jiǎn)單介紹編譯器的原理，并實(shí)現(xiàn)一個(gè)簡(jiǎn)單的編譯器，使它能編譯我們自定義語(yǔ)法格式的源代碼。(文中使用的源碼都已上傳至 GitHub 以方便查看)。

自定義語(yǔ)法

為了簡(jiǎn)潔易懂，我們的編譯器將只支持以下簡(jiǎn)單功能：

• 數(shù)據(jù)類型只支持整型，這樣不需要數(shù)據(jù)類型符;
• 支持 加(+)，減(-)，乘(*)， 除(/) 運(yùn)算
• 支持函數(shù)調(diào)用
• 支持 extern(為了調(diào)用 printf 打印計(jì)算結(jié)果)

以下是我們要支持的源碼實(shí)例 demo.xy：

 
 

  
  
extern printi(val)
  
  

  
  
sum(a, b) {
  
  
  return a + b
  
  
}
  
  

  
  
mult(a, b) {
  
  
  return a * b
  
  
}
  
  

  
  
printi(mult(4, 5) - sum(4, 5)) 
 
 

編譯原理簡(jiǎn)介

一般編譯器有以下工作步驟：

1. 詞法分析(Lexical analysis)： 此階段的任務(wù)是從左到右一個(gè)字符一個(gè)字符地讀入源程序，對(duì)構(gòu)成源程序的字符流進(jìn)行掃描然后根據(jù)構(gòu)詞規(guī)則識(shí)別 單詞(Token)，完成這個(gè)任務(wù)的組件是 詞法分析器(Lexical analyzer，簡(jiǎn)稱Lexer)，也叫 掃描器(Scanner);
2. 語(yǔ)法分析(Syntactic analysis，也叫 Parsing)： 此階段的主要任務(wù)是由 詞法分析器 生成的單詞構(gòu)建 抽象語(yǔ)法樹(shù)(Abstract Syntax Tree ，AST)，完成此任務(wù)的組件是 語(yǔ)法分析器(Parser);
3. 目標(biāo)碼生成： 此階段編譯器會(huì)遍歷上一步生成的抽象語(yǔ)法樹(shù)，然后為每個(gè)節(jié)點(diǎn)生成 機(jī)器 / 字節(jié)碼。

編譯器完成編譯后，由 鏈接器(Linker) 將生成的目標(biāo)文件鏈接成可執(zhí)行文件，這一步并不是必須的，一些依賴于虛擬機(jī)運(yùn)行的語(yǔ)言(如 Java，Erlang)就不需要鏈接。

工具簡(jiǎn)介

對(duì)應(yīng)編譯器工作步驟我們將使用以下工具，括號(hào)里標(biāo)明了所使用的版本號(hào)：

• Flex(2.6.0): Flex 是 Lex 開(kāi)源替代品，他們都是 詞法分析器 制作工具，它可以根據(jù)我們定義的規(guī)則生成 詞法分析器 的代碼;
• Bison(3.0.4)： Bison 是 語(yǔ)法分析器 的制作工具，同樣它可以根據(jù)我們定義的規(guī)則生成 語(yǔ)法分析器 的代碼;
• LLVM(3.8.0)： LLVM 是構(gòu)架編譯器的框架系統(tǒng)，我們會(huì)利用他來(lái)完成從 抽象語(yǔ)法樹(shù) 生成目標(biāo)碼的過(guò)程。

在 ubuntu 上可以通過(guò)以下命令安裝這些工具：

 
 

  
  
sudo apt-get install flex
  
  
sudo apt-get install bison
  
  
sudo apt-get install llvm-3.8* 
 
 

介紹完工具，現(xiàn)在我們可以開(kāi)始實(shí)現(xiàn)我們的編譯器了。

詞法分析器

前面提到 詞法分析器 要將源程序分解成 單詞，我們的語(yǔ)法格式很簡(jiǎn)單，只包括：標(biāo)識(shí)符，數(shù)字，數(shù)學(xué)運(yùn)算符，括號(hào)和大括號(hào)等，我們將通過(guò) Flex 來(lái)生成 詞法分析器 的源碼，給 Flex 使用的規(guī)則文件 lexical.l 如下：

 
 

  
  
%{
  
  
#include 
  
  
#include "ast.h"
  
  
#include "syntactic.hpp"
  
  

  
  
#define SAVE_TOKEN  yylval.string = new std::string(yytext, yyleng)
  
  
#define TOKEN(t)    (yylval.token = t)
  
  
%}
  
  

  
  
%option noyywrap
  
  

  
  
%%
  
  

  
  
[ \t\n]                 ;
  
  
"extern"                return TOKEN(TEXTERN);
  
  
"return"                return TOKEN(TRETURN);
  
  
[a-zA-Z_][a-zA-Z0-9_]*  SAVE_TOKEN; return TIDENTIFIER;
  
  
[0-9]+                  SAVE_TOKEN; return TINTEGER;
  
  

  
  
"="                     return TOKEN(TEQUAL);
  
  
"=="                    return TOKEN(TCEQ);
  
  
"!="                    return TOKEN(TCNE);
  
  

  
  
"("                     return TOKEN(TLPAREN);
  
  
")"                     return TOKEN(TRPAREN);
  
  
"{"                     return TOKEN(TLBRACE);
  
  
"}"                     return TOKEN(TRBRACE);
  
  

  
  
","                     return TOKEN(TCOMMA);
  
  

  
  
"+"                     return TOKEN(TPLUS);
  
  
"-"                     return TOKEN(TMINUS);
  
  
"*"                     return TOKEN(TMUL);
  
  
"/"                     return TOKEN(TDIV);
  
  

  
  
.                       printf("Unknown token!\n"); yyterminate();
  
  

  
  
%% 
 
 

我們來(lái)解釋一下，這個(gè)文件被 2 個(gè) %% 分成 3 部分，第 1 部分用 %{ 與 %} 包括的是一些 C++ 代碼，會(huì)被原樣復(fù)制到 Flex 生成的源碼文件中，還可以在指定一些選項(xiàng)，如我們使用了 %option noyywrap，也可以在這定義宏供后面使用;第 2 部分用來(lái)定義構(gòu)成單詞的規(guī)則，可以看到每條規(guī)都是一個(gè) 正則表達(dá)式 和 動(dòng)作，很直白，就是 詞法分析器 發(fā)現(xiàn)了匹配的 單詞 后執(zhí)行相應(yīng)的 動(dòng)作 代碼，大部分只要返回 單詞 給調(diào)用者就可以了;第 3 部分可以定義一些函數(shù)，也會(huì)原樣復(fù)制到生成的源碼中去，這里我們留空沒(méi)有使用。

現(xiàn)在我們可以通過(guò)調(diào)用 Flex 生成 詞法分析器 的源碼：

 
 

  
  
flex -o lexical.cpp lexical.l
 
 

生成的　lexical.cpp　里會(huì)有一個(gè) yylex() 函數(shù)供　語(yǔ)法分析器　調(diào)用;你可能發(fā)現(xiàn)了，有些宏和變量并沒(méi)有被定義(如TEXTERN，yylval，yytext 等)，其實(shí)有些是 Flex 會(huì)自動(dòng)定義的內(nèi)置變量(如 yytext)，有些是后面 語(yǔ)法分析器 生成工具里定義的變量(如 yylval)，我們后面會(huì)看到。

語(yǔ)法分析器

語(yǔ)法分析器 的作用是構(gòu)建 抽象語(yǔ)法樹(shù)，通俗的說(shuō) 抽象語(yǔ)法樹(shù) 就是將源碼用樹(shù)狀結(jié)構(gòu)來(lái)表示，每個(gè)節(jié)點(diǎn)都代表源碼中的一種結(jié)構(gòu);對(duì)于我們要實(shí)現(xiàn)的語(yǔ)法，其語(yǔ)法樹(shù)是很簡(jiǎn)單的，如下：

現(xiàn)在我們使用 Bison 生成 語(yǔ)法分析器 代碼，同樣 Bison 需要一個(gè)規(guī)則文件，我們的規(guī)則文件 syntactic.y 如下，限于篇幅，省略了某些部分，可以通過(guò)鏈接查看完整內(nèi)容：

 
 

  
  
%{
  
  
    #include "ast.h"
  
  
    #include 
  
  

  
  
...
  
  

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

  
  
...
  
  

  
  
%token  TLPAREN TRPAREN TLBRACE TRBRACE TCOMMA
  
  

  
  
...
  
  

  
  
%%
  
  

  
  
program:
  
  
  stmts { programBlock = $1; }
  
  
        ;
  
  
...
  
  

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

  
  
...
  
  

  
  
%% 
 
 

是不是發(fā)現(xiàn)和 Flex 的規(guī)則文件很像呢?確實(shí)是這樣，它也是分 3 個(gè)部分組成，同樣，第一部分的 C++ 代碼會(huì)被復(fù)制到生成的源文件中，還可以看到這里通過(guò)以下這樣的語(yǔ)法定義前面了 Flex 使用的宏：

 
 

  
  
%token  TLPAREN TRPAREN TLBRACE TRBRACE TCOMMA
 
 

比較不同的是第 2 部分，不像 Flex 通過(guò) 正則表達(dá)式 通過(guò)定義規(guī)則，這里使用的是 巴科斯范式(BNF: Backus-Naur Form) 的形式定義了我們識(shí)別的語(yǔ)法結(jié)構(gòu)。如下的語(yǔ)法表示函數(shù)：

 
 

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

可以看到后面大括號(hào)中間的也是 動(dòng)作 代碼，上例的動(dòng)作是在 抽象語(yǔ)法樹(shù) 中生成一個(gè)函數(shù)的節(jié)點(diǎn)，其實(shí)這部分的其他規(guī)則也是生成相應(yīng)類型的節(jié)點(diǎn)到語(yǔ)法樹(shù)中。像 NFunctionDeclaration 這是一個(gè)我們自己定義的節(jié)點(diǎn)類，我們?cè)?ast.h 中定義了我們所要用到的節(jié)點(diǎn)，同樣的，我們摘取一段代碼如下：

 
 

  
  
...
  
  

  
  
class NFunctionDeclaration : public NStatement {
  
  
public:
  
  
    const NIdentifier& id;
  
  
    VariableList arguments;
  
  
    NBlock& block;
  
  
    NFunctionDeclaration(const NIdentifier& id,
  
  
            const VariableList& arguments, NBlock& block) :
  
  
        id(id), arguments(arguments), block(block) { }
  
  
    virtual llvm::Value* codeGen(CodeGenContext& context);
  
  
};
  
  

  
  
... 
 
 

可以看到，它有 標(biāo)識(shí)符(id)，參數(shù)列表(arguments)，函數(shù)體(block) 這些成員，在語(yǔ)法分析階段會(huì)設(shè)置好這些成員的內(nèi)容供后面的 目標(biāo)碼生成 階段使用。還可以看到有一個(gè) codeGen() 虛函數(shù)，你可能猜到了，后面就是通過(guò)調(diào)用它來(lái)生成相應(yīng)的目標(biāo)代碼。

我們可以通過(guò)以下命令調(diào)用 Bison 生成 語(yǔ)法分析器 的源碼文件，這里我們使用 -d 使頭文件和源文件分開(kāi)，因?yàn)榍懊?詞法分析器的源碼使用了這里定義的一些宏，所以需要使用這個(gè)頭文件，這里將會(huì)生成 syntactic.cpp 和 syntactic.hpp：

 
 

  
  
bison -d -o syntactic.cpp syntactic.y
 
 

目標(biāo)碼生成

這是最后一步了，這一步的主角是前面提到 LLVM，LLVM 是一個(gè)構(gòu)建編譯器的框架系統(tǒng)，我們使用他遍歷 語(yǔ)法分析 階段生成的 抽象語(yǔ)法樹(shù)，然后為每個(gè)節(jié)點(diǎn)生成相應(yīng)的 目標(biāo)碼。當(dāng)然，無(wú)法避免的是我們需要使用 LLVM 提供的函數(shù)來(lái)編寫(xiě)生成目標(biāo)碼的源碼，就是實(shí)現(xiàn)前面提到的虛函數(shù) codeGen()，是不是有點(diǎn)拗口?不過(guò)確實(shí)是這樣。我們?cè)?gen.cpp 中編寫(xiě)了不同節(jié)點(diǎn)的生成代碼，我們摘取一段看一下：

 
 

  
  
...
  
  

  
  
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 args;
  
  
    ExpressionList::const_iterator it;
  
  
    for (it = arguments.begin(); it != arguments.end(); it++) {
  
  
        args.push_back((**it).codeGen(context));
  
  
    }
  
  
    CallInst *call = CallInst::Create(function, makeArrayRef(args), "", context.currentBlock());
  
  
    std::cout << "Creating method call: " << id.name << endl;
  
  
    return call;
  
  
}
  
  

  
  
... 
 
 

看起來(lái)有點(diǎn)復(fù)雜，簡(jiǎn)單來(lái)說(shuō)就是通過(guò) LLVM 提供的接口來(lái)生成 目標(biāo)碼，需要了解更多的話可以去 LLVM 的官網(wǎng)學(xué)習(xí)一下。

至此，我們所有的工作基本都做完了。簡(jiǎn)單回顧一下：我們先通過(guò) Flex 生成 詞法分析器 源碼文件 lexical.cpp，然后通過(guò) Bison 生成 語(yǔ)法分析器 源碼文件 syntactic.cpp 和頭文件 syntactic.hpp，我們自己編寫(xiě)了 抽象語(yǔ)法樹(shù) 節(jié)點(diǎn)定義文件 ast.h 和 目標(biāo)碼生成文件 ast.cpp，還有一個(gè) gen.h 包含一點(diǎn) LLVM 環(huán)境相關(guān)的代碼，為了輸出我們程序的結(jié)果，還在 printi.cpp 里簡(jiǎn)單的通過(guò)調(diào)用 C 語(yǔ)言庫(kù)函數(shù)實(shí)現(xiàn)了輸出一個(gè)整數(shù)。

對(duì)了，我們還需要一個(gè) main 函數(shù)作為編譯器的入口函數(shù)，它在 main.cpp 里：

 
 

  
  
...
  
  

  
  
int main(int argc, char **argv) {
  
  
    yyparse();
  
  
    InitializeNativeTarget();
  
  
    InitializeNativeTargetAsmPrinter();
  
  
    InitializeNativeTargetAsmParser();
  
  
    CodeGenContext context;
  
  
    context.generateCode(*programBlock);
  
  
    context.runCode();
  
  

  
  
    return 0;
  
  
} 
 
 

我們可以看到其調(diào)用了 yyparse() 做 語(yǔ)法分析，(yyparse() 內(nèi)部會(huì)先調(diào)用 yylex() 做 詞法分析);然后是一系列的 LLVM 初始化代碼，context.generateCode(*programBlock) 是開(kāi)始生成 目標(biāo)碼;最后是 context.runCode() 來(lái)運(yùn)行代碼，這里使用了 LLVM 的 JIT(Just In Time) 來(lái)直接運(yùn)行代碼，沒(méi)有鏈接的過(guò)程。

現(xiàn)在我們可以用這些文件生成我們的編譯器了，需要說(shuō)明一下，因?yàn)?詞法分析器 的源碼使用了一些 語(yǔ)法分析器 頭文件中的宏，所以正確的生成順序是這樣的：

 
 

  
  
bison -d -o syntactic.cpp syntactic.y
  
  
flex -o lexical.cpp lexical.l syntactic.hpp
  
  
g++ -c `llvm-config --cppflags` -std=c++11 syntactic.cpp gen.cpp lexical.cpp printi.cpp main.cpp
  
  
g++ -o xy-complier syntactic.o gen.o main.o lexical.o printi.o `llvm-config --libs` `llvm-config --ldflags` -lpthread -ldl -lz -lncurses -rdynamic 
 
 

如果你下載了 GitHub 的源碼，那么直接：

 
 

  
  
cd src
  
  
make 
 
 

就可以完成以上過(guò)程了，正常會(huì)生成一個(gè)二進(jìn)制文件 xy-complier，它就是我們的編譯器了。

編譯測(cè)試

我們使用之前提到實(shí)例 demo.xy 來(lái)測(cè)試，將其內(nèi)容傳給 xy-complier 的標(biāo)準(zhǔn)輸入就可以看到運(yùn)行結(jié)果了：

 
 

  
  
cat demo.xy | ./xy-complier
 
 

也可以直接通過(guò)

 
 

  
  
make test
 
 

來(lái)測(cè)試，輸出如下：

 
 

  
  
...
  
  

  
  
define internal i64 @mult(i64 %a1, i64 %b2) {
  
  
entry:
  
  
  %a = alloca i64
  
  
  %0 = load i64, i64* %a
  
  
  store i64 %a1, i64* %a
  
  
  %b = alloca i64
  
  
  %1 = load i64, i64* %b
  
  
  store i64 %b2, i64* %b
  
  
  %2 = load i64, i64* %b
  
  
  %3 = load i64, i64* %a
  
  
  %4 = mul i64 %3, %2
  
  
  ret i64 %4
  
  
}
  
  
Running code:
  
  
11
  
  
Exiting... 
 
 

可以看到最后正確輸出了期望的結(jié)果，至此我們簡(jiǎn)單的編譯器就完成了。

標(biāo)題名稱：實(shí)現(xiàn)一個(gè)簡(jiǎn)單的編譯器
鏈接分享：http://uogjgqi.cn/article/dpijjoe.html