5.3.4. Расширенный вывод для ат-грамматики

    В качестве иллюстрации описанного способа обработки атрибутов рассмотрим изображение расширенного вывода в грамматике Г _{5. 5}. Такой вывод включает не только терминальные, нетерминальные и операционные символы, но и атрибуты, значения которых еще не определены. Для отображения связей между атрибутами, соответствующих операциям присваивания, воспользуемся линейным выводом. Такой вывод строится следующим образом:а) Переместим атрибуты с позиции индексов в строку и поместим их непосредственно за соответствующим символом грамматики.б) Каждому копирующему правилу, которое соответствует шагу отложенных вычислений, поставим в соответствие дугу, связывающую в цепочки вывода источник и приемник, и направленную от источника к приемнику.в) Множественным копирующим правилам поставим в соответствие в выводимой цепочке последовательность дуг, связывающих источник с приемниками.г) Если в процессе вывода атрибут получает значение, то это значение запишем в выводимую цепочку вместо имени атрибута, а соответствующую дугу удалим.д) При замене нетерминального символа в выводимой цепочке он удаляется, но его атрибуты должны остаться на месте.Линейный вывод цепочки с/1+с/2*с/3 в грамматике Г _{5. 5} можно представить в следующем виде:

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

5.4. Атрибутные преобразователи ( ап )

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

5.4.1. Представление правил lat-грамматики в магазине.

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

E%d  E%e+T%f{сложить}/x/y%z x=e;  y=f; d=z;

следующим образом:

На рисунке атрибут левой части правила d расположен непосредственно под самым правым символом правой части правила,что соответствует построению левого вывода грамматики в магазине. Действительно, если заменять нетерминальные символы в вершине магазина правой частью правила грамматики, оставляя его атрибуты в магазине, то самый правый символ заменяющего правила окажется непосредственно над атрибутами удаляемого нетерминала.