LL(1) 与 LR(1) 文法分析器对比：从理论到 5 个典型考题实战-尧图网络科技

LL(1) 与 LR(1) 文法分析器深度解析：从理论到典型考题实战

在编译原理的学习中，语法分析器是理解编程语言如何被计算机"读懂"的关键环节。LL(1)和LR(1)作为两种主流的自顶向下和自底向上分析技术，各自展现出独特的优势与适用场景。本文将深入探讨它们的核心差异，并通过典型考题演示实际应用技巧。

1. 基础概念与核心差异

LL(1)分析器采用自顶向下的分析策略，其名称中的第一个"L"表示从左到右扫描输入，第二个"L"代表最左推导，而"(1)"意味着只需向前查看一个符号。这种分析器在实现递归下降解析时表现出色，特别适合处理结构清晰的声明式语言。

与之相对的LR(1)分析器采用自底向上的方法，其中"L"表示从左到右扫描，"R"代表最右推导，"(1)"同样表示前瞻一个符号。它能处理更复杂的文法，常被用于现代编译器构建。

二者的核心差异体现在几个关键维度：

特性	LL(1)	LR(1)
分析方向	自顶向下	自底向上
分析表构建	基于FIRST和FOLLOW集	基于项目集规范族
文法限制	不能处理左递归和歧义	能处理更广泛的文法
错误检测	较早检测错误	较晚但更精确的错误定位
实现复杂度	相对简单	较为复杂

提示：选择分析器类型时，应考虑语言复杂度与开发效率的平衡。LL(1)适合快速原型开发，而LR(1)更适合工业级编译器。

2. 构建过程对比

2.1 LL(1)分析表的构建步骤

构建LL(1)分析表需要系统性地计算相关集合：

消除左递归：将形如A → Aα | β的文法转换为A → βA'，A' → αA' | ε
提取左公因子：处理如A → αβ1 | αβ2的情况
计算FIRST集：
- 对于终结符a，FIRST(a) = {a}
- 对于非终结符A，考虑所有产生式A→α，FIRST(A)包含FIRST(α)
- 若A→ε，则ε ∈ FIRST(A)
计算FOLLOW集：
- 对于开始符号S，将$加入FOLLOW(S)
- 若有产生式B → αAβ，则FIRST(β)-{ε}加入FOLLOW(A)
- 若有B → αA或(B → αAβ且ε ∈ FIRST(β))，则FOLLOW(B)加入FOLLOW(A)
构造分析表：
- 对每个产生式A → α，将A → α加入表项M[A,b]，其中b ∈ FIRST(α)
- 若ε ∈ FIRST(α)，则对每个b ∈ FOLLOW(A)，将A → α加入M[A,b]

# FIRST集计算示例（伪代码） def compute_first(grammar): first = {} for non_terminal in grammar.non_terminals: first[non_terminal] = set() changed = True while changed: changed = False for production in grammar.productions: A = production.lhs for symbol in production.rhs: if symbol.is_terminal: if symbol not in first[A]: first[A].add(symbol) changed = True break else: added = len(first[A]) first[A].update(first[symbol] - {'ε'}) if 'ε' not in first[symbol]: break if len(first[A]) != added: changed = True else: if 'ε' not in first[A]: first[A].add('ε') changed = True return first

2.2 LR(1)分析器的构建过程

LR(1)分析器的构建更为复杂，主要步骤如下：

构造LR(1)项目集规范族：
- 初始项目[S'→·S, $]的闭包
- 通过GOTO函数计算状态转移
构造分析表：
- ACTION表：对终结符a，若[A→α·aβ, b]在I中，则ACTION[I,a]=移进j
- GOTO表：对非终结符A，GOTO[I,A]=j
- 归约项：对[A→α·, a]，将ACTION[I,a]设为按A→α归约
- 接受项：对[S'→S·, $]，设为接受

典型冲突类型包括移进-归约冲突和归约-归约冲突，这些冲突通常意味着文法不是LR(1)的。

3. 典型考题解析

3.1 非LL(1)文法的处理

考虑以下文法：

S → aSb | ab

步骤分析：

计算FIRST集：
- FIRST(S) = {'a'}
计算FOLLOW集：
- FOLLOW(S) = {'b', '$'}
构造分析表时发现冲突：
- 对输入'a'，两个产生式都有a ∈ FIRST(α)

解决方案：

提取左公因子：

S → aS' S' → Sb | b

重新计算分析表后冲突消除

3.2 LR(1)分析中的状态转换

给定文法：

0. S' → S 1. S → CC 2. C → cC 3. C → d

构造LR(1)项目集时，关键状态I0包含：

[S'→·S, $] [S→·CC, $] [C→·cC, c/d] [C→·d, c/d]

状态转移示例：

在I0遇到c时转移到I2：

[C→c·C, c/d] [C→·cC, c/d] [C→·d, c/d]

3.3 综合应用题解析

题目：判断文法是否属于LL(1)或LR(1)，并给出分析过程。

文法：

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

解题步骤：

LL(1)分析：
- 存在左递归，直接判定不是LL(1)
- 消除左递归后：
```
E → TE' E' → +TE' | ε T → FT' T' → *FT' | ε F → (E) | id
```
- 计算FIRST和FOLLOW集后可构造无冲突分析表
LR(1)分析：
- 直接构造LR(1)项目集
- 检查无冲突，故是LR(1)文法
- 典型状态包含如：
```
[E→E·+T, $] [T→T·*F, +/$]
```