Детерминированные атрибутные преобразователи могут работать не
только на основе нисходящего, но и на основе восходящего метода. Особенность
процедуры построения восходящих атрибутных преобразователей заключается
в том, что перевод, реализуемый такими преобразователями
должен быть задан в форме 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. В исходном состоянии в стеке находится
маркер дна, а на входе - заданная цепочка.
Стек
Вход
Выход
h0 i/5 + i/7 |-- -
2. По таблицам 3.4 и 3.5 находим,
что необходимо выполнить операцию переноса. В результате имеем:
Стек
Вход
Выход
h0 5 i + i/7 |-- -
3. По таблицам определяем,
что следует выполнить операцию Свертка(4). Получаем:
.
Стек
Вход
Выход
h0 5 T2 + i/7 |-- -
4. Следующей должна выполняться операция Свертка(2).
Стек
Вход
Выход
h0 5 Ex + i/7 |-- -
5. После выполнения
операции переноса имеем:
Стек
Вход
Выход
h0 5 Ex + i/7 |-- -
6. Выполняя операцию переноса в стек символа
i с атрибутом
получаем:
.
Стек
Вход
Выход
h0 5 Ex + 7 i |-- -
7. Согласно таблицам очередной операцией должна
быть Свертка(4), после выполнения которой имеем:
Стек
Вход
Выход
h0 5 Ex + 7 T1 |-- -
8. По таблицам находим, что следующей
должна выполняться операция Свертка(1), поэтому, полагая, что функция
СЛЕДУК возвращает значение 22, имеем:
.
Стек
Вход
Выход
h0 22 Ex |-- {СЛОЖ/5/7/22}
9. Входной символ, находящийся в вершине стека в соответствии с таблицами работы определяет выполнение операции Допустить, которая говорит об успешном завершении работы преобразователя.