实现简单算术表示式到抽象语法树的转换

将算术表达式转换为抽象语法树的一般方法是使用递归下降分析器。下面是一个简单的实现示例，可以将中缀表达式转换为抽象语法树。

假设我们要将以下算术表达式转换为抽象语法树：

2 + 3 * 4 - 5

首先，我们需要定义语法规则。在这个例子中，我们只有加、减、乘三种运算符，因此我们可以定义以下语法规则：

expression -> term ( ( "+" | "-" ) term )*
term -> factor ( ( "*" | "/" ) factor )*
factor -> NUMBER | "(" expression ")"

其中，expression 表示一个算术表达式，term 表示一个项，factor 表示一个因子。这些规则描述了表达式中运算符的优先级和结合性。

接下来，我们可以使用递归下降分析器来实现这些语法规则。具体实现如下：

class Node:
    def evaluate(self):
        pass

class NumberNode(Node):
    def __init__(self, value):
        self.value = value

    def evaluate(self):
        return self.value

class BinaryOperationNode(Node):
    def __init__(self, left, operator, right):
        self.left = left
        self.operator = operator
        self.right = right

    def evaluate(self):
        left_value = self.left.evaluate()
        right_value = self.right.evaluate()

        if self.operator == "+":
            return left_value + right_value
        elif self.operator == "-":
            return left_value - right_value
        elif self.operator == "*":
            return left_value * right_value
        elif self.operator == "/":
            return left_value / right_value

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def parse(self):
        return self.expression()

    def expression(self):
        left = self.term()

        while self.pos < len(self.tokens):
            if self.tokens[self.pos][0] == "+":
                self.pos += 1
                right = self.term()
                left = BinaryOperationNode(left, "+", right)
            elif self.tokens[self.pos][0] == "-":
                self.pos += 1
                right = self.term()
                left = BinaryOperationNode(left, "-", right)
            else:
                break

        return left

    def term(self):
        left = self.factor()

        while self.pos < len(self.tokens):
            if self.tokens[self.pos][0] == "*":
                self.pos += 1
                right = self.factor()
                left = BinaryOperationNode(left, "*", right)
            elif self.tokens[self.pos][0] == "/":
                self.pos += 1
                right = self.factor()
                left = BinaryOperationNode(left, "/", right)
            else:
                break

        return left

    def factor(self):
        token = self.tokens[self.pos]

        if token[0] == "NUMBER":
            self.pos += 1
            return NumberNode(token[1])
        elif token[0] == "(":
            self.pos += 1
            node = self.expression()
            if self.tokens[self.pos][0] != ")":
                raise Exception("Expected ')'")
            self.pos += 1
            return node
        else:
            raise Exception("Expected number or '('")

在这个实现中，我们定义了一个 Node 类作为所有节点的基类。NumberNode 表示一个数字节点，BinaryOperationNode 表示一个二元运算节点。Parser 类负责将 token 序列解析为抽象语法树。

我们首先定义了 expression、term 和 factor 三个方法，分别表示表达式、项和因子。在 expression 方法中，我们首先调用 term 方法获取左侧节点，然后使用 while 循环处理剩下的运算符，构建抽象语法树。term 和 factor 方法类似。

在 term 和 expression 方法中，我们使用了 while 循环来处理运算符。这是因为我们需要考虑运算符的优先级和结合性。例如，在表达式 "2 + 3 * 4" 中，乘法运算符具有更高的优先级，因此我们需要先处理乘法。

最后，我们可以使用以下代码来测试 Parser 类：

tokens = [
    ("NUMBER", 2),
    ("+", None),
    ("NUMBER", 3),
    ("*", None),
    ("NUMBER", 4),
    ("-", None),
    ("NUMBER", 5),
]

parser = Parser(tokens)
tree = parser.parse()
print(tree.evaluate())  # 输出: 9

这段代码首先定义了一个 token 序列，并将其传递给 Parser 类。然后，我们调用 parse 方法获取抽象语法树，并调用 evaluate 方法计算表达式的值。在这个例子中，输出应该为 9。