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

5.4.2. Преобразование LАТ-грамматики в LАТ-грамматику в форме простого присваивания

Опишем последовательность шагов для преобразования заданной LАТ-грамматики в

LАТ-грамматику в форме простого присваивания.

1) Для каждой функции f(x1, x2, ..., xn), входящей в правила вычисления атрибутов, связанных с некоторым правилом грамматики, введем дополнительный символ действия с n+1 атрибутом, который обозначим {f} и определим следующим образом:

{f}/a1/a2/.../an%y,

где значение y определяется как f(a1, a2, ..., an).

2) Для каждого некопирующего правила

(z1, z2, ..., zn) := f(x1, x2, ..., xn),

связанного с некоторым правилом грамматики, включим в правую часть правила грамматики символ

{f}/a1/a2/.../an%y,

полагая, что символы a1, a2, ..., an и y не содержатся в правиле грамматики, и заменим некопирующее правило на n+1 копирующих правил вида:

…….. ai := xi; ……..

(z1, z2, ..., zm) := y.

3) При включении символа действия {f}/a1/a2/.../an%y необходимо соблюдать следующие ограничения:

а) Символ действия должен располагаться правее каждого символа правой части правила грамматики, атрибутом которого является один из аргументов x1, x2, ..., xn.

67

б) Символ действия должен располагаться левее каждого символа правой части грамматики, атрибутом которого является один из символов z1, z2, ..., zm.

в) Если существует несколько позиций для размещения символа действия, то предпочтение следует оказать самой левой из возможных позиций.

4) Два копирующих правила одного и того же правила грамматики следует объединить в одно правило, если источник одного из них входит в другое. Это объединение осуществляется путем удаления правила с лишним источником и объединения его получателя с получателями оставшегося правила. Следует соблюдать осторожность при объединении зависимых правил, использующих в правой части процедуры без параметров, которые можно рассматривать как константы и, следовательно, считать источниками, поскольку могут возникнуть ошибки за счет того, что разные вызовы процедур могут давать разные значения.

Вкачестве примера преобразования AT-грамматики в грамматику в форме простого присваивания выполним такое преобразование для ранее рассмотренной грамматики Г5.0. Введем для правил, содержащих операции операционные символы {сложить} и {умножить}, приписывая каждому символу два наследуемых и один синтезируемый атрибуты.

Врезультате получаем грамматику в форме простого присваивания:

68

Ограничения, накладываемые на атрибуты LAT–грамматиками в форме простого присваивания, делают возможным использование таких грамматик для построения атри-

бутных преобразователей (АТ-преобразователей). Основой построения АТ– преобразователей являются следующие рассуждения.

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

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

69

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

Такой вывод включает не только терминальные, нетерминальные и операционные символы, но и атрибуты, значения которых еще не определены. Для отображения связей между атрибутами, соответствующих операциям присваивания, воспользуемся линейным выводом. Такой вывод строится следующим образом:

а) Переместим атрибуты с позиции индексов в строку и поместим их непосредственно за соответствующим символом грамматики б) Каждому копирующему правилу, которое соответствует шагу отложенных вычисле-

ний, поставим в соответствие дугу, связывающую в цепочки вывода источник и приемник и направленную от источника к приемнику.

в) Множественным копирующим правилам поставим в соответствие в выводимой цепочке последовательность дуг, связывающих источник с приемниками.

г) Если в процессе вывода атрибут получает значение, то это значение запишим в выводимую цепочку вместо имени атрибута, а соответствующую дугу удалим.

д) При замене нетерминального символа в выводимой цепочке он удаляется, но его атрибуты должны остаться на месте.

Линейный вывод цепочки с/1+с/2*с/3 в грамматике Г 5. 3 можно представить в следующем виде:

70