前端与编译原理——用JS写一个JS解释器

栏目: 服务器 · 编程工具 · 发布时间: 5年前

内容简介:说起编译原理,印象往往只停留在本科时那些枯燥的课程和晦涩的概念。作为前端开发者,编译原理似乎离我们很远,对它的理解很可能仅仅局限于“抽象语法树(AST)”。但这仅仅是个开头而已。编译原理的使用,甚至能让我们利用JS直接写一个能运行JS代码的解释器。接触过小程序开发的同学应该知道,小程序运行的环境禁止

前端与编译原理——用JS写一个JS解释器

说起编译原理,印象往往只停留在本科时那些枯燥的课程和晦涩的概念。作为前端开发者,编译原理似乎离我们很远,对它的理解很可能仅仅局限于“抽象语法树(AST)”。但这仅仅是个开头而已。编译原理的使用,甚至能让我们利用JS直接写一个能运行JS代码的解释器。

一、为什么要用JS写JS的解释器

接触过小程序开发的同学应该知道,小程序运行的环境禁止 new Functioneval 等方法的使用,导致我们无法直接执行字符串形式的动态代码。此外,许多平台也对这些JS自带的可执行动态代码的方法进行了限制,那么我们是没有任何办法了吗?既然如此,我们便可以用JS写一个解析器,让JS自己去运行自己。

在开始之前,我们先简单回顾一下编译原理的一些概念。

二、什么是编译器

说到编译原理,肯定离不开编译器。简单来说,当一段代码经过编译器的词法分析、语法分析等阶段之后,会生成一个树状结构的“抽象语法树(AST)”,该语法树的每一个节点都对应着代码当中不同含义的片段。

比如有这么一段代码:

const a = 1
console.log(a)

经过编译器处理后,它的AST长这样:

{
  "type": "Program",
  "start": 0,
  "end": 26,
  "body": [
    {
      "type": "VariableDeclaration",
      "start": 0,
      "end": 11,
      "declarations": [
        {
          "type": "VariableDeclarator",
          "start": 6,
          "end": 11,
          "id": {
            "type": "Identifier",
            "start": 6,
            "end": 7,
            "name": "a"
          },
          "init": {
            "type": "Literal",
            "start": 10,
            "end": 11,
            "value": 1,
            "raw": "1"
          }
        }
      ],
      "kind": "const"
    },
    {
      "type": "ExpressionStatement",
      "start": 12,
      "end": 26,
      "expression": {
        "type": "CallExpression",
        "start": 12,
        "end": 26,
        "callee": {
          "type": "MemberExpression",
          "start": 12,
          "end": 23,
          "object": {
            "type": "Identifier",
            "start": 12,
            "end": 19,
            "name": "console"
          },
          "property": {
            "type": "Identifier",
            "start": 20,
            "end": 23,
            "name": "log"
          },
          "computed": false
        },
        "arguments": [
          {
            "type": "Identifier",
            "start": 24,
            "end": 25,
            "name": "a"
          }
        ]
      }
    }
  ],
  "sourceType": "module"
}

常见的JS编译器有 babylonacorn 等等,感兴趣的同学可以在 AST explorer 这个网站自行体验。

可以看到,编译出来的AST详细记录了代码中所有语义代码的类型、起始位置等信息。这段代码除了根节点 Program 外,主体包含了两个节点 VariableDeclarationExpressionStatement ,而这些节点里面又包含了不同的子节点。

正是由于AST详细记录了代码的语义化信息,所以Babel,Webpack,Sass,Less等 工具 可以针对代码进行非常智能的处理。

三、什么是解释器

如同翻译人员不仅能看懂一门外语,也能对其艺术加工后把它翻译成母语一样,人们把能够将代码转化成AST的工具叫做“编译器”,而把能够将AST翻译成目标语言并运行的工具叫做“解释器”。

在编译原理的课程中,我们思考过这么一个问题:如何让计算机运行算数表达式 1+2+3 :

