第53集：递归下降分析器

学习目标

• 理解递归下降分析器的基本原理
• 掌握递归下降分析器的实现方法
• 了解LL(1)文法的概念和要求
• 学会处理递归下降分析中的回溯问题
• 能够使用Python实现简单的递归下降分析器

1. 递归下降分析器概述

1.1 基本原理

递归下降分析器是一种自顶向下的语法分析方法，它的基本原理是：

• 为文法中的每个非终结符编写一个递归函数
• 每个函数根据当前的输入符号，选择合适的产生式进行推导
• 通过递归调用函数来处理产生式右部的非终结符
• 当遇到终结符时，与当前输入符号进行匹配

1.2 优缺点

优点：

• 实现简单直观，代码结构清晰
• 容易理解和调试
• 可以方便地生成有意义的错误信息
• 适合手工实现小型语言的语法分析器

缺点：

• 对于左递归文法无法直接处理
• 可能存在回溯问题，导致效率低下
• 对于复杂文法，代码量较大

1.3 适用场景

• 小型语言或领域特定语言(DSL)的语法分析
• 编译器前端的快速原型开发
• 脚本语言的解析器
• 配置文件的解析器

2. LL(1)文法

2.1 LL(1)文法的定义

LL(1)文法是一种适合递归下降分析的文法，它具有以下特点：

• 第一个L：从左到右扫描输入符号
• 第二个L：最左推导
• 1：每一步只需要向前看一个符号就能决定使用哪个产生式

2.2 LL(1)文法的要求

一个文法是LL(1)的，当且仅当对于文法中的任意两个不同的产生式 A → α 和 A → β，满足以下条件：

1. α 和 β 不能同时推导出以同一个终结符开头的字符串
2. 如果 α 可以推导出 ε，那么 β 不能推导出以 FOLLOW(A) 中的符号开头的字符串
3. 如果 β 可以推导出 ε，那么 α 不能推导出以 FOLLOW(A) 中的符号开头的字符串

2.3 FIRST集和FOLLOW集

FIRST集

对于文法符号串 α，FIRST(α) 是所有可能出现在 α 推导的第一个终结符的集合。如果 α 可以推导出 ε，则 ε 也在 FIRST(α) 中。

FOLLOW集

对于非终结符 A，FOLLOW(A) 是所有可能出现在 A 之后的终结符的集合。如果 A 可以出现在句子的末尾，则结束符 $ 也在 FOLLOW(A) 中。

2.4 LL(1)分析表

LL(1)分析表是一个二维表，行代表非终结符，列代表终结符，表中的元素是该非终结符在遇到该终结符时应该使用的产生式。

3. 递归下降分析器的实现

3.1 实现步骤

1. 消除左递归：递归下降分析器无法处理左递归文法，需要先消除左递归
2. 提取左因子：处理可能导致回溯的产生式
3. 计算FIRST集和FOLLOW集：用于构建LL(1)分析表
4. 为每个非终结符编写递归函数：根据产生式和FIRST/FOLLOW集实现分析逻辑
5. 实现词法分析器：为递归下降分析器提供词法单元
6. 实现错误处理：在遇到语法错误时提供有意义的错误信息

3.2 消除左递归

直接左递归的消除

对于形如 A → Aα | β 的直接左递归，可以转换为：

A → βA'
A' → αA' | ε

间接左递归的消除

对于间接左递归，需要先将其转换为直接左递归，然后再消除。

3.3 提取左因子

对于形如 A → αβ1 | αβ2 | ... | αβn | γ 的产生式，可以提取左因子为：

A → αA' | γ
A' → β1 | β2 | ... | βn

4. 实战案例：简单表达式分析器

4.1 文法定义

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

E → T E'
E' → + T E' | - T E' | ε
T → F T'
T' → * F T' | / F T' | ε
F → ( E ) | id | num

这个文法已经消除了左递归，并且是LL(1)的。

4.2 词法分析器实现

首先，我们需要实现一个简单的词法分析器，用于识别表达式中的词法单元：

# lexer.py

class Token:
    def __init__(self, type_, value):
        self.type = type_  # 词法单元类型
        self.value = value  # 词法单元值

    def __repr__(self):
        return f"Token({self.type}, {self.value})"

