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

Формальные грамматики - это хорошо развитый математический

аппарат, позволяющий, кроме изучения "высоких материй",

(математически) грамотно создавать языки программирования и

писать компиляторы для этих языков.

Между естественными и формальными языками непреодолимая

пропасть. Поэтому совпадение терминологии лучше считать

случайным... Тем более, в рамках многогранного и разветвленного

ЯЗЫКА МАТЕМАТИКИ раздел формальных грамматик и языков

ориентирован прежде всего на проблемы построения компиляторов.

Формальный язык можно задать как некое множество слов.

Слово, это последовательность символов. Любая компьютерная

программа в этом случае тоже воспринимается как слово. Пробелы в

ней - специальные символы, для которых на клавиатуре выделена

самая длинная клавиша.

Словами данного языка может быть далеко не любая

абракадабра, доступная клавиатуре. А только лексически и

синтаксически (безупречно!) правильные программы. Безупречная с

точки зрения грамматики программа может быть бесполезной,

бессмысленной или даже вредной. Но за правильную работу программы

формальная грамматика и компилятор не отвечают. (Повторим,

математика обычно смыслом не занимается).

Поскольку и здесь, в формальных грамматиках и языках,

математика за смысл не отвечает. Есть специальное направление в

теоретическом программировании, когда на формальном языке (обычно

на языке предикатов и его диалектах) описывается, что должна

делать программа. На основании этого описания специальная система

синтезирует программу. Однако, это тема совсем другого разговора.

Тем более, что ошибок в описании того, что должна делать

программа, человек допускает больше, чем при написании программы

непосредственно.

Для того, чтобы задать грамматику, надо задать множества

ТЕРМИНАЛЬНЫХ и НЕТЕРМИНАЛЬНЫХ символов. Терминальные символы это

символы используемые в языке. Нетерминальные (промежуточные)

символы - это символы, используемые в создании (порождении) слов

языка. А создаются слова по грамматическим правилам. И каждое

слово, напомним, это с точки зрения программиста - программа,

записанная исключительно терминальными символами. Далее задаются

ГРАММАТИЧЕСКИЕ ПРАВИЛА. Они очень напоминают подстановки в

алгорифмах Маркова. Но в отличие от последних порядок применения

грамматических правил произвольный. Применение правила

заключается в замене в преобразуемой строке какой-то

последовательности символов, совпадающей с левой частью какого-то

правила, правой частью (последовательностью символов) этого

правила.

Введем в оборот из чисто эстетических соображений еще один

красивый термин - СЕНТЕНЦИАЛЬНАЯ ФОРМА. Дело в том, что при

построении программ в формальных грамматиках всегда танцуют от

одного начального нетерминального символа. Обозначим этот символ

<программа>. Вместо этого символа по одному из грамматических

правил происходит подстановка соответствующей правой части,

которая может содержать последовательность из каких-то

нетерминальных и терминальных символов. Кстати, такой процесс

называется НЕПОСРЕДСТВЕННЫМ ПОРОЖДЕНИЕМ. Любой их появившихся

нетерминальных символов может быть заменен по подходящему

грамматическому правилу какой-то цепочкой символов. То есть

начальный нетерминальный символ <программа> последовательно

превращается во все более длинную цепочку символов. И так вплоть

до того момента, когда в последовательности символов останутся

только терминальные символы. То есть будет получено слово данного

языка (по иронии судьбы называемое ПРЕДЛОЖЕНИЕМ). Все

последовательности символов, которые в процессе непосредственных

порождений находятся между начальным нетерминальным символом и

конечным предложением и называются сентенциальными формами. А

нам остается радоваться, что английский язык нам неродной.

Компилятор, получив программу, выполняет обратную работу.

Пред'явленное предложение он свертывает по грамматическим

правилам (теперь двигаясь от правой части правила к левой)

начального символа <программа>.

Обычно существует огромное количество вариантов как

порождения, так и свертывания. Если свертывание потерпело

неудачу, то должны исследоваться другие варианты. Слово будет

признано НЕпринадлежащим данному языку (грамматике), если ни один

из вариантов свертывания не приведет к удаче. Поскольку такой

перебор вариантов на практике как правило неприемлем, то и

грамматики пытаются придумывать не случайные, а с полезными

свойствами. А способы свертывания (распознавания) используют эти

хорошие свойства, чтобы минимизировать или вообще исключить

блуждания.

Есть достаточно грубая, но, все равно, полезная в первом

приближении классификация грамматик, принадлежащая Хомскому. Он

их делит на три типа, если не считать нулевого. К нулевому он

относит грамматики с грамматическими правилами произвольного

вида. А раз нет никаких ограничений, то там может быть все, что

угодно и, следовательно, анализировать их невозможно. Точнее,

считайте, что проанализировали и сделали заключение: Там может

быть все, что угодно и неугодно. Так что иметь с ними дело

бессмысленно. Даже сумасшедшим.

Грамматики первого типа называют КОНТЕКСТНО-ЗАВИСИМЫМИ (или

просто КЗ). В большинстве случаев разумно принять общее

ограничение, что правило заменяет строго один нетерминальный

символ. Отличительная особенность КЗ-правил в том, что замена

нетерминального символа на строку допускается, когда этот символ

находится в некотором окружении других символов (в контексте).

Например, нетерминальный символ <оператор> может быть заменен на

нетерминальный символ <пустой оператор>, если в преобразуемой

строке перед символом <оператор> был другой символ, за которым

непосредственно следовал <оператор>. А иначе такую замену делать

нельзя.

Представьте например, правило официанта. Осуществлять замену

грязной тарелки на выписанный счет можно при наличии

опустошенного бокала. В другом контексте (при полном бокале

[граненом стакане] рядом) вместо грязной тарелки клиенту

предлагается новая закуска.

Для того, чтобы грамматика относилась к типу КЗ достаточно,

чтобы хотя бы одно правило было именно первого типа. (Остальные

могут быть других типов, кроме нулевого).

Грамматики второго типа называют КОНТЕКСТНО-СВОБОДНЫМИ (или

просто КС). Каждое правило может применяться без оглядки на

контекст. Вместо грязной тарелки - новая закуска (без всяких

дополнительных условий)... Грамматики разных типов могут

порождать один и тот же язык. Компиляторы диктуют требование

приводить грамматику к типу КС. Обычно в рамках уже этого типа

накладываются дополнительные ограничения, что позволяет

существенно упростить грамматический разбор в компиляторе.

Грамматики последнего третьего типа называются АВТОМАТНЫМИ

или РЕГУЛЯРНЫМИ. Это связано с тем, что они порождаются и

распознаются автоматами (эту математическую модель ассоциируют не

с Калашниковым, а с фамилиями математиков-логиков Мили Мура

Трахтенбротта и т. п.) и регулярными выражениями (это, как и в

регулярной армии - выражения строятся по простым правилам и

просто распознаются - это тоже математическая модель).

Обычно автоматные грамматики используются на уровне лексики.

Лексема, в обычном понимании - это словарная единица. Тем ни

менее, с точки зрения компилятора это "символ", коль скоро

"словом" будет вся программа. В данном случае, например, 345.08

может быть распознан как один символ - действительное число.

Лексический анализ в компиляторе предшествует

синтаксическому анализу... Существуют знаменитые команды UNIX lex

и yacc, который позволяют автоматизировать процесс написания

лексического и синтаксического анализаторов компилятора.

Что-то мы очень уклонились в сторону программирования.

Программирование - это тоже математика. Тоже дискретная. Но уже

другая. И это другая история.

А из программирования уже, обычно, так просто не

возвращаются...