写在前面

最近完成了镜像计划中的完成JS解释器的项目，根据acorn模块生成的AST树来实现eval功能，已支持ES5语法，Async语法，Generator语法，且模拟实现了作用域。特作此文以分享收获与想法。

编译原理

高级语言为我们常用的语言，如C/CPP/JS等，是在底层接口与特性之上封装而生，符合人们习惯，但往往效率低；而低级语言更接近机械码，如汇编语言，编写难度大，但效率非常高。

编辑原理是一种对高级程序语言进行翻译的一种技术，主要有如下步骤：

• 词法分析
  • 扫描文件中所有字符，构造状态机进行状态转移。
  • 字符所组成的符号表包括标识符/关键字/操作符/界符等。
• 语法分析
  • 根据词法分析的各个词法单元进行分析，常用以语法树来构造结构。
  • 分析过程可以通过自上而下的LL文法或自下而上的LR文法。
• 语义分析
  • 语义分析器借助用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。
  • 主要包括类型检查，词法结构等。
• 中间代码生成
  • 中间代码是处于源代码和目标代码的中间结构，容易由其生成目标代码。
  • 这是一种结构简单、含义明确的记号系统。
• 代码优化
  • 改进中间代码（或目的代码），以使得空间占用减少，运行时间缩短。
• 目的代码生成
  • 根据中间代码生成的二进制的机器指令或汇编语言。

JIT和AOT

根据所使用语言的编译时机，可以将分为编译型语言和解释型语言。

编译型语言是程序运行前便将代码编译为计算机能够理解的语言，即汇编码或机械码。典型的如C，C++等。

解释型语言是程序运行时边编译边运行，因此需要用到解释器才可执行代码，且执行效率天生比编译型语言低。典型的便是JS。

因此引申出两个概念AOT(Ahead-of-Time)提前编译，和JIT(Just-in-Time)即时编译。

JS执行过程

JS作为解释型语言，其执行步骤基本有如下四步（非完全的步骤）：

1. 语义分析，即进行分词

[
  { type: 'Keyword', value: 'var' }, 
  { type: 'Identifier', value: 'a' },
  { type: 'Punctuator', value: '=' },
  { type: 'Number', value: '1' }
];

2. 语法分析，即生成AST树

{
  "type": "VariableDeclaration",
  "declarations": [
    {
      "type": "VariableDeclarator",
      "id": {
        "type": "Identifier",
        "name": "a"
      },
      "init": {
        "type": "Literal",
        "value": 1,
      }
    }
  ],
  "kind": "var"
}

3. 预解析，即对某些变量与函数进行声明提前的处理等。

该步骤可在运行中处理，执行某一作用域前，先对该作用域进行预解析，即预解析在运行之中，本项目便是采用此种做法。

4. 运行，即根据AST树，或其它中间表示形式来执行JS代码。

运行和预解析是本文中的主要内容，由于分词与解析为AST的过程过于复杂，便不再具体实现，如对分词与解析感兴趣，可参考我以下两个项目：

• MrPluto0/Lexical-Analyzer (github.com) 该项目中仅实现了对c语言的分词功能，项目报告里记录了更多细节的内容。
• MrPluto0/dslBot (github.com) 其中定义了简单的dsl语言，并对该语言实现tokenize，parser，runner三个模块，即对应以上除了预解析外的其它模块。

JS解释器

本文中主要借助acorn模块来生成JS代码的语法树AST，我们将从此树入手来递归实现JS代码的实现——JS解释器。

相关工具

1. 一个在线网址可以根据代码在线生成AST树，以在完成过程中进行比对：AST explorer
2. 关于es5语法生成AST树各种节点的类型说明文档：estree/es5.md · estree/estree (github.com)

核心：递归实现

注：此处的初步的封装，根据后面的步骤，该递归函数会传入多个参数，函数类型变成generator类型，函数调用方式也会发生变化。

实现一个类似于eval的功能，给它取名为evaluate，传入的参数即为node节点对象。在其中通过switch/case来判断节点类型，进行转换。

比如最简单的1+2的式子的计算，转换出来的AST树如下：

{
  "type": "Program",
  "start": 0,
  "end": 3,
  "body": [
    {
      "type": "ExpressionStatement",
      "start": 0,
      "end": 3,
      "expression": {
        "type": "BinaryExpression",
        "start": 0,
        "end": 3,
        "left": {
          "type": "Literal",
          "start": 0,
          "end": 1,
          "value": 1,
          "raw": "1"
        },
        "operator": "+",
        "right": {
          "type": "Literal",
          "start": 2,
          "end": 3,
          "value": 2,
          "raw": "2"
        }
      }
    }
  ],
  "sourceType": "module"
}

