第77集：递归下降分析器（二）

学习目标

• 掌握递归下降分析器中处理选择产生式的方法
• 学会分析重复结构（如循环、列表）的技巧
• 理解并实现错误检测与恢复机制
• 通过完整示例巩固递归下降分析器的实现技巧
• 掌握构建完整语法树的方法

一、处理选择产生式

选择产生式是指一个非终结符有多个可能的产生式，如 A → α | β | γ。在递归下降分析器中，需要通过向前看一个Token来选择正确的产生式。

基本方法

处理选择产生式的基本方法是：

1. 向前看一个Token：获取当前输入的Token
2. 匹配FIRST集：检查当前Token属于哪个产生式的FIRST集
3. 选择产生式：根据匹配结果选择对应的产生式
4. 处理错误：如果没有匹配的产生式，报告错误

示例：处理条件语句

考虑以下条件语句的文法：

Stmt → IfStmt | WhileStmt | AssignStmt
IfStmt → if Expr then Stmt else Stmt | if Expr then Stmt
WhileStmt → while Expr do Stmt
AssignStmt → id = Expr

对应的分析函数实现：

def parse_Stmt(self):
    """解析语句：Stmt → IfStmt | WhileStmt | AssignStmt"""
    current = self.current_token()
    if current and current[0] == 'IF':
        return self.parse_IfStmt()
    elif current and current[0] == 'WHILE':
        return self.parse_WhileStmt()
    elif current and current[0] == 'ID':
        # 检查下一个Token是否是'='，以区分标识符和赋值语句
        next_token = self.tokens[self.pos + 1] if self.pos + 1 < len(self.tokens) else None
        if next_token and next_token[0] == 'ASSIGN':
            return self.parse_AssignStmt()
        else:
            self.error(f"Unexpected token: {current}")
    else:
        self.error(f"Unexpected token: {current}")

def parse_IfStmt(self):
    """解析条件语句：IfStmt → if Expr then Stmt else Stmt | if Expr then Stmt"""
    self.eat('IF')
    expr_node = self.parse_Expr()
    self.eat('THEN')
    then_stmt_node = self.parse_Stmt()
    
    # 检查是否有else子句
    if self.current_token() and self.current_token()[0] == 'ELSE':
        self.eat('ELSE')
        else_stmt_node = self.parse_Stmt()
        return ASTNode('IfStmt', [expr_node, then_stmt_node, else_stmt_node])
    else:
        return ASTNode('IfStmt', [expr_node, then_stmt_node])

二、处理重复结构

重复结构是指在文法中可以重复出现的结构，如循环、列表、参数列表等。在递归下降分析器中，有两种主要方法处理重复结构：递归方法和迭代方法。

1. 递归方法

递归方法通过递归调用自身来处理重复结构，适用于右递归的产生式。

示例：处理表达式列表

ExprList → Expr | Expr , ExprList

对应的分析函数实现：

def parse_ExprList(self):
    """解析表达式列表：ExprList → Expr | Expr , ExprList"""
    expr_node = self.parse_Expr()
    if self.current_token() and self.current_token()[0] == 'COMMA':
        self.eat('COMMA')
        expr_list_node = self.parse_ExprList()
        return ASTNode('ExprList', [expr_node] + expr_list_node.children)
    else:
        return ASTNode('ExprList', [expr_node])

2. 迭代方法

迭代方法通过循环来处理重复结构，适用于左递归的产生式（需要先消除左递归）。

示例：处理表达式列表（迭代版本）

ExprList → Expr ExprList'
ExprList' → , Expr ExprList' | ε

对应的分析函数实现：

def parse_ExprList(self):
    """解析表达式列表：ExprList → Expr ExprList'"""
    expr_node = self.parse_Expr()
    expr_list = [expr_node]
    self.parse_ExprList_prime(expr_list)
    return ASTNode('ExprList', expr_list)

