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

    5.3.2. Форма простого присваивания АТ-грамматик

    Вторым видом ограничений, накладываемых на АТ-грамматики, предназначенные для построения преобразователей, является запрещение использования в правилах вычисления атрибутов нетерминальных символов и некоторых атрибутов символов действия функциональных зависимостей. При выполнении этого запрета правила вычисления атрибутов должны иметь форму операторов присваивания с переменными в правой части. Грамматика с такими правилами называется АТ-грамматикой простого присваивания.
    Чтобы сократить число правил вычисления атрибутов, в таких грамматиках разрешается использовать правила не только в виде простых операторов присваивания
                                                            a = b,
но и в виде операторов множественного присваивания
                                                            (a1, a2, a3) = b,
когда нескольким переменным присваивается одно и то же значение. Правила в виде простых и множественных операторов присваивания называются копирующими правилами. Правую часть таких правил называют источником, а каждый атрибут левой части - приемником.
 
Определение.

Множество копирующих правил называется независимым тогда и только тогда, когда источник каждого правила из этого множества не входит ни в одно из других правил этого множества.
 
Если копирующие правила являются зависимыми, то в некоторых случаях их можно объединить в одно правило. Например, правила

можно записать как одно правило или правила также можно записать в виде поскольку источнику второго правила x, согласно первому правилу, присваивается значение z. Если копирующие правила являются независимыми, то их объединять нельзя. Используя понятие независимости копирующих правил, сформулируем следующее определение.
Определение.

АТ-грамматика имеет форму простого присваивания, если выполняются следующие условия:

а) все правила вычисления атрибутов, за исключением правила вычисления синтезируемых символов действия, являются копирующими,

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

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

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

    Вначале введем новый символ действия, представляющий вычисление функции f. Обозначим символ действия {f} и снабдим его тремя атрибутами. Два наследуемых атрибута b1, b2 необходимы для задания аргументов функции, и один синтезируемый атрибут с – для получения значения функции. В результате получаем следующее определение символа действия:
  где значение с определяется как функция f(b1, b2).

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

которое содержит только копирующие правила, два из которых копируют аргументы, и одно - результат. Это правило дает тот же эффект, что и первоначальное правило, в том смысле, что оба правила порождают одинаковые выходные цепочки с атрибутами и дают одно и то же значение атрибута z.
    Необходимо подчеркнуть, что место включения нового нетерминального символа в правило грамматики должно выбираться с таким расчетом, чтобы не нарушить свойств L - атрибутности заданной грамматики. Если в рассматриваемом примере поместить новый символ действия перед нетерминалом <B>, то получим правило в котором значение наследуемого атрибута b2 определяется синтезируемым атрибутом y, расположенным правее него, что нарушает свойство L - атрибутности.
Если же поместить новый символ действия после символа <C>, то получим правило
                                       <A> ® a/x<B>%y<C>/z{f}/b1/b2/c
                                                  b1 = x; b2 = y; z = c,
в котором атрибут z определяется по атрибуту с, расположенному правее него, что также нарушает свойство L - атрибутности. Таким образом, в рассматриваемом примере оказалось, что расположить новый символ действия без нарушения свойств L - атрибутности  возможно только в одной позиции правила - между нетерминалами <B> и <C>.
    В общем случае в правиле может оказаться несколько позиций, пригодных для размещения нового символа действия. Если это так, то предпочтение следует отдать самой левой из возможных позиций, поскольку в некоторых случаях самые левые символы действия не нужно заносить в магазин преобразователя, производящего обработку.
    Если же оказывается, что все позиции, в которых может быть расположен новый символ действия, являются непригодными и приводят к нарушению свойств L - атрибутности, то преобразовать такую грамматику невозможно.

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