如何用JavaScript实现一门编程语言 - 写一个解析器（Parser）

[llwanghong]

整篇译文的目录章节如下：

• 前言
• λanguage描述
• 写一个解析器（Parser）
  • 字符流（Character Stream）
  • 标记流（Token Stream）
  • AST
  • 解析器
• 简单的解释器（Interpreter）
  • 我们得到了什么
  • 增加新的结构
  • 我们有多快？
• CPS求值器（CPS Evaluator）
  • 保护堆栈
  • Continuations
  • Yield进阶
• 编译成JS
  • JS代码生成器
  • CPS转换器
  • 示例及改进
  • 优化器
• 总结
• 真实示例

写一个解析器（Parser）

编写一个语言解析器是一个相对稍复杂的任务。本质上，它是通过检测字符的方式将一块代码片段转化成抽象语法树（Abstract Syntax Tree，AST）。AST是程序在内存中的结构化展现，“抽象”意味着不用关心源代码具体是由什么字符组成，只需要把程序的语义表达出来即可。我写了一个单独的章节来描述我们的AST。

例如，对于下面的程序代码：

sum = lambda(a, b) {
  a + b;
};
print(sum(1, 2));

我们的解析器将会生成如下的AST（一个JavaScript对象）：

{
  type: "prog",
  prog: [
    // 第一个表达式:
    {
      type: "assign",
      operator: "=",
      left: { type: "var", value: "sum" },
      right: {
        type: "lambda",
        vars: [ "a", "b" ],
        body: {
          // the body should be a "prog", but because
          // it contains a single expression, our parser
          // reduces it to the expression itself.
          type: "binary",
          operator: "+",
          left: { type: "var", value: "a" },
          right: { type: "var", value: "b" }
        }
      }
    },
    // 第二个表达式:
    {
      type: "call",
      func: { type: "var", value: "print" },
      args: [{
        type: "call",
        func: { type: "var", value: "sum" },
        args: [ { type: "num", value: 1 },
                { type: "num", value: 2 } ]
      }]
    }
  ]
}

写解析器的一个主要难点在于如何恰当的组织代码。解析器工作层面要更高，不仅仅是如何从字符串读取字符。下面是将复杂度做到可控的几点建议：

• 多拆分些函数，保证函数足够小。每个函数保证只做好一件事即可。
• 不要试图使用正则表达式去做解析。效果不好。虽然正则表达式对词法分析器能起到作用，但我建议将它们限制在非常简单的处理上。
• 不要试图去猜测。当不确定如何解析某部分时，就当成错误抛出来（需要确保错误信息包含了错误发生的行列位置）。

为了便于理解，会将实现代码分成三部分，各部分会进一步拆分成许多小的函数：

• 字符流
• Token流（分词器Lexer）
• 解析器