s77

Пред.Страница

След.Страница

Раздел

Содержание

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, который является одним из результатов трансляции.

Пред.Страница След.СтраницаРаздел Содержание