写给前端的零基础编译原理科普

Nealyang

发布于 2021-04-20 16:03:56

8630

发布于 2021-04-20 16:03:56

本文是 @神说要有光对编译小白 ssh 的一次答疑解惑，很适合零基础的新手第一次了解编译原理的概念，故分享出来。近些年，编译原理在前端领域的应用越来越多，大家比较熟悉的有工程化领域各种转译器：babel、typescript、eslint、terser、prettier、postcss、posthtml、taro、vue template compiler 等。由此来看，在前端生涯的路上，难以避免的要遇到编译原理这座大山。以这篇文章为起点，开始你的编译原理之旅吧~

昊昊是一个前端工程师，最近涉及到工程化领域，想了解一些编译的知识。恰好我比他研究的早一些，所以把我了解的东西给他介绍了一遍，于是就有了下面的对话。

介绍一下自己，大家可以叫我神光，17 年毕业，目前就职于阿里高德的跨端架构组，做前端工程化相关的建设，包括 builder 和 ide 等。

大家也可以在知乎-神说要有光[1]关注我。

前端为什么要学编译原理？

昊昊：编译原理这么深入的东西，前端有必要学吗？

我：学习编译原理对前端来说，大概想了这么几个好处，当然实际上肯定远远不止这些：

babel、typescript、postcss、posthtml、prettier、eslint、stylelint、taro、vue template compiler，jsx 等的转译器的深入掌握
JS 解释器比如 v8 的原理的掌握，甚至自己写一个解释器
wasm 是其他语言编译到 wasm 字节码的，掌握这个也需要懂编译
dart 既可以 JIT 又可以 AOT，要理解它的原理也要懂编译
需要自己实现 dsl 的时候，也要懂编译原理
ide 的插件，language server provider 的实现需要懂 parser，懂编译原理

什么是编译啊？

昊昊：最近想了解一些编译的东西，光哥，编译到底是什么啊？

我：编译啊就是一种转换技术，从一门编程语言到另一门编程语言，从高级语言转换成低级语言，或者从高级语言到高级语言，这样的转换技术。

昊昊：什么是高级语言，什么是低级语言啊？

我：低级语言是与机器有关的，涉及到寄存器、cpu 指令等，特别“低”，描述具体在机器上的执行过程，比如机器语言、汇编语言、字节码等。高级语言则没有这些具体执行的东西，主要用来表达逻辑，而且提供了条件、循环、函数、面向对象等特性来组织逻辑，然后通过编译来把这些描述好的高级语言逻辑自动转换为低级语言的指令，这样既能够方便的表达逻辑，又不影响具体执行。说不影响执行也不太对，因为如果直接写汇编，能写出效率最高的代码，但是如果是高级语言通过编译来自动转换为低级语言，那么就难以保证生成代码的执行效率了，需要各种编译优化，这是编译领域的难点。

其实想想，我们把脑中的想法，把制订好的方案转换为高级语言代码，这个过程是不是也是转换，可不可以自动化呢，这就涉及到 ai 了。现在有理解需求文档生成代码的智能化技术的研究方向。

昊昊：那具体是怎么转换的呢？

我：要转换首先得了解转换的双方，要转换的是什么，转换到什么。比如高级语言到高级语言，要转换的是字符串，按照一定的格式组织的，这些格式分别叫做词法、语法，整体叫做文法，那要转换的目标呢，目标如果也是高级语言那么要了解目标语言的格式，如果目标是低级语言，比如汇编，那要了解每条指令时干啥的。然后就要进行语义等价的转换，注意这个“语义等价”，通过一门语言解释另一门语言，不能丢失或者添加一些语义，一定要前后一致才可以。

知道了转换的双方都是什么，就可以进行转换了，首先得让计算机理解要转换的东西，什么叫“计算机理解“呢？就是把我们规定的那些词法、语法格式告诉计算机，怎么告诉呢？就是数据结构，要按照一定的数据结构把源码字符串解析后的结果组织起来，计算机就能处理了。这个过程叫做 parse，要先分词，再构造成语法树。

