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

Поскольку и здесь, в формальных грамматиках и языках, математика за смысл не отвечает. Есть специальное направление в теоретическом программировании, когда на формальном языке (обычно на языке предикатов и его диалектах) описывается, что должна делать программа. На основании этого описания специальная система синтезирует программу. Однако, это тема совсем другого разговора. Тем более, что ошибок в описании того, что должна делать программа, человек допускает больше, чем при написании программы непосредственно.

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

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

Компилятор, получив программу, выполняет обратную работу. Пред'явленное предложение он свертывает по грамматическим правилам (теперь двигаясь от правой части правила к левой) начального символа «программа».

Обычно существует огромное количество вариантов как порождения, так и свертывания. Если свертывание потерпело неудачу, то должны исследоваться другие варианты. Слово будет признано НЕ принадлежащим данному языку (грамматике), если ни один из вариантов свертывания не приведет к удаче. Поскольку такой перебор вариантов на практике как правило неприемлем, то и грамматики пытаются придумывать не случайные, а с полезными свойствами. А способы свертывания (распознавания) используют эти хорошие свойства, чтобы минимизировать или вообще исключить блуждания.

Есть достаточно грубая, но, все равно, полезная в первом приближении классификация грамматик, принадлежащая Хомскому. Он их делит на три типа, если не считать нулевого. К нулевому он относит грамматики с грамматическими правилами произвольного вида. А раз нет никаких ограничений, то там может быть все, что угодно и, следовательно, анализировать их невозможно. Точнее, считайте, что проанализировали и сделали заключение: Там может быть все, что угодно и неугодно. Так что иметь с ними дело бессмысленно. Даже сумасшедшим.

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