本篇文章来自于云巴技术工程师,在介绍编译器的原理之后,还手把手教你实现一个简单的编译器~
简单的说 编译器
就是语言翻译器,它一般将高级语言翻译成更低级的语言,如 GCC 可将 C/C++ 语言翻译成可执行机器语言, Java 编译器可以将 Java 源代码翻译成 Java 虚拟机可以执行的字节码。
编译器如此神奇,那么它到底是如何工作的呢?本文将简单介绍编译器的原理,并实现一个简单的编译器,使它能编译我们自定义语法格式的源代码。(文中使用的源码都已上传至 GitHub 以方便查看)。
为了简洁易懂,我们的编译器将只支持以下简单功能:
数据类型只支持整型,这样不需要数据类型符;
支持 加(+)
,减(-)
,乘(*)
, 除(/)
运算
支持函数调用
支持 extern
(为了调用 printf
打印计算结果)
以下是我们要支持的源码实例 demo.xy:
extern printi(val)
sum(a, b) {
return a + b
}
mult(a, b) {
return a * b
}
printi(mult(4, 5) - sum(4, 5))
一般编译器有以下工作步骤:
词法分析( Lexical analysis ): 此阶段的任务是从左到右一个字符一个字符地读入源程序,对构成源程序的字符流进行扫描然后根据构词规则识别 单词( Token )
,完成这个任务的组件是 词法分析器( Lexical analyzer ,简称 Lexer )
,也叫 扫描器( Scanner )
;
语法分析( Syntactic analysis ,也叫 Parsing ): 此阶段的主要任务是由 词法分析器
生成的单词构建 抽象语法树( Abstract Syntax Tree , AST )
,完成此任务的组件是 语法分析器( Parser )
;
目标码生成: 此阶段编译器会遍历上一步生成的抽象语法树,然后为每个节点生成 机器 / 字节码
。
编译器完成编译后,由 链接器( Linker )
将生成的目标文件链接成可执行文件,这一步并不是必须的,一些依赖于虚拟机运行的语言(如 Java , Erlang )就不需要链接。
对应编译器工作步骤我们将使用以下工具,括号里标明了所使用的版本号:
Flex ( 2.6.0 ): Flex 是 Lex 开源替代品,他们都是 词法分析器
制作工具,它可以根据我们定义的规则生成 词法分析器
的代码;
Bison ( 3.0.4 ): Bison 是 语法分析器
的制作工具,同样它可以根据我们定义的规则生成 语法分析器
的代码;
LLVM ( 3.8.0 ): LLVM 是构架编译器的框架系统,我们会利用他来完成从 抽象语法树
生成目标码的过程。
在 ubuntu 上可以通过以下命令安装这些工具:
sudo apt-get install flex
sudo apt-get install bison
sudo apt-get install llvm-3.8*
介绍完工具,现在我们可以开始实现我们的编译器了。
前面提到 词法分析器
要将源程序分解成 单词
,我们的语法格式很简单,只包括:标识符,数字,数学运算符,括号和大括号等,我们将通过 Flex 来生成 词法分析器
的源码,给 Flex 使用的规则文件 lexical.l 如下:
%{
#include <string>
#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();
%%
我们来解释一下,这个文件被 2 个 %%
分成 3 部分,第 1 部分用 %{
与 %}
包括的是一些 C++ 代码,会被原样复制到 Flex 生成的源码文件中,还可以在指定一些选项,如我们使用了 %option noyywrap
,也可以在这定义宏供后面使用;第 2 部分用来定义构成单词的规则,可以看到每条规都是一个 正则表达式
和 动作
,很直白,就是 词法分析器
发现了匹配的 单词
后执行相应的 动作
代码,大部分只要返回 单词
给调用者就可以了;第 3 部分可以定义一些函数,也会原样复制到生成的源码中去,这里我们留空没有使用。
现在我们可以通过调用 Flex 生成 词法分析器
的源码:
flex -o lexical.cpp lexical.l
生成的 lexical.cpp 里会有一个 yylex()
函数供 语法分析器
调用;你可能发现了,有些宏和变量并没有被定义(如 TEXTERN
,yylval
,yytext
等),其实有些是 Flex 会自动定义的内置变量(如 yytext
),有些是后面 语法分析器
生成工具里定义的变量(如 yylval
),我们后面会看到。
语法分析器
的作用是构建 抽象语法树
,通俗的说 抽象语法树
就是将源码用树状结构来表示,每个节点都代表源码中的一种结构;对于我们要实现的语法,其语法树是很简单的,如下:
现在我们使用 Bison 生成 语法分析器
代码,同样 Bison 需要一个规则文件,我们的规则文件 syntactic.y 如下,限于篇幅,省略了某些部分,可以通过链接查看完整内容:
%{
#include "ast.h"
#include <cstdio>
...
extern int yylex();
void yyerror(const char *s) { std::printf("Error: %s\n", s);std::exit(1); }
%}
...
%token <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; }
;
...
%%
是不是发现和 Flex 的规则文件很像呢?确实是这样,它也是分 3 个部分组成,同样,第一部分的 C++ 代码会被复制到生成的源文件中,还可以看到这里通过以下这样的语法定义前面了 Flex 使用的宏:
%token <token> TLPAREN TRPAREN TLBRACE TRBRACE TCOMMA
比较不同的是第 2 部分,不像 Flex 通过 正则表达式
通过定义规则,这里使用的是 巴科斯范式( BNF: Backus-Naur Form )
的形式定义了我们识别的语法结构。如下的语法表示函数:
func_decl:
ident TLPAREN func_decl_args TRPAREN block { $$ = new NFunctionDeclaration(*$1, *$3, *$5); delete $3; }
;
可以看到后面大括号中间的也是 动作
代码,上例的动作是在 抽象语法树
中生成一个函数的节点,其实这部分的其他规则也是生成相应类型的节点到语法树中。像 NFunctionDeclaration
这是一个我们自己定义的节点类,我们在 ast.h 中定义了我们所要用到的节点,同样的,我们摘取一段代码如下:
...
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);
};
...
可以看到,它有 标识符( id )
,参数列表( arguments )
,函数体( block )
这些成员,在语法分析阶段会设置好这些成员的内容供后面的 目标码生成
阶段使用。还可以看到有一个 codeGen()
虚函数,你可能猜到了,后面就是通过调用它来生成相应的目标代码。
我们可以通过以下命令调用 Bison 生成 语法分析器
的源码文件,这里我们使用 -d
使头文件和源文件分开,因为前面 词法分析器
的源码使用了这里定义的一些宏,所以需要使用这个头文件,这里将会生成 syntactic.cpp
和 syntactic.hpp
:
bison -d -o syntactic.cpp syntactic.y
这是最后一步了,这一步的主角是前面提到 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 << "no such function " << id.name << endl;
}
std::vector<Value *> 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;
}
...
看起来有点复杂,简单来说就是通过 LLVM 提供的接口来生成 目标码
,需要了解更多的话可以去 LLVM 的官网学习一下。
至此,我们所有的工作基本都做完了。简单回顾一下:我们先通过 Flex 生成 词法分析器
源码文件 lexical.cpp
,然后通过 Bison 生成 语法分析器
源码文件 syntactic.cpp
和头文件 syntactic.hpp
,我们自己编写了 抽象语法树
节点定义文件 ast.h 和 目标码
生成文件 ast.cpp,还有一个 gen.h 包含一点 LLVM 环境相关的代码,为了输出我们程序的结果,还在 printi.cpp 里简单的通过调用 C 语言库函数实现了输出一个整数。
对了,我们还需要一个 main
函数作为编译器的入口函数,它在 main.cpp 里:
...
int main(int argc, char **argv) {
yyparse();
InitializeNativeTarget();
InitializeNativeTargetAsmPrinter();
InitializeNativeTargetAsmParser();
CodeGenContext context;
context.generateCode(*programBlock);
context.runCode();
return 0;
}
我们可以看到其调用了 yyparse()
做 语法分析
,(yyparse()
内部会先调用 yylex()
做 词法分析
);然后是一系列的 LLVM 初始化代码,context.generateCode(*programBlock)
是开始生成 目标码
;最后是 context.runCode()
来运行代码,这里使用了 LLVM 的 JIT ( Just In Time )
来直接运行代码,没有链接的过程。
现在我们可以用这些文件生成我们的编译器了,需要说明一下,因为 词法分析器
的源码使用了一些 语法分析器
头文件中的宏,所以正确的生成顺序是这样的:
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
就可以完成以上过程了,正常会生成一个二进制文件 xy-complier
,它就是我们的编译器了。
我们使用之前提到实例 demo.xy 来测试,将其内容传给 xy-complier
的标准输入就可以看到运行结果了:
cat demo.xy | ./xy-complier
也可以直接通过
make test
来测试,输出如下:
...
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...
可以看到最后正确输出了期望的结果,至此我们简单的编译器就完成了。
1
lc4t 2016-11-08 11:19:14 +08:00 via iPhone
mark 下学期上编译原理看看有没有时间也去写一个~
|
3
future0906 2016-11-08 12:11:12 +08:00
这样还不是标题党?这么简单的建议器还用 Lex , Yacc , Bison 和 LLVM 。
简直跟我在大三用 OpenCV 做图形图像的大作业有异曲同工之妙。 |
4
riaqn 2016-11-08 12:27:37 +08:00 via Android
牛逼哄哄在哪里?
|
5
adadada 2016-11-08 12:34:27 +08:00 via iPhone
没看出哪牛逼了,这不就是典型的面向 llvm 的编译器开发吗?
|
7
yunbaIO OP @future0906 是编译器不是建议器哦~
|
9
zsj950618 2016-11-08 12:58:47 +08:00 1
|
11
starcraft 2016-11-08 13:05:04 +08:00 via iPhone
哪儿牛逼了 你拿 C 写一遍也比这牛逼吧。你非要牛逼为啥不自己写套简化版 lex yacc 。我就这么一说:P
|
12
20015jjw 2016-11-08 13:14:53 +08:00 via Android
不觉得很厉害 berkeley 的 cs61a 的 final project 见过吗
|
14
yunbaIO OP |
15
980502757 2016-11-08 14:23:20 +08:00
喜欢折腾的人大爱。
|
17
amustart 2016-11-08 14:32:50 +08:00
不标题党--- > 牛逼哄哄
请问你确定你没有标题党么 |
20
yunbaIO OP @amustart 哈哈,(o ゚ω゚ o),同上,在我心目中,编程写代码本身就是一件很牛逼的事情啦。
我说出了我的感受而已啦(*゚ー゚*) |
23
zhou00 2016-11-08 15:12:57 +08:00
不懂,感觉好牛逼,赞
|
24
qfdk 2016-11-08 15:32:01 +08:00 via iPhone
之前写过一个编译器 自己的语言 翻译成 js 。 用 xtext 搞最后和 eclipse 一样的效果 打包成 jar 可以命令行编译。。
|
27
qfdk 2016-11-08 15:41:51 +08:00 via iPhone
@yunbaIO http://esir.qfdk.me 甩个链接
|
31
tiancaiamao 2016-11-08 17:59:35 +08:00
|
32
yunbaIO OP @tiancaiamao 你好哇, tiancaiamao( ´∀`)σ
|
33
daimao 2016-11-08 19:10:54 +08:00 via iPhone
v2ex 真是越来越水了
恭喜 lz 重新定义了牛逼 |
34
qfdk 2016-11-08 19:28:36 +08:00 via iPhone
@yunbaIO 好久没搞这些了 看见的就看见了 这个是定义自己的奇葩语言 要是中文编程 原理一样 贴 xtext 链接吧 毕竟它是最大的贡献者
|
40
Livid MOD 用公司 Logo 当头像的 100% 都是营销号,这一点就请大大方方地承认吧。这个帖子会从 /go/create 移动到 /go/promotions
另外, Markdown 整理得很认真,这一点是值得赞的。 |
41
miao1007 2016-11-08 23:38:31 +08:00 via Android
这个不就是 DSL 吗,可以直接用 MPS
|
42
yunbaIO OP @Livid 我没否定我是营销号啊,但是这篇为技术文章不是广告贴啊,(。í _ ì。),营销号不能发技术文章,发的所有东西都要被认为是广告?这篇文章也发在了其它平台,用的也都是公司的 Logo ,但没人说广告贴、营销号。
|
43
msg7086 2016-11-09 10:52:59 +08:00
如果你要发与营销号无关的技术贴,可以用自己的账号发……
|