说起编译原理，印象往往只停留在本科时那些枯燥的课程和晦涩的概念。作为前端开发者，编译原理似乎离我们很远，对它的理解很可能仅仅局限于“抽象语法树（ AST ）”。但这仅仅是个开头而已。编译原理的使用，甚至能让我们利用 JS 直接写一个能运行 JS 代码的解释器。
接触过小程序开发的同学应该知道，小程序运行的环境禁止new Function，eval等方法的使用，导致我们无法直接执行字符串形式的动态代码。此外，许多平台也对这些 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 编译器有
babylon，acorn等等，感兴趣的同学可以在AST explorer这个网站自行体验。
可以看到，编译出来的 AST 详细记录了代码中所有语义代码的类型、起始位置等信息。这段代码除了根节点Program外，主体包含了两个节点VariableDeclaration和ExpressionStatement，而这些节点里面又包含了不同的子节点。
正是由于 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，则需要把这个变量也定义到 父级作用域当中，这也就是我们常说的“全局变量污染”。
细心的读者会发现，在定义Scope基类的时候，其全局作用域globalScope被赋值了一个standardMap对象，这个对象就是 JS 标准库。
简单来说，JS 标准库就是 JS 这门语言本身所带有的一系列方法和属性，如常用的setTimeout，console.log等等。为了让解析器也能够执行这些方法，所以我们需要为其 注入标准库：
const standardMap = {
console: new SimpleValue(console)
}
这样就相当于往解析器的全局作用域当中注入了console这个对象，也就可以直接被使用了。
在处理完节点遍历器、作用域处理的工作之后，便可以来 编写节点处理器了。顾名思义，节点处理器是专门用来处理 AST 节点的，上文反复提及的VariableDeclaration()方法便是其中一个。下面将对部分关键的节点处理器进行讲解。
在开发节点处理器之前，需要用到一个工具，用于判断 JS 语句当中的return，break，continue关键字。
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
}
}
有了它，就可以对 语句当中的关键字进行判断处理，接下来会有大用处。
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)
}
}
},
Identifier()专门用于从作用域中获取标识符的值。
Identifier (nodeIterator) {
if (nodeIterator.node.name === 'undefined') {
return undefined
}
return nodeIterator.scope.get(nodeIterator.node.name).value
},
Literal()返回字符节点的值。
Literal (nodeIterator) {
return nodeIterator.node.value
}
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)
},
MemberExpression()区分于上面的“表达式调用节点处理器”，表达式节点指的是person.say，console.log这种函数表达式。
MemberExpression (nodeIterator) {
// 获取对象，如 console
const obj = nodeIterator.traverse(nodeIterator.node.object)
// 获取对象的方法，如 log
const name = nodeIterator.node.property.name
// 返回表达式，如 console.log
return obj[name]
}
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循环。第一个用于处理 块级内语句，第二个专门用于识别关键字，如循环体内部的break，continue或者函数体内部的return。
FunctionDeclaration()往作用当中声明一个和函数名相同的变量，值为所定义的函数：
FunctionDeclaration (nodeIterator) {
const fn = NodeHandler.FunctionExpression(nodeIterator)
nodeIterator.scope.varDeclare(nodeIterator.node.id.name, fn)
return fn
}
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
}
ThisExpression()该处理器直接使用 JS 语言自身的特性，把this 关键字从作用域中取出即可。
ThisExpression (nodeIterator) {
const value = nodeIterator.scope.get('this')
return value ? value.value : null
}
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))
}
ForStatement()For 循环的三个参数对应着节点的init，test，update属性，对着三个属性分别调用节点处理器处理，并放回 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...in，while和do...while循环也是类似的处理方式，这里不再赘述。
IfStatemtnt()处理 If 语句，包括if，if...else，if...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/canjs
这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.