Greibach 范式 (GNF)

GNF 代表 Greibach 范式。如果所有产生式规则都满足以下条件之一，则 CFG（上下文无关文法）处于 GNF（Greibach 范式）中：

• 一个生成 ε 的起始符号。例如，S → ε。
• 一个生成一个终结符的非终结符。例如，A → a。
• 一个生成一个终结符的非终结符，其后跟任意数量的非终结符。例如，S → aASB。

例如

文法 G1 的产生式规则满足 GNF 规定的规则，因此文法 G1 处于 GNF。但是，文法 G2 的产生式规则不满足 GNF 规定的规则，因为 A → ε 和 B → ε 包含 ε（只有起始符号可以生成 ε）。因此，文法 G2 不处于 GNF。

将 CFG 转换为 GNF 的步骤

步骤 1： 将文法转换为 CNF。

如果给定的文法不在 CNF 中，则将其转换为 CNF。您可以参考以下主题将 CFG 转换为 CNF：乔姆斯基范式

步骤 2： 如果文法存在左递归，则消除它。

如果上下文无关文法包含左递归，则消除它。您可以参考以下主题来消除左递归：左递归

步骤 3： 在文法中，将给定的产生式规则转换为 GNF 形式。

如果文法中的任何产生式规则不属于 GNF 形式，则将其转换。

示例

解决方案

由于给定的文法 G 已经处于 CNF 形式，并且不存在左递归，因此我们可以跳过步骤 1 和步骤 2，直接进行步骤 3。

产生式规则 A → SA 不属于 GNF，因此我们用 S → XB | AA 代替产生式规则 A → SA，如下所示

产生式规则 S → XB 和 B → XBA 不属于 GNF，因此我们用 X → a 代替产生式规则 S → XB 和 B → XBA，如下所示

现在我们将消除左递归 (A → AAA)，我们得到

现在我们将消除空产生式 C → ε，我们得到

产生式规则 S → AA 不属于 GNF，因此我们用 A → aC | aBAC | a | aBA 代替产生式规则 S → AA，如下所示

产生式规则 C → AAC 不属于 GNF，因此我们用 A → aC | aBAC | a | aBA 代替产生式规则 C → AAC，如下所示

因此，这是文法 G 的 GNF 形式。