Введение в формальные грамматики

Posted on Tue 14 April 2020

tags: дискретная математика формальные грамматики язык строка алфавит

Формальные языки, грамматики и автоматы

Представьте себе, что вам необходимо наладить обмен сообщениями между двумя объектами. Для нас не столь важно, что это за объекты, и что это за сообщения, но для определенности предположим, что эти объекты - космический зонд, который должен принимать команды с Земли, и, соответственно, командный центр на Земле, который передает эти команды.

Для того, чтобы обмен был эффективным и не зависел от ошибок передачи, помех, возникающих на пути сигнала, ошибочных действий персонала, в конце концов, нам необходимо использовать какой-то способ описать формат передаваемых сигналов (чтобы мы знали, как их формировать, из чего они состоят, что за чем следует), и какой-то способ распознавать принимаемый сигнал, определять, содержатся ли в нем ошибки, не потерялась ли часть сообщения в процессе передачи. Фактически, нам необходимо описать формат передачи сообщений.

Для этих целей мы как раз и можем использовать аппарат формальных грамматик (чтобы правильно формировать наши сообщения на Земле) и аппарат конечных автоматов (чтобы правильно распознавать сигналы с Земли на нашем космическом зонде).

Давайте начнем с формальных грамматик.

Формальные грамматики и языки

Если говорить очень упрощенно, то все возможные сообщения, которые мы только можем передать на наш космический зонд с Земли, образуют своеобразный язык. Там будут команды, что должен сделать зонд, и там будут числа, которые укажут ему, как именно он должен это сделать, там будут разделители, чтобы отделять одно от другого, наши указания будут иметь определенную стрктуру (например, сначала указывается команда, а потом - ее числовые параметры), в общем, это действительно будет свой, особый язык, со своими правилами и особенностями. И этот язык необходимо как-то описать, как минимум, чтобы мы сами не запутались в том, какие команды можно отправлять зонду, а какие - нет, и как они выглядят.

Для этого нам нужна формальная грамматика.

Базовые понятия

Однако, давайте сначала введм некоторые понятия, которые упростят нам дальнейшее описание.

Самым важным, базовым понятием является алфавит. Алфавитом $A$ принято называть множество неделимых в данном представлении символов, из которых могут состоять слова нашего языка.

Примером можно назвать алфавит $A_1$:

$$ A_1 = \{ 0, 1 \} $$

Это алфавит, состоящий из двух символов, из двух букв, $0$ и $1$.

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

Например, алфавит $A_2$

$$ A_2 = \{ 01, 10\} $$

состоит из двух символов, $01$ и $10$. Иногда такое представление символов может быть удобным.

Еще одним важным понятием является слово - это просто набор символов алфавита.

Ну, а набор слов, состоящих из символов заданного алфавита $A$, называтся языком $L$ над алфавитом $A$.

Такие определния дают нам максимальную свободу, ничем нас не ограничивают. С этой точки зрения, алфавит может быть любым, он может состоять из любых букв, которые нам нужны, или из цифр, или из объединения того и другого, или даже из иероглифов, а может - из значков, которые мы придумаем сами.

Как же получить из символов алфавита слова? Для описания этого нам и нужна формальная грамматика.

Формальная грамматика

Вернемся к нашему примеру с космическим зондом. Будем считать, что нам нужно передавать только числа, десятичные, целые и дробные, со знаком и без знака.

Алфавит нашего языка будет иметь вот такой вид:

$$ A = \{ 0, 1, 2, 3, 4, 5, 6, 7, 8 ,9, 0, +, -, .\} $$

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

Начем с самого числа. Обозначим число $\langle Число \rangle$.

А теперь скажем, что число может состоять из целой части, и запишем это вот так:

$$ \langle Число \rangle \to \langle ЦелаяЧасть \rangle $$

Здесь стрелка заменяет слово "состоит", или "может состоять", так что строка выше читается "Число может состять из целой части". А еще стрелку можно читать как "можно заменить на", так что строка выше может читаться и "Число можно заменить на целую часть". Для чего это может понадобиться, мы рассмотрим ниже.

Но ведь числа бывают и дробными? Тогда скажем, что число может состоять из целой части и дробной части, разделенных точкой:

$$ \langle Число \rangle \to \langle ЦелаяЧасть \rangle . \langle ДробнаяЧасть \rangle $$

А еще перед целой частью может стоять знак:

$$ \langle Число \rangle \to \langle Знак \rangle \langle ЦелаяЧасть \rangle . \langle ДробнаяЧасть \rangle $$

и еще один вариант:

$$ \langle Число \rangle \to \langle Знак \rangle \langle ЦелаяЧасть \rangle $$

