开发笔记:类Lisp解释器JavaScript实现

离职之前得把这坑填了……可能会有些仓促，如果有错误之处之后还请大家自行勘误啦。

类 Lisp 语言语法

(define fib (lambda (n)
(if ( (+ (fib (- n 1)) (fib (- n 2))))))

观察上述斐波那契数生成函数。

1. 使用 define 关键字绑定变量与实体


2. 全部使用前缀表达式


3. 没有 return 关键字


4. 循环多采用递归实现


5. 函数被称为“lambda表达式”，使用 lambda 关键字定义


6. 函数必须有返回值

编译原理基本知识

使用某种语言来编写的一段程序本质上是字符串，编译器/解释器的任务是将这段字符串翻译为某个“执行器”可以理解的编码。

我认为编译器和解释器最大的不同在于，前者存在明显输出，且输出为某执行器可以理解的字符串（编码）；后者没有明显输出，它直接执行了该段字符串（源程序）所表达的东西（此处应当被提出质疑）。

本文只介绍解释器的基本组成。

解释器从接受源程序到最终执行的基本过程有：

1. 词法分析。这个步骤会将源代码分解为该语言的最小组成元素（一个一个的短字符串）。如 var a = 1; 会被分解为 [‘var‘, ‘a‘, ‘=‘, ‘1‘]。形如这样的短字符串，我们称其为“Token”。


2. 语法分析。这个步骤会根据该语言的自身语法规则分析 Token 列表，检查源代码是否有语法错误，如果没有，则解析出一个抽象语法树（AST），语义及代码块之间的关系都由树状数据结构进行描述。


3. 执行。当 AST 被生成之后，解释器会继续对 AST 进行分析，遵照 AST 表达出的语义来执行，其执行结果就是源代码所想要的执行结果。一些语言特性，比如闭包，就是在执行函数中实现的。

实现

接下来我们将实现一个支持整数与浮点数运算、数组类型、lambda 表达式，有着基本逻辑语句的类 Lisp 语言解释器。

词法分析

由于类 Lisp 语言本身语法比较简洁，所以词法分析的实现也会比较简单：

function tokenize(program) {
return program.replace(/\(/g, ‘ ( ‘).replace(/\)/g, ‘ ) ‘).split(‘ ‘)
}

语法分析

在生成 AST 的过程中，需要将每一个 Token 的“身份”做确认，比如 var 和 a 是关键字，1 是整数，给 Token 做身份标记。这里使用数组实现 AST。

// 生成抽象语法树
function read_from_tokens(tokens) {
if (tokens.length === 0) {
throw new Error(‘unexpected EOF while reading‘)
}
let token = tokens.shift()
while (token === ‘‘) {
token = tokens.shift()
}
if (‘(‘ === token) {
let L = []
while (tokens[0] === ‘‘) {
tokens.shift()
}
while (tokens[0] !== ‘)‘) {
L.push(read_from_tokens(tokens))
while (tokens[0] === ‘‘) {
tokens.shift()
}
}
tokens.shift()
return L
} else if (‘)‘ === token) {
throw new Error(‘unexpected )‘)
} else {
return atom(token)
}
}
// 元类型 Meta，所有数据类型的基类，随着解释器的完善会变得有用，亦在语义的角度可体现出其合理性，但在本文中不做讨论
class Meta {
constructor(value) {
this.value = value
}
}
// 符号类型 如 if define 自定义变量等语言关键字都属于此类型
class Sym extends Meta {
constructor(value) {
super(value)
}
}
// 将 token 的类型具体化
function atom(token) {
let temp = parseInt(token)
if (isNaN(temp)) {
return new Sym(token)
} else if (token - temp === 0) {
return temp
} else {
return parseFloat(token)
}
}

执行

执行的过程是解释器的核心，在这里实现为一个 eval 函数。

eval 函数

eval 函数的大致结构是一个状态机，按照该语言的语法规则对 AST 进行解析。

function eval(x, env=global_env) {
if (x instanceof Sym) { // 如果该 Token 是关键字
return env.find(x.value)[x.value] // 在当前作用域中寻找与该 Token 绑定的实体
} else if (! (x instanceof Array)) { // 不是数组
return x // 直接返回（因为此时会认为它是整数或浮点数）
} else if (x[0].value == ‘if‘) { // 如果是 if
let [sym, test, conseq, alt] = x // 按照该语言语法中约定的 if 语句的格式提取信息
let exp = (eval(test, env) ? conseq : alt)
return eval(exp, env)
} else if (x[0].value == ‘define‘) { // 如果是 define
let [vari, exp] = x.slice(1)
env.add(vari.value, eval(exp, env))
} else if (x[0].value == ‘lambda‘) { // 如果是 lambda
let [parms, body] = x.slice(1)
return new Procedure(parms, body, env) // 创建一个 Procedure 实例
} else if (x[0].value == ‘quote‘) { // 如果是 quote
let [sym, exp] = x
return exp
} else { // 否则（这里可能的情况是：x 是一个数组或一个过程（函数，在这里的实现为 Procedure 的实例，下面会讲到））
let proc = eval(x[0], env)
let args = []
x.slice(1).forEach(function(arg) {
args.push(eval(arg, env))
})
if (proc instanceof Procedure) {
return proc.execute.call(proc, args)
}
return proc.apply(this, args)
}
}

函数与环境

在该语言中，我们规定，作用域的界线是函数，且该作用域是词法作用域（与 Javascript 相同）。
所以每当碰到函数调用的时候，我们都需要创建一个新的求值环境，并使该函数被调用时所在的环境成为这个新的求值环境的父环境（如果不明白为什么这样规定，请自行搜索词法作用域）。故当我们在任何地方查找变量时，都应顺着环境链（作用域链）向上查找，直到找到。如果找不到，则抛异常。
由此，我们可以将作用域理解为一个类似单向链表的数据结构。

// Procedure 类，该语言中函数的实现
class Procedure {
constructor(parms, body, env) {
this.parms = parms
this.body = body
this.env = env
}
execute(args) {
return eval(this.body, new Env(this.parms, args, this.env))
}
}
// Env 类，该语言中求值环境的实现
class Env {
constructor(parms=[], args=[], outer=null) {
this.e = new Object()
this.init(parms, args)
this.outer = outer // 父环境
}
// 在该环境中查找某个变量
find(vari) {
if ((! (vari in this.e)) && (! this.outer)) {
throw new ReferenceError(‘variable ‘ + vari + ‘ is undefined.‘)
}
return vari in this.e ? this.e : this.outer.find(vari)
}
init(keys, values) {
keys.forEach((key, index) => {
this.e[key.value] = values[index]
})
}
assign(subEnv) {
Object.assign(this.e, subEnv)
}
add(key, value) {
this.e[key] = value
}
}
// 初始化一个全局环境
let global_env = new Env()
global_env.assign(baseEnv)

尾声

至此，这个简单的解释器就已经完成了，涉及到更多细节，如异常定义、全局环境定义，可以点此查看完整的代码。

我建议大家如果有兴趣可以自己动手实现一下，对解释器原理以及闭包会有更深刻的理解。

本文的完成比较仓促，如果大家有什么疑问可以点此阅读该解释器的 Python 实现，作者讲解得非常详细，也有很多测试用例，我正是阅读了这篇文章才写了 Javascript 版。

如果有任何错误之处，请自行勘误，或者通过邮箱（[email&＃160;protected]）和 GitHub （Sevenskey）联系我。

感谢阅读qwq