Определение и свойства АТ-грамматики

АТ-грамматика — это транслирующая грамматика, дополненная следующим образом.

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

2. Все атрибуты нетерминалов и операционных символов делятся на наследуемые и синтезируемые.

3. Наследуемые атрибуты вычисляются следующим образом:

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

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

4. Синтезируемые атрибуты вычисляются так:

а) значение синтезируемого атрибута нетерминала из левой
части правила грамматики вычисляется как функция некоторых
других атрибутов символов из левой или правой части данного
правила;

б) значение синтезируемого атрибута операционного символа вычисляется как функция некоторых других атрибутов этого
символа.

5. Значения атрибутов терминалов считаются заданными, они
не относятся ни к наследуемым, ни к синтезируемым.

Исходя из этого определения и анализа грамматик, убеждаемся, что в грамматике выражений атрибуты всех нетерминалов — синтезируемые, а в грамматике описаний — наследуемые. В обоих грамматиках атрибуты операционных символов — наследуемые. Значения атрибутов терминалов устанавливает лексический анализатор. Атрибуты отдельных символов не указывались, поскольку не играли никакой роли.

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

1. По Т-грамматике построить дерево разбора активной цепочки, состоящей из терминалов и операционных символов без атрибутов.

2. Присвоить значения атрибутам терминалов, входящих в
дерево разбора.

3. Присвоить начальные значения наследуемым атрибутам
аксиомы грамматики на дереве разбора.

4.Вычислять значения атрибутов символов на дереве, пока это возможно, по правилу: найти атрибут, которого еще нет на дереве, но аргументы для функции его вычисления уже известны; вычислить значение этого атрибута; разместить атрибут на дереве. Если по завершении п.4 значения всех атрибутов всех символов дерева оказываются вычисленными, то такое дерево называют завершенным.

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

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

Теорема 1.Любая трансляция, определяемая L-AT-грамматикой, может быть выполнена недетерминированной атрибутной МП - машиной.

АТ - грамматика называется L-AT-грамматикой, если выполняются следующие условия (ограничения на АТ - грамматику).

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

2. Значение синтезируемого атрибута нетерминала из левой части правила может зависеть только от наследуемых атрибутов этого символа и от любых атрибутов символов правой.

3. Значение синтезируемого атрибута операционного символа зависит только от наследуемых атрибутов этого символа. Условие 1 делает наследуемые атрибуты некоторого узла дерева разбора зависящими (прямо или косвенно) от атрибутов терминалов, расположенных на дереве левее данного узла. Отсюда и наименование грамматики (Left - левая). Условия 2 и 3 делают грамматику корректной.

Теорема 4.Любую трансляцию, определяемую L-AT-грамматикой, у которой входная грамматика является LL(k)-грамматикой, можно выполнить на атрибутной детерминированной МП-I машине с концевым маркером.

Отметим, что здесь, как и в случае с МП-распознавателем, LL(k)-грамматика обеспечивает применение нисходящей стратегии анализа.

Теорема 6.Всякая трансляция, определяемая некоторой S-атрибутной польской транслирующей грамматикой (S-АПТ-грамматикой) с входной LR(к)-грамматикой, может быть выполнена детерминированной атрибутной МП - машиной с концевым маркером.

В данном случае МП - машина работает с использованием восходящей стратегии анализа. АТ - грамматика называется польской, если все операционные символы встречаются только в качестве последних символов правых частей правил грамматики. Наконец, L-AT-грамматика называется S-атрибутной, если все атрибуты нетерминалов — синтезируемые.

Формирование АТ-грамматики

Теперь покажем, как по конкретной входной КС-грамматике можно построить АТ-грамматику и определить ее класс.

ЗадачаДана КС-грамматика G = (V_T, V_n, P, S) описания вещественных переменных, где V_T- {real, имя, , }, V_N = {DCL, LIST), S = DCL и P - множество правил:

1)DCL -> real имя LIST

2)LIST ->, имя LIST

3)LIST-> ε

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

Решение

1. Определим класс входной грамматики G. Следуя методике, изложенной в разделе LL(k)-грамматики, устанавливаем, что грамматика G обладает свойствами LL(1)-грамматик.

2. Преобразуем входную грамматику в Т-грамматику. Адрес должен быть назначен переменной сразу после чтения во входной строке символа имя. Поэтому операционный символ, который обозначим [ALLOC], располагается в Т-грамматике после каждого терминала имя:

1) DCL -> real имя [ALLOC] LIST

2)LIST-*, имя [ALLOC]LIST

3)LIST-> ε

3. Определим атрибуты символов Т-грамматики. Атрибут символа имя - указатель на строку таблицы имен. Атрибуты символа DCL:

