编译原理

编译器（compiler）

编译器的作用是将A语言转化为B语言，这里的语言指的是包含着某种语法规则的文本。

编译器的一种常见用途是将高级语言转化为低级语言，比如C语言转化为汇编语言、汇编语言转化为机器码（又叫做机器指令，或CPU指令）；除此之外编译器还能实现其他各种语言间的转化，比如TypeScript转化为JavaScript、Markdown转化为HTML等等。

编译流程

一般来说，编译器的执行流程可以被简化成如下步骤：

词法分析。使用词法分析器（lexical analyzer，或者叫扫描scanner，或者叫tokenizer），输入源代码，输出token流。
语法分析。使用语法分析器，输入token流，输出抽象语法树AST。步骤一和步骤二统称为解析器（Parser）。
语义分析。这一步包括但不仅限于对AST进行类型检查，我们拿eslint举例，在通过解析器获取AST后，它会对AST进行语义分析，当发现禁止的语法规则后就会报编译错误。
代码生成。目标代码通常是机器码（如Rust -> 机器码）、或中间表示/字节码（如Rust -> LLVM-IR或Java -> Java字节码）、或其他高级语言（如TypeScript -> JavaScript）。我们拿Babel举例，在通过解析器获取AST后，我们会遍历（Traverse）AST的节点，进行分析和对节点的转换，从而获得新的抽象语法树，再根据新的AST生成对应的语言。

一般对于像C/C++、Go、Rust这类语言而言，目标代码指的是机器码，因为其能够直接被CPU加载执行，所以在运行效率上是非常高的。不过像这种编译形式也存在着痛点，那就是由于不同机器通常对应着多种CPU指令集，我们必须针对不同环境都编译出一份能够运行的二进制产物，而LLVM是一个能够帮助我们解决该问题的热门方案。

LLVM

LLVM的全称是Low Level Virtual Machine，当然随着这个项目的不断发展它真正的作用已经超出了这个名字所表示的范畴。

简单来说这个项目是一个模块化的编译器框架，它的核心是中间表示IR（Intermediate Representation），这是一种类似汇编的底层语言（字节码也是一种中间表示）。我们拿Rust举例，它自身的编译器只是将Rust代码编译成LLVM IR，这个编译器通常被称之为编译器前端（也就是主要做词法分析、语法分析、语义分析、代码生成）；而Rustc使用LLVM作为编译器后端，实现LLVM IR到不同机器指令的生成；另外除了前端和后端，LLVM还存在着优化器的概念，它将LLVM IR作为输入并会生成更高效的LLVM IR。

解释器（Interpreter）

解释器的作用是接受指定的输入，执行相应的过程。

解释流程

词法分析。
语法分析。
语义分析。
解释执行。可以看到，解释器和编译器的实现都包括解析器，即需要实现源代码到抽象语法树的转换，区别在于最终如何处理抽象语法树。一般解释器的实现中，抽象语法树的每个节点都会存在一个eval方法，eval方法将会递归调用该节点的子节点的eval方法，并根据它们的返回值计算自身的返回值，因此我们只需要调用抽象语法树根节点的eval方法就可以执行这颗树所代表的动作。

一般如果想要自己实现简易的解释器的话，以这种AST解释器为目标或许是个不错的选择。而实际上许多主流的语言（如Java、JavaScript）的内部实现使用的并不是AST解释器，而是字节码解释器。以JavaScript（V8引擎）为例，它会首先把JavaScript解析成AST、再生成对应的字节码、之后再通过内部的Ignition解释器对字节码解释执行。

相较于使用编译器直接生成二进制产物，交由CPU直接加载执行；使用解释器的本质是CPU会先加载解释器自身的二进制代码，执行的过程中会把输入的内容解释成二进制代码再给CPU执行；如果我们使用解释器去实现解释器，比如使用JavaScript（V8引擎）实现Python，如node interpreter.js source.py，本质上来说CPU会先加载V8的代码，之后V8会把interpreter.js解释成二进制代码交给CPU执行，这段代码的执行又会把source.py解释成二进制代码交给CPU执行，由此可见为了执行这样的一段代码我们启用了两个解释器，效率明显是比较低的。