1 + 2 + 3

当机器执行的时候,它可能会是这样的机器码:

1 PUSH 1
2 PUSH 2
3 ADD
4 PUSH 3
5 ADD

而运行这段机器码的程序,就是解释器。

在这篇文章中,我们不会搞出机器码这样复杂的东西,仅仅是使用JS在其runtime环境下去解释JS代码的AST。由于解释器使用JS编写,所以我们可以大胆使用JS自身的语言特性,比如this绑定、new关键字等等,完全不需要对它们进行额外处理,也因此让JS解释器的实现变得非常简单。

在回顾了编译原理的基本概念之后,我们就可以着手进行开发了。

四、节点遍历器

通过分析上文的AST,可以看到每一个节点都会有一个类型属性 type ,不同类型的节点需要不同的处理方式,处理这些节点的程序,就是“节点处理器( nodeHandler )”

定义一个节点处理器:

const nodeHandler = {
  Program () {},
  VariableDeclaration () {},
  ExpressionStatement () {},
  MemberExpression () {},
  CallExpression () {},
  Identifier () {}
}

关于节点处理器的具体实现,会在后文进行详细探讨,这里暂时不作展开。

有了节点处理器,我们便需要去遍历AST当中的每一个节点,递归地调用节点处理器,直到完成对整棵语法书的处理。

定义一个节点遍历器( NodeIterator ):

class NodeIterator {
  constructor (node) {
    this.node = node
    this.nodeHandler = nodeHandler
  }

  traverse (node) {
    // 根据节点类型找到节点处理器当中对应的函数
    const _eval = this.nodeHandler[node.type]
    // 若找不到则报错
    if (!_eval) {
      throw new Error(`canjs: Unknown node type "${node.type}".`)
    }
    // 运行处理函数
    return _eval(node)
  }

}

理论上,节点遍历器这样设计就可以了,但仔细推敲,发现漏了一个很重要的东西——作用域处理。

回到节点处理器的 VariableDeclaration() 方法,它用来处理诸如 const a = 1 这样的变量声明节点。假设它的代码如下:

VariableDeclaration (node) {
    for (const declaration of node.declarations) {
      const { name } = declaration.id
      const value = declaration.init ? traverse(declaration.init) : undefined
      // 问题来了,拿到了变量的名称和值,然后把它保存到哪里去呢?
      // ...
    }
  },

问题在于,处理完变量声明节点以后,理应把这个变量保存起来。按照JS语言特性,这个变量应该存放在一个作用域当中。在JS解析器的实现过程中,这个作用域可以被定义为一个 scope 对象。

改写节点遍历器,为其新增一个 scope 对象

class NodeIterator {
  constructor (node, scope = {}) {
    this.node = node
    this.scope = scope
    this.nodeHandler = nodeHandler
  }

  traverse (node, options = {}) {
    const scope = options.scope || this.scope
    const nodeIterator = new NodeIterator(node, scope)
    const _eval = this.nodeHandler[node.type]
    if (!_eval) {
      throw new Error(`canjs: Unknown node type "${node.type}".`)
    }
    return _eval(nodeIterator)
  }

  createScope (blockType = 'block') {
    return new Scope(blockType, this.scope)
  }
}

然后节点处理函数 VariableDeclaration() 就可以通过 scope 保存变量了:

VariableDeclaration (nodeIterator) {
    const kind = nodeIterator.node.kind
    for (const declaration of nodeIterator.node.declarations) {
      const { name } = declaration.id
      const value = declaration.init ? nodeIterator.traverse(declaration.init) : undefined
      // 在作用域当中定义变量
      // 如果当前是块级作用域且变量用var定义,则定义到父级作用域
      if (nodeIterator.scope.type === 'block' && kind === 'var') {
        nodeIterator.scope.parentScope.declare(name, value, kind)
      } else {
        nodeIterator.scope.declare(name, value, kind)
      }
    }
  },

