Top Down Operator Precedence - 自顶向下算符优先分析法

by 司徒正美

at 2012-09-08 15:42:00

original http://www.cnblogs.com/rubylouvre/archive/2012/09/08/2657682.html

这是一篇翻译，原文来自 Top Down Operator Precedence。由于毕设搞的就是相关技术，所以近期花了块两天时间把文章翻译了，实在够累，希望大侠看见，不吝赐教！

简介

1973年，波士顿 Vaughan Pratt 在编程语言原则座谈会(Principles of Programming Languages Symposium) 第一期年刊上发表自顶向下算符优先(Top Down Operator Precedence)。在论文中 Pratt 描述了一种结合递归向下(Recursive Descent)方法以及 Floyd 算符优先(Operator Precedence)方法优良特性的解析技术。它非常易用。同时，它看起来很像递归向下，但是却可用更少代码实现以及更高效的性能。他声称这项技术非常易懂，便于实现，方便使用，性能特出，同时也很灵活。它是动态的，支持真正语言级别的扩展。

但是很奇怪，对于编译器编译来说如此优异的方法如今却完全被忽略了。为什么会这样呢？Pratt 在论文中指出，由于更早出现的 BNF 语法以及其各种各样的变种版本，伴随着与之相关的自动机和定理的出现，限制了自动机这种不可见领域的多样发展。

另外一种解释说，他的这种技术只是在应用于动态的，函数式编程语言上才会有很高的效率。将它应用于静态程序语言上则略先困难。在论文中，Pratt 用 LISP 语言基本毫不费力地就从词法单元流中解析出来了语法树。但是这种解析技术却没有在 LISP 社区中体现出太大的价值。自从 LISP 诞生之日起，就有出现很多让它拥有算法似的语法(ALGOL-like syntax)，其中包括 Pratts 的 CGOL，LISP 2，MLISP，Dylan，Interlisp 的 Clisp 以及 McCarthy 的原始 M 表达式(original M-expressions)。但是最终都没有被接纳。LISP 社区发现协调程序与数据比富裕表达的语法更有价值。但是主流编程社区依然热衷于自己的语法，所以 LISP 从来没被主流接纳过。Pratt 的技术需要一门动态语言，但是动态语言社区历来都没使用过方便 Pratt 的技术解析的那种语法。

JavaScript

随着 JavaScript 的诞生这种情况发生了改变。JavaScript 是一门动态的函数式语言，但是从语法上看它明显是 C 语言风格家族的一员。它是一门动态语言且拥有社区都喜欢的语法。

JavaScript 也拥有面向对象特性。Pratt 1973年的论文预测面向对象将会是一种趋势，但是却缺乏一套富于表达的描述方法。JavaScript 是一门非常适合使用 Pratt 技术的语言。接下来我会用 JavaScript 快速实现一个简单的解析器。

在这么短小的一个章节里，我们没有足够的时间来实现整个 JavaScript，同时我们基本上也不会想去实现，因为语言里面的有一部分是糟粕。但是语言里面依然有一些考虑周全的精华元素。我们将会编写一个只能解析简化版 JavaScript(Simplified JavaScript) 的解析器。同时我们也会使用简化版的 JavaScript 来编写这个解析器。简化版的 JavaScript 只包含精华的部分，包括：

函数是一级对象。在简化版 JavaScript 中，函数是拥有词法作用域的 lambda 表达式。
原型继承的动态对象。对象是类无关的。我们可以使用普通的赋值方法像任何一个对象中添加一个成员。一个对象可以从另外一个对象中继承其成员。
拥有对象直接量和数组直接量。对于创建新的对象和数组，这是一种绝佳的描述方法。JavaScript 直接量是 JSON 数据接口格式的灵感来源。

我们将充分利用 JavaScript 原型继承的先天特性让词法单元继承自符号对象(symbols)。我们的实现依赖于 Object.create 方法（这个方法是创建一个新对象，并从一个已存在的对象中继承成员）以及一个词法单元生成器(tokenizer)（这个方法是从一个字符串里面生成一个包含简单词法单元对象的数组）。我们在这个词法单元的数组中逐步前进，生成我们的解析树。

