XSharp开发思路-表达式解析-Pratt Parsing

手工实现 Parser 常用递归下降法(Recusive Descent)，XSharp 的 Parser 也采用了递归下降的主体结构。

一般来说递归下降法适用于自上而下的结构，更容易解析开头有标识符的语言，如：

if () {}
while () {}
class {}

但也由于同样的原因，递归下降法处理表达式非常吃力。Parser 在读到表达式开头的时候，无法知道自己身处哪种表达式之中，这是因为操作符往往在表达式的中间位置（甚至结尾），比如加法运算的+、函数调用的()。为了能自顶向下地解析表达式，你需要将每一种操作符 优先级(priority) 都单独作为一个层级，为其编写解析函数，并手动处理 结合性(associativity) ，因此解析函数会比较多、比较复杂。

所以在重构 XSharp 的 Parser 时，我选择了 Pratt Parsing 作为表达式的算法

笔者参考了 Pratt Parsing 知乎 和 Pratt Parsing Rust 进行了有关代码的重构

核心代码如下：

ASTNode* lhs = operand();

while (true) {
    if (isStopwords(current, stopwords)) return lhs;

    if (current->type != Operator)
        throw XSharpError("No operator matched after operand");

    if (priority(current->value) <= ctxPriority) break;

    XString op = current->value;

    forward();
    auto right_binding_power =
        assoc(op) == LeftToRight ? priority(op) : priority(op) - 1;
    auto rhs = expression(stopwords, right_binding_power);

    auto new_lhs = new BinaryOperatorNode;
    new_lhs->setOperatorStr(op);
    new_lhs->setLeft(lhs);
    new_lhs->setRight(rhs);
    lhs = new_lhs;
}

return lhs;

原理如下：

我们在解析表达式时，我们总是倾向于让priority较高的运算符与operand结合

故我们在已知左边表达式 lhs 时，从人类通常思维出发

我们倾向于在 op 的 priority 较高时拆散 lhs，让 op 不断与 lhs 最右边的 operand 结合直到优先级不足

而在 op 的 priority 较低时，让 op 与 lhs 整体结合

但这不符合机器从左到右解析的顺序，所以我们可以换一种思路

所以，我们从左向右扫描，设初始优先级为 0，从 priority 较低的层级出发，一步步找到优先级更高的运算符并结合

以表达式 a / b = 2 + 5 * 6 为例

初始层级优先级为 0，给当前层级命名 initial

• 进入 initial 层，我们先读入 token a

  发现 / 的优先级大于 0，于是结合 0 与/ 并进入属于 ‘/’ 的层级，该层级优先级为 3，该层级求优先级大于 3 的 rhs

  • 然后读入 token b, b 属于 ‘/’ 层级，又读入 operator = 发现其优先级<=当前层级最小优先级

    于是结束 ‘/’ 层级， 确定其 rhs 为 b，得到一个整体 (a / b)

• 回到 initial 层，且此时 lhs 为a / b，继续读入 operator = ，其优先级为 1>=0，故进入 ‘=’ 层

  • 现在读入 token 2，再读入 operator +，发现其优先级 2>=1 故可作为 rhs，进入 '+' 层

    • 继续求 '+' 的 rhs，发现 token 5，和 operator * ，* 的优先级 3>=2，故进入'*'层

      • 读入 6 表达式结束，将 6 作为 '*' 的 rhs，开始回溯

      将 5 * 6 作为 ‘+’ 的 rhs，退出 ‘+’ 层

    得到 2 + (5*6) ，将其作为 '=' 的 rhs，退出 ‘=' 层

最后回到initial层，结合已有 lhs：a / b, op: =, rhs 2 + ( 5 * 6 )，返回(a / b) = ( 2 + ( 5 * 6 ) )

至此基本算法结束，对于右结合的associativity可以通过降低其’右优先级‘来实现（如代码所示），其他高级特性可参考上面引用的文章

通过这个算法，我们成功把原本 200 行的复杂函数压缩到 20 行，且获得了更高的性能。