CFG 的简化

正如我们所看到的，各种语言都可以通过上下文无关文法有效地表示。 并非所有文法都总是经过优化的，这意味着文法可能包含一些额外的符号（非终结符）。 拥有额外的符号会不必要地增加文法的长度。 文法的简化意味着通过删除无用符号来减少文法。 简化文法的属性如下

1. G 的每个变量（即非终结符）和每个终结符都出现在 L 中某个单词的推导中。
2. 不应存在任何产生式，如 X → Y，其中 X 和 Y 是非终结符。
3. 如果 ε 不在语言 L 中，则不需要产生式 X → ε。

让我们详细研究一下精简过程。

删除无用符号

如果一个符号没有出现在产生式规则的右侧，并且没有参与任何字符串的推导，那么它就可能是无用的。 该符号称为无用符号。 同样，如果一个变量没有参与任何字符串的推导，那么它可能就是无用的。 该变量称为无用变量。

例如

在上面的例子中，变量“C”永远不会出现在任何字符串的推导中，所以产生式 C → ad 是无用的。 因此，我们将删除它，并且以这样一种方式编写其他产生式，即变量 C 永远无法从起始变量“T”到达。

产生式 A → aA 也是无用的，因为没有办法终止它。 如果它永远不终止，那么它永远无法产生一个字符串。 因此，此产生式永远无法参与任何推导。

为了删除这个无用的产生式 A → aA，我们将首先找到所有永远不会导致终结符字符串的变量，比如变量 'A'。 然后我们将删除所有出现变量 'B' 的产生式。

消除 ε 产生式

S → ε 类型的产生式称为 ε 产生式。 只有在那些不生成 ε 的文法中才能删除这些类型的产生式。

步骤 1： 首先找出所有导出 ε 的可空非终结符变量。

步骤 2： 对于每个产生式 A → a，构造所有产生式 A → x，其中 x 是通过从步骤 1 中的 a 中删除一个或多个非终结符而获得的。

步骤 3： 现在将步骤 2 的结果与原始产生式结合起来，并删除 ε 产生式。

示例

通过保留以下 CFG 的含义来删除产生式。

解决方案

现在，在删除 ε 产生式时，我们正在删除规则 X → ε 和 Y → ε。 为了保留 CFG 的含义，我们实际上是在每次出现 X 和 Y 时将 ε 放在右侧。

让我们采用

如果右侧的第一个 X 是 ε。 那么

类似地，如果 RHS 中的最后一个 X = ε。 那么

如果 Y = ε 那么

如果 Y 和 X 是 ε 那么，

如果两个 X 都被 ε 替换

现在，

现在让我们考虑

如果我们为 X 在右侧放置 ε 那么，

类似地 Y → 1Y | 1

总的来说，我们可以使用删除的 ε 产生式来重写 CFG

删除单元产生式

单元产生式是指一个非终结符给出另一个非终结符的产生式。 使用以下步骤删除单元产生式

步骤 1： 要删除 X → Y，只要 Y → a 出现在文法中，就将产生式 X → a 添加到文法规则中。

步骤 2： 现在从文法中删除 X → Y。

步骤 3： 重复步骤 1 和步骤 2，直到删除所有单元产生式。

例如

解决方案

S → C 是一个单元产生式。 但是在删除 S → C 时，我们必须考虑 C 给出了什么。 所以，我们可以向 S 添加一个规则。

类似地，B → A 也是一个单元产生式，所以我们可以将其修改为

因此，最后我们可以编写没有单元产生式的 CFG，如下所示