class Lexer:
    def __init__(self, text):
        self.text = text
        self.pos = 0
        self.current_char = self.text[self.pos] if self.pos < len(self.text) else None

    def error(self):
        raise Exception(f"Invalid character: {self.current_char}")

    def advance(self):
        """前进到下一个字符"""
        self.pos += 1
        self.current_char = self.text[self.pos] if self.pos < len(self.text) else None

    def skip_whitespace(self):
        """跳过空白符"""
        while self.current_char is not None and self.current_char.isspace():
            self.advance()

    def number(self):
        """识别数字"""
        result = []
        while self.current_char is not None and (self.current_char.isdigit() or self.current_char == '.'):
            result.append(self.current_char)
            self.advance()
        return ''.join(result)

    def identifier(self):
        """识别标识符"""
        result = []
        while self.current_char is not None and (self.current_char.isalnum() or self.current_char == '_'):
            result.append(self.current_char)
            self.advance()
        return ''.join(result)

    def get_next_token(self):
        """获取下一个词法单元"""
        while self.current_char is not None:
            if self.current_char.isspace():
                self.skip_whitespace()
                continue

            if self.current_char.isdigit():
                return Token('num', self.number())

            if self.current_char.isalpha() or self.current_char == '_':
                return Token('id', self.identifier())

            if self.current_char == '+':
                self.advance()
                return Token('+', '+')

            if self.current_char == '-':
                self.advance()
                return Token('-', '-')

            if self.current_char == '*':
                self.advance()
                return Token('*', '*')

            if self.current_char == '/':
                self.advance()
                return Token('/', '/')

            if self.current_char == '(':
                self.advance()
                return Token('(', '(')

            if self.current_char == ')':
                self.advance()
                return Token(')', ')')

            self.error()

        return Token('EOF', None)

4.3 递归下降分析器实现

现在，我们使用Python实现递归下降分析器：

# parser.py
from lexer import Lexer, Token

class Parser:
    def __init__(self, lexer):
        self.lexer = lexer
        self.current_token = self.lexer.get_next_token()

    def error(self):
        raise Exception(f"Syntax error at token {self.current_token}")

    def eat(self, token_type):
        """匹配当前词法单元，如果匹配则前进，否则报错"""
        if self.current_token.type == token_type:
            self.current_token = self.lexer.get_next_token()
        else:
            self.error()

    def factor(self):
        """factor : ( expr ) | id | num"""
        token = self.current_token
        if token.type == '(':
            self.eat('(')
            result = self.expr()
            self.eat(')')
            return result
        elif token.type == 'id':
            self.eat('id')
            return f"id({token.value})"
        elif token.type == 'num':
            self.eat('num')
            return f"num({token.value})"
        else:
            self.error()

    def term_tail(self):
        """term_tail : * factor term_tail | / factor term_tail | ε"""
        token = self.current_token
        if token.type == '*':
            self.eat('*')
            factor_val = self.factor()
            tail_val = self.term_tail()
            return f"*({factor_val}, {tail_val})"
        elif token.type == '/':
            self.eat('/')
            factor_val = self.factor()
            tail_val = self.term_tail()
            return f"/({factor_val}, {tail_val})"
        else:
            return "ε"

    def term(self):
        """term : factor term_tail"""
        factor_val = self.factor()
        tail_val = self.term_tail()
        if tail_val == "ε":
            return factor_val
        else:
            return f"term({factor_val}, {tail_val})"

    def expr_tail(self):
        """expr_tail : + term expr_tail | - term expr_tail | ε"""
        token = self.current_token
        if token.type == '+':
            self.eat('+')
            term_val = self.term()
            tail_val = self.expr_tail()
            return f"+({term_val}, {tail_val})"
        elif token.type == '-':
            self.eat('-')
            term_val = self.term()
            tail_val = self.expr_tail()
            return f"-({term_val}, {tail_val})"
        else:
            return "ε"

    def expr(self):
        """expr : term expr_tail"""
        term_val = self.term()
        tail_val = self.expr_tail()
        if tail_val == "ε":
            return term_val
        else:
            return f"expr({term_val}, {tail_val})"

    def parse(self):
        """开始分析"""
        return self.expr()

# 测试代码
if __name__ == "__main__":
    while True:
        try:
            text = input("Enter expression: ")
            if not text:
                continue
            lexer = Lexer(text)
            parser = Parser(lexer)
            result = parser.parse()
            print(f"Parse tree: {result}")
        except Exception as e:
            print(f"Error: {e}")
            continue

4.4 测试示例

测试1：简单表达式

输入：

3 + 4 * 2

输出：

Parse tree: expr(num(3), +(term(num(4), *(num(2), ε)), ε))

测试2：带括号的表达式

输入：

(3 + 4) * 2

输出：

Parse tree: term((expr(num(3), +(num(4), ε))), *(num(2), ε))

测试3：复杂表达式

输入：

x + y * (z - 1)

