5.3.3. Преобразование LАТ-грамматики в LАТ-грамматику в форме простого присваивания.
В качестве итога проведенного анализа опишем последовательность преобразования заданной LАТ-грамматики в LАТ-грамматику в форме простого присваивания.
1) Для каждой функции f(x1, x2, ..., xn), входящей в правила вычисления атрибутов, связанных с некоторым правилом грамматики, введем дополнительный символ действия с n+1 атрибутом, который обозначим {f} и определим следующим образом:
2) Для каждого некопирующего правила
а) Символ действия должен располагаться правее каждого символа правой части правила грамматики, атрибутом которого является один из аргументов x1, x2, ..., xn.
б) Символ действия должен располагаться левее каждого символа правой части грамматики, атрибутом которого является один из символов z1, z2, ..., zm.
в) Если существует несколько позиций для размещения символа действия, то предпочтение следует оказать самой левой из возможных позиций.
4) Два копирующих правила одного и того же правила грамматики следует объединить в одно правило, если источник одного из них входит в другое. Это объединение осуществляется путем удаления правила с лишним источником и объединения его получателя с получателями оставшегося правила. Отметим, что следует соблюдать осторожность при объединении зависимых правил, использующих в правой части процедуры без параметров, которые можно рассматривать как константы и, следовательно, считать источниками, поскольку могут возникнуть ошибки за счет того, что разные вызовы процедур могут давать разные значения. Например, правила
В результате получаем грамматику в форме простого присваивания:
Г 5. 3 :
Если из правил LAT-грамматики
удалить все атрибуты, то получится транслирующая
грамматика, для которой может быть построен нисходящий магазинный
преобразователь. Следовательно, АТ-преобразователь
можно строить в виде магазинного преобразователя, дополненного действиями,
связанными с обработкой атрибутов.
При определении
значений синтезируемых атрибутов в LAT-грамматиках
могут возникать отложенные присваивания, поэтому, планируя работу АТ-преобразователя,
необходимо предусмотреть возможность сохранения атрибутов, значения которых
еще не определены. Для сохранения таких атрибутов может быть использован
магазин. Простое сохранение атрибутов является недостаточным, поскольку
необходимо еще сохранять сведения о том, какое значение должен получить
атрибут. Учитывая, что в форме простого присваивания используется только
один способ определения значения - с помощью оператора присваивания, можно
отобразить сведения о присваиваниях в магазине с помощью указателей. Для
этого в каждый элемент магазина, соответствующий источнику, можно записать
указатель на элемент, соответствующий приемнику. Такие указатели можно
устанавливать в магазине при записи в него правой части правила грамматики.
В этом случае должен обеспечиваться порядок определения значений атрибутов,
в котором всегда вначале определяется источник, а затем приемник. Получение
такого порядка вычислений гарантируют свойства L
- атрибутности грамматики. Оно предусматривает,
что каждое значение атрибута определяется значениями атрибутов, расположенных
слева от него в правилах грамматики. Учитывая, что в магазин записывается
зеркальное отображение правой части правила, можно утверждать, что атрибуты,
расположенные левее рассматриваемого атрибута, будут вычисляться раньше
него, обеспечивая тем самым требуемый порядок вычисления атрибутов.