那么switch进行状态转换的关键就是节点的type属性，该属于在es5的文档中均有详细描述：

function evaluate(node) {
    let res;
    
    switch (node.type) {
        case "Program": {
            for (const stat of node.body) {
                 res = evaluate(node.body);
            }
            return res;
        }
        case "Literal":
            return node.value;
        case "ExpressionStatement":
            return evaluate(node.expressiopn);
        case "BinaryExpression": {
            switch (node.operator) {
                case "+":
                    return evaluate(node.left) + evaluate(node.right);
                case "-":
                    return evaluate(node.left) - evaluate(node.right);
                // ...
            }
        }
    }
}

于是，只要把AST生成的节点传入函数中，并执行即可得到最终结果3，即eval("1+2") === 3。

作用域 Scope

在解释执行过程中，必定会存在着变量，那么变量该如何存储呢？考虑这个问题的话，就需要考虑变量的产生环境——作用域。

作用域用于保存一个区块的变量，常量，函数等的定义信息和赋值信息；与此经常同时提起的一个名字叫做执行上下文，上下文的产生是在代码执行过程中产生，其中包含变量信息与this信息等，二者不能等同，但是可认为执行上下文中包含着作用域。

这里我们进行简化，只考虑执行过程中的作用域，同时作用域包含着作用域链，若在当前域中找不到变量信息，可继续沿着链向上寻找，类比原型链很好理解。

分类

JS中作用域主要分为三类：

• 全局作用域
  • 全局作用域中仅存在一处，即为最上级的环境。
• 函数作用域
  • 顾名思义，函数存在并执行时，内部存储函数作用域。
• 块作用域
  • 每隔block块{}都可产生作用域，如if for while等。

本解释器中，作用域中存储相关的变量信息，包含declare，get，set等部分。其中针对var const let三类变量进行存储，各自具备各自的声明与使用特点。

注：下面的Scope结构框架如此，实际使用还需增加其它元素，如变量的类型，如父作用域的处理，如错误处理等。具体见项目js-interpreter/scope.js at master · MrPluto0/js-interpreter (github.com)。

class Scope {
    constructor(type, parent = null) {
        this.type = type;  // Global Or Function Or Block
        this.parent = parent;
        this.variables = {};
    }
    declare(name) {
        this.variables[name] = undefined;
    }
    get(name) {
        if (this.variables[name])
            return this.variables[name];
        else
            return this.parent.get(name);
    }
    set(name, value) {
        if (this.variables[name])
            this.variables[name] = value;
        else
            this.parent.set(name, value);
    }
}

var

• 允许重复声明
• 声明提前至函数作用域或全局作用域
• 全局作用域下变量直接赋值，则当作var处理
  • 如：name = 1，会自动将为其进行var声明
• 全局作用域下会成为全局环境变量的属性
  • window.name
  • global.name

const

• 不允许重复声明
• 不允许重新赋值
• 不能声明提前

let

• 不允许重复声明
• 允许重新赋值
• 不能声明提前

上下文 This

This即为执行上下文中较为关键的一个属性，但是在递归中如何绑定This？有两种做法。

第一种，可以在每次递归调用evaluate的时候直接传入this，即evaluate.call(this, node)，这样便不需要额外处理this，只需在ThisExpression时，返回当前的this即可。

第二种，可以在每次产生新的上下文的时候，进行人工判断，在代码中此处为scope定义一个'this'变量来存储该环境的this，只需在ThisExpression时，通过scope.get('this')，来返回当前的this。

条件语法

条件语法这里主要涉及IfStatement和ConditionalExpression，前者不多言，后者即为三元表达式。

这两种表达式生成的AST都有共同点：

{
  "type": "IfStatement", // type: "ConditionalExpression"
  "test": {},
  "consequent": {},
  "alternate": {}
}

根据test执行的返回值是否正确，决定执行consequent语法，还是alternate语法。

循环 Loop

循环语法主要设置while do while for for of，以ForStatement为例：

{
  "type": "ForStatement",
  "init": {},
  "test": {},
  "update": {}
}

这里通过init执行一步操作，多为创建一个变量，注意此时创建的变量应该存储for的作用域中，需要新建作用域：const child = new Scope("Block", scope);

然后进行循环检测，该循环可以借用js自带的语法for或while，循环体内容执行完毕后执行update，最后判断test的条件是否正确，若正确则继续，否则退出。

