在编译的流程中，一个很重要的步骤是语法分析（又称解析，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-expressionequality-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是这样注册的：

// 加减法的优先级定义为120infixParselets["-"] = {  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
  • 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
  • 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