如何用JavaScript实现一门编程语言 - 解析器

[llwanghong]

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

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

解析器（Parser）

解析器会按照上一节AST中的描述创建出各种类型的AST节点。

得益于前面的分词器，解析器可以直接操作标记流而不用处理单个字符。为了降低复杂度，它同样定义了很多工具函数。这里首先讨论一下构成解析器的主要函数。我们从一个上层的lambda解析器开始讲起：

function parse_lambda() {
    return {
        type: "lambda",
        vars: delimited("(", ")", ",", parse_varname),
        body: parse_expression()
    };
}

解析标记流的过程中，当遇到lambda关键字则会调用上面的函数，所以它关心的就是解析参数名字：被圆括号包裹并由逗号分隔。相比于直接将代码实现在parse_lambda中，我更倾向于写一个delimited函数，delimited接收start，stop，separator及parser四个参数，parser是一个函数，会解析start和stop之间的标记。上面parse_lambda中将parse_varname函数传递给parser，parse_varname函数在解析到非变量时会抛出错误。parse_lambda函数体是一个表达式，所以可通过parse_expression解析得到。

delimited是一个相对底层的函数：

function delimited(start, stop, separator, parser) {
    var a = [], first = true;
    skip_punc(start);
    while (!input.eof()) {
        if (is_punc(stop)) break;
        if (first) first = false; else skip_punc(separator);
        if (is_punc(stop)) break; // the last separator can be missing
        a.push(parser());
    }
    skip_punc(stop);
    return a;
}

正如你所看到的，它使用了更多的工具函数：is_punc和skip_punc。当前token如果是给定的符号，is_punc会返回true（不会消耗掉当前token），skip_punc会确认token是给定的符号（否则会抛错）并将其从输入流中丢弃。

解析整体程序（prog节点）的函数可能是最简单的：

function parse_toplevel() {
    var prog = [];
    while (!input.eof()) {
        prog.push(parse_expression());
        if (!input.eof()) skip_punc(";");
    }
    return { type: "prog", prog: prog };
}

由于不支持语句，所以我们就简单通过不停地调用parse_expression()函数来读取输入流中的表达式。使用skip_punc(";")因为表达式要求由分号分隔。

另外一个简单的示例：parse_if()：

function parse_if() {
    skip_kw("if");
    var cond = parse_expression();
    if (!is_punc("{")) skip_kw("then");
    var then = parse_expression();
    var ret = { type: "if", cond: cond, then: then };
    if (is_kw("else")) {
        input.next();
        ret.else = parse_expression();
    }
    return ret;
}

parse_if中通过skip_kw（判断当前token如果不是给定的关键字会抛出错误）跳过if关键字 ，通过parse_expression()来读取条件。接下来，如果条件成立分支（consequent branch）不是以左花括号“{”开始，则要求有then关键字（如果不要求then关键字，这样的语法可能会太罕见）。分支就是表达式，所以我们通过parse_expression()解析它们。else 分支是可选的，所以需要先检测关键字是否存在再来决定是否解析它。

有很多小工具函数的好处就是能很大程度上保持代码简洁。我们几乎像使用了专门用做解析的高级语言一样来实现解析器。所有这些小工具函数是“互斥的”，例如，parse_atom()函数是主要的调度者 — 基于当前的token来调用其它函数。其中一个就是parse_if()（当前token为 if 时会被调用) ，并且它会进一步调用parse_expression()。但parse_expression()会再次调用parse_atom()。之所以没有发生死循环，是因为每步处理中，每个函数都会至少消费掉一个token。

上述类型的解析器叫做“递归下降解析器”（recursive descent parser），也可能算是可以手写实现的最简单类型。

更低层次：parse_atom()和parse_expression()

parse_atom()依据当前的token完成了主要的调度工作：

function parse_atom() {
    return maybe_call(function(){
        if (is_punc("(")) {
            input.next();
            var exp = parse_expression();
            skip_punc(")");
            return exp;
        }
​
        // This is the proper place to implement unary operators.
        // Following is the code for boolean negation, which is present
        // in the final version of lambda.js, but I'm leaving it out
        // here since support for it is not implemented in the interpreter
        // nor compiler, in this tutorial:
        //
        // if (is_op("!")) {
        //     input.next();
        //     return {
        //         type: "not",
        //         body: parse_atom()
        //     };
        // }
​
        if (is_punc("{")) return parse_prog();
        if (is_kw("if")) return parse_if();
        if (is_kw("true") || is_kw("false")) return parse_bool();
        if (is_kw("lambda") || is_kw("λ")) {
            input.next();
            return parse_lambda();
        }
        var tok = input.next();
        if (tok.type == "var" || tok.type == "num" || tok.type == "str")
            return tok;
        unexpected();
    });
}