break和continue

考虑这么一种情况，在遇到break和continue时，此时是一次新的递归，碰到了BreakStatement和ContinueStatement，那么直接调用break或continue是行不通的，这是便需要将其返回值进行封装，以便在原来循环的执行栈中进行操作。

这里你会发现，有个label字段，这是一种平时比较少使用的语句LabeledStatement，那具体如何处理呢，想一想。

case "WhileStatement": {
  let res;
  const child = new Scope("Block", scope);
  while (evaluate.call(this, node.test, child)) {
    res = evaluate.call(this, node.body, child);
    // 记住下面这条语句，处理函数返回。
    if (res && res.type === "return") return res; 
    // 处理break和continue
    if (res && res.type === "break") break;
    if (res && res.type === "continue") continue;
  }
  return res?.type ? res.value : res;
}
case "ContinueStatement":
  return { type: "continue", label: node.label?.name };
case "BreakStatement":
  return { type: "break", label: node.label?.name };

函数 Function

本解释器中将处理以下四类函数：

• 普通函数 function() {}
• 箭头函数 () => {}
• 异步函数 async function() {}
• 生成器函数 funtion* (){}

对于函数的处理，需创建新的函数返回，在新的函数中对原函数进行调用。其中涉及到CallExpression，FunctionExpress，FunctionDeclaration，ArrowFunctionExpression。

这里先演示普通函数的实现与调用过程（至于异步与生成器作为下面另一类内容）。

function f(a,b) {}
f(1,2)

对于上面的函数声明与调用，生成如下的简化的AST树，主要分为两部分：

{
  "type": "FunctionDeclaration",
  "id": {
    "type": "Identifier",
    "name": "f"
  },
  "params": [
    {
      "type": "Identifier",
      "name": "a"
    },
    {
      "type": "Identifier",
      "name": "b"
    }
  ],
  "body": {
    "type": "BlockStatement",
    "body": []
  }
},
{
  "type": "ExpressionStatement",
  "expression": {
    "type": "CallExpression",
    "callee": {
      "type": "Identifier",
      "name": "f"
    },
    "arguments": [
      {
        "type": "Literal",
        "value": 1,
        "raw": "1"
      },
      {
        "type": "Literal",
        "value": 2,
        "raw": "2"
      }
    ],
  }
}

函数声明

对于函数声明的封装，应该自己封装一个函数，并存储到scope信息中。

注：该声明方式会默认将函数名设置为func，函数参数长度设置为0，但是function.name和function.length属于不可写属性，此处可通过Object.defineProperty来修改。

case "FunctionExpression":
    let func = function (...args) {
      // 创建函数作用域
      const child = new Scope("Function", scope);
      // 遍历参数，将函数参数传入作用域中
      node.params.forEach((param, _i) => {
        child.declare("let", param.name);
        child.set(param.name, args[_i]);
      })
      // 执行函数体，并返回
      let res = evaluate(node.body, child);
      if (res?.type === "return") return res.value;
    };
    
    // 将函数本身加入当前作用域中，并返回
    scope.declare("let", name);
    scope.set(name, func);
    return func;

函数调用

当函数执行时，则同步参数后，即可执行：

注：此处的执行将上下文直接定为this，但是需要考虑函数作为对象的属性执行时的情况。此时this应该指向该对象。

case "CallExpression": {
    let callee = evaluate(node.callee, scope)

    return callee.apply(
        this,
        node.arguments.map(
          (subNode) => evaluate.call(this, subNode, scope).next().value
        )
    );
}

函数返回

考虑这么一种情况，在递归过程中，如果遇到了return关键字，那直接return的话，返回的是该evaluate的值，此时需要进行处理加工，其处理方式类似于前面的break和continue，但是有所不同的时，在前提的过程中，每个语句执行结果若为{type:"return", value:"xxx"}都应该直接return，直到碰到了函数体。

可查看上面函数声明的代码中对return的判断。

生成器 Generator

生成器的特点在于中断和恢复，即中断当前执行环境，恢复上一次的执行环境。

yield

gen.next()返回值为如下对象：

{
  value: "xx",
  done: false // true
}

正由于生成器的特点，yield不能像return一样前提，否则会结束当前执行内容，那么就必须在出现yield的位置，实实在在的执行yield，使得程序在此处中断。因此，递归函数就封装为 generator函数，即为function* evaluate()，否则将无法执行yield。

接下来碰到的问题就是，若将evaluate封装为生成器，那么其返回值就成为一个对象，因此需要对各处调用evaluate.call(this, node, scope)的地方进行加工：

