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

Порядок построения АП

 Построение детерминированного атрибутного преобразователя можно выполнить для любой 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 и выполнять действия, предписываемые инструкциями.

Содержание символов действия, используемых в инструкциях, можно описать следующим образом : {СЛЕДУК} - определяет следующий свободный адрес таблицы значений и присаваивает его своему атрибуту, {СЛОЖ} - читает из магазина атрибуты, формирует атом, состоящий из знака операции сложения, адресов операндов и результата, и передает атом на выход, {ВЫЧИТ} - читает из магазина атрибуты, формирует атом, состоящий из знака операции вычитания, адресов операндов и результата, и передает атом на выход, {УДАЛИТЬ(3)} - удаляет из вершины магазина три символа.

4) Включая обозначение построенных инструкций в команды преобразователя и учитывая, что обработка символов действия была включена в правила работы АП, команды (7) - (12) можно исключить из списка команд. В результате получаем систему команд в виде

Демонстрация работы АП

Работу построенного АТ-преобразователя рассмотрим на примере трансляции цепочки i%22-i%24 при начальном значении атрибута b=28, которое является указателем на первый свободный элемент ТЗ. Описание работы представим в виде последовательности тактов. 1. В исходном состоянии в стеке находится маркер дна, а на входе - заданная цепочка.

2. После выполнения команды (1) в стек заносится начальный символ грамматики с двумя атрибутами, один из которых имеет начальное значение 28.

3. Затем выполняется команда (2), которая предписывает построение фрагмента стека, определяемого инструкцией #2. В результате получаем:

4. На входе и в вершине магазина находятся терминальные символы, поэтому выполняется команда (6), которая сравнивает терминалы, читает атрибут входного терминала и проверяет значение магазинного терминала. Обнаружив, что значением магазинного терминала является указатель, команда осуществляет запись значения атрибута входного терминала в ячейку стека, определяемую указателем.

5. Знак минуса и нетерминал <R> в вершине магазина определяют выполнение команды (4). Эта команда удаляет нетерминал из вершины стека, производит построение фрагмента стека в соответствии с инструкцией #4 и сдвигает входную головку на следующую позицию.

6. Преобразователь, анализируя символ, находящийся в вершине, и обнаружив, что это операционный символ, выполняет действия, предписываемые этим символом, которые заключаются в вычислении указателя на следующий свободный элемент таблицы значений. Полученное значение указателя присваивается элементу стека с указателем SP-10, поскольку этот указатель записан в качестве значения атрибута операционного символа. В результате имеем:

7. Обнаружив в вершине стека терминал, преобразователь читает очередной символ на входе и сравнивает его с магазинным терминалом, выполняя команду (6). Убедившись, что символы совпадают, преобразователь читает атрибут входного терминала и проверяет значение атрибута магазинного терминала. Затем он заносит значение атрибута входного нетерминала в ячейку с атрибутом SP-3, удаляет атрибут из стека и сдвигает входную головку.

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

9. Символ в вершине магазина и входной терминал определяют возможность выполнения преобразователем команды (5). В результате выполнения инструкции, соответствующей этой команде, определяется значение синтезируемого атрибута. В ячейке стека, выделенной этому атрибуту, находится указатель, представляющий собой начало цепочки. Преобразователь заносит полученное значение атрибута во все ячейки стека, входящие в цепочку, и удаляет нетерминал R и его атрибуты из магазина.

10. После удаления нетерминала R и его атрибутов в стеке остаются атрибуты начального символа грамматики, которые могут быть использованы для построения дальнейшей трансляции конструкций, включающих арифметические выражения, например, оператора присваивания. Если же конструкции более высокого уровня не рассматриваются, то преобразователь просто удаляет все атрибуты из стека, поскольку их значения определены. После удаления атрибутов из стека в вершине магазина оказывается маркер дна. Маркер дна и пустой символ на входе определяют команду преобразователя (13) , которая переводит преобразователь в заключительное состояние s₁.