如何使用 Pratt 解析器?

原文地址

1.什么是解析器？

当您阅读一个表达式（例如 1/2+3.4）时，可以立即理解它的一些含义。您可以识别到这里有三个数字，并且这些数字由运算符组合在一起。您可能还记得除法的优先级高于加法，因此在计算表达式时，您应该先计算除法 1/2 ，然后计算加法 +3.4 。

再看一下这个字符串 2H3SGKHJD 。乍一看，这似乎是一个无意义的字符序列。如果我告诉你这些字母应该 以 2个字符为一对 进行分组，并以 G 作为分隔符，你心里可能看起来更接近 2H 3S ; KH JD ，这让我们更进一步理解这个字符串代表 在纸牌游戏中 手中的纸牌(梅花©、方片(D)、红心(H)、黑桃(S)四种花色)。

解析是获取字符串并将其转换为抽象语法树（或 AST）的过程。这是表达式(expression) AST结构的表示，例如：

OperatorNode(operator: "+",left: OperatorNode(operator: "/",left: 1,right: 2),right: 3.4
)

或者，如图所示，

       "+"/     \"/"    3.4/     \
1         2

这样的树是计算表达式的值或进行漂亮地渲染它的第一步。

那么，如何创建 AST？在 Desmos(Desmos是一个图形计算器)，我们使用 Vaughan Pratt 描述的方法。本文首先将清晰、简洁地解释 Pratt 解析的工作原理。然后，我们将解释在 Desmos 采用此技术的动机，并将其与我们之前的方法 jison 解析器生成器进行比较。

最后，我们提供了 Typescript 中解析器（和词法分析器）的示例实现，并与 CodeMirror 集成。我们希望这对于任何有兴趣在浏览器中进行解析的人来说都是一个有用的参考和起点。

2.它是如何工作的？

解析函数(parse function)将在 tokens 对象上进行操作。这是一个token序列，例如 [1, “/”, 2, “+”, 3.4] ，它是通过称为词法分析的过程根据输入生成的。我们不会在这里详细讨论词法分析的细节，只是向您介绍我们的示例实现。

tokens 对象是一个token 流，它允许我们 消费(consume ) 一个token ，返回下一个token 并 向前推进token 流。我们还可以查看 (peek)一个token ，这会为我们提供下一个token ，而无需 推进token 流。

//consume 消费了token 1,并返回1
[1, "/", 2, "+", 3.4].consume() -> 1, ["/", 2, "+", 3.4]
//consume 只是返回1，并不消费
[1, "/", 2, "+", 3.4].peek() -> 1, [1, "/", 2, "+", 3.4]
// 空的token流只是返回  empty token
[].consume() -> empty token, []
[].peek() -> empty token, []

让我们从递归调用开始，并在进行过程中填写内容。将以伪代码的形式展示我们的方法，但欢迎您在我们进行过程中参考 Typescript 实现。

function parse(tokens):firstToken = tokens.consume()if firstToken is a numberleftNode = NumberNode(firstToken)otherwiseError("Expected a number")nextToken = tokens.consume()if nextToken is an operator tokenrightNode = parse(tokens)return OperatorNode(operator: nextToken,leftNode,rightNode)otherwisereturn leftNode

我们期望一个数字 token 后跟一个 可选的运算符(operator )。然后执行递归调用来查找右侧的子表达式。到目前为止一切顺利——我们开始了解如何解析像 3 * 2 + 1 这样的表达式：

parse [3, "*", 2, "+", 1]
1 consume 3 as a NumberNode into leftNode
1 consume "*" to be nextToken
1 rightNode = parse [2, "+", 1]2 consume 2 as a NumberNode into leftNode2 consume "+" to be nextToken2 rightNode = parse [1]3 consume 1    as a NumberNode into leftNode3 no next token3 return:12 combine 2, "+" and 1 into an OperatorNode2 return:"+"/     \2         11 combine 3, "*" and rightNode into an OperatorNode
1 return:"*"/     \
3        "+"/     \2         1

2.1 优先级 Precedence

如果用上边的逻辑 计算 3 * 2 + 1 这个表达式，将先计算加法 2 + 1 ，然后将该子树的结果乘以 3 ，最终得到 9 。结果是不对的，因为传统上乘法的优先级高于加法，我们希望树看起来像这样：

        "+"/     \"*"        1/     \
3         2