это целое число, перед которым стоит знак.

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

Все правила равноправны, при построении числа мы можем выбрать любое из них.

Таким образом, получается, что:

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

В целом мы описали, как выглядит число. Но это его структура, а как от структуры перейти к конкретному числу?

Давайте опишем отдельные составные части числа, и начнем со знака:

$$ \langle Знак \rangle \to + \\ \langle Знак \rangle \to - $$

Эти правила говорят нам, что знак числа - это либо "+", либо "-".

Настало время разобраться с целой частью числа и дробной частью числа.

Очевидно, что целая часть и дробная часть очень похожи друг на друга:

состоят из набора цифр
набор цифр состоит из одной или более цифр

Давайте опишем это в виде правил:

$$ \langle ЦелаяЧасть \rangle \to \langle СписокЦифр \rangle \\ \langle ДробнаяЧасть \rangle \to \langle СписокЦифр \rangle \\ \langle СписокЦифр \rangle \to \langle Цифра \rangle \\ \langle СписокЦифр \rangle \to \langle Цифра \rangle\langle СписокЦифр \rangle $$

Здесь мы говорим, что:

целая часть числа - это список цифр
дробная часть числа - это список цифр
список цифр может состоять из одной цифры
список цифр может состоять из цифры, за которой продолжается список цифр

Ну, и наконец, мы опишем цифры:

$$ \langle Цифра \rangle \to 0 \\ \langle Цифра \rangle \to 1 \\ \ldots \\ \langle Цифра \rangle \to 9 $$

Работает это так:

Берем список цифр: $\langle СписокЦифр \rangle$
Заменяем $\langle СписокЦифр \rangle$ на $\langle Цифра \rangle\langle СписокЦифр \rangle$
В строке $\langle Цифра \rangle\langle СписокЦифр \rangle$ снова заменяем $\langle СписокЦифр \rangle$ на $\langle Цифра \rangle\langle СписокЦифр \rangle$, и получаем $\langle Цифра \rangle\langle Цифра \rangle\langle СписокЦифр \rangle$
Теперь заменяем $\langle СписокЦифр \rangle$ на $\langle Цифра \rangle$, и получаем $\langle Цифра \rangle\langle Цифра \rangle\langle Цифра \rangle$
А вот теперь можно последовательно заменять $\langle Цифра \rangle$ на какие-либо определенные цифры, получив, например, $123$

Дробная часть описывается аналогично:

$\langle ДробнаяЧасть \rangle \to \langle СписокЦифр \rangle$

Соберем все наши правила в одно целое:

$$ \langle Число \rangle \to \langle ЦелаяЧасть \rangle \\ \langle Число \rangle \to \langle ЦелаяЧасть \rangle . \langle ДробнаяЧасть \rangle \\ \langle Число \rangle \to \langle Знак \rangle \langle ЦелаяЧасть \rangle . \langle ДробнаяЧасть \rangle \\ \langle Число \rangle \to \langle Знак \rangle \langle ЦелаяЧасть \rangle \\ \langle Знак \rangle \to + \\ \langle Знак \rangle \to - \\ \langle ЦелаяЧасть \rangle \to \langle СписокЦифр \rangle \\ \langle ДробнаяЧасть \rangle \to \langle СписокЦифр \rangle \\ \langle СписокЦифр \rangle \to \langle Цифра \rangle \\ \langle СписокЦифр \rangle \to \langle Цифра \rangle\langle СписокЦифр \rangle \\ \langle Цифра \rangle \to 0 \\ \langle Цифра \rangle \to 1 \\ \ldots \\ \langle Цифра \rangle \to 9 $$

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

По сути, это и есть сердце нашей грамматики - набор правил.

Еще раз повторю, правила можно рассматривать как указания, что на что можно заменять: слева от стрелки указывается часть строки, которая заменяется, а справа от стрелки указывается, на что она заменяется, то есть правило $\langle Знак \rangle \to +$ говорит, что термин $\langle Знак \rangle$ можно заменить на +.

Давайте посмотрим, что нам понадобилось, чтобы описать числа:

Алфавит $A_t = \{0, 1, 2, 3, 4, 5, 6, 7,8 ,9, 0, +, -, .\}$, из которого состоят числа и который обычно называют терминальным алфавитом.
Набор терминов, описывающих, из чего состоит число, $A_o = \{\langle Число \rangle, \langle ЦелаяЧасть \rangle, \langle ДробнаяЧасть \rangle, \langle Знак \rangle, \langle СписокЦифр \rangle, \langle Цифра \rangle\}$, который называют нетерминальным алфавитом. Элементы нетерминального алфавита не могут встречаться в числе.
Термин, который мы хотим получить, то есть $\langle Число \rangle$, он называется начальным символом грамматики.
Набор правил, который мы описали выше, его обычно обозначают $R$.