def parse_ExprList_prime(self, expr_list):
    """解析表达式列表后缀：ExprList' → , Expr ExprList' | ε"""
    while self.current_token() and self.current_token()[0] == 'COMMA':
        self.eat('COMMA')
        expr_node = self.parse_Expr()
        expr_list.append(expr_node)
    # ExprList' → ε，什么都不做

3. 处理可选结构

可选结构是指在文法中可以出现也可以不出现的结构，如可选的else子句、可选的参数列表等。

示例：处理可选的参数列表

Params → ( ) | ( ExprList )

对应的分析函数实现：

def parse_Params(self):
    """解析参数列表：Params → ( ) | ( ExprList )"""
    self.eat('LPAREN')
    if self.current_token() and self.current_token()[0] == 'RPAREN':
        self.eat('RPAREN')
        return ASTNode('Params', [])
    else:
        expr_list_node = self.parse_ExprList()
        self.eat('RPAREN')
        return ASTNode('Params', expr_list_node.children)

三、错误检测与恢复

错误检测与恢复是递归下降分析器的重要组成部分，它可以帮助分析器在遇到语法错误时继续分析，发现更多错误，而不是立即停止。

1. 错误检测

错误检测的基本方法是：

1. 预期Token：在需要特定Token的地方，检查当前Token是否符合预期
2. FIRST集匹配：在选择产生式时，检查当前Token是否属于任何产生式的FIRST集
3. 同步Token：在错误恢复时，跳过Token直到找到同步Token

2. 错误恢复策略

常见的错误恢复策略包括：

1. 恐慌模式恢复：跳过Token直到找到同步Token（如分号、右括号等）
2. 短语级恢复：插入或删除一个Token，尝试继续分析
3. 错误产生式：在文法中添加专门处理常见错误的产生式

3. 实现错误恢复

示例：恐慌模式恢复

def synchronize(self, sync_tokens):
    """恐慌模式恢复：跳过Token直到找到同步Token"""
    print(f"Error: unexpected token {self.current_token()}")
    while self.current_token():
        if self.current_token()[0] in sync_tokens:
            return True
        self.pos += 1
    return False

def parse_Stmt(self):
    """解析语句，带错误恢复"""
    current = self.current_token()
    if current and current[0] == 'IF':
        try:
            return self.parse_IfStmt()
        except SyntaxError:
            if self.synchronize(['SEMICOLON', 'ELSE', 'END']):
                return ASTNode('ErrorStmt', [])
            else:
                raise
    # 其他产生式的处理...

示例：短语级恢复

def parse_Expr(self):
    """解析表达式，带短语级错误恢复"""
    try:
        return self.parse_T()
    except SyntaxError:
        # 尝试恢复：假设缺少一个表达式
        print("Error: missing expression, inserting dummy")
        return ASTNode('DummyExpr', [])

四、完整示例：简单语句分析器

现在，我们将构建一个完整的简单语句分析器，包括处理选择、重复和错误恢复。

文法定义

Program → StmtList
StmtList → Stmt StmtList | ε
Stmt → IfStmt | WhileStmt | AssignStmt | PrintStmt
IfStmt → if Expr then Stmt else Stmt | if Expr then Stmt
WhileStmt → while Expr do Stmt
AssignStmt → id = Expr
PrintStmt → print ( ExprList )
ExprList → Expr | Expr , ExprList
Expr → Term Expr'
Expr' → + Term Expr' | - Term Expr' | ε
Term → Factor Term'
Term' → * Factor Term' | / Factor Term' | ε
Factor → ( Expr ) | id | number

分析器实现

