Нормальная форма Грейбах

Любой КС язык может быть задан КС-грамматикой в нормальной форме Грейбах (НФГ), а любую КС-грамматику можно преобразовать в эквивалентную ей грамматику в НФГ.

Грамматика в НФГ содержит только правила двух видов:

1) Аt , где А – нетерминал, t – терминал,  - цепочка нетерминалов, возможно пустая;

2) S , если пустая цепочка принадлежит языку, причём начальный нетерминал S не встречается в правых частях правил.

Другими словами, это грамматика без -правил, а правые части правил содержат только один терминал, занимающий крайнюю левую позицию.

Для преобразования произвольной грамматики в НФГ предварительно нужно привести грамматику и устранить левую рекурсию.

Алгоритм преобразования приведённой грамматики без левой рекурсии в НФГ.

1. Упорядочить правила грамматики следующим образом:

а) последовательно выписать правила вида АВ в таком порядке, чтобы для любого правила выполнялось условие:

правила с нетерминалом В в левой части должны располагаться ниже правила АВ , а правила с краем А – выше правила АВ .

б) последовательно выписать правила вида Аt ;

2. Просматривая правила грамматики снизу вверх, выполнять замену края, пока это возможно.

3. Если в правой части некоторого правила встречается терминал t , занимающий не крайнюю левую позицию, и в грамматике есть одиночное правило Аt , то терминал t заменить нетерминалом А , если же в грамматике нет одиночного правило Аt , то ввести его и терминал t заменить на нетерминал А . Выполнять п.3 , пока это возможно.

Пример.

Преобразовать заданную грамматику в НФГ.

Выполнение пунктов 1 и 2 алгоритма представлено в таблице.

Исходная граммати-ка	Правила упорядо-чены	Выполнение замены края			Результат п.2
SAC	BSb	BSb	BSb	BaBCb	SaBC
CAaC	SAC	SAC	SaBC	BdCb	SdC
BSb	CAaC	CaBaC	SdC	SaBC	CaBaC
BbB	BbB	CdaC	CaBaC	SdC	CdaC
AaB	AaB	BbB	CdaC	CaBaC	BaBCb
Ad	Ad	AaB	BbB	CdaC	BdCb
		Ad	AaB	BbB	BbB
			Ad	AaB	AaB
				Ad	Ad

При выполнении п.3 алгоритма вводим два одиночных правила Db и Ea и в правых частях правил, полученных в результате п.2, заменяем терминалы b, расположенные не в крайней левой позиции, на нетерминал D, а терминалы а, расположенные не в крайней левой позиции, на нетерминал E. В итоге получаем грамматику в нормальной форме Грейбах:

SaBC BbB

SdC AaB

CaBEC Ad

CdEC Db

BaBCD Ea

BdCD