成人免费xxxxx在线视频软件_久久精品久久久_亚洲国产精品久久久_天天色天天色_亚洲人成一区_欧美一级欧美三级在线观看

實現一個簡單的編譯器

開發 開發工具
簡單的說 編譯器 就是語言翻譯器,它一般將高級語言翻譯成更低級的語言,如 GCC 可將 C/C++ 語言翻譯成可執行機器語言,Java 編譯器可以將 Java 源代碼翻譯成 Java 虛擬機可以執行的字節碼。

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

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

自定義語法

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

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

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

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

編譯原理簡介

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

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

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

工具簡介

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

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

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

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

介紹完工具,現在我們可以開始實現我們的編譯器了。

詞法分析器

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

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

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

現在我們可以通過調用 Flex 生成 詞法分析器 的源碼: 

  1. flex -o lexical.cpp lexical.l 

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

語法分析器

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

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

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

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

  1. %token <token> TLPAREN TRPAREN TLBRACE TRBRACE TCOMMA 

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

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

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

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

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

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

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

目標碼生成

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

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

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

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

對了,我們還需要一個 main 函數作為編譯器的入口函數,它在 main.cpp 里:

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

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

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

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

如果你下載了 GitHub 的源碼,那么直接:

  1. cd src 
  2. make  

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

編譯測試

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

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

也可以直接通過

  1. make test 

來測試,輸出如下:

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

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

責任編輯:龐桂玉 來源: segmentfault
相關推薦

2021-06-25 10:38:05

JavaScript編譯器前端開發

2021-12-30 11:26:31

語言編譯器腳本

2020-06-04 12:55:44

PyTorch分類器神經網絡

2020-08-26 09:05:03

函數編譯詞法

2009-09-01 10:35:19

C# 3.0編譯器

2022-03-28 10:25:27

前端文件編譯器

2022-06-02 16:46:25

京東APP升級Android升級AGP

2021-04-08 13:54:52

LinuxIBM編譯器

2020-01-10 18:04:01

Python編程語言Windows

2018-09-18 10:11:21

前端vue.jsjavascript

2021-07-20 10:30:46

Golanghttp語言

2012-04-05 09:13:17

C代碼

2023-07-10 07:58:45

2012-07-18 11:31:50

ibmdw

2010-03-23 11:17:16

Python 動態編譯

2021-05-26 07:53:58

Linux運維Linux系統

2022-11-29 17:34:43

虛擬形象系統

2010-10-20 13:43:37

C++編譯器

2010-01-27 16:39:48

C++編譯器

2021-06-08 07:48:26

lambda表達式編譯器
點贊
收藏

51CTO技術棧公眾號

主站蜘蛛池模板: 99热这里只有精品8 激情毛片 | 五月婷婷丁香婷婷 | 亚洲成人日韩 | 自拍偷拍第1页 | 久久综合久久久 | 国产午夜三级一区二区三 | 五月天天丁香婷婷在线中 | 久久99精品久久久久久琪琪 | 最新超碰 | 日本在线免费视频 | 精品av| 6080yy精品一区二区三区 | 亚洲综合区 | 欧美精品一区二区三区蜜桃视频 | 中文字幕国产第一页 | 欧美电影一区 | 国产91一区| 亚洲国产精品成人无久久精品 | 日韩免费一区二区 | 91精品国产综合久久香蕉922 | 黄色片免费 | 欧美精品福利 | 操久久 | 嫩草网 | 亚洲www啪成人一区二区麻豆 | 天天色影视综合 | 久久久激情 | 亚洲乱码一区二区三区在线观看 | 亚洲精选一区二区 | 国产一区二区精品在线观看 | 久久这里只有 | 伊人色综合久久久天天蜜桃 | 亚洲网站在线观看 | 日本啊v在线 | 欧美激情在线播放 | 天堂资源 | 丁香婷婷久久久综合精品国产 | 亚洲视频第一页 | 久久国产精品亚洲 | 日韩久久久久 | 亚洲视频www|