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

---

5.4.7. Построение восходящих атрибутных преобразователей

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

Определение. L-атрибутная  грамматика в форме простого присваивания, у которой все  атрибуты  нетерминальных символов являются синтезируемыми атрибутами, 
называется S-атрибутной грамматикой.

     Необходимость использования  только  синтезируемых атрибутов вытекает из способа работы восходящего преобразователя, соответствующего построению дерева вывода в направлению от листьев к корню дерева, при котором передача наследуемых атрибутов оказывается невозможной.
     Свойства L-атрибутной грамматики гарантируют, что в правилах вычисления синтезируемых атрибутов нетерминала <X> не используются другие синтезируемые атрибуты этого символа,  и что в правилах вычисления  наследуемых  атрибутов,  находящихся  в правых частях правил грамматики,  используются только атрибуты символов, расположенных в правилах грамматики слева от символа с рассматриваемым
атрибутом.
     В качестве примера приведем S-атрибутную грамматику, построеннуую по грамматике Г _{3. 14}, которая имеет вид:

Г_5.7:

<E>%a ® <E>%b+T%c{СЛЕДУК}%d{СЛОЖИТЬ/x /y %z}
              !! x = b; y = c; (a, z) = d;
<E>%g ® <T>%h
             !! g = h;
<T>%k ® (<E>%l)
          !! k = l;
<T>%n ® i/m
        !! n = m;

     Эта грамматика для выражения строит последовательность атомов,  атрибутами  которых  являются указатели на элементы памяти, хранящие значения операндов и результата.Значения указателей операндов  передаются  от терминалов i через атрибуты нетерминальных символов на выход. Указатели на элементы памяти,  выделяемые  для
промежуточных результатов,  формируются символом действия с функцией СЛЕДУК.  Если задана постфиксная транслирующая грамматика  в виде S-атрибутной грамматики,  и если входная грамматика заданной транслирующей грамматики относится к подклассу грамматик,  порождающих детерминированные языки,  например,  к подклассу LR(0) или
SLR(1), то для нее можно построить  детерминированный  восходящий атрибутный преобразователь.  Такой преобразователь строится путем расширения восходящего распознавателя цепочки входной грамматики.
Расширение заключается в том, что каждому грамматическому вхождению в стеке выделяются дополнительные элементы памяти для  хранения атрибутов.  К операциям свертки добавляются действия, связанные с вычислением значений атрибутов,  их записью в стек и удалением из стека, а к операциям переноса добавляются действия записи атрибутов в стек.
     Например, для грамматики Г_5.7 операции Свертка(4) и  Свертка(2) должны заключаться в замене символа, находящегося в вершине стека.  При выполнении операции Свертка(3) необходимо прочитать 4 элемента  из стека и сохранить значение третьего элемента,  соответствующего атрибуту l, затем записать в стек символ <T> с атрибутом n, присвоить этому атрибуту значение l. Выполнение операции Свертка(1) можно описать следующим образом:
     1) выполнить  действие {СЛЕДУК}%d и присвоить значение атрибута d атрибуту z,
     2) прочитать из стека символ n, его атрибут, а затем присвоить значение этого атрибута атрибуту y,
     3) удалить из стека один символ,
     4) прочитать из стека символ и его атрибут,  а затем присвоить этот атрибут атрибуту x,
     5) записать в стек символ <E> с одним атрибутом и  присвоить этому атрибуту значение атрибута с,
     6) передать на выход атом {СЛОЖИТЬ/x /y %z}, атрибуты которого определены.
     Атрибутный преобразователь,   построенный   для   грамматики Г_5.7, должен  работать  в  соответствии  с таблицами переходов и действий распознавателя (Табл.  3.4 и Табл.  3.5). Последователь ность шагов, выполняемых атрибутным преобразователем при трансля ции входной цепочки i5 + i7+- можно изобразить в следующем виде.
     1. В исходном состоянии в стеке находится маркер дна,  а  на входе - заданная цепочка.
        Стек            Вход            Выход

  h₀              i/5 + i/7 |--              -

     2. По  таблицам  3.4 и 3.5 находим, что необходимо выполнить операцию переноса. В результате имеем:
       Стек            Вход            Выход

h₀  5    i         + i/7 |--              -

        3. По таблицам определяем,  что следует  выполнить  операцию Свертка(4). Получаем:
.
           Стек            Вход            Выход

  h₀  5   T₂             + i/7 |--             -

     4. Следующей должна выполняться операция Свертка(2).
        Стек            Вход            Выход

  h₀  5  E_x         + i/7 |--             -

         5. После выполнения операции переноса имеем:
        Стек                  Вход            Выход

h₀  5  E_x  +            i/7 |--             -

     6. Выполняя операцию переноса в стек символа i  с  атрибутом
получаем:
.
                  Стек                 Вход            Выход

   h₀  5  E_x  +  7   i              |--               -

     7. Согласно таблицам очередной операцией должна быть  Свертка(4), после выполнения которой имеем:
        Стек                            Вход            Выход

h₀  5  E_x  +  7   T₁           |--                   -

     8. По таблицам находим,  что  следующей  должна  выполняться операция Свертка(1), поэтому, полагая, что функция СЛЕДУК возвращает значение 22, имеем:
.
           Стек            Вход            Выход

  h₀  22  E_x            |--             {СЛОЖ/5/7/22}

     9. Входной символ,  находящийся в вершине стека  в  соответствии с таблицами работы определяет  выполнение  операции  Допустить, которая  говорит об успешном завершении работы преобразователя.

---

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