日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關咨詢
選擇下列產(chǎn)品馬上在線溝通
服務時間：8:30-17:00
你可能遇到了下面的問題
關閉右側工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
實現(xiàn)一個簡單的編譯器

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

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

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

自定義語法

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

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

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

 
 
    
  
  
  1. extern printi(val)
    2. 
  
  
  2. 
  
  
  3. sum(a, b) {
    4. 
  
  
  4.   return a + b
    5. 
  
  
  5. }
    6. 
  
  
  6. 
  
  
  7. mult(a, b) {
    8. 
  
  
  8.   return a * b
    9. 
  
  
  9. }
    10. 
  
  
  10. 
  
  
  11. printi(mult(4, 5) - sum(4, 5)) 
    12.

編譯原理簡介

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

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

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

工具簡介

對應編譯器工作步驟我們將使用以下工具，括號里標明了所使用的版本號：

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

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

 
 
    
  
  
  1. sudo apt-get install flex
    2. 
  
  
  2. sudo apt-get install bison
    3. 
  
  
  3. sudo apt-get install llvm-3.8* 
    4.

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

詞法分析器

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

 
 
    
  
  
  1. %{
    2. 
  
  
  2. #include 
    3. 
  
  
  3. #include "ast.h"
    4. 
  
  
  4. #include "syntactic.hpp"
    5. 
  
  
  5. 
  
  
  6. #define SAVE_TOKEN  yylval.string = new std::string(yytext, yyleng)
    7. 
  
  
  7. #define TOKEN(t)    (yylval.token = t)
    8. 
  
  
  8. %}
    9. 
  
  
  9. 
  
  
  10. %option noyywrap
    11. 
  
  
  11. 
  
  
  12. %%
    13. 
  
  
  13. 
  
  
  14. [ \t\n]                 ;
    15. 
  
  
  15. "extern"                return TOKEN(TEXTERN);
    16. 
  
  
  16. "return"                return TOKEN(TRETURN);
    17. 
  
  
  17. [a-zA-Z_][a-zA-Z0-9_]*  SAVE_TOKEN; return TIDENTIFIER;
    18. 
  
  
  18. [0-9]+                  SAVE_TOKEN; return TINTEGER;
    19. 
  
  
  19. 
  
  
  20. "="                     return TOKEN(TEQUAL);
    21. 
  
  
  21. "=="                    return TOKEN(TCEQ);
    22. 
  
  
  22. "!="                    return TOKEN(TCNE);
    23. 
  
  
  23. 
  
  
  24. "("                     return TOKEN(TLPAREN);
    25. 
  
  
  25. ")"                     return TOKEN(TRPAREN);
    26. 
  
  
  26. "{"                     return TOKEN(TLBRACE);
    27. 
  
  
  27. "}"                     return TOKEN(TRBRACE);
    28. 
  
  
  28. 
  
  
  29. ","                     return TOKEN(TCOMMA);
    30. 
  
  
  30. 
  
  
  31. "+"                     return TOKEN(TPLUS);
    32. 
  
  
  32. "-"                     return TOKEN(TMINUS);
    33. 
  
  
  33. "*"                     return TOKEN(TMUL);
    34. 
  
  
  34. "/"                     return TOKEN(TDIV);
    35. 
  
  
  35. 
  
  
  36. .                       printf("Unknown token!\n"); yyterminate();
    37. 
  
  
  37. 
  
  
  38. %% 
    39.

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

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

 
 
    
  
  
  1. flex -o lexical.cpp lexical.l
    2.

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

語法分析器

語法分析器 的作用是構建 抽象語法樹，通俗的說 抽象語法樹 就是將源碼用樹狀結構來表示，每個節(jié)點都代表源碼中的一種結構;對于我們要實現(xiàn)的語法，其語法樹是很簡單的，如下：

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

 
 
    
  
  
  1. %{
    2. 
  
  
  2.     #include "ast.h"
    3. 
  
  
  3.     #include 
    4. 
  
  
  4. 
  
  
  5. ...
    6. 
  
  
  6. 
  
  
  7.     extern int yylex();
    8. 
  
  
  8.     void yyerror(const char *s) { std::printf("Error: %s\n", s);std::exit(1); }
    9. 
  
  
  9. %}
    10. 
  
  
  10. 
  
  
  11. ...
    12. 
  
  
  12. 
  
  
  13. %token  TLPAREN TRPAREN TLBRACE TRBRACE TCOMMA
    14. 
  
  
  14. 
  
  
  15. ...
    16. 
  
  
  16. 
  
  
  17. %%
    18. 
  
  
  18. 
  
  
  19. program:
    20. 
  
  
  20.   stmts { programBlock = $1; }
    21. 
  
  
  21.         ;
    22. 
  
  
  22. ...
    23. 
  
  
  23. 
  
  
  24. func_decl:
    25. 
  
  
  25.   ident TLPAREN func_decl_args TRPAREN block { $$ = new NFunctionDeclaration(*$1, *$3, *$5); delete $3; }
    26. 
  
  
  26. ;
    27. 
  
  
  27. 
  
  
  28. ...
    29. 
  
  
  29. 
  
  
  30. %% 
    31.

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

 
 
    
  
  
  1. %token  TLPAREN TRPAREN TLBRACE TRBRACE TCOMMA
    2.

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

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

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

 
 
    
  
  
  1. ...
    2. 
  
  
  2. 
  
  
  3. class NFunctionDeclaration : public NStatement {
    4. 
  
  
  4. public:
    5. 
  
  
  5.     const NIdentifier& id;
    6. 
  
  
  6.     VariableList arguments;
    7. 
  
  
  7.     NBlock& block;
    8. 
  
  
  8.     NFunctionDeclaration(const NIdentifier& id,
    9. 
  
  
  9.             const VariableList& arguments, NBlock& block) :
    10. 
  
  
  10.         id(id), arguments(arguments), block(block) { }
    11. 
  
  
  11.     virtual llvm::Value* codeGen(CodeGenContext& context);
    12. 
  
  
  12. };
    13. 
  
  
  13. 
  
  
  14. ... 
    15.

