CFG 简化

在 CFG 中，可能出现这样的情况：所有产生式和符号都不是导出字符串所必需的。此外，可能存在一些空产生式和单元产生式。消除这些产生式和符号称为 CFG 的简化。简化主要包括以下步骤 −

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

CFG 的简化

CFG 的简化分为两个阶段 −

阶段 1 −从 CFG，G 中推导出一个等效语法，G'，使得每个变量都派生出一些终端字符串。

推导程序 −

步骤 1 − 包括所有派生出一些终端并初始化 i=1 的符号，W₁。

步骤 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 等价的简化语法，其生成规则为 P：S → AC | B, A → a, C → c | BC, E → aA | e

解决方案

阶段 1 −

T = { a, c, e }

W₁ = { A, C, E } 来自规则 A → a, C → c 和 E → aA

W₂ = { A, C, E } U { S } 来自规则 S → AC

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 }

Y₂ = { S, A, C } 来自规则 S → AC

Y₃ = { S, A, C, a, c } 来自规则 A → a 和 C → 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 可以为 Null]

步骤 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

这是没有空转换的最终生产集。