Pratt Parsing 算法介绍及实现

引言

手写递归下降 Parser 时常常会遇到左递归的问题。传统方法是改写文法消除左递归，但需要引入额外的文法，不便于代码的维护。另外，不同的运算符的优先级、结合性都不同。种种原因导致传统递归下降 Parser 的实现难度较大。

下面介绍由 Vaughan Pratt 提出的 Pratt Parsing 算法，它可以解决这些问题。

基础概念

首先介绍 Parsing 的一些基础概念。

前缀运算符（Infix Operator）：例如正负号 + -。特点是运算符在操作数之前。
中缀运算符（Prefix Operator）：例如加减乘除 + - * /。特点是运算符在操作数之间。
后缀运算符（Postfix Operator）：例如阶乘 !。特点是运算符在操作数之后。

在本文章中，定义：

1type InfixOp = '+' | '-' | '*' | '/' | '^'
2type PrefixOp = '-' | '+'
3type PostfixOp = '!'

AST（Abstract Syntax Tree）是一种树形结构，用于表示程序的语法结构。对于一个表达式，我们定义如下的 AST 结构：

 1class ExprNode {
 2    toString(): string {
 3        throw new Error('not implemented')
 4    }
 5}
 6
 7class ValueNode extends ExprNode {
 8    constructor(public val: number) {
 9        super()
10    }
11    toString() {
12        return this.val.toString()
13    }
14}
15
16class PrefixOpNode extends ExprNode {
17    constructor(public op: PrefixOp, public rhs: ExprNode) {
18        super()
19    }
20    toString() {
21        return `(${this.op}${this.rhs})`
22    }
23}
24class InfixOpNode extends ExprNode {
25    constructor(public op: InfixOp, public lhs: ExprNode, public rhs: ExprNode) {
26        super()
27    }
28    toString() {
29        return `(${this.lhs}${this.op}${this.rhs})`
30    }
31}
32class PostfixOpNode extends ExprNode {
33    constructor(public op: PostfixOp, public lhs: ExprNode) {
34        super()
35    }
36    toString() {
37        return `(${this.lhs}${this.op})`
38    }
39}

分词器（Tokenizer）将输入的字符串分割成 Token 序列。并且通常以迭代器的形式提供接口。分词相对简单，这里不再赘述。我们直接假设已经得到了 Token 流。

在本例子中，定义如下 Token 类型：

1
2enum TokenType { None, Num, Add, Sub, Mul, Div, Fac, Pow, LPa, RPa, Eoi }
3
4class Token {
5    constructor(public type: TokenType = TokenType.None, public value: string = '') { }
6}

TokenType.None：空 Token，用于占位。
TokenType.Num：数字。
TokenType.Add，TokenType.Sub，TokenType.Mul，TokenType.Div，TokenType.Pow：加减乘除乘方。
TokenType.Fac：阶乘。
TokenType.LPa，TokenType.RPa：左右括号。
TokenType.Eoi：End of Input，表示输入结束。

定义优先级：

 1    precOf(token: string): number {
 2        const precs = {
 3            '+': 10,
 4            '-': 10,
 5            '*': 20,
 6            '/': 20,
 7            '^': 30,
 8            '!': 40,
 9        } as Record<string, number>
10
11        return precs[token] || 0
12    }

定义迭代器：

 1class Iterator<T> {
 2    private pos: number
 3    constructor(private inner: Array<T> = []) {
 4        this.pos = 0
 5    }
 6    next(): T | undefined {
 7        var peek = this.peek()
 8        this.pos++
 9        return peek
10    }
11    peek(): T | undefined {
12        return this.inner[this.pos] || undefined
13    }
14}

我们会用迭代器包装一个 Token 数组。

next() 方法返回当前 Token，并将迭代器指针指向下一个 Token。这种操作也称为 consume 或者 eat。
peek() 方法返回当前 Token，但不改变迭代器指针。

