原文地址
1.什么是解析器？
当您阅读一个表达式（例如 1/2+3.4）时，可以立即理解它的一些含义。您可以识别到这里有三个数字，并且这些数字由运算符组合在一起。您可能还记得除法的优先级高于加法，因此在计算表达式时，您应该先计算除法 1/2 ，然后计算加法 +3.4 。
再看一下这个字符串 2H3SGKHJD 。乍一看，这似乎是一个无意义的字符序列。如果我告诉你这些字母应该 以 2个字符为一对 进行分组，并以 G 作为分隔符，你心里可能看起来更接近 2H 3S ; KH JD ，这让我们更进一步理解这个字符串代表 在纸牌游戏中 手中的纸牌(梅花(C)、方片(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 number
leftNode = NumberNode(firstToken)
otherwise
Error("Expected a number")
nextToken = tokens.consume()
if nextToken is an operator token
rightNode = parse(tokens)
return OperatorNode(
operator: nextToken,
leftNode,
rightNode
)
otherwise
return 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 leftNode
2 consume "+" to be nextToken
2 rightNode = parse [1]
3 consume 1 as a NumberNode into leftNode
3 no next token
3 return:
1
2 combine 2, "+" and 1 into an OperatorNode
2 return:
"+"
/
2 1
1 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 number
leftNode = NumberNode(firstToken)
otherwise
Error("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
)
otherwise
return 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 leftNode
2 peek "+" to be nextToken
2 greaterBindingPower("+", "*") is false
2 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 未处理。现在来解决这个问题：
原文地址
1.什么是解析器？
当您阅读一个表达式（例如 1/2+3.4）时，可以立即理解它的一些含义。您可以识别到这里有三个数字，并且这些数字由运算符组合在一起。您可能还记得除法的优先级高于加法，因此在计算表达式时，您应该先计算除法 1/2 ，然后计算加法 +3.4 。
再看一下这个字符串 2H3SGKHJD 。乍一看，这似乎是一个无意义的字符序列。如果我告诉你这些字母应该 以 2个字符为一对 进行分组，并以 G 作为分隔符，你心里可能看起来更接近 2H 3S ; KH JD ，这让我们更进一步理解这个字符串代表 在纸牌游戏中 手中的纸牌(梅花(C)、方片(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 number
leftNode = NumberNode(firstToken)
otherwise
Error("Expected a number")
nextToken = tokens.consume()
if nextToken is an operator token
rightNode = parse(tokens)
return OperatorNode(
operator: nextToken,
leftNode,
rightNode
)
otherwise
return 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 leftNode
2 consume "+" to be nextToken
2 rightNode = parse [1]
3 consume 1 as a NumberNode into leftNode
3 no next token
3 return:
1
2 combine 2, "+" and 1 into an OperatorNode
2 return:
"+"
/
2 1
1 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 number
leftNode = NumberNode(firstToken)
otherwise
Error("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
)
otherwise
return 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 leftNode
2 peek "+" to be nextToken
2 greaterBindingPower("+", "*") is false
2 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 number
leftNode = NumberNode(firstToken)
otherwise
Error("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
)
otherwise
return 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 leftNode
leftNode:
"*"
/
3 2
1 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 leftNode
leftNode:
"+"
/
"*" 1
/
3 2
1 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]
