如何将 CFG 转换为 Greibach 范式？

Form(GNF)如果产生式规则满足以下标准之一，则称上下文无关文法 (CFG) 属于 Greibach Normal ：

• 只有开始符号可以生成ε。例如，如果 S 是起始符号，则 S → ε 在 GNF 中。

• 非终端可以生成终端。例如，如果 A 是非终结符而 a 是终结符，则 A → a 在 GNF 中。

• 一个非终结符可以生成一个终结符，后面跟着任意数量的非终结符。例如，S → aAS 在 GNF 中。

情况1

G1 = {S → aAB | aB, A → aA| a, B → bB | 乙}

G1 的产生式规则满足为 GNF 指定的规则，则文法 G1 在 GNF 中。

案例二

G2 = {S → aAB | aB, A → aA | ε, B → bB | ε}

G2 的产生式规则不满足为 GNF 指定的规则为

A → ε 和 B → ε 包含 ε（只有起始符号可以生成 ε）。

因此，语法 G2 不在 GNF 中。

CFG转GNF的步骤

• 步骤 1 - 将语法转换为 CNF。如果给定的语法不在 CNF 中，则将其转换为 CNF。

• Step 2 - 如果语法由左递归组成，则消除它。如果上下文无关文法包含任何左递归，则将其消除。

• Step 3 - 在语法中，将给定的产生式规则转换为 GNF 形式。如果语法中的任何产生式规则不是 GNF 形式，则对其进行转换。

例子

考虑上下文无关文法

S→SS|(S)|a

将此文法转换为 Greibach 范式。

解决方案

下面给出了将 CFG 转换为 GNF 的解释 -

Step 1:
Converting to CNF:
S->SS|XSY|a
X->(
Y->)

Step 2:
Remove left recursion from S->SS
S->XSYP/aP
P->SP/ε
X->(
Y->)

Step 3:
Remove null production P->ε
S->XSYP/aP
P->SP/S
X->(
Y->)

Step 4:
Convert to GNF as S->XSYP is not in GNF,
Replace X with (
S->(SYP/aP
P->SP/S
X->(
Y->)

Step 5:
Convert to GNF as P->SP is not in GNF,
Replace S with (SYP/aP
S->(SYP/aP
P->(SYPP/aPP/(SYP/aP
X->(
Y->)