如何编写一个简单的解释器

发表于 | 分类于

背景

上一篇文章中，我们编写了一个简单的 parser，

将字符串转换成了有结构的数据 AST，

也提到了 parser 其实只是编译领域中很小的一部分业务。


对于每一种常见的编程语言来说，一般都有很多成熟的 parser 库供选择，

很少有场景需要从零开始实现一个 parser。

但我们不同，为了练习，为一门极简的编程语言实现一个 parser。


本文我们将继续往下写，给这门语言实现一个简单的解释器吧。

刚好几年前我用 Scheme 写过一个类似的解释器，正好可以接上了。


下文源码地址在这里：github: tiny-language

回顾解析

这个解析过程，跟上文逻辑相同，只是用 typescript 重写了一遍。

并且适当的进行了文件拆分，parser 入口在这里 github: tiny-parser/parse。

它的结构跟之前介绍的 parser 写法并无二致，为了完整性起见，这里还是再贴一下吧，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
export function letParse() {
  let sourceCode: string;
  let length: number;
  let pos: number;
  let token: Token;

  return parse;

  // ---- ---- ---- ---- ---- ---- ---- ----

  /**
   * syntax
   * 
   * Expr = Atom | List
   * Atom = Identifier
   * List = '(' Exprs ')'
   * Exprs = Expr Exprs
   */
  function parse(code): Node {
  }

  // ---- ---- ---- ---- ---- ---- ---- ----

  /**
   * 向后扫描下一个 token，并修改当前 `token` 变量
   */
  function nextToken() {    
  }
};

主要由 3 部分构成：

  • 闭包内的全局变量：sourceCode、length、pos、token

  • 解析入口函数：parse

  • 词法分析器：nextToken


值得一提的时，我们手写的 parser 采用了递归下降解析的方法，

parse 和几个 parseXXX 函数互相递归，完成了在字符串递归结构上进行解析的过程。

解释器

对代码进行解释，指的是直接执行代码得到结果，不用翻译成其他代码再执行。

一个比较简单的解释方式是，直接在 AST 结构上进行递归 eval。

我们可以假定每一个表达式的含义，是由它的子表达式决定的。


所以，当我们 eval (a b) 时，其实是在讨论 a 和 b 如何解释的问题。

一个解释器的常见结构是这样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
export function letEval() {
  const env = [{}];

  return function (ast) {
    return theEval(ast, env);
  };

  // ---- ---- ---- ---- ---- ---- ---- ----

  function theEval(ast, env) {
    const { nodeKind, value } = ast;

    switch (nodeKind) {
      case NodeKind.Atom:
        return evalAtom(value, env);

      case NodeKind.List:
        return evalList(value, env);

      default:
        throw new Error(`unexpected node kind: ${nodeKind}`);
    }
  }

  function evalAtom(value, env) {
  }

  /**
   * 列表：要么是一个特殊算符调用，要么是一个函数调用
   */
  function evalList(value, env) {
  }
};

它比 parser 的结构更简单，只有一个闭包内的全局变量 env 为表达式的求值环境，

剩下的都是互递归一些 evalXXX 函数了。

eval 每个表达式的时候，要分 AST 节点类型的不同进行处理。

实现函数定义

一个常见的编程语言构成要素就是函数了，我们来看下如何在这门极简的编程语言中添加函数特性。

我们希望的函数定义是这样的，

1
(lambda (x) (add x 1))

这个表达式定义了一个匿名函数，它接收 x 作为参数，返回 x+1 的结果。

因此，我们实际关心的是，以上字符串被解析成 AST 之后，如何 eval 的问题。


我是这样实现的，

1
2
3
4
5
6
7
8
9
10
11
12
function evalLambda(value, env) {
  const [, paramList, body] = value;
  return createFunc(paramList, body);
}

export function createFunc(paramList, body, env?) {
  return {
    paramList,
    body,
    env,
  };
}

先从 AST 中拿到 paramList 子节点，对应着 (x)，

以及 body 子节点，对应着 (add x 1)，

然后创建了一个对象 { paramList, body, env? }（这个 env 为什么是可选的后文会说）。


创建一个对象，就是把函数定义相关的 AST 节点信息都存起来了，

然后我们看函数调用的时候如何执行，

首先我们是这样表示函数定义的，把函数的定义放在前面，参数放在后面，然后用括号围起来。

1
2
3
4
(
  (lambda (x) (add x 1))
  2
)

这个字符串解析成 AST 之后，我会对它这样 eval，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function evalFuncApply(func, funcArgs, env) {
  const { paramList, body, env: funcDefEnv } = func;
  const afterEvalFuncArgs = funcArgs.map(expr => theEval(expr, env));

  const frame = {};
  paramList.value.forEach((param, index) => {
    frame[param.value.text] = afterEvalFuncArgs[index];
  });

  env.push(frame);
  const funcReturn = evalList(body.value, env);
  env.pop(frame);

  return funcReturn;
}

其中 func 就是上文 lambda 创建的那个 js 对象 { paramList, body, env? }，

我们可以从 func 中拿出里面的 AST 信息，借此可以知道形参列表为 (x)。


funcArgs 就是传入的实参，本例中为 lambda 表达式后面的那个 2。

然后我们要做的事情，是创建了一个 “栈帧” frame，它里面保存了形参名与实参的映射关系，

即，{ x: 2 }。


有了这个映射关系之后，就把这个栈帧压入当前的求值环境中，

再在这个新环境中求值函数体 body，

求值完后，再把栈帧弹出来，这样就是实现了函数调用后恢复环境的功能。

