《代码之美》（九）－－自顶向下的运算符优先级

Douglas Crockford

Vaughan Pratt在1973年的第一届年度编程语言原理研讨会上宣讲了《自顶向下的运算符优先级》，他在这篇论文里描述了一项解析技术，该技术融合了递归下降分 析和Robert W Floyd的运算符优先级句法技术的最佳特性。

Pratt在论文里认为如今人们在构造编译器时， 都沉溺于使用BNF语法及其变种，以及相关的自动机理论，以至于自动机理论以外的研究方向没有得到发展。凭借他的解析技术，Pratt几乎毫不费力使用 LISP从语素（token）流搭建出了解析树。至于他的技术为什么被忽略，还有一种解释就是它对动态的函数编程语言最为有效，而应用到静态的过程语言会 比较困难。

虽然LISP是动态语言，但它却不支持句法：函数编程社区发现程序和数据间对应关系的价值远远超过了句法丰富的表达能力所带来的价值。因此，Pratt的技术给出的句法并没有被动态编程语言社区使用过。

JavaSript的出现改变了这种状况：它是一门动态函数语言，但从句法的角度看，它是C家族的一员。因此，JavaScript可作为探索Pratt技术的理想语言。本章就用JavaScript来实现一个解析JavaScript语言的解析器。

 

符号表

解析器里需要一个符号表：

var symbol_table = {};

这张表里用来存放original_symbol对象：

var original_symbol = {
    // nud是Null Denotation的缩写，之后会解释
    nud: function() {
        this.error("Undefined");
    }
    // led是Left Denotation的缩写，之后会解释
    led: function(left) {
        this.error("Missing operator.");
    }
};

接下来定义一个名为symbol的函数，它用来向symbol_table添加original_symbol（及其子类）的对象：

var symbol = function(id, bp) {
    var s = symbol_table[id];
    bp = bp || 0;
    if (s) {
        if (bp >= s.lbp) {
            s.lbp = bp;
        }
    } else {
        s = object(original_symbol);
        s.id = s.value = id;
        s.lbp = bp;
        symbol_table[id] = s;
    }
    return z;
};

symbol函数接受两个参数：符号的id，以及可选的默认值为0的参数bp。bp表示一个绑定权值，用于生成表达式，在后面我们可以看到它的用处。symbol函数会查找符号表，如果符号存在，那么在需要的时候改变该符号的左绑定权值，否则生成一个新的符号对象，放入符号表中。

下面定义一些流行的分割符和终结符：

symbol(":");
symbol(";");
symbol(",");
symbol(")");
symbol("]");
symbol("}");
symbol("else");

“(end)”表示再没有多余符号，“(name)”表示新名字的原型，比如变量名的原型：

symbol("(end)");
symbol("(name)");

“(literal)”表示所有的字符串和数字常量：

var itself = function() {
    return this;
};
symbol("(literal)").nud = itself;

“this”是个专用变量，在调用方法时，他指向调用该方法的对象和引用：

symbol("this").nud = function() {
    scope.reserve(this);
    this.arity = "this";
    return this;
};

上面的代码定义了一个original_symbol的子类，它的id为"this"，同时覆盖了它的nud方法。scope是作用域，arity表示符号的类型，这些都会在后面解释。

 

语素

通过（上阶段的）词法分析，文本已经被转换为一组简单的语素对象(tokens)。每个语素对象包含一个表示对象类型的成员type和表示对象值的成员 value。成员type是一段字符串（"name", "string", "number", "operator"），而成员value是一段符串或者一个数。

我们在语法分析时要做的事，就是把这些已有的语素流，转换成一个语法树。为此，我们需要遍历所有的语素对象。首先，我们定义一个全局变量token用来表示当前正在访问的语素：

var token;

接下来，我们定义一个名为advance的函数，用于得到下一个语素，同时根据它在程序中的作用，为它添加类型信息——元数（arity）。元数可以 是"name"（名字），"literal"（字面量），或者"operator"（运算符）。当我们更了解该语素的作用后，可以把它的元数改 为"binary”（二元操作）、"unary”（一元操作）或者“statement”（语句）。advance还可以接受一个参数id，表示期望的下 一个语素。下面是它的实现：

