最近在看基于DSL的热更新框架，瞬间对编译器原理产生了浓厚的兴趣。百度、知乎了很久，给自己定了一套学习路径(🐶)。龙书，虎书，鲸书这些是必看的，但是书还在路上。《Engineering a Compiler》和《游戏脚本高级编程》看起来口碑也不错。不过我的入门，从一本叫《两周自制脚本语言》开始（以下简称《两周》）。希望这个主题会有第二篇、第三篇….吧。
0x01.前言
在计算机的世界里，计算机的底层执行逻辑一定是通过二进制的命令结合硬件电路实现的。硬件看不懂我们的代码，它们只知道把高电压当成1，低电压当成0，执行过程就是一次次放电过程。所以程序本质上是一串很长很长的的二进制数字，由于不易阅读，人们常通过汇编语言程序来表达这个巨大的数字。程序只有载入内存后才能通过硬件执行。因此，用户在实际使用的时候，必须先通过软件从磁盘文件中读取机器语言程序，再将复制到内存中，这类程序称不上时语言处理器，通常称为操作系统。
而计算机是如何将高级语言变成机器语言的呢？这里就需要用到语言处理器，其实语言处理器在我们的工作中时时刻刻都在接触。这之中大致分两种:
-
编译器：将某种语言写成的程序转换成另一种语言的程序。通常会将源程序转化为机器语言程序。编译器转化程序的行为称为编译。
-
解释器：根据程序中的算法执行运算。简单来讲，它时一种用于执行程序的软件。如果执行的程序由虚拟机器语言或类似于机器语言的程序设计语言写成，这种软件也能称为虚拟机，例如JS，Python等脚本语言。
Java语言会特殊一些，首先会通过编译器把源代码转化成Java字节码，并将这种虚拟的机器语言保存在文件中。之后,Java虚拟机的解释器将执行这些代码。大多数Java虚拟机为了提高性能，会在执行过程中通过编译器将一部分Java字节码直接转化为机器代码使用，执行过程中进行搞得机器语言转化称为动态编译或JIT编译，转化后得到的机器语言将被载入内存，由硬件执行，无需使用解释器。
过去人们提到编译器时，首先会联想编译过程非常耗时。不过由于编译后实际执行的是机器语言，因此执行速度很快。而对于解释器，人们通常认为它会在程序输入的同时立即执行，执行速度较慢。这就是两者的基本区别。现代的解释器内部常采用各种类型的编译器，已经越来越没必要将解释器与编译器区分看待。
0x02.词法分析
语言处理器的第一个组成部分是词法分析。程序的源代码本质只是一长串字符串，这样的字符串很难处理，语言处理器通常会首先将字符串中的字符以单词为单位分组，切割成多个子字符串。这就是词法分析
token对象
下面是某个程序中的一行代码
1
while i < 10 {
词法分析会把它拆分为下面这样的字符串
1
"while" "i" "<" "10" "{"
这句代码被分割为了5个字符串。通常把词法分析的结果称为单词（token），当然可能你的换行会变成一个"\n"的token，注释标志也可能会变成一个"/*"、"*/" 两个token，这都是有可能的，具体看编译器是如何工作的。当然具体是怎么切的，《两周》这本书用的是正则匹配:
- 用
[0-9]+来匹配整型。 - 用
[A-Z_a-z][A-Z_a-z0-9]*(以字母、下划线开头，之后仅包含有字母、数字、下划线)来匹配标识符，（是不是很像我们平时定义变量?，不可以用数字开头） - …
执行词法分析时，语言处理器会逐行读取源代码，从各行开头起检查内容是否与该正则表达式匹配，并在检查完后获取与正则表达式括号内的模式相匹配的字符串。
在这一步中，空格、换行、注释这些都会被分析器所忽略。编译器会事先获知之后取得的单词，一边获取一边构造抽象语法树，在中途发现构造有误时，需要退回若干单词，重新构造语法树，称之为回溯。
0x03.语法分析/AST(抽象语法树)
语言处理器在词法分析阶段将程序分割为单词后，将开始构造抽象语法树。抽象语法树（AST，Abstract Syntax Tree）是一种用于表示程序结构的树形结构。语法分析的主要任务是分析单词之间的关系，如判断哪些单词属于同一个表达式或语句，以及处理左右括号（单词）的配对等问题。这一阶段还会检查程序中是否含有语法错误。
1
13 + x * 2
我们对上面这条语句进行词法分析。我们通过上面的分析可以得出，编译器大致会分割成 13 、 + 、 x 、 * 、2，这几个token。
然后我们将这些token进行重新排列，变成一个抽象语法树，每个叶节点存储着具体的值和值的类型。
那么像+和*，在进行语法树构建的过程中，符号其实是有优先级以及左右结合顺序的，后面会提到。
0x04.BNF
什么是BNF？总的来说BNF是一个描述语法规则的语言。
初次理解BNF会觉得很难懂，至少我是理解了好久。如果看文字实在太绕，建议看视频，https://www.bilibili.com/video/BV1Us411h72K?from=search&seid=14895223797156770591 我是看了这个视频之后开窍了（我居然可以在bilibli学技术）。
BNF中常用的元字符及其表示的意义如下：
1
2
3
4
5
6
7
8
9
在双引号中的字 "word" 代表着这些字符本身。而double_quote用来代表双引号；
在双引号外的字（有可能有下划线）代表着语法部分；
尖括号 < > 内包含的为必选项；
方括号 [ ] 内包含的为可选项；
大括号 { } 内包含的为可重复0至无数次的项；
圆括号 ( ) 内包含的所有项为一组，用来控制表达式的优先级；
竖线 | 表示在其左右两边任选一项，相当于"OR"的意思；
::= 是“被定义为”的意思；
... 表示术语符号；
理解了上面这些符号的规则，可以来看看书中对自制语言的规则描述:
1
2
3
4
5
6
7
primary ::= "(" expr ")" | NUMBER | IDENTIFIER | STRING
factor ::= "-" primary | primary
expr ::= factor { OP factor }
block ::= "{" [ statement ] { (";" | EOL) [ statement ]} "}"
simple ::= expr
statement ::= "if" expr block [ "else" block ] | "while" expr block | simple
program ::= [ statement ] (";" | EOL)
非终结符factor（因子）或表示一个primary，或表示primary之前再添加一个-号的组合
expr（表达式）用于表示两个factor之间夹有一个双目运算符的组合
block（代码块）指的是由{括起来的statement（语句）序列
statement之间需要用分号或换行符（EOL）分隔。由于Stone 语言支持空语句，因此规则中的statement两侧写有中括号[]。可以看到，它的结构大致与expr类似。它们都由其他的非终结符（statement或factor）与一些用于分隔的符号组合而成
statement可以是if语句、while语句或仅仅是简单表达式语句（simp1e）。简单表达式语句是仅由表达式（expr）构成的语句。
最后的program（程序）是一个非终结符，它可以包含分号或换行符，用于表示一句完整的语句。其中，statement可以省略，因此program还能用来表示空行。代码块中最后一句能够省略句尾分号与换行符。
想要彻底理解BNF，递归的思想是必不可少的
假如以上BNF规定了语言语法的时候，在进行抽象语法树组合的时候，如果不符合以上制定的这些规则时，编译器就会抛出异常。
例如:最后声明的program（程序），你只能用分号或者换行符作为结束符，你想用用句号（。）作为结束符，是不被允许的。
0x04.解释器执行
语法分析将从词法分析器逐一读取非终结符program。即，以语句为单位读取单词，并进行语法分析，执行语法分析后得到的抽象语法树。只要通过语法分析得到抽象语法树，剩下的就简单了，只要从根结点开始遍历至叶节点，并计算各节点的内容即可，这就是解释器的基本实现原理。
要根据得到的抽象语法树来执行程序，各个语法树节点对象的类都需要具备eval方法。eval是evaluate（求值）的缩写。eval方法将计算与以该节点为根的子树对应的语句、表达式及子表达式，并返回执行结果。一直执行，执行到根节点为止。
其实这同样是一种递归过程，
0x05.编译器
在使用中间代码解释器时，我们要事先将抽象语法树转换为中间代码。简单来说，中间代码是一种虚拟的机器语言，因此，中间代码的转换方法，其实与编译器将抽象语法树转换为真正的机器语言时采用的方法大体相同。
中间代码与机器语言
之间利用抽象语法树，语言处理器需要在节点之间往返操作，这是一件费时的工作。因此，如果语言处理器能够实现计算遍历顺序，并以此重新排列节点，执行开销就可能有所降低
通常，语言处理器不会直接将重新排列的抽象语法树节点作为中间代码使用。如果直接保存抽象语法树的节点，多余的无用信息是一种空间上的浪费，因此，我们需要设计一种虚拟的机器语言，并将各个节点转换为与该节点运算逻辑对应的机器语言。大多数语言处理器使用的中间语言都是这种转换后的代码（见下图）
虚拟机由若干个通用寄存器与内存组成。内存分为四个区域，分别是栈（stack）区、堆（heap）区、程序代码区与文字常量区。虚拟机器语言保存于程序代码区，字符串字面量保存干文字常量区。
本书作者自己实现了一个自制的虚拟机，在程序启动过程中同时启动虚拟机，对于抽象语法树的操作不再是简单的执行，而是首先将语言转为虚拟机语言，再通过汇编执行函数的思路进行执行。不过本书中的程序为了演示虚拟机的工作原理并没有给程序性能带来提升，因为自制的语言是程序启动过程中进行编译，执行。不如直接执行抽象语法树来的直接。
0x06.总结
其实书中的细节还有很多，作者对自制的语言也加入很多功能，比如函数，静态变量、闭包等等。在实现局部和全部变量时，居然讨巧的用了一个hashmap + namespace来实现，来确保变量的作用域，这真的非常有意思。
看了这本书，算是对编译原理有一个入门级的认识吧， 取名（1），希望鞭策自己这个主题会有第二篇、第三篇….吧。
众所周知，目前程序的编译器基本都是C++实现的，但是第一个C++程序又是谁给编译的呢？都知道蛋是鸡生的，那么第一只鸡是哪来的呢？
1
2
3
4
5
6
所谓C语言编译器，就是把编程得到的文件，比方.c,.h的文件，进行读取，并对内容进行剖析，按照C语言的规则，将其转换成体系能够履行的二进制文件。
其本质在于对文件的读入，剖析，及处理。这些操作，C言语都是能够完成的。所以用C言语来做C言语的编译器是彻底可行的。
可是，历史上的第一个C言语编译器，必定不是C言语写的，因为在没有编译器时，无法把C言语转换成可履行文件。
只需有了第一版其它言语的编译器，就能够用C言语写编译器了。事实上，现在大多数的C言语编译器，都是用C言语写的。
首要你要理解编译的意思，它是指把高档言语翻译成计算机 能读懂的低级言语（二进制代码），这样计算机才会履行你 的指令，
编译器就相当于一个翻译，在翻译的过程中还会检 查你语法上有没有错误 C言语编译器自然是把用C言语写的程序翻译成二进制代码咯。
0x07.参考
两周自制脚本语言/提取码: t8qm
https://github.com/wmathor/Stone-language
