第75集：自顶向下分析概述

学习目标

• 理解自顶向下分析的基本概念和核心思想
• 掌握自顶向下分析的方法分类
• 理解预测分析的基本原理
• 理解递归下降分析的基本原理
• 掌握LL(1)分析法的基本思想
• 了解自顶向下分析的优缺点

一、自顶向下分析的基本概念

自顶向下分析（Top-Down Parsing）是一种语法分析方法，它从文法的开始符号出发，通过构建最左推导，尝试与输入的Token序列匹配。

核心思想

自顶向下分析的核心思想是：

1. 从开始符号开始：以文法的开始符号作为语法树的根节点
2. 最左推导：在每一步推导中，选择最左边的非终结符进行替换
3. 匹配输入：尝试将推导产生的符号串与输入的Token序列匹配
4. 回溯：当匹配失败时，回溯到之前的选择点，尝试其他产生式

分析过程

以简单算术表达式为例，输入串为 id + id * id，自顶向下分析过程如下：

1. 开始符号为 E
2. 应用产生式 E → E + T，得到 E + T
3. 对 E 应用产生式 E → T，得到 T + T
4. 对 T 应用产生式 T → F，得到 F + T
5. 对 F 应用产生式 F → id，得到 id + T，匹配输入的 id +
6. 对 T 应用产生式 T → T * F，得到 T * F
7. 对 T 应用产生式 T → F，得到 F * F
8. 对 F 应用产生式 F → id，得到 id * F，匹配输入的 id *
9. 对 F 应用产生式 F → id，得到 id，匹配输入的 id
10. 分析成功

二、自顶向下分析的方法分类

自顶向下分析主要分为两大类：

1. 带回溯的自顶向下分析：尝试所有可能的产生式，失败时回溯
2. 不带回溯的自顶向下分析：通过预测选择正确的产生式，避免回溯

1. 带回溯的自顶向下分析

基本思想：

• 尝试使用非终结符的第一个产生式
• 如果匹配失败，回溯到之前的状态，尝试下一个产生式

优点：

• 可以处理任何上下文无关文法

缺点：

• 效率低，存在大量回溯
• 难以处理左递归
• 错误定位困难

2. 不带回溯的自顶向下分析

基本思想：

• 通过向前看一个或多个Token，预测应该使用哪个产生式
• 避免回溯，提高分析效率

代表方法：

• 预测分析：使用分析表和栈进行分析
• 递归下降分析：使用递归函数进行分析

优点：

• 效率高，无回溯
• 错误定位准确
• 易于实现

缺点：

• 只能处理LL(k)文法
• 需要消除左递归和提取左公因子

三、预测分析

预测分析（Predictive Parsing）是一种不带回溯的自顶向下分析方法，它使用分析表和栈来指导分析过程。

预测分析器的组成

预测分析器由以下三部分组成：

1. 输入缓冲区：存放待分析的Token序列，以结束符 $ 结尾
2. 分析栈：存放文法符号，初始时包含开始符号和结束符 $
3. 分析表：二维表格，行代表非终结符，列代表终结符，表项为产生式或错误

预测分析的过程

预测分析的基本过程如下：

1. 初始化：将开始符号压入栈，输入指针指向第一个Token
2. 循环：
   • 取出栈顶符号 X
   • 如果 X 是终结符：
     • 如果 X 与当前输入Token匹配，输入指针前进一位
     • 否则，分析失败
   • 如果 X 是非终结符：
     • 查看分析表 M[X, a]，其中 a 是当前输入Token
     • 如果 M[X, a] 是产生式 X → α，将 X 弹出栈，将 α 逆序压入栈
     • 如果 M[X, a] 是错误，分析失败
   • 如果 X 是 $：
     • 如果当前输入Token也是 $，分析成功
     • 否则，分析失败

示例：预测分析过程

考虑以下文法：

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

输入串：id + id * id $

分析过程如下：

四、递归下降分析

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

基本原理

递归下降分析的基本原理是：

1. 为每个非终结符编写一个函数：函数名通常与非终结符同名
2. 函数实现：函数体根据非终结符的产生式编写
3. 终结符处理：当遇到终结符时，匹配当前输入Token
4. 非终结符处理：当遇到非终结符时，调用相应的函数
5. 预测选择：通过向前看一个Token，选择正确的产生式