var advance = function(id) {
    var a, o, t, v;
    if (id && token.id !== id) {
        token.error("Expected '" + id + "'.");
    }
    if (token_nr >= tokens.length) {
        token = symbo_table["(end)"];
        return;
    }
    t = tokens[token_nr];
    token_nr += 1;
    v = t.value;
    a = t.type;
    if (a === "name") {
        o = scope.find(v);
    } else if (a === "operator") {
        o = symbol_table[v];
        if (!o) {
            t.error("Unknown operator.");
        }
    } else if (a === "string" || a === "number") {
        a = "literal";
        o = symbol_table["(literal)"];
    } else {
        t.error("Unexpected token.");
    }
    token = object(o);
    token.value = v;
    token.arity = a;
    return token;
};

token_nr是当前访问的语素下标。如果所有的语素都被访问后，函数返回"(end)"。可以看到，函数根据不同的情况为语素添加不同的元数信息。

 

优先级

不同的操作符有不同的优先级，比如乘法操作"*"就比加法操作"+"有更高的优先级。下列公式中，A和B是运算符：
d A e B f
那么运算对象e应该同A绑定：
(d A e) B f
还是同B绑定：
d A (e B f) ？
为了解决这类歧义，每个语素都包含一个nud方法，或led方法。nud（null denotation）不在乎靠左的语素，值对象（比如变量和字面量）和前置运算符用nud方法；led（left denotation）在乎靠左的语素，中置运算符和后置运算符用led方法。一个语素可以同时具备nud和led方法，比如“-"可以是前置运算符（负 号），也可以是中置运算符（减号）。

表达式

表达式函数expression是Pratt技术的核心。它的参数是一个右绑定权值：

var expression = function (rbp) {
    var left;
    var t = token;
    advance();
    left = t.nud();
    while (rbp < token.lbp) {
        t = token;
        advance();
        left = t.led(left);
    }
    return left;
}

这个函数会生成一个语法（子）树，返回值为这棵树的根。表达式的长度根据传入的右绑定权值决定。比如，当前的语素是一个加号，通过调用 expression函数来得到这个加号所绑定的表达式，传入的参数就是加号的权值（优先级）。很明显，加号能绑定的表达式长度肯定要比乘号长：比如语素 串“1+2*3+4”，第一个加号所绑定的表达式为"1+2*3"，如果它变为乘号，那它能绑定的表达式只能为"1*2"。

中置运算符

加号“+”是中置运算符，它包含一个led方法，这个方法可以生成一个以加号语素为根的二叉树，左支为加号左边的运算对象，而右支为加号右边的运算对象：

symbol("+", 60).led = function (left) {
    this.first = left;
    this.second = expression(60);
    this.arity = "binary";
    return this;
}

把这个led方法和前面的expression函数放在一起研究下。假设有语素流“1+2+3"，当前token为“1”，我们调用expession(0)来解析它。之所以用参数0，是因为“1”的左侧没有需要结合的东西。

expression函数首先调用“1”的nud方法，它会返回"1"本身，所以在循环前，left就是"1"。在循环开始时，token已经是第一个 “+”了。因为rbp是0，而“+"的lbp为60（symbol("+", 60)设置了这个lbp值），所以rbp < token.lbp，进入循环体，t变为"+"，advance读取下个元素“2”，t.led(left)进入"+"号的led方法，传入的参数是 “1”。

在led方法里，"+"被设置为了根，它的左孩子是“1”，右孩子通过expression来得到。于是我们又进入expression函数，当前的token为"2"，传入expression的参数为60。

在被递归调用的expression里，循环开始前，left被设置为“2”的nud，即"2"本身，当前的token为"+"，因为rbp和"+"的lbp都为60，所以不进入循环体，而返回left，即"2"。

这样，我们得到了表达式："1+2"，其中"+"为根，"1"为左支，“2”为右支。

注意：现在回到了最外层的expression里的循环体了，这里的参数lbp仍然是0，所以继续进入下一次循环，这时当前token为第二个“＋” 号，left变为“1+2”，调用第二个“+”的led方法，从而生成了以第二个“＋”为根，"1+2"为左支，“3”为右支的树。而这就是整个表达式 “1＋2＋3”的语法树。

乘号"*"同样也是个中置运算符，它的优先级比加号高，所以它的led方法为：

symbol("*", 70).led = function (left) {
    this.first = left;
    this.second = expression(70);
    this.arity = "binary";
    return this;
}

基于加号与乘号的led实现，考虑语素流“1+2*3”。首先前两步与分析“1+2+3"是一样的："1"成为左支，”+"成为根。不同的是在得到"+"的右支时，expression(60)的调用：
此时当前token为“2”，在进入循环前，left被设置为"2"，而当前token被设为“*”，所以rpb < token.lbp，即加法的权值比乘法低，所以继续进入循环，生成一棵由"*"为根，"2"为左支，"3"为右支的树，而“*”本身，成为了"+"的右 孩子。

