Пред.Страница След.Страница Раздел Содержание
5.2.2. Пример использования АТ-грамматики.
Рассмотрим еще один пример использования АТ-грамматик. Допустим, что необходимо описать процесс трансляции инфиксных выражений без скобок, построенных из идентификаторов и бинарных операций сложения и вычитания, синтаксис которых задается схемой следующей грамматики.
Г 5. 2 :<E>
® i<R>,
<R>
® +i<R>,
<R> ® -i<R>,
<R> ® .
В приведенных правилах символ i представляет
идентификатор переменной, значением которого является указатель на элемент
таблицы переменных (ТП). Результатом трансляции выражений, порождаемых
этой грамматикой, должна быть последовательность операторных символов - атомов,
определяющих как последовательность действий, так и операнды каждого действия.
Учитывая это обстоятельство, зададим требуемый перевод
в виде следующей грамматики.
Г 5. 3 : <E> ® i<R>,
<R> ® +i{СЛОЖ}<R>,
<R> ® -i{ВЫЧИТ}<R>,
<R> ® .
Символы действия в правилах этой грамматики расположены так, чтобы результат
можно было передать на выход, как только будут построены оба операнда
рассматриваемой операции. Чтобы обеспечить передачу на выход не только символов
операций, но и указателей на переменные, с которыми выполняются операции,
припишем символам грамматики атрибуты и построим АТ-грамматику.
Каждому
символу, обозначающему идентификатор, припишем атрибут, представляющий
указатель на ТЗ. Каждому символу действия придадим три наследуемые
атрибута, которые должны определять операнды и результат выполнения операции.
При последовательном вычислении выражений образуются промежуточные результаты,
которые необходимо сохранять на время подготовки следующего операнда. Условимся
о том, что промежуточные результаты должны сохраняться в таблице значений (ТЗ).
Для записи промежуточного результата нужно иметь указатель на очередной
свободный элемент ТЗ и изменять его значение после того, как запись
произведена. Для изменения этого указателя воспользуемся введенной в предыдущем
примере функцией СЛЕДУК. Если
рассматриваемая грамматика описывает трансляцию подвыражений, являющихся частью
других конструкций языка, то после построения арифметического выражения в ТЗ
могут записываться другие величины. Следовательно, после трансляции выражения
кроме последовательности атомов необходимо в качестве результата получить
указатель на первый свободный элемент ТЗ после выделения места в ней для
записи промежуточных результатов. Чтобы получить такой указатель, припишем
начальному символу грамматики <E> один
синтезируемый атрибут %a и один наследуемый
атрибут /b. Начальное значение наследуемого
атрибута должно быть указателем на первый свободный элемент ТЗ до записи
промежуточных результатов. Значение синтезируемого атрибута должно быть
сформировано при завершении трансляции и быть равным указателю на первый
свободный элемент ТЗ после записи промежуточных результатов.
Нетерминальный символ грамматики <R>
используется для передачи первого операнда каждой выполняемой операции. Чтобы
осуществить передачу указателя на этот операнд, припишем <R> наследуемый атрибут /с. Учитывая, что первый операнд может быть
промежуточным результатом, который был записан в ТЗ, припишем <R> еще один наследуемый атрибут /d для передачи на следующий шаг вывода указателя
на очередной свободный элемент ТЗ, а для того, чтобы передать на выход
значение указателя на первый свободный элемент ТЗ после завершения
трансляции, припишем ему еще один синтезируемый атрибут %e. Полагая, что формирование элементов таблицы ТЗ
выполняется символами действия, схему искомой АТ-грамматики
можно представить в виде:
Г 5. 4 :
<E>%a/b ® i/x<R>%e/c/d
!! c = x; a = b; a =e;
<R>%e1/c1/d1
® +i/x1{СЛОЖ/f1/g1/h1}<R>%e2/c2/d2
!! f1 = c1; g1 = x1; h1 = d1; c2 = d1; d2 = СЛЕДУК; e1 = e2;
<R>
%e3/c3/d3 ® -i/x2{ВЫЧИТ/f2/g2/h2}<R>%e4/c4/d4
!! f2 = c3; g2 = x2; h2 = d3; c4 = d3; d4 = СЛЕДУК; e3 = e4;
<R>%e5/c5/d5
® .
!! e5 = d5;
Чтобы получить результат трансляции входной цепочки i-i+i для идентификаторов с указателями 22, 24, 26 и указателем первого свободного элемента ТЗ, равным 28, построим вывод в грамматике Г5.4.
Вывод Отложенные вычисления
1. <E>%a/28
2. i/22<R>%e/c/d
!! c = 22; d = 28; a = e;
3. i/22-i/24{ВЫЧИТ/f2/g2/h2}<R>%e4/c4/d4
!! f2 = 22;
g2 = 24; h2
= 28; c4:=
28;
!! d4
=30;
a = e; e =
e4;
4. i/22-i/24{ВЫЧИТ/22/24/28}+i/26
{СЛОЖ/f1/g1/h1}<R>%e2/c2/d2
!! f1 = 28; g1
= 26; h1
= 30; c2
= 30;
!! d2 =
32;
a = e; e =
e4; e4 = е2;
5. i/22-i/24{ВЫЧИТ/22/24/28}+i/26
{СЛОЖ/26/28/30}.
!!e2 = 32; a = 32;
Приведенный вывод показывает, что значение синтезируемого атрибута нетерминала <R> определяется только на пятом шаге вывода с помощью присваивания e2 = 32, которое приводит к выполнению цепочки незавершенных вычислений. Результатом этих вычислений является определение атрибута начального символа a = 32, который является одним из результатов трансляции.