Posted on Tue 14 April 2020
In Архив.
tags: дискретная математика формальные грамматики язык строка алфавит
Представьте себе, что вам необходимо наладить обмен сообщениями между двумя объектами. Для нас не столь важно, что это за объекты, и что это за сообщения, но для определенности предположим, что эти объекты - космический зонд, который должен принимать команды с Земли, и, соответственно, командный центр на Земле, который передает эти команды.
Для того, чтобы обмен был эффективным и не зависел от ошибок передачи, помех, возникающих на пути сигнала, ошибочных действий персонала, в конце концов, нам необходимо использовать какой-то способ описать формат передаваемых сигналов (чтобы мы знали, как их формировать, из чего они состоят, что за чем следует), и какой-то способ распознавать принимаемый сигнал, определять, содержатся ли в нем ошибки, не потерялась ли часть сообщения в процессе передачи. Фактически, нам необходимо описать формат передачи сообщений.
Для этих целей мы как раз и можем использовать аппарат формальных грамматик (чтобы правильно формировать наши сообщения на Земле) и аппарат конечных автоматов (чтобы правильно распознавать сигналы с Земли на нашем космическом зонде).
Давайте начнем с формальных грамматик.
Если говорить очень упрощенно, то все возможные сообщения, которые мы только можем передать на наш космический зонд с Земли, образуют своеобразный язык. Там будут команды, что должен сделать зонд, и там будут числа, которые укажут ему, как именно он должен это сделать, там будут разделители, чтобы отделять одно от другого, наши указания будут иметь определенную стрктуру (например, сначала указывается команда, а потом - ее числовые параметры), в общем, это действительно будет свой, особый язык, со своими правилами и особенностями. И этот язык необходимо как-то описать, как минимум, чтобы мы сами не запутались в том, какие команды можно отправлять зонду, а какие - нет, и как они выглядят.
Для этого нам нужна формальная грамматика.
Однако, давайте сначала введм некоторые понятия, которые упростят нам дальнейшее описание.
Самым важным, базовым понятием является алфавит. Алфавитом \(A\) принято называть множество неделимых в данном представлении символов, из которых могут состоять слова нашего языка.
Примером можно назвать алфавит \(A_1\):
Это алфавит, состоящий из двух символов, из двух букв, \(0\) и \(1\).
Неделимость в данном представлении означает, что несколько символов рассматриваются, как одно целое.
Например, алфавит \(A_2\)
состоит из двух символов, \(01\) и \(10\). Иногда такое представление символов может быть удобным.
Еще одним важным понятием является слово - это просто набор символов алфавита.
Ну, а набор слов, состоящих из символов заданного алфавита \(A\), называтся языком \(L\) над алфавитом \(A\).
Такие определния дают нам максимальную свободу, ничем нас не ограничивают. С этой точки зрения, алфавит может быть любым, он может состоять из любых букв, которые нам нужны, или из цифр, или из объединения того и другого, или даже из иероглифов, а может - из значков, которые мы придумаем сами.
Как же получить из символов алфавита слова? Для описания этого нам и нужна формальная грамматика.
Вернемся к нашему примеру с космическим зондом. Будем считать, что нам нужно передавать только числа, десятичные, целые и дробные, со знаком и без знака.
Алфавит нашего языка будет иметь вот такой вид:
Введем обозначения составных частей числа. Все обозначения мы будем окружать угловыми скобками, чтобы отличать их от символов, из которых состоит само число.
Начем с самого числа. Обозначим число \(\langle Число \rangle\).
А теперь скажем, что число может состоять из целой части, и запишем это вот так:
Здесь стрелка заменяет слово "состоит", или "может состоять", так что строка выше читается "Число может состять из целой части". А еще стрелку можно читать как "можно заменить на", так что строка выше может читаться и "Число можно заменить на целую часть". Для чего это может понадобиться, мы рассмотрим ниже.
Но ведь числа бывают и дробными? Тогда скажем, что число может состоять из целой части и дробной части, разделенных точкой:
А еще перед целой частью может стоять знак:
и еще один вариант:
это целое число, перед которым стоит знак.
Таким образом, мы получили набор правил, который описывает структуру числа:
Все правила равноправны, при построении числа мы можем выбрать любое из них.
Таким образом, получается, что:
В целом мы описали, как выглядит число. Но это его структура, а как от структуры перейти к конкретному числу?
Давайте опишем отдельные составные части числа, и начнем со знака:
Эти правила говорят нам, что знак числа - это либо "+", либо "-".
Настало время разобраться с целой частью числа и дробной частью числа.
Очевидно, что целая часть и дробная часть очень похожи друг на друга:
Давайте опишем это в виде правил:
Здесь мы говорим, что:
Ну, и наконец, мы опишем цифры:
Работает это так:
Дробная часть описывается аналогично:
\(\langle ДробнаяЧасть \rangle \to \langle СписокЦифр \rangle\)
Соберем все наши правила в одно целое:
Этот набор правил позволяет нам получить любое число, со знаком или без, целое или дробное.
По сути, это и есть сердце нашей грамматики - набор правил.
Еще раз повторю, правила можно рассматривать как указания, что на что можно заменять: слева от стрелки указывается часть строки, которая заменяется, а справа от стрелки указывается, на что она заменяется, то есть правило \(\langle Знак \rangle \to +\) говорит, что термин \(\langle Знак \rangle\) можно заменить на +.
Давайте посмотрим, что нам понадобилось, чтобы описать числа:
Таким образом, мы получили формальную грамматику \(G = \langle A_t, A_o, \langle I \rangle, R \rangle\): совокупность терминального алфавита \(A_t\), нетерминального алфавита \(A_o\), начального символа грамматики \(<I> \in A_o\) и множества правил \(R\).
Как происходит процесс получения числа при помощи нашей формальной грамматики (кстати, процесс получения слова языка называется выводом)?
Рассмотрим пример вывода числа \(-11.25\). При выводе мы будем придерживаться следующего соглашения: стрелка вида \(\Rightarrow\) означает использование одного из правил грамматики, и, значит, замену одной части строки на другую, как указано в выбранном правиле.
Напомню, вывод всегда начинается с начального символа грамматики\(<I>\), в нашем случае - с \(\langle Число \rangle\).
Вывод будет выглядеть вот так:
При первой замене мы нетерминальный символ \(\langle Число \rangle\) заменили на строку, состоящую из нетерминальных символов \(\langle Знак \rangle\langle ЦелаяЧасть \rangle.\langle ДробнаяЧасть \rangle\) в соответствии с четвертым правилом нашей грамматики, при второй замене заменили нетерминал \(\langle Знак \rangle\) на терминальный символ "-" в соответствии с шестым правилом грамматики, и так далее.
Вот таким способом термин "Число" превратился в конкретное число "-11.25".
Обратите пожалуйста внимание: в процессе вывода мы всегда заменяли первый, или самый левый встретившийся нам в строке нетерминальный символ. Это называется левый или левосторонний вывод. Замена самого левого нетерминального символа не является строгим требованием, и существует так же правый или правосторонний вывод, когда в строке каждый раз заменяется последний нетерминальный символ. Однако во многих отношениях левосторонний вывод является более простым.
Здесь мне хотелось бы напомнить, что формальная грамматика, состоящая из терминального и нетерминального алфавитов, начального символа и правил грамматики, описывает процесс получения всех возможных строк языка, который мы пытаемся описать, в данном случае - всех возможных целых и рациональных чисел. Формальная грамматика - это способ получить любое слово языка, который данная грамматика описывает.
Применяются формальные грамматики довольно широко, в том числе при описании языков программирования (когда автор описывает, из чего состоит программа на данном языке программирования, какие команды в ней встречаются, как формируются имена переменных, и так далее), при описании форматов данных, в общем, везде, где нужно как можно точнее описать структуру какого-либо текста.
Правда, в этом случае способ описания формальной грамматики несколько отличается, и чаще используют более удобные способы, например, расширенную форму Бэкуса-Наура, так же называемую РБНФ.
Кроме того, аппарат формальных грамматик так же используются и для более интересных задач, в частности, для преобразования текста из одного формата в другой, например, для преобразования Markdown в HTML, что используется, например, при написании статей Wikipedia, или для преобразования математических выражений из привычной нам инфиксной записи в обратную польскую запись и наоборот, или для преобразования блок-схем в текст на каком-либо языке программирования.
Для изучения аппарата формальных грамматик и конечных автоматов существует замечательная программа с открытым исходным кодом JFLAP.
Пример грамматики, описанной в данной заметке, описывающей десятичные числа, доступен здесь, на сайте.
Между нетерминальными символами грамматики JFLAP и нетерминальными символами описанной в данной статье грамматики установлено следующее соответствие: