Пред.Страница
След.Страница
Раздел
Содержание
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, построим вывод в грамматике Г.
Вывод
Отложенные вычисления
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>
определяется только на пятом шаге вывода с помощью присваивания
с2 := 32, которое приводит к выполнению
цепочки незавершенных вычислений. Результатом этих вычислений является
определение атрибута начального символа a :=
32, который является одним из результатов
трансляции.
Пред.Страница
След.Страница
Раздел
Содержание