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.2 《flex与bison》中的那个sql的解析挺不错的
3.3 《自制编译器》中的cbc
3.4 llvm 文档中的Kaleidoscope
0x02 : toy compiler学习
1. 基本情况
老外写的一个简易的compiler，使用flex+bison做前端，llvm后端代码生成的一个demo。
writing-your-own-toy-compiler
代码在GitHub上可以找到
2. 项目结构
稍微复杂一些、大一些的项目，阅读之前最好搞明白项目的结构，这个toy compiler虽然代码量不大，但是最好还是搞明白结构，方便后面的阅读。
编译的流程是词法分析、语法分析、语义分析、代码生成。
根据这个过程去分(有些头文件在不同的过程中都会用到，比如node.h)：
3. 代码阅读学习
3.1 主体部分 main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
|
yyparse();
cout << programBlock << endl;
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
35
|
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的文档来看