关于作用域的处理,可以说是整个JS解释器最难的部分。接下来我们将对作用域处理进行深入的剖析。

五、作用域处理

考虑到这样一种情况:

const a = 1
{
  const b = 2
  console.log(a)
}
console.log(b)

运行结果必然是能够打印出 a 的值,然后报错: Uncaught ReferenceError: b is not defined

这段代码就是涉及到了作用域的问题。块级作用域或者函数作用域可以读取其父级作用域当中的变量,反之则不行,所以对于作用域我们不能简单地定义一个空对象,而是要专门进行处理。

定义一个作用域基类 Scope

class Scope {
  constructor (type, parentScope) {
    // 作用域类型,区分函数作用域function和块级作用域block
    this.type = type
    // 父级作用域
    this.parentScope = parentScope
    // 全局作用域
    this.globalDeclaration = standardMap
    // 当前作用域的变量空间
    this.declaration = Object.create(null)
  }

  /*
   * get/set方法用于获取/设置当前作用域中对应name的变量值
     符合JS语法规则,优先从当前作用域去找,若找不到则到父级作用域去找,然后到全局作用域找。
     如果都没有,就报错
   */
  get (name) {
    if (this.declaration[name]) {
      return this.declaration[name]
    } else if (this.parentScope) {
      return this.parentScope.get(name)
    } else if (this.globalDeclaration[name]) {
      return this.globalDeclaration[name]
    }
    throw new ReferenceError(`${name} is not defined`)
  }

  set (name, value) {
    if (this.declaration[name]) {
      this.declaration[name] = value
    } else if (this.parentScope[name]) {
      this.parentScope.set(name, value)
    } else {
      throw new ReferenceError(`${name} is not defined`)
    }
  }

  /**
   * 根据变量的kind调用不同的变量定义方法
   */
  declare (name, value, kind = 'var') {
    if (kind === 'var') {
      return this.varDeclare(name, value)
    } else if (kind === 'let') {
      return this.letDeclare(name, value)
    } else if (kind === 'const') {
      return this.constDeclare(name, value)
    } else {
      throw new Error(`canjs: Invalid Variable Declaration Kind of "${kind}"`)
    }
  }

  varDeclare (name, value) {
    let scope = this
    // 若当前作用域存在非函数类型的父级作用域时,就把变量定义到父级作用域
    while (scope.parentScope && scope.type !== 'function') {
      scope = scope.parentScope
    }
    this.declaration[name] = new SimpleValue(value, 'var')
    return this.declaration[name]
  }

  letDeclare (name, value) {
    // 不允许重复定义
    if (this.declaration[name]) {
      throw new SyntaxError(`Identifier ${name} has already been declared`)
    }
    this.declaration[name] = new SimpleValue(value, 'let')
    return this.declaration[name]
  }

  constDeclare (name, value) {
    // 不允许重复定义
    if (this.declaration[name]) {
      throw new SyntaxError(`Identifier ${name} has already been declared`)
    }
    this.declaration[name] = new SimpleValue(value, 'const')
    return this.declaration[name]
  }
}

这里使用了一个叫做 simpleValue() 的函数来定义变量值,主要用于处理常量:

class SimpleValue {
  constructor (value, kind = '') {
    this.value = value
    this.kind = kind
  }

  set (value) {
    // 禁止重新对const类型变量赋值
    if (this.kind === 'const') {
      throw new TypeError('Assignment to constant variable')
    } else {
      this.value = value
    }
  }

  get () {
    return this.value
  }
}

处理作用域问题思路,关键的地方就是在于JS语言本身寻找变量的特性——优先当前作用域,父作用域次之,全局作用域最后。反过来,在节点处理函数 VariableDeclaration() 里,如果遇到块级作用域且关键字为 var ,则需要把这个变量也定义到父级作用域当中,这也就是我们常说的“全局变量污染”。

