编译技术4-2

🌟 LL(1) 文法识别的四个步骤 Four Steps to Recognize LL(1) Grammar

识别一个文法是否是 LL(1) 的过程，通常包含以下四步：

  1. 计算 nullable 非终结符（Can derive ε）
  2. 计算 FIRST 集（First terminals that can appear）
  3. 计算 FOLLOW 集（Terminals that can follow a nonterminal）
  4. 根据 LL(1) 的定义进行判断（判断是否满足 LL(1) 条件）

🔶 第一步：计算 Nullable 非终结符（a. Compute Nullable）

✨ 什么是 Nullable？

中文定义： 一个非终结符 A 如果可以推导出 ε（即空串），那么我们称 A 是 “nullable” 的。

英文定义： A nonterminal A is nullable if there exists a derivation:  A ⇒* ε

📜 算法步骤（Algorithm Steps）

我们用一个集合 U 来存储所有 nullable 的非终结符：

Step 1：

首先，把所有右边 直接是 ε 的产生式左边的非终结符加到集合 U 里：

1
U = { A | A → ε 是一个产生式 }

Step 2：

然后对每条产生式 A → X₁ X₂ … Xₙ， 如果右边的每个符号 Xi 都在 U 中（也都是 nullable），那么 A 本身也是 nullable，把它加进 U。

Step 3：

重复 Step 2，直到 U 不再发生变化为止（固定点算法）。

✅ 示例讲解（Example）

给定文法 G[S]：

1
2
3
4
5
S → AB | bC
A → b | ε
B → aD | ε
C → AD | b
D → aS | c

我们一步步计算：

初始集合：

从直接可推出 ε 的产生式入手：

  • A → ε ⇒ A 是 nullable
  • B → ε ⇒ B 是 nullable
1
初始 U = { A, B }

第一次遍历所有产生式：

看哪些新的非终结符可以变成 ε：

  • S → AB，因为 A 和 B 都是 nullable，所以 S 是 nullable！

更新集合：

1
U = { A, B, S }

第二次遍历：

再检查一遍，但这次没有新的符号能加入了，所以停止：

1
最终 nullable 集合：{ A, B, S }

🧠 小结（Summary）

符号 是否 Nullable 理由
A ✅ 是 A → ε
B ✅ 是 B → ε
S ✅ 是 S → AB 且 AB 都 nullable
C ❌ 否 没有能导出 ε 的路径
D ❌ 否 右边都不能导出 ε

🔍 英文总结 (English Summary)

  • Nullable nonterminals are those that can derive ε.
  • To compute them, start from direct ε-productions and use fixed-point iteration.
  • This information is critical for building FIRST and FOLLOW sets, which are needed for LL(1) analysis.

🔷 LL(1) 语法分析中的步骤 b：计算 FIRST(α)

💡 英文定义（Definition in English）：

The FIRST set of a string α (which can be terminals and/or nonterminals) is the set of terminals that begin the strings derivable from α. 如果 α 能够推导出 ε，那么 ε 也属于 FIRST(α)。

✅ Step-by-Step Algorithm for Computing FIRST(A)

💬 1. For Terminals：

For any terminal a ∈ VT, FIRST(a) = { a } 👉终结符的 FIRST 集就是它自己。

💬 2. For Nonterminals：

For a nonterminal A ∈ VN:

  • If A ⇒* ε (A 是 nullable)，那么 ε ∈ FIRST(A)。
  • 初始时令 FIRST(A) = ∅。
  • 对于每个产生式 A → X1X2…Xn，计算 SectionFirst(X1X2…Xn) 并加入到 FIRST(A) 中。

重复此过程，直到所有的 FIRST 集都不再变化（达到稳定）。

🔍 如何计算 SectionFirst(X1X2…Xn)

也就是右侧字符串的 FIRST 集

算法规则（中英文对照）：

条件 SectionFirst 结果 中文解释
如果 X1 不是 nullable FIRST(X1) 只看第一个符号
如果 X1 是 nullable (FIRST(X1) - {ε}) ∪ FIRST(X2) 继续看下一个符号
如果 X1, ..., Xn 都是 nullable (所有符号的 FIRST 集减去 ε) ∪ {ε} 最后加上 ε

📘 例子：G[S]

1
2
3
4
5
S → AB | bC
A → b | ε
B → aD | ε
C → AD | b
D → aS | c

🧩 1. Nullable 非终结符集合：

{A, B, S}（你之前已经算出来了）

🧮 2. FIRST 集计算（手动展开）：

FIRST(b) = {b}

FIRST(a) = {a}

FIRST(c) = {c}

FIRST(A)

A → b | ε 所以： FIRST(A) = {b, ε}

FIRST(B)

B → aD | ε 所以： FIRST(B) = {a, ε}

FIRST(C)

C → AD | b 要计算 FIRST(AD)：

  • A 的 FIRST 是 {b, ε}
  • D 的 FIRST 需要先算出来（D → aS | c）