其实不只是编译领域需要“理解”，很有很多别的领域也要“理解”：

全文搜索引擎也要先把搜索的字符串通过分词器分词，然后根据这些词去用同样分词器分词并做好索引的数据库中去查，对词的匹配结果进行打分排序，这样就是全文搜索。

人工智能领域要处理的是自然语言，他也要按照词法、语法、句法等等去“理解”，变成一定的数据结构之后，计算机才懂才能处理，然后就是各种处理算法的介入了。

分词是按照状态机来分的，有限状态机 DFA，这个是干啥的，为啥分词需要它，我知道你肯定有疑问。因为词法描述的是最小的单词的格式，比如标识符不能以数字开头，然后后面加字母数字下划线等，这种，还有关键字 if、while、continue 等，这些不能再细分了，再细分没意义啊。分词就是把字符串变成一个个的最小单元的不能再拆的单词，也叫 token，因为不同的单词格式不同，总不能写 if else 来处理不同的格式吧。其实还真可以，wenyan 就是 if else，吐槽一下。但是当有 100 中单词的格式要处理，全部写成 if else，我的天，那代码还能看么。所以要把每个单词的处理过程当成一种状态，处理到不同的单词格式就跳到不同的状态，跳转的方式自然是根据当前处理的字符来的，处理一个字符串从开始状态流转到不同的状态来处理，这样就是状态自动机，每个 token 识别完了就可以抛出来，最终产出的就是一个 token 数组。没错，就像你说的吃豆子一样。其实状态也不只一级的，你想想比如一个 html 标签的开始标签，可以作为一个状态来处理，但这个状态内部又要处理属性、开始标签等，这就是二级状态，属性又可以再细分几个状态来处理，这是三级状态，这是分治的思想，一层层的处理。

分词之后我们拿到了一个个的单词，之后要把这些单词进行组装，生成 ast，为啥一定要 ast 呢？我知道你肯定想问。其实高级语言的代码都是嵌套的，你看低级语言比如汇编，就是一条条指令，线性的结构，但是高级语言呢，有函数、if、else、while 等各种块，块之间又可以嵌套。所以自然要组织成一棵树形数据结构让计算机理解，就是 Abtract Syntaxt Tree，语法树、而且是抽象的，也就是忽略了一些没有含义的分隔符，比如 html 的<、>、</等字符，js 的{ }() [] ;就是细节，不需要关心，注释也会忽略掉，注释只是分词会分出来，但是不放到 ast 里面。

怎么组装呢，还是嵌套的组装，那是不是要递归组装，是的，你想的没错需要递归，不只是这里的 ast 组装需要递归，后面的处理也很多递归，除非到了线性的代码的阶段，就像汇编那样，你递归啥，没嵌套的结构可以递归了。词法我们刚才分析了，就是一个个的字符串格式，语法呢，是组装格式，是单词之间的组合方式。这也是为啥我们刚刚要先分词了，要是直接从字符串来组装 ast，那么处理的是字符串级别，而从 token 开始是单词级别，这就像让你用积木造个城堡，但是积木也要你自己用泥巴造，那你怎么造呢，可以先把一个个积木造好，然后再去组装成城堡，也可以边造积木边组装。不过小汽车的话你可以边制作积木，边组装，城堡级别的边做积木边组装你能理清要造啥积木么，就很难，所以还是要看情况。用这两种方式来做 parser 的都有，简单的可以边词法分析，分析出热乎乎的单词然后马上组装到 ast 中，比如 html、css 这种，但是像 js、c++这种，如果不先分词，直接从字符串开始造 ast，我只能说太生猛了。

