Пред.СтраницаСлед.Страница Раздел Содержание
5.3.2. Форма простого присваивания АТ-грамматик
Вторым
видом ограничений, накладываемых на АТ-грамматики,
предназначенные для построения преобразователей, является запрещение
использования в правилах вычисления атрибутов нетерминальных символов и
некоторых атрибутов символов действия функциональных зависимостей. При
выполнении этого запрета правила вычисления атрибутов должны иметь форму
операторов присваивания с переменными в правой части. Грамматика с такими
правилами называется АТ-грамматикой простого
присваивания.
Чтобы
сократить число правил вычисления атрибутов, в таких грамматиках разрешается
использовать правила не только в виде простых операторов присваивания
a = b,
но и в виде операторов
множественного присваивания
(a1, a2, a3) = b,
когда нескольким переменным
присваивается одно и то же значение. Правила в виде простых и множественных
операторов присваивания называются копирующими правилами. Правую часть таких
правил называют источником, а каждый атрибут левой части - приемником.
Определение. Множество копирующих
правил называется независимым тогда
и только тогда, когда источник каждого правила из этого множества не входит
ни в одно из других правил этого множества. |
Если копирующие правила являются зависимыми, то в некоторых случаях их можно объединить в одно правило. Например, правила
a = x и (b, c) = x
можно записать как одно правило
(a, b, c) = x,
или правила
(a, x) = z и (b,c) = x
также можно записать в виде
(a, b, c, x) = z,
поскольку
источнику второго правила x, согласно
первому правилу, присваивается значение z. Если копирующие правила являются
независимыми, то их объединять нельзя. Используя понятие независимости
копирующих правил, сформулируем следующее определение.
Определение. АТ-грамматика имеет форму простого присваивания, если выполняются следующие условия: а) все правила вычисления атрибутов, за исключением правила вычисления синтезируемых символов действия, являются копирующими, б) для каждого правила грамматики множество копирующих правил
является независимым. |
Свойства L - атрибутности и простого
присваивания АТ-грамматик являются необходимыми для построения
преобразователя, реализующего атрибутный
перевод.
Утверждение:
|
Такое построение связано с исключением некопирующих правил вычисления атрибутов и добавлением вместо них операционных символов в правила грамматики.
Прежде
чем описать последовательность преобразования некопирующих правил, рассмотрим
пример, иллюстрирующий как такое преобразование выполняется. Допустим, что
задано некопирующее атрибутное правило
в виде:
<A> ® a/x<B>%y<C>/z
!! z = f(x, y).
Вначале введем новый символ действия, представляющий вычисление функции f. Обозначим символ действия {f} и снабдим его тремя атрибутами. Два
наследуемых атрибута b1, b2 необходимы для
задания аргументов функции, и один синтезируемый атрибут с – для получения значения функции. В результате получаем
следующее определение символа действия:
{f}/b1/b2%c,
где значение с определяется как функция f(b1, b2).
Затем включим новый символ действия в правило грамматики и заменим некопирующее правило вычисления атрибута с функцией f в правой части несколькими копирующими правилами, устанавливающими связь между атрибутами нового символа действия и аргументами функции f. После выполнения перечисленных действий может быть получено следующее атрибутное правило:
<A>
® a/x<B>%y{f}/b1/b2%c<C>/z
b1 = x; b2 =
y; z = c,
которое
содержит только копирующие правила, два из которых копируют аргументы, и одно -
результат. Это правило дает тот же эффект, что и первоначальное правило, в том
смысле, что оба правила порождают одинаковые выходные цепочки с атрибутами и
дают одно и то же значение атрибута z.
Необходимо
подчеркнуть, что место включения нового нетерминального символа в правило
грамматики должно выбираться с таким расчетом, чтобы не нарушить свойств L - атрибутности заданной грамматики.
Если в рассматриваемом примере поместить новый символ действия перед
нетерминалом <B>, то получим правило
<A>
® a/x{f}/b1/b2%c<B>%y<C>/z
b1 = x; b2 = y; z = e,
в котором
значение наследуемого атрибута 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 - атрибутности, то преобразовать такую
грамматику невозможно.