class SimpleParser:
    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 None
    
    def eat(self, token_type):
        if self.current_token() and self.current_token()[0] == token_type:
            self.pos += 1
            return True
        raise SyntaxError(f"Expected {token_type}, got {self.current_token()}")
    
    def error(self, message):
        raise SyntaxError(f"Error at position {self.pos}: {message}")
    
    def synchronize(self, sync_tokens):
        """恐慌模式恢复"""
        print(f"Error: {self.current_token()}")
        while self.current_token():
            if self.current_token()[0] in sync_tokens:
                return True
            self.pos += 1
        return False
    
    # 表达式相关分析函数
    def parse_Factor(self):
        """解析因子：Factor → ( Expr ) | id | number"""
        current = self.current_token()
        if current and current[0] == 'LPAREN':
            self.eat('LPAREN')
            expr_node = self.parse_Expr()
            self.eat('RPAREN')
            return expr_node
        elif current and current[0] == 'ID':
            self.eat('ID')
            return {'type': 'ID', 'value': current[1]}
        elif current and current[0] == 'NUMBER':
            self.eat('NUMBER')
            return {'type': 'NUMBER', 'value': current[1]}
        else:
            self.error(f"Unexpected token: {current}")
    
    def parse_Term_prime(self):
        """解析项后缀：Term' → * Factor Term' | / Factor Term' | ε"""
        current = self.current_token()
        if current and current[0] == 'MUL':
            self.eat('MUL')
            factor = self.parse_Factor()
            term_prime = self.parse_Term_prime()
            return {'type': 'MUL', 'left': factor, 'right': term_prime}
        elif current and current[0] == 'DIV':
            self.eat('DIV')
            factor = self.parse_Factor()
            term_prime = self.parse_Term_prime()
            return {'type': 'DIV', 'left': factor, 'right': term_prime}
        else:
            return None
    
    def parse_Term(self):
        """解析项：Term → Factor Term'"""
        factor = self.parse_Factor()
        term_prime = self.parse_Term_prime()
        if term_prime:
            return {'type': 'Term', 'left': factor, 'right': term_prime}
        else:
            return factor
    
    def parse_Expr_prime(self):
        """解析表达式后缀：Expr' → + Term Expr' | - Term Expr' | ε"""
        current = self.current_token()
        if current and current[0] == 'ADD':
            self.eat('ADD')
            term = self.parse_Term()
            expr_prime = self.parse_Expr_prime()
            return {'type': 'ADD', 'left': term, 'right': expr_prime}
        elif current and current[0] == 'SUB':
            self.eat('SUB')
            term = self.parse_Term()
            expr_prime = self.parse_Expr_prime()
            return {'type': 'SUB', 'left': term, 'right': expr_prime}
        else:
            return None
    
    def parse_Expr(self):
        """解析表达式：Expr → Term Expr'"""
        term = self.parse_Term()
        expr_prime = self.parse_Expr_prime()
        if expr_prime:
            return {'type': 'Expr', 'left': term, 'right': expr_prime}
        else:
            return term
    
    # 语句相关分析函数
    def parse_ExprList(self):
        """解析表达式列表：ExprList → Expr | Expr , ExprList"""
        expr = self.parse_Expr()
        expr_list = [expr]
        while self.current_token() and self.current_token()[0] == 'COMMA':
            self.eat('COMMA')
            expr = self.parse_Expr()
            expr_list.append(expr)
        return {'type': 'ExprList', 'exprs': expr_list}
    
    def parse_PrintStmt(self):
        """解析打印语句：PrintStmt → print ( ExprList )"""
        self.eat('PRINT')
        self.eat('LPAREN')
        expr_list = self.parse_ExprList()
        self.eat('RPAREN')
        return {'type': 'PrintStmt', 'exprs': expr_list}
    
    def parse_AssignStmt(self):
        """解析赋值语句：AssignStmt → id = Expr"""
        current = self.current_token()
        self.eat('ID')
        self.eat('ASSIGN')
        expr = self.parse_Expr()
        return {'type': 'AssignStmt', 'id': current[1], 'expr': expr}
    
    def parse_WhileStmt(self):
        """解析while语句：WhileStmt → while Expr do Stmt"""
        self.eat('WHILE')
        expr = self.parse_Expr()
        self.eat('DO')
        stmt = self.parse_Stmt()
        return {'type': 'WhileStmt', 'expr': expr, 'stmt': stmt}
    
    def parse_IfStmt(self):
        """解析if语句：IfStmt → if Expr then Stmt else Stmt | if Expr then Stmt"""
        self.eat('IF')
        expr = self.parse_Expr()
        self.eat('THEN')
        then_stmt = self.parse_Stmt()
        
        if self.current_token() and self.current_token()[0] == 'ELSE':
            self.eat('ELSE')
            else_stmt = self.parse_Stmt()
            return {'type': 'IfStmt', 'expr': expr, 'then_stmt': then_stmt, 'else_stmt': else_stmt}
        else:
            return {'type': 'IfStmt', 'expr': expr, 'then_stmt': then_stmt}
    
    def parse_Stmt(self):
        """解析语句：Stmt → IfStmt | WhileStmt | AssignStmt | PrintStmt"""
        current = self.current_token()
        if current and current[0] == 'IF':
            return self.parse_IfStmt()
        elif current and current[0] == 'WHILE':
            return self.parse_WhileStmt()
        elif current and current[0] == 'ID':
            # 检查是否是赋值语句
            next_token = self.tokens[self.pos + 1] if self.pos + 1 < len(self.tokens) else None
            if next_token and next_token[0] == 'ASSIGN':
                return self.parse_AssignStmt()
            else:
                self.error(f"Unexpected token: {current}")
        elif current and current[0] == 'PRINT':
            return self.parse_PrintStmt()
        else:
            self.error(f"Unexpected token: {current}")
    
    def parse_StmtList(self):
        """解析语句列表：StmtList → Stmt StmtList | ε"""
        stmt_list = []
        while self.current_token():
            try:
                stmt = self.parse_Stmt()
                stmt_list.append(stmt)
            except SyntaxError:
                # 错误恢复
                if not self.synchronize(['IF', 'WHILE', 'ID', 'PRINT']):
                    break
        return {'type': 'StmtList', 'stmts': stmt_list}
    
    def parse(self):
        """解析程序：Program → StmtList"""
        return self.parse_StmtList()

