Greibach 范式

如果产生式符合以下形式，则 CFG 符合 Greibach 范式 −

A → b

A → bD₁…D_n

S → ε

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

将 CFG 转换为 Greibach 范式的算法

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

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

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

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

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

问题

将以下 CFG 转换为 CNF

S → XY | Xn | p

X → mX | m

Y → Xn | o

解决方案

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

步骤 4

现在，在将

S → XY | Xo | p

替换为

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