可以看到，加号和乘号的led方法很相似。为此，我们可以为大多数的中置运算符提供一个普遍的infix函数：

var infix = function (id, bp, led) {
    var s = symbol(id, bp);
    s.led = led || function (left) {
        this.first = left;
        this.second = expression(bp);
        this.arity = "binary";
        return this;
    }
    return s;
}

对于不同处理方式的中置运算符，可以通过传递led函数来定制特殊的处理方法。

有了这个infix函数后，我们就可以很简单地定义一些中置运算符了：

infix("+", 60);
infix("-", 60);
infix("*", 70);
infix("/", 70);

infix("===", 50);
infix("!==", 50);
infix("<", 50);
infix("<=", 50);
infix(">", 50);
infix(">=", 50);

三元运算符"? :"与普通的中置运算符不同，所以另外定义它的led方法：

infix("?", 20, function(left) {
    this.first = left;
    this.second = expression(0);
    advance(":");
    this.third = expression(0);
    this.arity = "ternary";
    return this;
});

它会生成一个三叉树。

点运算符“.”用于选择成员。它右边的语素必须是名字：

infix(".", 90, function(left) {
    this.first = left;
    if (token.arity !== "name") {
        token.error("Expected a property name.");
    }
    token.arity = "literal";
    token.second = token;
    this.arity = "binary";
    advance();
    return this;
});

运算符“[”用于从对象或数组中动态地选出成员。它右边的表达式必须用“]”收尾：

infix("[", 90, function (left) {
    this.first = left;
    this.second = expression(0);
    this.arity = "binary";
    advance("]");
    return this;
});

上述中置运算符是左结合的。我们也可以通过减小右绑定值来创建右结合的运算符，比如短路逻辑运算符：

var infixr = function (id, bp, led) {
    var s = symbol(id, bp);
    s.led = led || function (left) {
        this.first = left;
        this.second = expression(bp - 1);
        this.arity = "binary";
        return this;
    }
    return s;
}

右结合的运算符有：

infixr("&&", 40);
infixr("||", 40);

“左结合”与“右结合”的区别在于同样种类的运算符之间，是左边的优先级高，还是右边的高。比如，“1+2+3"最右生成的语法树的根是第二个加号，左支 为“1＋2”，右支为“3”。而“1&&2&&3”，因为第一个“&&”（在与利用第二个 “&&”生成表达式时）的优先级是40-1=39，而第二个“&&”的优先级为40，所以生成的语法树的根为第一个“& amp;&”，左支为“1”，右支为“2&&3”。

这里有个很精巧的地方：如果有第三个“&&”，第二个 “&&”与第三个结合时，第二个“&&”的bp值为39，而第三个“&&”为40，所以这种减少bp值 的方式可以处理任意多的“&&”。（博主：“&&”应该比“||”的优先级高，但这里给出的bp值都为40，应该有误 吧？）

前置运算符

前置运算符可以与后面的语素合并，作为一个中置运算符的一支。在前面expression函数里，一个语素的nud方法会最先调用，之后（根据需要）调用后续语素的led方法。前置运算符的一般定义为：

var prefix = function (id, nud) {
    var s = symbol(id);
    s.nud = nud || function () {
        scope.reserve(this);
        this.first = expression(80);
        this.arity = "unary";
        return this;
    }
    return s;
}
preifx("-");
prefix("+");
prefix("typeof");

prefix不需要左绑定值，而且它只有一个右分支。scope.reserve用来（在需要时）把这个前置运算符作为保留字，scope在后面介绍。

左括号“(”的nud函数会调用advance“)”，而且左右括号都不会成为解析树的一部分。它的nud函数的定义为:

prefix("(", function() {
    var e = expression(0);
    advance(")");
    return e;
});

非常简单明了，就是把“(”右边的表达式全部包括进来，再匹配“)”。

赋值运算符

赋值运算符也是一个右结合的运算符，所以它其实成与infixr函数类似，不过多了一些额外的操作：

var assignment = function(id) {
    return infixr(id, 10, function (left) {
        if (left.id !== "." && left.id !== "[" && left.arity !== "name") {
            left.error("Bad lvalue");
        }
        this.first = left;
        this.second = expression(9);
        this.assignment = true;
        this.arity = "binary";
        return this;
    });
};
assignment("=");
assignment("+=");
assignment("-=");

