Top down precedence algorithm

Table of Contents

• 1. 方法
• 2. Top down precedence algorithm原理
• 3. Ref

1. 方法

Wikipedia上介绍了 三种Bottom Up Parser用来解析表达式，分别是：

• Edsger Dijkstra的shunting yard algorithm
• Top down precedence algorithm
• Precedence climbing algorithm

shunting yard algorithm在开源项目 EvalEx中使用到，Top down precedence algorithm在Beautiful Code这本书和开源项目 Rodin Tool中有介绍

我只用Top down precedence algorithm写过一个类似逻辑门的解析器，支持

• bool 变量
• 与
• 或
• 非
• 括号

限制：the operator-precedence parser can parse all LR(1) grammars where two consecutive nonterminals never appear in the right-hand side of any rule.

2. Top down precedence algorithm原理

TDPA的核心就是下面一个递归函数expression()：

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

一个典型的中缀运算符实现

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

给定一个父节点的优先级，expression函数出解析一个表达式，这个表达式最顶层的运算符的优先级不会低于给定的父节点的优先级

首先需要给operator定义nud或/和led函数

• 前缀表达式和值(literal, constant)：定义nud(null denotation符号)
• 中缀和后缀操作符: 定义led(left denomination)

注意nud和led返回的也是一个expression，并且可能递归的调用expression

该算法描述如下：

• (1) 表达式的第一个字段必须后面几种之一：前缀表达式，值(literal, constant) ，因此调用第一个token的nud函数，返回一个表达式用left表示
• (2) 读取第二个符号
• (3) 当父节点的优先级小于当前token(操作符)的优先级时，继续把该token左边的表达式(树）给他，从而解析出新的left
• (4) 返回left
• 开始解析式expression的rbp为0

例如给定表达式 a + b * c * d，假定+的优先级为1, *为2

执行过程:

3. Ref

• Beautiful Code: Leading Programmers Explain How They Think
• Operator-precedence parser
• Operator-precedence parser