Pratt 解析器 用术语“绑定能力 binding power”来表达这个想法。乘法比加法具有更高的绑定能力，因此上面表达式中的 3 * 2 优先。当我们执行递归调用来解析 2 + 1 时，我们正在寻找代表 乘号* 右侧的节点。因此，当我们看到+时，我们想要停下来，因为它的绑定能力不如*。让我们将这个想法添加到代码中，注意这仍然不完整，我们将不断改进：

function parse(tokens, lastOperator):firstToken = tokens.consume()if firstToken is a numberleftNode = NumberNode(firstToken)otherwiseError("Expected a number")nextToken = tokens.peek()if nextToken is an operator and greaterBindingPower(nextToken, lastOperator)tokens.consume()rightNode = parse(tokens, nextToken)return OperatorNode(operator: nextToken,leftNode,rightNode)otherwisereturn leftNode

让我们考虑一下这如何改变解析 3 * 2 + 1 的执行：

parse [3, "*", 2, "+", 1], empty token
1 consume 3 as a NumberNode into leftNode
1 peek "*" to be nextToken
1 greaterBindingPower("*", empty token) is true by default, so continue
1 consume "*"
1 parse [2, "+", 1], "*"2 consume 2 as a NumberNode into leftNode2 peek "+" to be nextToken2 greaterBindingPower("+", "*") is false2 return:2
1 combine 3, "*" and 2 into an OperatorNode
1 return:"*"/     \
3         2

2.2 在左侧积累(Accumulating on the left )

根据需要，在解析子表达式 2 + 1 时，我们的递归调用在 + 之前停止。这使我们能够在外部调用中正确地将 3 * 2 组合到乘法节点中。然而，计算会提前停止，而剩余的 + 1 未处理。现在来解决这个问题：

function parse(tokens, lastOperator):firstToken = tokens.consume()if firstToken is a numberleftNode = NumberNode(firstToken)otherwiseError("Expected a number")repeat  nextToken = tokens.peek()if nextToken is an operator and greaterBindingPower(nextToken, lastOperator)tokens.consume()rightNode = parse(tokens, nextToken)leftNode = OperatorNode(operator: nextToken,leftNode,rightNode)otherwisereturn leftNode

这会产生以下计算结果：

parse [3, "*", 2, "+", 1], empty token
1 consume 3 as a NumberNode into leftNode
1 peek "*" to be nextToken
1 greaterBindingPower(*, empty token) is true by default, so continue
1 consume "*"
1 rightNode = parse [2, "+", 1], "*"... returns 2, as above
1 combine 3, "*" and 2 into an OperatorNode, and store it in leftNodeleftNode:"*"/     \
3         21 repeat
1 peek "+" to be nextToken
1 greaterBindingPower(+, empty token) is true by default
1 consume +
1 parse [1], '+'... returns 1
1 combine leftNode, "+" and 1 into an OperatorNode, and store it in leftNodeleftNode:"+"/     \"*"        1/     \
3         21 repeat
1 nextToken is empty, so return leftNode

我们现在正确地将 3 * 2 子表达式分组为 AST 中的 OperatorNode！

2.3 合成（ Synthesis ）

现在可以看到绑定能力如何指导我们在构建树时进行正确的分组。只要遇到的运算符具有更高的绑定能力，就会继续进行递归调用，从而在树的右侧构建我们的表达式。当遇到具有较低绑定能力的运算符时，将结果沿着调用链传播，直到达到绑定能力足以继续分组的级别。在那里，我们将积累的项转移到 leftNode 中，并继续构建表达式的右侧。

换句话说，虽然绑定力高于我们的上下文，但我们使用递归调用 关联到右侧。当它较低时，我们使用重复循环关联到 左侧。这是理解 Pratt 解析器如何工作的关键，因此值得花一点时间来逐步执行诸如 3 + 4 * 2 ^ 2 * 3 - 1 之类的内容来感受它。

2.4 结合性和绑定能力(Associativity and binding power)

我们还没有明确提到的一件事是运算符结合性。一些运算符（例如加法和减法）是左结合的，这意味着当我们重复应用它们时， 3 - 2 - 1 ，我们会结合到左侧 (3 - 2) - 1 。其他的，如求幂，则与右侧相结合，因此 2 ^ 3 ^ 4 与 2 ^ (3 ^ 4) 相同。

希望到目前为止的阐述能够清楚地说明我们如何使用 greaterBindingPower 函数来实现这一点。我们希望左结合运算符在遇到相同的运算符时停止递归。因此， greaterBindingPower(-, -) 应该为 false。另一方面，当运算符是右结合时，我们希望继续递归，因此 greaterBindingPower(^, ^) 应该为 true。

