中卫市网站建设_网站建设公司_ASP.NET_seo优化

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

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

1. FIRST(α) 与 FIRST(β) 不相交（即不能推出以相同终结符开头的串）；
2. α 和 β 最多只有一个可以推导出空串 ε；
3. 若 β ⇒ ε，则 α 不能推导出以 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(α)。

计算规则：

1. 若 X 是终结符：
   FIRST(X) = {X}

2. 若 X 是非终结符且有产生式 X → Y₁Y₂…Yₖ：

   • 将 FIRST(Y₁) 中所有非 ε 元素加入 FIRST(X)；
   • 若 Y₁ ⇒ ε，则加入 FIRST(Y₂)，依此类推；
   • 若所有 Yᵢ 都可推出 ε，则 ε ∈ FIRST(X)

3. 若 X → ε 是一个产生式：
   则 ε ∈ FIRST(X)

4. 重复迭代直到所有集合不再变化

手动计算步骤：

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

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

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

计算规则：

1. 对文法开始符号 S，初始化 FOLLOW(S) 包含 #，即 # ∈ FOLLOW(S)

2. 若存在产生式 A → αBβ：

   • 将 FIRST(β) 中除 ε 外的所有元素加入 FOLLOW(B)
   • 如果 β ⇒ ε（即 ε ∈ FIRST(β)），则将 FOLLOW(A) 加入 FOLLOW(B)

3. 若存在产生式 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 集：

1. FOLLOW(E) 包含 #（因为 E 是开始符号）

2. E → T E’ ⇒ FOLLOW(T) 加入 FIRST(E’) \ {ε} = {‘+’}；因 E’ ⇒ ε，故 FOLLOW(T) 还需加入 FOLLOW(E)
   → FOLLOW(T) = {‘+’, #}

3. E’ → + T E’ ⇒ FOLLOW(T) 已处理；由 E’ 在末尾 ⇒ FOLLOW(E’) = FOLLOW(E) = {#, ‘)’}
   （注意：E 出现在 ( E ) 中，所以 ‘)’ ∈ FOLLOW(E)）

4. T → F T’ ⇒ FOLLOW(F) 加入 FIRST(T’) \ {ε} = {‘‘}；因 T’ ⇒ ε ⇒ FOLLOW(F) 加入 FOLLOW(T)
   → FOLLOW(F) = {'’, ‘+’, #}

5. T’ → * F T’ ⇒ FOLLOW(F) 已处理；T’ 在末尾 ⇒ FOLLOW(T’) = FOLLOW(T) = {‘+’, #}

6. F → ( E ) ⇒ FOLLOW(E) 加入 ‘)’

最终结果：

• FOLLOW(E) = {#, )}
• FOLLOW(E’) = {#, )}
• FOLLOW(T) = {+, #, )}
• FOLLOW(T’) = {+, #, )}
• FOLLOW(F) = {*, +, #, )}

这些集合可用于构建 LL(1) 分析表，确保每个 [非终结符, 输入符号] 组合至多对应一个产生式。