→ FIRST(D)

D → aS | c FIRST(D) = {a, c}

那么： FIRST(C) = FIRST(AD) ∪ FIRST(b) → AD 中 A 是 nullable，继续看 D → FIRST(AD) = (FIRST(A) - {ε}) ∪ FIRST(D) = {b} ∪ {a, c} = {a, b, c} → 加上 b：{a, b, c}

FIRST(C) = {a, b, c}

FIRST(S)

S → AB | bC

  • AB：A 和 B 都 nullable → FIRST(AB) = (FIRST(A) - {ε}) ∪ (FIRST(B) - {ε}) ∪ {ε} = {b} ∪ {a} ∪ {ε} = {a, b, ε}
  • bC：FIRST(b) = {b}

FIRST(S) = {a, b, ε}

✅ 总结：所有 FIRST 集

符号 FIRST 集
A {b, ε}
B {a, ε}
C {a, b, c}
D {a, c}
S {a, b, ε}
b {b}
a {a}
c {c}
img

📝 中文概括总结

什么是 FIRST 集？

FIRST 集就是：一个符号串可以推导出的串的第一个终结符。 如果这个串能推出空串 ε，FIRST 集也包含 ε。

如何计算？

  1. 终结符的 FIRST 集是它自己。
  2. 非终结符要看它的产生式右边：
    • 从左往右看；
    • 如果遇到能推出 ε 的符号，就继续看下一个；
    • 如果所有符号都能推出 ε，最后把 ε 加进去。

LL(1) 文法分析第二步：计算 FIRST 集合详细笔记

🌐 Definition (English)

The FIRST set of a string α (which may include terminals and nonterminals) is the set of terminals that begin the strings derivable from α. If α ⇒* ε, then ε ∈ FIRST(α).

⭐ 定义：什么是 FIRST 集？

FIRST(α)* 是指：一个符号串能*推导出的一些串中，最前面出现的第一个终符号的集合。如果能推导出空串（ε），那么 ε 也属于 FIRST(α)。

🔹 第二步：计算非终符号的 FIRST 集 (First Sets for Nonterminals)

根据文法 G[S]：

1
2
3
4
5
S → AB | bC
A → b | ε
B → aD | ε
C → AD | b
D → aS | c

已经计算出来：

Symbol FIRST Set
S {a, b, ε}
A {b, ε}
B {a, ε}
C {a, b, c}
D {a, c}

🔹 第三步：计算产生式右侧字符串的 FIRST 集

🔍 如何计算 FIRST(X1X2...Xn)？

  1. 如果 X1 不是 nullable，那么 FIRST(α) = FIRST(X1)
  2. 如果 X1 是 nullable，续续往后看 X2, X3...
  3. 如枟 X1 到 Xn 全部是 nullable，那么结果加上 ε

💲 实际计算例子：

➡ S → AB

  • FIRST(A) = {b, ε}
  • A 是 nullable，继续看 B
  • FIRST(B) = {a, ε}
  • B 也是 nullable
  • 部分求和：(FIRST(A) - {ε}) ∪ (FIRST(B) - {ε}) ∪ {ε} = {b} ∪ {a} ∪ {ε} = {a, b, ε}

➡ S → bC

  • b 是终符号，FIRST(bC) = FIRST(b) = {b}

➡ A → ε

  • FIRST(ε) = {ε}

➡ A → b

  • FIRST(b) = {b}

➡ C → AD

  • FIRST(A) = {b, ε}，A 是 nullable，看 D
  • FIRST(D) = {a, c}
  • FIRST(AD) = (FIRST(A)-{ε}) ∪ FIRST(D) = {b} ∪ {a, c} = {a, b, c}

➡ D → aS

  • a 是终符号，FIRST(aS) = {a}

🎓 总结 (Summary)

产生式 FIRST 集
S → AB {a, b, ε}
S → bC {b}
A → ε {ε}
A → b {b}
C → AD {a, b, c}
D → aS {a}

📘 FOLLOW 集计算算法（中英文详细笔记）

✅ 步骤 Step-by-step（计算每个非终结符的 FOLLOW 集）：

🍀 定义 Definition

FOLLOW(A)：表示在某些推导中紧跟在非终结符 A 后面的终结符集合。

Intuitively（直观理解）：FOLLOW(A) 是所有可能在 A 之后出现的终结符，包括输入结束符 ``。

🔢 算法步骤 Algorithm Steps

  1. 初始化 Initialization：
    • FOLLOW(S) = { $ }（S 是开始符号）
    • 对于其他所有非终结符 A ≠ S，FOLLOW(A) = { }
  2. 遍历每条产生式 B → αAγ（A 是非终结符）：
      1. 将 FIRST(γ) - {ε} 加入到 FOLLOW(A)
      1. 如果 ε ∈ FIRST(γ)，则将 FOLLOW(B) 加入到 FOLLOW(A)
  3. 重复步骤 2，直到所有 FOLLOW 集不再改变（达到固定点）