实际上，这种行为是通过为每个运算符类分配一个绑定力编号来实现的。例如，

+, - : 10
*, / : 20
^    : 30

我们将这个数字传递给解析函数，并查找下一个token的绑定能力来做出决定。右结合运算符是通过在进行递归调用时从其绑定能力中减去 1 来实现的。

parse(tokens, currentBindingPower):...repeat...nextToken = tokens.peek()if bindingPower[nextToken] <= currentBindingPowerstop repeatingnextBindingPower = if nextToken is left-associative then bindingPower otherwise bindingPower - 1rightNode = parse(tokens, nextBindingPower)...

2.5 扩展语法( Extending the grammar)

到目前为止，我们可以解析 <expression> <operator> <expression> 形式的数字和二元运算符，但我们可能必须处理其他形式，例如 ( <expression> ) 、 log <expression> ，甚至 if <expression> then <expression> otherwise <expression> 。

我们可以使用解析调用，它可以为我们提供一个比给定上下文绑定更强的子表达式。这样，我们就可以以一种优雅、可读的方式解析这些不同的形式。例如，要解析一对大括号中包含的表达式，

...
currentToken = tokens.consume()
if currentToken is "("expression = parse(tokens, 0) // Note, reset the binding power to 0 so we parse a whole subexpressionnext = tokens.consume()if next is not ")"Error("Expected a closing brace")
...

We can combine these concepts - the parsing of a sub-expression, the adjustment of the binding power passed to the recursive call, the left/right associativity, and error handling into a unit called a Parselet.

我们可以将这些概念（子表达式的解析、传给递归调用的绑定能力的调整 、左/右结合性以及错误处理）组合到一个称为 Parselet 的单元中。

We have two places in our code where parselets may be called. The first is the one between expressions that we have spent some time looking at (in Pratt parlance, this is referred to as “led”). The other is at the beginning of a new expression (in Pratt’s paper, “nud”). Currently we handle number tokens there, converting them to number nodes. This nicely abstracts into a parselet - one that converts a single token into a node and doesn’t perform any recursive calls to parse sub-expressions. This is also where the above code for parsing braces would go.

我们的代码中有两个地方可以调用 parselet。第一个地方是我们查找的表达式中间（Pratt的论文中，这被称为“led”）。另一个位于新表达的开头（在Pratt的论文中为“nud”）。目前我们在那里处理数字token，将它们转换为数字节点。这很好地抽象为一个解析器 - 将单个token转换为节点并且不执行任何递归调用来解析子表达式。这也是上面解析大括号的代码所在的位置。

在示例代码中，我们将它们标识为 initialParselet 和 consequentParselet 。每组 Parselet 都存储在一个map 中，由标识该 Parselet 的token类型作为 key。

initialPareselets = {"number": NumberParselet,"(": ParenthesisParselet,...
}NumberParselet:parse(tokens, currentToken):return NumberNode(currentToken)consequentParselets = {"+": OperatorParselet("+"),"-": OperatorParselet("-"),...
}OperatorParselet(operator):parse(tokens, currentToken, leftNode):myBindingPower = bindingPower[operator]rightNode = parse(tokens, if operator is left associative then myBindingPower otherwise myBindingPower - 1)return OperatorNode(operator,leftNode,rightNode)

2.6 将所有内容放在一起

通过上述更改，我们为完成的解析函数获得以下伪代码：

parse(tokens, currentBindingPower):initialToken = tokens.consume()initialParselet = initialMap[initialToken.type]if we didn't find a initialParseletError("Unexpected token")leftNode = initialParselet.parse(tokens, initialToken)repeatnextToken = tokens.peek()if nextToken is emptystop repeatingconsequentParselet = consequentMap[nextToken]if we didn't find an consequentParseletstop repeatingif bindingPower[nextToken] <= currentBindingPowerstop repeatingtokens.consume()leftNode = consequentParselet.parse(tokens, leftNode, nextToken)return leftNode

或者，请参阅 Typescript 中的实现。

3.转向使用 Pratt parsing

在转向 Pratt 解析器之前，我们使用 jison。对于那些不熟悉的人来说，jison 是 bison 解析器生成器的 JavaScript 实现。在 jison 中，您指定一个语法，例如：

an expression is a number or an operation
an operation is a sum, difference, product, or quotient
a sum is <expression> + <expression>
etc...

