Pratt Parsing 是一种在手写递归下降解析器时处理表达式解析的好方法，通过给算符定义优先级，可以处理左递归的语法定义，写起来非常简单。
我学到这个方法是在这本书里：《Writing An Interpreter In Go》，作者用手写递归下降的方式实现了一个名为 Monky 的语言，其中解析表达式的部分就是用 Pratt Parsing 实现的。
整一个解析器无非就两种方法：手写、使用parser generator工具生成。
如果选择手写，那肯定是采用自顶向下的方式。
选择生成器，也有两个流派：自顶向下、自底向上。比如：
- 自顶向下：ANTLR - ALL(*)
- 自底向上：Yacc/Bison - LALR
我更喜欢年轻的ANTLR，甚至都没用过Yacc/Bison，自顶向下的方式更符合人类思维，而LALR算法生成的代码很难懂(不光生成的代码难懂，算法思想本身也难懂)。还有就是手写递归下降很流行，Go的编译器就是这么干的。
自顶向下的方式缺点是无法处理左递归，但ANTLR允许定义直接左递归，它会帮你自动改写。在《ANTRL4权威指南》14章 移除直接左递归中提到了左递归规则转换的方法，和Pratt Parsing 的方式非常相似！
写一个parser，最困难的地方可能就是解析表达式了，不同于其他语法结构，表达式涉及运算符优先级问题，并且在定义上也是递归的。
比如这样一个表达式：
乘法运算的优先级应该更高，所以parser在得到1+2的输入时，并不能直接构造一个算术表达式返回，我们希望的返回是 1+(2*3) 而不是 (1+2)*3。
另外，一般语言中都支持分组，来自定义运算顺序：
即使乘法的优先级最高，parser在读入3*之后也不能从分组中把1抢过来构造(3*1)+2，正确的返回应该是3*(1+2)
再复杂一点，函数调用也可以参与表达式运算：
函数的参数也可以是更复杂的表达式，函数也可以嵌套：
1
|
add(3 * (1 + 2), add(1,2)) * 100
|
很明显表达式的定义是递归的，对于上面所有case，给出表达式的定义：
1
2
3
4
5
6
7
8
9
10
|
expr:
expr ('+'|'-'|'*'|'/') expr
| ('-') expr
| '(' expr ')'
| literal;
literal:
IDENTIFIER // 标识别符
| integer // 整数字面量
| '(' ( expr (',' expr)* )? ')'; //参数列表
|
如何在手写递归下降解释器中，正确解析这样一个表达式，就是Pratt Parsing所解决的问题。
Pratt Parsing 的基本思想是：为每一个算符定义一个优先级。算符会被分为两类，一类称为前缀算符，另一类称为中缀算符。-5中的负号就是一个前缀算符，特别的是一个字面量或标识符也被划分为一个前缀算符，如5、add，因为他们都是一元的；像1+2中的加号是中缀算符，同样比较特别的是函数调用add(1,2)，函数名后面的(也被归类为中缀算符，因为函数名必须要与参数列表结合。前缀算符和后缀算符都会有关联函数，关联函数负责构造具体的子表达式，过程中会递归的调用主解析函数。通过算符优先级，来决定如何构造AST。
一个算符既可以是前缀算符，也可以是中缀算符，如何定义取决于它们在表达式中所处的位置。在定义过算符之后，最重要的事情是定义算符优先级：
1
2
3
4
5
6
7
8
9
|
// 优先级从低到高排列
const (
_ int = iota
LOWEST // 最低的
SUM // + -
PRODUCT // * /
PREFIX // -1
CALL // 函数调用，最高
)
|
可以发现并没有关于分组的优先级，稍后会看到分组在解析过程中是如何巧妙处理的。
先给出解析表达式的入口方法（下文都省略词法分析器）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
// pratt parsing 的主要逻辑
func (p *Parser) parseExpr(precedence int) ast.Expr {
prefix := p.prefixParseFns[p.curToken.Type]
if prefix == nil {
p.noPrefixParseFnError(p.curToken.Type)
return nil
}
leftExpr := prefix()
// 如果外部算符优先级没有后面遇到的的高，会循环下去
for !p.peekTokenIs(token.SEMICOLON) && precedence < p.peekPrecedence() {
infix := p.infixParseFns[p.peek_Tok.Type]
if infix == nil {
return leftExpr
}
p.nextToken()
leftExpr = infix(leftExpr) // 合并中缀表达式
}
return leftExpr
}
|
-
解析开始时，传入的优先级参数一定是LOWEST，第一个遇到的算符一定是前缀算符。
-
去预定好的map中查找该算符作为前缀算符的关联函数，就是代码中的prefix，在prefix函数中构建子表达式(prefix中可能会递归调用parseExpr函数)。
-
得到prefix返回的子表达式后，窥探下一个算符的优先级。
-
如果下个算符优先级更高，就在map中查找该算符作为中缀算符的关联函数infix
-
如果没有说明这不是一个中缀算符，把当前构造好的leftExpr返回。
-
如果有，就读入这个算符，调用infix函数构造中缀表达式(infix同样可能递归调用parseExpr)。
-
函数返回
算符关联函数的签名如下：
1
2
|
type prefixParseFn func() ast.Expr
type infixParseFn func(ast.Expr) ast.Expr
|
各算符作为前缀、中缀算符的关联函数如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
// 前缀算符关联函数
p.prefixParseFns = make(map[token.Type]prefixParseFn)
// 标识符：变量名、函数名
p.registerPrefix(token.IDENT, p.parseIdentifier)
// 整数字面量：5、10
p.registerPrefix(token.INT, p.parseIntLiteral)
// 负号：-5
p.registerPrefix(token.MINUS, p.parsePrefixExpression)
// 分组(左括号)：3*(1+2)
p.registerPrefix(token.LPAREN, p.parseGroupExpr)
// 中缀算符关联函数
p.infixParseFns = make(map[token.Type]infixParseFn)
// 二元算术运算：+ - * /
p.registerInfix(token.PLUS, p.parseInfixExpr)
p.registerInfix(token.MINUS, p.parseInfixExpr)
p.registerInfix(token.ASTERISK, p.parseInfixExpr)
p.registerInfix(token.SLASH, p.parseInfixExpr)
// 函数调用(左括号)： add(1,2)
p.registerInfix(token.LPAREN, p.parseCallExpr)
|
然后看下各算符关联函数的实现(parser在解析过程中的原则是尽可能不要推进当前算符)。
1
2
3
4
5
6
7
|
func (p *Parser) parseIdentifier() ast.Expr {
// 注意这里不调用 nextToken, 这很重要
return &ast.Identifier{
Token: p.curToken,
Value: p.curToken.Literal,
}
}
|
很简单，就直接把单个token构造成AST上的Identifier节点返回。
1
2
3
4
5
6
7
8
9
10
11
12
|
// int 作为prefix的关联函数
func (p *Parser) parseIntLiteral() ast.Expr {
lit := &ast.Int_Literal{Token: p.curToken}
v, err := strconv.ParseInt(p.curToken.Literal, 0, 64)
if err != nil {
p.errs = append(p.errs, fmt.Sprintf("无法将%s转换为int", p.curToken.Literal))
return nil
}
lit.Value = v
return lit
}
|
也很简单，就是把源码中的字符串转换为int并构造节点。
1
2
3
4
5
6
7
8
9
10
11
|
func (p *Parser) parsePrefixExpression() ast.Expr {
expression := &ast.PrefixExpression{
Token: p.curToken,
Operator: p.curToken.Literal,
}
p.nextToken()
// 注意这里，是pratt parsing的关键
// 传入优先级为 PREFIX, -3*5 , -add(1,2) 只有CALL大于此优先级
expression.Right = p.parseExpr(PREFIX)
return expression
}
|
这里开始递归了，直接递归调用parseExpr(注意传入优先级参数是PREFIX)得到负号后面跟的子表达式。PREFIX优先级很大，仅次于CALL:
1
2
|
-3*5 => (-3)*5
-add(1,2) => -(add(1,2))
|
1
2
3
4
5
6
7
8
|
func (p *Parser) parseGroupExpr() ast.Expr {
p.nextToken()
exp := p.parseExpr(LOWEST)
if !p.expectPeek(token.RPAREN) { // 吃掉 )
return nil
}
return exp
}
|
分组的实现很简单，也很奇妙。读入(后，直接把优先级降到LOWEST，这样相当于屏蔽了前面的优先级，不管前面优先级多高，后面都看不见，思考：3*(1+2)。结束后读出)到curToken，如果下个字符不是)就说明输入语法错误。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// 中缀算符的关联函数 + - * /
func (p *Parser) parseInfixExpr(left ast.Expr) ast.Expr {
expr := &ast.Infix_Expr{
Token: p.curToken,
Left: left,
Operator: p.curToken.Literal,
}
precedence := p.curPrecedence()
p.nextToken()
expr.Right = p.parseExpr(precedence)
return expr
}
|
最终构造的节点有三部分：left、op、right，读取当前算符的优先级(SUM/PRODUCT)，传入parseExpr解析得到right部分，构造结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
func (p *Parser) parseCallExpr(fn ast.Expr) ast.Expr {
exp := &ast.Call_Expr{Token: p.curToken, Function: fn}
exp.Arguments = p.parseCallArgs()
return exp
}
func (p *Parser) parseCallArgs() []ast.Expr {
args := []ast.Expr{}
// 没有参数的情况
if p.peekTokenIs(token.RPAREN) {
p.nextToken()
return args
}
// 解析参数
p.nextToken()
args = append(args, p.parseExpr(LOWEST))
for p.peekTokenIs(token.COMMA) {
p.nextToken()
p.nextToken()
args = append(args, p.parseExpr(LOWEST))
}
if !p.expectPeek(token.RPAREN) {
return nil
}
return args
}
|
主要是解析参数列表，有多个参数情况下，都是逗号分割，直接循环处理，每次递归调用parseExpr传入的优先级都是LOWEST，因为每个参数都是独立的expr。
整个算法的核心思想是使用优先级，来控制当前应该返回已构造的expr，还是继续解析。再贴一遍主流程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
func (p *Parser) parseExpr(precedence int) ast.Expr {
prefix := p.prefixParseFns[p.curToken.Type]
if prefix == nil {
p.noPrefixParseFnError(p.curToken.Type)
return nil
}
leftExpr := prefix()
// 如果当前算符优先级没有后面的高，会循环下去
for !p.peekTokenIs(token.SEMICOLON) && precedence < p.peekPrecedence() {
infix := p.infixParseFns[p.peek_Tok.Type]
if infix == nil {
return leftExpr
}
p.nextToken()
leftExpr = infix(leftExpr) // 合并中缀表达式
}
return leftExpr
}
|
用一个例子来演示下整个执行流程：
假设要解析1 + 2 * 5
| id |
剩余算符 |
当前算符 |
执行操作 |
说明 |
局部AST构造stack |
| 0 |
1+2*5 |
|
parseExpr(LOWEST) |
开始解析，传入最低优先级 |
|
| 1 |
+2*5 |
1 |
parserIntLiteral() |
从映射中找到当前算符的prefix关联函数，执行后得到ast节点 |
1 |
| 2 |
2*5 |
+ |
parseInfixExpr(left) |
窥探得知+的算符优先级SUM大于LOWEST，执行+的关联函数 |
1+ |
| 3 |
2*5 |
+ |
parseExpr(SUM) |
在2中递归调用了解析，并且传入优先级为SUM |
|
| 4 |
*5 |
2 |
parserIntLiteral() |
解析函数发现算符还是整数，继续调用关联函数 |
2 |
| 5 |
5 |
* |
parseInfixExpr(left) |
发现的优先级PRODUCT大于当前优先级SUM，调用的关联函数 |
2* |
| 6 |
5 |
* |
parseExpr(PRODUCT) |
在5中递归调用解析，并传入优先级为PRODUCT |
|
| 7 |
|
5 |
parserIntLiteral |
算符还是整数，继续调用关联函数 |
5 |
| 8 |
|
|
7->6 |
输入结束，7返回到6，并得到ast |
{5} |
| 9 |
|
|
6->3 |
6返回到3，并得到ast |
{2*{5}} |
| 10 |
|
|
3->0 |
6返回到0，并得到ast |
{1+{2*{5}}} |
基本上是对简介中那本书中实现内容的裁剪，强烈建议读一读。