测试示例

测试用例1：简单语句

# 测试用例1：赋值和打印语句
tokens1 = [
    ('ID', 'x'),
    ('ASSIGN', '='),
    ('NUMBER', 5),
    ('PRINT', 'print'),
    ('LPAREN', '('),
    ('ID', 'x'),
    ('RPAREN', ')')
]

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

测试用例2：条件和循环语句

# 测试用例2：条件和循环语句
tokens2 = [
    ('ID', 'i'),
    ('ASSIGN', '='),
    ('NUMBER', 0),
    ('WHILE', 'while'),
    ('ID', 'i'),
    ('ADD', '+'),
    ('NUMBER', 1),
    ('DO', 'do'),
    ('IF', 'if'),
    ('ID', 'i'),
    ('MUL', '*'),
    ('NUMBER', 2),
    ('THEN', 'then'),
    ('PRINT', 'print'),
    ('LPAREN', '('),
    ('ID', 'i'),
    ('RPAREN', ')'),
    ('ELSE', 'else'),
    ('PRINT', 'print'),
    ('LPAREN', '('),
    ('NUMBER', 0),
    ('RPAREN', ')')
]

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

测试用例3：带错误的语句

# 测试用例3：带错误的语句（缺少右括号）
tokens3 = [
    ('PRINT', 'print'),
    ('LPAREN', '('),
    ('ID', 'x'),
    ('ASSIGN', '='),
    ('NUMBER', 5)
]

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

五、构建完整语法树

在实际编译器中，递归下降分析器通常需要构建完整的抽象语法树（AST），以便后续的语义分析和代码生成。

语法树节点设计

一个完整的语法树节点应该包含：

1. 节点类型：如表达式、语句、运算符等
2. 子节点：对应产生式中的符号
3. 属性：如标识符名称、常量值等
4. 位置信息：用于错误报告和调试

