共计 11488 个字符，预计需要花费 29 分钟才能阅读完成。
前言
对于大多数前端开发者来说 JavaScript 堪称是咱们最相熟的编程语言了，它非常弱小可是有些语言个性却非常难以了解，例如 闭包 和this 绑定等 概念往往会让初学者摸不着头脑。网上有很多诸如《你看完这篇还不懂 this 绑定就来砍我》之类的文章来为大家传道解惑。可是在我看来这些文章大多流于外表，你读了很多可能还是会被面试官问倒。那么如何能力彻彻底底了解这些语言个性，从而在面试的时候立于不败之地呢？在我看来要想真的了解一样货色，最好的路径就是 实现 这样货色，这也是东方程序员十分喜爱说的 learning by implementing。例如，你想更好地了解 React，那么最好的方法就是你本人入手实现一个 React。因而为了更好地了解 JavaScript 的语言个性，我就本人入手实现了一个叫做 Simple 的 JavaScript 语言解释器，这个解释器非常简略，它基于TypeScript 实现了JavaScript 语法的子集，次要包含上面这些性能：
- 根本数据类型
- 简单数据类型 object, array 和 function
- 变量定义
- 数学运算
- 逻辑运算
- if 条件判断
- while，for 循环
- 函数式编程
- 闭包
- this 绑定
本系列文章正是笔者在实现完 Simple 语言解释器后写的整顿性文章，它会包含上面这些局部：
- 我的项目介绍和词法剖析（本文）
- 语法分析
- 执行 JavaScript 代码
尽管 Simple 的实现和 V8 引擎（或者其它 JavaScript 引擎）没什么关系，你也不能通过本系列文章来了解它们的源码，可是看完本系列文章后你将会有上面这些播种：
- 加深对 JavaScript 语言的了解（this 和闭包等）
- 把握编译原理的基础知识
- 晓得什么是 DSL 以及如何实现外部 DSL 来进步研发效率（Simple 的语法分析是基于外部 DSL 的）
Simple 解释器的源代码曾经开源在 github 下面了，地址是 https://github.com/XiaocongDong/simple，我还开发了一个繁难的代码编辑器供大家把玩，地址是 https://superseany.com/opensource/simple/build/，大家能够在这个编辑器外面编写和运行 JavaScript 代码，并且能够看到 JavaScript 代码生成的 单词（Token）和 语法树（AST）。
接着就让咱们进入本系列文章的第一局部 – 我的项目介绍和词法剖析的内容。
我的项目介绍
编译器 vs 解释器
在开始理解 Simple 的实现原理之前，咱们先来搞清楚两个根本的编译原理概念：编译器（Compiler）vs 解释器（Interpreter）。
编译器
编译器能够了解成语言的 转换器 ，它会把源文件从一种模式的代码转换成另外一种模式的代码，它只是负责转换代码， 不会真正执行代码的逻辑。在开发前端我的项目的过程中，咱们用到的代码打包器 Webpack 其实就是一个 JavaScript 编译器，它只会打包咱们的代码而不会执行它们。
解释器
解释器顾名思义就是会对咱们的代码进行 解释执行，它和编译器不一样，它不会对源代码进行转换（最起码不会输入两头文件），而是边解释边执行源代码的逻辑。
Simple 解释器
因为 Simple 不会对编写的 JavaScript 代码进行中间代码转换，它只会解释并且执行代码的逻辑，所以它是一个不折不扣的JavaScript 语言解释器。
Simple 的架构设计
咱们编写的代码其实就是保留在计算机硬盘下面的字符串文本，而实现语言解释器的实质其实就是 教会计算机如何能力了解并执行这些文本代码。那么计算机如何能力了解咱们写的货色呢？思考到大多数编程语言都是用英语进行编码的，咱们无妨先来看一下人是如何了解一个英语句子的，看能不能受到一些启发。
人了解英语句子的过程
Put a pencil on the table。我置信大家必定都晓得这句话是什么意思，可是你是否有思考过你是如何 了解这句话 的呢？或者更进一步，你能不能将你了解这句话的过程拆分成一个个独自的步骤？
我置信大多数人在了解下面这句话的过程中都会经验这些阶段：
-
切割 单词，了解 每个单词的意思：句子是由单词组成的，咱们要了解句子的意思首先就要晓得每个单词的意思。Put a pencil on the table 这个句子每个单词的意思别离是：
- put: 动词，搁置。
- a: 不定冠词，一个。
- pencil: 名词，铅笔。
- on: 介词，在 … 下面。
- the: 定冠词，这张。
- table: 名词，桌子。
-
单词切割完后，咱们就会依据 英语语法规定 划分句子的 构造：在了解完句子每个单词的意思后，咱们接着就会依据英语的语法规定来对句子进行构造的划分，例如对于下面这个句子，咱们会这样进行划分：
- 因为句子第一个单词是动词 put，而且动词前面跟的是不定冠词润饰的名词，所以这个句子应该是个 动词 + 名词 的祈使句，因而这句话的前半句的意思就是叫某人放（put）一支（a）铅笔（pencil）。
- 前半句解释完后，咱们再看一下这个句子的后半句。后半句的结尾是一个介词（on）而后接着一个定冠词润饰的名词（the table），所以它是用来润饰句子前半句的构造为 介词 + 名词 的状语，示意铅笔是放在这个桌子上的。
- 划分和了解完句子的构造后，咱们天然也明确了这个句子的意思，那就是：将铅笔放在这张桌子下面。
计算机如何了解代码
晓得了咱们是如何了解一个英语句子后，咱们再来思考一下如何让计算机来了解咱们的代码。咱们都晓得 计算机科学的很多常识都是对事实世界的建模 。举个例子，咱们熟知的数据结构 Queue 对应的就是咱们日常生活中常常会排的队，而一些设计模式，例如 Visitor，Listener 等都是对现实生活情景的建模。在计算机科学外面钻研编程语言的学科叫做 编译原理，那么编译原理的一些基本概念是如何和咱们下面说到的人类了解句子的步骤一一对应起来的呢？
下面说到咱们了解一个句子的第一步是 切割单词而后了解每个单词的意思 ，这一个步骤其实对应的就是编译原理中的 词法剖析（Lexical Analysis）。词法剖析顾名思义就是在单词层面对代码进行解释，它次要会将代码字符串划分为一个个独立的单词（token）。
在了解完每个单词的意思后咱们会 依据英语语法规定划分句子的构造 ，这个步骤对应的编译原理的概念是 语法分析 （Syntax Analysis/Parser）。语法分析的过程会将词法剖析生成的单词串依据定义的 语法规定 生成一颗 形象语法树 （AST）。生成的形象语法树最初就会被一些 运行时（runtime）执行。
综上所述，一个语言解释器的软件架构大体是这样的：
下面其实也就是 Simple 的软件架构，接着让咱们来看一下词法剖析的具体实现。
词法剖析
后面曾经说过，所谓的 词法剖析 就是将文件的代码 以单词（token）为单位切割成一个个独立的单元 。这里要留神的是编译原理的单词和英文外面的单词不是等同的概念，在编译原理外面，除了let，for 和while等用字母连接起来的字符串是单词，一些诸如 =，==，&& 和+等非字母连接起来的字符串也是非法的单词。对于 Simple 解释器来说，上面都是一些非法的单词：
- 关键字：let，const，break，continue，if，else，while，function，true，false，for，undefined，null，new，return
- 标识符：次要是一些开发者定义的变量名字，例如 arr，server，result 等
- 字面量：字面量包含数字字面量（number）和字符串字面量（string），Simple 解释器只反对单引号字符串，例如 ’this is a string literal’
- 算术和逻辑运算符号：+，-，++，–，*，/，&&，||，>，>=，<，<=，==
- 赋值运算符：=，+=，-=
- 特殊符号：[，]，{，}，.，:，(，)
这里要留神的是词法分析阶段不会保留源代码中所有的字符，一些无用的信息例如空格，换行和代码正文等都会在这个阶段被去掉。上面是一个词法剖析的效果图：
对于词法剖析，大略有以下两种实现：
正则表达式
这个办法可能是大多数开发者都会想到的做法。因为 Simple 解释器没有应用这种做法，所以这里只会简略介绍一下流程，总体来说，它蕴含以下这些步骤：
- 为各个单词类型定义对应的正则表达式，例如数字字面量的正则表达式是
/[0-9][0-9]*/（不思考浮点数的状况），简略赋值运算符的正则表达式是/=/，等于运算符的正则表达式是/==/。 - 将各个单词类型的正则表达式依照 词法优先级程序 顺次和代码字符串进行 match 操作，如果某个单词类型的正则表达式有 命中 ，就将对应的子字符串提取进去，而后从方才命中的字符串 最初的地位 开始继续执行 match 操作，如此 循环反复 直到所有字符串都 match 结束为止。这里有一个非常重要的点是不同的单词类型是有 词法优先级程序 的，例如等于运算符
==的优先级要比=的优先级要高，因为如果开发者写了两个等号，想表白的必定是等于判断，而不是两个赋值符号。
基于无限状态机
因为 所有的正则表达式都能够转化为与其对应的无限状态机，所以词法剖析同样也能够应用无限状态机来实现。那么什么是无限状态机呢？
无限状态机的英文名称是Finite State Machine（FSM），它有上面这些特点：
- 它的状态是 无限的
- 它同一个时刻只能有一个状态，也就是 以后状态
- 在接管到外界的数据后，无限状态机会依据 以后状态 以及 接管到的数据 计算出下一个状态并 转换 到该状态
咱们相熟的红绿灯其实就是一个无限状态机的例子。红绿灯只能有三种色彩，别离是红色，绿色和黄色，所以它的状态集是无限的。因为红绿灯在某一个时刻只能有一种色彩（试想下红绿灯同时是红色和绿色会怎么：）），因而它以后的状态是惟一的。最初红绿灯会依据以后的状态（色彩）和输出（过了多少工夫）转换成下一个状态，例如红灯过了 60 秒就会变黄灯而不能变绿灯。
从下面的定义咱们晓得一个无限状态机最重要的是上面这三个因素：
- 状态集
- 以后状态
- 不同状态之间如何扭转
晓得了什么是无限状态机和它的三要素之后，接着让咱们来看一个应用繁难无限状态机来做词法剖析的例子。咱们要设计的无限状态机能够辨认上面类型的单词：
- identifier（标识符）
- number（数字字面量，不蕴含浮点数）
- string（字符串字面量，单引号包起来的）
- 加号（+）
- 加号赋值运算符（+=）
咱们先来为这个无限状态机定义一下下面提到的状态机三要素：
-
状态集：状态集应该蕴含状态机在接管到任何输出后呈现的
所有状态，对于下面的状态机会有上面的状态：- initial：初始状态
- number：当状态机辨认到数字字面量时会处于这个状态
- start string literal：当状态机接管到第一个单引号的时候并且没有接管到第二个单引号前（字符串还没完结）都是处于这个状态
- string literal：当状态机辨认到字符串字面量时会处于这个状态
- identifier：当状态机辨认到标识符会处于这个状态
- plus：当状态机辨认到加号会处于这个状态
- plus assign：以后状态机辨认到加号赋值运算符会处于这个状态
- 以后状态：该无限状态机的以后状态能够是下面定义的任意一个状态
- 不同状态之间如何扭转：当状态机处于某一个状态时，它只能够 扭转到某些特定的状态 。举个例子，如果状态机当初处于
start string literal状态，它只能够维持以后状态或者转换到string literal状态。在以后输出不能让状态机进行状态扭转时，会有两种状况，第一种状况是以后状态是一个 可终止的状态 ，也就是说以后状态机曾经晓得生成一个 token 须要的所有信息了，这个时候状态机会输入以后状态示意的单词类型，输入上一个单词后，状态机会重置为初始状态接着再重新处理方才的输出；如果以后状态是个 非终止状态 的话，也就是说以后状态机还没有足够的信息输入一个单词，这个时候状态机会报错。在以后这个例子中，可终止状态有number，string literal和identifier，而非终止状态有start string literal。上面是这个状态机的状态扭转图：
这里要留神的是状态机除了要存储以后的状态信息外，还要保留当初还没输入为单词的字符，也就是说要有一个 buffer 变量来存储遇到的字符输出。例如遇到 + 后，buffer会变成 +，前面再遇到=，buffer 会变为 +=，最初+= 被输入，buffer会被重置为空字符串''。
状态机三要素定义实现后，咱们就能够应用下面的状态机来对 a+='Simple' 这个字符串就行词法剖析了：
- 刚开始的时候状态机会处于 initial 状态，接着状态机会一一接管代码的每个字符并实现对应的状态扭转和单词输入
- 状态机接管到
a字符，依据下面定义的状态扭转图咱们晓得该字符能够让状态机扭转为identifier这个状态，并且会将该字符保留在buffer这个变量外面 - 状态机接管到
+字符，因为 identifier 不能依据+字符进行状态扭转了，而它以后又处于一个可终止状态（identifier 状态）所以状态机会输入之前记录下来的a单词，而后将状态重置为initial。状态机重置状态后会重新处理+字符，这时候状态机转换为plus状态，并且将+这个字符记录下来，这时候buffer变为+ - 状态机接管到
=字符，从下面的扭转图能够看出，状态机能够转换到plus assign这个状态，所以状态机会进行状态的扭转并记录下=这个字符，buffer变为+= - 状态机接管到
'字符，因为plus assign不能依据'字符进行状态转换，而plus assign又是一个可终止的状态，所以状态机会输入以后buffer记录的+=作为单词，并且将状态重置为initial。状态机重置状态后会重新处理'字符，这时候状态机转换为start string literal状态 - 当状态机别离接管到
S，i，m，p，l和e时，因为它们都不是单引号，所以状态机会维持在start string literal这个状态，并且这些字符会被顺次退出到buffer中，最初 buffer 会变为Simple - 状态机接管到
'字符，状态机转换到string literal状态，这就意味着状态机曾经辨认到一个非法的字符串单词了 - 最初状态机判断没有字符能够输出后，它会看一下以后的状态是否是可终止状态，因为
string literal是可终止状态，所以状态机会输入以后单词。反之，如果状态机发现没有新的字符能够输出而本人又处于一个非终止的状态，它就会抛一个叫做Unexpected EOF的谬误
以上就是应用无限状态机来实现词法分析器的一个简略例子，Simple 解释器的词法剖析实现和下面的步骤是一样的。在 Simple 解释器中，我将状态机的外围逻辑（记录以后状态和进行状态扭转）和状态机的配置（状态集的定义以及不同状态之间如何扭转）的逻辑解耦开来了，这样能够不便前面对 Simple 语言的词法规定进行批改和扩大，并且它还能够应用另外一个状态机配置来实现另外一门语言的词法剖析。
状态机的外围逻辑代码放在了 lib/lexer/Tokenizer.ts 文件外面，而状态机的配置则放在 lib/config/Tokenizer.ts 外面，上面是具体的源代码剖析：
状态机配置定义
Simple 的状态机配置定义在 lib/config/Tokenizer.ts 外面，上面是简化版的例子，具体代码能够到 github 下面看：
// lib/config/Tokenizer.ts
// State 定义了 Simple 语言状态机所有可能的状态
enum State {
INITIAL = 'INITIAL',
NUMBER_LITERAL = 'NUMBER_LITERAL',
IDENTIFER = 'IDENTIFER',
START_STRING_LITERAL = 'START_STRING_LITERAL',
STRING_LITERAL = 'STRING_LITERAL'
...
}
// 状态扭转定义
const config: IConfig = {
initialState: State.INITIAL, // 定义状态机的初始状态
states: { // 枚举状态机所有的状态配置
[State.INITIAL]: {
isEnd: false, // 示意该状态是否是可终止状态
transitions: [ // 枚举状态机所有的状态转换
{
state: State.NUMBER_LITERAL,
checker: /[0-9]/
},
{
state: State.START_STRING_LITERAL,
checker: "'"
}
},
[State.NUMBER_LITERAL]: {
isEnd: true,
TokenType: TOKEN_TYPE.NUMBER_LITERAL,
transitions: [
{
state: State.NUMBER_LITERAL,
checker: /[0-9\.]/
}
]
},
[State.START_STRING_LITERAL]: {
isEnd: false,
transitions: [
{
state: State.START_STRING_LITERAL,
checker: /[^']/
},
{
state: State.STRING_LITERAL,
checker: "'"
}
]
},
[State.STRING_LITERAL]: {
isEnd: true,
TokenType: TOKEN_TYPE.STRING_LITERAL
},
...
}
}下面的配置文件定义了一个 config 对象，该对象会作为参数传递给 lib/lexer/Tokenizer.ts 外面的无限状态机类 Tokenizer。这个 config 对象有两个参数，一个是初始状态值，一个是该状态机的所有状态配置states。初始状态值就是状态机刚开始的状态值，同时在状态机辨认到一个新的单词后，它也会重置为这个状态。states 是一个 Object 类型的对象，它的 key 是某个状态的值，而 value 则是这个状态对应的配置，一个状态的配置包含上面这些内容:
- isEnd: boolean，代表这个状态是否是可终止状态
- TokenType: 代表这个状态对应的单词类型。如果该状态是个可终止状态，它就能够有对应的单词类型。如果 TokenType 没有指定，即便有单词匹配胜利也不会生成对应的单词。
-
transitions: 外面存储了这个状态所有可能的状态转换（transition），每个状态转换会有上面这些属性：
- state：要转换到的状态
- checker：状态转换的条件，能够是字符串，正则表达式或者是一个返回布尔值的函数，当输出满足 checker 的条件时状态机就会产生状态转换
状态机外围逻辑实现
下面看了 Simple 状态机的配置后，咱们再来看一下应用该配置的状态机的外围代码 lib/Lexer/Tokenizer.ts。为了实现Tokenizer 的性能，我设计了两个辅助类，一个是用于记录以后地位信息的 LocationKeeper 类，它是用来记录以后解决的字符在源文件的行数和列数的，这个类比较简单，这里不会具体介绍有趣味的能够看源代码。另外一个类是 TokenBuffer 类，所有被状态机辨认出的单词都会被存储到这个类的实例中，因而它须要提供一些办法对单词进行读写（read/write）操作，这个类会在 Tokenizer 类介绍完后介绍。
咱们先来看一下 Tokenizer 类解决输出字符的外围逻辑 consume(ch: string) 函数：
// lib/lexer/Tokenizer.ts
class Tokenizer {
...
consume(ch: string) {
// 如果输出字符是空格或者换行符而且以后的状态是初始状态的话，只更新以后地位信息
if ((ch === SPACE || ch === NEW_LINE) && this.state === this.initialState) {this.locationKeeper.consume(ch)
return
}
// 接着会依据以后的状态和输出的字符进行状态扭转
// 获取以后状态的配置信息，this.state 保留的是状态机以后的状态
const currentStateConfig: IStateConfig = this.statesConfig[this.state]
if (!currentStateConfig) {
// 开发者遗记配置这个状态了，咱们也要报错，develper-friendly：）throw new Error(`Missing state config for ${this.state}`)
}
// 获取以后状态所有转换可能
const transitions = currentStateConfig.transitions
if (!transitions) {
// 如果以后状态不能够转换而且是可终止状态
if (currentStateConfig.isEnd) {
// 生成 token，存进 tokenBuffer 外面
this.addToken(currentStateConfig.TokenType)
// 重置以后状态
this.reset()
// 再次耗费以后输出的字符
this.consume(ch)
return
}
// 以后状态不能转换而且是非终止状态的话就报错！throw new SyntaxError(`Unexpected character ${ch}`, this.locationKeeper.getCurrentLocation())
}
// 将输出字符和 checker 进行比拟以确定须要进行的状态转换
const targetTransition = transitions.find(({checker}) => {if (typeof checker === 'string') {return ch === checker}
if (checker instanceof RegExp) {return checker.test(ch)
}
return checker(ch)
})
// 不存在能够转换的状态
if (!targetTransition) {
// 是可终止状态
if (currentStateConfig.isEnd) {if (currentStateConfig.TokenType) {
// 增加 token 到 tokenBuffer 实例
this.addToken(currentStateConfig.TokenType)
}
// 重置状态
this.reset()
// 从新耗费输出字符
this.consume(ch)
return
}
// 不存在能够转换的状态而当初又是非终止状态，咱们只能报错了！this.locationKeeper.consume(ch)
throw new SyntaxError('Invalid or unexpected token', this.locationKeeper.getCurrentLocation())
}
// 上面的逻辑是状态胜利扭转后进行的
// 更新以后记录的地位信息，代码的行数和列数
this.locationKeeper.consume(ch)
// 上面代码是为了记录以后单词的开始地位的
if (this.state === this.initialState && targetTransition.state !== this.initialState) {this.locationKeeper.markLocation()
}
// 将以后状态转换为指标状态
this.state = targetTransition.state
// 将以后的字符退出到 buffer 外面
this.buffer += ch
}
}接着咱们来看一下用来存储辨认到的单词的类 TokenBuffer 的源代码：
// lib/lexer/TokenBuffer.ts
import {IToken} from "./types/token"
class TokenBuffer {
// 存储以后曾经辨认进去的单词
private tokens: Array<IToken> = []
// 存储以后曾经读到的单词的地位
private cursor: number = 0
// peek 会返回以后的单词，它不会扭转光标的地位，只会预读
peek() {return this.tokens[this.cursor]
}
// 和 peek 不一样，它会读出以后的单词，因而会扭转光标的地位
read() {const currentToken = this.tokens[this.cursor]
const nextCursor = this.cursor < this.tokens.length ? ++this.cursor : this.tokens.length
this.cursor = nextCursor
return currentToken
}
// 勾销上次的读取，将单词 "放" 回去
unread() {
const lastCursor = --this.cursor
this.cursor = lastCursor
return this.tokens[lastCursor]
}
// 写入新的 token
write(token: IToken) {this.tokens.push(token)
}
// 获取以后光标的地位
getCursor() {return this.cursor}
// 间接设置当期光标的地位，次要是在语法分析阶段进行回退用的
setCursor(cursor: number) {this.cursor = cursor}
// 以 JSON 格局输入以后的 tokens
toJSON(): Array<IToken> {return this.tokens}
// 判断单词是否曾经全副处理完毕了
isEmpty(): boolean {return this.cursor === this.tokens.length}
}仔细的同学会发现我在实现下面的 TokenBuffer 时每次读取单词都只是挪动光标，而没有真正将该单词从数组外面取出来，这样做的益处就是不便语法分析阶段在某个语法规定不匹配的时候回退之前读到的单词，从而应用另外一个语法规定来匹配。
Token 单词串
最初咱们再来看一下这个无限状态机辨认到的 Token 串是什么样子的，上面是输出的代码：
let a = 'HelloWorld';通过无限状态机的解决，输入的 Token 串是：
[
{
"type": "LET",
"value": "let",
"range": {
"start": {
"line": 1,
"column": 1
},
"end": {
"line": 1,
"column": 3
}
}
},
{
"type": "IDENTIFIER",
"value": "a",
"range": {
"start": {
"line": 1,
"column": 5
},
"end": {
"line": 1,
"column": 5
}
}
},
{
"type": "ASSIGN",
"value": "=",
"range": {
"start": {
"line": 1,
"column": 7
},
"end": {
"line": 1,
"column": 7
}
}
},
{
"type": "STRING_LITERAL",
"value": "'HelloWorld'",
"range": {
"start": {
"line": 1,
"column": 9
},
"end": {
"line": 1,
"column": 20
}
}
},
{
"type": "SEMICOLON",
"value": ";",
"range": {
"start": {
"line": 1,
"column": 21
},
"end": {
"line": 1,
"column": 21
}
}
}
]从下面的输入能够看出每个单词（token）都会有上面这些属性：
- type: 单词的类型，也就是非终止状态外面定义的 TokenType
- value: 这个单词具体的值
- range: 外面存储了这个单词的开始和完结的地位信息，包含行数和列数。这些地位信息会在代码报错的时候帮忙开发者定位谬误
小结
在本篇文章中我为大家介绍了 Simple 这个我的项目的 背景和内容 ，而后再为大家介绍了一些简略的 编译原理 基础知识，最初再详述了如何应用 无限状态机 来实现 词法剖析 并且解读了 Simple 我的项目对应的 源代码。
在下一篇文章中我将会为大家具体介绍 语法分析 的一些基本知识，以及遍及一些 畛域特定语言（DSL）的基本概念，最初再具体介绍一下我是如何应用灵便的 DSL 来实现 Simple 语言的 语法分析 的。
集体技术动静
文章始发于我的集体博客
欢送关注公众号 进击的大葱 一起学习成长