递归下降语法分析器 python实现

递归下降（Recursive Descent）是一种解析技术，常用于构建语法分析器，特别是用于语言处理，如编程语言。在Python中实现递归下降分析器，主要利用了函数的定义和递归调用。以下是一个简单的例子：

# 假设我们正在解析一个非常基础的算术表达式语言，只支持加减操作
# 采用BNF（巴科斯-诺尔范式）描述：
# E -> T '+' E | T
# T -> F '-' T | F
# F -> ('(' E ')') | number

def parse_expression(tokens):
    def term():
        num = parse_factor()
        while tokens and tokens == '+':
            tokens.pop(0)
            num += parse_factor()
        return num

    def factor():
        if tokens == '(':
            tokens.pop(0)  # 消耗左括号
            result = parse_expression(tokens)
            assert tokens == ')', 'Expected closing parenthesis'
            tokens.pop(0)  # 消耗右括号
            return result
        else:
            return int(tokens.pop(0))

    if tokens == '+':
        tokens.pop(0)
        return term()
    else:
        return factor()

# 使用示例
tokens = ['(', '3', '+', '4', ')']
expression_result = parse_expression(tokens)

在这个例子中，`parse_expression`函数作为顶层解析器，根据输入的token列表调用`term`和`factor`这些辅助函数。每个辅助函数都是递归的，直到遇到终结符（如数字或运算符）。