类 Lisp 语言语法

(define fib (lambda (n)    (if (< n 2) 1    (+ (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 版。

如果有任何错误之处，请通过邮箱（sevenskey@163.com）和 GitHub （Sevenskey）联系我。

感谢阅读qwq