GNF означава нормална форма на Greibach. CFG (граматика без контекст) е в GNF (нормална форма на Грайбах), ако всички производствени правила отговарят на едно от следните условия:

• Начален символ, генериращ ε. Например S → ε.
• Нетерминал, генериращ терминал. Например A → a.
• Нетерминал, генериращ терминал, който е последван от произволен брой нетерминали. Например S → aASB.

Например:

 G1 = aB, A → aA G2 = S → aAB 

Правилата за производство на Grammar G1 отговарят на правилата, определени за GNF, така че граматиката G1 е в GNF. Въпреки това, производственото правило на Grammar G2 не удовлетворява правилата, определени за GNF като A → ε и B → ε съдържа ε (само началният символ може да генерира ε). Така че граматиката G2 не е в GNF.

Стъпки за конвертиране на CFG в GNF

Етап 1: Преобразувайте граматиката в CNF.

Ако дадената граматика не е в CNF, преобразувайте я в CNF. Можете да се обърнете към следната тема, за да конвертирате CFG в CNF: Нормална форма на Чомски

Стъпка 2: Ако граматиката съществува лява рекурсия, елиминирайте я.

Ако граматиката без контекст съдържа лява рекурсия, елиминирайте я. Можете да се обърнете към следната тема, за да премахнете лявата рекурсия: Лява рекурсия

Стъпка 3: В граматиката преобразувайте даденото производствено правило в GNF форма.

Ако някое производствено правило в граматиката не е в GNF форма, преобразувайте го.

Пример:

 S → XB | AA A → a | SA B → b X → a 

Решение:

Тъй като дадената граматика G вече е в CNF и няма лява рекурсия, така че можем да пропуснем стъпка 1 и стъпка 2 и директно да преминем към стъпка 3.

Правилото за производство A → SA не е в GNF, така че заместваме S → XB | AA в производственото правило A → SA като:

 S → XB | AA A → a | XBA | AAA B → b X → a 

Правилото за производство S → XB и B → XBA не е в GNF, така че заместваме X → a в правилото за производство S → XB и B → XBA като:

 S → aB | AA A → a | aBA | AAA B → b X → a 

Сега ще премахнем лявата рекурсия (A → AAA), получаваме:

java виртуална машина

 S → aB | AA A → aC | aBAC C → AAC | ε B → b X → a 

Сега ще премахнем нулевото производство C → ε, получаваме:

 S → aB | AA A → aC | aBAC | a | aBA C → AAC | AA B → b X → a 

Правилото за производство S → AA не е в GNF, така че заместваме A → aC | aBAC | a | aBA в производственото правило S → AA като:

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → AAC C → aCA | aBACA | aA | aBAA B → b X → a 

Правилото за производство C → AAC не е в GNF, така че заместваме A → aC | aBAC | a | aBA в производствено правило C → AAC като:

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → aCAC | aBACAC | aAC | aBAAC C → aCA | aBACA | aA | aBAA B → b X → a 

Следователно, това е GNF формата за граматиката G.