硬核系列 | 手写脚本语言编译器（一）
前言
编译技术它难吗？确实很复杂，而一旦驾驭它，日常开发过程中，除了能够使你在同事面前秀一把“屠龙技”外，还能为你开启一扇新世界的大门。众所周知，编译技术的应用场景非常广泛（尤其是前端编译技术），诸如解析类的场景绝大多数都采用了编译技术（比如：Sharding 中间件的 SQL 解析器），那么既然编译技术如此重要，为何大部分同学都掌握的不好？在我看来，这绝对是由一些客观原因造成的，市面上，关于编译原理类的书籍可谓星罗棋布，共性问题就是仅停留在理论层面做引导，所导致的结果就是，读者在通篇读完后，由于缺乏实战指导，自然不得要领。而我编写本文的目的，就是为了帮助大家扫清这些障碍，尽量用通俗易懂的方式去讲清楚编译技术所涉及到的一些核心知识点，且侧重实战，让你知其然，更知其所以然。
本系列博文一共分为 3 个部分，前 2 部分，我会聚焦在编译器的前端技术上，站在实战的视角，深入为大家讲解词法分析器、语法分析器的实现过程。而最后一部分，主要侧重讲解编译器的后端技术，并结合之前所学的内容，将 AST 抽象语法树生成对应的字节码指令，实现一款基于解释型语言的编译器。当然出于私心，也顺便为了回顾下自己尘封已久的汇编语法，我还会直接将语法树生成底层的汇编指令执行。
究竟什么是编译器
所谓编译器，简而言之，就是将由源语言编写的程序，“翻译”为一个等价的，用另外一种语言编写的程序（比如我们的 Java 代码，会优先被 Javac 编译器编译为字节码形式的中间代码，而 C1 和 C2 编译器又会在运行时将其编译为本地代码执行）。实际上，编译器的作用就有点像日常生活中的翻译员，张三用中文表达，翻译员将其翻译为李四听得懂的英文，这就是编译器的主要任务和作用。开篇，我曾提及过，编译技术大致可以分为 2 类，一类是编译器的前端技术，而另一类则是编译器的后端技术，如图 1 所示。
在前端编译技术中，主要包括了词法分析、语法分析和语义分析等 3 个阶段。其中词法分析是整个编译任务的伊始，其主要作用就是一个字符一个字符的读取源文件中的内容，并根据指定规则将其转换成对应的词法单元（即：Token 序列），这里听起来似乎比较抽象，降维解释来说，就是识别出源文件中的每一个字符序列，并区分出标识符、保留字、字面值、运算符等，实际上类似于我们在说话时，大脑会自动区分出哪些词是名词，哪些词是动词，遇到标点符号要进行停顿是一个道理，这就是词法分析阶段的主要任务，如图 2 所示。
当词法分析器将字符序列解析为一个个的 Token 序列后，编译器接下来就会进入到语法分析阶段，在此大家需要注意，编译器并不会在一开始就将源码中的所有字符序列都转换为 Token 序列，而是由语法分析器来负责驱动词法分析器，这实际上有点类似于 Lazy 模式，真正需要用到的时候再解析。而语法分析器的主要任务就是调用词法分析器获取出对应的 Token，然后生成一颗结构化的，符合目标语言语法结构的 AST 抽象语法树，期间，语法分析器会强制验证 Token 序列的排列组合方式以满足语法规范的要求。以 Java 为例，当我们在程序中声明成员变量时，首先会定义访问修饰符，然后再是数据类型、标识符、赋值运算符“=”，最后才是相关的初始化操作，而如果数据类型后面跟的不是标识符，则不符合语法规范，如图 3 所示。
我们都知道，程序中语法没错，并不代表语义没错，比如，二元运算中数值 0 不能作为除数，但语法却是正确的。因此，当语法分析器解析出 AST 抽象语法树后，接下来编译器就会进入到前端编译技术的最后一个阶段，即语义分析。语义分析器的主要任务，就是围绕类型检查展开，比如一些强类型的语言，当声明一个 int 类型的变量时，如果赋值为字符串，编译器就会出现编译错误的异常堆栈，而如果尝试赋值浮点类型，语义分析器则需要丢失目标数值的精度去实现自动类型转换。最终，语义分析阶段也是输出一颗 AST 抽象语法树，只是在先前语法分析阶段产生的那颗 AST 抽象语法树的基础之上，进行了进一步的雕琢，使之更加完善。
其实在大部分场景下，编译器前端技术的应用场景要远远大于后端，且就纯粹的技术难度而言，后者明显更为复杂，因为编译器后端技术的主要任务就是生成高效目标代码的过程，如果最终的编译结果为汇编代码，那么开发人员除了需要掌握汇编语法外，对于 CPU 寄存器等硬件相关的知识也需要有一定的了解，甚至我们还需要花费大量的时间去实现编译优化来提升程序的执行效率。并且，哪怕是生成像字节码这样的中间代码也绝不是一件轻松的事情，因为对于 JVM 指令的熟悉程度决定了我们是否能够正确的去操作字节码。
词法分析器的实现细节
在上一个小节中，我们已经大致清楚词法分析器的主要任务就是负责一个字符一个字符的读取源文件中的内容，然后将这些字符组成词素，最后再转换成对应的 Token 序列输出。这里我简单解释下词素和 Token 的对应关系。所谓词素，实际上指的就是读入的字符集合，也称之为字符序列（比如：“abc”是一个词素，“int”同样也是一个词素），之所以词法分析器的输出结果不是词素而是 Token，是因为编译器需要输出一种更具价值，且更容易被语法分析器进行语法分析的抽象符号。Token 中会包含一些词素所不具备的内容，换句话说，词素是 Token 的构成部分之一，一个词素可以匹配一个 Token（比如：INT 类型的 Token 所对应的词素为 int），而多个词素同时也可以匹配同一个 Token（比如：IDENTIFIER 类型的 Token 可以对应于任意的标识符词素）。
接下来，我们正式开始编写我们的词法分析器。首先，我们需要定义好 Token，而 Token 的构成部分，主要包括如下 4 部分内容：
tokenAttribute：每个 Token 都对应着一个属性值；
tokenKind：用于表示 Token 的类型；
pos：每一个 Token 的起始位；
length：词素的具体长度；
示例 1-1，定义 Token 类型：
TokenAttribute 代表着 Token 所对应的属性值，其中主要包括词素信息和 flag 标记位。flag 的作用非常重要，在接下来的实战演示中，词法分析器在进行词法分析时就是根据此值来区分 Token 的类型。示例 1-2，定义 TokenAttribute：
实现编译器的过程，同时也是赋予一门编程语言生命的过程，如果是“新生命”，那么我们就需要仔细思考并提前规划好词法分析器究竟需要支持哪些保留字、数据类型、运算符，以及标识符等 Token 类型，因为，Token 类型的丰富程度在某种意义上决定了语法分析器的语法解析能力（即：语法层面所支持的语法特性）。简单起见，在此我仅定义了 4 种数据类型，字符串类型（STRING）、正整数类型（INT），单精度浮点类型（FLOAT），以及布尔类型（BOOL），并支持一些基础的运算符和流程控制语句。示例 1-3，定义 TokenKind：
而 Token 类型中的 pos 属性代表着每一个 Token 类型的起始位，即构成词素的第一个字符的索引位，这个属性存在的意义主要是语法解析器在回溯上一个 Token 时会使用到。而属性 length 代表着词素长度。
词法分析器在进行词法分析期间会频繁的与 SymbolTable（符号表）进行交互，站在词法分析器的视角来看，符号表中记录着每一个与 Token 对应的 TokenAttribute，也就是说，无需为同一个词素去重复创建相同的 TokenAttribute。在此大家需要注意，词法分析的过程，实际上就是将有穷自动机的状态转换图转换为代码解析的过程。因此，词法分析器通常可以采用如下 2 种形式来区分 Token 类型：
为每一个保留字都实现一个独立的状态转换流程；
编译器初始化时就将各个保留字记录至符号表中。
关于第 1 种实现方式，我放在后面再讲，先看第 2 种更为通用和灵活的实现方式。编译器在初始化阶段就选择将所有的保留字（即：预定义类型）都保存至符号表中，并同时记录每一个词素的字符串长度，最后计算出所有保留字的词素总长，称之为 maxFlag。举个例子，假设我们在 TokenKind 中只定义了 INT 和 FLOAT 等 2 个保留字，那么编译器在初始化时，词素 int 的 TokenAttribute.flag 会被指定为 3，而记录词素 float 时，TokenAttribute.flag 会被指定为 8。换句话说，在符号表中创建 TokenAttribute 时，其 flag 值是持续累加的，待初始化结束后，最终 maxFlag 的值也等于 8。当词法分析器在创建一个 Token 时，会从符号表中获取出对应词素的 TokenAttribute（不存在时则创建），如果TokenAttribute.flag > maxFlag，则意味着目标词素尚未出现在符号表中，那么它的 Token 类型就一定是 IDENTIFIER，如图 4 所示。
符号表中创建 TokenAttribute 的核心代码，示例 1-4：
当然，上述实现方式看起来是比较复杂的（这是 Javac 编译器的实现方式），当然也可以采用空间换时间的方式，用不同的集合存储不同的 TokenAttribute，区分保留字和非保留字，如果在保留字集合中无法获取到对应的 TokenAttribute 则表示目标词素尚未出现在符号表中。当然具体采用哪种方式，大家则还需要结合实际的业务场景而定。
接下来，我们正式进入到词法分析的核心部分，即实现词法解析的过程。当然，首先我们需要定义好词法分析器接口，明确词法分析器要实现的主要功能有哪些，示例 1-5：
当成功定义好功能接口后，接下来我们需要实现 SpiderLexer。刚才曾经提及过，我们需要在词法分析器的初始化阶段就将所有保留字记录至符号表中，以便于后续通过比对 flag 来区分目标 Token 的具体类型，示例 1-6：
在上述程序示例中，每一个保留字都会优先被记录至符号表中，然后接下来初始化阶段还会做 2 件事，首先是存储 TokenKind 的序数，Key 为 TokenAttribute.flag，这里相当于构建了一个反向索引，如果在创建 Token 时，确定是保留字，则通过对应的 flag 值从 TokenKind 中获取出对应的 Token 类型。其次，计算出所有保留字的词素总长至变量 maxFlag 中。词法分析的过程，实际上就是将有穷自动机的状态转换图转换为代码解析的过程，这一点大家务必要牢记。接下来，我们来看下究竟应该如何读取 Token，示例 1-7：
当调用 nextToken()方法获取出 Token 时，词法分析器会判断当前读入的第一个字符是什么？当匹配正则规则[a-z|A-Z|$|_]时则进入到 scanIdent()方法中读取一个完整的标识符。而如果匹配正则规则[0-9]则进入到 scanNumber()方法中读取一个完整的数字字面值，其它以符号，运算符等字符开头的读取规则以此类推。考虑到篇幅限制，本文仅以读取一个完整的标识符为例进行讲解，示例 1-8：
参考 Java 语法规范，标识符的第一个字符需要匹配正则规则[a-z|A-Z|$|_]，而一个完整的标识符由正则规则[a-z|A-Z|$|_|0-9|\\u4e00-\\u9fa5]*构成。当词法分析器进入到 scanIdent()方法中所读取到的字符不匹配正则规则时退出，并返回目标 Token 输出。在生成 Token 并指定其类型时，如果flag <= maxFlag则表示为保留字，反之为 Token 类型为 IDENTIFIER，示例 1-9：
先前我曾经提及过，词法分析器区分 Token 类型通常有 2 种比较常见的方式，在示例 1-7 至 1-9 中，我为大家演示了保留字的优先录入方式，那么接下来，我们再来看看第 1 种方式。尽管采用这样的方式比较繁琐和冗余，但作为了解大家还是必须要清楚和掌握的。
采用第 1 种方式，无非就是为语法中的每一个保留字都构建一个独立的状态转换图，如图 5 所示。以保留字 if 为例，在 nextToken()方法中，我们需要调整下代码，如果当前字符为‘i’，则推进 if 关键字的状态，示例 1-10：
而 scanIdent()方法中，也需要进行相应的状态判断和流程推进，示例 1-11：
而最终再返回 Token 时，我们可以根据当前词素的 State 来区分出 Token 类型，示例 1-12：
关于词法分析器的其它实现细节，本文就不过过多进行叙述，如果大家感兴趣，可以参考spider-compiler的具体实现。
====== END ======
至此，本文内容全部结束。如果在阅读过程中有任何疑问，欢迎在评论区留言参与讨论。
推荐文章：
版权声明: 本文为 InfoQ 作者【九叔】的原创文章。
原文链接:【http://xie.infoq.cn/article/66dbac4c3cb1a60739ab3e2c5】。文章转载请联系作者。
阿里巴巴 | 高级技术专家 2020.03.25 加入
GIAC全球互联网架构大会讲师，《超大流量分布式系统架构解决方案》、《人人都是架构师》、《Java虚拟机精讲》书籍作者
评论 (2 条评论)