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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим язык простейших арифметических формул:

Опишем грамматику математической формулы с использованием метаязыка Бэкуса-Наура:

< формула>: (< формула>) | < число> | < формула> < знак> < формула>

< знак>: + | *

Почему «3+5*2» является формулой? Приведем последовательность преобразований цепочек (так называемый «разбор» или «вывод»):

Сокращенно наличие вывода (цепочки преобразований) будем за писывать в виде < формула>:: 3+5*2. Большинство грамматик допускают несколько различных выводов для одной и той же цепочки из языка. Постройте другой вывод для цепочки «3+5*2» - упражнение.

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

Изобразим выполняемые замены цепочек в виде т.н. «дерева разбора» (или дерева вывода). По традиции дерево изображается «вверх ногами»:

Нарисованное дерево имеет ветви (линии) и узлы (помечены терминалами и нетерминалами), из которых растут ветви. Конечные узлы (терминалы) называются листьями. Понятия «поддерево», «корень дерева», видимо, не нуждаются в определении.

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

Если для одной и той же цепочки можно изобразить два разных дерева разбора (или, что то же самое, построить, два разных правых вывода), грамматика называется неоднозначной. Описанная грамматика неоднозначна. Тот же самый язык можно описать однозначной грамматикой:

< формула>: < терм> | < терм> < знак> < формула>

< терм>: (< формула>) | < число>

< знак>: + | *

Как изменится дерево разбора? Дерево разбора определяет некоторую структуру цепочки языка. Так, мы видим, что подцепочка «3+5» является «формулой». Это противоречит нашим (интуитивным) понятиям о смысле исходной формулы: 3+5 в отличие от 5*2 не является подвыражением. Мы можем учесть приоритет операций, изменив грамматику:

< формула>: < терм> | < формула> + < терм>

< терм>: < элемент> | < терм> * < элемент>

< элемент>: (< формула>) | < число>

Кроме привычной формы записи арифметических формул (т.н. «инфиксной», т.е. со знаком операции между операндами), широко распространена «постфиксная» (или обратная польская) форма записи, в которой операция расположена после операндов.

Примеры:

2+3 2 3 +

2*3+4 2 3 * 4 +

2*(3+4) 2 3 4 + *

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

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

CompForm() {

CompForm()

...

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

Если устранить левую рекурсию:

< формула>: < терм> | < терм> < плюс минус> < формула>

< терм>: < элемент> | < элемент> < умножить разделить> < терм>

< плюс минус>: + | -

< умножить разделить>: * | /

то описанная проблема исчезнет, рекурсивный компилятор можно будет написать, однако появятся новые трудности (какое дерево разбора будет соответствовать цепочке «5-3-2»?).

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

Наиболее просто решить эту проблему можно, добавив в метаязык НФБН символы итерации {} «повторить 0 или более раз». С применением новых обозначений грамматика легко запишется без левой рекурсии:

< формула>: < терм> { < плюс минус> < формула> }

< терм>: < элемент> { < умножить разделить> < элемент> }

Написанный по этой грамматике рекурсивный компилятор также будет выглядеть просто:

char *infix, *postfix; /* указатели на входную и выход-

ную цепочки */

CompForm() { /* компилировать формулу */

register char sign;

CompTerm();

while ((sign = *infix) == '+' || sign == '-') {

++infix;

CompTerm();

*postfix++ = sign;

*postfix++ = ' ';

}

}

CompTerm() { /* компилировать терм */

register char sign;

CompEl();

while ((sign = *infix) == '*' || sign == '/') {

++infix;

CompEl();

*postfix++ = sign;

*postfix++ = ' ';

}

}

CompEl () { /* компилировать элемент */

if (*infix == '(') {

++infix;

CompForm();

if (*infix++! = ')') error();

} else {

if (! isdigit(*infix)) error();

while (isdigit(*infix)) *postfix++ = *infix++;

*postfix++ = ' ';

}

}

Использованная нами при написании компилятора техника носит название рекурсивного спуска. Входную цепочку мы просматриваем слева направо, дерево вывода проходим сверху вниз (т.е. от начального нетерминала < формула>).

Функция error в компиляторе служит для вывода сообщения о том, что предъявленная цепочка не входит в язык арифметических формул. Если компилятор при получении на вход цепочки не выдает сообщения об ошибке, говорят, что эта цепочка допущена.

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