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

5.3. L - атрибутные транслирующие грамматики

  5.3.1. L - атрибутные транслирующие грамматики

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

Определение.  АТ-грамматика является L - атрибутной транслирующей грамматикой, если выполняются следующие три условия:     1) Каждый наследуемый атрибут символа правой части правила грамматики должен вычисляться с использованием либо наследуемых атрибутов символов левой части правила, либо с использованием произвольных атрибутов символов правой части правила, расположенных левее данного символа.     2) Каждый синтезируемый атрибут символа левой части правила грамматики должен вычисляться с использованием наследуемых атрибутов этого символа левой части правила или произвольных атрибутов символов правой части этого правила.     3) Каждый синтезируемый атрибут символа действия должен вычисляться по наследуемым атрибутам этого символа действия.

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

<A>  <B><C>:

1) наследуемые атрибуты <A>,2) наследуемые атрибуты <B>,3) синтезируемые атрибуты <B>,4) наследуемые атрибуты <C>,5) синтезируемые атрибуты <C>,6) синтезируемые атрибуты <A>.

    Чтобы убедиться в том, что заданная АТ-грамматика обладает свойствами LАТ-грамматики, нужно проверить для каждого правила грамматики выполнение условий 1 и 2, а также для каждого символа действия - выполнение условия 3. Такая проверка заключается в анализе зависимостей атрибутов для каждого правила их вычисления.    В качестве иллюстрации выполним анализ возможных зависимостей атрибутов, отвечающих описанным условиям, для следующего правила:

<A>/a1%x1%y1 <B>/b1<C>%x2<D>%y2/a2/b2<E>/a3

    Анализ зависимостей этого правила должен заключаться в проверке того, что правила вычисления атрибутов b1, a2, b2, a3 должны удовлетворять условию 1, а правила вычисления атрибутов x1, y1 - условию 2. Согласно условию 1 правило вычисления атрибута b1 может использовать для вычисления только атрибут a1, поэтому такие правила могут, например, иметь вид:

b1 = f(a1) или b1 = 112  или (b1,b2) = a1.

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

Отметим также, что правила вычисления не могут иметь, например, следующий вид:

b1 = x1 или b1 = g(y2,b1).

    Условие 1 для рассматриваемого правила позволяет использовать для вычисления атрибутов a2 и b2 в качестве аргументов величины a1, b1, x2, а при вычислении a3 аргументами могут быть a1, b1, x2, y2, a2, b2.

    Согласно условию правила 2 при вычислении атрибутов x1 и y1 могут быть использованы любые атрибуты кроме самих x1, y1.

    Условие 3 используется для проверки символов действия. Чтобы убедиться в его выполнении, нужно просмотреть список аргументов правил вычисления атрибутов и убедиться, что среди них нет синтезированных атрибутов.