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的文档来看

文章目录
  1. 1. 0x00:前言
  2. 2. 0x01:关于学习
    1. 2.1. 1. 公开课
      1. 2.1.1. 1.1 哈工大的编译原理
      2. 2.1.2. 1.2 中科大编译原理课程
      3. 2.1.3. 综合
    2. 2.2. 2. 书
      1. 2.2.1. 2.1 龙书
      2. 2.2.2. 2.2 《自制编译器》
      3. 2.2.3. 2.3 flex与bison
      4. 2.2.4. 2.4 现代编译器(虎书)
      5. 2.2.5. 2.5 Antlr4 权威指南
    3. 2.3. 3. 实践项目
      1. 2.3.1. 3.1 一个外国人写的toy compiler,based on llvm
      2. 2.3.2. 3.2 《flex与bison》中的那个sql的解析挺不错的
      3. 2.3.3. 3.3 《自制编译器》中的cbc
      4. 2.3.4. 3.4 llvm 文档中的Kaleidoscope
      5. 2.3.5. 3.5 手把手教你构建 C 语言编译器
  3. 3. 0x02 : toy compiler学习
    1. 3.1. 1. 基本情况
    2. 3.2. 2. 项目结构
    3. 3.3. 3. 代码阅读学习
      1. 3.3.1. 3.1 主体部分 main.cpp
      2. 3.3.2. 3.2 词法分析
      3. 3.3.3. 3.2 语法分析
      4. 3.3.4. 3.3 代码生成(还在看)
,