如果解析到了一个开括号，则其必定是一个括号表达式 — 因此首先会跳过开括号，然后调用parse_expression()并预期以闭括号结尾。如果解析到了某个关键字，则会调用对应关键字的解析函数。如果解析到了一个常量或者标识符，则会原样返回token。如果所有情况都未满足，则会调用unexpected()抛出一个错误。

当期望是一个原子表达式（atomic expression）但是解析到了“{”，解析器会调用parse_prog来解析整个序列的表达式。正如下面所定义的。它做了一些小的优化 — 如果prog节点为空，则直接返回 FALSE。如果程序只包含一个表达式，则返回表达式的解析结果。否则返回一个包含表达式的"prog"节点。

// we're going to use the FALSE node in various places,
// so I'm making it a global.
var FALSE = { type: "bool", value: false };
​
function parse_prog() {
    var prog = delimited("{", "}", ";", parse_expression);
    if (prog.length == 0) return FALSE;
    if (prog.length == 1) return prog[0];
    return { type: "prog", prog: prog };
}

下面是parse_expression()函数。 与parse_atom()相反，这个函数将会使用maybe_binary()来尽可能地向右扩展一个表达式，将会在下面解释。

function parse_expression() {
    return maybe_call(function(){
        return maybe_binary(parse_atom(), 0);
    });
}

maybe_*函数

这些函数会根据表达式后面跟随的具体内容来决定是用另外一个节点来包裹表达式，还是直接按原样返回表达式。

maybe_call()非常简单。接收一个解析当前表达式的函数。如果在那个表达式后解析到一个“(”符号，则其必定是一个调用“call”节点，将会由parse_call()来处理（包含在下面代码中）。可以再次注意到delimited()如何被用来读取参数列表。

function maybe_call(expr) {
    expr = expr();
    return is_punc("(") ? parse_call(expr) : expr;
}
​
function parse_call(func) {
    return {
        type: "call",
        func: func,
        args: delimited("(", ")", ",", parse_expression)
    };
}

操作符优先级

maybe_binary(left, my_prec) 用来组合类似 1 + 2 * 3 的二元表达式。能正确解析它们的技巧就是要准确地定义操作符的优先级，如下：

var PRECEDENCE = {
    "=": 1,
    "||": 2,
    "&&": 3,
    "<": 7, ">": 7, "<=": 7, ">=": 7, "==": 7, "!=": 7,
    "+": 10, "-": 10,
    "*": 20, "/": 20, "%": 20,
};

上述定义意味着 * 要比 + 有更强的约束，所以对一个表达式，比如 1 + 2 * 3，必须被解析为 (1 + (2 * 3)) 而不是 ((1 + 2) * 3)，后者是按通常从左到右（left-to-right）顺序解析的结果。

这里的技巧就是读一个原子表达式（只有1）并将它（作为左参数）和当前的优先级（my_prec）一起传给maybe_binary()。maybe_binary将会解析紧跟着的内容。如果没有解析到运算符，或者运算符的优先级更低，则直接原样返回左参数。

如果解析到一个更高优先级的运算符，则会将左参数包裹到一个新的二元表达式"binary"节点中，并在新的优先级(*)上对右参数重复上面的技巧：

function maybe_binary(left, my_prec) {
    var tok = is_op();
    if (tok) {
        var his_prec = PRECEDENCE[tok.value];
        if (his_prec > my_prec) {
            input.next();
            var right = maybe_binary(parse_atom(), his_prec) // (*);
            var binary = {
                type     : tok.value == "=" ? "assign" : "binary",
                operator : tok.value,
                left     : left,
                right    : right
            };
            return maybe_binary(binary, my_prec);
        }
    }
    return left;
}

需要注意的是在返回二元表达式之前，为了能将表达式包裹到另一个紧跟着的具有更高优先级的表达式中，必须在旧的优先级（my_prec）上也调用maybe_binary。如果这些难以理解，请一遍遍反复阅读代码（也许可以在脑中尝试某些输入表达式的执行）直到搞明白了。

最终，由于my_prec初始化为0，任何运算符都会构建出一个二元表达式"binary"节点（或当运算符为=时构建一个赋值"assign"节点）。解析器中还有另外一些其它的函数，所以我将整体解析函数放到了下面。点击“显示代码”来显示所有的代码（大约150行）。

显示代码

var FALSE = { type: "bool", value: false };
function parse(input) {
    var PRECEDENCE = {
        "=": 1,
        "||": 2,
        "&&": 3,
        "<": 7, ">": 7, "<=": 7, ">=": 7, "==": 7, "!=": 7,
        "+": 10, "-": 10,
        "*": 20, "/": 20, "%": 20,
    };
    return parse_toplevel();
    function is_punc(ch) {
        var tok = input.peek();
        return tok && tok.type == "punc" && (!ch || tok.value == ch) && tok;
    }
    function is_kw(kw) {
        var tok = input.peek();
        return tok && tok.type == "kw" && (!kw || tok.value == kw) && tok;
    }
    function is_op(op) {
        var tok = input.peek();
        return tok && tok.type == "op" && (!op || tok.value == op) && tok;
    }
    function skip_punc(ch) {
        if (is_punc(ch)) input.next();
        else input.croak("Expecting punctuation: \"" + ch + "\"");
    }
    function skip_kw(kw) {
        if (is_kw(kw)) input.next();
        else input.croak("Expecting keyword: \"" + kw + "\"");
    }
    function skip_op(op) {
        if (is_op(op)) input.next();
        else input.croak("Expecting operator: \"" + op + "\"");
    }
    function unexpected() {
        input.croak("Unexpected token: " + JSON.stringify(input.peek()));
    }
    function maybe_binary(left, my_prec) {
        var tok = is_op();
        if (tok) {
            var his_prec = PRECEDENCE[tok.value];
            if (his_prec > my_prec) {
                input.next();
                return maybe_binary({
                    type     : tok.value == "=" ? "assign" : "binary",
                    operator : tok.value,
                    left     : left,
                    right    : maybe_binary(parse_atom(), his_prec)
                }, my_prec);
            }
        }
        return left;
    }
    function delimited(start, stop, separator, parser) {
        var a = [], first = true;
        skip_punc(start);
        while (!input.eof()) {
            if (is_punc(stop)) break;
            if (first) first = false; else skip_punc(separator);
            if (is_punc(stop)) break;
            a.push(parser());
        }
        skip_punc(stop);
        return a;
    }
    function parse_call(func) {
        return {
            type: "call",
            func: func,
            args: delimited("(", ")", ",", parse_expression),
        };
    }
    function parse_varname() {
        var name = input.next();
        if (name.type != "var") input.croak("Expecting variable name");
        return name.value;
    }
    function parse_if() {
        skip_kw("if");
        var cond = parse_expression();
        if (!is_punc("{")) skip_kw("then");
        var then = parse_expression();
        var ret = {
            type: "if",
            cond: cond,
            then: then,
        };
        if (is_kw("else")) {
            input.next();
            ret.else = parse_expression();
        }
        return ret;
    }
    function parse_lambda() {
        return {
            type: "lambda",
            vars: delimited("(", ")", ",", parse_varname),
            body: parse_expression()
        };
    }
    function parse_bool() {
        return {
            type  : "bool",
            value : input.next().value == "true"
        };
    }
    function maybe_call(expr) {
        expr = expr();
        return is_punc("(") ? parse_call(expr) : expr;
    }
    function parse_atom() {
        return maybe_call(function(){
            if (is_punc("(")) {
                input.next();
                var exp = parse_expression();
                skip_punc(")");
                return exp;
            }
            if (is_punc("{")) return parse_prog();
            if (is_kw("if")) return parse_if();
            if (is_kw("true") || is_kw("false")) return parse_bool();
            if (is_kw("lambda") || is_kw("λ")) {
                input.next();
                return parse_lambda();
            }
            var tok = input.next();
            if (tok.type == "var" || tok.type == "num" || tok.type == "str")
                return tok;
            unexpected();
        });
    }
    function parse_toplevel() {
        var prog = [];
        while (!input.eof()) {
            prog.push(parse_expression());
            if (!input.eof()) skip_punc(";");
        }
        return { type: "prog", prog: prog };
    }
    function parse_prog() {
        var prog = delimited("{", "}", ";", parse_expression);
        if (prog.length == 0) return FALSE;
        if (prog.length == 1) return prog[0];
        return { type: "prog", prog: prog };
    }
    function parse_expression() {
        return maybe_call(function(){
            return maybe_binary(parse_atom(), 0);
        });
    }
}

致谢

我是在学习Marijn Haverbeke的parse-js库（Common Lisp）时明白了如何去写一个有意义的解析器。 上面的解析器仿照他的代码，尽管是为了解析一个更简单的语言。