JS标准库注入

细心的读者会发现,在定义 Scope 基类的时候,其全局作用域 globalScope 被赋值了一个 standardMap 对象,这个对象就是JS标准库。

简单来说,JS标准库就是JS这门语言本身所带有的一系列方法和属性,如常用的 setTimeoutconsole.log 等等。为了让解析器也能够执行这些方法,所以我们需要为其注入标准库:

const standardMap = {
  console: new SimpleValue(console)
}

这样就相当于往解析器的全局作用域当中注入了 console 这个对象,也就可以直接被使用了。

六、节点处理器

在处理完节点遍历器、作用域处理的工作之后,便可以来编写节点处理器了。顾名思义,节点处理器是专门用来处理AST节点的,上文反复提及的 VariableDeclaration() 方法便是其中一个。下面将对部分关键的节点处理器进行讲解。

在开发节点处理器之前,需要用到一个工具,用于判断JS语句当中的 returnbreakcontinue 关键字。

关键字判断工具 Signal

定义一个 Signal 基类:

class Signal {
  constructor (type, value) {
    this.type = type
    this.value = value
  }

  static Return (value) {
    return new Signal('return', value)
  }

  static Break (label = null) {
    return new Signal('break', label)
  }

  static Continue (label) {
    return new Signal('continue', label)
  }

  static isReturn(signal) {
    return signal instanceof Signal && signal.type === 'return'
  }

  static isContinue(signal) {
    return signal instanceof Signal && signal.type === 'continue'
  }

  static isBreak(signal) {
    return signal instanceof Signal && signal.type === 'break'
  }

  static isSignal (signal) {
    return signal instanceof Signal
  }
}

有了它,就可以对语句当中的关键字进行判断处理,接下来会有大用处。

1、变量定义节点处理器—— VariableDeclaration()

最常用的节点处理器之一,负责把变量注册到正确的作用域。

VariableDeclaration (nodeIterator) {
    const kind = nodeIterator.node.kind
    for (const declaration of nodeIterator.node.declarations) {
      const { name } = declaration.id
      const value = declaration.init ? nodeIterator.traverse(declaration.init) : undefined
      // 在作用域当中定义变量
      // 若为块级作用域且关键字为var,则需要做全局污染
      if (nodeIterator.scope.type === 'block' && kind === 'var') {
        nodeIterator.scope.parentScope.declare(name, value, kind)
      } else {
        nodeIterator.scope.declare(name, value, kind)
      }
    }
  },

2、标识符节点处理器—— Identifier()

专门用于从作用域中获取标识符的值。

Identifier (nodeIterator) {
    if (nodeIterator.node.name === 'undefined') {
      return undefined
    }
    return nodeIterator.scope.get(nodeIterator.node.name).value
  },

3、字符节点处理器—— Literal()

返回字符节点的值。

Literal (nodeIterator) {
    return nodeIterator.node.value
  }

4、表达式调用节点处理器—— CallExpression()

用于处理表达式调用节点的处理器,如处理 func()console.log() 等。

CallExpression (nodeIterator) {
    // 遍历callee获取函数体
    const func = nodeIterator.traverse(nodeIterator.node.callee)
    // 获取参数
    const args = nodeIterator.node.arguments.map(arg => nodeIterator.traverse(arg))

    let value
    if (nodeIterator.node.callee.type === 'MemberExpression') {
      value = nodeIterator.traverse(nodeIterator.node.callee.object)
    }
    // 返回函数运行结果
    return func.apply(value, args)
  },

5、表达式节点处理器—— MemberExpression()

区分于上面的“表达式调用节点处理器”,表达式节点指的是 person.sayconsole.log 这种函数表达式。

MemberExpression (nodeIterator) {
    // 获取对象,如console
    const obj = nodeIterator.traverse(nodeIterator.node.object)
    // 获取对象的方法,如log
    const name = nodeIterator.node.property.name
    // 返回表达式,如console.log
    return obj[name]
  }