赋值运算符在一般的infixr函数的基础上，首先增加了对合法左值的验证，然后增加了“assignment”的标志。

常数

常数的nud方法主要是更新符号表，同时返回语素自身：

var constant = function(s, v) {
    var x = symbol(s);
    x.nud = function () {
        scope.reserve(this);
        this.value = symbol_table[this.id].value;
        this.arity = "literal";
        return this;
    };
    x.value = v;
    return x;
};
constant("true", true);
constant("false", false);
constant("null", null);
constant("pi", 3.141592653589793);

Scope

当我们在语言里遇到新词时，比如变量，我们会定义这个新词，并把它放到符号表里。复杂的语言里，我们需要作用域来控制变量的生命周期和可见度。

首先定义一个全局变量表示当前的作用域：

var scope;

接下来要定义作用域类original_scope。它主要有四个方法：
define：定义一个变量；
find：找到一个名字的定义，必要时找其父作用域；
pop：关闭作用域；
reserve：把一个名字作为当前作用域的保留字，比如关键字。

下面是original_scope的定义：

var original_scope = {
    define: function (n) {
        var t = this.def[n.value];
        if (typeof t == "object") {
            n.error(t.reserved ? "Already reserved" : "Already defined.");
        }
        this.def[n.value] = n;
        n.reserved = false;
        n.nud = itself;
        n.led = null;
        n.std = null;
        n.lbp = 0;
        n.scope = scope;
        return n;
    },

    find: function (n) {
        var e = this;
        while (true) {
            var o = e.def[n];
            if (o) {
                return o;
            }
            e = e.parent;
            if (!e) {
                return symbol_table[symbol_table.hasOwnProperty[n] ? n : "(name)"];
            }
        }
    },

    pop: function () {
        scope = this.parent;
    },

    reserve: function (n) {
        if (n.arity !== "name" || n.reserved) {
            return;
        }
        var t = this.def[n.value];
        if (t) {
            if (t.reserved) {
                return;
            }
            if (t.arity == "name") {
                n.error("Already defined.");
            }
        }
        this.def[n.value] = n;
        n.reserved = true;
    }
};

当进入一个新作用域时，便可以调用一个函数:

var new_scope = function () {
    var s = scope;
    scope = object(original_scope);
    scope.def = {};
    scope.parent = s;
    return scope;
}

在前面某些语素通过调用scope.reserve来说明自身是一个保留字，比如中置运算符“”、前置运算符“”和一些常数（"true", "false"和"null"）。这样，在程序里就不能有与这样保留字重名的变量名了。

语句

Pratt最初的推导结果适用于所有的函数语言。函数语言里一切都是表达式。现在大多数主流语言支持语句，所以我们也在Pratt方法中添加对语句的支持。除了nud和led，我们再在语素中加入一个std方法（statement denotation）。

函数statement一次解析一条语句，除非语素有自己的std方法，否则我们只接受赋值或函数调用的表达式语句：

var statement = function () {
    var n = token, v;
    if (n.std) {
        advance();
        scope.reserve(n);
        return n.std();
    }
    v = expression(0);
    if (!v.assignment && v.id !== "(") {
        v.error("Bad expression statement.");
    }
    advance(";");
    return v;
}

函数statements逐条解释语句，直到看见“(end)”或者“}”。它可以返回一条语句、一组语句或者null（没有语句）：

var statements = function() {
    var a = [], s;
    while (true) {
        if (token.id === "}" || token.id === "(end)") {
            break;
        }
        s = statement();
        if (s) {
            a.push(s);
        }
    }
    return s.length === 0 ? null : a.length === 1? a[0] : a;
};

函数stmt用来将语句加入符号表：

var stmt = function(s, f) {
    var x = symbol(s);
    x.std = f;
    return x;
};

下面定义程序块语句，它把一串语句组织起来，并赋予他们新的作用域：

stmt("{", function() {
    new_scope();
    var a = statements();
    advance("}");
    scope.pop();
    return a;
});

函数block解析程序块：

var block = function() {
    var t = token;
    advance("{");
    return t.std();
}

语句var可以定义一个或多个变量，每个变量名后可带=和一条表达式：

stmt("var", function() {
    var a = [], n, t;
    while (true) {
        n = token;
        if (n.arity !== "name") {
            n.error("Expected a new variable name.");
        }
        scope.define(n);
        advance();
        if (token.id === "=") {
            t = token;
            advance("=");
            t.first = n;
            t.second = expression(0);
            t.arity = "binary";
            a.push(t);
        }
        if (token.id !== ",") {
            break;
        }
        advance(",");
    }
    advance(";");
    return a.length === 0 ? null : a.length === 1 ? a[0] : a;
});

