学习编译原理有什么好的书籍? 第1页

看不懂不要慌，我也看不懂（逃

• Engineer a Compiler： 超级棒，强烈推荐！尤其是IR、代码生成、优化这方面
• Static Single Assignment Book：如果用了SSA的话，这就是 "The SSA book"，感觉当时同一节要读好几遍才能明白
• Compilers： 又名龙书，感觉 top-down parsing 也就是讲 recursive descent parser 的那一章感觉还不错，但其他的部分感觉一般，不是很好懂
• Modern Compiler Implementation in Java/C/ML：又名虎书，我们当时的教科书就是这本的 Java 版，但是可能是我太弱了，这本书完全看不懂。我觉得它 IR 首先就长得很奇怪，我不太能接受这种树形的 IR。
• Parsing Techniques： 硬核 parser，我没看过，但大家都在推荐就是了。但我觉得 parsing 不如代码生成和优化有意思，所以没怎么花时间在 lexer/parser 上面。
• The Definitive ANTLR 4 Reference：如果你像我一样偷懒直接用 ANTLR 来做 lexer/parser 的话，可以看一眼这个。太长不想看的话，我之前也有两篇关于 ANTLR 的笔记：（一）（二）
• 我大三教编译器的时候还有一些其他的资源在我们课程的网站上，有需要的话也可以看看：Compiler 2017 - ACM Class Wiki

补充说明一下我当时写编译器的过程。这里感恩一下 @RednaxelaFX，我在写编译器的时候有好多不懂的地方，于是问了R大好多弱智问题，R大非常耐心地给我解答。

• 心理准备
• 先看了看龙书关于 recursive descent parser 的介绍，先写了一个计算器，大概明白了简单的 LL(1) top-down parser 怎么写的了
• 但是我又不想花太多时间在 parser 上面，所以就学了学 ANTLR，又用 ANTLR 写了个计算器。学习了 visitor pattern 和 listener pattern
• 然后就正式开始写编译器了
• 前端：parsing
• 首先搞定语法，这一步参考了 ANTLR 官方的语法例子里面的 Java 语法和 C++ 语法
• 前端：abstract syntax tree
• 设计了一下 AST
• 把 ANTLR 生成的 concrete syntax tree 转成 AST
• 写了一个小工具把 AST 打印出来，肉眼看 AST 长得对不对
• 做 semantic check，主要是建立符号表以及检查类型对不对，还有一些其他杂七杂八的语义检查
• 有个事情我没有做，但是大家有需要的话可以做一做：就是写一个跑在 AST 上面的 interpreter。这样一来，你可以跑程序了，你觉得很好玩很开心；二来你可以检查生成的 AST 是不是正确的
• 前端：intermediate representation
• 仔细地看了看 EaC 里面关于 IR 的章节
• 设计了一下 IR，这一步纠结了好久，不像 AST 当时一下子就搞定了
• 把 AST 转成 IR，这一步比较有意思的是控制流（if/for/while）的生成以及短路求值
• 写了一个跑在 IR 上面的 interpreter，用来检查到目前为止的所有变换都是正确的
• 后端：code generation
• 仔细地看了看 EaC 里面关于代码生成的章节
• 找 @游宇榕 大大拷贝了一份 builtin function 的实现，因为我实在是太懒了，而且我觉得这不是编译器这个课的重点
• 写了一个假的寄存器分配，也就是给每个变量分配一个栈上面的地址，每次要读一个变量就从栈上 load 到寄存器上，每次要写一个变量就把寄存器的值写到
• 把 IR 转成 MIPS 汇编，因为我的IR跟目标语言很接近，所以这一步比较简单
• 接下来当然是愉快地在 MIPS 上面跑啦，检查一下是不是到目前为止的所有变换都是正确的
• 到这里一个编译器已经从头到尾完成啦，开心，撒花！
• 后端：register allocation
• 仔细地看了一下 EaC 里面关于寄存器分配的章节
• 看到 local bottom up allocator 好像很简单，于是写了一个。跑了跑，发现指令数确实下降了。
• 写了一个 liveness analysis，为图染色做准备
• 终于做好了思想准备，写了 graph coloring allocator，发现效果非常明显，非常开心
• 优化：杂项
• 其实我留给优化的时间不是很多（太菜了学不会），大概就随便写了一些，比方说
• inlining
• 在生成 IR 的时候把 print 相关的操作优化了一下
• 这个不具备普适性，但是在我们这个课程里面效果非常明显
• 原因是尽管我们的目标语言有 print(str) 和 printInt(num) 这两种输出方法，但是我们的源语言规定了只有 print(str) 这一种输出方式，所以说就需要很多额外的字符串转换和字符串拼接操作
• 这里做了一些针对性的 hack 能显著地减少那些产生大量输出的程序所需的指令数
• print(A + B + C); => print(A); print(B); print(C);
• print(toString(i)); => printInt(i);
• 优化：static single assignment
• 虽然说 SSA 很厉害，但真的是个很大的话题啊（太菜了学不会）
• 仔细读了读 The SSA Book 关于转入转出 SSA 形式的的章节
• 实现了一些在 SSA 上面的简单的优化
• naive dead code elimination
• simple constant propagate
• 做 presentation