学习编译原理的脉络

(旧文整理)

阿男老师,我学过编译原理,研究生也上过形式语言自动机的课,有一定的理论基础了,但是编译原理的技术是个短板,该怎么下手呢?谢谢老师。

答:这个问题在之前的文章中写过很多,但是没有集中在一起讲过,这里就集中讲一下。

首先编译原理是一个很大的范畴,需要学习的领域很多,总的来讲可以分为「前端」和「后端」。

「前端」是用来处理 Context Free Language ,把 text 转化成 tokens ,然后再把 tokens 通过 syntax rules 转化成 AST 的过程。

其中把 text 转化成 tokens ,一般用到的技术是 Regular Expression ,也就是「正则表达式」,背后对应的是无状态的自动机 NFA , NFA 可以转化为 DFA 。

然后, tokens 根据 syntax rules 进行 semantic analysis 的过程,是通过 parser 来完成的。

因为 context free language 需要分析文本前后的联系,也就是所谓代码的内在关系,所以必须用到内存,但不必用到随机存取内存,因此就在无状态自动机基础上加上 stack memory ,变成 Pushdown Automaton ,也就是 PDA ,下推自动机。

而我们把语言设计的范围限定在 Deterministic context-free grammars 这里,那么就可以使用 Deterministic Pushdown Automaton 进行分析。

1965年,Donald Knuth发明了 LR(k) parser 并证明了 LR(k) grammar 可以表示任何 Deterministic context-free language 。

Parser要学的东西主要是这里,这块人类研究的比较透彻,而且也不怎设计具体的硬件实现等等。所以大家可以重点把这里学好。

这块推荐一本书:

书名叫做 Parsing Techniques: A Practical Guide (Monographs in Computer Science) 2nd Edition 。关于Parser,你需要看这本书。

关于正则表达式的实现,看的文章:

-https://www.douban.com/note/tags/Parsing?people=weinanli-

接下来我们说一说「后端」吧。「后端」就是把 AST 转化成实际的目标代码。这里面用到的技术就是万花筒了,而且面对的实际情况也是五花八门。

为什么呢?因为目标代码决定了具体实现。比如,如果目标代码是汇编语言,那么汇编语言就是和CPU打交道,每种CPU的架构不同,需要生成的汇编代码不同。

当然我们常用的是Intel架构的CPU,那么把源代码最终转化成目标代码的时候,就要考虑变量的寄存器分配,内存管理,对操作系统接口的调用,等等。

这些知识和Parser那块用到的太不一样了,当然有些算法上可能有可以共用的部分,但是,更多来自于对目标平台的知识掌握。如果你写一个C语言的compiler,最终生成汇编代码,如果你不了解操作系统和Intel的CPU架构,那几乎是不可能完成「后端」的实现的。

此外,目标代码还可能是虚拟机的代码,比如Java的代码最终要编译成 JVM 上面的 bytecode ,那么你要是实现Java的compiler,就需要学习 JVM 这个虚拟机的架构,以及 bytecode 的知识。

当然,通用的知识还是有的,因为compiler的目标代码一般都比较低层,不管是Intel的CPU上运行的汇编代码,还是JVM虚拟机bytecode,都会遇到内存管理,寄存器分配等方面的问题。

这些地方的知识,就是操作系统和硬件架构的知识,以及很多不同算法的综合应用,这些地方需要常年大量系统的综合学习,也是在给大家写的系列文章在做的事情。

后端这块不可能有一本书来教你全部的知识,但是有一些通用的知识还是可以学习的,就推荐这本吧:

关于编译原理的学习脉络,就讲这么多。而且自己在长期写文章,大家一直跟下去也会有收获。