简单来说，编译器就是一个语言翻译器，一般将高级语言翻译成低级语言，比如GCC可以将C/C++语言翻译成可执行的机器语言，而Java编译器可以将Java源代码翻译成Java虚拟机可以执行的字节码。编译器如此神奇，那么它是如何工作的呢？本文将简要介绍编译器的原理，并实现一个简单的编译器，可以编译出我们自定义语法格式的源代码。（本文使用的源码已上传至GitHub，方便查看）。为了简洁易懂的自定义语法，我们的编译器将只支持以下简单函数：数据类型只支持整数，所以不需要数据类型说明符；支持加(+)、减(-)、乘(*)、除(/)计算支持函数调用支持extern(以便调用printf打印计算结果)下面是我们的源码例子demo.xy想支持：externprinti(val)sum(a,b){returna+b}mult(a,b){returna*b}printi(mult(4,5)-sum(4,5))编译原理介绍一般的编译器有以下工作步骤：词法分析：这个阶段的任务是一个字符从左到右逐个字符读取源程序，扫描构成源程序的字符流，然后识别单词（Token)根据构词规则。完成这个任务的组件就是词法分析器（Lexer，简称Lexer），也叫扫描器（Scanner）；句法分析（Syntacticanalysis，也叫Parsing）：这个阶段的主要任务是根据词法分析器生成的词构建抽象语法树（AbstractSyntaxTree，AST），而完成这个任务的组件就是解析器（解析器）；目标代码生成：在这个阶段，编译器遍历上一步生成的抽象语法树，然后为每个节点生成机器码/字节码。编译器完成编译后，链接器（Linker）会将生成的目标文件链接成可执行文件。这一步不是必须的，一些依赖虚拟机运行的语言（比如Java、Erlang）不需要链接。工具介绍对应编译器的工作步骤，我们会用到以下工具，括号中标明使用的版本号：Flex(2.6.0)：Flex是Lex的开源替代品，都是词法分析器制作工具。定义的规则生成词法分析器的代码；Bison(3.0.4)：Bison是制作词法分析器的工具，它也可以根据我们定义的规则生成词法分析器的代码；LLVM(3.8.0)：LLVM是框架编译器的框架系统，我们将用它来完成从抽象语法树生成目标代码的过程。这些工具可以在ubuntu上安装，命令如下：sudoapt-getinstallflexsudoapt-getinstallbisonsudoapt-getinstallllvm-3.8*介绍完这些工具，现在我们就可以开始实现我们的编译器了。词法分析器如前所述，词法分析器需要将源程序分解成单词。我们的语法格式很简单，只包括：标识符、数字、数学运算符、括号和花括号等。我们将使用Flex来生成词法分析Flex的源代码如下：%{#include#include"ast.h"#include"syntactic.hpp"#defineSAVE_TOKENyylval.string=newstd::string(yytext,yyleng)#defineTOKEN(t)(yylval.token=t)%}%optionnoyywrap%%[\t\n];“外部”returnTOKEN（TEXTERN）；“返回”returnTOKEN（TRETURN）；[a-zA-Z_][a-zA-Z0-9_]*SAVE_TOKEN；returnTIDENTIFIER；[0-9]+SAVE_TOKEN；returnTINTEGER；“=”returnTOKEN(TEQUAL);"=="returnTOKEN(TCEQ);"!="returnTOKEN(TCNE);"("returnTOKEN(TLPAREN);")"returnTOKEN(TRPAREN);"{"returnTOKEN(TLBRACE);"}"returnTOKEN(TRBRACE);","re??turnTOKEN(TCOMMA);"+"returnTOKEN(TPLUS);"-"returnTOKEN(TMINUS);"*"returnTOKEN(TMUL);"/"returnTOKEN(TDIV);.printf("Unknownotoken!\n");yyterminate();%%解释一下，这个文件分为2%%3个部分，第1部分有%{和%}包括一些C++代码，会原样复制到Flex生成的源代码文件中，也可以指定一些选项，比如我们使用%optionnoyywrap，这里也可以定义宏用于以后使用；第2部分用于定义构成单词的规则。你可以看到每条规则都是一个正则表达式和一个动作。很直接，就是词法分析器找到一个匹配的词后，执行相应的动作代码。大部分只需要将这个词返回给调用者就可以了；一些函数可以在第3部分中定义，它们将原样复制到生成的源代码中。这里我们留空不使用。现在我们可以通过调用Flex来生成词法分析器的源代码：flex-olexical.cpplexical。在生成的 lexical.cpp 中会有一个yylex()函数供 语法分析器 调用；你可能会发现有些宏和变量没有定义（如TEXTERN、yylval、yytext等），其实有些是Flex自动定义的内置变量（如yytext），有些是变量（如yylval)稍后在语法分析器生成工具中定义，我们将在后面看到。语法分析器的作用是构建抽象语法树。一般来说，抽象语法树就是将源代码以树状结构表示，每个节点代表源代码中的一个结构；对于我们要实现的语法，其他的语法树很简单，如下：现在我们使用Bison来生成解析器代码，Bison还需要一个规则文件。我们的规则文件syntactic.y如下。限于篇幅，省略了部分内容。您可以通过链接查看完整内容：%{#include"ast.h"#include...externintyylex();voidyyerror(constchar*s){std::printf("Error:%s\n",s);std::exit(1);}%}...%tokenTLPARENTRPARENTLBRACETRBRACETCOMMA...%%program:stmts{programBlock=$1;};...func_decl:identTLPARENfunc_decl_argsTRPARENblock{$$=newNFunctionDeclaration(*$1,*$3,*$5);delete$3;};...%%是不是觉得和Flex规则文件很像？事实上，它也由3部分组成。同样的，第一部分的C++代码会被复制到生成的源文件中，也可以看到Flex使用的宏定义如下语法：%tokenTLPARENTRPARENTLBRACETRBRACETCOMMA不同的是在第二部分，与Flex通过正则表达式来定义规则不同，这里使用的是巴科斯-诺尔范式（BNF：Backus-NaurForm）的形式，它定义了我们所识别的语法结构。以下语法表示函数：func_decl:identTLPARENfunc_decl_argsTRPARENblock{$$=newNFunctionDeclaration(*$1,*$3,*$5);delete$3;};可以看到大括号中间的动作代码也是上面例子中的动作代码。在树中生成一个功能节点。事实上，这部分的其他规则也会将相应类型的节点生成到语法树中。和NFunctionDeclaration一样，这是我们自己定义的节点类。我们在ast.h中定义了我们想要使用的节点。同样，我们提取一段代码如下：...classNFunctionDeclaration:publicNStatement{public:constNIdentifier&id;VariableListarguments;NBlock█NFunctionDeclaration(constNIdentifier&id,constVariableList&arguments,NBlock&block):id(id),arguments(arguments),block(block){}virtualllvm::Value*codeGen(CodeGenContext&context);};...如你所见，它有一个标识符（id）、参数列表（arguments）、函数体（block）这些成员，这些成员的内容会在语法分析阶段设置好，以供后续目标代码生成阶段使用。还可以看到有一个codeGen()虚函数，大家可能已经猜到了，调用它就会生成相应的目标代码。我们可以使用如下命令调用Bison来生成解析器的源代码文件。这里我们使用-d来将头文件和源文件分开。因为前面词法分析器的源码使用了这里定义的一些宏，所以我们需要用到这个头文件。Syntactic.cpp和syntactic.hpp将在这里生成：bison-d-osyntactic.cppsyntactic.yobjectcodegeneration这是最后一步。这一步的主角就是前面提到的LLVM。LLVM是用于构建编译器的框架系统。我们用它来遍历语法分析阶段生成的抽象语法树，然后为每个节点生成对应的目标代码。当然，不可避免的是我们需要使用LLVM提供的函数来编写源代码来生成目标代码，也就是实现上面提到的虚函数codeGen()。是不是有点啰嗦？但这是真的。我们在gen.cpp中写好了不同节点的生成代码，我们来看一下：...Value*NMethodCall::codeGen(CodeGenContext&context){Function*function=context.module->getFunction(id.name.c_str());if(function==NULL){std::cerr<<"nosuchfunction"<args;ExpressionList::const_iteratorit;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<<"Creatingmethodcall:"<