jison 接受这样的描述并输出一个能够解析该语法的 JavaScript 程序。这样做的好处是，您只需要担心声明语法，所有的实现都会为您处理！再加上我们的一些工程师熟悉类似的方法，使得 jison 成为我们最初实施的一个简单选择。

然而，随着时间的推移，我们发现了几个问题，促使我们寻找替代方案：

3.1 错误消息（Error messages ）

如果用户输入的表达式不满足我们的语法，例如忘记关闭括号或填充指数，我们的 jison 实现只能通知我们整个表达式格式错误。正如您可以想象的那样，这对于学生和老师来说是一次令人沮丧的经历。

在 jison 中，可以通过预测语法中的不正确模式来自定义错误。然而，这种方法有两个显着的缺点。首先，它是选择性加入的，这意味着您永远无法确定您已经涵盖了语法中所有可能的语法错误。其次，它使您的语法变得复杂，使得推理完整性和正确性变得更加困难，从而首先取消了使用解析器生成器的主要优点之一。

另一方面，Pratt 解析器方法自然会鼓励您在编写每个解析器时考虑边缘情况。它还使得捕获错误上下文以供外部代码使用变得非常简单。这使我们能够轻松地在编辑器中突出显示错误的位置。我们还利用这一点创建了一个非常强大的自动完成系统（未来帖子的主题）。

3.2 开发者友好度(Developer Friendliness )

以前，研究解析器内部需要熟悉 jison 规范语言，以及用于生成和测试解析器的周围工具。现在，我们的实现是用 Typescript 编写的——这也是我们团队每天使用的语言。这使得团队中的每个人都可以访问解析器代码，特别是因为实现是可读且简洁的。此外，由于团队的所有成员都可以轻松地审查代码，因此可以放心地进行更改。

3.3 代码重用和类型安全

以前，我们必须维护两个词法分析器 - 一个与 jison 兼容，另一个用于在 CodeMirror 中执行语法突出显示。通过采用 Pratt 解析，我们能够在 CodeMirror 使用的同一接口之上构建解析管道，从而消除重复。此外，我们的代码现在全部都是 Typescript，这意味着我们在实现内部以及与其他代码的边界处进行彻底的类型检查。

3.3 打包速度和大小

解析器实现需要比在 jison 中指定语法更多的代码行。然而，当 jison 生成解析程序时，它将语法扩展为非常大的转换表。结果是我们实际上向客户端发送了约 20KB，而新的实现将其减少到约 10KB。此外，经过测试超过 100k 个计算器表达式，Pratt 解析器最终比 jison 实现快大约 4 倍。我们认为（虽然我们还没有验证）这是因为 jison 生成的转换表太大而无法保存在缓存中，而浏览器在优化递归函数调用方面相当擅长。

4. 注意事项

我们发现使用 Pratt 解析器有几个缺点，但这些缺点可能对您有用。

4.1递归和内存（Recursion and Memory ）

因为我们依赖递归函数调用，所以您的解析器可能会耗尽 深度嵌套表达式的调用堆栈空间，例如 1^1^1^1... 。您可以通过在解析和抛出自定义“此表达式嵌套太深”错误时跟踪表达式的深度来缓解这种情况。另一种策略是通过自己管理解析器状态或使用诸如蹦床（trampolining）之类的方法将解析堆栈移至堆中。

4.2 正确性和性能复杂性 Correctness and Performance Complexity

有很多用于解析器生成器和语法的工具。例如，您可以分析语法并保证解析器的正确性或性能特征。因为 Pratt 解析器只是代码，所以总是存在效率低下的危险。开发人员可能会试图通过尝试多个解析路径来解决棘手的解析情况，这很容易导致指数级的复杂性。不幸的是，这里的解决方案是要小心。即使进行了代码审查和彻底的测试，您也无法保证您的解析器不会因某些输入而崩溃。

5. 总结

我们转向 Pratt 解析器的主要动机是灵活性。它使我们能够显示有用的本地化错误消息，从而显着改善了我们网站上的用户体验。我们希望本文能够帮助您选择正确的方法，并且如果您选择在项目中使用 Pratt 解析器，那么它是一个很好的起点。

6. 参考文章

在快速了解 Pratt 解析器的过程中，我们发现以下文章非常有用，您也可能会：

• 本系列博文由 Andy Chu 撰写。

• Jonathan Apodaca 撰写的关于 Pratt 解析的教程。

• Bob Nystrom 撰写的关于 Pratt 解析的教程。

• Eli Bendersky 的自上而下运算符优先级解析教程

• Douglas Crockford 撰写的关于创建 JavaScript 解析器//原文地址