实现一个简单的编译器

简单的说 编译器 就是语言翻译器，它一般将高级语言翻译成更低级的语言，如 GCC 可将 C/C++ 语言翻译成可执行机器语言，Java 编译器可以将 Java 源代码翻译成 Java 虚拟机可以执行的字节码。

成都创新互联公司是一家集网站建设,大连企业网站建设,大连品牌网站建设,网站定制,大连网站建设报价,网络营销,网络优化,大连网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

编译器如此神奇，那么它到底是如何工作的呢?本文将简单介绍编译器的原理，并实现一个简单的编译器，使它能编译我们自定义语法格式的源代码。(文中使用的源码都已上传至 GitHub 以方便查看)。

自定义语法

为了简洁易懂，我们的编译器将只支持以下简单功能：

  • 数据类型只支持整型，这样不需要数据类型符;
  • 支持 加(+)，减(-)，乘(*)， 除(/) 运算
  • 支持函数调用
  • 支持 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)： 此阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描然后根据构词规则识别 单词(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. 
  
  
  2. sudo apt-get install bison
    3. 
  
  
  3. sudo apt-get install llvm-3.8* 
    4.

介绍完工具，现在我们可以开始实现我们的编译器了。

词法分析器

前面提到 词法分析器 要将源程序分解成 单词，我们的语法格式很简单，只包括：标识符，数字，数学运算符，括号和大括号等，我们将通过 Flex 来生成 词法分析器 的源码，给 Flex 使用的规则文件 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 部分用来定义构成单词的规则，可以看到每条规都是一个 正则表达式 和 动作，很直白，就是 词法分析器 发现了匹配的 单词 后执行相应的 动作 代码，大部分只要返回 单词 给调用者就可以了;第 3 部分可以定义一些函数，也会原样复制到生成的源码中去，这里我们留空没有使用。

现在我们可以通过调用 Flex 生成 词法分析器 的源码：

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

生成的　lexical.cpp　里会有一个 yylex() 函数供　语法分析器　调用;你可能发现了，有些宏和变量并没有被定义(如TEXTERN，yylval，yytext 等)，其实有些是 Flex 会自动定义的内置变量(如 yytext)，有些是后面 语法分析器 生成工具里定义的变量(如 yylval)，我们后面会看到。

语法分析器

语法分析器 的作用是构建 抽象语法树，通俗的说 抽象语法树 就是将源码用树状结构来表示，每个节点都代表源码中的一种结构;对于我们要实现的语法，其语法树是很简单的，如下：

现在我们使用 Bison 生成 语法分析器 代码，同样 Bison 需要一个规则文件，我们的规则文件 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.

是不是发现和 Flex 的规则文件很像呢?确实是这样，它也是分 3 个部分组成，同样，第一部分的 C++ 代码会被复制到生成的源文件中，还可以看到这里通过以下这样的语法定义前面了 Flex 使用的宏：

 
 
    
  
  
  1. %token  TLPAREN TRPAREN TLBRACE TRBRACE TCOMMA
    2.

比较不同的是第 2 部分，不像 Flex 通过 正则表达式 通过定义规则，这里使用的是 巴科斯范式(BNF: Backus-Naur Form) 的形式定义了我们识别的语法结构。如下的语法表示函数：

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

可以看到后面大括号中间的也是 动作 代码，上例的动作是在 抽象语法树 中生成一个函数的节点，其实这部分的其他规则也是生成相应类型的节点到语法树中。像 NFunctionDeclaration 这是一个我们自己定义的节点类，我们在 ast.h 中定义了我们所要用到的节点，同样的，我们摘取一段代码如下：

 
 
    
  
  
  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)，参数列表(arguments)，函数体(block) 这些成员，在语法分析阶段会设置好这些成员的内容供后面的 目标码生成 阶段使用。还可以看到有一个 codeGen() 虚函数，你可能猜到了，后面就是通过调用它来生成相应的目标代码。

我们可以通过以下命令调用 Bison 生成 语法分析器 的源码文件，这里我们使用 -d 使头文件和源文件分开，因为前面 词法分析器的源码使用了这里定义的一些宏，所以需要使用这个头文件，这里将会生成 syntactic.cpp 和 syntactic.hpp：

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

目标码生成

这是最后一步了，这一步的主角是前面提到 LLVM，LLVM 是一个构建编译器的框架系统，我们使用他遍历 语法分析 阶段生成的 抽象语法树，然后为每个节点生成相应的 目标码。当然，无法避免的是我们需要使用 LLVM 提供的函数来编写生成目标码的源码，就是实现前面提到的虚函数 codeGen()，是不是有点拗口?不过确实是这样。我们在 gen.cpp 中编写了不同节点的生成代码，我们摘取一段看一下：

 
 
    
  
  
  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 的官网学习一下。

至此，我们所有的工作基本都做完了。简单回顾一下：我们先通过 Flex 生成 词法分析器 源码文件 lexical.cpp，然后通过 Bison 生成 语法分析器 源码文件 syntactic.cpp 和头文件 syntactic.hpp，我们自己编写了 抽象语法树 节点定义文件 ast.h 和 目标码生成文件 ast.cpp，还有一个 gen.h 包含一点 LLVM 环境相关的代码，为了输出我们程序的结果，还在 printi.cpp 里简单的通过调用 C 语言库函数实现了输出一个整数。

对了，我们还需要一个 main 函数作为编译器的入口函数，它在 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) 来直接运行代码，没有链接的过程。

现在我们可以用这些文件生成我们的编译器了，需要说明一下，因为 词法分析器 的源码使用了一些 语法分析器 头文件中的宏，所以正确的生成顺序是这样的：

 
 
    
  
  
  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.

可以看到最后正确输出了期望的结果，至此我们简单的编译器就完成了。

本文名称：实现一个简单的编译器
网页地址：http://www.csdahua.cn/qtweb/news10/23760.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网

成都快上网为您推荐相关内容

网页设计公司知识

分类信息网

腾讯云虚拟主机　　 　成都网络推广　　 　普格博源建站　　 　成都做网站　　 　云锦斋建筑　　 　德阳电信服务器托管　　 　宜宾网站设计　　 　宣传册设计　　 　温江做网站公司　　 　温江电信机房　　 　成都酒店服定制　　 　led无边发光字　　 　成都网站制作　　 　香港云主机　　 　重庆托管服务器　　 　清舞人间　　 　成都添翼二手车　　 　柔性防护网　　 　外贸营销网站建设　　 　手机网站制作