9 只生成语法分析之自顶向下与自底向上的解析

在编译器设计的过程中，语法分析是一个至关重要的阶段。本篇文章将深入探讨 自顶向下 和 自底向上 的解析方法。这两种解析技术是实现语法分析的核心技术，理解它们对后续的 语义分析 阶段是非常重要的。

自顶向下解析

自顶向下解析，顾名思义，是从语法树的根部开始，逐步向下展开的过程。它使用 递归下降 或者 预测分析 方法来构建语法树。

递归下降解析

递归下降解析 是一种通过设计函数来对应文法非终结符的解析方法。每个文法规则都可以用一个函数来表示。这种方法简洁直观，但需要满足文法的某些性质，如 无左递归 和 适配。

例子

假设我们有以下文法：

E → E + T | T
T → T * F | F
F → ( E ) | id

对于这个文法，我们可以为 E、T 和 F 创建三个函数。下面是一个简单的伪代码示例：

def parse_E():
    parse_T()
    while current_token == '+':
        consume_token('+')
        parse_T()

def parse_T():
    parse_F()
    while current_token == '*':
        consume_token('*')
        parse_F()

def parse_F():
    if current_token == '(':
        consume_token('(')
        parse_E()
        consume_token(')')
    else:
        consume_token('id')

预测分析

预测分析 是一种更主动的自顶向下解析方法，它通过构建一个 预测分析表 来决定采用哪个文法规则。LL(1) 文法是很适合使用预测分析的一类文法，其中的 1 表示考虑一个输入符号来做决策。

构建预测分析表的步骤包括：

1. 计算 FIRST 集合: 每个文法符号的所有可能的开始符号。
2. 计算 FOLLOW 集合: 每个非终结符后可能出现的符号。
3. 填充预测分析表: 根据 FIRST 和 FOLLOW 集合来决定状态转移。

自底向上解析

相对于自顶向下解析，自底向上解析是从输入符号开始，逐步向上构建语法树直至根部。最常用的自底向上解析方法是 LR 解析，尤其是 SLR（简单的 LR）和 LALR（Look-Ahead LR），是较为常见的策略。

LR 解析

LR 解析器通过维护一个状态栈来处理输入符号。解析过程中包含两个主要操作：

1. 移进: 将当前输入符号推入栈中。
2. 归约: 根据栈顶符号与预测分析表进行比对，发现完整的文法规则后进行归约。

例子

同样使用上面的文法，我们可以实现一个 LR 解析器。下列伪代码展示了 LR 解析的基本逻辑：

stack = []
input_stack = tokenize(input_string)  # 假设已实现的分词功能

while True:
    state = get_current_state(stack)
    action = parse_table[state][next_token]

    if action == 'shift':
        stack.append(next_token)  # 移进
        next_token = next_input()  # 获取下一个输入符号
    elif action == 'reduce':
        rule = get_rule(stack)  # 获取要归约的规则
        stack = reduce_stack(stack, rule)  # 归约栈
    elif action == 'accept':
        print("解析成功")
        break
    else:
        print("解析失败")
        break

小结

在本篇中，我们讨论了 自顶向下 和 自底向上 的解析方法。自顶向下 方法如递归下降解析和预测分析，对于简单文法易于实现，但对于复杂文法则可能存在局限。而 自底向上 的 LR 解析法在处理更复杂的语法时表现更为出色。

接下来，我们将进入 语义分析 的阶段，探讨其基本概念以及如何在语法分析的基础上进行有效的语义检查与处理。具体内容将涵盖如何通过语法树进行类型检查、作用域管理等方面的内容，以确保程序的语义正确性。