示例：增强的语法树节点

class ASTNode:
    def __init__(self, node_type, children=None, attributes=None, position=None):
        self.type = node_type          # 节点类型
        self.children = children or []  # 子节点
        self.attributes = attributes or {}  # 属性
        self.position = position        # 位置信息
    
    def __repr__(self):
        return f"ASTNode({self.type}, {self.children}, {self.attributes})"
    
    def add_child(self, child):
        """添加子节点"""
        self.children.append(child)
    
    def set_attribute(self, name, value):
        """设置属性"""
        self.attributes[name] = value
    
    def get_attribute(self, name):
        """获取属性"""
        return self.attributes.get(name)

在分析函数中构建语法树

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

def parse_AssignStmt(self):
    """解析赋值语句，返回语法树节点"""
    current = self.current_token()
    pos = self.pos
    self.eat('ID')
    self.eat('ASSIGN')
    expr = self.parse_Expr()
    node = ASTNode('AssignStmt', [expr], {'id': current[1]}, pos)
    return node

六、递归下降分析器的最佳实践

1. 代码组织

• 模块化：将分析器分为多个模块，如词法分析、语法分析、错误处理等
• 清晰的函数命名：函数名应与非终结符对应，如 parse_Expr 对应非终结符 Expr
• 注释：为每个函数添加注释，说明其对应的产生式

2. 性能优化

• 消除递归：对于深层递归的文法，使用迭代方法
• 缓存Token：缓存当前Token，避免重复获取
• 预计算FIRST集：预计算每个产生式的FIRST集，加快选择产生式的速度

3. 错误处理

• 详细的错误信息：提供详细的错误信息，包括错误位置、预期Token等
• 错误恢复：实现错误恢复机制，尽可能发现更多错误
• 错误计数：统计错误数量，决定是否继续编译

4. 测试

• 单元测试：为每个分析函数编写单元测试
• 集成测试：测试完整的分析过程
• 边界测试：测试边界情况，如空语句、嵌套结构等
• 错误测试：测试各种语法错误的处理

七、递归下降分析器的应用场景

递归下降分析器适用于以下场景：

1. 小型语言：对于小型语言，递归下降分析器实现简单，维护方便
2. **领域特定语言(DSL)**：DSL通常语法简单，适合使用递归下降分析器
3. 脚本语言：许多脚本语言的解释器使用递归下降分析器
4. 编译器前端原型：在编译器开发的早期阶段，递归下降分析器可以快速构建前端原型
5. 教育和学习：递归下降分析器直观易懂，适合作为编译原理的教学工具

八、自测题

1. 如何处理选择产生式 A → α | β | γ？
2. 处理重复结构有哪两种方法？它们的区别是什么？
3. 什么是恐慌模式错误恢复？如何实现？
4. 如何在递归下降分析器中构建完整的语法树？
5. 递归下降分析器的最佳实践有哪些？
6. 递归下降分析器适用于哪些场景？

九、总结与展望

本集详细介绍了递归下降分析器中处理选择、重复和错误恢复的方法，以及构建完整语法树的技巧。递归下降分析器是一种直观易懂、易于实现的语法分析方法，它通过为每个非终结符编写一个递归函数来处理该非终结符的分析。

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

1. 处理选择产生式：通过向前看一个Token来选择正确的产生式
2. 处理重复结构：使用递归或迭代方法处理重复结构
3. 实现错误恢复：使用恐慌模式或短语级恢复来处理语法错误
4. 构建语法树：为后续的语义分析和代码生成做准备
5. 优化性能：消除递归、缓存Token、预计算FIRST集等

在接下来的几集中，我们将继续学习语法分析的其他方法：

• LL(1)分析表构造：基于FIRST集和FOLLOW集构建分析表
• LL(1)分析器实现：基于分析表的预测分析器实现
• 自底向上分析概述：介绍移进-归约分析和LR分析

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

十、参考资料

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