假设我们使用Rust实现字节码的解释器，从实现上看我们实现了字节码到Rust的解释，但考虑到Rust代码会被编译成二进制，所以从运行上看我们实现的是字节码到机器码的解释
假设我们使用Rust实现JavaScript的解释器，从实现上看我们实现了JavaScript到Rust的解释，但考虑到Rust代码会被编译成二进制，所以从运行上看我们实现的是JavaScript到机器码的解释
假设我们使用JavaScript实现Python的解释器，从实现上看我们实现了Python到JavaScript的解释，但考虑到JavaScript代码会被解释成二进制，所以从运行上看我们实现的是Python到机器码的解释

虚拟机

以个人的理解，虚拟机所表达的范围要比解释器更小，即虚拟机都能被称为解释器，但解释器并不都能被叫做虚拟机。一般被称为虚拟机的一大要素是它解释的源码是一种虚拟指令集（如字节码，或中间表示），虚拟机能够虚拟指令集映射为真实的机器指令执行。

通常虚拟机从实现上可以分为基于栈的虚拟机和基于寄存器的虚拟机，下文中的Java虚拟机就是基于栈的，而V8内部的Ignition则是基于寄存器的，一般来说基于栈的实现要更简单一些。

Java

Java的口号是编译一次处处运行，实现这个功能所依靠的就是JVM（Java Virtual Machine）。Java代码首先会被编译成Java字节码，在运行时Java虚拟机会对输入的Java字节码解释执行。

相比于直接由CPU执行机器码，通过虚拟机解释执行会在运行效率上稍打折扣，但虚拟机这个概念也带来了许多好处，最重要的就是抹去了目标平台的差异性。除此之外，其他的语言也可以通过被编译成Java字节码，实现整个生态的复用，这其中比较知名的语言是Kotlin。

JavaScript

JavaScript最主流的解释器/运行环境是V8引擎，它是Chrome浏览器和NodeJS的核心，V8引擎的执行流程和Java十分相似。它是在运行时接受JavaScript源码作为输入，将其解析成抽象语法树AST，AST会被传入V8的Ignition解释器生成对应的字节码，之后Ignition会对字节码解释执行。

从实现的角度上来看，V8引擎是JavaScript的解释器，而V8内部的Ignition又是JavaScript字节码的解释器（同时又是虚拟机，功能上更贴近JVM）。

即时编译（Just-In-Time Compilation）

即时编译通常指的是在运行时进行编译。事实上Java和JavaScript这对好兄弟都采用了解释器+即时编译的混合技术。我们以V8引擎为例，在Ignition不断解释执行字节码的同时，会将高频执行的代码段标记为热点代码，而V8内部的TurboFan编译器（优化编译器）就会把热点代码编译成机器码，这样在后续的执行中这段代码就不需要再被解释执行了，能够加快整体的执行效率。

另外，即时编译技术的特点是在运行时进行编译，因此能够收集到许多运行时的信息，方便进行相应的优化。

如何自制语言

上述内容以理论为主，虽说稍微加强了我们对于一些概念的理解，但现在我们依然只是站在编译原理这门课的门口而已，真要我们实战去写一门语言还是有一些困难的。不过我们的目的也不是说一定要去自制编程语言，通过简单的学习至少我们能够了解到如果要去自制一门语言的话，大概需要去做些什么。

静态编译

方案一：完全手写。那么我们至少需要做到源代码 -> AST -> 机器码 ，难点是AST到机器码的代码生成，特别是我们还需要具备能够编译到不同平台的能力。
方案二：自己只实现编译器前端，使用LLVM作为编译器后端。这应该是目标最主流的一种开发范式，Rust就是用的这种方式。我们只需要实现源代码 -> AST -> LLVM-IR即可，可以使用LLVM的生态（优化器和后端）来生成多个平台的二进制产物。

