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}}} |
基本上是对简介中那本书中实现内容的裁剪,强烈建议读一读。