1) указатель на начальную ячейку блока памяти для переменных - наследуемый;

2) указатель на свободную ячейку после обработки всего описания - синтезируемый (от символа LIST в правой части правила).

Атрибуты символа LIST:

1) указатель на очередную свободную ячейку блока памяти - наследуемый (из левой части правила);

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

Атрибуты символа [ALLOC]:

1) указатель на строку таблицы имен — наследуемый (от левого символа имя);

2) адрес ячейки памяти для значения переменной — наследуемый (от символа в левой части правила).

4. Выберем обозначения для атрибутов символов правила, положив i=0, 1, ...:

pi — указатель на строку таблицы имен;

bi — указатель на свободную ячейку блока памяти;

ai — адрес, назначенный переменной.

5. Запишем грамматику, приписав символам атрибуты, а за тем пополнив ее комментариями для атрибутов и правилами вычисления их значений. В результате этих действий получим АТ-грамматику:

/*** DCL_x_1,_x₂ - наследуемый x1, синтезируемый х2; ***/

/*** LIST_y_1,_y₂ - наследуемый y1, синтезируемый у2; ***/

/*** [ALLOC]_z_1,_z₂ - наследуемые z1 и z2. ***********/

1) DCL_{b0, b1} -> real имя_р₀[АLLОС]_{p1, a0}LIST_{b2, b3}

p1 = p0, a0 = b0, b2 = b0+1, b1 = b3

2) LIST_{b0, b1} ->, имя_р₀[АLLОС]_{p1, a0}LIST_{b2, b3}

p1 = p0, a0 = b0, b2 = b0+1, b1 = b3

3) LISTboM -> ε

b1 = b0

Поясним отдельные формулы для вычисления значений атрибутов. Предварительно еще раз уточним функцию операционного символа [ALLOC]. По своей сути это подпрограмма, которая по указателю р1 на элемент таблицы имен для информации о переменной, предшествующей [ALLOC], помещает в определенное поле этого элемента адрес a0 ячейки для значения переменной. Носителем указателя является терминал имя, отсюда формула р1 = р0. Носителем адреса является первый атрибут нетерминала в левой части правила, отсюда формула a0 = b0. Информация о текущей свободной ячейке передается к другим правилам посредством атрибута b2 нетерминала LIST вправой части правила. Номер свободной ячейки на 1 больше последней занятой (формула b2 = b0 + 1). Атрибут b0 символа LIST в правиле 3 будет содержать адрес свободной ячейки после назначения адресов всем элементам списка переменных. Поэтому второй атрибут в этом правиле должен получить значение первого (формула b1 = b0). Формула b1 = b3 позволяет передать это значение атрибуту b1 нетерминала DCL.

6. Определим класс АТ-грамматики.

Для этого проверим выполнение условий для атрибутов из определения L-AT-грамматики. Все эти условия выполняются. Значит, полученная грамматика есть L-AT-грамматика с входной LL(1)-грамматикой.

Порядок вычисления значений атрибутов хорошо иллюстрируется с помощью дерева разбора активной атрибутной цепочки.

ПримерДля входной строки real имя₅, имя₄ и L-AT-грамматики из предыдущей задачи дерево разбора соответствующей активной атрибутной цепочки показано на рис. 5.5. В этом примере начальный адрес в блоке принят равным нулю.

Рисунок 5.5 Дерево разбора активной атрибутной цепочки

real имя₅ [ALLOC]₅ имя₄ [ALLOC]₄

После построения безатрибутного дерева оно заполнялось значениями атрибутов. Вычисление наследуемых атрибутов выполнялось раньше синтезируемых и велось в направлении от корня дерева к его листьям. Синтезируемые атрибуты, напротив, вычислялись при движении от листьев к корню. Интересно проследить, как пришедшая сверху информация (номер 2 очередной свободной ячейки) направляется снова вверх после применения правила 3 грамматики. Заметим также, что свойство L-атрибутной грамматики обеспечивает вычисление атрибутов в порядке, пригодном для нисходящей обработки входной строки.

Атрибутную трансляцию, описанную формально АТ - грамматикой, можно выполнить с помощью атрибутного МП - преобразователя, который называют также атрибутным МП - процессором или атрибутной МП - машиной. Выполнение атрибутной трансляции предполагает следующие действия МП - преобразователя:

- последовательное чтение входных символов вместе с их атрибутами;

- проверку принадлежности входной строки языку, определенному входной грамматикой;

- выдачу последовательности атрибутных операционных символов, соответствующей входной строке, из активной атрибутной цепочки.

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

⇐ Предыдущая 15 16 17 18 19 20 21 22 2324