格雷巴赫范式

---

---

如果产生式具有以下形式，则 CFG 处于格雷巴赫范式：

A → b

A → bD₁…D_n

S → ε

其中 A、D₁、....、D_n是非终结符，b 是终结符。

将 CFG 转换为格雷巴赫范式的算法

步骤 1 - 如果起始符号 S 出现在某个右侧，则创建一个新的起始符号 S’ 和一个新的产生式 S’ → S。

步骤 2 - 删除空产生式。（使用前面讨论的空产生式删除算法）

步骤 3 - 删除单元产生式。（使用前面讨论的单元产生式删除算法）

步骤 4 - 删除所有直接和间接的左递归。

步骤 5 - 对产生式进行适当的替换，将其转换为 GNF 的正确形式。

问题

将以下 CFG 转换为 CNF

S → XY | Xn | p

X → mX | m

Y → Xn | o

解决方案

这里，S 没有出现在任何产生式的右侧，并且产生式规则集中没有单元或空产生式。因此，我们可以跳过步骤 1 到步骤 3。

步骤 4

现在替换

S → XY | Xo | p 中的

X 为

mX | m

我们得到

S → mXY | mY | mXo | mo | p。

并且替换

Y → X_n | o 中的

X 为

X → mX | m

我们得到

Y → mXn | mn | o 的右侧。

向产生式集中添加了两个新的产生式 O → o 和 P → p，然后我们得到了最终的 GNF，如下所示：

S → mXY | mY | mXC | mC | p

X → mX | m

Y → mXD | mD | o

O → o

P → p