5.4.3. Описание работы ап

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

1) Обработка входной цепочки начинается, когда в магазине находится начальный символ грамматики и маркер дна. Первая инструкция  преобразователя должна заносить в магазин начальный символ грамматики и присваивать наследуемым атрибутам начального символа начальные значения. При этом поля синтезируемых атрибутов заполняются пустыми указателями. 2) Если в вершине магазина находится входной символ, имеющий атрибут, то производится считывание очередного символа с входной ленты, и эти символы сравниваются. Если они совпадают, то читается атрибут входного символа с ленты и записывается в ячейки магазина, образующие цепочку, на которую ссылается указатель, записанный в поле атрибута рассматриваемого входного символа. Затем входной символ и его атрибут удаляются из магазина, и входная головка сдвигается. 3) Если в вершине магазина находится входной символ, не имеющий атрибута, то производится считывание очередного входного символа с входной ленты, и эти символы сравниваются. Если они совпадают, то символ удаляется из магазина, и входная головка сдвигается на одну позицию. 4) Если в вершине магазина находится символ действия, то выполняется чтение атрибутов, соответствующих его аргументам, затем вычисляются значения в соответствии с функцией символа действия синтезируемых атрибутов, и эти значения помещаются во все поля, определяемые цепочкой указателей, на которую ссылается указатель в поле синтезируемого атрибута. Если символ действия должен передаваться на выход, то осуществляется запись этого символа и его атрибутов на выходную ленту. 5) Если в вершине магазина находится нетерминал, то он удаляется из магазина и вместо него в магазине строится фрагмент, соответствующий правой части правила грамматики, и устанавливаются связи этого фрагмента с атрибутами удаленного символа, которые оказываются расположенными непосредственно под создаваемым фрагментом. Такие связи должны быть определены в инструкции построения фрагмента. 6) Если в вершине магазина находится атрибут, значение которого определено, то он удаляется из магазина.

5.4.4. Порядок построения ап

 Построение детерминированного атрибутного преобразователя можно выполнить для любой LАТ-грамматики в форме простого присваивания, входная грамматика которой относится к классу LL(1) грамматик. Существенными факторами, определяющими возможность построения преобразователя, являются свойства L - атрибутности и форма простого присваивания. Свойство L - атрибутности обеспечивает порядок вычисления атрибутов, соответствующий порядку извлечения атрибутов из стека при работе нисходящего преобразователя. Он является следствием того, что в грамматике рассматриваемого типа атрибуты, значения которых вычисляются в процессе вывода, должны зависеть только от атрибутов, расположенных слева от них в правилах грамматики. Согласно этому порядку вначале всегда вычисляются атрибуты, расположенные ближе к вершине стека, а затем уже зависящие от них атрибуты, расположенные в глубине стека. Свойства формы простого присваивания, допускающее использование в качестве правил вычисления значений атрибутов только копирующих правил, позволяют свести процесс вычисления атрибутов к передаче значений. При этом сведения об отложенных присваиваниях сохраняются в виде цепочек указателей, определяющих порядок присваивания. Добавочные символы действия, появляющиеся в правилах заданной грамматики в результате ее преобразования к форме простого присваивания, не изменяют перевод, определяемый заданной грамматикой, поскольку согласно правилам работы преобразователя они не должны передаваться на выход. Приведенные рассуждения позволяют сделать вывод в форме следующего утверждения.    

Утверждение.  Для любой L-атрибутной грамматики в форме простого присваивания, у которой входная грамматика относится к классу LL(1) грамматик, можно построить нисходящий детерминированный преобразователь с магазинной памятью, выполняющий перевод, заданный этой грамматикой.

Подводя итог приведенным рассуждениям, опишем порядок построения  АТ - преобразователя по заданной LАТ-грамматике в форме простого присваивания следующим образом:

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

     (s₀, <заданная цепочка>, h₀),

     б) откажемся от совмещения команд для правил вида <А> --> b , где b является терминалом, имеющим атрибут, и- некоторая цепочка из терминальных и нетерминальных символов, используя вместо команды

     f(s₀, b,<A>) = (s₀, ^R)

две команды

     f * 0(s₀, b, <A>) = (s₀, ^Rb)      f(s₀, b, b) = (s₀, $),

поскольку при выполнении  одной  команды  терминальный  символ и, следовательно, его атрибут не записываются в магазин, что  делает невозможным формирование  указателя для правила вычисления атрибута, в котором используется атрибут терминала b. 3) Для каждого правила заданной LАТ- грамматики построим инструкцию, описывающую построение фрагмента стека при записи правой части правила в стек. 4) Пронумеруем инструкции и введем обозначение инструкции в виде символа  #  с последующим номером инструкции. Во всех командах построенного преобразователя, выполняющих запись цепочек в стек, заменим цепочки обозначениями соответствующих инструкций, выполняющих запись атрибутной цепочки в стек. В результате получаем функцию преходов в виде:

     f(s₀, <входной символ>,<символ в вершине магазина>) = (s₀, <номер выполняемой инструкции>).

Подразумевается, что построенный таким образом АТ-преобразователь должен работать в соответствии с правилами 1-6 и выполнять действия, предписываемые инструкциями.