1
2
3
env.push(frame);
const funcReturn = evalList(body.value, env);
env.pop(frame);

作用域

动态作用域

作用域指定了标识符（变量）的查找规则，

上文我们实现的 eval 函数，是动态作用域的，

指的是每次函数调用，都是针对全局 env 在做压栈和弹栈操作。


动态作用域的语言，有一个很好玩的特性，

1
2
3
4
5
(begin
  (define f (lambda (x) (lambda (y) (add x y))))
  (define g (f 1))
  (define x 100)
  (display (g 2)))

这个结果会 102，而不是 3。


我们改写成 js 代码来看看，到底有什么问题。

1
2
3
4
5
6
7
8
9
10
const f = x => {
  return y => {
    return x + y;
  }
};

const g = f(1);
const x = 100;

console.log(g(2));  // 3

由于 js 是的作用域规则是静态的（词法的），不是我们刚才实现的那种动态的，

所以，在 js 中执行上述代码会返回 3。

因为 x 的值会被 “闭包” 在 f 中，外层设置 x = 1 不会影响到它。


但是为什么我们实现的 eval 会返回 102 呢？

这是因为函数 f 返回之后，全局 env 又会退到最初的状态了，

并没有保存 {x: 1} 这个值。

对 g 进行调用时（即求值 (add x y) 时），x 是多少完全，取决于全局 env 里 x 设置了多少。

静态作用域

那么如何实现像 js 那样的静态（词法）作用域特性呢？

神奇的是，并不需要修改多少代码。


第一步，我们需要将函数定义时的那个环境存起来，

1
2
3
4
5
6
7
function evalLambda(value, env) {
  const [, paramList, body] = value;

  // 词法作用域：将 lambda 定义时的环境保存下来
  const funcDefEnv = JSON.stringify(env);
  return createFunc(paramList, body, funcDefEnv);
}

为了简单起见，我们的 env 是一个数组，但 js 中对于数组的更改是引用修改，

无法作为快照存起来，所以这里就直接粗糙的将它序列化为字符串了，

更好的办法应该是实现为一个链表，保存当前 env 所指向的位置。


第二步，在对函数调用表达式进行求值的时候，我们要传入函数定义时的这个环境，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function evalFuncApply(func, funcArgs, env) {
  const { paramList, body, env: funcDefEnv } = func;
  const afterEvalFuncArgs = funcArgs.map(expr => theEval(expr, env));

  const frame = {};
  paramList.value.forEach((param, index) => {
    frame[param.value.text] = afterEvalFuncArgs[index];
  });

  // 确定函数调用时的求值环境：词法作用域：函数定义时的环境
  const funcEvalEnv = JSON.parse(funcDefEnv);

  funcEvalEnv.push(frame);
  const funcReturn = evalList(body.value, funcEvalEnv);
  funcEvalEnv.pop(frame);

  return funcReturn;
}

我们从 func 中拿出了之前序列化的 env 快照之后，重新解析为 js 对象，

然后让函数体在这个环境中求值。

1
2
3
4
5
(begin
  (define f (lambda (x) (lambda (y) (add x y))))
  (define g (f 1))
  (define x 100)
  (display (g 2)))

对于里面那个 (lambda (y) (add x y)) 来说，它定义的时候，环境中是由 x 的值的，

因为它在 (lambda (x) ...) 函数体中。

这样我们就实现了静态（词法）作用域，现在代码的执行结果应该是 3 了。

实现递归

一个递归函数是可以不停机的，因此理论上它可以执行任意复杂的计算，例如 js 中计算阶乘的函数，

1
2
3
4
5
const fact = function (n) {
  return n == 0 ? 1 : n * fact(n - 1);
};

console.log(fact(5));  // 120

fact 函数体中又调用了自己，这也许需要在计算函数求值环境时，把函数自己也放到 env 中。

实践上就是这么做的，但也可以不这样做。


因为我们可以借用 Y 组合子来实现递归功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const yCombinator = function (k) {
  const f = function (g) {
    return g(g);
  };

  const p = function (r) {
    return function (n) {
      return k(r(r))(n);
    };
  };

  return f(p);
};

const factProto = function (h) {
  return function (x) {
    return x == 0 ? 1 : x * h(x - 1);
  };
};

console.log(yCombinator(factProto)(5));  // 120

factProto 这个函数内部，只需要调用它的形参 h 就可以实现递归功能了，

因此，Y 组合子可以对匿名函数实现递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(begin
  (define y-combinator (lambda (k) (begin
    (define f (lambda (g)
      (g g)))
    (define p (lambda (r)
      (lambda (n)
        ((k (r r)) n))))
    (f p))))

  (define fact-proto (lambda (h)
    (lambda (x)
      (if (equal x 0) 1 (mul x (h (sub x 1)))))))

  (display ((y-combinator fact-proto) 5)))

以上代码在我们的实现中是可以运行的。

结语

本文介绍了如何实现编写一个简单的解释器，分析了 eval 的写法套路。

实现了动态作用域和静态（词法）作用域这两种语言特性。

因为语法本身就简单，所以 eval 对 AST 进行递归解释的时候，也变得简单了。


实际工作中用到的那些编程语言，处理起来就没有这样简单了，

有时还需要满足各种极端的性能要求，或者处理各种边界情况。


但大部分工作，有适当的编程经验也应足够了，

所以，最重要的还是日积月累所得来的编程方法，以及在有限资源的情况下把项目做成能力。

编译领域也有很多困难的课题，我就是外行了，希望以后有机会深入学习一下。