compiler学习

0x00:前言

一直想做的fuzzer涉及到很多语法相关的东西,编译原理相关的补课迫在眉睫-。- 不过也只能慢慢的来学习。这篇文章准备慢慢更新,涉及我的学习过程和对以前的大佬的一个toy compiler的学习,理论+实践才是王道。

0x01:关于学习

1. 公开课
1.1 哈工大的编译原理

陈老师讲的超级好~慢慢看,看了下,这个是基于龙书讲的,当然没有展开很多,还是需要多下功夫去看看;

1.2 中科大编译原理课程

这个也行,通俗易懂,但是个人感觉没有哈工大那个课程全面。

综合

个人感觉,概念太多,涉及的知识杂而广,所以有个大概印象,需要什么的时候再深入看会比较好一点。

2. 书
2.1 龙书
我是看不下去...好枯燥,也就下了个pdf,看公开课的时候用来当参考,一些概念记不清了就去翻一翻啥的。
2.2 《自制编译器》
这本不错,实践的一本书,不过,没有看过一些基础内容的就别看了,这本书没什么太多的基础内容介绍,就是上来就从词法分析、语法分析、代码生成一点一点地拿代码给你讲;是用java实现的一个类c语言的一个编译器。所以这本我是放在后面一点的位置再去看的,基本看完,但是需要结合去看他的代码,还需要仔细过一过。
2.3 flex与bison
这个不错两百多页的小薄本,但是内容很多,代码要好好消化,还是那句话,没有基础知识(from 龙书or公开课),就算了,要不然看到作者写的那些代码理解起来很费劲。这本只看了部分,只到sql那个分析。
2.4 现代编译器(虎书)
偏实践的一本,但是我没看 233333
2.5 Antlr4 权威指南
有一定基础,推荐看。结合antlr4可以很快上手~ 而且这个东西应用十分广泛 -。- 比如在bug hunting的部分~
3. 实践项目
3.1 一个外国人写的toy compiler,based on llvm
3.2 《flex与bison》中的那个sql的解析挺不错的
3.3 《自制编译器》中的cbc
3.4 llvm 文档中的Kaleidoscope
3.5 手把手教你构建 C 语言编译器

0x02 : toy compiler学习

1. 基本情况

老外写的一个简易的compiler,使用flex+bison做前端,llvm后端代码生成的一个demo。

writing-your-own-toy-compiler

代码在GitHub上可以找到

2. 项目结构

稍微复杂一些、大一些的项目,阅读之前最好搞明白项目的结构,这个toy compiler虽然代码量不大,但是最好还是搞明白结构,方便后面的阅读。

编译的流程是词法分析、语法分析、语义分析、代码生成。

根据这个过程去分(有些头文件在不同的过程中都会用到,比如node.h):

  • 词法分析

    tokens.l 、parser.hpp、node.h

  • 语法分析

    parser.y、node.h

  • 代码生成

    codegen.cpp、codegen.h、corefn.cpp

  • 其他

    main.cpp toy compiler的主体

    example.txt 测试用例

3. 代码阅读学习
3.1 主体部分 main.cpp
1
2
3
4
5
6
7
8
9
10
11

yyparse();
cout << programBlock << endl;
// see http://comments.gmane.org/gmane.comp.compilers.llvm.devel/33877
InitializeNativeTarget();
InitializeNativeTargetAsmPrinter();
InitializeNativeTargetAsmParser();
CodeGenContext context;
createCoreFunctions(context);
context.generateCode(*programBlock);
context.runCode();

调用yyparse解析输入,然后输出progranblock之后,使用llvm做代码生成。

3.2 词法分析

词法分析是使用flex做的,词法分析是把输入分割成token序列,在tokens.l中,定义了各种token。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
[ \t\n]                            ;
"extern" return TOKEN(TEXTERN);
"return" return TOKEN(TRETURN);
[a-zA-Z_][a-zA-Z0-9_]* SAVE_TOKEN; return TIDENTIFIER;
[0-9]+\.[0-9]* SAVE_TOKEN; return TDOUBLE;
[0-9]+ SAVE_TOKEN; return TINTEGER;

"=" return TOKEN(TEQUAL);
"==" return TOKEN(TCEQ);
"!=" return TOKEN(TCNE);
"<" return TOKEN(TCLT);
"<=" return TOKEN(TCLE);
">" return TOKEN(TCGT);
">=" return TOKEN(TCGE);

"(" return TOKEN(TLPAREN);
")" return TOKEN(TRPAREN);
"{" return TOKEN(TLBRACE);
"}" return TOKEN(TRBRACE);

"." return TOKEN(TDOT);
"," return TOKEN(TCOMMA);

"+" return TOKEN(TPLUS);
"-" return TOKEN(TMINUS);
"*" return TOKEN(TMUL);
"/" return TOKEN(TDIV);

匹配的话就是正则表达式的那种匹配原则,也就是说,在源码里遇到了对应的token,就返回{字面值,TOKEN名}这样的序列。不同的token类型,在parser.hpp中定义(宏定义)。

3.2 语法分析

这部分是使用了bison,从token序列依照提前定义好的语法规则,生成对应的ast。

规则在parser.y里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
program : stmts { programBlock = $1; }
;

stmts : stmt { $$ = new NBlock(); $$->statements.push_back($<stmt>1); }
| stmts stmt { $1->statements.push_back($<stmt>2); }
;

stmt : var_decl | func_decl | extern_decl
| expr { $$ = new NExpressionStatement(*$1); }
| TRETURN expr { $$ = new NReturnStatement(*$2); }
;

block : TLBRACE stmts TRBRACE { $$ = $2; }
| TLBRACE TRBRACE { $$ = new NBlock(); }
;

var_decl : ident ident { $$ = new NVariableDeclaration(*$1, *$2); }
| ident ident TEQUAL expr { $$ = new NVariableDeclaration(*$1, *$2, $4); }
;

extern_decl : TEXTERN ident ident TLPAREN func_decl_args TRPAREN
{ $$ = new NExternDeclaration(*$2, *$3, *$5); delete $5; }
;

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

对表达式、代码块、变量定义,都有对应的语法规则。

作者设计的ast在node.h中,对于不同的语句,对应的ast也不同,这里举例了表达式声明和变量声明的ast设计:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//表达式声明
class NExpressionStatement : public NStatement {
public:
NExpression& expression;
NExpressionStatement(NExpression& expression) :
expression(expression) { }
virtual llvm::Value* codeGen(CodeGenContext& context);
};

//变量声明,两个构造方法。
//类型 变量名
//类型 变量名 = 初始值
class NVariableDeclaration : public NStatement {
public:
const NIdentifier& type;
NIdentifier& id;
NExpression *assignmentExpr;
NVariableDeclaration(const NIdentifier& type, NIdentifier& id) :
type(type), id(id) { assignmentExpr = NULL; }
NVariableDeclaration(const NIdentifier& type, NIdentifier& id, NExpression *assignmentExpr) :
type(type), id(id), assignmentExpr(assignmentExpr) { }
virtual llvm::Value* codeGen(CodeGenContext& context);
};

class NExternDeclaration : public NStatement {
public:
const NIdentifier& type;
const NIdentifier& id;
VariableList arguments;
NExternDeclaration(const NIdentifier& type, const NIdentifier& id,
const VariableList& arguments) :
type(type), id(id), arguments(arguments) {}
virtual llvm::Value* codeGen(CodeGenContext& context);
};
3.3 代码生成(还在看)

这部分如果纯自己做的话,怕是要写好久了,如果使用llvm的话,就快很多。

这部分的代码还在看,要结合llvm的文档来看

Kommentare

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×