关于javascript:手写一个Parser-代码简单而功能强大的Pratt-Parsing

在编译的流程中，一个很重要的步骤是语法分析（又称解析，Parsing）。解析器（Parser）负责将 Token 流转化为形象语法树（AST）。这篇文章介绍一种 Parser 的实现算法：Pratt Parsing，又称 Top Down Operator Precedence Parsing，并用 TypeScript 来实现它。

Pratt Parsing 实现起来非常简单，你能够看一下 TypeScript 实现后果，外围代码不到 40 行！

实现一个解析器的形式个别有 2 种：

应用 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，又称 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;
}

上面咱们逐行解说这个算法的工作原理。

首先，这个办法会从 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 这个参数。优先级的具体机理在前面还会讲述。

失去了 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
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

关于javascript:手写一个Parser-代码简单而功能强大的Pratt-Parsing

利用背景

Parser generator

手工实现

递归降落算法

Pratt Parsing

算法介绍

概念介绍

代码解说

2~10 行

11~19 行

示例的执行过程

如何解决联合性

残缺实现

参考资料

Just My Socks（注册教程内含优惠码）

关于javascript:手写一个Parser-代码简单而功能强大的Pratt-Parsing

利用背景

Parser generator

手工实现

递归降落算法

Pratt Parsing

算法介绍

概念介绍

代码解说

2~10 行

11~19 行

示例的执行过程

如何解决联合性

残缺实现

参考资料

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）