ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ   ::   Соловьев Александр

Нетерминальные (промежуточные) символы – это символы, используемые в создании (порождении) слов языка. А создаются слова по грамматическим правилам. И каждое слово, напомним, это с точки зрения программиста – программа, записанная исключительно терминальными символами. Далее задаются ГРАММАТИЧЕСКИЕ ПРАВИЛА . Они очень напоминают подстановки в алгорифмах Маркова. Но в отличие от последних порядок применения грамматических правил произвольный. Применение правила заключается в замене в преобразуемой строке какой-то последовательности символов, совпадающей с левой частью какого-то правила, правой частью (последовательностью символов) этого правила.

Введем в оборот из чисто эстетических соображений еще один красивый термин – СЕНТЕНЦИАЛЬНАЯ ФОРМА . Дело в том, что при построении программ в формальных грамматиках всегда танцуют от одного начального нетерминального символа. Обозначим этот символ «программа». Вместо этого символа по одному из грамматических правил происходит подстановка соответствующей правой части, которая может содержать последовательность из каких-то нетерминальных и терминальных символов. Кстати, такой процесс называется НЕПОСРЕДСТВЕННЫМ ПОРОЖДЕНИЕМ . Любой их появившихся нетерминальных символов может быть заменен по подходящему грамматическому правилу какой-то цепочкой символов. То есть начальный нетерминальный символ «программа» последовательно превращается во все более длинную цепочку символов.