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

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

作者:Douglas Crockford

简介

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 的 CGOLLISP 2MLISPDylanInterlisp 的 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)的。(我们将会在接下来的优先级一节来解释 nudled 的作用以及约束力的含义)

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 中继承的元素。

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.create(original_symbol);
        s.id = s.value = id;
        s.lbp = bp;
        symbol_table[id] = s;
    }
    return s;
};

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

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)。

var advance = function(id) {
    var a, o, t, v;
    if (id && token.id !== id) {
        token.error('Expected "' + id + '".');
    }
    if (token_nr >= tokens.length) {
        token = symbol_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.create(o);
    token.value = v;
    token.arity = a;
    return token;
};

阅读全文…