如何将 CFG 转换为 Greibach 范式？
Form(GNF)如果产生式规则满足以下标准之一，则称上下文无关文法(CFG)属于GreibachNormal：
只有开始符号可以生成ε。例如，如果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。
Step2-如果语法由左递归组成，则消除它。如果上下文无关文法包含任何左递归，则将其消除。
Step3-在语法中，将给定的产生式规则转换为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->)