示例：递归下降分析器框架

以简单算术表达式文法为例，递归下降分析器的框架如下：

def parse_E():
    parse_T()
    parse_E_prime()

def parse_E_prime():
    if current_token == '+':
        match('+')
        parse_T()
        parse_E_prime()
    # 否则，E' → ε，什么都不做

def parse_T():
    parse_F()
    parse_T_prime()

def parse_T_prime():
    if current_token == '*':
        match('*')
        parse_F()
        parse_T_prime()
    # 否则，T' → ε，什么都不做

def parse_F():
    if current_token == 'id':
        match('id')
    elif current_token == '(':
        match('(')
        parse_E()
        match(')')
    else:
        error()

def match(token_type):
    if current_token == token_type:
        advance()  # 前进到下一个Token
    else:
        error()

递归下降分析的过程

以输入串 id + id * id 为例，递归下降分析过程如下：

1. 调用 parse_E()
2. parse_E() 调用 parse_T()
3. parse_T() 调用 parse_F()
4. parse_F() 匹配 id，调用 match('id')
5. parse_T() 调用 parse_T_prime()
6. parse_T_prime() 看到当前Token是 +，什么都不做
7. parse_E() 调用 parse_E_prime()
8. parse_E_prime() 匹配 +，调用 match('+')
9. parse_E_prime() 调用 parse_T()
10. parse_T() 调用 parse_F()
11. parse_F() 匹配 id，调用 match('id')
12. parse_T() 调用 parse_T_prime()
13. parse_T_prime() 匹配 *，调用 match('*')
14. parse_T_prime() 调用 parse_F()
15. parse_F() 匹配 id，调用 match('id')
16. parse_T_prime() 看到输入结束，什么都不做
17. parse_E_prime() 看到输入结束，什么都不做
18. 分析成功

五、LL(1)分析法

LL(1)分析法是一种不带回溯的自顶向下分析方法，它是预测分析和递归下降分析的理论基础。

LL(1)的含义

LL(1)中的每个字母都有特定的含义：

• 第一个L：表示从左到右扫描输入串
• 第二个L：表示构建最左推导
• 1：表示向前看一个Token来决定使用哪个产生式

LL(1)文法的条件

一个文法是LL(1)的，当且仅当对于每个非终结符A和每个终结符a，满足以下两个条件：

1. 互斥性：对于A的任意两个不同产生式A→α和A→β，有：

   • FIRST(α) ∩ FIRST(β) = ∅

2. ε产生式条件：如果A→ε是一个产生式，则：

   • FIRST(α) ∩ FOLLOW(A) = ∅ 对于所有A→α的产生式

FIRST集和FOLLOW集

LL(1)分析依赖于两个重要的集合：

1. FIRST集：对于符号串α，FIRST(α)是α推导的第一个终结符的集合
2. FOLLOW集：对于非终结符A，FOLLOW(A)是可能出现在A后面的终结符的集合

LL(1)分析表的构造

LL(1)分析表的构造步骤如下：

1. 计算每个非终结符的FIRST集和FOLLOW集
2. 对于每个产生式A→α：
   • 对于每个终结符a∈FIRST(α)，将A→α填入分析表M[A,a]
   • 如果ε∈FIRST(α)，则对于每个终结符b∈FOLLOW(A)，将A→α填入分析表M[A,b]

六、自顶向下分析的优缺点

优点

1. 直观易懂：分析过程与语法树的构建过程一致，直观易懂
2. 易于实现：递归下降分析器可以手动编写，实现简单
3. 错误定位准确：可以在分析过程中精确定位语法错误的位置
4. 适合手写：对于简单的文法，递归下降分析器非常适合手写

缺点

1. 只能处理LL(k)文法：只能处理满足LL(k)条件的文法
2. 需要消除左递归：左递归会导致无限循环
3. 需要提取左公因子：左公因子会导致回溯
4. 分析表可能很大：对于复杂的文法，LL(1)分析表可能非常大
5. 难以处理二义性：对于二义性文法，需要通过优先级和结合性规则解决

七、自顶向下分析的应用

