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