符号表

每一个词法单元，例如操作符和标识符，都继承自一个符号对象。我们把所有的符号都保存在 symbol_table 对象（这个符号表是用来判断我们语言中词法单元的类型）中。

var symbol_table = {};

这个 original_symbol 对象是所有其他符号的原型。它其中的方法同时是被用来重写(overridden)的。（我们将会在接下来的优先级一节来解释 nud 和 led 的作用以及约束力的含义）

var original_symbol = {
nud: function() {
this.error('Undefined.');
},
led: function(left) {
this.error('Missing operator.');
}
};

让我们来定义一个生成符号的函数。它包含一个符号 id 和一个可选的约束力值，默认为0。函数返回一个对应 id 的符号对象。如果这个符号已经存在于 symbol_table 中，则函数就直接返回那个符号对象。否则，就创建一个继承于 original_symbol 的符号对象，存储在符号表中，并返回这个对象。一个符号对象初始的时候包含一个 id，一个符号值，一个左约束力，以及其他从 original_symbol 中继承的元素。

下列是常见的分隔符号和结束符号。

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

(end) 符号表示词法单元流的结束。(name) 符号是新命名符号的原型，例如变量名。包含在 id 两边的括号主要是用来防止与用户定义的词法单元冲突。

symbol('(end)');
symbol('(name)');

词法单元

我们假设源代码已经被转换成一个包含简单词法单元对象（tokens）的数组，每一个对象有一个类型(type)成员（包含名称(name)，字符串(string)，数字(number)或者操作符(operator)）以及一个值(value)成员（是字符串或者数字）。

token 变量总是指向当前的词法单元。

var token;

advance 方法从数组中的下一个简单词法单元创建一个新的词法单元对象，并且赋值给 token 变量。它拥有一个可选参数 id 用来检查是否和之前一个词法单元匹配。新的词法单元对象的原型是当前作用域中的 (name) 词法单元或者是符号表中的一个符号。新的词法单元的 arity(运算元) 是名称(name)，直接量(literal)或者操作符(operator)。arity 随后也可能根据我们了解更多该词法单元在程序中的角色而变化成二元运算(binary)，一元运算(unary)或者语句(statement)。

作用域

大部分语言都为定义新符号准备了一些描述方法（例如变量名）。在非常简单的语言中，当我们遇到一个新的单词时，我们给它一个定义然后放到符号表中。在一些更加复杂语言中，我们可以使用作用域，方便程序员控制这个变量的生存周期和可见性。

作用域就是程序中变量被定义和可访问的一块区域。当前作用域可以被嵌套进其他作用域中。定义在内层作用域的变量对于外层作用域是不可见的。

我们将当前作用域对象保存在 scope 变量中。

var scope;

original_scope 是所有作用域对象的原型。它包含一个 define 方法用于在作用域中定义新的变量。define 方法将一个名称词法单元转成一个变量词法单元。如果这个变量已经在作用域中定义过或者这个名字被用作保留字，那么将会报错。

find 方法用于查找一个名称的定义。这个方法会从当前作用域开始查找，如果有必要的话，会顺着该作用域的父作用域链查找直到最后到达符号表。如果没有找到该名称的定义，则返回 symbol_table['(name)']。

find 方法还会测试查找到的值，判断其不是 undefined （可能会导致未声明的命名），也不是 function （可能与被继承的方法导致冲突）。

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

pop 方法用于结束一个作用域，回到其父作用域中。

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

reserve 方法用于声明一个名称已经在当前作用域中被保留为关键字。

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;
}
};

我们需要为保留字准备一个策略。在某些语言中，被用于程序结构的词（例如 if）被当作保留字，不能用作变量的名称。由于我们解析器的灵活性，允许我们有一个更有效的策略。例如，我们可以说，在任何一个函数中，所有名称要么用作结构的单词，要么当作变量，但是不可能同时成为两者。那么我们只需当一个名称被用作保留词的时候，才将它保留在局部。这样的话，对于语言的设计者会更好，因为当要为语言添加新的结构单词时，不会破坏现有的程序，同样对于程序员也是好事，他们对于名称的使用不再受限于无关的约束。

