如何用JavaScript实现一门编程语言 - Token流

[llwanghong]

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

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

标记流（Token Stream）

分词器Tokenizer（也叫做词法分析器Lexer）运行在字符流基础上，同样也返回一个具有相同接口的流对象，但是它的peek()/next()函数返回值为一个个标记token。token是有两个属性的对象：type 和 value。下面是我们所支持的token一些示例：

{ type: "punc", value: "(" }           // punctuation: parens, comma, semicolon etc.
{ type: "num", value: 5 }              // numbers
{ type: "str", value: "Hello World!" } // strings
{ type: "kw", value: "lambda" }        // keywords
{ type: "var", value: "a" }            // identifiers
{ type: "op", value: "!=" }            // operators

空白符和注释会被跳过，不会返回token。

为了实现分词器，我们需要更进一步认识λanguage语言的语法。整体思路就是根据当前的字符（input.peek()函数的返回）来决定读取相应类型的token：

• 首先，跳过所有的空格。
• 如果输入流已到结尾，即input.eof()为真，返回空值null。
• 如果遇到井号“#”，则跳过注释（注释所在行结束后，重新开始上面的流程）。
• 如果是引号，则读取字符串。
• 如果是数字字符，则连续读取得到一个数字。
• 如果是一个字母，则读取一个标识符（identifier）或者关键字（keyword）。
• 如果是一种标点符号字符，则返回标点符号token。
• 如果是一种操作符，则返回操作符token。
• 如果上面的情况都不符合，则抛出一个异常input.croak()。

下面的read_next函数作为分词器的核心，实现了上面各描述情况：

function read_next() {
    read_while(is_whitespace);
    if (input.eof()) return null;
    var ch = input.peek();
    if (ch == "#") {
        skip_comment();
        return read_next();
    }
    if (ch == '"') return read_string();
    if (is_digit(ch)) return read_number();
    if (is_id_start(ch)) return read_ident();
    if (is_punc(ch)) return {
        type  : "punc",
        value : input.next()
    };
    if (is_op_char(ch)) return {
        type  : "op",
        value : read_while(is_op_char)
    };
    input.croak("Can't handle character: " + ch);
}

这是一个“调度器”函数，next()函数会调用它以获取下一个token。可以注意到它使用到很多针对具体token类型的工具函数，如read_string()，read_number()等。没有理由因为它们而让调度器函数变得复杂，尽管没有其他地方会调用它们。

另外需要注意我们没有一次性把输入流全部消费掉。每次当解析器需要下一个token时，才会读取一个token。当解析发生错误时我们甚至都不会到达流的末尾。

read_ident()函数将会尽可能长的读取可以组成标识符的字符（is_id）。标识符必须以字母，或λ或下划线_开头，剩余部分可以由这三种字符，或数字，或?!-<>=等字符组成。所以foo-bar会被识别为一个标识符（一个vartoken）而不是三个token。这条规则的原因是希望可以使用is-pair或string>=名称来定义函数（抱歉，这是我内心的Lisper在捣乱）。

read_ident()函数也会将标识符和已知的关键字列表进行对比，如果标识符是一个关键字则会返回一个kwtoken，否则返回一个vartoken。

代码更有助于理解上面的描述，下面是λanguage语言分词器的完整实现。附带了一些其他的备注。

function TokenStream(input) {
    var current = null;
    var keywords = " if then else lambda λ true false ";
    return {
        next  : next,
        peek  : peek,
        eof   : eof,
        croak : input.croak
    };
    function is_keyword(x) {
        return keywords.indexOf(" " + x + " ") >= 0;
    }
    function is_digit(ch) {
        return /[0-9]/i.test(ch);
    }
    function is_id_start(ch) {
        return /[a-zλ_]/i.test(ch);
    }
    function is_id(ch) {
        return is_id_start(ch) || "?!-<>=0123456789".indexOf(ch) >= 0;
    }
    function is_op_char(ch) {
        return "+-*/%=&|<>!".indexOf(ch) >= 0;
    }
    function is_punc(ch) {
        return ",;(){}[]".indexOf(ch) >= 0;
    }
    function is_whitespace(ch) {
        return " \t\n".indexOf(ch) >= 0;
    }
    function read_while(predicate) {
        var str = "";
        while (!input.eof() && predicate(input.peek()))
            str += input.next();
        return str;
    }
    function read_number() {
        var has_dot = false;
        var number = read_while(function(ch){
            if (ch == ".") {
                if (has_dot) return false;
                has_dot = true;
                return true;
            }
            return is_digit(ch);
        });
        return { type: "num", value: parseFloat(number) };
    }
    function read_ident() {
        var id = read_while(is_id);
        return {
            type  : is_keyword(id) ? "kw" : "var",
            value : id
        };
    }
    function read_escaped(end) {
        var escaped = false, str = "";
        input.next();
        while (!input.eof()) {
            var ch = input.next();
            if (escaped) {
                str += ch;
                escaped = false;
            } else if (ch == "\\") {
                escaped = true;
            } else if (ch == end) {
                break;
            } else {
                str += ch;
            }
        }
        return str;
    }
    function read_string() {
        return { type: "str", value: read_escaped('"') };
    }
    function skip_comment() {
        read_while(function(ch){ return ch != "\n" });
        input.next();
    }
    function read_next() {
        read_while(is_whitespace);
        if (input.eof()) return null;
        var ch = input.peek();
        if (ch == "#") {
            skip_comment();
            return read_next();
        }
        if (ch == '"') return read_string();
        if (is_digit(ch)) return read_number();
        if (is_id_start(ch)) return read_ident();
        if (is_punc(ch)) return {
            type  : "punc",
            value : input.next()
        };
        if (is_op_char(ch)) return {
            type  : "op",
            value : read_while(is_op_char)
        };
        input.croak("Can't handle character: " + ch);
    }
    function peek() {
        return current || (current = read_next());
    }
    function next() {
        var tok = current;
        current = null;
        return tok || read_next();
    }
    function eof() {
        return peek() == null;
    }
}

• next()函数并不总会调用read_next()函数，因为之前可能已经读取过（此时read_next()已经调用过，流已经被消费）。所以我们需要一个current变量来保存当前的token。
• 我们仅支持常用符号的十进制数字（不支持1E5写法，不支持十六进制，不支持八进制）。如果需要更多的支持，只需要修改read_number()函数，比较容易实现。
• 和JavaScript不同，字符串中不能出现的未转译字符只有引号本身以及反斜杠。你需要用反斜杠对它们进行转译。否则字符串中可能会包含硬换行符、制表符等。我们不会解析通常的转译符比如\n，\t。同样如果想支持也不难，改动会很小（read_string函数）。

我们现在有了足够强大的工具去轻松地编写解析器，但首先推荐你阅读一下AST的描述。