构建一个 Human Resource Machine 编译器 - 语法解析器（1）

(Thanks to Doubao for translating. See original at this page. 感谢豆包的翻译, 原文见此页面。如有差异，请以英文版为准。如果中文使你困惑看不懂，也请读英文版。)

这是Human Resource Machine 编译器系列的一篇文章。

编写一个解析器并不完全直观，这个过程可能会让人感觉有点原始。

为了简单起见，让我们为这个例子设计一种迷你语言，称为“zoo”。

animal    : 'ostrich' | 'pig';
action    : 'eats' | 'smells' | 'takes';
fruit     : 'apple' | 'banana' | 'cherry';
vegetable : 'broccoli' | 'cabbage';
state     : 'fresh' | 'spoiled';
color     : 'green' | 'yellow' | 'pink';
subject   : [color] animal;
object    : [color] fruit | [state] vegetable;
sentence  : subject action object;

一个有效的句子可以是“pig eats green apple”（猪吃青苹果）或“pink ostrich takes spoiled cabbage”（粉色鸵鸟拿烂白菜）。然而，在这种情况下，像“pig eats pig”（猪吃猪）或“pig smells yellow broccoli”（猪闻黄色西兰花）这样的句子是无效的。终结符是“animal”（动物）、“action”（动作）、“fruit”（水果）、“color”（颜色）、“vegetable”（蔬菜）和“state”（状态）。非终结符是“subject”（主语）、“object”（宾语）和“sentence”（句子），其中“sentence”是我们的最高规则。

要构建一个解析器，你可以从自底向上（从终结符开始）或自顶向下（从“sentence”开始）开始。

最简单的自顶向下解析器——“Zoo 语言”

一种自然的方法是从根规则开始，并相应地匹配标记。让我们采取一种直接、对初学者友好的方法。

考虑解析句子“pig eats green apple”（猪吃青苹果）。我们从最高规则“sentence”开始，并向前看一个标记——“pig”。然后我们深入到产生式规则中，直到我们到达一个终结规则。在这里，那将是“subject”，然后是“[color]”。我们尝试将标记与规则匹配，但失败了——“pig”不是一种颜色。由于“color”是可选的，我们回溯并尝试匹配下一个规则，“animal”。这次，我们有了一个匹配！我们将“pig”添加到我们的抽象语法树（AST）中。这个过程重复进行，直到我们要么用完了针对该标记的匹配规则（失败），要么成功地将所有标记与我们的规则匹配。

简化的回溯自顶向下解析器

这看起来熟悉吗？它本质上是一个图搜索问题，特别是针对我们的语法产生空间的深度优先搜索！

这里有一些优化的机会。目前，当在下降过程中匹配失败时，我们回溯。然而，对于像这样的简单语法，我们可以预先计算可能的有效标记（一种称为预测解析的技术）。这些有效标记被称为$\text{FIRST}$集合。例如，“subject”的$\text{FIRST}$集合是“[green, yellow, pink, ostrich, pig]”。在解析过程中，我们可以查找$\text{FIRST}$集合来决定是否进一步下降。如果标记不在$\text{FIRST}$集合中，它表示语法错误。由于“zoo”是一种简单的语言，我们只需要向前看一个标记。更复杂的语言可能需要向前看更多的标记，这会使解析器变得复杂。

在这种类型的解析器中，我们递归地通过产生式规则下降以找到匹配并构建 AST。这种方法被称为“递归下降解析器”。由于我们从左到右解析并推导最左边的产生式，它也被称为“LL”解析器。如果我们使用单个标记的预测解析来实现，我们创建一个“LL(1)”解析器（我们这里的例子还不完全是，因为它使用深度优先搜索并需要回溯）。“LL(1)”解析器也可以使用状态转换表来实现。

还有另一个概念称为$\text{FOLLOW}$集合，它表示可以合法地跟随一个非终结符的标记集合。例如，“subject”的$\text{FOLLOW}$集合是“[eats, smells, takes]”。在像“zoo”这样的简单语法中，这也可以预先计算，尽管我们在当前的例子中不需要它。