说了半天积木和组装，那么怎么组装呢，从左到右的处理 token，遇到一个 token 怎么知道他是啥语法呢，这就像怎么知道一块积木是属于那个部件的。也有两种思路，一种是你先确定这个积木是属于那个部件，然后找到那个部件的图纸，按照图纸来组装，另一种是你先组装，组装完了再看看这个是啥部件。这就是两种方式，先根据一两个积木确定是哪个部件，再按照图纸组装这个部件，这种是 ll 的方式，先组装，组装完了看看是啥部件，这种是 lr 的方式。ll 的方式要确定组装的是啥 ast 节点要往下看几个，根据要看几个来确定组装的是什么就分别是 LL(1)，LL(2)等算法。ll 也就是递归下降，这是最简单的组装方式，当然有人觉得 lr 的方式也挺简单。ll 有个问题还必须得用 lr 解决，那就是递归下降遇到了左边一直往下递归不到头的情况，要消除左递归，也就是你按照图纸来组装搞不定的时候，就先组装再看看组装出来的是啥吧。这其实和人生挺像的，一种方式是往下看两步然后决定当前怎么走，另一种方式是先走，走到哪步再说。其实我就属于第二种，没啥计划性。

经过词法、语法分析之后就产生了 ast。用一棵树形的数据结构来描述源代码，从这里开始就是计算机可以理解的了，后续可以解释执行、可以编译转换。不管是解释还是编译都需要先 parse，也就是要先让计算机理解他是什么，然后再决定怎么处理。

后面把树形的 ast 转换为另一个 ast，然后再打印成目标代码的字符串，这是转译器，把 ast 解释执行或者专成线性的中间代码再解释执行，这是解释器，把 ast 转成线性中间代码，然后生成汇编代码，之后做汇编和链接，生成机器码，这是编译器。

编译器是咋处理 AST 的？

昊昊：光哥，那编译器是怎么处理 ast 的啊？

我：有了 ast 之后，计算机就能理解高级语言代码了，但是编译器要产生低级语言，比如汇编代码，直接从 ast 开始距离比较远。因为一个是嵌套的、树形的，一个是线性的、顺序的，所以啊，需要先转成一种线性的代码，再生成低级代码。我觉得 ast 也可以算一种树形 IR，IR 是 immediate representation 中间表示的意思。要先把 AST 转成线性 IR，然后再生成汇编、字节码等。

咋翻译，树形的结构咋变成线性的呢？明显要递归啊，按照语法结构递归 ast，进行每个节点的翻译，这叫做语法制导翻译，用线性 IR 中的指令来翻译 AST 节点的属性。每个节点的翻译方式，if 咋翻译、while 咋翻译等可以去看下相关资料，搜中间代码生成就好了。

但是 ast 不能上来就转中间代码。

昊昊：为啥，ast 不就能表示源码信息了么，为啥不能直接翻译成线性 ir？

我：因为还没做语义检查啊，结构对不一定意思对，就像“昊昊是只猪”，这个符合语法吧，但是语义明显不对啊，这不是骂人么，所以要先做语义检查。还有就是要推导出一些信息来，才能做后续的翻译。

语义分析要检查出语义的错误，比如类型是否匹配、引用的变量是否存在、break 是否在 while 中等，主要要做作用域分析、引用消解、类型推导和检查、正确性检查等。

作用域分析就是分析函数、块等，这些作用域内的变量都有啥，作用域之间的联系是怎样的，其实作用域是一棵树，从顶层作用域到子作用域可以生成一个树形数据结构。我记得有个做 scope 分析的 webpack 插件，他是把模块也给链接起来了，形成了一个大的 scope graph，然后做分析。

作用域中有各种声明，要把它们的类型、初始值、访问修饰符等信息记录下来，保存这个信息的结构叫符号表，这相当于是一个缓存，之后处理这个符号的时候直接去查符号表就行，不用再次从 ast 来找。

引用消解呢就是对每个符号检查下是否都能查找到定义，如果查找不到就报错。类型方面你比较熟，js 的源码中肯定不可能都写类型，很多地方可以直接推导出来，根据 ast 可以得出类型的声明，记录到符号表中，之后遍历 ast，对各种节点取出声明时的类型来进行检查，不一致就报错。还有其他一些琐碎的检查，比如 continue、break 只能出现在 while 中等等一些检查。