🔍 为什么 Follow(B) 会传给 Follow(A)?

假设 B → αAγ 是某条产生式，而 γ 能推导出 ε：

  • 这意味着整个 γ 可以“消失”，那么 FOLLOW(B) 中本该出现在 γ 后面的符号现在就可能直接跟在 A 后面。
  • 所以 FOLLOW(B) 应该加入到 FOLLOW(A)。

例子说明：

  • 若 b ∈ FOLLOW(B)
  • B → αAγ，且 γ ⇒* ε
  • 那么 S ⇒* …Bb… ⇒* …αAb…
  • 说明 b 也在 FOLLOW(A) 中

🧪 示例：G[S] 文法

1
2
3
4
5
6
7
8
9
10
[1] S → AB
[2] S → bC
[3] A → b
[4] A → ε
[5] B → aD
[6] B → ε
[7] C → AD
[8] C → b
[9] D → aS
[10] D → c

✅ First 集回顾：

1
2
3
First(S)={a,b,ε}   First(A)={b,ε}
First(B)={a,ε}     First(C)={a,b,c} 
First(D)={a,c}

🔁 FOLLOW 集初始化：

1
2
3
4
5
FOLLOW(S) = { $ }
FOLLOW(A) = { }
FOLLOW(B) = { }
FOLLOW(C) = { }
FOLLOW(D) = { }

🔁 Step-by-step 更新：

  • [1] S → AB
    • FOLLOW(A) += FIRST(B) - {ε} = {a}
    • 因为 B 是句尾，B 可为空（B → ε），FOLLOW(B) += FOLLOW(S) = { $ }
    • A 后接 B，可为空 ⇒ FOLLOW(A) += FOLLOW(S) = { $ }
  • [2] S → bC
    • FOLLOW(C) += FOLLOW(S) = { $ }
  • [7] C → AD
    • FOLLOW(A) += FIRST(D) - {ε} = {a, c}
    • D 不是可空 ⇒ 不加 FOLLOW(C)
  • [9] D → aS
    • FOLLOW(S) += FOLLOW(D)
  • [5] B → aD
    • FOLLOW(D) += FOLLOW(B)

🧮 最终结果（经过多轮迭代）

1
2
3
4
5
FOLLOW(S) = { $, a }
FOLLOW(A) = { $, a, c }
FOLLOW(B) = { $ }
FOLLOW(C) = { $ }
FOLLOW(D) = { $ }

✅ 总结 Summary

  • FOLLOW 集帮助我们决定 何时可以使用 ε 产生式。
  • 若 FIRST(α) 包含 ε，那么必须检查 FOLLOW(A) 来判断是否该用 A → ε。

LL(1) Grammar Recognition - Detailed Notes with Chinese Translation

Summary Note / 简要笔记

  • $ $ (epsilon) 是 First 集的元素，但不是 Follow 集的元素
  • First 集定义于 "组合符号串" （可以是符号串）和非终结符号；Follow 集只定义于非终结符号

d. Recognize based on the definition of LL(1)

Definition of LL(1) Grammar / LL(1) 文法的定义

A grammar is LL(1) if the following conditions are satisfied:

  1. For each nonterminal $ A $ and each pair of its productions $ A _i | _j $, $ First(_i) First(_j) = $
    • 每个非终结符号 A 的两个产生式之间，它们形成的 First 集不能有交集
  2. If $ First(_i) $，then $ First(_i) Follow(A) = $
    • 如果有产生式可以退化为空，则 First(A) 与 Follow(A) 也不能有交集

Example G[S]

1
2
3
4
5
6
7
8
9
10
[1] S → AB
[2] S → bC
[3] A → b
[4] A → ε
[5] B → aD
[6] B → ε
[7] C → AD
[8] C → b
[9] D → aS
[10] D → c

First Sets:

1
2
3
4
5
First(S) = {a, b, ε}
First(A) = {b, ε}
First(B) = {a, ε}
First(C) = {a, b, c}
First(D) = {a, c}

Step-by-step Conflict Check:

Check 1: S → AB | bC

  • First(AB) = (First(A) - {ε}) ∪ (First(B) - {ε}) ∪ {ε} = {b, a, ε}
  • First(bC) = {b}
  • Conflict: First(AB) ∩ First(bC) = {b} ≠ ∅
  • 结论：存在交集，不满足 LL(1) 条件

Check 2: C → AD | b

  • First(AD) = (First(A) - {ε}) ∪ First(D) = {b, a, c}
  • First(b) = {b}
  • Conflict: First(AD) ∩ First(b) = {b} ≠ ∅
  • 结论：存在交集，不满足 LL(1) 条件

Final Conclusion / 最终结论

The grammar is not LL(1) because: - $ First(AB) First(bC) $ - $ First(AD) First(b) $

因此，该文法不是 LL(1) 文法。