我们的 Token 流定义如下：

 1let tokens = new Iterator<Token>([
 2    // - 1 + (2 - 3) * 6 / 3 ! - 2 ^ 3 ^ 4
 3    new Token(TokenType.Sub, '-'),
 4    new Token(TokenType.Num, '1'),
 5    new Token(TokenType.Add, '+'),
 6    new Token(TokenType.LPa, '('),
 7    new Token(TokenType.Num, '2'),
 8    new Token(TokenType.Sub, '-'),
 9    new Token(TokenType.Num, '3'),
10    new Token(TokenType.RPa, ')'),
11    new Token(TokenType.Mul, '*'),
12    new Token(TokenType.Num, '6'),
13    new Token(TokenType.Div, '/'),
14    new Token(TokenType.Num, '3'),
15    new Token(TokenType.Fac, '!'),
16    new Token(TokenType.Sub, '-'),
17    new Token(TokenType.Num, '2'),
18    new Token(TokenType.Pow, '^'),
19    new Token(TokenType.Num, '3'),
20    new Token(TokenType.Pow, '^'),
21    new Token(TokenType.Num, '4'),
22    new Token(TokenType.Eoi),
23])

Pratt Parser

Pratt Parser 是一种自顶向下的语法分析器。它的核心工作原理是：

把 Token 分为两类，一类是前缀运算符，一类是中缀运算符。假设前缀运算符的优先级最高，中缀运算符的优先级依次降低。注意：对于后缀运算符，我们把它当作中缀运算符的特殊形式处理。（具体原因可以看后文）因此，分成三类，也没问题。
每个 Token 都有与之关联的解析函数，这个函数的作用是解析以该 Token 开头的表达式。
- 例如，对于 Num，解析得到一个 ValueNode。
- 例如，对于 Add，解析得到一个 InfixOpNode。
由于我们把 Token 分为三类，每类都有对应的 Parser，具体来说分别是：
1. PrefixParser：前缀 Token 的 Parser。
2. InfixParser：中缀 Token 的 Parser。
3. PostfixParser：后缀 Token 的 Parser。（可看作一种特殊 InfixParser）
每个 Token 都有与之关联的优先级，这个优先级用于决定解析顺序。实际上在 Parse 函数中，我们会有两个优先级，一个是上下文优先级（未必是当前 Token 的优先级），来自于 Parse 函数的实参。一个是下一个 Token 的优先级，通过往后 peek 得到。
我们 Parse 好前缀表达式，然后重点来了。如果下一个 Token 的优先级大于上下文优先级，那么我们就把它当作中/后缀表达式的一部分，继续 Parse。否则，我们就把前缀表达式返回。

举个例子。结合下面的核心代码理解：

 1    parse(prec: number = 0): ExprNode {
 2        let token = this.tokens.next()!
 3        let prefixParser: PrefixFn = this.parsers.prefix[token.type]
 4        if (!prefixParser) {
 5            throw new Error(`Unexpected prefix token ${token.type}`)
 6        }
 7        let lhs: ExprNode = prefixParser(token)
 8        let precRight = this.precOf(this.tokens.peek()!.value)
 9
10
11        while (prec < precRight) {
12            token = this.tokens.next()!
13            let infixParser: InfixFn | PostfixFn = this.parsers.infix[token.type] || this.parsers.postfix[token.type]
14            if (!infixParser) {
15                throw new Error(`Unexpected infix or postfix token ${token.value}`)
16            }
17            lhs = infixParser(lhs, token)
18            precRight = this.precOf(this.tokens.peek()!.value)
19        }
20
21        return lhs
22    }

初始状态，

