将上下文无关语法转换为格雷巴赫范式

先决条件—— 上下文无关语法 , 简化上下文无关语法

如果所有产生式规则满足以下条件之一，则上下文无关语法（CGF）为格雷巴赫范式（GNF）：

• 生成终端的非终端（例如X->X）
• 一个非终端，生成一个终端，后跟任意数量的非终端（例如：X->xX1X2…Xn）
• 开始生成符号ε。（例如：S->ε）

考虑下面的语法：

G1 = {S->aA|bB, B->bB|b, A->aA|a} 
G2 = {S->aA|bB, B->bB|ε, A->aA|ε}

语法G1在GNF中，因为生产规则满足为GNF指定的规则。但是，语法G2不在GNF中，因为产生式规则B->ε和A->ε不满足为GNF指定的规则（只有开始符号可以生成ε）。 注——

• 对于给定的语法，可以有多个GNF
• GNF生成的语言与CFG生成的语言相同

如何将CFG转换为GNF——

第一步。 将语法转换为CNF。 如果给定的语法不在CNF中，请将其转换为CNF。您可以参考以下文章将CFG转换为CNF： 将上下文无关语法转换为乔姆斯基范式

第二步。 从语法中消除左递归（如果存在）。 如果CFG包含左递归，则消除它们。您可以参考以下文章来消除左递归： 解析|集合1（简介、歧义和解析器）

第三步。 将生产规则转换为GNF形式。 如果GNF表单中没有任何生成规则，请转换它们。让我们举一个将CFG转换为GNF的例子。考虑给定的语法G1：

S → XA|BB 
B → b|SB 
X → b 
A → a

由于G1已经在CNF中，并且没有左递归，我们可以跳过步骤1和2，直接转到步骤3。 产生式规则B->SB不在GNF中，因此，我们将产生式规则B->SB中的S->XA | BB替换为：

S → XA|BB 
B → b|XAB|BBB 
X → b 
A → a

生产规则S->XA和B->XAB不在GNF中，因此，我们将生产规则S->XA和B->XAB中的X->B替换为：

S → bA|BB 
B → b|bAB|BBB 
X → b 
A → a

移除左递归（B->BBB），我们得到：

S → bA|BB 
B → bC|bABC
C → BBC| ε
X → b 
A → a

除去空生产（C->ε），我们得到：

S → bA|BB 
B → bC|bABC|b|bAB
C → BBC|BB
X → b 
A → a

生产规则S->BB不在GNF中，因此，我们用B代替→ bC | bABC | b | bAB在生产规则S->BB as中：

S → bA| bCB|bABCB|bB|bABB 
B → bC|bABC|b|bAB
C → BBC|BB
X → b 
A → a

产生式规则C->BB不在GNF中，因此，我们用B代替→ 生产规则C->BB中的bC | bABC | b | bAB as：

S → bA| bCB|bABCB|bB|bABB 
B → bC|bABC|b|bAB
C → BBC
C → bCB|bABCB|bB|bABB
X → b 
A → a

生产规则C->BBC不在GNF中，因此，我们用B代替→ bC | bABC | b | bAB在生产规则C->BBC as中：

S → bA| bCB|bABCB|bB|bABB 
B → bC|bABC|b|bAB
C → bCBC|bABCBC|bBC|bABBC
C → bCB|bABCB|bB|bABB
X → b 
A → a

这是语法G1的GNF形式。