Pratt Parsing - 自顶向下的算符优先级

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,最困难的地方可能就是解析表达式了,不同于其他语法结构,表达式涉及运算符优先级问题,并且在定义上也是递归的。

比如这样一个表达式:

1
1 + 2 * 3

乘法运算的优先级应该更高,所以parser在得到1+2的输入时,并不能直接构造一个算术表达式返回,我们希望的返回是 1+(2*3) 而不是 (1+2)*3

另外,一般语言中都支持分组,来自定义运算顺序:

1
3 * (1 + 2)

即使乘法的优先级最高,parser在读入3*之后也不能从分组中把1抢过来构造(3*1)+2,正确的返回应该是3*(1+2)

再复杂一点,函数调用也可以参与表达式运算:

1
5 * (add(2,3) + 1)

函数的参数也可以是更复杂的表达式,函数也可以嵌套:

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 的基本思想是:为每一个算符定义一个优先级。算符会被分为两类,一类称为前缀prefix算符,另一类称为中缀infix算符。-5中的负号就是一个前缀算符,特别的是一个字面量或标识符也被划分为一个前缀算符,如5add,因为他们都是一元的;像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
}
  1. 解析开始时,传入的优先级参数一定是LOWEST,第一个遇到的算符一定是前缀算符。

  2. 去预定好的map中查找该算符作为前缀算符的关联函数,就是代码中的prefix,在prefix函数中构建子表达式(prefix中可能会递归调用parseExpr函数)。

  3. 得到prefix返回的子表达式后,窥探下一个算符的优先级。

  4. 如果下个算符优先级更高,就在map中查找该算符作为中缀算符的关联函数infix

  5. 如果没有说明这不是一个中缀算符,把当前构造好的leftExpr返回。

  6. 如果有,就读入这个算符,调用infix函数构造中缀表达式(infix同样可能递归调用parseExpr)。

  7. 函数返回

算符关联函数的签名如下:

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}}}

基本上是对简介中那本书中实现内容的裁剪,强烈建议读一读。