昊昊：语义分析我懂了，就是检查错误和记录一些分析出的信息到符号表，那语义分析之后呢？

语义分析之后就代表着程序已经没有语法和语义的错误了，可以放心进行各种后续转换，不会再有开发者的错误。之后先翻译成线性 IR，然后对线性 IR 进行优化，需要优化就是因为自动生成的代码难免有很多冗余，需要把各种没必要的处理去掉。但是要保证语义不变。比如死代码删除、公共子表达式删除、常量传播等等。

线性 IR 的分析要建立流图，就是控制流图，控制流就是根据 if、while、函数调用等导致的程序跳转，把顺序执行的代码和跳转到的代码之间连接起来就是一个图，顺序执行的代码看成一个整体，叫做基本快。之后根据这个流图做数据流分析，也就是分析一个变量流经了那些代码，然后基于这些做各种优化。

这个部分叫做程序分析，或者静态分析，是一个专门的方向，可以用于代码漏洞的静态检查，可以用于编译优化，这个是比较难的。研究这个的博士都比较少。国内只有北大和南大开设程序分析课程。

优化之后的线性 IR 就可以生成汇编代码了，然后通过汇编器转成机器码，再链接一些标准库，比如 v8 目录下可以看到 builtins 目录，这里就是各种编译好的机器码文件，可以静态链接成一个可执行文件。

昊昊：哦，感觉汇编和链接这两步前端接触不到啊。

我：对的，因为 js 是解释型语言，直接从源码解释执行，不要说 js 了，java 的字节码也不需要静态链接。像 c、c++这些生成可执行文件的才需要通过汇编器把代码专成机器码然后链接成一个文件。而且如果目标平台有这些库，那么不需要静态链接到一起，可以动态链接。你可能听过.dll 和.so 这就分别是 windows 和 linux 的用于运行时动态加载的保存机器码的文件。

你说的没错，前端领域基本不需要汇编和链接，就算是 wasm，也是生成 wasm 字节码，之后解释执行。前端主要还是转译器。

转译器是咋处理 AST 的？

昊昊：那转译器在 ast 之后又做了哪些处理呢？

我：转译器的目标代码也是高级语言，也是嵌套的结构，所以从高级语言到高级语言是从树形结构到树形结构，不像翻译成低级的指令方式组织的语言，还得先翻译成线性 IR，高级到高级语言的转换，只需要 ast，对 ast 做各种转换之后，就可以做代码生成了。

昊昊：我说呢，我就没听说 babel 中有线性 IR 的概念。

我：对的，不管是跨语言的转换，比如 ts 转 rust，还是同语言的转换 js 转 js 都不需要线性结构，两棵树的转换要啥线性中间代码啊。所以一般转译器都是 parse、transform、generate 这 3 个阶段。

parse 广义上来说包含词法、语法和语义的分析，狭义的 parse 单指语法分析。这个不必纠结。

transform 就是对 ast 的增删改，之后 generator 再把 ast 打印成字符串，我们解析 ast 的时候把[]{} () 等分隔符去掉了，generate 的时候再把细节加回来。

其实前端领域主要还是转译器，因为主流 js 引擎执行的是源代码，但是这个源代码和我们写的源代码还不太一样，所以前端很多源码到源码的转译器来做这种转换，比如 babel、typescript、terser、eslint、postcss、prettier 等。

babel 是把高版本 es 代码转成低版本的，并且注入 polyfill。typescript 是类型检查和转成 js 代码。eslint 是根据规范检查，但--fix 也可以生成修复后的代码。prettier 也是用于格式化代码的，比 eslint 处理的更多，不只限于 js。postcss 主要是处理 css 的，posthtml 用于处理 html。相信你也用过很多了。taro 这种小程序转译器就是基于 babel 封装的。

解释器是咋处理 AST 的？

昊昊：哦，光哥，我大概知道编译器和转译器都对 ast 做了啥处理了，这俩都是生成代码的，那解释器呢？

