Разработка компиляторов


         

Пример нормализации грамматики


Легко видеть, что процесс, описанный выше, всегда завершится, и что полученная грамматика будет грамматикой в нормальной форме, эквивалентной исходной.

В качестве примера рассмотрим грамматику, показанную на иллюстрации. Здесь второе правило изначально не находится в нормальной форме, поскольку образец в его правой части содержит нетривиальный подобразец (лист, помеченный терминальным символом b).

В данном случае нормализация приводит к введению дополнительного нетерминала K1 и двух правил

K1:b и K: a(K1, K)

вместо второго правила.



Содержание  Назад  Вперед