自顶向下分析在编译器和解释器的实现中被广泛应用：

1. 小型语言的编译器：对于小型语言，递归下降分析器是一种常见的选择
2. 脚本语言的解释器：许多脚本语言的解释器使用递归下降分析器
3. 领域特定语言(DSL)的解析器：DSL通常语法简单，适合使用递归下降分析器
4. 编译器前端的快速原型：在编译器开发的早期阶段，递归下降分析器可以快速构建前端原型

示例：Python解释器的解析器

Python解释器的解析器就是使用递归下降分析实现的。Python的语法相对简单，适合使用递归下降分析器。Python的解析器由多个递归函数组成，每个函数对应一个语法结构，例如：

• parse_expression()：解析表达式
• parse_statement()：解析语句
• parse_function_def()：解析函数定义

这种实现方式使得Python的解析器代码清晰易懂，易于维护和扩展。

八、代码示例：简单的递归下降分析器

下面是一个简单的递归下降分析器实现，用于分析简单的算术表达式：

class RecursiveDescentParser:
    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
        return False
    
    def parse_E(self):
        """解析表达式：E → TE'"""
        self.parse_T()
        self.parse_E_prime()
    
    def parse_E_prime(self):
        """解析表达式后缀：E' → + TE' | ε"""
        if self.current_token() and self.current_token()[0] == 'ADD':
            self.eat('ADD')
            self.parse_T()
            self.parse_E_prime()
        # 否则，E' → ε，什么都不做
    
    def parse_T(self):
        """解析项：T → FT'"""
        self.parse_F()
        self.parse_T_prime()
    
    def parse_T_prime(self):
        """解析项后缀：T' → * FT' | ε"""
        if self.current_token() and self.current_token()[0] == 'MUL':
            self.eat('MUL')
            self.parse_F()
            self.parse_T_prime()
        # 否则，T' → ε，什么都不做
    
    def parse_F(self):
        """解析因子：F → (E) | id"""
        if self.current_token() and self.current_token()[0] == 'ID':
            self.eat('ID')
        elif self.current_token() and self.current_token()[0] == 'LPAREN':
            self.eat('LPAREN')
            self.parse_E()
            if self.current_token() and self.current_token()[0] == 'RPAREN':
                self.eat('RPAREN')
            else:
                raise SyntaxError("Missing closing parenthesis")
        else:
            raise SyntaxError(f"Unexpected token: {self.current_token()}")
    
    def parse(self):
        """开始分析"""
        self.parse_E()
        if self.pos != len(self.tokens):
            raise SyntaxError(f"Unexpected tokens at end: {self.tokens[self.pos:]}")
        return True

# 测试
if __name__ == "__main__":
    # 测试用例 1：简单表达式
    tokens1 = [
        ('ID', 'id'),
        ('ADD', '+'),
        ('ID', 'id'),
        ('MUL', '*'),
        ('ID', 'id')
    ]
    
    parser1 = RecursiveDescentParser(tokens1)
    try:
        result1 = parser1.parse()
        print("测试用例 1 分析成功！")
    except SyntaxError as e:
        print(f"测试用例 1 分析失败：{e}")
    
    # 测试用例 2：带括号的表达式
    tokens2 = [
        ('LPAREN', '('),
        ('ID', 'id'),
        ('ADD', '+'),
        ('ID', 'id'),
        ('RPAREN', ')'),
        ('MUL', '*'),
        ('ID', 'id')
    ]
    
    parser2 = RecursiveDescentParser(tokens2)
    try:
        result2 = parser2.parse()
        print("测试用例 2 分析成功！")
    except SyntaxError as e:
        print(f"测试用例 2 分析失败：{e}")
    
    # 测试用例 3：错误的表达式（缺少右括号）
    tokens3 = [
        ('LPAREN', '('),
        ('ID', 'id'),
        ('ADD', '+'),
        ('ID', 'id'),
        ('MUL', '*'),
        ('ID', 'id')
    ]
    
    parser3 = RecursiveDescentParser(tokens3)
    try:
        result3 = parser3.parse()
        print("测试用例 3 分析成功！")
    except SyntaxError as e:
        print(f"测试用例 3 分析失败：{e}")