前言

对于大多数前端开发者来说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'这个字符串就行词法剖析了：

  1. 刚开始的时候状态机会处于initial状态，接着状态机会一一接管代码的每个字符并实现对应的状态扭转和单词输入
  2. 状态机接管到a字符，依据下面定义的状态扭转图咱们晓得该字符能够让状态机扭转为identifier这个状态，并且会将该字符保留在buffer这个变量外面
  3. 状态机接管到+字符，因为identifier不能依据+字符进行状态扭转了，而它以后又处于一个可终止状态（identifier状态）所以状态机会输入之前记录下来的a单词，而后将状态重置为initial。状态机重置状态后会重新处理+字符，这时候状态机转换为plus状态，并且将+这个字符记录下来，这时候buffer变为+
  4. 状态机接管到=字符，从下面的扭转图能够看出，状态机能够转换到plus assign这个状态，所以状态机会进行状态的扭转并记录下=这个字符，buffer变为+=
  5. 状态机接管到'字符，因为plus assign不能依据'字符进行状态转换，而plus assign又是一个可终止的状态，所以状态机会输入以后buffer记录的+=作为单词，并且将状态重置为initial。状态机重置状态后会重新处理'字符，这时候状态机转换为start string literal状态
  6. 当状态机别离接管到S，i，m，p，l和e时，因为它们都不是单引号，所以状态机会维持在start string literal这个状态，并且这些字符会被顺次退出到buffer中，最初buffer会变为Simple
  7. 状态机接管到'字符，状态机转换到string literal状态，这就意味着状态机曾经辨认到一个非法的字符串单词了
  8. 最初状态机判断没有字符能够输出后，它会看一下以后的状态是否是可终止状态，因为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.tsclass 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.tsimport { 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语言的语法分析的。

集体技术动静

文章始发于我的集体博客

欢送关注公众号进击的大葱一起学习成长