一个比较偷懒的办法是将其写为evaluate.call(this, node, scope).next().value，next()将会执行到下一次yield时，或者return时，由于在此之前的步骤中均为一次return，故可将暂时这么做，一次next().value获取的就是返回值了。

但是倘若此前步骤中包含yield的话，那么用该办法将会不能得到正确的结果，正确的办法该怎么办呢？核心代码如下：

注：该处理方案无法进行封装，因此涉及yield层叠的缘故，只能在需要evaluate的时候，进行如下的解析。

function* sample() {
    // 表示根据 yield 输入和输出的值
    let input, output;
    let gen = evaluate.call(this, node, scope); // generator

    while (true) {
        // sample的`yield`输入值作为gen的下一个`yield`的输入值
        // gen的输出值，若已经return，则可结束sample函数，并返回
        output = gen.next(input);
        if (!output.done) {
          input = yield output.value;
        } else {
          return output.value; // break;
        }
    }
}

个人项目中仅针对测试用例，完成生成器的模拟，也即大部分地方仍使用上面所介绍的偷懒的方式，部分地方改用为以上的正规的处理方法。（要是所有都替换，代码量暴增，好不优雅www）

异步 Async

异步函数将基于 Generator 来实现，处理async和await字段。

async和await

问：一个函数如果是异步函数，那么它会如何运行？函数的内部是异步还是同步执行？

答：标记了async后，函数成为异步函数，其内部仍然是同步执行（允许异步操作）；只有在异步函数中才可以进行await操作，存在await时，函数内可以进行阻塞，直到获取await的返回值。

问：调用异步函数会产生什么返回值？

答：async和await实际上是一种语法糖，异步函数的调用默认会返回一个Promise，若异步执行该函数需要promise.then()获取返回值，但若通过await调用，则会阻塞且直接返回返回值，如下。

async funtion test() {
    async funtion f() {
        return 1;
    }

    f().then((res) => {
        console.log(res); // 1
    })
    
    console.log(await f()); // 1
}

注：异步函数改成的生成器函数中，实际上以yield来替代await，主要是实现await的阻塞功能。

鉴于以上的特性，可以使用generator来实现，将异步函数改造为生成器函数，通过包装，使得其不断地gen.next()执行，直到获取done为true的情况，将对应的value作为异步函数的返回值返回即可。这里所谈到的包装即为AsyncToGenerator函数，将将生成器函数按照异步函数的逻辑执行即可。

通过asyncToGenerator函数来同步执行异步函数，可见项目文档js-interpreter/libs.js at master · MrPluto0/js-interpreter (github.com)。

异步函数执行

关于异步的判断，可以观察异步函数的语法树中的属性async，不妨研究一下语法树的结构。

// 这里的封装函数属于关键
func = asyncToGenerator(function* (...args) {
  // 创建新的作用域
  const child = new Scope("Function", scope);
  // 参数传递
  node.params.forEach((param, _i) => {
    child.declare("let", param.name);
    child.set(param.name, args[_i]);
  });

  // 存储返回值
  let res;
  // 存储生成器对象
  let gen = evaluate.call(this, node.body, child);

  // 执行生成器的内容
  while (true) {
    res = gen.next(res);
    if (!res.done) {
      res = yield res.value;
    } else {
      res = res.value;
      return res?.type ? res.value : res;
    }
  }
});

总结

这篇文章对于JS解释器的完成来说，也仅仅是以点盖面，并没有把所有的表达式和语句类型的处理方法均给出，也是考虑到其中很多小的问题大家可以自己思考，比如对象的计算属性如何处理，赋值操作中如何处理对象的深层属性，LabeledExpression如何实现跳转等待。

这些小问题，在个人的项目中已经得到解决，但并不完备，非常欢迎大家指点与学习，也希望大家通过自己的思考能够有自己的解决方案。

我的项目：MrPluto0/js-interpreter (github.com)

若本文有出错的地方，希望大家指出~

参考文章

• 编译原理——一个编译器的各个步骤的介绍_没有标题-CSDN博客
• 理解Javascript执行过程 - 龙恩0707 - 博客园
• 什么是作用域和执行上下文 - 简书
• es5语法树节点文档 · estree/estree (github.com)
• 9k字 | Promise/async/Generator实现原理解析 - 掘金

相关项目

• MrPluto0/Lexical-Analyzer C词法处理器
• MrPluto0/dslBot DSL语言程序
• MrPluto0/js-interpreter JS解释器