我们不会定义一个无意义的$\text{FOLLOW}$集合🤪。一个有用的应用是处理$\epsilon$解析。有时，一个转换后的规则可能会产生一个空字符串，表示为$\epsilon$。我们稍后将讨论这些转换。当$\text{FIRST}$集合包含$\epsilon$时，这意味着当前规则可以接受一个空字符串，所以如果在$\text{FIRST}$中没有匹配，那么可以安全地继续到下一个产生式规则。在这种情况下，我们将向前看的标记与$\text{FOLLOW}$集合进行匹配。

以下是$\text{FIRST}$和$\text{FOLLOW}$表：

符号	FIRST	FOLLOW
action	'eats', 'smells', 'takes'	'apple', 'banana', 'broccoli', 'cherry', 'cabbage', 'fresh', 'green', 'pink', 'spoiled', 'yellow'
animal	'ostrich', 'pig'	'eats', 'smells', 'takes'
color	'green', 'pink', 'yellow'	'apple', 'banana', 'cherry', 'ostrich', 'pig'
fruit	'apple', 'banana', 'cherry'
object	'apple', 'banana', 'broccoli', 'cherry', 'cabbage', 'fresh', 'green', 'pink', 'spoiled', 'yellow'
sentence	'green', 'ostrich', 'pig', 'pink', 'yellow'
state	'fresh', 'spoiled'	'broccoli', 'cabbage'
subject	'green', 'ostrich', 'pig', 'pink', 'yellow'	'eats', 'smells', 'takes'
vegetable	'broccoli', 'cabbage'

通用解析过程

让我们逐步分解解析过程：

1. 开始解析过程：

   • 通过从输入流中读取第一个标记来初始化解析器，并从最高产生式规则开始。

2. 使用可能的起始标记集合进行决策：

   • 对于每个非终结符规则，检查当前标记（向前看），并根据每个产生式规则生成的序列开头可能出现的标记集合（$\text{FIRST}$）来决定应用哪个产生式规则。
   • 在我们前面的例子中，我们没有实现这个；相反，我们深入到产生式规则中，并让它们决定行动的过程。

3. 匹配并消耗标记：

   • 如果当前产生式规则期望一个特定的终结符（标记），将其与当前标记进行比较。
   • 如果它们匹配，消耗该标记并移动到下一个标记。

4. 递归函数调用：

   • 如果产生式规则涉及其他非终结符，递归地调用这些非终结符的相应函数。

5. 处理空产生式：

   • 如果一个非终结符可以产生一个空字符串（$\epsilon$），检查当前标记是否在可以合法地跟随这个非终结符的标记集合（$\text{FOLLOW}$）中，以决定函数是否应该在不消耗任何标记的情况下返回。
   • 我们当前的简单语法不包括$\epsilon$产生式，但我们稍后将更详细地探讨这个概念。

6. 检测语法错误：

   • 如果没有规则适用（即当前标记与任何规则的可能起始标记都不匹配），则引发语法错误。

7. 完成解析：

   • 这个过程递归地继续，直到开始符号的函数完成并且所有标记都被消耗，确认整个输入符合语法。

8. 以文件结束符结束：

   • 确保最后一个标记是文件结束符（EOF），以验证输入已被完全解析。

更复杂的“快乐动物园”

让我们稍微调整一下我们的语法：

animal    : 'ostrich' | 'pig';
fruit     : 'apple' | 'banana' | 'cherry';
happiness : 'happy' | 'joyful' | happiness 'and' happiness;
color     : 'green' | 'yellow' | 'pink';
subject   : [color] happiness animal;
object    : [color] fruit;
sentence  : subject 'feeds on' object | object 'feeds' subject;

这个语法可能会产生一个相当愚蠢的句子，比如“happy and happy and happy and joyful pig feeds on banana”（快乐又快乐又快乐又欢乐的猪吃香蕉）🤪。别介意，它符合我们例子的目的。有了这个语法，我们的解析器中出现了一个重大问题。

可怕的左递归

