s791

Пред.СтраницаСлед.Страница Раздел Содержание

5.3.3. Преобразование 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.
б) Символ действия должен располагаться левее каждого символа правой части грамматики, атрибутом которого является один из символов z1, z2, ..., zm.
в) Если существует несколько позиций для размещения символа действия, то предпочтение следует оказать самой левой из возможных позиций.
4) Два копирующих правила одного и того же правила грамматики следует объединить в одно правило, если источник одного из них входит в другое. Это объединение осуществляется путем удаления правила с лишним источником и объединения его получателя с получателями оставшегося правила. Отметим, что следует соблюдать осторожность при объединении зависимых правил, использующих в правой части процедуры без параметров, которые можно рассматривать как константы и, следовательно, считать источниками, поскольку могут возникнуть ошибки за счет того, что разные вызовы процедур могут давать разные значения. Например, правила

x = СЛЕДУК и y = СЛЕДУК

объединить нельзя, поскольку значениями x и y будут указатели на соседние элементы ТЗ. В качестве примера преобразования АТ-грамматики в грамматику в форме простого присваивания выполним такое преобразование для грамматики
Г _{5. 0}. Введем для правил, содержащих операции, операционные символы {сложить} и {умножить}, приписывая каждому символу два наследуемых и один синтезируемый атрибуты.
В результате получаем грамматику в форме простого присваивания:

Г _{5. 5} :

<S> ® E%a{ОТВЕТ/b} !! b=a;

<E>%d ® <E>%e+T%f{СЛОЖИТЬ}/x1/x2%y
              !! x1 = e; x2 = f; d = y;
<E>%g ® <T>%h
             !! g = h;
<T>%i ® <T>%j*<P>%k{УМНОЖИТЬ}/z1/z2%u
             !! z1 = j; z2 = k; i = u;
<T>%m ® <P>%n
            !! m = n
<P>%p ® (<E>%q)
          !! p = q;
<P>%r ® c/s
        !! r = s;

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

Пред.Страница След.СтраницаРаздел Содержание