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 的方式非常相似！
Pratt Parsing 解决什么问题写一个 parser，最困难的地方可能就是解析表达式了，不同于其他语法结构，表达式涉及运算符优先级问题，并且在定义上也是递归的。
比如这样一个表达式：
11 + 2 * 3 乘法运算的优先级应该更高，所以 parser 在得到 1+2 的输入时，并不能直接构造一个算术表达式返回，我们希望的返回是 1+(2*3) 而不是 (1+2)*3。
另外，一般语言中都支持分组，来自定义运算顺序：
13 * (1 + 2)即使乘法的优先级最高，parser 在读入 3 之后也不能从分组中把 1 抢过来构造(31)+2，正确的返回应该是 3*(1+2)
再复杂一点，函数调用也可以参与表达式运算：
15 * (add(2,3) + 1)函数的参数也可以是更复杂的表达式，函数也可以嵌套：
1add(3 * (1 + 2), add(1,2)) * 100 很明显表达式的定义是递归的，对于上面所有 case，给出表达式的定义：
12345678910expr: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。
一个算符既可以是前缀算符，也可以是中缀算符，如何定义取决于它们在表达式中所处的位置。在定义过算符之后，最重要的事情是定义算符优先级：
123456789// 优先级从低到高排列 const (_ int = iotaLOWEST // 最低的 SUM // + -PRODUCT // * /PREFIX // -1CALL // 函数调用，最高)可以发现并没有关于分组的优先级，稍后会看到分组在解析过程中是如何巧妙处理的。
主流程先给出解析表达式的入口方法（下文都省略词法分析器）：
123456789101112131415161718192021// 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()
}解析开始时，传入的优先级参数一定是 LOWEST，第一个遇到的算符一定是前缀算符。
去预定好的 map 中查找该算符作为前缀算符的关联函数，就是代码中的 prefix，在 prefix 函数中构建子表达式(prefix 中可能会递归调用 parseExpr 函数)。
得到 prefix 返回的子表达式后，窥探下一个算符的优先级。
如果下个算符优先级更高，就在 map 中查找该算符作为中缀算符的关联函数 infix
如果没有说明这不是一个中缀算符，把当前构造好的 leftExpr 返回。
如果有，就读入这个算符，调用 infix 函数构造中缀表达式(infix 同样可能递归调用 parseExpr)。
函数返回
算符关联函数的签名如下：
12type prefixParseFn func() ast.Exprtype infixParseFn func(ast.Expr) ast.Expr 各算符作为前缀、中缀算符的关联函数如下：
1234567891011121314151617181920// 前缀算符关联函数 p.prefixParseFns = make(map[token.Type]prefixParseFn)// 标识符：变量名、函数名 p.registerPrefix(token.IDENT, p.parseIdentifier)// 整数字面量：5、10p.registerPrefix(token.INT, p.parseIntLiteral)// 负号：-5p.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 在解析过程中的原则是尽可能不要推进当前算符)。
前缀算符关联函数标识符 1234567func (p *Parser) parseIdentifier() ast.Expr {// 注意这里不调用 nextToken, 这很重要 return &ast.Identifier{Token: p.curToken,Value: p.curToken.Literal,}}很简单，就直接把单个 token 构造成 AST 上的 Identifier 节点返回。
整型字面量 123456789101112// int 作为 prefix 的关联函数 func (p *Parser) parseIntLiteral() ast.Expr {lit := &ast.Int_Literal{Token: p.curToken}
}也很简单，就是把源码中的字符串转换为 int 并构造节点。
负号 1234567891011func (p Parser) parsePrefixExpression() ast.Expr {expression := &ast.PrefixExpression{Token: p.curToken,Operator: p.curToken.Literal,}p.nextToken()// 注意这里，是 pratt parsing 的关键// 传入优先级为 PREFIX, -35 , -add(1,2) 只有 CALL 大于此优先级 expression.Right = p.parseExpr(PREFIX)return expression}这里开始递归了，直接递归调用 parseExpr(注意传入优先级参数是 PREFIX)得到负号后面跟的子表达式。PREFIX 优先级很大，仅次于 CALL:
12-3*5 => (-3)*5-add(1,2) => -(add(1,2))分组 12345678func (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，如果下个字符不是)就说明输入语法错误。
后缀算符关联函数算术运算 1234567891011121314// 中缀算符的关联函数 + - * /func (p *Parser) parseInfixExpr(left ast.Expr) ast.Expr {expr := &ast.Infix_Expr{Token: p.curToken,Left: left,Operator: p.curToken.Literal,}
}最终构造的节点有三部分：left、op、right，读取当前算符的优先级(SUM/PRODUCT)，传入 parseExpr 解析得到 right 部分，构造结束。
函数调用 123456789101112131415161718192021222324252627func (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{}
}主要是解析参数列表，有多个参数情况下，都是逗号分割，直接循环处理，每次递归调用 parseExpr 传入的优先级都是 LOWEST，因为每个参数都是独立的 expr。
总结整个算法的核心思想是使用优先级，来控制当前应该返回已构造的 expr，还是继续解析。再贴一遍主流程：
1234567891011121314151617181920func (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()
}用一个例子来演示下整个执行流程：
假设要解析 1 + 2 * 5
id 剩余算符 当前算符 执行操作 说明 局部 AST 构造 stack0 1+25 parseExpr(LOWEST) 开始解析，传入最低优先级 1 +25 1 parserIntLiteral() 从映射中找到当前算符的 prefix 关联函数，执行后得到 ast 节点 12 25 + parseInfixExpr(left) 窥探得知+的算符优先级 SUM 大于 LOWEST，执行+的关联函数 1+3 25 + parseExpr(SUM) 在 2 中递归调用了解析，并且传入优先级为 SUM 4 5 2 parserIntLiteral() 解析函数发现算符还是整数，继续调用关联函数 25 5 * parseInfixExpr(left) 发现的优先级 PRODUCT 大于当前优先级 SUM，调用的关联函数 26 5 * parseExpr(PRODUCT) 在 5 中递归调用解析，并传入优先级为 PRODUCT 7 5 parserIntLiteral 算符还是整数，继续调用关联函数 58 7->6 输入结束，7 返回到 6，并得到 ast {5}9 6->3 6 返回到 3，并得到 ast {2*{5}}10 3->0 6 返回到 0，并得到 ast {1+{2*{5}}}
版权声明: 本文为 InfoQ 作者【乌龟哥哥】的原创文章。
原文链接:【http://xie.infoq.cn/article/2cb7367d7e6e40cba82224352】。文章转载请联系作者。
正在努力寻找offer的大四小菜鸟 2021-03-16 加入
擅长 Hbuilder、VS Code、MyEclipse、AppServ、PS 等软件的安装与卸载 精通 Html、CSS、JavaScript、jQuery、Java 等单词的拼写 熟悉 Windows、Linux、 等系统的开关机 看–时间过得多快，不说了，去搬砖了
评论