每当我们想要为一个函数或者一个代码块建立一个新的作用域，我们调用 new_scope 函数，这将新建一个对象实例，其原型指向 original_scope 对象。

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

优先级

词法单元对象上包含一些可以做优先级判断，匹配其他词法单元已经创建语法树（在未来更大的项目中，可以包含类型判断，代码优化及生成）的方法。优先级判断最基本的问题是：在两个操作符直接给定几个操作数，操作数是应该从左到右运算还是从右到左？

d A e B f

如果 A 和 B 是运算符的话，操作数 e 是应该绑定在 A 还是 B 上？换句话说，也就是这个意思：

(d A e) B f or d A (e B f) ?

最终，这个复杂的解析过程给出了二义性的解决办法。我们在这儿开发用到的解决技术是这样的，每一个词法单元对象都有一个约束力(binding powers)（或者也可以说是优先级）作为成员，以及两个叫做 nud（空判定符）以及 lef（做判定符）的简单方法。nud 不管词法单元的左侧，而 led 却关注。nud 方法常用于值（例如变量和直接量）以及前缀操作符。led 方法常用于中缀和后缀运算符。一个词法单元也可以同时拥有 nud 和 led 方法。例如，- 及可以当作前缀运算符（负号），也可以当作中缀运算符（减号），所以它既拥有 nud 方法也拥有 led 方法。

在我们的论文中，我们使用这样的优先级：

0 最低优先级运算符，例如 ;
10 赋值运算符，例如 =
20 ?
30 || &&
40 关系运算符，例如 ===
50 + -
60 * /
70 一元运算符，例如 !
80 . [ (

表达式

Pratt 技术的核心就是 expression 函数。它需要一个右约束力（right binding power）参数，用来控制它对右侧词法单元有多大的约束力。

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 调用 token 的 nud 方法。nud 方法用于处理直接量，变量和前缀运算符。只要右约束力小于下一个词法单元的左约束力，那么就对接下来的词法单元调用 led 方法。led 方法用于处理中缀和后缀运算符。这一过程是递归的，因为 nud 和 led 方法都会调用 expression。

前缀运算符

+ 是一个前缀运算符，所以他有一个 led 方法用于将 + 左侧和右侧的词法单元对象转换为树的两支（first 和 second）。左侧的操作数传入 led 中运算，在运算中通过调用 expression 函数来获得右侧操作数。

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

符号 与 + 很类似，除了 id 和约束力不同之外。它拥有更大的约束力，由于它优先级更高。

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

并不是所有的中缀运算符都与这相似，但是大部分都会是这样的，所以为了让我们的工作更简单，我们定义了一个 infix 函数，用来帮助我们创建中缀运算符的符号对象。infix 函数需要 id，约束力，以及一个可选的 led 函数作为参数。如果没有提供 led 函数，那么 infix 函数提供一个大部分情况下都有用的 led 默认函数。

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

这就运行我们使用一种更具表达性的风格来指定中缀运算符：

infix('+', 50);
infix('-', 50);
infix('*', 60);
infix('/', 60);

=== 是 JavaScript 中的精确等于的运算符。

infix('===', 40);
infix('!==', 40);
infix('<', 40);
infix('<=', 40);
infix('>', 40);
infix('>=', 40);

三元运算符需要三个表达式，用 ? 和 : 分隔。这不是一个普通的前缀运算符，所以我们需要提供 led 函数。

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

. 运算符用于选择一个对象的成员。右侧的词法单元必须是一个名称且会被当作直接量使用。

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

[ 运算符用于动态地从一个对象或数组中选择成员。右侧的表达式必须有 ] 结尾。

infix('[', 80, 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;
};

如果 && 运算符的第一个操作数为假，那么就返回第一个操作数。否则返回第二个。如果 || 运算符的第一个操作数为真，那么就返回第一个操作数，否则返回第二个。（这里“假”的含义包括数字 0，空字符串 ''以及 false 值和 null 值。所有其他值（包括所有的对象）都是“真”。）

infixr('&&', 30);
infixr('||', 30);

前缀运算符

我们用于右结合中缀运算符的代码，可以适配到前缀运算符。前缀运算符是右结合的。由于前缀运算符不需要项做绑定，所以没有左约束力。前缀运算符同时也可用作保留关键字。

var prefix = function(id, nud) {
var s = symbol(id);
s.nud = nud || function() {
scope.reserve(this);
this.first = expression(70);
this.arity = 'unary';
return this;
};
return s;
};

prefix('-')；
prefix('!');
prefix('typeof');

( 的 nud 函数需要调用 advance(')') 去匹配对应的 ) 词法单元。由于 nud 函数返回内部表达式，所以( 词法单元不会成为语法树的一部分。

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

赋值运算符

我们可以用 infixr 来定义赋值运算符，但是我们还需要对 assignment 函数做一些特殊定制，来让它多做两件事：测试左侧操作数，确保是正确的左值(lvalue)，添加一个 assignment 成员，之后便可以快速地判断出赋值语句。

需要注意的是，我们这里的实现利用了一些列的继承模式，assignment 返回调用 infixr 的结果，而 infixr 则返回调用 symbol 的结果。

常量

constant 函数用于构建语言内部的常量。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);

(literal) 是所有字符串直接量和数字直接量的原型。直接量词法单元的 nud 方法返回词法单元自身。

symbol('(literal)').nud = itself;

语句

Pratt 原始的陈述体系只针对那些所有东西都是表达式的函数式语言有效。大部分主流语言不像那些层层嵌套的表达式一样，而是拥有语句的概念。只要为词法单元再添加一个 std（语句描述符）方法，就可以很轻松地处理语句。std 很像 nud，除了它只在语句开头调用外。

statement 方法解析一个语句。如果当前词法单元有 std 方法，那么这个词法单元就会被保留做关键词，然后调用 std 方法。否则，我们则假设一个以分号结尾的表达式语句。为了代码更好的可读性，我们只允许赋值或者调用的表达式语句。

statements 函数解析所有语句直到遇到 (end) 或者 } 这些表示块结束的标识符。这个函数的返回值是一个语句，或者包含很多语句的一个数组，或者是 null 用来表示没有语句出现。

stmt 函数用于将语句符号添加到符号表中。需要两个参数，语句的 id 和 std 函数。

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

语句块是用花括号括起来的一些列语句，同时也要给它们一个新的作用域。（JavaScript 没有块级作用域，简化版的 JavaScript 修正了这一点。）

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 语句允许有条件地执行。如果我们看见 else 符号后面还有一个语句块，那么我们就接着解析下面的语句块或者是 if 语句。

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

break 语句用于跳出循环。

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

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 = [];
new_scope();
if (token.arity === 'name') {
scope.define(token);
this.name = token.value;
advance();
}
advance('(');
if (tokend.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('(', function(left) {
var a = [];
if (left.id === '.' || left.id === '[') {
this.arity = 'ternary';
this.first = left.first;
this.second = left.sconed;
this.third = a;
} else {
this.arity = 'binary';
this.first = left;
this.second = a;
if ((left.arity !== 'unary' || left.id !== 'function') &&
left.arity !== 'name' && left.id !== '(' &&
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;
});

this 符号是一个特殊的变量。当函数是以方法的形式被调用，那它就指向那个对象。

symbol('this').nud = function() {
scope.reserve(this);
this.arity = 'this';
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;
});

未完成的以及一些想法

语法树可以被代码生成器解析，或者直接交由翻译器执行。处理语法树是很简单的，同样写程序创建一棵语法树也很简单。

我们可以让 infix 函数接受一个 opcode 参数，这样有助于代码生成。我们同样也可以添加一些其他方法来支持常量折叠或者代码生成。

我们还可以继续添加更多的语句支持（例如，for，switch 以及 try），语句标签，更多的错误检查，错误恢复以及更多的运算符。我们还可以添加类型规范已经类型推断。

我们可以让我们的语言更具扩展性。可以让定义变量更加方便，同样也可以让程序员自己添加新的运算符和语句。

快来试试我们在这篇论文中描述的解析器。

关于解析器的其他技术例子可以在 JSLint 中找到。

本文链接

Google Reader