语句while定义循环。它包含一个括号内的表达式和一个程序块：

stmt("while", function() {
    advance("(");
    this.first = expression(0);
    advance(")");
    this.second = block();
    this.arity = "statement";
    return this;
});

语句if用于执行条件执行。如果在if的程序块后看到else，我们继续解析下一个程序块，或下一个if语句：

stmt("if", function() {
    advance("(");
    this.first = expression(0);
    advance(")");
    this.second = block();
    if (token.id === "else") {
        scope.reserve(token);
        advance("else");
        this.third = token.id === "if" ? statement() : block();
    }
    this.arity = "statement";
    return this;
});

语句break用来跳出循环。我们确保下一个符号是“}”（因为所有的程序块都用“{”和“}”包括，break必须是一个程序块最后一条语句）：

stmt("break, function() {
    advance(";");
    if (token.id !== "}") {
        token.error("Unreachable statement.");
    }
    this.arity = "statement

语句return用于从函数返回。它可以返回一则表达式：

stmt("return", function () {
    if (token.id !== ";") {
        this.first = expression(0);
    }
    advance(";");
    if (token.id !== "}") {
        token.error("Unreachable statement.");
    }
    this.arity = "statement";
    return this;
});

函数
函数是可以执行的对象值。它可以有名字、一组参数和函数体：

prefix("function", function () {
    var a = [];
    scope = new_scope();
    if (token.arity === "name") {
        scope.define(token);
        this.name = token.value;
        advance();
    }
    advance("(");
    if (token.id !== ")") {
        while (true) {
            if (token.arity !== "name") {
                token.error("Expected a parameter name.");
            }
            scope.define(token);
            a.push(token);
            advance();
            if (token.id !== ",") {
                break;
            }
            advance(",");
        }
    }
    this.first = a;
    advance(")");
    advance("{");
    this.second = statements();
    advance("}");
    this.arity = "function";
    scope.pop();
    return this;
});

函数通过“(”运算符调用。它可以接受零个或多个参数。我们要判断它的左运算对象是不是可以作为可调用的函数：

infix ("(", 90, function(left) {
    var a = [];
    this.first = left;
    this.second = a;
    this.arity = "binary";
    if ((left.arity !== "unary" || left.id !== "function")
        && left.arity !== "name"
        && (left.arity !== "binary" || (left.id !== "." && left.id !== "(" && left.id !== "["))) {
        left.error("Expected a variable name.");
    }
    if (token.id !== ")") {
        while (true) {
            a.push(expression(0));
            if (token.id !== ",") {
                break;
            }
            advance(",");
        }
    }
    advance(")");
    return this;
});

数组和对象字面量
数组字面量是包含零个或多个表达式的一组方括号。表达式用逗号分隔。每个表达式求解后的值收集起来，得到一个新的数组：

prefix("[", function () {
    var a = [];
    if (token.id !== "]") {
        while (true) {
            a.push(expression(0));
            if (token.id !== ",") {
                break;
            }
            advance(",");
        }
    }
    advance("]");
    this.first = a;
    this.arity = "unary";
    return this;
}

对象字面量是包含零个或多个键值对的一组花括号。键值是用冒号分隔的键／表达式对：键要么是字面量，要么是被当作字面量的名字：

prefix("{", function() {
    var a = [];
    if (token.id !== "}") {
        while (true) {
            var n = token;
            if (n.arity !== "name" && n.arity !== "literal") {
                token.error("Bad key.");
            }
            advance();
            advance(":");
            var v = expression(0);
            v.key = n.value;
            a.push(v);
            if (token.id !== ",") {
                break;
            }
            advance(",");
        }
    }
    advance("}");
    this.first = a;
    this.arity = "unary";
    return this;
});

总结

本章展示的简单解析器容易扩展。我们可以加上其它语句比如for、swith和try等。我们还可以加入更多的运算符。这样的解析器使得我们的语言具备扩展能力，使得程序员加入新运算符和新语句就跟加入新的变量一样容易。JSLink也用到了这里的解析技术：。

：美国计算机程序员与企业家。现任Yahoo!高级Javascript架构师，同时是关于Javascript、JSON以及相关网络技术的作家与演讲者。代表作有《Javascript: The Good Parts》。