回想一下我们解析器中的产生式规则处理顺序，我们推导最左边的规则以寻找有效的匹配。这里的问题在于“happiness”的规则，因为“happiness”是它自己的最左边产生式。我们的最左推导策略可能会导致在产生“happiness”时陷入无限循环。虽然这可以通过其他解析技术来处理，但对于我们这些喜欢 LL 解析器的人来说，非常希望转换语法以避免这个问题。

幸运的是，这个问题只发生在左递归产生式中。虽然我们不能完全消除递归，但我们可以将左递归转换为右递归。一般来说，左递归可以系统地转换为右递归形式。

可怕的数学事实

一般来说，对于一个语法

$$\Alpha \rightarrow \Alpha\omega | \beta$$

其中$\Alpha$是一个非终结符，$\omega$和$\beta$是符号组，这个语法可以重写为：

$$\Alpha \rightarrow \beta\Alpha' \\ \Alpha' \rightarrow \epsilon | \omega\Alpha'$$

这个转换有效地将左递归转换为右递归。

让我们以“happiness: 'happy' | 'joyful' | happiness 'and' happiness”为例。无论我们如何产生这个规则，它总是以“happy”或“joyful”开头，例如“happy and joyful”（快乐和欢乐）、“happy and happy”（快乐又快乐）、“joyful and happy and happy”（欢乐和快乐又快乐），或者只是“joyful”（欢乐）。在符号$\Alpha \rightarrow \Alpha\omega | \beta$中，一个$\beta$（“happy”或“joyful”）总是首先出现，后面跟着零个或多个$\Alpha$（“'and' happiness”）。

自然地，我们定义一个新规则“r”，它允许重复“'and' happiness”部分而没有左递归：“r: 'and' happiness r | ε”。将这个放回原始规则中，我们现在有“happiness: 'happy' r | 'joyful' r”。$\epsilon$允许它为空，因为“happiness”可以只是“happy”或“joyful”。现在我们有：

happiness: 'happy' r | 'joyful' r
r: 'and' happiness r | ε

这成功地将左递归转换为右递归。

FIRST 冲突

在“LL(1)”解析器中，我们向前看一个标记，并将其与$\text{FIRST}$集合进行匹配。现在，考虑以下产生式规则：

color    : 'green' | 'yellow' | 'pink';
subject  : [color] happiness animal;
object   : [color] fruit;
sentence : subject 'feeds on' object | object 'feeds' subject;