当前上下文优先级是 0，后面的 Token 流是 + 1 - 2 * 3，那么我们利用 Prefix + 的 Parser 先得到 (+1)。然后看到 - 的优先级相同，于是直接返回 LHS 即 + 1 的 AST Node。
此时上下文优先级是 0，后面的 Token 流是 - 2 * 3，我们发现 - 的优先级 10 高于 0. 因此吃掉 -，然后我们调用 Infix - 的 Parser
- 此时上下文优先级是 10，后面的 Token 流是 2 * 3，我们先把 2 作为 prefix，调用其 PrefixParser，得到一个 ValueNode(2)
  - 然后我们 peek 到 *，发现 * 的优先级 20 高于 10. 因此吃掉 *，然后我们调用 Infix * 的 Parser
    - InfixParser 调用 Parse
      - 此时上下文优先级是 20，后面的 Token 流是 3，将其作为 Prefix 吃掉。后面我们发现 Eoi 的优先级 0 低于 20. 因此我们直接返回 3 的 AST Node。
    - InfixParser 得到 3 作为 RHS。结合通过实参得到的 2 作为 LHS，得到一个 InfixOpNode(2 * 3)。
- 然后我们从 - 的 InfixParser 返回，通过 LHS=(+1) 和 RHS=(2 * 3) 得到一个 InfixOpNode((+1) - (2 * 3))
最后由于不再有 Token，我们直接返回。

我们的 Prefix/Infix/PostfixParser 定义如下：

 1    public parsers = {
 2        prefix: {
 3            [TokenType.Num]: (token: Token) => {
 4                return new ValueNode(parseInt(token.value))
 5            },
 6            [TokenType.Add]: (token: Token) => {
 7                return new PrefixOpNode('+', this.parse(this.precOf('+')))
 8            },
 9            [TokenType.Sub]: (token: Token) => {
10                return new PrefixOpNode('-', this.parse(this.precOf('-')))
11            },
12            [TokenType.LPa]: (token: Token) => {
13                const expr = this.parse(0)
14                const next = this.tokens.next()!
15                if (next.type !== TokenType.RPa) {
16                    throw new Error('Expected )')
17                }
18                return expr
19            },
20        } as { [k: number]: PrefixFn },
21        infix: {
22            [TokenType.Add]: (lhs: ExprNode, token: Token) => {
23                return new InfixOpNode('+', lhs, this.parse(this.precOf('+')))
24            },
25            [TokenType.Sub]: (lhs: ExprNode, token: Token) => {
26                return new InfixOpNode('-', lhs, this.parse(this.precOf('-')))
27            },
28            [TokenType.Mul]: (lhs: ExprNode, token: Token) => {
29                return new InfixOpNode('*', lhs, this.parse(this.precOf('*')))
30            },
31            [TokenType.Div]: (lhs: ExprNode, token: Token) => {
32                return new InfixOpNode('/', lhs, this.parse(this.precOf('/')))
33            },
34            [TokenType.Pow]: (lhs: ExprNode, token: Token) => {
35                return new InfixOpNode('^', lhs, this.parse(this.precOf('^') - 1)) // Right associative
36            },
37        } as { [k: number]: InfixFn },
38        postfix: {
39            [TokenType.Fac]: (lhs: ExprNode, token: Token) => {
40                return new PostfixOpNode('!', lhs)
41            }
42        } as { [k: number]: PostfixFn }
43    }

步骤解析

上面的小例子只是为了快速理解。实际上我们还会遇到其它问题：

后缀的情况
优先级相同的情况
左结合和右结合的情况

所以给出一个更综合性的例子。

1- 1 + (2 - 3) * 6 / 3 ! - 2 ^ 3 ^ 4

首先，我们读入 Token -，它是一个前缀操作符。因此找到它的 PrefixParser。

1- 1 + (2 - 3) * 6 / 3 ! - 2 ^ 3 ^ 4
2^

1[TokenType.Sub]: (token: Token) => {
2    return new PrefixOpNode('-', this.parse(this.precOf('-')))
3},

我们以 - 的优先级为基准继续解析。即 this.parse(this.precOf('-'))

于是我们读入 Token 1，它是一个数字。因此找到它的 PrefixParser。

