Преобразование КС-грамматики к обобщенной нормальной форме Грейбах

КС-грамматика представлена в нормальной форме Грейбах, если правые части всех ее порождающих правил начинаются с терминала. Обобщенная нормальная форма Грейбах допускает, кроме того, пустые правые части правил. Пусть задана приведенная КС-грамматика, в которой устранена (если она была) левая рекурсия.

Преобразование начинается с нахождения тех порождающих правил, правые части которых начинаются с терминалов или пусты. Эти порождающие правила остаются без изменения. Пусть имеется правило вида A → Bα, тогда нетерминал B надо заменить совокупностью правых частей правил B → γ₁ | … |γ_n. В результате получатся правила:

A → γ₁α | … |γ_nα.

Если какие-либо из цепочек γ₁α, …, γ_nα начинаются с нетерминального символа, то аналогичную замену правых частей правил для нетерминала A следует продолжать. Так как леворекурсивных правил в грамматике нет, то такой процесс обязательно закончится, и в преобразованных правилах правые части будут начинаться с терминальных символов.

После этого надо отыскать оставшиеся правила вида A’ → B’α’, и продолжить процесс замен. Когда все подобные замены будут сделаны, все правые части правил будут начинаться с терминальных символов или будут пустыми.

Заметим, что при устранении левой рекурсии и преобразования грамматики к обобщенной нормальной форме Грейбах на КС-грамматику не накладывались никакие дополнительные ограничения, из чего следует, что любой язык представим в КС-грамматике без левой рекурсии и, более того, в обобщенной нормальной форме Грейбах.

Пример 7. Пусть задана грамматика простых арифметических выражений с устраненной левой рекурсией:

S → TU

U → + TU | λ

T → FV

V → * FV | λ

F → (S) | a

После ее преобразования к обобщенной нормальной форме Грейбах получим:

S → (S)VU | aVU

U → + TU | λ

T → (S)V | aV

V → * FV | λ

F → (S) | a

Конец примера.

Дата добавления: 2015-07-26; просмотров: 233; Нарушение авторских прав

Мы поможем в написании ваших работ!