6、块级声明节点处理器—— BlockStatement()

非常常用的处理器,专门用于处理块级声明节点,如函数、循环、 try...catch... 当中的情景。

BlockStatement (nodeIterator) {
    // 先定义一个块级作用域
    let scope = nodeIterator.createScope('block')

    // 处理块级节点内的每一个节点
    for (const node of nodeIterator.node.body) {
      if (node.type === 'VariableDeclaration' && node.kind === 'var') {
        for (const declaration of node.declarations) {
          scope.declare(declaration.id.name, declaration.init.value, node.kind)
        }
      } else if (node.type === 'FunctionDeclaration') {
        nodeIterator.traverse(node, { scope })
      }
    }

    // 提取关键字(return, break, continue)
    for (const node of nodeIterator.node.body) {
      if (node.type === 'FunctionDeclaration') {
        continue
      }
      const signal = nodeIterator.traverse(node, { scope })
      if (Signal.isSignal(signal)) {
        return signal
      }
    }
  }

可以看到这个处理器里面有两个 for...of 循环。第一个用于处理块级内语句,第二个专门用于识别关键字,如循环体内部的 breakcontinue 或者函数体内部的 return

7、函数定义节点处理器—— FunctionDeclaration()

往作用当中声明一个和函数名相同的变量,值为所定义的函数:

FunctionDeclaration (nodeIterator) {
    const fn = NodeHandler.FunctionExpression(nodeIterator)
    nodeIterator.scope.varDeclare(nodeIterator.node.id.name, fn)
    return fn    
  }

8、函数表达式节点处理器—— FunctionExpression()

用于定义一个函数:

FunctionExpression (nodeIterator) {
    const node = nodeIterator.node
    /**
     * 1、定义函数需要先为其定义一个函数作用域,且允许继承父级作用域
     * 2、注册`this`, `arguments`和形参到作用域的变量空间
     * 3、检查return关键字
     * 4、定义函数名和长度
     */
    const fn = function () {
      const scope = nodeIterator.createScope('function')
      scope.constDeclare('this', this)
      scope.constDeclare('arguments', arguments)

      node.params.forEach((param, index) => {
        const name = param.name
        scope.varDeclare(name, arguments[index])
      })

      const signal = nodeIterator.traverse(node.body, { scope })
      if (Signal.isReturn(signal)) {
        return signal.value
      }
    }

    Object.defineProperties(fn, {
      name: { value: node.id ? node.id.name : '' },
      length: { value: node.params.length }
    })

    return fn
  }

9、this表达式处理器—— ThisExpression()

该处理器直接使用JS语言自身的特性,把 this 关键字从作用域中取出即可。

ThisExpression (nodeIterator) {
    const value = nodeIterator.scope.get('this')
    return value ? value.value : null
  }

10、new表达式处理器—— NewExpression()

this 表达式类似,也是直接沿用JS的语言特性,获取函数和参数之后,通过 bind 关键字生成一个构造函数,并返回。

NewExpression (nodeIterator) {
    const func = nodeIterator.traverse(nodeIterator.node.callee)
    const args = nodeIterator.node.arguments.map(arg => nodeIterator.traverse(arg))
    return new (func.bind(null, ...args))
  }

11、For循环节点处理器—— ForStatement()

For循环的三个参数对应着节点的 inittestupdate 属性,对着三个属性分别调用节点处理器处理,并放回JS原生的for循环当中即可。

ForStatement (nodeIterator) {
    const node = nodeIterator.node
    let scope = nodeIterator.scope
    if (node.init && node.init.type === 'VariableDeclaration' && node.init.kind !== 'var') {
      scope = nodeIterator.createScope('block')
    }

    for (
      node.init && nodeIterator.traverse(node.init, { scope });
      node.test ? nodeIterator.traverse(node.test, { scope }) : true;
      node.update && nodeIterator.traverse(node.update, { scope })
    ) {
      const signal = nodeIterator.traverse(node.body, { scope })
      
      if (Signal.isBreak(signal)) {
        break
      } else if (Signal.isContinue(signal)) {
        continue
      } else if (Signal.isReturn(signal)) {
        return signal
      }
    }
  }

