在编译的流程中，一个很重要的步骤是语法分析（又称解析，Parsing）。解析器（Parser）负责将 Token 流转化为形象语法树（AST）。这篇文章介绍一种 Parser 的实现算法：Pratt Parsing，又称 Top Down Operator Precedence Parsing，并用 TypeScript 来实现它。
Pratt Parsing 实现起来非常简单，你能够看一下 TypeScript 实现后果，外围代码不到 40 行！
利用背景
实现一个解析器的形式个别有 2 种：
- 应用 Parser generator
- 手工实现
Parser generator
应用 Parser generator。用一种 DSL（比方 BNF）来形容你的语法，将形容文件输出给 Parser generator，后者就会输入一份用来解析这种语法的代码。
这种形式十分不便，足以满足绝大部分的需要。然而在一些场景下，它不够灵便（比方无奈提供更有用的、蕴含上下文的错误信息）、性能不够好、生成代码较长。并且，在形容 表达式的操作符优先级 (precedence) 和联合性 (associativity) 的时候，语法形容会变得非常复杂、难以浏览，比方 wikipedia 的例子：
expression ::= equality-expression
equality-expression ::= additive-expression (( '==' | '!=') additive-expression ) *
additive-expression ::= multiplicative-expression (( '+' | '-') multiplicative-expression ) *
multiplicative-expression ::= primary (( '*' | '/') primary ) *
primary ::= '(' expression ')' | NUMBER | VARIABLE | '-' primary你须要为每一种优先级创立一个规定，导致表达式的语法形容非常复杂。
因而有时候须要用第二种形式：手工实现。
手工实现
递归降落算法
手工实现 Parser 的常见办法是 递归降落算法 。递归降落算法比拟善于解析的是 语句(Statement)，因为创造者在设计语句的时候，无意地将语句类型的标识放在最结尾，比方if (expression) ...、while (expression) ...。得益于此，Parser 通过结尾来辨认出语句类型当前，就晓得须要顺次解析哪些构造了，顺次调用对应的构造解析函数即可，实现非常简单。
然而，递归降落算法在解决 表达式 (Expression) 的时候十分 吃力 ，因为 Parser 在读到表达式结尾的时候，无奈晓得正在解析哪种表达式，因为操作符(Operator) 往往在表达式的两头地位（甚至结尾），比方加法运算的 +、函数调用的()。并且，你须要为每一种 操作符优先级 (precedence) 都独自编写一个解析函数，并手动解决 联合性(associativity)，因而解析函数会比拟多、比较复杂。
比方在 wikipedia 的例子中，expression负责解决加减法、term负责解决乘除法，并且前者调用后者。能够设想有更多优先级时，代码会更加简单，递归调用层级会更深。比方，即便输出字符串是简略的1，这个解析器也须要递归地调用以下解析函数：program -> block -> statement -> expression -> term -> factor。前面 2 层调用本应该防止，因为输出基本不蕴含加减乘除法！
因而，在手工实现 Parser 的时候，个别会 将表达式的解析交给其它算法，躲避递归降落的劣势。Pratt Parsing 就是这样一种善于解析表达式的算法。
Pratt Parsing
Pratt Parsing，又称 Top Down Operator Precedence Parsing，是一种很奇妙的算法，它实现简略、性能好，而且很容易定制扩大，尤其善于解析表达式 ，善于解决表达式操作符 优先级 (precedence) 和联合性(associativity)。
算法介绍
概念介绍
Pratt Parsing 将 token 分成 2 种：
- prefix (正规术语是 nud)。如果一个 token 能够放在表达式的最结尾，那么它就是一个 ”prefix”。比方
123、(，或者示意正数的-。以这种 token 为核心，构建表达式节点时，不须要晓得这个 token 右边的表达式。它们构建进去的表达式节点相似于这样：
// 正数的负号前缀
// 不须要晓得它右边的表达式
{
type: "unary",
operator: "-",
body: rightExpression,
}- infix (正规术语是 led)。如果一个 token 在构建表达式节点的时候，必须晓得它右边的子表达式，那么它就是一个 ”infix”。这意味着 infix 不能放在任何表达式的结尾。比方加减乘除法操作符。它们构建进去的表达式节点相似于这样：
// 减法操作符
// 须要提前解析好它右边的表达式，失去 leftExpression，能力构建减法节点
{
type: "binary",
operator: "-",
left: leftExpression,
right: rightExpression,
}留神，尽管 - 既能够是 prefix 又能够是 infix，但实际上，你在从左到右读取输出字符串的时候，你是能够立刻判断出你遇到的 - 应该当作 prefix 还是 infix 的，不必放心混同（比方-1-2）。在了解了上面的算法当前，你会更明确这一点。
代码解说
Pratt Parsing 算法的外围实现就是 parseExp 函数：
function parseExp(ctxPrecedence: number): Node {let prefixToken = scanner.consume();
if (!prefixToken) throw new Error(`expect token but found none`);
// because our scanner is so naive,
// we treat all non-operator tokens as value (.e.g number)
const prefixParselet =
prefixParselets[prefixToken] ?? prefixParselets.__value;
let left: Node = prefixParselet.handle(prefixToken, parser);
while (true) {const infixToken = scanner.peek();
if (!infixToken) break;
const infixParselet = infixParselets[infixToken];
if (!infixParselet) break;
if (infixParselet.precedence <= ctxPrecedence) break;
scanner.consume();
left = infixParselet.handle(left, infixToken, parser);
}
return left;
}上面咱们逐行解说这个算法的工作原理。
2~10 行
首先，这个办法会从 token 流 吃掉 一个 token。这个 token必然 是一个 prefix（比方遇到 - 要将它了解为 prefix）。
留神，consume 示意吃掉，peek 示意瞥一眼。
在第 7 行，咱们找到这个 prefix 对应的表达式构建器（prefixParselet），并调用它。prefixParselet 的作用是，构建出以这个 prefix 为核心的表达式节点。
咱们先假如简略的状况，假如第一个 token 是123。它会触发默认的 prefixParselet(prefixParselets.__value)，间接返回一个 value 节点：
{
type: "value",
value: "123",
}它就是咱们在第 9 行赋值给 left 的值（曾经构建好的表达式节点）。
在更简单的状况下，prefixParselet 会递归调用 parseExp。比方，负号- 的 prefixParselets 是这样注册的：
// 负号前缀的优先级定为 150，它的作用在前面讲述
prefixParselets["-"] = {handle(token, parser) {const body = parser.parseExp(150);
return {
type: "unary",
operator: "-",
body,
};
},
};它会递归调用 parseExp，将它左边的表达式节点解析进去，作为本人的 body。（留神它基本不关怀本人右边的表达式是什么）
在这里，递归调用 parseExp(150) 传递的参数 150，能够了解成 它与左边子表达式的绑定强度 。举个例子，在解析-1+2 的时候，prefix - 调用 parseExp(150) 失去的 body 是1，而不是1+2，这就要归功于 150 这个参数。优先级的具体机理在前面还会讲述。
11~19 行
失去了 prefix 的表达式节点当前，咱们就进入了一个 while 循环，这个循环负责解析出后续的 infix 操作。比方-1 + 2 + 3 + 4，前面 3 个加号都会在这个循环中解析进去。
它先从 token 流 瞥见 一个 token，作为 infix，找到它对应的表达式构建器（infixParselet），调用它，失去新的表达式节点。留神，调用 infixParselet 时传入了left，因为 infix 须要它右边的表达式节点能力构建本人 **。
比方，-的 infixParselet 是这样注册的：
// 加减法的优先级定义为 120
infixParselets["-"] = {
precedence: 120,
handle(left, token, parser) {const right = parser.parseExp(120);
return {
type: "binary",
operator: "-",
left,
right,
};
},
};相似于 prefixParselet，它也会递归调用 parseExp 来解析左边的表达式节点。不同之处在于，它自身还有一个可读取的 precedence 属性，以及它在构建表达式节点时应用了 left 参数。
持续往下，了解 13~16 行的 3 个判断，是了解整个算法的要害。
第一个判断 if (!infixToken) break; 很好了解，阐明曾经读到输出开端，解析天然就要完结。
第二个判断 if (!infixParselet) break;也比拟好了解，阐明遇到了非中断操作符，可能是因为输出有谬误语法，也可能是遇到了 ) 或者;，须要将以后解析进去的表达式节点返回给调用者来解决。
第三个判断 if (infixParselet.precedence <= ctxPrecedence) break; 是整个算法的外围，后面提到的 parseExp 的参数 ctxPrecedence，就是为这一行而存在的。它的作用是， 限度本次 parseExp 调用只能解析优先级大于 ctxPrecedence 的 infix 操作符 。如果遇到的 infix 优先级小于等于ctxPrecedence，则进行解析，将以后解析后果返回给调用者，让调用者来解决后续 token。 初始时 ctxPrecedence 的值为 0 ，示意要解析完所有操作，直到遇到结尾（或遇到不意识的操作符）。
比方，在后面 -1+2 的例子中，前缀 - 的 prefixParselet 递归调用了 parseExp(150)，在递归的 parseExp 执行中，ctxPrecedence 为 150，大于 +infix 的优先级 120，因而这个递归调用遇到 + 的时候就完结了，使得前缀 - 与1绑定，而不是与 1+2 绑定。这样，能力失去正确的后果(-(1))+2。
在 infixParselet 递归调用 parseExp 的时候，也是同样的情理。
你能够将 prefixParselet 和 infixParselet 递归调用 parseExp 的行为，了解成 用一个“磁铁”来吸引后续的 token，递归参数 ctxPrecedence 就示意这个磁铁的“吸力”。仅仅当后续 infix 与它右边的 token 联合的足够严密（infixParselet.precedence 足够大）时，这个 infix 才会一起被“吸”过去。否则，这个 infix 会与它右边的 token“拆散”，它右边的 token 会参加本次 parseExp 构建表达式节点的过程，而这个 infix 不会参加。
综上所述，Pratt Parsing 是一种循环与递归相结合的算法 。parseExp 的执行构造大略是这样：
-
吃一个 token 作为 prefix，调用它的 prefixParselet，失去
left（曾经构建好的表达式节点）- prefixParselet递归调用 parseExp，解析本人须要的局部，构建表达式节点
-
while 循环
- 瞥一眼 token 作为 infix，如果它的优先级足够高，能力持续解决。否则函数
return left -
吃掉 infix token，调用它的 infixParselet，将
left传给它- infixParselet递归调用 parseExp，解析本人须要的局部，构建表达式节点
- 失去新的
left
- 瞥一眼 token 作为 infix，如果它的优先级足够高，能力持续解决。否则函数
return left
示例的执行过程
当初，用 1 + 2 * 3 - 4 作为例子，了解 Pratt Parsing 算法的执行过程：
- 先定义好每个 infix 的优先级（即
infixParselet.precedence）：比方，加减法为 120，乘除法为 130（乘除法的“绑定强度”更高） -
初始时调用
parseExp(0)，即ctxPrecedence=0- 吃 掉一个 token
1，调用 prefixParselet，失去表达式节点1，赋值给left - 进入 while 循环，瞥见
+，找到它的 infixParselet，优先级为 120，大于 ctxPrecedence。因而这个 infix 也一起被“吸走” -
吃 掉
+，调用+的 infixParselet.handle，此时left为1+的 infixParselet.handle 递归调用parser.parseExp(120)，即ctxPrecedence=120- 吃 掉一个 token
2，调用 prefixParselet，失去表达式节点2，赋值给left - 进入 while 循环，瞥见
*，找到它的 infixParselet，优先级为 130，大于 ctxPrecedence。因而这个 infix 也一起被“吸走” -
吃 掉
*，调用*的 infixParselet.handle，此时left为2*的 infixParselet.handle 递归调用parser.parseExp(130)，即ctxPrecedence=130- 吃 掉一个 token
3，调用 prefixParselet，失去表达式节点3，赋值给left - 进入 while 循环，瞥见
-，找到它的 infixParselet，优先级为 120， 不大于 ctxPrecedence，因而这个 infix 不会被一起吸走，while 循环完结 parser.parseExp(130)返回3
*的 infixParselet.handle 返回2 * 3（将parser.parseExp的返回值与left拼起来），赋值给left- 持续 while 循环，瞥见
-，找到它的 infixParselet，优先级为 120， 不大于 ctxPrecedence。因而这个 infix 不会被一起吸走，while 循环完结 parser.parseExp(120)返回子表达式2 * 3
+的 infixParselet.handle 返回1+(2*3)（将parser.parseExp的返回值与left拼起来），赋值给left- 持续 while 循环，瞥见
-，找到它的 infixParselet，优先级为 120，大于 ctxPrecedence。因而这个 infix 也一起被“吸走” - 吃 掉
-，调用-的 infixParselet.handle，此时left为1+(2*3) - 与之前同理，
-的 infixParselet.handle 的返回后果为(1+(2*3))-4（将parser.parseExp的返回值与left拼起来），赋值给left - while 循环持续，然而发现前面没有 token，因而退出 while 循环，返回
left
- 吃 掉一个 token
parseExp(0)返回(1+(2*3))-4
如何解决联合性
操作符的联合性 (associativity)，是指，当表达式呈现多个 间断的 、 雷同优先级的 操作符时，是右边的操作符优先联合(left-associative)，还是左边的优先联合(right-associative)。
依据下面形容的算法，1+1+1+1是左联合的，也就是说，它会被解析成((1+1)+1)+1，这合乎咱们的预期。
然而，有一些操作符是右联合的，比方赋值符号 =(比方a = b = 1 应该被解析成 a = (b = 1))、取幂符号^(比方a^b^c 应该被解析成a^(b^c))。
在这里，咱们应用
^作为取幂符号，而不是像 Javascript 一样应用**，是为了防止一个操作符恰好是另一个操作符的前缀，引发以后实现的缺点：遇到**的第一个字符就急迫地辨认成乘法。实际上这个缺点很好修复，你能尝试提一个 PR 吗？
如何实现这种右联合的操作符呢？答案只须要一行：在 infixParselet 中，递归调用 parseExp 时，传递一个稍小一点的 ctxPrecedence。这是咱们用于注册 infix 的工具函数：
function helpCreateInfixOperator(
infix: string,
precedence: number,
associateRight2Left: boolean = false
) {infixParselets[infix] = {
precedence,
handle(left, token, { parseExp}) {const right = parseExp(associateRight2Left ? precedence - 1 : precedence);
return {
type: "binary",
operator: infix,
left,
right,
};
},
};
}这样，递归 parseExp 的“吸力”就弱了一些，在遇到雷同优先级的操作符时，左边的操作符联合得更加严密，因而也被一起“吸”了过去（而没有拆散）。
残缺实现
残缺实现的 Github 仓库。它蕴含了测试（覆盖率 100%），以及更多的操作符实现（比方括号、函数调用、分支操作符 ...?...:...、右联合的幂操作符^ 等）。
参考资料
- https://engineering.desmos.com/articles/pratt-parser/
- http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/
- https://youtu.be/Nlqv6NtBXcA?t=1257