“subject”和“object”在它们的$\text{FIRST}$规则中都会有颜色派生。这导致$\text{FIRST(\texttt{subject `feeds on' object})}$和$\text{FIRST(\texttt{object `feeds' subject})}$都共享“[green, yellow, pink]”。“LL(1)”解析器不允许$\text{FIRST}$冲突，这阻止了解析器立即选择正确的下降路径。

幸运的是，这个问题可以通过左因子分解轻松解决。通过提取共同部分，我们可以消除冲突：

sentence        : [color] sentence_prime;
sentence_prime  : happiness_prime 'feeds on' object | fruit_prime 'feeds' subject;
happiness_prime : happiness animal;
fruit_prime     : fruit;

如果不希望修改语法，恢复为 LL 回溯解析器也可以解决这个问题——尽管会以性能为代价。回溯解析器在发现选择的下降路径不可行时会回退。另一种方法是增加向前看的标记数量。在这种情况下，两个标记就足够了，因为我们可以通过查看颜色后面的标记来区分“subject”和“object”。

这个例子突出显示在“LL(1)”语法中，预测集合（递归的$\text{FIRST}$和$\text{FOLLOW}$）必须是不相交的，以避免解析表中的冲突。

可怕的数学事实

对于一个语法$G$，当且仅当对于任何产生式$\Alpha \rightarrow \omega_1$和$\Alpha \rightarrow \omega_2$，以下条件成立时，“LL(1)”解析的条件才满足：

$$\text{FIRST(}\omega_1\text{ FOLLOW(}\Alpha\text{))} \cap \text{FIRST(}\omega_2\text{ FOLLOW(}\Alpha\text{))} = \emptyset$$

令人烦恼的表达式……

有一个上下文中左递归经常出现：表达式解析。考虑以下语法：

expr     : primary | expr operator expr;
primary  : INTEGER | '(' expr ')';
operator : '+' | '-' | '*' | '/' | '%' | '^';

当然可以重构语法以消除左递归。然而，表达式解析带来的挑战不仅仅是递归。运算符有优先级，它决定了操作执行的顺序。例如，指数运算具有最高优先级，其次是乘法、除法和取模，最后是加法和减法。括号可以覆盖这个优先级。除了优先级之外，还有结合性。结合性决定了具有相同优先级的运算符的分组和求值方向（即从左到右或从右到左）。

在我们的运算符集合中，只有指数运算是右结合的，而其他都是左结合的。考虑表达式“1 + 2 * 3 / 4 ^ 5 ^ 6”。这里，“4 ^ 5 ^ 6”具有最高优先级，并且由于右结合性，它被分组为“4 ^ (5 ^ 6)”。整个表达式被求值为“1 + ((2 * 3) / (4 ^ (5 ^ 6)))”。对于一个解析器来说，正确识别优先级和结合性是至关重要的。

一种方法是调整语法以确保在解析过程中遵守这些规则：

expr    : term | '+' term | '-' term ;
term    : factor | '*' factor | '/' factor | '%' factor;
factor  : base | base '^' factor;
primary : '(' expr ')' | INTEGER;

然而，在某些情况下，语法规则可能会变得过于复杂，使其难以管理并导致难以阅读的 EBNF。在这种情况下，将表达式视为一个整体并使用专门的技术进行解析可能更实际。

优先级爬升

我们不会深入探讨这个算法的所有细节，因为互联网上有大量的资源。维基百科有一个关于这个的很好的页面。我将对这个算法进行一个基本介绍。

该算法从左边开始。有一个最小优先级级别设置，解析函数将只接受优先级等于或高于此级别的运算符。假设没有语法错误；它解析左值的主表达式（如字面量和带括号的表达式），然后查看运算符。

如果运算符是左结合的（常见情况）并且其优先级大于当前最小优先级，算法将以最小优先级设置为当前运算符的优先级 + 1 进行递归解析。这确保了具有更高优先级的运算符首先被处理。对于具有相同优先级级别的运算符（其中优先级相等），算法不递归，确保这些运算符从左到右正确分组。

当算法遇到右结合运算符时，它需要确保在将运算符应用于左值之前先完全解析表达式的右值。为了实现这一点，算法以相同的优先级级别递归下降。这允许首先处理最右边的操作，确保右结合运算符从右到左分组表达式。

本质上，该算法顺序评估两个运算符，并决定是使用当前优先级构建表达式树，还是让更高优先级运算符的解析函数首先构建其部分。

以下是代码：

from parse_token import *
from parse_node import *


def parse_primary() -> Node:
    lookahead = peek_token()
    if lookahead.token_type == TokenType.INTEGER:
        consume_token()
        return Node(lookahead)
    elif lookahead.token_type == TokenType.LEFT_PARENTHESIS:
        consume_token()
        node = parse_expression_root()
        lookahead = peek_token()
        if lookahead.token_type == TokenType.RIGHT_PARENTHESIS:
            consume_token()
            return node
        else:
            raise ParsingError(
                f"failed parse primary. expect ')' but got '{lookahead}'"
            )
    else:
        raise ParsingError(f"unknown token {lookahead}")


def parse_expression_root() -> Node:
    lhs = parse_primary()
    return parse_expression(lhs, 0)


def parse_expression(lhs: Node, min_precedence) -> Node:
    lookahead: Token = peek_token()
    while (
        lookahead.token_type == TokenType.BINARY_OPERATOR
        and get_precedence(lookahead.content) >= min_precedence
    ):
        operator = lookahead
        current_precedence = get_precedence(operator.content)
        consume_token()
        rhs = parse_primary()
        lookahead = peek_token()

        while lookahead.token_type == TokenType.BINARY_OPERATOR:
            lookahead_left_associative = (
                get_associativity(lookahead.content) == Associativity.Left
            )
            lookahead_right_associative = not lookahead_left_associative
            lookahead_precedence = get_precedence(lookahead.content)

            if (
                lookahead_left_associative and lookahead_precedence > current_precedence
            ) or (
                lookahead_right_associative
                and lookahead_precedence >= current_precedence
            ):
                rhs = parse_expression(
                    rhs,
                    (
                        current_precedence
                        if current_precedence == lookahead_precedence
                        else current_precedence + 1
                    ),
                )
                lookahead = peek_token()
            else:
                break

        result = Node(operator, lhs, rhs)
        lhs = result
    return lhs

为“1+23/4⁵6+7(8+9)”生成的树

调度场算法

调度场算法是一种著名的解析技术，传统上用于将表达式从中缀表示法转换为逆波兰表示法（RPN）。然而，它在构建抽象语法树（AST）方面也非常出色。你可以在维基百科页面上找到更多详细信息，但我将在这里提供一个简要概述。

当使用调度场算法进行 AST 构建时，随着你遍历表达式的标记，操作数被推到输出栈上，而运算符被推到运算符栈上。如果遇到左括号，它只是被推到运算符栈上等待进一步处理。当遇到运算符时，如果栈顶的运算符具有更高的优先级（或者如果是左结合的且优先级相同），则评估前面的表达式。这涉及从它们各自的栈中弹出操作数和运算符，形成一个 AST 节点，然后将这个节点推回到操作数栈上。

当遇到右括号时，算法使用现有的运算符和操作数构建节点，直到找到匹配的左括号。

以下是实现此算法的代码：

from parse_node import *
from parse_token import *


def parse_expression() -> Node | None:
    operators: list[Token] = []
    operands: list[Node] = []

    lookahead = peek_token()
    while lookahead.token_type != TokenType.EOF:
        match lookahead.token_type:
            case TokenType.INTEGER:
                operands.append(Node(lookahead))
            case TokenType.BINARY_OPERATOR:
                while (
                    operators and operators[-1].token_type != TokenType.LEFT_PARENTHESIS
                ):
                    lookahead_precedence = get_precedence(lookahead.content)
                    last_operator_precedence = get_precedence(operators[-1].content)
                    lookahead_associativity = get_associativity(lookahead.content)

                    if last_operator_precedence > lookahead_precedence or (
                        last_operator_precedence == lookahead_precedence
                        and lookahead_associativity == Associativity.Left
                    ):
                        op = operators.pop()

                        if len(operands) < 2:
                            raise ParsingError("missing operand")
                        right = operands.pop()
                        left = operands.pop()
                        operands.append(Node(op, left, right))

                    else:
                        break

                operators.append(lookahead)
            case TokenType.LEFT_PARENTHESIS:
                operators.append(lookahead)
            case TokenType.RIGHT_PARENTHESIS:
                while True:
                    if (
                        operators
                        and operators[-1].token_type != TokenType.LEFT_PARENTHESIS
                    ):
                        if len(operators) == 0:
                            raise ParsingError("mismatched parathensis")
                        op = operators.pop()

                        if len(operands) < 2:
                            raise ParsingError("missing operand")
                        right = operands.pop()
                        left = operands.pop()
                        operands.append(Node(op, left, right))
                    else:
                        break
                if (
                    not operators
                    or operators[-1].token_type != TokenType.LEFT_PARENTHESIS
                ):
                    raise ParsingError("mismatched parathensis")
                operators.pop()
        consume_token()
        lookahead = peek_token()

    while len(operators) > 0:
        last_operator = operators[-1]
        if last_operator.token_type == TokenType.LEFT_PARENTHESIS:
            raise ParsingError("mismatched parathensis")

        if len(operands) < 2:
            raise ParsingError("missing operand")
        right = operands.pop()
        left = operands.pop()
        operands.append(Node(last_operator, left, right))

        operators.pop()

    return operands.pop() if operands else None

为“1+23/4⁵6+7(8+9)”生成的树

优先级爬升在现代编译器中更常见，因为它具有更大的灵活性。它可以处理更复杂的表达式，并在这些情况下支持直接构建抽象语法树，同时也提供更详细的错误报告。