同理, for...inwhiledo...while 循环也是类似的处理方式,这里不再赘述。

12、If声明节点处理器—— IfStatemtnt()

处理If语句,包括 ifif...elseif...elseif...else

IfStatement (nodeIterator) {
    if (nodeIterator.traverse(nodeIterator.node.test)) {
      return nodeIterator.traverse(nodeIterator.node.consequent)
    } else if (nodeIterator.node.alternate) {
      return nodeIterator.traverse(nodeIterator.node.alternate)
    }
  }

同理, switch 语句、三目表达式也是类似的处理方式。

---

上面列出了几个比较重要的节点处理器,在es5当中还有很多节点需要处理,详细内容可以访问 这个地址 一探究竟。

七、定义调用方式

经过了上面的所有步骤,解析器已经具备处理es5代码的能力,接下来就是对这些散装的内容进行组装,最终定义一个方便用户调用的办法。

const { Parser } = require('acorn')
const NodeIterator = require('./iterator')
const Scope = require('./scope')

class Canjs {
  constructor (code = '', extraDeclaration = {}) {
    this.code = code
    this.extraDeclaration = extraDeclaration
    this.ast = Parser.parse(code)
    this.nodeIterator = null
    this.init()
  }

  init () {
    // 定义全局作用域,该作用域类型为函数作用域
    const globalScope = new Scope('function')
    // 根据入参定义标准库之外的全局变量
    Object.keys(this.extraDeclaration).forEach((key) => {
      globalScope.addDeclaration(key, this.extraDeclaration[key])
    })
    this.nodeIterator = new NodeIterator(null, globalScope)
  }

  run () {
    return this.nodeIterator.traverse(this.ast)
  }
}

这里我们定义了一个名为 Canjs 的基类,接受字符串形式的JS代码,同时可定义标准库之外的变量。当运行 run() 方法的时候就可以得到运行结果。

八、后续

至此,整个JS解析器已经完成,可以很好地运行ES5的代码(可能还有bug没有发现)。但是在当前的实现中,所有的运行结果都是放在一个类似沙盒的地方,无法对外界产生影响。如果要把运行结果取出来,可能的办法有两种。第一种是传入一个全局的变量,把影响作用在这个全局变量当中,借助它把结果带出来;另外一种则是让解析器支持 export 语法,能够把 export 语句声明的结果返回,感兴趣的读者可以自行研究。

最后,这个JS解析器已经在我的Github上开源,欢迎前来交流~

https://github.com/jrainlau/c...

参考资料

从零开始写一个Javascript解析器

微信小程序也要强行热更代码,鹅厂不服你来肛我呀

jkeylu/evil-eval


以上所述就是小编给大家介绍的《前端与编译原理——用JS写一个JS解释器》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

未来简史

未来简史

[以色列] 尤瓦尔·赫拉利 / 林俊宏 / 中信出版集团 / 2017-2 / 68.00元

进入21世纪后,曾经长期威胁人类生存、发展的瘟疫、饥荒和战争已经被攻克,智人面临着新的待办议题:永生不老、幸福快乐和成为具有“神性”的人类。在解决这些新问题的过程中,科学技术的发展将颠覆我们很多当下认为无需佐证的“常识”,比如人文主义所推崇的自由意志将面临严峻挑战,机器将会代替人类做出更明智的选择。 更重要的,当以大数据、人工智能为代表的科学技术发展的日益成熟,人类将面临着从进化到智人以来z......一起来看看 《未来简史》 这本书的介绍吧!

MD5 加密
MD5 加密

MD5 加密工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换