格雷巴赫范式

---

如果产生式采用以下形式，则 CFG 处于 Greibach 范式 -

甲 → 乙

A → bD ₁ …D _n

S → ε

其中 A, D ₁ ,...,D _n是非终结符，b 是终结符。

将 CFG 转换为 Greibach 范式的算法

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

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

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

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

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

问题

将以下CFG转换为CNF

S → XY | Xn | p

X → mX | 米

Y → Xn | 哦

解决方案

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

步骤4

现在更换后

S 中的 X → XY | Xo | p

和

米X | 米

我们获得

S → mXY | 米亚 | mXo | 莫| p。

并且更换后

Y 中的 X → X _n | 哦

与右侧

X → mX | 米

我们获得

Y → mXn | 百万 | o。

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

S → mXY | 米亚 | 米XC | MC | p

X → mX | 米

Y → mXD | 医学博士 | 哦

奥 → 奥

P → p