Способы описания формальных языков
1.3 Формы Бэкуса — Наура
Цепочки языка могут содержать метасимволы, имеющие особое назначение. Метаязык, предложенный Бэкусом и Науром (БНФ) использует следующие обозначения:
- символ «::=» отделяет левую часть правила от правой (читается: «определяется как»);
- нетерминалы обозначаются произвольной символьной строкой, заключенной в угловые скобки « »;
- терминалы — это символы, используемые в описываемом языке;
- правило может определять порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты «|» (читается: «или»).
Для повышения удобства и компактности описаний, в расширенных БНФ вводятся следующие дополнительные конструкции (метасимволы):
- квадратные скобки «[» и «]» означают, что заключенная в них синтаксическая конструкция может отсутствовать;
- фигурные скобки «<» и «>» означают повторение заключенной в них синтаксической конструкции ноль или более раз;
- сочетание фигурных скобок и косой черты «» используется для обозначения повторения один и более раз;
- круглые скобки «(» и «)» используются для ограничения альтернативных конструкций;
- кавычки используются в тех случаях, когда один из метасимволов нужно включить в цепочку обычным образом.
Пример 1.10. Правила, определяющие понятие «идентификатор» языка программирования, могут выглядеть следующим образом:
::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w |
x | y | z
::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
::=
1.4 Диаграммы Вирта
В метаязыке диаграмм Вирта используются графические примитивы, представленные на рисунке 1.2.
При построении диаграмм учитывают следующие правила:
- каждый графический элемент, соответствующий терминалу или нетерминалу, имеет по одному входу и выходу, которые обычно изображаются на противоположных сторонах;
- каждому правилу соответствует своя графическая диаграмма, на которой терминалы и нетерминалы соединяются посредством дуг;
- альтернативы в правилах задаются ветвлением дуг, а итерации — их слиянием;
- должна быть одна входная дуга (располагается обычно слева или сверху), задающая начало правила и помеченная именем определяемого нетерминала, и одна выходная, задающая его конец (обычно располагается справа или снизу);
- стрелки на дугах диаграмм обычно не ставятся, а направления связей отслеживаются движением от начальной дуги в соответствии с плавными изгибами промежуточных дуг и ветвлений.
Рисунок 1.2 – Графические примитивы диаграмм Вирта
1) – терминальный символ, принадлежащий алфавиту языка;
2) – постоянная группа терминальных символов, определяющая название лексемы;
3) – нетерминальный символ, определяющий название правила;
4) – входная дуга с именем правила, определяющая его название;
5) – соединительные линии, обеспечивающие связь между терминальными и нетерминальными символами в правилах.
Пример 1.11. Возможные правила, определяющие понятие «идентификатор» языка программирования, показаны на рисунке 1.3.
Рисунок 1.3 – Диаграмма Вирта понятия «идентификатор»
Источник
Способы описания формальных языков
Как уже было сказано, для описания языка-объекта должен применяться метаязык. Но метаязык также должен обладать некоторыми свойствами формального языка, чтобы однозначно определять конструкции языка-объекта. Следовательно, метаязык должен быть сначала описан сам, для чего также нужен язык — естественно, может сложиться впечатление, что такой процесс никогда не закончится. Однако доказано, что для описания любого метаязыка можно использовать язык естественный. Таким образом, для построения формального языка необходимо средствами естественного языка описать метаязык, а затем посредством метаязыка описать язык формальный. Рассмотрим два варианта описания метаязыков.
Один из широко распространенных метаязыков известен как нотации Бекуса-Наура. Для формирования предложений в форме Бекуса-Наура используются универсальные метасимволы: <, ::=, | >. Первые два метасимвола называют «угловыми скобками» — они служат для обрамления нетерминального символа. Символ «::=» читается «по определению есть»; символ «|» — «или». В предложениях, записанных в форме Бекуса-Наура, нетерминальный символ, стоящий в угловых скобках, играет роль определяемой конструкции языка-объекта. В формулах Бекуса-Наура могут использоваться терминальные символы из алфавита языка-объекта, отличные от универсальных метасимволов. Терминальные символы формального языка ничем не ограничиваются.
Описание формального языка строится из последовательности формул, каждая из которых в левой части содержит один метасимвол, обозначающий некоторую конструкцию языка-объекта. Правая часть такой формулы содержит либо перечисление метасимволов и терминальных символов языка-объекта (никаких разделителей при этом не ставится), либо совокупности перечислений, разделенных символом «|». Правая и левая части объединяются в единую формулу знаком «::=».
Язык-объект можно считать полностью определенным в форме Бекуса-Наура, если любой нетерминальный символ можно представить последовательностью терминальных символов.
В качестве примера можно рассмотреть определение понятия «идентификатор», которое используется во многих языках программирования. На естественном языке определение звучит следующим образом: «Идентификатор — это любая последовательность букв и цифр, начинающаяся с буквы». В форме Бекуса-Наура оно будет выглядеть следующим образом:
Видно, что в определении данного понятия присутствует рекурсивность, поскольку понятие «идентификатор» определяется через само себя. Элементарным оказывается идентификатор из одной буквы.
Достоинство нотаций Бекуса-Наура в том, что они представляется в буквенном виде; неудобны нотации однообразностью способов построения предложений языка-объекта — запись оказывается громоздкой и плохо воспринимаемой.
Гораздо более наглядной следует считать другой способ описания формального языка, предложеннный Никласом Виртом — создателем языка программирования PASCAL, получивший название «синтаксические диаграммы». Синтаксическая диаграмма — это схема (графическое представление) описания какого-либо нетерминального символа языка-объекта. Схема всегда имеет один вход и один выход. Элементами схемы могут служить терминальные символы языка-объекта, заключенные в окружность (или овал) или нетерминальные символы (понятия) языка-объекта, заключенные в прямоугольник. Элементы соединяются между собой направленными линиями, указывающие порядок следования объектов в определяемом нетерминальном символе.
Структура синтаксических диаграмм идентична структурам языков программирования, что позволило широко использовать диаграммы для написания трансляторов различных языков. Первым языком, описанным с помощью синтаксических диаграмм, был язык PASCAL.
Чтение диаграммы производится в направлении стрелок; в точке ветвления может выбираться любой маршрут. В качестве метаязыка может использоваться естественный русский язык; языки программирования строятся на англоязычной основе. Терминальные символы переписываются в конструкции формального языка дословно. Нетерминальные символы могут выражаться через терминальные или другие нетерминальные — в этом случае для них строятся уточняющие диаграммы; в конечном счете, все нетерминальные символы должны быть выражены через терминальные. При использовании синтаксических диаграмм принимается условие, что среди терминальных символов языка-объекта не должно быть одинаковых, а также ни один из терминальных символов не может служить началом другого. При нарушении данного условия возможно неоднозначное чтение диаграммы и, как следствие, построение или распознавание неверной конструкции языка.
Рассмотрим ряд примеров построения синтаксических диаграмм, первым из которых будет определение понятия «Идентификатор» для сопоставления с приведенной выше нотацией Бекуса-Наура.
Необходимы уточняющими диаграммы:
Примерами построения англоязычных идентификаторов в соответствии с этой диаграммой являются: q, a 123, identificator, e2e4.
Диаграмма, задающая общий вид программы на языке PASCAL, выглядит следующим образом:
В качестве примеров предписаний рассмотрим условное и циклическое.
В соответствии с этими и подобными диаграммами строятся допустимые синтаксические конструкции языка.
Итак, нотации Бекуса-Наура и синтаксические диаграммы — это два альтернативных способа описания конструкций метаязыка, с помощью которого строится формальный язык. После того, как построена формальная грамматика, и ею порожден язык, он может быть использован для решения прикладных задач — коммуникации, хранения и обработки информации. Последний класс задач приводит к необходимости формулировки с помощью языков последовательностей обработки информации, т.е. алгоритмов, и их представлению в форме, доступной для понимания и исполнения лицом или техническим устройством, которые обработку производят.
Источник
Формальные языки и грамматики
Мотивация
Время от времени на Хабре публикуются посты и переводные статьи, посвященные тем или иным аспектам теории формальных языков. Среди таких публикаций (не хочется указывать конкретные работы, чтобы не обижать их авторов), особенно среди тех, которые посвящены описанию различных программных инструментов обработки языков, часто встречаются неточности и путаница. Автор склонен считать, что одной из основных причин, приведших к такому прискорбному положению вещей, является недостаточный уровень понимания идей, лежащих в основании теории формальных языков.
Этот текст задуман как популярное введение в теорию формальных языков и грамматик. Эта теория считается (и, надо сказать, справедливо) довольно сложной и запутанной. На лекциях студенты обычно скучают и экзамены тем более не вызывают энтузиазма. Поэтому и в науке не так много исследователей в этой тематике. Достаточно сказать, что за все время, с зарождения теории формальных грамматик в середине 50-х годов прошлого века и до наших дней, по этому научному направлению было выпущено всего две докторских диссертации. Одна из них была написана в конце 60-х годов Алексеем Владимировичем Гладким, вторая уже на пороге нового тысячелетия — Мати Пентусом.
Далее в наиболее доступной форме описаны два основных понятия теории формальных языков: формальный язык и формальная грамматика. Если тест будет интересен аудитории, то автор дает торжественное обещание разродиться еще парой подобных опусов.
Формальные языки
Коротко говоря, формальный язык — это математическая модель реального языка. Под реальным языком здесь понимается некий способ коммуникации (общения) субъектов друг с другом. Для общения субъекты используют конечный набор знаков (символов), которые проговариваются (выписываются) в строгом временном порядке, т.е. образуют линейные последовательности. Такие последовательности обычно называют словами или предложениями. Таким образом, здесь рассматривается только т.н. коммуникативная функция языка, которая изучается с использованием математических методов. Другие функции языка здесь не изучаются и, потому, не рассматриваются.
Чтобы лучше разобраться в том, как именно изучаются формальные языки, необходимо сначала понять, в чем заключаются особенности математических методов изучения. Согласно Колмогорову и др. (Александров А.Д., Колмогоров А.Н., Лаврентьев М.А. Математика. Ее содержание, методы и значение. Том 1. М.: Издательство Академии Наук СССР, 1956.), математический метод, к чему бы он ни применялся, всегда следует двум основным принципам:
- Обобщение (абстрагирование). Объекты изучения в математике — это специальные сущности, которые существуют только в математике и предназначены для изучения математиками. Математические объекты образуются путем обобщения реальных объектов. Изучая какой-нибудь объект, математик замечает только некоторые его свойства, а от остальных отвлекается. Так, абстрактный математический объект «число» может в реальности обозначать количество гусей в пруду или количество молекул в капле воды; главное, чтобы о гусях и о молекулах воды можно было
говорить как о совокупностях. Из такой «идеализации» реальных объектов следует одно важное свойство: математика часто оперирует бесконечными совокупностями, тогда как в реальности таких совокупностей не существует. - Строгость рассуждений. В науке принято для выяснения истинности того или иного рассуждения сверять их результаты с тем, что существует в действительности, т.е. проводить эксперименты. В математике этот критерий проверки рассуждения на истинность не работает. Поэтому выводы не проверяются экспериментальным путем, но принято доказывать их справедливость строгими, подчиняющимися определенным правилам, рассуждениями. Эти рассуждения называются доказательствами и доказательства служат единственным способом обоснования верности того или иного утверждения.
Таким образом, чтобы изучать языки с помощью математических методов, необходимо сначала выделить из языка его свойства, которые представляются важными для изучения, а затем эти свойства строго определить. Полученная таким образом абстракция будет называться формальным языком — математической моделью реального языка. Содержание конкретной математической модели зависит от того, какие свойства важны для изучения, т.е. что планируется в данный момент выделить и изучать.
В качестве известного примера такой математической абстракции можно привести модель, известную под неблагозвучным для русского уха названием «мешок слов». В этой модели исследуются тексты естественного языка (т.е. одного из тех языков, которые люди используют в процессе повседневного общения между собой). Основной объект модели мешка слов — это слово, снабженное единственным атрибутом, частотой встречаемости этого слова в исходном тексте. В модели не учитывается, как слова располагаются рядом друг с другом, только сколько раз каждое слово встречается в тексте. Мешок слов используется в машинном обучении на основе текстов в качестве одного из основных объектов изучения.
Но в теории формальных языков представляется важным изучить законы расположения слов рядом друг с другом, т.е. синтаксические свойства текстов. Для этого модель мешка слов выглядит бедной. Поэтому формальный язык задается как множество последовательностей, составленных из элементов конечного алфавита. Определим это более строго.
Алфавит представляет собой конечное непустое множество элементов. Эти элементы будем называть символам. Для обозначения алфавита обычно будем использовать латинское V, а для обозначения символов алфавита — начальные строчные буквы латинского алфавита. Например, выражение V =
Цепочка представляет собой конечную последовательность символов. Например, abc — цепочка из трех символов. Часто при обозначении цепочек в символах используют индексы. Сами цепочки обозначают строчными символами конца греческого алфавита. Например, omega = a1. an — цепочка из n символов. Цепочка может быть пустой, т.е. не содержать ни одного символа. Такие цепочки будем обозначать греческой буквой эпсилон.
Наконец, формальный язык L над алфавитом V — это произвольное множеств цепочек, составленных из символов алфавита V. Произвольность здесь означает тот факт, что язык может быть пустым, т.е. не иметь ни одной цепочки, так и бесконечным, т.е. составленным из бесконечного числа цепочек. Последний факт часто вызывает недоумение: разве имеются реальные языки, которые содержат бесконечное число цепочек? Вообще говоря, в природе все конечно. Но мы здесь используем бесконечность как возможность образования цепочек неограниченной длины. Например, язык, который состоит из возможных имен переменных языка программирования C++, является бесконечным. Ведь имена переменных в C++ не ограничены по длине, поэтому потенциально таких имен может быть бесконечно много. В реальности, конечно, длинные имена переменных не имеют для нас особого смысла т.к. к концу чтения такого имени уже забываешь его начало. Но в качестве потенциальной возможности задавать неограниченные по длине переменные, это свойство выглядит полезным.
Итак, формальные языки — это просто множества цепочек, составленных из символов некоторого конечного алфавита. Но возникает вопрос: как можно задать формальный язык? Если язык конечен, то можно просто выписать все его цепочки одну за другой (конечно, можно задуматься, имеет ли смысл выписывать цепочки языка, имеющего хотя бы десять тысяч элементов и, вообще, есть ли смысл в таком выписывании?). Что делать, если язык бесконечен, как его задавать? В этот момент на сцену выходят грамматики.
Формальные грамматики
Способ задания языка называет грамматикой этого языка. Таким образом, грамматикой мы называем любой способ задания языка. Например, грамматика L =
Назначение грамматики — задание языка. Это задание обязательно должно быть конечным, иначе человек не будет в состоянии эту грамматику понять. Но каким образом, конечное задание описывает бесконечные совокупности? Это возможно только в том случае, если строение всех цепочек языка основано на единых принципов, которых конечное число. В примере выше в качестве такого принципа выступает следующий: «каждая цепочка языка начинается с символов a, за которыми идет столько же символов b». Если язык представляет собой бесконечную совокупность случайным образом набранных цепочек, строение которых не подчиняется единым принципам, то очевидно для такого языка нельзя придумать грамматику. И здесь еще вопрос, можно или нет считать такую совокупность языком. В целях математической строгости и единообразия подхода обычно такие совокупности языком считают.
Итак, грамматика языка описывает законы внутреннего строения его цепочек. Такие законы обычно называют синтаксическими закономерностями. таким образом, можно перефразировать определение грамматики, как конечного способа описания синтаксических закономерностей языка. Для практики интересны не просто грамматики, но грамматики, которые могут быть заданы в рамках единого подхода (формализма или парадигмы). Иначе говоря, на основе единого языка (метаязыка) описания грамматик всех формальных языков. Тогда можно придумать алгоритм для компьютера, который будет брать на вход описание грамматики, сделанное на этом метаязыке, и что-то делать с цепочками языка.
Такие парадигмы описания грамматик называют синтаксическими теориями. Формальная грамматика — это математическая модель грамматики, описанная в рамках какой-то синтаксической теории. Таких теорий придумано довольно много. Самый известный метаязык для задания грамматик — это, конечно, порождающие грамматики Хомского. Но имеются и другие формализмы. Один из таких них — окрестностные грамматики, будет описан чуть ниже.
С алгоритмической точки зрения грамматики можно подразделить по способу задания языка. Имеются три основных таких способа (вида грамматик):
- Распознающие грамматики. Такие грамматики представляют собой устройства (алгоритмы), которым на вход подается цепочка языка, а на выходе устройство печатает «Да», если цепочка принадлежит языку, и «Нет» — в противном случае.
- Порождающие грамматики. Этот вид устройств используется для порождения цепочек языков по требованию. Образно говоря, при нажатии кнопки будет сгенерирована некоторая цепочка языка.
- Перечисляющие грамматики. Такие грамматики печатают одну за другой все цепочки языка. Очевидно, что если язык состоит из бесконечного числа цепочек, то процесс перечисления никогда не остановится. Хотя, конечно его можно остановить принудительно в нужный момент времени, например, когда будет напечатана нужная цепочка.
Интересным представляет вопрос о преобразовании видов грамматики друг в друга. Можно ли, имея порождающую грамматику, построить, скажем, перечисляющую? Ответ — да, можно. Для этого достаточно генерировать цепочки, упорядочив их, скажем по длине и порядку символов. Но превратить перечисляющую грамматику в распознающую в общем случае нельзя. Можно использовать следующий метод. Получив на вход цепочку, запустить процесс перечисления цепочек и ждать, напечатает ли перечисляющая грамматика эту цепочку или нет. Если такая цепочка напечатана, то заканчиваем процесс перечисления и печатаем «Да». Если цепочка принадлежит языку, то она обязательно будет напечатана и, таким образом, распознана. Но, если цепочка не принадлежит языку, то процесс распознавания будет продолжаться бесконечно. Программа распознающей грамматики зациклится. В этом смысле мощность распознающих грамматик меньше мощности порождающих и перечисляющих. Это следует иметь ввиду, когда сравнивают порождающие грамматики Хомского и распознающие машины Тьюринга.
Окрестностные грамматики
В середине 60-х годов советский математик Юлий Анатольевич Шрейдер предложил простой способ описания синтаксиса языков на основе т.н. окрестностных грамматик. Для каждого символа языка задается конечное число его «окрестностей» — цепочек, содержащих данный символ (центр окрестности) где-то внутри. Набор таких окрестностей для каждого символа алфавита языка называется окрестностной грамматикой. Цепочка считается принадлежащей языку, задаваемому окрестностной грамматикой, если каждый символ этой цепочки входит в нее вместе с некоторой своей окрестностью.
В качестве примера рассмотрим язык A =
Рассмотрим цепочку a+a+a и проверим, принадлежит ли она языку. Первый символ «a» цепочки входит в нее вместе с окрестностью #a+ . Второй символ «+» входит в цепочку вместе с окрестностью a+a . Подобное вхождение можно проверить и для остальных символов цепочки, т.е. данная цепочка принадлежит языку, как и следовало ожидать. Но, например, цепочка a+aa языку A не принадлежит, поскольку последний и предпоследний символы «a» не имеют окрестностей, с которыми они входят в эту цепочку.
Не всякий язык может быть описан окрестностной грамматикой. Рассмотрим, например, язык B, цепочки которого начинаются либо с символа «0», либо с символа «1». В последнем случае далее в цепочке могут идти символы «a» и «b». Если же цепочка начинается с нуля, то далее могут идти только символы «a». Нетрудно доказать, что для этого языка нельзя придумать никакой окрестностной грамматики. Легитимность вхождения символа «b» в цепочку обусловлена ее первым символом. Для любой окрестностной грамматики, в которой задается связь между символами «b» и «1» можно будет подобрать достаточно длинную цепочку, чтобы всякая окрестность символа «b» не доставала до начала цепочки. Тогда в начало можно будет подставить символ «0» и цепочка будет принадлежать языку A, что не отвечает нашим интуитивным представлениям о синтаксическом строении цепочек этого языка.
С другой стороны, легко можно построить конечный автомат, который распознает этот язык. Значит, класс языков, которые описываются окрестностными грамматиками, уже класса автоматных языков. Языки, задаваемые окрестностными грамматиками, будем называть шрейдеровскими. Таким образом, в иерархии языков можно выделить класс шрейдеровских языков, который является подклассом автоматных языков.
Можно сказать, что шрейдеровские языки задают одно простое синтаксическое отношение — «быть рядом» или отношение непосредственного предшествования. Отношение дальнего предшествования (которое, очевидно, присутствует в языке B) окрестностной грамматикой задано быть не может. Но, если визуализировать синтаксические отношения в цепочках языка, то для диаграмм отношений, в которые превращаются такие цепочки, можно придумать окрестностную грамматику.
Источник