解释执行

方案一：完全手写，开发语言，只是用脚本语言实现脚本语言的话运行效率上恐怕不高。
1. 路线一：实现AST解释器，相对来说更简单，那么我们需要实现源代码 -> AST -> 解释执行
2. 路线二：实现字节码解释器，那么我们需要实现源代码 -> AST -> 字节码 -> 解释执行
方案二：复用现成虚拟机，如Java虚拟机（主流的HotSpot VM）。诸如Kotlin之类的语言就是使用这种方案，这种做法不但实现起来更加简单，更能够轻松的复用整个生态。我们需要实现源代码 -> AST -> Java字节码，Java字节码可以直接拿来在目标虚拟机上解释执行。
方案三：复用现成解释器。考虑到V8本身可以视为JavaScript的解释器，我们需要实现源代码 -> AST -> JavaScript就可以复用整个前端的生态（取名为TypeScript2）

与前端领域结合

如上所说，我们的目的并不是去自制一门语言，而是加深我们对于一些底层概念的理解。事实上，前端领域（或者说前端工程化）中有许多内容是涉及到编译原理的，通过掌握这些知识，我们能够参与到一些更加有意思的事情当中，在接下来的章节中，我将介绍如何更深入的玩耍Babel。

我们都知道Babel的主要作用是实现JavaScript/TypeScript语法的转化，它实际上由多个模块组成：

@babel/parser：babel的解析器（曾用名babylon，封装于Acorn），能够将JavaScript解析成标准（即符合estree规范）的AST。
@babel/traverse：可以用来遍历@babel/parser生成的AST，通过编写Visitor来实现各类AST操作（比如替换所有变量名）
@babel/types：类似lodash风格的工具库，主要用来搭配@babel/traverse操作AST节点（比如提供了创建AST节点的方法）
@babel/generator：我们可以根据修改后的AST生成新的JavaScript代码，以及sourceMap
@babel/core：结合以上工具实现代码的转化

信息

顺带一提，eslint使用espree（同样封装于Acorn）解析器，但@babel/parser支持对TypeScript的解析而espree并不支持。

因此如果希望eslint解析TS代码我们需要自行把eslint的解析器设置为@typescript-eslint/parser，并提供相应的插件支持@typescript-eslint/eslint-plugin（需要安装typescript模块）。

也就是说稍微麻烦的AST生成以及代码生成都有了现成的轮子，我们只需要在前人的肩膀上做一些微小的工作即可，我们只需要稍微了解一下常见的AST节点的类型定义，就可以实战写一些有意思的Visitor了，比如说简单的把所有的箭头函数都转换成普通函数（像这种单一功能的转化被称作Babel Plugin，而Presets预设则代表着多个插件的集合）

import { parse } from "@babel/parser";
import _traverse from "@babel/traverse";
import _generator from '@babel/generator';
const traverse = _traverse.default;
const generator = _generator.default

const oldCode = `
    const a = () => {
        const b = async () => {
            return () => {

            }
        }    

        return {
            fn: b,
            fn2: () => {

            }
        }
    }
`
const ast = parse(oldCode, { sourceType: 'module'})
traverse(ast, {
    ArrowFunctionExpression(path) {
        path.node.type = 'FunctionExpression'
    }
})
const { code: newCode } = generator(ast)

const a = function () {
  const b = async function () {
    return function () {};
  };

  return {
    fn: b,
    fn2: function () {}
  };
};

参考

Babel Plugin-handbook

编译原理

编译器（compiler）​

编译流程​

LLVM​

解释器（Interpreter）​

解释流程​

虚拟机​

Java​

JavaScript​

即时编译（Just-In-Time Compilation）​

如何自制语言​

静态编译​

解释执行​

与前端领域结合​

参考​