Разработка компиляторов
Пример нормализации грамматики
Легко видеть, что процесс, описанный выше, всегда завершится, и что полученная грамматика будет грамматикой в нормальной форме, эквивалентной исходной.
В качестве примера рассмотрим грамматику, показанную на иллюстрации. Здесь второе правило изначально не находится в нормальной форме, поскольку образец в его правой части содержит нетривиальный подобразец (лист, помеченный терминальным символом b).
В данном случае нормализация приводит к введению дополнительного нетерминала K1 и двух правил
K1:b и K: a(K1, K)
вместо второго правила.
