Расширенные Бэкуса-Наура формы (РБНФ)

 

Метаязыки, представленные выше, позволяют описывать любой синтаксис. Однако, для повышения удобства и компактности описания, целесообразно вести в язык дополнительные конструкции. В частности, специальные метасимволы были разработаны для описания необязательных цепочек, повторяющихся цепочек, обязательных альтернативных цепочек. Существуют различные расширенные формы метаязыков, незначительно отличающиеся друг от друга. Их разнообразие зачастую объясняется желанием разработчиков языков программирования по-своему описать создаваемый язык. К примерам таких широко известных метаязыков можно отнести: метаязык PL/I, метаязык Вирта, используемый при описании Модулы-2, метаязык Кернигана-Ритчи, описывающий Си. Зачастую такие языки называются расширенными формами Бэкуса-Наура (РБНФ).

В частности, РБНФ, используемые Виртом, имеют следующие особенности:

– квадратные скобки «[«и «]» означают, что заключенная в них синтаксическая конструкция может отсутствовать;

– фигурные скобки «{» и «}» означают ее повторение (возможно, 0 раз);

– круглые скобки «(» и «)» используются для ограничения альтернативных конструкций;

– сочетание фигурных скобок и косой черты «{/» и «/}» используется для обозначения повторения один и более раз. Нетерминальные символы изображаются словами, выражающими их интуитивный смысл и написанными на русском языке.

Если нетерминал состоит из нескольких смысловых слов, то они должны быть написаны слитно. В этом случае для повышения удобства в восприятии фразы целесообразно каждое ее слово начинать с заглавной буквы или разделять слова во фразах символом подчеркивания. Терминальные символы изображаются словами, написанными буквами латинского алфавита (зарезервированные слова) или цепочками знаков, заключенными в кавычки. Синтаксическим правилам предшествует знак «$» в начале строки. Каждое правило оканчивается знаком «.» (точка). Левая часть правила отделяется от правой знаком «=» (равно), а альтернативы - вертикальной чертой «|». Этот вариант РБНФ и будет использоваться для описания синтаксиса языков в практических работах. В соответствии с данными правилами синтаксис идентификатора будет выглядеть следующим образом:

$ буква = ""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"|"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".

 

$ идентификатор = буква {буква | цифра}.

 

Диаграммы Вирта

 

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

 

Рисунок 4.1 Графические примитивы, используемые при построении диаграмм Вирта

 

– терминальные символы и их постоянные группы располагаются в окружностях или прямоугольниках со скругленными вертикальными сторонами;

– нетерминальные символы заносятся внутрь прямоугольников;

– каждый графический элемент, соответствующий терминалу или нетерминалу, имеет по одному входу и выходу, которые обычно рисуются на противоположных сторонах;

– каждому правилу соответствует своя графическая диаграмма, на которой терминалы и нетерминалы соединяются посредством дуг;

– альтернативы в правилах задаются ветвлением дуг, а итерации – их слиянием;

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

Пример описания идентификатора с использованием диаграмм Вирта представлен на рис 2.2.

Рисунок 4.2 Описание идентификатора с использованием

Диаграмм Вирта

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

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

 

Распознаватели

 

Распознаватель – это очень схематизированный алгоритм, определяющий некоторое множество. Его можно представить в виде устройства (автомата). Этот автомат состоит из трех частей: входной ленты, устройства управления с конечной памятью и вспомогательной (рабочей) памяти (Рисунок 4.3).

Входная лента – линейная последовательность клеток (ячеек), каждая из которых содержит один входной символ из конечного входного алфавита. Могут присутствовать левый и правый концевые маркеры, может присутствовать только один концевой маркер (левый или правый), могут отсутствовать оба маркера.

Входная головка – в каждый момент читает одну входную ячейку. За один шаг входная головка может сдвинуться на одну ячейку влево, вправо и остаться неподвижной.

Распознаватель, никогда не передвигающий входную головку влево, называется односторонним. Обычно предполагается, что входная головка только читает. Но могут быть такие распознаватели, у которых входная головка и читает, и пишет.

Память – хранит информацию, построенную только из символов конечного алфавита памяти. Может иметь различную структуру: очередь, стек (магазин) и т. д. Можно читать из вспомогательной памяти и писать в нее. Для стека и очереди используются специфические операции (вталкивание, выталкивание).

 

Рисунок 4.3 Обобщенная структура распознавателя

 

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

Конфигурация распознавателя – мгновенный снимок, на котором изображены:

 

1. Состояние устройства управления.

2. Содержимое входной ленты.

3. Содержимое памяти.

Начальная конфигурация – устройство управления находится в заданном начальном состоянии, входная головка читает самый левый символ на входной ленте, память имеет заранее установленное начальное содержимое.

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

Распознаватель допускает входную цепочку w, если, начиная с начальной конфигурации, в которой цепочка w записана на входной ленте, распознаватель может проделать последовательность шагов, заканчивающуюся заключительной конфигурацией.

Язык, определяемый распознавателем – это множество цепочек, которые он допускает.

 

Для каждой из грамматик, приведенных выше в соответствии с иерархией Хомского, существуют распознаватели определяющие один и тот же класс языков.

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

2. Язык L контекстно-свободный тогда и только тогда, когда он определяется односторонним недетерминированным автоматом с магазинной памятью.

3. Язык L контекстно-зависимый тогда и только тогда, когда он определяется двухсторонним недетерминированным линейно ограниченным автоматом.

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

 

Данные определения показывают, что теория языков и формальных грамматик продвинулась достаточно далеко, чтобы служить самостоятельным предметом изучения. Не вдаваясь в детали, зафиксируем только сам факт эквивалентности между механизмами порождения и распознавания.