6

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

 2 years ago
source link: https://www.kirito41dd.cn/pratt-parsing/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

 2021-08-15  约 3333 字   预计阅读 7 分钟 

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 的方式非常相似！

Pratt Parsing 解决什么问题

写一个parser，最困难的地方可能就是解析表达式了，不同于其他语法结构，表达式涉及运算符优先级问题，并且在定义上也是递归的。

比如这样一个表达式：

1 + 2 * 3

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

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

3 * (1 + 2)

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

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

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

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

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

很明显表达式的定义是递归的，对于上面所有case，给出表达式的定义：

expr:
    expr ('+'|'-'|'*'|'/') expr
    | ('-') expr
    | '(' expr ')'
    | literal;

literal:
    IDENTIFIER // 标识别符
    | integer // 整数字面量
    | '(' ( expr (',' expr)* )? ')'; //参数列表

如何在手写递归下降解释器中，正确解析这样一个表达式，就是Pratt Parsing所解决的问题。

Pratt Parsing 的基本思想是：为每一个算符定义一个优先级。算符会被分为两类，一类称为前缀prefix算符，另一类称为中缀infix算符。-5中的负号就是一个前缀算符，特别的是一个字面量或标识符也被划分为一个前缀算符，如5、add，因为他们都是一元的；像1+2中的加号是中缀算符，同样比较特别的是函数调用add(1,2)，函数名后面的(也被归类为中缀算符，因为函数名必须要与参数列表结合。前缀算符和后缀算符都会有关联函数，关联函数负责构造具体的子表达式，过程中会递归的调用主解析函数。通过算符优先级，来决定如何构造AST。

一个算符既可以是前缀算符，也可以是中缀算符，如何定义取决于它们在表达式中所处的位置。在定义过算符之后，最重要的事情是定义算符优先级：

// 优先级从低到高排列
const (
	_           int = iota
	LOWEST          // 最低的
	SUM             // + -
	PRODUCT         // * /
	PREFIX          // -1
	CALL            // 函数调用，最高
)

可以发现并没有关于分组的优先级，稍后会看到分组在解析过程中是如何巧妙处理的。

先给出解析表达式的入口方法（下文都省略词法分析器）：

// 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)。

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

type prefixParseFn func() ast.Expr
type infixParseFn func(ast.Expr) ast.Expr

各算符作为前缀、中缀算符的关联函数如下：

// 前缀算符关联函数
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在解析过程中的原则是尽可能不要推进当前算符)。

前缀算符关联函数

func (p *Parser) parseIdentifier() ast.Expr {
	// 注意这里不调用 nextToken, 这很重要
	return &ast.Identifier{
		Token: p.curToken,
		Value: p.curToken.Literal,
	}
}

很简单，就直接把单个token构造成AST上的Identifier节点返回。

整型字面量

// 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并构造节点。

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:

-3*5 => (-3)*5
-add(1,2) => -(add(1,2))

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)。结束后吃掉)，如果下个字符不是)就说明输入语法错误。

后缀算符关联函数

// 中缀算符的关联函数 + - * /
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部分，构造结束。

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，还是继续解析。再贴一遍主流程：

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

下一篇贴一下完整的代码实现，基本上是对简介中那本书中实现内容的裁剪。

再水一篇(雾


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK