第76集：递归下降分析器（一）

学习目标

• 掌握递归下降分析器的基本思想和设计原则
• 学会为每个非终结符设计对应的分析函数
• 理解终结符和非终结符的处理方法
• 掌握递归下降分析器的代码框架
• 通过简单示例巩固递归下降分析器的实现技巧

一、递归下降分析器的基本思想

递归下降分析器（Recursive Descent Parser）是一种自顶向下的语法分析方法，它为每个非终结符编写一个递归函数来处理该非终结符的分析。

核心设计原则

递归下降分析器的核心设计原则是：

1. 一个非终结符对应一个函数：每个非终结符都有一个对应的分析函数
2. 产生式对应函数体：函数体根据非终结符的产生式来实现
3. 终结符直接匹配：遇到终结符时，匹配当前输入的Token
4. 非终结符递归调用：遇到非终结符时，调用对应的函数
5. 预测选择：通过向前看一个Token，选择正确的产生式

为什么称为"递归下降"？

• 递归：因为分析函数会递归调用其他分析函数（包括自身，在处理间接左递归时）
• 下降：因为分析过程是从开始符号（语法树的根）向下构建语法树的过程

二、递归下降分析器的实现步骤

实现一个递归下降分析器通常需要以下步骤：

1. 消除左递归：确保文法不存在左递归，避免无限递归
2. 提取左公因子：消除左公因子，避免回溯
3. 为每个非终结符设计函数：根据产生式编写对应的分析函数
4. 实现终结符匹配：编写匹配终结符的函数
5. 实现错误处理：添加错误检测和报告机制
6. 测试分析器：使用测试用例验证分析器的正确性

三、递归下降分析器的代码框架

基本结构

一个典型的递归下降分析器包含以下部分：

1. Token流管理：负责获取下一个Token，跟踪当前Token
2. 分析函数：为每个非终结符编写的分析函数
3. 匹配函数：用于匹配终结符的函数
4. 错误处理：处理语法错误的函数
5. 主分析函数：启动分析过程的函数

代码框架示例

class RecursiveDescentParser:
    def __init__(self, tokens):
        """初始化分析器"""
        self.tokens = tokens  # Token列表
        self.pos = 0          # 当前Token位置
    
    def current_token(self):
        """获取当前Token"""
        if self.pos < len(self.tokens):
            return self.tokens[self.pos]
        return None
    
    def eat(self, token_type):
        """匹配并消费指定类型的Token"""
        if self.current_token() and self.current_token()[0] == token_type:
            self.pos += 1
            return True
        return False
    
    def error(self, message):
        """报告错误"""
        raise SyntaxError(f"Error at position {self.pos}: {message}")
    
    # 以下是为每个非终结符编写的分析函数
    def parse_A(self):
        """分析非终结符A"""
        # 根据A的产生式实现
        pass
    
    def parse_B(self):
        """分析非终结符B"""
        # 根据B的产生式实现
        pass
    
    def parse(self):
        """开始分析"""
        # 调用开始符号对应的分析函数
        self.parse_start_symbol()
        # 检查是否所有Token都已分析完毕
        if self.pos != len(self.tokens):
            self.error("Unexpected tokens at end")
        return True

四、终结符和非终结符的处理

终结符的处理

终结符的处理相对简单，只需要匹配当前输入的Token是否与预期的终结符类型一致：

1. 获取当前Token：使用current_token()函数获取当前Token
2. 检查类型：检查当前Token的类型是否与预期一致
3. 消费Token：如果匹配，前进到下一个Token；否则，报告错误

非终结符的处理

非终结符的处理需要递归调用对应的分析函数：

1. 识别非终结符：确定当前需要处理的非终结符
2. 调用函数：调用该非终结符对应的分析函数
3. 处理返回值：根据需要处理分析函数的返回值（如构建语法树）

五、产生式的处理

递归下降分析器根据非终结符的产生式来实现分析函数。对于不同形式的产生式，有不同的处理方法。

1. 简单产生式

对于简单产生式 A → α，其中 α 是一个符号串：

def parse_A(self):
    # 处理 α 中的每个符号
    self.parse_symbol1()
    self.parse_symbol2()
    # ...
    self.parse_symboln()

2. 选择产生式

对于选择产生式 A → α | β | ... | γ，需要通过向前看一个Token来选择正确的产生式：

def parse_A(self):
    current = self.current_token()
    if current and current[0] in FIRST(α):
        # 处理 α
        pass
    elif current and current[0] in FIRST(β):
        # 处理 β
        pass
    # ...
    elif current and current[0] in FIRST(γ):
        # 处理 γ
        pass
    else:
        self.error(f"Unexpected token: {current}")

3. ε产生式

对于 ε 产生式 A → ε，当没有其他产生式可选择时，什么都不做：

def parse_A(self):
    current = self.current_token()
    if current and current[0] in FIRST(α):
        # 处理 α
        pass
    else:
        # A → ε，什么都不做
        pass

六、示例：简单算术表达式分析器

文法定义

我们使用以下文法来构建一个简单的算术表达式分析器：

E → TE'
E' → + TE' | ε
T → FT'
T' → * FT' | ε
F → (E) | id

分析器实现

class ExpressionParser:
    def __init__(self, tokens):
        """初始化分析器"""
        self.tokens = tokens
        self.pos = 0
    
    def current_token(self):
        """获取当前Token"""
        if self.pos < len(self.tokens):
            return self.tokens[self.pos]
        return None
    
    def eat(self, token_type):
        """匹配并消费指定类型的Token"""
        if self.current_token() and self.current_token()[0] == token_type:
            self.pos += 1
            return True
        return False
    
    def error(self, message):
        """报告错误"""
        raise SyntaxError(f"Error at position {self.pos}: {message}")
    
    def parse_E(self):
        """解析表达式：E → TE'"""
        print(f"Entering parse_E at position {self.pos}")
        self.parse_T()
        self.parse_E_prime()
        print(f"Exiting parse_E at position {self.pos}")
    
    def parse_E_prime(self):
        """解析表达式后缀：E' → + TE' | ε"""
        print(f"Entering parse_E_prime at position {self.pos}")
        if self.current_token() and self.current_token()[0] == 'ADD':
            self.eat('ADD')
            self.parse_T()
            self.parse_E_prime()
        # 否则，E' → ε，什么都不做
        print(f"Exiting parse_E_prime at position {self.pos}")
    
    def parse_T(self):
        """解析项：T → FT'"""
        print(f"Entering parse_T at position {self.pos}")
        self.parse_F()
        self.parse_T_prime()
        print(f"Exiting parse_T at position {self.pos}")
    
    def parse_T_prime(self):
        """解析项后缀：T' → * FT' | ε"""
        print(f"Entering parse_T_prime at position {self.pos}")
        if self.current_token() and self.current_token()[0] == 'MUL':
            self.eat('MUL')
            self.parse_F()
            self.parse_T_prime()
        # 否则，T' → ε，什么都不做
        print(f"Exiting parse_T_prime at position {self.pos}")
    
    def parse_F(self):
        """解析因子：F → (E) | id"""
        print(f"Entering parse_F at position {self.pos}")
        current = self.current_token()
        if current and current[0] == 'ID':
            self.eat('ID')
        elif current and current[0] == 'LPAREN':
            self.eat('LPAREN')
            self.parse_E()
            if self.current_token() and self.current_token()[0] == 'RPAREN':
                self.eat('RPAREN')
            else:
                self.error("Missing closing parenthesis")
        else:
            self.error(f"Unexpected token: {current}")
        print(f"Exiting parse_F at position {self.pos}")
    
    def parse(self):
        """开始分析"""
        print("Starting parsing...")
        self.parse_E()
        if self.pos != len(self.tokens):
            self.error("Unexpected tokens at end")
        print("Parsing completed successfully!")
        return True

测试示例

测试用例1：简单表达式

# 测试用例1：id + id * id
tokens1 = [
    ('ID', 'id'),
    ('ADD', '+'),
    ('ID', 'id'),
    ('MUL', '*'),
    ('ID', 'id')
]

parser1 = ExpressionParser(tokens1)
try:
    result1 = parser1.parse()
    print("测试用例1分析成功！")
except SyntaxError as e:
    print(f"测试用例1分析失败：{e}")

测试用例2：带括号的表达式

# 测试用例2：(id + id) * id
tokens2 = [
    ('LPAREN', '('),
    ('ID', 'id'),
    ('ADD', '+'),
    ('ID', 'id'),
    ('RPAREN', ')'),
    ('MUL', '*'),
    ('ID', 'id')
]

parser2 = ExpressionParser(tokens2)
try:
    result2 = parser2.parse()
    print("测试用例2分析成功！")
except SyntaxError as e:
    print(f"测试用例2分析失败：{e}")

测试用例3：错误的表达式

# 测试用例3：id + (id * id （缺少右括号）
tokens3 = [
    ('ID', 'id'),
    ('ADD', '+'),
    ('LPAREN', '('),
    ('ID', 'id'),
    ('MUL', '*'),
    ('ID', 'id')
]

parser3 = ExpressionParser(tokens3)
try:
    result3 = parser3.parse()
    print("测试用例3分析成功！")
except SyntaxError as e:
    print(f"测试用例3分析失败：{e}")

六、递归下降分析器的执行流程

以测试用例1 id + id * id 为例，递归下降分析器的执行流程如下：

1. 开始分析：调用 parse() 函数
2. 解析E：调用 parse_E() 函数
3. 解析T：parse_E() 调用 parse_T() 函数
4. 解析F：parse_T() 调用 parse_F() 函数
5. 匹配id：parse_F() 匹配并消费 id Token
6. **解析T'**：parse_T() 调用 parse_T_prime() 函数
7. T'为空：parse_T_prime() 看到当前Token是 +，什么都不做
8. **解析E'**：parse_E() 调用 parse_E_prime() 函数
9. **匹配+**：parse_E_prime() 匹配并消费 + Token
10. 解析T：parse_E_prime() 调用 parse_T() 函数
11. 解析F：parse_T() 调用 parse_F() 函数
12. 匹配id：parse_F() 匹配并消费 id Token
13. **解析T'**：parse_T() 调用 parse_T_prime() 函数
14. 匹配*：parse_T_prime() 匹配并消费 * Token
15. 解析F：parse_T_prime() 调用 parse_F() 函数
16. 匹配id：parse_F() 匹配并消费 id Token
17. **解析T'**：parse_T_prime() 看到输入结束，什么都不做
18. **解析E'**：parse_E_prime() 看到输入结束，什么都不做
19. 完成分析：parse() 函数检查所有Token都已分析完毕，返回成功

七、构建语法树

递归下降分析器不仅可以用于语法检查，还可以在分析过程中构建语法树（Syntax Tree）或抽象语法树（Abstract Syntax Tree, AST）。

语法树节点的设计

首先，需要设计语法树节点的结构：

class ASTNode:
    def __init__(self, node_type, children=None, value=None):
        self.type = node_type      # 节点类型
        self.children = children or []  # 子节点
        self.value = value          # 节点值（如标识符名称、常量值等）
    
    def __repr__(self):
        return f"ASTNode({self.type}, {self.children}, {self.value})"

在分析函数中构建语法树

修改分析函数，使其返回语法树节点：

def parse_E(self):
    """解析表达式：E → TE'"""
    t_node = self.parse_T()
    e_prime_node = self.parse_E_prime()
    if e_prime_node:
        # E' 不为空，构建加法节点
        return ASTNode('ADD', [t_node, e_prime_node])
    else:
        # E' 为空，直接返回 T 节点
        return t_node

def parse_E_prime(self):
    """解析表达式后缀：E' → + TE' | ε"""
    if self.current_token() and self.current_token()[0] == 'ADD':
        self.eat('ADD')
        t_node = self.parse_T()
        e_prime_node = self.parse_E_prime()
        if e_prime_node:
            return ASTNode('ADD', [t_node, e_prime_node])
        else:
            return t_node
    else:
        # E' → ε，返回 None
        return None

八、递归下降分析器的优缺点

优点

1. 直观易懂：分析过程与语法树的构建过程一致，直观易懂
2. 易于实现：可以手动编写，实现简单
3. 错误定位准确：可以在分析过程中精确定位语法错误的位置
4. 灵活性高：可以方便地添加语义动作，如构建语法树、类型检查等
5. 适合手写：对于简单的文法，非常适合手写实现

缺点

1. 递归调用开销：递归调用可能导致栈溢出，对于深层递归的文法不适合
2. 只能处理LL(1)文法：只能处理满足LL(1)条件的文法
3. 需要消除左递归：左递归会导致无限递归
4. 需要提取左公因子：左公因子会导致回溯
5. 代码冗余：对于复杂的文法，代码可能会变得冗余

九、递归下降分析器的优化

1. 消除递归

对于深层递归的文法，可以考虑使用迭代方法消除递归，避免栈溢出：

def parse_E_prime(self):
    """迭代版本的 E' 分析函数"""
    nodes = []
    while self.current_token() and self.current_token()[0] == 'ADD':
        self.eat('ADD')
        nodes.append(self.parse_T())
    # 构建语法树
    if not nodes:
        return None
    result = nodes[0]
    for node in nodes[1:]:
        result = ASTNode('ADD', [result, node])
    return result

2. 预处理Token流

在分析开始前，可以对Token流进行预处理，如合并连续的空白符、注释等，简化分析过程：

def preprocess_tokens(self, tokens):
    """预处理Token流"""
    processed = []
    for token in tokens:
        # 跳过注释Token
        if token[0] == 'COMMENT':
            continue
        # 跳过空白Token
        if token[0] == 'WHITESPACE':
            continue
        processed.append(token)
    return processed

3. 缓存当前Token

为了提高效率，可以缓存当前Token，避免重复获取：

class OptimizedParser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0
        self.current = None
        self._update_current()
    
    def _update_current(self):
        """更新当前Token"""
        if self.pos < len(self.tokens):
            self.current = self.tokens[self.pos]
        else:
            self.current = None
    
    def eat(self, token_type):
        """匹配并消费指定类型的Token"""
        if self.current and self.current[0] == token_type:
            self.pos += 1
            self._update_current()
            return True
        return False

十、自测题

1. 递归下降分析器的基本思想是什么？
2. 为什么递归下降分析器被称为"递归下降"？
3. 如何处理终结符和非终结符？
4. 对于选择产生式 A → α | β | γ，如何选择正确的产生式？
5. 递归下降分析器的优点和缺点是什么？
6. 如何在递归下降分析器中构建语法树？
7. 如何优化递归下降分析器？

十一、总结与展望

本集详细介绍了递归下降分析器的基本思想、实现方法、代码框架以及简单示例。递归下降分析器是一种直观易懂、易于实现的语法分析方法，它为每个非终结符编写一个递归函数来处理该非终结符的分析。

在实现递归下降分析器时，需要注意以下几点：

1. 消除左递归：避免无限递归
2. 提取左公因子：避免回溯
3. 为每个非终结符设计函数：函数名通常与非终结符同名
4. 正确处理终结符和非终结符：终结符直接匹配，非终结符递归调用
5. 添加错误处理：提高分析器的健壮性
6. 构建语法树：方便后续的语义分析和代码生成

在接下来的几集中，我们将继续学习递归下降分析器的高级特性，包括：

• 递归下降分析器（二）：处理选择、重复和错误恢复
• LL(1)分析表构造：基于FIRST集和FOLLOW集构建分析表
• LL(1)分析器实现：基于分析表的预测分析器实现

通过这些学习，我们将能够掌握各种自顶向下分析方法的实现技巧，为构建完整的编译器打下坚实的基础。

十二、参考资料

1. 《编译原理》（龙书）- Alfred V. Aho 等
2. 《现代编译原理》（虎书）- Andrew W. Appel
3. 《编译器设计》- Keith D. Cooper 等
4. 递归下降分析器 - 维基百科
5. Python 官方文档 - 语法分析器实现