Лекция 12. ФОРМАЛЬНЫЕ ГРАММАТИКИ
Формальные грамматики - это хорошо развитый математический
аппарат, позволяющий, кроме изучения "высоких материй",
(математически) грамотно создавать языки программирования и
писать компиляторы для этих языков.
Между естественными и формальными языками непреодолимая
пропасть. Поэтому совпадение терминологии лучше считать
случайным... Тем более, в рамках многогранного и разветвленного
ЯЗЫКА МАТЕМАТИКИ раздел формальных грамматик и языков
ориентирован прежде всего на проблемы построения компиляторов.
Формальный язык можно задать как некое множество слов.
Слово, это последовательность символов. Любая компьютерная
программа в этом случае тоже воспринимается как слово. Пробелы в
ней - специальные символы, для которых на клавиатуре выделена
самая длинная клавиша.
Словами данного языка может быть далеко не любая
абракадабра, доступная клавиатуре. А только лексически и
синтаксически (безупречно!) правильные программы. Безупречная с
точки зрения грамматики программа может быть бесполезной,
бессмысленной или даже вредной. Но за правильную работу программы
формальная грамматика и компилятор не отвечают. (Повторим,
математика обычно смыслом не занимается).
Поскольку и здесь, в формальных грамматиках и языках,
математика за смысл не отвечает. Есть специальное направление в
теоретическом программировании, когда на формальном языке (обычно
на языке предикатов и его диалектах) описывается, что должна
делать программа. На основании этого описания специальная система
синтезирует программу. Однако, это тема совсем другого разговора.
Тем более, что ошибок в описании того, что должна делать
программа, человек допускает больше, чем при написании программы
непосредственно.
Для того, чтобы задать грамматику, надо задать множества
ТЕРМИНАЛЬНЫХ и НЕТЕРМИНАЛЬНЫХ символов. Терминальные символы это
символы используемые в языке. Нетерминальные (промежуточные)
символы - это символы, используемые в создании (порождении) слов
языка. А создаются слова по грамматическим правилам. И каждое
слово, напомним, это с точки зрения программиста - программа,
записанная исключительно терминальными символами. Далее задаются
ГРАММАТИЧЕСКИЕ ПРАВИЛА. Они очень напоминают подстановки в
алгорифмах Маркова. Но в отличие от последних порядок применения
грамматических правил произвольный. Применение правила
заключается в замене в преобразуемой строке какой-то
последовательности символов, совпадающей с левой частью какого-то
правила, правой частью (последовательностью символов) этого
правила.
Введем в оборот из чисто эстетических соображений еще один
красивый термин - СЕНТЕНЦИАЛЬНАЯ ФОРМА. Дело в том, что при
построении программ в формальных грамматиках всегда танцуют от
одного начального нетерминального символа. Обозначим этот символ
<программа>. Вместо этого символа по одному из грамматических
правил происходит подстановка соответствующей правой части,
которая может содержать последовательность из каких-то
нетерминальных и терминальных символов. Кстати, такой процесс
называется НЕПОСРЕДСТВЕННЫМ ПОРОЖДЕНИЕМ. Любой их появившихся
нетерминальных символов может быть заменен по подходящему
грамматическому правилу какой-то цепочкой символов. То есть
начальный нетерминальный символ <программа> последовательно
превращается во все более длинную цепочку символов. И так вплоть
до того момента, когда в последовательности символов останутся
только терминальные символы. То есть будет получено слово данного
языка (по иронии судьбы называемое ПРЕДЛОЖЕНИЕМ). Все
последовательности символов, которые в процессе непосредственных
порождений находятся между начальным нетерминальным символом и
конечным предложением и называются сентенциальными формами. А
нам остается радоваться, что английский язык нам неродной.
Компилятор, получив программу, выполняет обратную работу.
Пред'явленное предложение он свертывает по грамматическим
правилам (теперь двигаясь от правой части правила к левой)
начального символа <программа>.
Обычно существует огромное количество вариантов как
порождения, так и свертывания. Если свертывание потерпело
неудачу, то должны исследоваться другие варианты. Слово будет
признано НЕпринадлежащим данному языку (грамматике), если ни один
из вариантов свертывания не приведет к удаче. Поскольку такой
перебор вариантов на практике как правило неприемлем, то и
грамматики пытаются придумывать не случайные, а с полезными
свойствами. А способы свертывания (распознавания) используют эти
хорошие свойства, чтобы минимизировать или вообще исключить
блуждания.
Есть достаточно грубая, но, все равно, полезная в первом
приближении классификация грамматик, принадлежащая Хомскому. Он
их делит на три типа, если не считать нулевого. К нулевому он
относит грамматики с грамматическими правилами произвольного
вида. А раз нет никаких ограничений, то там может быть все, что
угодно и, следовательно, анализировать их невозможно. Точнее,
считайте, что проанализировали и сделали заключение: Там может
быть все, что угодно и неугодно. Так что иметь с ними дело
бессмысленно. Даже сумасшедшим.
Грамматики первого типа называют КОНТЕКСТНО-ЗАВИСИМЫМИ (или
просто КЗ). В большинстве случаев разумно принять общее
ограничение, что правило заменяет строго один нетерминальный
символ. Отличительная особенность КЗ-правил в том, что замена
нетерминального символа на строку допускается, когда этот символ
находится в некотором окружении других символов (в контексте).
Например, нетерминальный символ <оператор> может быть заменен на
нетерминальный символ <пустой оператор>, если в преобразуемой
строке перед символом <оператор> был другой символ, за которым
непосредственно следовал <оператор>. А иначе такую замену делать
нельзя.
Представьте например, правило официанта. Осуществлять замену
грязной тарелки на выписанный счет можно при наличии
опустошенного бокала. В другом контексте (при полном бокале
[граненом стакане] рядом) вместо грязной тарелки клиенту
предлагается новая закуска.
Для того, чтобы грамматика относилась к типу КЗ достаточно,
чтобы хотя бы одно правило было именно первого типа. (Остальные
могут быть других типов, кроме нулевого).
Грамматики второго типа называют КОНТЕКСТНО-СВОБОДНЫМИ (или
просто КС). Каждое правило может применяться без оглядки на
контекст. Вместо грязной тарелки - новая закуска (без всяких
дополнительных условий)... Грамматики разных типов могут
порождать один и тот же язык. Компиляторы диктуют требование
приводить грамматику к типу КС. Обычно в рамках уже этого типа
накладываются дополнительные ограничения, что позволяет
существенно упростить грамматический разбор в компиляторе.
Грамматики последнего третьего типа называются АВТОМАТНЫМИ
или РЕГУЛЯРНЫМИ. Это связано с тем, что они порождаются и
распознаются автоматами (эту математическую модель ассоциируют не
с Калашниковым, а с фамилиями математиков-логиков Мили Мура
Трахтенбротта и т. п.) и регулярными выражениями (это, как и в
регулярной армии - выражения строятся по простым правилам и
просто распознаются - это тоже математическая модель).
Обычно автоматные грамматики используются на уровне лексики.
Лексема, в обычном понимании - это словарная единица. Тем ни
менее, с точки зрения компилятора это "символ", коль скоро
"словом" будет вся программа. В данном случае, например, 345.08
может быть распознан как один символ - действительное число.
Лексический анализ в компиляторе предшествует
синтаксическому анализу... Существуют знаменитые команды UNIX lex
и yacc, который позволяют автоматизировать процесс написания
лексического и синтаксического анализаторов компилятора.
Что-то мы очень уклонились в сторону программирования.
Программирование - это тоже математика. Тоже дискретная. Но уже
другая. И это другая история.
А из программирования уже, обычно, так просто не
возвращаются...