Дискретная математика без формул [Александр Валерьевич Соловьев] (fb2) читать постранично, страница - 19

математику. Но на самом деле это очень мощный механизм, поскольку через него можно выразить решение любой алгоритмически разрешимой задачи. И опять напомним, что это не следует воспринимать, как предложение решать любую задачу через подстановки (хотя на этих принципах работает замечательный язык программирования РЕФАЛ). Это лишь означает, что любую алгоритмически разрешимую задачу МОЖНО представить в виде такой системы подстановок. А если нельзя (и вы это смогли доказать), то такая задача вообще не имеет алгоритма решения.

Лекция 12. ФОРМАЛЬНЫЕ ГРАММАТИКИ

Формальные грамматики – это хорошо развитый математический аппарат, позволяющий, кроме изучения «высоких материй», (математически) грамотно создавать языки программирования и писать компиляторы для этих языков.

Между естественными и формальными языками непреодолимая пропасть. Поэтому совпадение терминологии лучше считать случайным… Тем более, в рамках многогранного и разветвленного ЯЗЫКА МАТЕМАТИКИ раздел формальных грамматик и языков ориентирован прежде всего на проблемы построения компиляторов.

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

Словами данного языка может быть далеко не любая абракадабра, доступная клавиатуре. А только лексически и синтаксически (безупречно!) правильные программы. Безупречная с точки зрения грамматики программа может быть бесполезной, бессмысленной или даже вредной. Но за правильную работу программы формальная грамматика и компилятор не отвечают. (Повторим, математика обычно смыслом не занимается).

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

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

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

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

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