Crafting Interpreters项目总结

最近跟着做了一个很有意思的开源项目，总结一下收获 期末周滚蛋吧QAQ

项目地址：Crafting Interpreters

这个项目将带你实现一个编程语言——Lox，并构建它的两个解释器——jlox与clox(后者似乎处于解释器和编译器的共同区域中)

相信你一定跃跃欲试了 总之，这是一个很棒的项目，还不去试试看吗(✿╹◡╹)

从源代码到运行时

相信正在阅读这篇文章的人已经接触过几门编程语言——C/C++/Java/Python等等。你或许还知道它们的源码是如何执行的：

• C/C++的代码会经过编译、链接，最终生成可以被执行的文件(机器码)；
• Java首先将源代码编译为字节码(.class)，然后在JVM中运行；
• Python(这里说的是CPython实现)，也是将源码编译为字节码后在Python解释器中运行。

但是光是知道这些似乎跟什么都不知道一样 对于在内部进行的，从源码到运行时的过程才是真正有意思的地方。

词法分析 Lexing

首先是词法分析。该过程也称扫描(Scanning)。实现这一过程的家伙叫词法分析器(lexer/lexical analyzer)。

根据名称猜测一下，它大概会将你写的源代码 (史) 掰开揉碎然后切成类似于单词的东西。

正是如此。词法分析器接受线性字符串流，并将其切分为有意义的小块，即词法单元(token)。

看下面的例子：

1

子路率尔而对曰千乘之国摄乎大国之间加之以师旅因之以饥馑由也为之比及三年可使有勇且知方也

这是高中学过的一篇文言文中的句子。我绞尽脑汁想不出什么其他更贴切的例子了QAQ 上面列出来的就是它的原文(标点是现代人为了方便阅读加的)。

你要是想读懂这段文字，首先要知道哪些字是什么意思(也就是词性，词义)。如果你将上面的句子丢进一个文言文词法分析器，那么可能得到下面的结果^[1]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

子路        (人名，主语)
率尔        (副词，形容突然或随意)
而          (连词，表转折)
对          (动词，回答)
曰          (动词，说)
千乘之国     (名词短语，指拥有千辆兵车的国家)
摄          (动词，处在……之间)
乎          (助词，相当于“于”)
大国之间     (名词短语，在大国之间)
加之以师旅   (动词短语，用军事压力威胁)
因之以饥馑   (动词短语，因饥荒导致的)
由也        (人名，主语，指孔子的学生子路)
为之        (动词，为此，做这件事)
比及        (连词，等到)
三年        (时间名词，三年)
可          (助动词，可以)
使          (动词，使得)
有勇        (形容词短语，有勇气)
且          (连词，并且)
知方        (动词短语，懂得方法)
也          (语气助词，表判断)

文言文不好，尽力了o(TヘTo)

对于编程语言来说，可能是这样的：

1
2
3
4
5
6
7
8
9
10

var a;
a = "初音ミク";

var         变量声明
a           变量 "a"
;           中括号
a           变量 "a"
=           赋值符号
"初音ミク"   字符串 "初音ミク"
;           中括号

以上就是词法分析的过程(⌒_⌒)

语法分析 Parsing

经过词法分析后，仅仅知道每个词的意思还不足以让你了解这一大堆的token想表达什么。我们还需要一个东西，能够将这些词串成真正的“句子”。也就是需要一个语法分析器(parser)

分析的过程称为解析(parsing)。这将从句法中得到语法(grammer)——将较小的token组成较大的表达式和语句。

还记得我们上一步得到的tokens吗，它现在变成了这样(我省略了句法信息)：

1

子路率尔而对曰：“千乘之国，摄乎大国之间，加之以师旅，因之以饥馑；由也为之，比及三年，可使有勇，且知方也。”

解析器生成的“句子”有下面几种表现形式

