5.4.2. Построение инструкций АП.
Итак, для построения левого вывода LАТ
- грамматики в магазине при каждом применении правила необходимо построить
фрагмент магазина, соответствующий правой части правила, и установить связи
атрибутов правой части правила с атрибутами заменяемой левой части правила,
которые в момент замены находятся непосредственно под вершиной магазина.
В результате установки связи в элементы магазина,
определяющие значения наследуемых атрибутов,
должны быть записаны указатели на элементы магазина, в которые нужно поместить
значения этих атрибутов, а в элементы, соответствующие синтезируемым атрибутам,
должны быть занесены указатели на элементы магазина, в которых будут
расположены значения этих атрибутов. При этом в магазине могут
образовываться цепочки указателей, ссылающихся друг на друга,
которые соответствуют отложенным присваиваниям и последовательностям стрелок
в графическом представлении вывода. Вывод в атрибутных грамматиках совмещается
с вычислением значений атрибутов. Если грамматика задана в форме простого
присваивания, то вычисление значений атрибутов осуществляется при
выполнении символов действия. Полученные в результате вычисления значения
атрибутов должны заноситься в отведенные этим
атрибутам элементы магазина, а также во все элементы, связанные
с ними цепочкой указателей.
Основываясь на описанной выше схеме выполнения
левого вывода в атрибутной грамматике с использованием магазина, можно
сделать вывод о том, что усложнение атрибутного преобразователя по сравнению
с преобразователем, построенным по транслирующей грамматике, возникает
за счет необходимости выделения памяти для атрибутов в магазине и работы
с указателями.
Действия, связанные с построением фрагмента
магазина, АТ- преобразователь может выполнять при записи правой части правила
в магазин. Предписания для установки указателей и определения значений
атрибутов, необходимые для построения фрагмента, могут быть определены
и описаны заранее на этапе построения
АТ - преобразователя. Такие предписания зависят от вида
атрибута и могут быть определены исходя из того, что при выводе с использованием
магазина корень синтаксического дерева вывода находится на дне магазина,
а конечные вершины дерева получаются на вершине.
Кроме того, необходимо учесть, что значения синтезируемых атрибутов
должны передаваться по направлению от конечных вершин дерева к корню, а
значения наследуемых атрибутов наоборот - от корня
к конечным вершинам. Отмеченные обстоятельства позволяют сформулировать
правила вычисления значений атрибутов следующим образом.
1) Если источником копирующего правила является синтезируемый атрибут или атрибут терминального символа, то в поле, соответствующее источнику, записывается указатель на поле приемника, в которое нужно поместить значение источника после его определения.
2) Если источником копирующего правила является наследуемый атрибут, то в поле, соответствующее приемнику, записывается указатель на поле источника, из которого нужно взять значение.
3) Если источником копирующего правила является константа, то ее значение заносится в поле, соответствующее приемнику.
4) Если приемниками копирующего правила являются несколько атрибутов (множественное присваивание), то они связываются цепочкой указателей.
При построении фрагментов для правил грамматики
следует помнить, что атрибуты левой
части заменяемого правила должны находиться в магазине
всегда непосредственно под первым атрибутом правой части
правила, заносимого в магазин.
Построим фрагмент магазина для правила
<A>/x1 ®
{СЛЕДУК}%y1 a %z{f}/x2/x3/x4%y2 <B> /x5 %q
!! ( x2,x5 ) = x1; x3 = y1; x4 = z; q = y2;
который можно изобразить в виде следующей диаграммы:
{
1.Записать в стек цепочку
%q/x5<B>%y2/x4/x3/x2{f}%z a%y1{СЛЕДУК}
2. STACK[SP-8] =SP-11;
3. STACK[SP-3] =SP-7;
4. STACK[SP-1] =SP-6;
5. STACK[SP-5] =SP-10;
6. STACK[SP-10] =SP-12;
}
Приведенное описание инструкции преобразователя
можно считать aлгоритмическим, поскольку описание действий в форме фразы
естественного языка, использованное для краткости, может быть заменено
последовательностью операций записи в магазин, сопровождающихся изменением
указателя стека. Однако использо-
вание адресации относительно вершины стека
обеспечивает корректное значение указателей, если только вершина стека
не изменяется. Чтобы получить возможность работы с указателями независимо
от положения вершины в стеке, возьмем в качестве
значения указателя приращение адреса стека
относительно элемента, в который заносится указатель. Используя такой способ
адресации, перепишем рассматриваемую инструкцию так:
{
1. Записать в стек цепочку
%q/x5<B>%y2/x4/x3/x2{f}%z a%y1{СЛЕДУК}
2. STACK[SP-1] =-5;
3. STACK[SP-3] =-4;
4. STACK[SP-5] =-5;
5. STACK[SP-8] =-3;
6.STACK[SP-10] =-2;
}