可以看到，它有 標識符(id)，參數(shù)列表(arguments)，函數(shù)體(block) 這些成員，在語法分析階段會設置好這些成員的內容供后面的 目標碼生成 階段使用。還可以看到有一個 codeGen() 虛函數(shù)，你可能猜到了，后面就是通過調用它來生成相應的目標代碼。

我們可以通過以下命令調用 Bison 生成 語法分析器 的源碼文件，這里我們使用 -d 使頭文件和源文件分開，因為前面 詞法分析器的源碼使用了這里定義的一些宏，所以需要使用這個頭文件，這里將會生成 syntactic.cpp 和 syntactic.hpp：

 
 
    
  
  
  1. bison -d -o syntactic.cpp syntactic.y
    2.

目標碼生成

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

 
 
    
  
  
  1. ...
    2. 
  
  
  2. 
  
  
  3. Value *NMethodCall::codeGen(CodeGenContext &context) {
    4. 
  
  
  4.     Function *function = context.module->getFunction(id.name.c_str());
    5. 
  
  
  5.     if (function == NULL) {
    6. 
  
  
  6.         std::cerr << "no such function " << id.name << endl;
    7. 
  
  
  7.     }
    8. 
  
  
  8.     std::vector args;
    9. 
  
  
  9.     ExpressionList::const_iterator it;
    10. 
  
  
  10.     for (it = arguments.begin(); it != arguments.end(); it++) {
    11. 
  
  
  11.         args.push_back((**it).codeGen(context));
    12. 
  
  
  12.     }
    13. 
  
  
  13.     CallInst *call = CallInst::Create(function, makeArrayRef(args), "", context.currentBlock());
    14. 
  
  
  14.     std::cout << "Creating method call: " << id.name << endl;
    15. 
  
  
  15.     return call;
    16. 
  
  
  16. }
    17. 
  
  
  17. 
  
  
  18. ... 
    19.

看起來有點復雜，簡單來說就是通過 LLVM 提供的接口來生成 目標碼，需要了解更多的話可以去 LLVM 的官網(wǎng)學習一下。

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

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

 
 
    
  
  
  1. ...
    2. 
  
  
  2. 
  
  
  3. int main(int argc, char **argv) {
    4. 
  
  
  4.     yyparse();
    5. 
  
  
  5.     InitializeNativeTarget();
    6. 
  
  
  6.     InitializeNativeTargetAsmPrinter();
    7. 
  
  
  7.     InitializeNativeTargetAsmParser();
    8. 
  
  
  8.     CodeGenContext context;
    9. 
  
  
  9.     context.generateCode(*programBlock);
    10. 
  
  
  10.     context.runCode();
    11. 
  
  
  11. 
  
  
  12.     return 0;
    13. 
  
  
  13. } 
    14.

我們可以看到其調用了 yyparse() 做 語法分析，(yyparse() 內部會先調用 yylex() 做 詞法分析);然后是一系列的 LLVM 初始化代碼，context.generateCode(*programBlock) 是開始生成 目標碼;最后是 context.runCode() 來運行代碼，這里使用了 LLVM 的 JIT(Just In Time) 來直接運行代碼，沒有鏈接的過程。

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

 
 
    
  
  
  1. bison -d -o syntactic.cpp syntactic.y
    2. 
  
  
  2. flex -o lexical.cpp lexical.l syntactic.hpp
    3. 
  
  
  3. g++ -c `llvm-config --cppflags` -std=c++11 syntactic.cpp gen.cpp lexical.cpp printi.cpp main.cpp
    4. 
  
  
  4. 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 
    5.

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

 
 
    
  
  
  1. cd src
    2. 
  
  
  2. make 
    3.

就可以完成以上過程了，正常會生成一個二進制文件 xy-complier，它就是我們的編譯器了。

編譯測試

我們使用之前提到實例 demo.xy 來測試，將其內容傳給 xy-complier 的標準輸入就可以看到運行結果了：

 
 
    
  
  
  1. cat demo.xy | ./xy-complier
    2.

也可以直接通過

 
 
    
  
  
  1. make test
    2.

來測試，輸出如下：

 
 
    
  
  
  1. ...
    2. 
  
  
  2. 
  
  
  3. define internal i64 @mult(i64 %a1, i64 %b2) {
    4. 
  
  
  4. entry:
    5. 
  
  
  5.   %a = alloca i64
    6. 
  
  
  6.   %0 = load i64, i64* %a
    7. 
  
  
  7.   store i64 %a1, i64* %a
    8. 
  
  
  8.   %b = alloca i64
    9. 
  
  
  9.   %1 = load i64, i64* %b
    10. 
  
  
  10.   store i64 %b2, i64* %b
    11. 
  
  
  11.   %2 = load i64, i64* %b
    12. 
  
  
  12.   %3 = load i64, i64* %a
    13. 
  
  
  13.   %4 = mul i64 %3, %2
    14. 
  
  
  14.   ret i64 %4
    15. 
  
  
  15. }
    16. 
  
  
  16. Running code:
    17. 
  
  
  17. 11
    18. 
  
  
  18. Exiting... 
    19.

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


新聞名稱：實現(xiàn)一個簡單的編譯器
文章源于：http://www.dlmjj.cn/article/dpijjoe.html