在 LLVM 的官方入门教程 My First Language Frontend with LLVM Tutorial 的第二章构造 AST 时涉及到了对运算符优先级解析的内容，使用的算法为优先级爬升法。尽管教程开篇称“不需要编译原理前置预备知识”，但直接理解代码仍有点吃力，本文为我个人对此方法的理解，难免存在错误，欢迎指正。

算法原理

约定和前置知识

在优先级爬升法中，中缀表达式被分解为主表达式（primary expression）和运算符（operator），例如在表达式 a+b*c-d 中，主表达式为 ['a', 'b', 'c', 'd']，运算符包括 ['+', '*', '-']，每个运算符都有与之对应的优先级和结合性，优先级使用正整数表示相对大小，四则运算中乘除优先级高于加减，均为左结合。在本例中，约定加减的优先级为 10，乘除的为 20。

中缀表达式可以被解析为表达式树，表达式树能够反映出计算的优先级。所谓运算符优先级解析本质上就是要解析出正确的表达式树。

表达式树图源：GeeksforGeeks

本文仅限于对双目运算符进行讨论，即每个运算符接收两个输入参数，输出一个计算结果。

原理

以表达式 a+b*c-d 为例，当我们自左向右扫描到第一个运算符 + 时，由于 b*c 的优先级更高，因此不能直接在表达式树上构造出 a+b，而应该优先构造出 b*c。那优先级高的是不是一定要被优先计算呢？非也，例如表达式 a+b+c*d，即便在计算 c*d 之前优先计算了 a+b，也并不会妨碍我们构造出正确的表达式树。

那当我们扫描到一个运算符时，什么情况可以在表达式树上构造对应节点，什么时候需要先计算优先级更高的节点呢？我们知道，在中缀表达式中，每个主元周围最多有有两个运算符，主元需要与优先级更高的那个运算符进行结合，因此，当我们扫描的运算符时，我们可以先解析出下一个主元，以及下一个运算符，如果当前运算符的优先级高于下一个运算符（或者优先级一致，但是当前运算符是左结合的），那么说明下一个主元是当前运算符的第二个输入参数 rhs，否则说明下一个主元是下一个运算符的第一个输入参数 lhs，需要先将下一个运算符解析完毕，解析结果才是当前运算符的 rhs。

例如，在表达式 a+b*c-d 中，首先扫描到第一个主元 a，将其记录为 rhs；扫描到第一个运算符 +，继续向后扫描到一个主元 b，以及与其邻接的运算符 *，* 的优先级高于 +，因此开辟一个新的函数栈，lhs = b，对 * 进行解析；向后扫描到一个主元 c，以及与其邻接的运算符 -，* 的优先级高于 -，因此 c 是 * 的 rhs，构造出 b*c 并返回该结果；回到解析第一个 + 的函数栈中，其接收到 b*c 作为新的 rhs，并继续扫描下一个运算符 -，+ 的优先级与 - 一致，且 + 是左结合的，因此构造出 a+b*c，并作为新的 lhs；继续扫描到下一个主元 d，并且不存在下一个运算符，则继续构造出 a+b*c-d，并结束解析。

算法伪代码如下所示 ¹：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


parse_expression()
    return parse_expression_1(parse_primary(), 0)

parse_expression_1(lhs, min_precedence)
    _lookahead_ := peek next token
    while _lookahead_ is a binary operator whose precedence is >= _min_precedence_
        _op_ := _lookahead_
        advance to next token
        _rhs_ := _parse_primary_ ()
        _lookahead_ := peek next token
        while _lookahead_ is a binary operator whose precedence is greater
                 than _op_'s, or a right-associative operator
                 whose precedence is equal to _op'_s
            _rhs_ := _parse_expression_1_ (_rhs_, precedence of _op_ + (1 if _lookahead_ precedence is greater, else 0))
            _lookahead_ := peek next token
        _lhs_ := the result of applying _op_ with operands _lhs_ and _rhs_
    return _lhs_

其中 parse_expression_1 是一个递归调用的函数，其接收两个参数 lhs 和 min_precedence，功能是对中缀表达式进行顺序解析，直至碰到优先级低于 min_precedence 返回解析结果。