我：对，首先转译器也是编译器的一种，只不过比较特殊，叫做 transpiler，一般的编译器叫做 compiler。解释器和编译器的区别确实是是否生成代码，提前编译成机器代码的叫做 AOT 编译器，运行时编译成机器代码的叫做 JIT 编译器，

解释器并不生成机器代码，那它是怎么执行的呢？知道你肯定有疑问。其实解释器是用一门高级语言来解释另一门高级语言，比如 c++，一般都用 c++来写解释器，因为可以做内存管理。用 c++来写 js 解释器，像 v8、spidermonkey 等都是。我们在有了 ast 并且做完语义分析之后就可以遍历 ast，然后用 c++来执行不同的节点了，这种叫做 tree walker 解释器，直接解释执行 ast，v8 引擎在 17 年之前都是这么干的。但是在 17 年之后引入了字节码，因为字节码可以缓存啊，这样下次再直接执行字节码就不需要 parse 了。字节码是种线性结构，也要做 ast 到线性 ir 的转换，之后在 vm 上执行字节码。

一般解释线性代码的比如汇编代码、字节码等这种的程序才叫做虚拟机，因为机器代码就是线性的，其实从 ast 开始就可以解释了，但是却不叫 vm，我觉得就是因为这个，和机器码比较像的线性代码的解释器才叫 vm。

不管是解释 ast 也好，还是转成字节码再解释也好，效率都不会特别高，因为是用别的高级语言来执行当前语言的代码，所以要提高效率还是得编译成机器代码，这种运行时编译就是 JIT 编译器，编译是耗时的，所以也不是啥代码都 JIT，要做热度的统计，到达了阈值才会做 JIT。然后把机器码缓存下来，当然也可能是缓存的汇编代码，用到的时候再用汇编器转成机器码，因为机器代码占的空间比较大。

可以对比 v8 来理解，v8 有 parser、ignation 解释器、turbofan 编译器，还有 gc。ignation 解释器就是把 parse 出的 ast 转成字节码，然后解释执行字节码，热度到达阈值之后会交给 turbofan 编译为汇编代码之后生成机器代码，来加速。gc 是独立的做内存管理的。

turbofan 是涡轮增压器，这个名字就能体现出 JIT 的意义。但 JIT 提升了执行速度，也有缺点，比如会使得 js 引擎体积更大，占用内存更大，所以轻量级的 js 引擎不包含 jit，这就是运行速度和包大小、内存空间之间的权衡。架构设计也经常要做这种两边都可以，但是要做选择的 trade off，我们叫做方案勾兑。

说到权衡，我想起 rn 的 js 引擎 hermes 就改成支持直接执行字节码了，在编译期间把 js 代码编译成字节码，然后直接执行字节码，这就是在跨端领域的 js 引擎的 trade off。

前端领域都有哪些地方用到编译知识？

昊昊：哦，光哥，我明白解释器、编译器、转译器都干啥的了，那前端领域都有那些地方用到编译原理的知识呢？

我：其实你也肯定有个大概的了解了，但是不够明确，我列一下我知道的。

工程化领域各种转译器：babel、typescript、eslint、terser、prettier、postcss、posthtml、taro、vue template compiler 等

js 引擎：v8、javascriptcore、quickjs、hermes 等

wasm：llvm 可以生成 wasm 字节码，所以 c++、rust 等可以转为 llvm ir 的语言都可以做 wasm 开发

ide 的 lsp：编程语言的语法高亮、智能提示、错误检查等通过 language service protocol 协议来通信，而 lsp 服务端主要是基于 parser 对正在编辑的文本做分析

自己如何实现一门语言呢？

昊昊：我学了编译原理可以实现一门语言么？

我：其实编程语言主要还是设计，实现的话首先实现 parser 和语义分析，后面分为两条路，一种是解释执行的解释器配合 JIT 编译器的路，一种是编译成汇编代码码，然后生成机器码再链接成可执行文件的编译器的路。

parser 部分比较繁琐，可以用 antlr 这种 parser 生成器来生成，语义分析要自己写，这个不太难，主要是对 ast 的各种处理。之后如果想做成编译器，可以用 llvm 这种通用的优化器和代码生成器，clang、rust、swift 都是基于它，所以很靠谱，可以直接用。如果做解释器可以写 tree walker 解释器，或者再进一步生成线性字节码，然后写个 vm 来解释字节码。JIT 编译器也可以用 llvm 来做。要把 ast 转成 llvm ir，也是树形结构转线性结构，这个还是编译领域很常见的操作。

其实编译原理只是告诉你怎么去实现，语言设计不关心实现，一门语言可以实现为编译型也可以实现为解释型，也可以做成 java 那种先编译后解释，你看 hermes 不就是先把 js 编译为字节码然后解释执行字节码么。语言不分编译解释，这个概念要有，c 也有解释器，js 也有编译器，我们说一门语言是编译型还是解释型主要是主流的方式是编译还是解释来决定的。

编程语言可以分为 GPL 和 DSL 两种。

GPL 是通用编程语言，它是图灵完备的，也就是能够描述任何可计算问题，像 c++、java、python、go、rust 等这些语言都是图灵完备的，所以一门语言能实现的另一门语言都能实现，只不过实现难度不同。比如 go 语言内置协程实现，那么写高并发程序就简单，java 没有语言级别的协程，那么就要上层来实现。你可能听到过设计模式是对语言缺陷的补充就是这个意思，不同语言设计思路不同，内置的东西也不同，有的时候需要运行时来弥补。、

编程语言有不同的设计思路，大的方向是编程范式，比如命令式、声明式、函数式、逻辑式等，这些大的思路会导致语言的语法，内置的实现都不同，表达能力也不同。这基本确定了语言基调，后续再补也很难，就像 js 里面实现函数式，你又不能限制人家不能用命令式，就很难写出纯粹的函数式代码。

DSL 不是图灵完备的，却换取了某领域的更强的表达能力，比如 html、css、正则表达式，jq 的选择器语法等等，比较像一种伪代码，特定领域的表达能力很强，但是却不是图灵完备的不能描述所有可计算问题。

编译原理是实现编程语言的步骤要学习的，更上层的语言设计还要学很多东西，最好能熟悉多门编程语言的特性。

我该怎么学习编译原理呢？

昊昊：光哥，那我该怎么学习编译原理呢？

我：首先你要理解编译都学什么，看我上面对编译、转译、解释的科普大概能有个印象，然后查下相关资料。知道都可以干啥了之后先写 parser，因为不管啥都要先 parse 成 ast 才能被“理解”和后续处理，学下有限状态机来分词和递归下降构造 ast。推荐看下 wepack 的 wxml transpiler，lexer 部分写的还可以。这种 xml 的 parser 比较简单，适合入门。语言级别的 parser 细节很多，还是得找一个来 debug 看。不过我觉得没太大必要，一般也就写个 html parser，要是语言的，可以用 antlr 生成。转译器肯定要了解 babel，这个是前端领域很不错的转译器。

js 引擎可以尝试用 babel 做 parser，自己做语义分析，解释执行 ast 试试，之后进一步生成字节码或其他线性 ir，然后写个 vm 来解释字节码。

还可以学习 wasm 相关技术，那个是涉及到其他语言编译到 wasm 字节码的过程的。

当你学完了编译原理，就大概知道怎么实现一门编程语言了，之后想深入语言设计可以多学一些其他编程范式的语言，了解下各种语言特性，怎么设计一门表达性强的 gpl 或者 dsl。也可以进一步学习一下操作系统和体系结构，因为编译以后的代码还是要在操作系统上以进程的形式运行的，那么运行时该怎么设计就要了解操作系统了。然后 cpu 指令集是怎么用电路实现的，这个想深入可以去看下计算机体系结构。

不过，前端工程师不需要达到那种深度，但是眼界开阔点没啥坏处。