CFG 简化

---

---

在 CFG 中，可能会发生并非所有产生式规则和符号都用于字符串的推导。此外，可能存在一些空产生式和单元产生式。消除这些产生式和符号称为 **CFG 的简化**。简化主要包括以下步骤：

• CFG 的化简
• 移除单元产生式
• 移除空产生式

CFG 的化简

CFG 分两个阶段进行化简：

**阶段 1** - 从 CFG **G** 推导出等价文法 **G’**，使得每个变量都推导出某个终结符串。

**推导过程** -

步骤 1 - 包含所有推导出某个终结符的符号 **W₁**，并初始化 **i=1**。

步骤 2 - 包含所有推导出 **W_i** 的符号 **W_i+1**。

步骤 3 - 增加 **i** 并重复步骤 2，直到 **W_i+1 = W_i**。

步骤 4 - 包含所有包含 **W_i** 的产生式规则。

**阶段 2** - 从 CFG **G’** 推导出等价文法 **G”**，使得每个符号都出现在某个句型中。

**推导过程** -

步骤 1 - 将开始符号包含在 **Y₁** 中，并初始化 **i = 1**。

步骤 2 - 包含所有可以从 **Y_i** 推导出的符号 **Y_i+1**，并包含所有已应用的产生式规则。

步骤 3 - 增加 **i** 并重复步骤 2，直到 **Y_i+1 = Y_i**。

问题

找到一个与文法 G 等价的化简文法，G 具有产生式规则 P：S → AC | B，A → a，C → c | BC，E → aA | e

解答

**阶段 1** -

T = { a, c, e }

根据规则 A → a，C → c 和 E → aA，W₁ = { A, C, E }

根据规则 S → AC，W₂ = { A, C, E } U { S }

W₃ = { A, C, E, S } U ∅

由于 W₂ = W₃，我们可以推导出 G’ 为：

G’ = { { A, C, E, S }, { a, c, e }, P, {S}}

其中 P：S → AC，A → a，C → c ，E → aA | e

**阶段 2** -

Y₁ = { S }

根据规则 S → AC，Y₂ = { S, A, C }

根据规则 A → a 和 C → c，Y₃ = { S, A, C, a, c }

Y₄ = { S, A, C, a, c }

由于 Y₃ = Y₄，我们可以推导出 G” 为：

G” = { { A, C, S }, { a, c }, P, {S}}

其中 P：S → AC，A → a，C → c

移除单元产生式

任何形式为 A → B 的产生式规则，其中 A、B ∈ 非终结符，称为 **单元产生式**。

移除过程 -

**步骤 1** - 为了移除 **A → B**，每当 **B → x** 出现在文法中时，将产生式 **A → x** 添加到文法规则中。[x ∈ 终结符，x 可以为空]

**步骤 2** - 从文法中删除 **A → B**。

**步骤 3** - 重复步骤 1，直到所有单元产生式都被移除。

问题

从以下内容中移除单元产生式：

S → XY，X → a，Y → Z | b，Z → M，M → N，N → a

**解答** -

文法中有 3 个单元产生式：

Y → Z，Z → M，和 M → N

首先，我们将移除 M → N。

由于 N → a，我们添加 M → a，并移除 M → N。

产生式集变为

S → XY，X → a，Y → Z | b，Z → M，M → a，N → a

现在我们将移除 Z → M。

由于 M → a，我们添加 Z→ a，并移除 Z → M。

产生式集变为

S → XY，X → a，Y → Z | b，Z → a，M → a，N → a

现在我们将移除 Y → Z。

由于 Z → a，我们添加 Y→ a，并移除 Y → Z。

产生式集变为

S → XY，X → a，Y → a | b，Z → a，M → a，N → a

现在 Z、M 和 N 不可到达，因此我们可以移除它们。

最终的 CFG 不包含单元产生式：

S → XY，X → a，Y → a | b

移除空产生式

在 CFG 中，非终结符 **‘A’** 是一个可空变量，如果存在产生式 **A → ε** 或存在一个从 **A** 开始并最终以

ε 结束的推导：A → .......… → ε

移除过程

**步骤 1** - 找出推导出 ε 的可空非终结符变量。

**步骤 2** - 对于每个产生式 **A → a**，构造所有产生式 **A → x**，其中 **x** 是从 **‘a’** 中移除一个或多个来自步骤 1 的非终结符获得的。

**步骤 3** - 将原始产生式与步骤 2 的结果结合起来，并移除 **ε - 产生式**。

问题

从以下内容中移除空产生式：

S → ASA | aB | b，A → B，B → b | ∈

**解答** -

有两个可空变量：**A** 和 **B**

首先，我们将移除 B → ε。

移除 **B → ε** 后，产生式集变为：

S→ASA | aB | b | a, A ε B| b | &epsilon, B → b

现在我们将移除 A → ε。

移除 **A → ε** 后，产生式集变为：

S→ASA | aB | b | a | SA | AS | S, A → B| b, B → b

这是最终不包含空转换的产生式集。