语法树解析器

标准的正则表达式只能做到词法分析，想要实现语法树需要借助递归来实现“先局部，后整体”的逻辑结构，具体例子可以参考算数运算、编程语法。
EBNF语法的形式定义如下：

expr ::= term { (+|-) term }*
term ::= factor { (|/) factor }
factor ::= ( expr ) | NUM

第一步、词法分析

def tokenize(text):
    tokens = []
    i = 0
    while i < len(text):
        char = text[i]
        
        # 1. 跳过空格
        if char.isspace():
            i += 1
            
        # 2. 如果遇到数字，就向后贪婪读取，直到拼接出完整的整数
        elif char.isdigit():
            num_str = ""
            while i < len(text) and text[i].isdigit():
                num_str += text[i]
                i += 1
            tokens.append(('NUM', int(num_str)))  # 存入完整的数字
            
        # 3. 如果遇到运算符号或括号，直接作为一个零件存入
        elif char in '+-*/()':
            tokens.append(('SYM', char))
            i += 1
            
        else:
            raise ValueError(f"不认识的字符: {char}")
            
    return tokens

# 演示：切分一个复杂的算术表达式
text = "3 + 4 * (5 - 2)"
tokens = tokenize(text)
print(f"切分结果: {tokens}")
# 输出: [('NUM', 3), ('SYM', '+'), ('NUM', 4), ('SYM', '*'), ('SYM', '('), ('NUM', 5), ('SYM', '-'), ('NUM', 2), ('SYM', ')')]

第二步、语法分析（这里用EBNF语法规则）

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0  # 游标卡尺，记录当前读到了哪个零件

    def current_token(self):
        """查看当前零件，但不吃掉它"""
        if self.pos < len(self.tokens):
            return self.tokens[self.pos]
        return ('EOF', None)  # 解析完毕

    def consume(self):
        """吃掉当前零件，游标推进一步"""
        token = self.current_token()
        self.pos += 1
        return token

    # 规则 3: factor ::= ( expr ) | NUM  （最底层，处理数字和括号）
    def parse_factor(self):
        token = self.consume()
        
        if token[0] == 'NUM':
            # 如果是纯数字，直接返回它的值
            return token[1]
            
        elif token[0] == 'SYM' and token[1] == '(':
            # 【递归的核心在这里！】遇到左括号，立刻回头调用最高层的 parse_expr
            result = self.parse_expr()
            
            # 表达式计算完后，必须紧跟着一个右括号，否则报错
            if self.consume()[1] != ')':
                raise SyntaxError("缺少右括号 ')'")
            return result

    # 规则 2: term ::= factor { (*|/) factor } （中层，处理高优先级的乘除法）
    def parse_term(self):
        # 先获取左边的一个因子
        left = self.parse_factor()
        
        # 只要后面紧跟着乘号或除号，就一直进行乘除运算（把它们焊死成一个整体）
        while self.current_token()[0] == 'SYM' and self.current_token()[1] in ('*', '/'):
            op = self.consume()[1]         # 拿出运算符
            right = self.parse_factor()    # 获取右边的因子
            
            if op == '*':
                left = left * right
            elif op == '/':
                left = left / right
                
        return left

    # 规则 1: expr ::= term { (+|-) term } （最高层，处理低优先级的加减法）
    def parse_expr(self):
        # 先获取左边的一个大块（项）
        left = self.parse_term()
        
        # 只要后面紧跟着加号或减号，就进行加减运算
        while self.current_token()[0] == 'SYM' and self.current_token()[1] in ('+', '-'):
            op = self.consume()[1]         # 拿出运算符
            right = self.parse_term()      # 获取右边的大块（项）
            
            if op == '+':
                left = left + right
            elif op == '-':
                left = left - right
                
        return left

# 终极测试
parser = Parser(tokens)
result = parser.parse_expr()
print(f"\n算术表达式 {text} 的最终计算结果是: {result}")
# 输出: 算术表达式 3 + 4 * (5 - 2) 的最终计算结果是: 15