1- 1 + (2 - 3) * 6 / 3 ! - 2 ^ 3 ^ 4
2  ^

1[TokenType.Num]: (token: Token) => {
2    return new ValueNode(parseInt(token.value))
3},

得到一个 ValueNode(1)，然后继续解析。我们 peek 到下一个 Token +。由于 - 的优先级比 + 高，所以我们继续解析。

1- 1 + (2 - 3) * 6 / 3 ! - 2 ^ 3 ^ 4
2    ^

然后我们发现右边是 Token (，它没有优先级（或者说，优先级为 0）。因此我们不会进入 while 循环，而是直接返回。返回两层之后，我们得到 PrefixOpNode('-', ValueNode(1))。

此时当前 prec 为 0，当前 Token 为 -。我们可以 peek 到 Token +。由于 + 的优先级比 0 大，因此我们进入 while 循环。然后得到 + 的 InfixParser。

1- 1 + (2 - 3) * 6 / 3 ! - 2 ^ 3 ^ 4
2^   ^
3    peek

于是我们以 + 的优先级为基准继续解析。即 this.parse(this.precOf('+'))。

此时在 while 循环外读取到的 prefix 为 (，因此采用 ( 的 PrefixParser。

1[TokenType.LPa]: (token: Token) => {
2    const expr = this.parse(0)
3    const next = this.tokens.next()!
4    if (next.type !== TokenType.RPa) {
5        throw new Error('Expected )')
6    }
7    return expr
8},

在 ( 中，实际上是把括号中的表达式当做一个全新的表达式处理。可以看到优先级归零（上面代码的第二行）。

我们会对内部的表达式进行解析，得到子表达式 InfixOpNode('-', ValueNode(2), ValueNode(3))。

那么右括号是如何处理的呢？实际上在 parse 函数中，由于右括号的优先级为 0，因此会直接返回。从而在上面的 LPa 的 PrefixParser 中，我们会吞掉右括号。然后继续解析。

于是优先级随着函数返回恢复到 + 的优先级。然后继续解析。

1- 1 + (2 - 3) * 6 / 3 ! - 2 ^ 3 ^ 4
2              ^

由于 * 的优先级比 + 高，我们会调用到 * 的 InfixParser。如此解析完 6 / 3! 这个右子表达式。

值得一提的是，实际上 InfixParser 和 PostfixParser 是等价的。因为 Postfix 只是 Infix 的一个特例。你可以对比如下两个子 Parser：

1[TokenType.Mul]: (lhs: ExprNode, token: Token) => {
2    return new InfixOpNode('*', lhs, this.parse(this.precOf('*')))
3},
4[TokenType.Fac]: (lhs: ExprNode, token: Token) => {
5    return new PostfixOpNode('!', lhs)
6}

可以发现，它们的实现是完全一样的。唯一的区别是，InfixParser 会继续解析右子表达式，而 PostfixParser 不会。

最后我们看一下结合性的处理。由于 + * 等运算都是左结合的，不需要特殊处理。而 ^ 是右结合的，例如说 2 ^ 3 ^ 4，应当解析为 2 ^ (3 ^ 4)。因此我们需要在 InfixParser 中进行特殊处理。

1[TokenType.Pow]: (lhs: ExprNode, token: Token) => {
2    return new InfixOpNode('^', lhs, this.parse(this.precOf('^') - 1)) // Right associati
3},

为什么把优先级减一呢？这样操作是让左边的 ^ 优先级更高，从而右边的 3 ^ 4 会解析为一个子表达式。

最后，我们得到的 AST 如下：

 1InfixOpNode {
 2  op: '-',
 3  lhs: InfixOpNode {
 4    op: '+',
 5    lhs: PrefixOpNode { op: '-', rhs: ValueNode { val: 1 } },
 6    rhs: InfixOpNode {
 7      op: '/',
 8      lhs: InfixOpNode {
 9        op: '*',
10        lhs: InfixOpNode {
11          op: '-',
12          lhs: ValueNode { val: 2 },
13          rhs: ValueNode { val: 3 }
14        },
15        rhs: ValueNode { val: 6 }
16      },
17      rhs: PostfixOpNode { op: '!', lhs: ValueNode { val: 3 } }
18    }
19  },
20  rhs: InfixOpNode {
21    op: '^',
22    lhs: ValueNode { val: 2 },
23    rhs: InfixOpNode {
24      op: '^',
25      lhs: ValueNode { val: 3 },
26      rhs: ValueNode { val: 4 }
27    }
28  }
29}

对应的括号表达式为：

(((-1)+(((2-3)*6)/(3!)))-(2^(3^4)))

完整代码

下面是完整的代码：

  1/**
  2 * Author: Zijing Zhang (Pluveto)
  3 * Date: 2023-01-11 15:28:00
  4 * Description: A Pratt Parser implemented in TypeScript.
  5 */
  6const util = require('util')
  7
  8type InfixOp = '+' | '-' | '*' | '/' | '^'
  9type PrefixOp = '-' | '+'
 10type PostfixOp = '!'
 11
 12class ExprNode {
 13    toString(): string {
 14        throw new Error('not implemented')
 15    }
 16}
 17
 18class ValueNode extends ExprNode {
 19    constructor(public val: number) {
 20        super()
 21    }
 22    toString() {
 23        return this.val.toString()
 24    }
 25}
 26
 27class PrefixOpNode extends ExprNode {
 28    constructor(public op: PrefixOp, public rhs: ExprNode) {
 29        super()
 30    }
 31    toString() {
 32        return `(${this.op}${this.rhs})`
 33    }
 34}
 35class InfixOpNode extends ExprNode {
 36    constructor(public op: InfixOp, public lhs: ExprNode, public rhs: ExprNode) {
 37        super()
 38    }
 39    toString() {
 40        return `(${this.lhs}${this.op}${this.rhs})`
 41    }
 42}
 43class PostfixOpNode extends ExprNode {
 44    constructor(public op: PostfixOp, public lhs: ExprNode) {
 45        super()
 46    }
 47    toString() {
 48        return `(${this.lhs}${this.op})`
 49    }
 50}
 51
 52class Iterator<T> {
 53    private pos: number
 54    constructor(private inner: Array<T> = []) {
 55        this.pos = 0
 56    }
 57    next(): T | undefined {
 58        var peek = this.peek()
 59        this.pos++
 60        return peek
 61    }
 62    peek(): T | undefined {
 63        return this.inner[this.pos] || undefined
 64    }
 65}
 66
 67
 68enum TokenType { None, Num, Add, Sub, Mul, Div, Fac, Pow, LPa, RPa, Eoi }
 69
 70class Token {
 71    constructor(public type: TokenType = TokenType.None, public value: string = '') { }
 72}
 73
 74type PrefixFn = (token: Token) => ExprNode
 75type InfixFn = (lhs: ExprNode, token: Token) => ExprNode
 76type PostfixFn = (lhs: ExprNode, token: Token) => ExprNode
 77
 78class Parser {
 79    constructor(public tokens: Iterator<Token>) { }
 80    public parsers = {
 81        prefix: {
 82            [TokenType.Num]: (token: Token) => {
 83                return new ValueNode(parseInt(token.value))
 84            },
 85            [TokenType.Add]: (token: Token) => {
 86                return new PrefixOpNode('+', this.parse(this.precOf('+')))
 87            },
 88            [TokenType.Sub]: (token: Token) => {
 89                return new PrefixOpNode('-', this.parse(this.precOf('-')))
 90            },
 91            [TokenType.LPa]: (token: Token) => {
 92                const expr = this.parse(0)
 93                const next = this.tokens.next()!
 94                if (next.type !== TokenType.RPa) {
 95                    throw new Error('Expected )')
 96                }
 97                return expr
 98            },
 99        } as { [k: number]: PrefixFn },
100        infix: {
101            [TokenType.Add]: (lhs: ExprNode, token: Token) => {
102                return new InfixOpNode('+', lhs, this.parse(this.precOf('+')))
103            },
104            [TokenType.Sub]: (lhs: ExprNode, token: Token) => {
105                return new InfixOpNode('-', lhs, this.parse(this.precOf('-')))
106            },
107            [TokenType.Mul]: (lhs: ExprNode, token: Token) => {
108                return new InfixOpNode('*', lhs, this.parse(this.precOf('*')))
109            },
110            [TokenType.Div]: (lhs: ExprNode, token: Token) => {
111                return new InfixOpNode('/', lhs, this.parse(this.precOf('/')))
112            },
113            [TokenType.Pow]: (lhs: ExprNode, token: Token) => {
114                return new InfixOpNode('^', lhs, this.parse(this.precOf('^') - 1)) // Right associative
115            },
116        } as { [k: number]: InfixFn },
117        postfix: {
118            [TokenType.Fac]: (lhs: ExprNode, token: Token) => {
119                return new PostfixOpNode('!', lhs)
120            }
121        } as { [k: number]: PostfixFn }
122    }
123    precOf(token: string): number {
124        const precs = {
125            '+': 10,
126            '-': 10,
127            '*': 20,
128            '/': 20,
129            '^': 30,
130            '!': 40,
131        } as Record<string, number>
132
133        return precs[token] || 0
134    }
135    parse(prec: number = 0): ExprNode {
136        let token = this.tokens.next()!
137        let prefixParser: PrefixFn = this.parsers.prefix[token.type]
138        if (!prefixParser) {
139            throw new Error(`Unexpected prefix token ${token.type}`)
140        }
141        let lhs: ExprNode = prefixParser(token)
142        let precRight = this.precOf(this.tokens.peek()!.value)
143
144
145        while (prec < precRight) {
146            token = this.tokens.next()!
147            let infixParser: InfixFn | PostfixFn = this.parsers.infix[token.type] || this.parsers.postfix[token.type]
148            if (!infixParser) {
149                throw new Error(`Unexpected infix or postfix token ${token.value}`)
150            }
151            lhs = infixParser(lhs, token)
152            precRight = this.precOf(this.tokens.peek()!.value)
153        }
154
155        return lhs
156    }
157}
158
159
160let tokens = new Iterator<Token>([
161    // - 1 + (2 - 3) * 6 / 3 ! - 2 ^ 3 ^ 4
162    new Token(TokenType.Sub, '-'),
163    new Token(TokenType.Num, '1'),
164    new Token(TokenType.Add, '+'),
165    new Token(TokenType.LPa, '('),
166    new Token(TokenType.Num, '2'),
167    new Token(TokenType.Sub, '-'),
168    new Token(TokenType.Num, '3'),
169    new Token(TokenType.RPa, ')'),
170    new Token(TokenType.Mul, '*'),
171    new Token(TokenType.Num, '6'),
172    new Token(TokenType.Div, '/'),
173    new Token(TokenType.Num, '3'),
174    new Token(TokenType.Fac, '!'),
175    new Token(TokenType.Sub, '-'),
176    new Token(TokenType.Num, '2'),
177    new Token(TokenType.Pow, '^'),
178    new Token(TokenType.Num, '3'),
179    new Token(TokenType.Pow, '^'),
180    new Token(TokenType.Num, '4'),
181    new Token(TokenType.Eoi),
182])
183
184let parser = new Parser(tokens)
185let ast = parser.parse()
186
187console.log(util.inspect(ast, { showHidden: false, depth: null, colors: true }))
188console.log("Equivalent expression: ", ast.toString());

参考资料

https://www.youtube.com/watch?v=Nlqv6NtBXcA&t=1171s