而在 parse_expression_1 内部，其如果碰到了可以直接计算的情形，即当前运算符的优先级更高，或者相等且为左结合，则将 lhs __0p__ rhs 的结果作为新的 lhs，并进行下一趟外部循环；如果需要先计算下一个右结合，则递归调用自身，并将 min_precedence 参数设置为当前运算符的优先级 +0/1。

+0 是为了正确处理右结合的情况，当下一个运算符与当前运算符优先级相当且右结合时，min_precedence 需要设置为与当前运算符优先级相等的值，以确保递归调用时碰到 1^2^3（右结合运算）时能够继续递归解析，而非像左结合一样直接返回；+1 是为了正确处理左结合的情况，以确保当碰到与当前优先级相同的运算符时其能够及时返回，而不是继续向后解析。

括号处理

上述算法碰到括号就扑街了：一方面，括号不是双目运算符，无法在小修的情况在融入我们的算法；另一方面，括号拥有着最高的优先级，意味着我们需要对其进行特殊处理。好在 LLVM 的 tutorial 中提供了另一种解决思路：括号内的内容本身就是一个表达式，调用 parse_expression() 函数对括号内的内容进行解析即可，并将解析结果当作我们算法中的一个主元即可。

具体实现见下一章。

实现

本章主要讲解 LLVM tutorial 对优先级爬升法的实现，在教程中实现了对 Kaleidoscope 语言的词法和语法分析，该语言支持基本四则运算。在第二章中需要代码解析为抽象语法树 AST，首先介绍几个脚手架，用于进行词法分析。

ParsePrimary 用于解析前文中提到的主表达式，主表达式可能是标识符、数字、括号包围的表达式：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


std::unique_ptr<ExprAST> ParsePrimary(){
    switch (CurTok) {
    default:
        return LogError("Unknown token when expecting an expression");
    case tok_identifier:
        return ParseIdentifierExpr();
    case tok_number:
        return ParseNumberExpr();
    case '(':
        return ParseParenExpr();
    }
}

运算符的优先级使用 map 来记录：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


std::map<char, int> BinopPredence;

int GetTokPrecidence() {
    if(BinopPredence.empty())
        InstallBinopPredence();
    if (!isascii(CurTok)){
        return -1;
    }

    int TokPrec = BinopPredence[CurTok];
    if (TokPrec <= 0)   return -1;
    return TokPrec;
}

void InstallBinopPredence(){
    // 1 is the lowest predence
    BinopPredence['<'] = 10;
    BinopPredence['>'] = 10;
    BinopPredence['+'] = 20;
    BinopPredence['-'] = 20;
    BinopPredence['*'] = 30;
    BinopPredence['/'] = 30;
}

ParseBinOpRHS 即为优先级爬升法的核心实现，对应伪代码中的 parse_expression_1，注意看注释：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec, 
                                        std::unique_ptr<ExprAST> LHS){
    while (true) {
        int TokPrec = GetTokPrecidence();
		// 如果当前Token不是运算符，说明解析结束，TokPrec=-1
        if (TokPrec < ExprPrec)
            return LHS;
        int BinOp = CurTok;
        getNextToken(); // eat BinOp
        auto RHS = ParsePrimary();
        if (!RHS) return nullptr;
        
        int NextPrec = GetTokPrecidence();
        if (TokPrec < NextPrec){
	        // 不考虑右结合
            RHS = ParseBinOpRHS(TokPrec+1, std::move(RHS));
        }
	    // 构造 BinOp 对应的AST
        LHS = std::make_unique<BinaryExprAST>(BinOp, std::move(LHS),
            std::move(RHS));
    }

}

解析表达式的主函数为：

1
2
3
4
5
6


std::unique_ptr<ExprAST> ParseExpression() {
    auto LHS = ParsePrimary();
    if (!LHS)
        return nullptr;
    return ParseBinOpRHS(0, std::move(LHS));
}

参考

Operator-precedence parser - Wikipedia ↩︎

算法原理#

约定和前置知识#

原理#

括号处理#

实现#

参考#

算法原理

约定和前置知识

原理

括号处理

实现

参考