• 抽象语法树 AST(abstract syntax tree)
• 具体语法树 CST(concreate syntax tree)
• 中间表示 IR(intermediate representations)
• 字节码 Bytecode

静态分析 Static Analysis

标识符绑定与类型检查。

中间码 Intermediate Representations

中间代码与源文件和目标文件的形式都没有紧密联系，它是一种“接口”。其表示形式可能为：

• 控制流图 CFG(controll flow graph)
• 静态单赋值形式 SSA(static single assignment)
• 三地址吗 TAC(three-address code)

通过中间码，你甚至可以写一个转译器。

优化 Optimization

编译器优化技术有很多种，举例如下

• 常量折叠 (constant folding)

计算常量表达式的结果并用结果替换他们，以减少运行时计算。

原代码：

1

int x = 2 + (6 - 3) * 3;

优化后：

1

int x = 11;

公共子表达式消除 (common subexpression elimination, CSE)

它能够识别源代码中重复的部分，将重复部分提取计算结果，在将结果代会表达式中。

原代码：

1
2

int a = b * c + d;
int e = b * c - f;

优化后；

1
2
3

int t = b * c;
int a = t + d;
int e = t - f;

• 循环不变代码外提 (loop-invariant code motion)

将在循环中不变的代码(在每次循环中计算结果相同的代码)移动到循环外，以减少重复计算。

原代码：

1
2
3
4

for (int i = 0; i < 10; ++i) {
    int x = a * b;
    sum += i;
}

优化后:

1
2
3
4

int x = a * b;
for (int i = 0; i < 10; ++i) {
    sum += i;
}

• 全局值编号 (global value numbering, GVN)

• 强度降低 (strength reduction)

通过将代价较高的运算替换为代价较低的运算来提高程序效率。

原代码：
1
int a = a * 8;

优化后
1
int a = a << 3;

• 聚合标量替换 (scalar replacement of aggregates)

将聚合数据结构(如数组或结构体)中的元素替换为常量标量，以减少内存访问。

原代码：

1
2
3
4
5
6

struct {
    int x;
    int y;
} point;
point.x = 1;
point.y = 2;

优化后：

1
2

int x = 1;
int y = 2;

• 死码删除 (dead code eliminatiom, DCE)

删除不会影响程序结果的代码。

原代码：

1
2

int x = 10;
x = 20;

优化后：

1

int x = 20;

• 循环展开

将循环体重复展开来减少控制开销

原代码：

1
2
3

for (int i = 0; i < 4; ++i) {
    arr[i] = i * 2;
}

优化后：

1
2
3
4

arr[0] = 0 * 2;
arr[1] = 1 * 2;
arr[2] = 2 * 2;
arr[3] = 3 * 2;

以上是一些优化技巧^[2]

代码生成 Code Generation

你有两种选择：

1. 原生代码
   • 快
   • 架构绑定，缺乏移植性
2. 虚拟机代码(字节码)
   • 慢
   • 移植性好

还有一种选择是先生成字节码，再为每个架构写一个小型编译器将字节码编译为原生代码

虚拟机 Virtual Machine

虚拟机是一个程序。它是一个专用于字节码处理的虚拟芯片。

一个编译器的工作大约有两项：

1. 解析源代码并理解其含义。
2. 利用这些含义输出相同语义的低级指令。

运行时 Runtime

到这里，源代码已经变成了能够执行的形式。如果我们将其编译成机器码，那么只需要告诉操作系统加载可执行文件。如果我们将其编译为字节码，我们就让VM启动它。

在运行时，我们通常还需要提供一些额外支持，比如垃圾回收器(garbage collector, GC)，调试器(debugger)等在程序运行时所执行的服务

捷径

以上几乎是实现一个编程语言的每个可能阶段。但下面也有一些捷径与备选路线。

单遍编译器

一些简单的编译器将解析、分析和代码生成交织在一起。这样它们就可以在解析器中生成输出代码。

树遍历解释器

转义器

编译器与解释器