Pratt 解析是个黑盒

# Pratt 解析是个黑箱 来源：https://vinipsmaker.github.io/blog/article/pratt-parsing-is-a-black-box/ ## 简介 我注意到，我遇到的大多数 Pratt 解析教程几乎把全部时间都花在解释 Pratt 的算法上，却没有解释 Pratt 背后真正重要的那些性质。如果你使用像 Rhombus 这样的高级语言编程，Pratt 解析只需要 9 行代码就能实现： ``` let mutable left = t.nud() ``` 这里有个秘密：这恰恰是关于 Pratt 最不需要理解的部分。事实上，你根本不需要理解这段代码！想象一下，如果你必须理解快速排序的实现才能使用它，那会是什么样子。想象一下，如果你必须知道如何从头实现一个文件系统才能使用文件。道理是一样的。如果你缺乏抽象能力，你在计算机科学领域将寸步难行，因为整个领域就是这样运作的。事实上，我从去年开始为一个编译器编写了一个重度依赖 Pratt 的解析框架的核心代码，而我甚至没有费心去详细了解上面那段代码。 还不信？想想传统解析技术是怎么做的：编译器编译器（parser generator）！它们使用代码生成器来生成解析算法，因为只有极少数人才会费心去了解解析引擎到底在做什么。Pratt 也是一样的。只不过 Pratt 非常小，你可以直接把这 9 行代码复制粘贴到项目里就完事了，而不是为项目添加一个复杂的新依赖。该算法自 1973 年以来没有变过，现在也不会变。 在本文中，我将讨论你在进行 Pratt 解析时真正需要记住的东西。重点不在于记忆任何内容，重点在于获得一种思维方式。只要获得了这种思维方式，你甚至不需要记住我说的任何一个字。 ## Nud 与 Led 对于从未接触过这个话题的人，我能坚定推荐的唯一一份 Pratt 解析教程，实际上是 Douglas Crockford 在 GOTO 2013 大会上的一场演讲 [1](https://vinipsmaker.github.io/blog/article/pratt-parsing-is-a-black-box/#)。Douglas Crockford 的这句话一针见血： > Pratt 把解析这件非常复杂的事情，归结为一个简单的问题：*我们期望在某个 token 的左边看到什么*？ > —— Douglas Crockford，GOTO 2013 乍一看，这可能像是一句缺乏意义的神秘宣言，但正是这个问题成为了你面对解析问题的框架，它会重塑你的大脑，让你内化 Pratt 解析的思维方式。这才是你需要理解的最重要的东西。 你需要为两类东西注册语义动作：nud 和 led。nud 是一个在其左侧不期望任何东西的 token（nud 代表 null denotation，空指称），而 led 则期望左侧有东西（led 代表 left denotation，左指称）。传统解析技术是将语义动作注册到产生式规则上的。这是我直接从 GNU Bison 手册中取的一个例子： ``` expr: expr '+' expr { $$ = $1 + $3; } ; ``` 花括号之间的文本是当左侧类似 BNF 的文法匹配时执行的代码。我要再强调一遍，因为这非常重要：传统解析技术是将语义动作注册到*产生式规则*上（根据定义，产生式规则是非终结符）。相比之下，Pratt 解析是将语义动作注册到*终结符本身*上。这是你面对解析问题方式上的根本转变。 这是我编译器中当前所用表格代码的精简版本： ``` static constinit const auto nud_table = make_dispatch_table( /* ... */ ); static constinit const auto led_table = make_dispatch_table( /* ... */ ); static constexpr auto prefix_operator_binding_power = 120; static constexpr auto binding_power = make_dispatch_table( /* ... */ ); ``` 每个表格左侧的值都是终结符的词法分析器代码。右侧的值取决于表格的类型： **Nud 表格**：符合签名 `ExprPtr(Context&, reader, reader&)` 的函数。 **Led 表格**：符合签名 `ExprPtr(Context&, reader, reader&, ExprPtr)` 的函数。 **结合力（binding power）表格**：正整数。 这些表格中的大多数语义动作，其函数体最多只有一个分号。下面是 `parse_unary_plus()` 的代码： ``` std::shared_ptr<Expr> parse_unary_plus( ParsingContext& context, Token tok, Reader& r) { return ast::make_expr<Expr>( tok.line(), tok.column(), parse_expr(context, r, prefix_operator_binding_power)); } ``` 表面上看，这只是一种不同但仍然非常相似的代码组织方式，但其影响实际上是巨大的。以下是仅由这一单一转变所带来的与传统解析技术的几个不同之处： - 你不需要担心在 LL(k) 等传统解析技术中出现的左递归问题。由于对语义动作的分发是在其关联的 token 已经从流中消费之后进行的，左递归根本不会发生。这不是问题。 - 解析引擎不需要测试备选方案或回溯。在某些解析器中（例如 PEG 与 packrat）常见的速度与内存之间的取舍消失了。Pratt 很快，而且它不会因为需要海量记忆化（memoization）而饿死。Pratt 只是比较数字，然后迭代或递归。 - 与上一点相关，但值得单独考虑：语义动作恰好执行一次！这意味着如果匹配失败，不需要回滚到之前的状态。换句话说，你的动作可以包含副作用。在我的解析器中，我利用这个特性，通过一个在每一层传递的共享上下文对象来完成词法作用域中的名称预留/释放。只是要注意不要滥用副作用，以免代码变成意大利面条。 - 同样相关的一点：你的语义动作总是知道自己是否是正确的匹配。因此，如果需要，它可以任意向前看。换句话说：你可以在语义动作中进一步使用 PEG 解析器（或分层的 Pratt 解析器）。虽然 Pratt 本身每次只消费 1 个 token，但 nud 和 led 本身每轮可以消费更多 token。你刚刚解锁了解析器组合器（parser combinators）的力量。 - 大多数文法歧义会变成表格冲突，这样你就可以在较简单的歧义情况上节省时间。如果你组合多个解析器，仍然可能出现文法歧义。所以你作为文法设计者的工作仍然存在，但根据我的经验，工作量要少得多。当你组合解析器时，你实际上是在组合文法。作为解析算法的 Pratt 并不会充当全知的神谕，去检测整个文法合并中的所有可能歧义。在这种情况下，Pratt（就像 PEG 一样）只会返回第一个可能的匹配。 - 表格中未填充的空缺在你的文法中会变成简单的扩展点。你可以根据已解析的文法来填充这些空缺。换句话说，你可以实现宏，甚至解析一个可以扩展自身运算符的语言。相比之下，基于产生式规则（正统解析学派）扩展现有文法，是一项值得用博士研究的复杂度来完成的工作。 你可能也会在传统学派中发现这些性质中的一些，但只是在一定程度上，或者要付出巨大的复杂度代价。尽管如此，我之前提到过这种组织方式是一种思维方式的*转变*，但到目前为止我只提到了采用 Pratt 后你可以使用的性质，那么转变到底在哪里呢？ 考虑解析函数调用的常见 EBNF 规则： ``` function_call = identifier, "(", [ argument_list ], ")" ; argument_list = expression, { ",", expression } ; ``` 当你工具箱中只有 nud 和 led，而没有产生式规则时，你如何处理这个问题？关键的观察是：左括号总是期望其左侧有东西，所以它是一个 led。就是这样：为左括号注册一个 led，然后从那里开始解析函数调用。这并不显而易见，特别是当你只接触过传统解析学派时。这也正是 Douglas Crockford 说这句话时一针见血的原因： > Pratt 把解析这件非常复杂的事情，归结为一个简单的问题：*我们期望在某个 token 的左边看到什么*？ > —— Douglas Crockford，GOTO 2013 数组索引的 led 与函数调用的 led 非常相似。下面是我自己的解析器中使用的变体： ``` std::shared_ptr<Expr> parse_array_indexing( ParsingContext& context, Token tok, Reader& r, std::shared_ptr<Expr> left) { std::vector<std::shared_ptr<Expr>> indexes; if (r.code() != rbrack) { indexes.emplace_back(parse_expr(context, r, parse_until_end)); while (r.code() != rbrack) { if (!r.eat()) { throw unexpected_token{r, /*expected=*/"]"}; } indexes.emplace_back(parse_expr(context, r, parse_until_end)); } } assert(r.code() == rbrack); return ast::make_expr<Expr>( tok.line(), tok.column(), left, std::move(indexes)); } ``` Pratt 不仅仅是优先级爬升（precedence climbing）。Pratt 是一种组织代码的方式。首先把 Pratt 当作黑箱来学习，实际上有助于理解这种区别。如果你接触不到黑箱，你就不会倾向于把 Pratt 简化为优先级爬升。希望当你想要揭开抽象、看看内部实现的时候，你不会犯下把 Pratt 仅仅当作优先级爬升的一个变体来对待的错误，因为到那时你已经见识了 Pratt 解析所解锁的全部力量。 Andy Chu 关于不使用原型继承的 Pratt 解析的博客文章值得一读，因为它对比了两种截然不同的 Pratt 解析器编写风格 [2](https://vinipsmaker.github.io/blog/article/pratt-parsing-is-a-black-box/#)。下面是一个用 Rhombus 编写的最小计算器，它（在风格上）更接近使用原型继承的版本，而不是 Andy Chu 展示的风格： ``` class Token(~nud: nud_impl = #false, ~led: led_impl = #false) { method nud(): nud_impl(this) method led(lhs): led_impl(this, lhs) method prefix(): expression(30) method rhs(): expression(this.lbp) } class RParen(): extends Token( ~led: fun(tok, lhs): lhs + tok.rhs(), ~led: fun(tok, lhs): lhs - tok.rhs(), ~led: fun(tok, lhs): lhs * tok.rhs(), ~led: fun(tok, lhs): lhs / tok.rhs(), ) { ... } | digit+: Token(~nud: fun(_): String.to_int(lexeme)) | error("expected closing parens") def input = Parse(...) ```