输出：

Parse tree: expr(id(x), +(term(id(y), *(expr(id(z), -(num(1), ε)), ε)), ε))

5. 递归下降分析中的错误处理

5.1 错误处理的重要性

在实际的编译器中，错误处理是非常重要的，因为：

• 它可以帮助程序员快速定位和修正语法错误
• 它可以使编译器在遇到错误时继续分析，发现更多错误
• 它可以提高编译器的用户友好性

5.2 错误处理策略

恐慌模式恢复：

• 当遇到错误时，跳过输入符号直到找到一个同步符号（如分号、右括号等）
• 然后从同步符号开始继续分析

错误产生式：

• 在文法中添加专门处理常见错误的产生式
• 当遇到错误时，使用这些产生式进行恢复

错误预测：

• 根据当前的分析状态，预测可能的错误并提供有意义的错误信息

5.3 错误处理示例

def factor(self):
    """factor : ( expr ) | id | num"""
    token = self.current_token
    if token.type == '(':
        self.eat('(')
        result = self.expr()
        if self.current_token.type != ')':
            print(f"Error: Expected ')', found {self.current_token.type}")
            # 恐慌模式恢复：跳过直到找到 ')'
            while self.current_token.type != ')' and self.current_token.type != 'EOF':
                self.current_token = self.lexer.get_next_token()
            if self.current_token.type == ')':
                self.eat(')')
        else:
            self.eat(')')
        return result
    elif token.type == 'id':
        self.eat('id')
        return f"id({token.value})"
    elif token.type == 'num':
        self.eat('num')
        return f"num({token.value})"
    else:
        print(f"Error: Expected '(', id, or num, found {token.type}")
        # 恐慌模式恢复：跳过当前符号
        self.current_token = self.lexer.get_next_token()
        return "error"

6. 左递归的处理

6.1 直接左递归

直接左递归是指产生式的右部以该非终结符开头，例如：

A → Aα | β

可以转换为：

A → βA'
A' → αA' | ε

6.2 间接左递归

间接左递归是指通过多个产生式的推导形成的左递归，例如：

A → Bα | γ
B → Aβ | δ

可以通过以下步骤消除：

1. 将文法中的非终结符排序为 A1, A2, ..., An
2. 对每个 i 从 1 到 n：
   • 对每个 j 从 1 到 i-1：
     • 将 Aj 的产生式代入 Ai 的产生式中
   • 消除 Ai 产生式中的直接左递归
3. 简化产生式，去除无用的产生式

7. 回溯的处理

7.1 回溯的概念

回溯是指在选择产生式时，选择了错误的产生式，需要回退到之前的状态并尝试其他产生式的过程。

7.2 回溯的优缺点

优点：

• 可以处理非LL(1)文法
• 实现简单

缺点：

• 效率低下，可能导致指数级的时间复杂度
• 错误定位困难

7.3 避免回溯的方法

• 使用LL(1)文法
• 提取左因子
• 使用预测分析表

8. 自测题

1. 递归下降分析器的基本原理是什么？

2. 什么是LL(1)文法？它有什么要求？

3. 如何计算FIRST集和FOLLOW集？

4. 递归下降分析器如何处理左递归？

5. 编写一个简单的递归下降分析器，处理以下文法：

   S → if ( E ) S | while ( E ) S | { L }
   L → S L | ε
   E → T E'
   E' → + T E' | - T E' | ε
   T → id | num

9. 小结

在本集中，我们介绍了递归下降分析器的基本原理、实现方法和应用场景。递归下降分析器是一种自顶向下的语法分析方法，它为文法中的每个非终结符编写一个递归函数，通过递归调用这些函数来处理输入符号串。我们还介绍了LL(1)文法的概念、FIRST集和FOLLOW集的计算，以及如何处理递归下降分析中的左递归和回溯问题。通过Python实现的简单表达式分析器，我们展示了递归下降分析器的实际应用。

10. 下集预告

下一集将介绍 LL(1)预测分析器，这是一种基于分析表的自顶向下分析方法，它通过预先计算的分析表来决定每一步应该使用哪个产生式，避免了递归下降分析中的回溯问题，提高了分析效率。

11. 参考资料

1. 《编译原理》（龙书），Alfred V. Aho 等著
2. 《编译原理教程》，蒋立源等著
3. 《编译器设计》，Alexander A. Stepanov 等著
4. Recursive Descent Parsing - Wikipedia：https://en.wikipedia.org/wiki/Recursive_descent_parser
5. LL Parser - Wikipedia：https://en.wikipedia.org/wiki/LL_parser