Таким образом, мы получили формальную грамматику $G = \langle A_t, A_o, \langle I \rangle, R \rangle$: совокупность терминального алфавита $A_t$, нетерминального алфавита $A_o$, начального символа грамматики $<I> \in A_o$ и множества правил $R$.

Как происходит процесс получения числа при помощи нашей формальной грамматики (кстати, процесс получения слова языка называется выводом)?

Вывод всегда начинается с начального символа грамматики $<I>$.
При помощи одного из подходящих правил грамматики начальный символ $<I>$ заменяется на какую-либо строку.
В полученной строке некторую ее часть опять-таки при помощи подходящих правил заменяют на что-либо.
Процесс повторяется, пока в строке есть хоть один нетерминальный символ (ну, или есть правила, которые можно использовать).

Рассмотрим пример вывода числа $-11.25$. При выводе мы будем придерживаться следующего соглашения: стрелка вида $\Rightarrow$ означает использование одного из правил грамматики, и, значит, замену одной части строки на другую, как указано в выбранном правиле.

Напомню, вывод всегда начинается с начального символа грамматики$<I>$, в нашем случае - с $\langle Число \rangle$.

Вывод будет выглядеть вот так:

$$\langle Число \rangle \Rightarrow \langle Знак \rangle\langle ЦелаяЧасть \rangle.\langle ДробнаяЧасть \rangle \Rightarrow -\langle ЦелаяЧасть \rangle.\langle ДробнаяЧасть \rangle \Rightarrow -\langle СписокЦифр \rangle.\langle ДробнаяЧасть \rangle \Rightarrow -\langle Цифра \rangle\langle СписокЦифр \rangle.\langle ДробнаяЧасть \rangle \Rightarrow -1<СписокЦифр \rangle.\langle ДробнаяЧасть \rangle \Rightarrow -1<Цифра \rangle.\langle ДробнаяЧасть \rangle \Rightarrow -11.\langle ДробнаяЧасть \rangle \Rightarrow -11.\langle СписокЦифр \rangle \Rightarrow -11.\langle Цифра \rangle\langle СписокЦифр \rangle \Rightarrow -11.2<СписокЦифр \rangle \Rightarrow -11.2<Цифра \rangle \Rightarrow -11.25$$

При первой замене мы нетерминальный символ $\langle Число \rangle$ заменили на строку, состоящую из нетерминальных символов $\langle Знак \rangle\langle ЦелаяЧасть \rangle.\langle ДробнаяЧасть \rangle$ в соответствии с четвертым правилом нашей грамматики, при второй замене заменили нетерминал $\langle Знак \rangle$ на терминальный символ "-" в соответствии с шестым правилом грамматики, и так далее.

Вот таким способом термин "Число" превратился в конкретное число "-11.25".

Обратите пожалуйста внимание: в процессе вывода мы всегда заменяли первый, или самый левый встретившийся нам в строке нетерминальный символ. Это называется левый или левосторонний вывод. Замена самого левого нетерминального символа не является строгим требованием, и существует так же правый или правосторонний вывод, когда в строке каждый раз заменяется последний нетерминальный символ. Однако во многих отношениях левосторонний вывод является более простым.

Здесь мне хотелось бы напомнить, что формальная грамматика, состоящая из терминального и нетерминального алфавитов, начального символа и правил грамматики, описывает процесс получения всех возможных строк языка, который мы пытаемся описать, в данном случае - всех возможных целых и рациональных чисел. Формальная грамматика - это способ получить любое слово языка, который данная грамматика описывает.

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

Правда, в этом случае способ описания формальной грамматики несколько отличается, и чаще используют более удобные способы, например, расширенную форму Бэкуса-Наура, так же называемую РБНФ.

Кроме того, аппарат формальных грамматик так же используются и для более интересных задач, в частности, для преобразования текста из одного формата в другой, например, для преобразования Markdown в HTML, что используется, например, при написании статей Wikipedia, или для преобразования математических выражений из привычной нам инфиксной записи в обратную польскую запись и наоборот, или для преобразования блок-схем в текст на каком-либо языке программирования.

Для изучения аппарата формальных грамматик и конечных автоматов существует замечательная программа с открытым исходным кодом JFLAP.

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

Между нетерминальными символами грамматики JFLAP и нетерминальными символами описанной в данной статье грамматики установлено следующее соответствие:

<Число>: N
<Знак>: S
<ЦелаяЧасть>: I
<ДробнаяЧасть>: F
<СписокЦифр>: L
<Цифра>: D

Alexander Sayapin Teacher's site