提取公共左因子和LL(1)文法的定义是编译原理中自顶向下语法分析的核心技术-编程实验室

提取公共左因子和LL(1)文法的定义是编译原理中自顶向下语法分析的核心技术。当一个非终结符有多个产生式具有相同的前缀（如A → αβ₁|αβ₂），会导致预测分析器无法确定应选择哪个产生式，从而引发“选择候选式”歧义。通过提取公共左因子，将原产生式重构为A → αA’ 和 A’ → β₁|β₂|…|βₙ，消除了这种前缀冲突，使文法更适合自顶向下分析。

LL(1)文法要求对任意两个关于同一非终结符的不同产生式A → α 和 A → β，必须满足三个条件：

FIRST(α) 与 FIRST(β) 不相交（即不能推出以相同终结符开头的串）；
α 和 β 最多只有一个可以推导出空串 ε；
若 β ⇒ ε，则 α 不能推导出以 FOLLOW(A) 中符号开头的串。

这些条件确保了在每一步分析中，仅凭当前输入符号（向前看1个符号）即可唯一确定使用的产生式，从而实现确定性预测分析。

FIRST集用于确定从某符号序列能推导出的第一个终结符，而FOLLOW集则表示某非终结符后可能出现的终结符。它们共同用于构建LL(1)分析表：对于每个产生式A → α，将该产生式填入分析表中[A, a]位置，其中a ∈ FIRST(α)；若ε ∈ FIRST(α)，还需将产生式填入[A, b]，b ∈ FOLLOW(A)。

这些机制是构造高效、无回溯的语法分析器的基础，广泛应用于现代编译器设计中。
手动计算 FIRST 集和 FOLLOW 集是编译原理中构造 LL(1) 分析表的关键步骤。以下是系统性的计算方法：

一、FIRST 集的定义与计算规则

定义：
对于文法符号串 α，FIRST(α) 是从 α 能够推导出的所有串的第一个终结符的集合。如果 α ⇒ ε，则 ε ∈ FIRST(α)。

计算规则：

若 X 是终结符：
FIRST(X) = {X}
若 X 是非终结符且有产生式 X → Y₁Y₂…Yₖ：
- 将 FIRST(Y₁) 中所有非 ε 元素加入 FIRST(X)；
- 若 Y₁ ⇒ ε，则加入 FIRST(Y₂)，依此类推；
- 若所有 Yᵢ 都可推出 ε，则 ε ∈ FIRST(X)
若 X → ε 是一个产生式：
则 ε ∈ FIRST(X)
重复迭代直到所有集合不再变化

手动计算步骤：

初始化每个符号的 FIRST 集为空。
对每条产生式，应用上述规则。
反复扫描所有产生式，更新 FIRST 集，直到稳定（不动点）。

二、FOLLOW 集的定义与计算规则

定义：
FOLLOW(A) 是在某个句型中可能紧跟在非终结符 A 后面的终结符集合。若 A 可能在句型最右端出现，则 # ∈ FOLLOW(A)（# 表示输入结束符）。

计算规则：

对文法开始符号 S，初始化 FOLLOW(S) 包含 #，即 # ∈ FOLLOW(S)
若存在产生式 A → αBβ：
- 将 FIRST(β) 中除 ε 外的所有元素加入 FOLLOW(B)
- 如果 β ⇒ ε（即 ε ∈ FIRST(β)），则将 FOLLOW(A) 加入 FOLLOW(B)
若存在产生式 A → αB（即 B 在产生式右部末尾）：
- 则将 FOLLOW(A) 加入 FOLLOW(B)

注意：FOLLOW 集只包含终结符或 #，不包含 ε

手动计算步骤：

初始化所有 FOLLOW 集为空，FOLLOW(S) 添加 #
反复遍历所有产生式，应用规则 2 和 3
直到所有 FOLLOW 集不再变化为止

三、示例演示

考虑文法 G：

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

计算 FIRST 集：

FIRST(id) = {id}, FIRST(‘(’) = {‘(’}, FIRST(‘)’) = {‘)’}, FIRST(‘+’) = {‘+’}, FIRST(‘‘) = {’’}
F → id | ( E ) ⇒ FIRST(F) = {id, ‘(’}
T’ → * F T’ | ε ⇒ FIRST(T’) = {‘*’, ε}
T → F T’ ⇒ FIRST(T) = FIRST(F) = {id, ‘(’}（因为 F 不含 ε）
E’ → + T E’ | ε ⇒ FIRST(E’) = {‘+’, ε}
E → T E’ ⇒ FIRST(E) = FIRST(T) = {id, ‘(’}

✅ 最终 FIRST 结果：

FIRST(E) = {id, ‘(’}
FIRST(E’) = {‘+’, ε}
FIRST(T) = {id, ‘(’}
FIRST(T’) = {‘*’, ε}
FIRST(F) = {id, ‘(’}

计算 FOLLOW 集：

FOLLOW(E) 包含 #（因为 E 是开始符号）
E → T E’ ⇒ FOLLOW(T) 加入 FIRST(E’) \ {ε} = {‘+’}；因 E’ ⇒ ε，故 FOLLOW(T) 还需加入 FOLLOW(E)
→ FOLLOW(T) = {‘+’, #}
E’ → + T E’ ⇒ FOLLOW(T) 已处理；由 E’ 在末尾 ⇒ FOLLOW(E’) = FOLLOW(E) = {#, ‘)’}
（注意：E 出现在 ( E ) 中，所以 ‘)’ ∈ FOLLOW(E)）
T → F T’ ⇒ FOLLOW(F) 加入 FIRST(T’) \ {ε} = {‘‘}；因 T’ ⇒ ε ⇒ FOLLOW(F) 加入 FOLLOW(T)
→ FOLLOW(F) = {'’, ‘+’, #}
T’ → * F T’ ⇒ FOLLOW(F) 已处理；T’ 在末尾 ⇒ FOLLOW(T’) = FOLLOW(T) = {‘+’, #}
F → ( E ) ⇒ FOLLOW(E) 加入 ‘)’

最终结果：