- •2.2 Определение непроизводящих символов.
- •2.5 Исключение леворекурсивных правил.
- •3.4.2 Построение функции перв(µ)
- •Построение Магазинного автомата по кс-грамматике.
- •Построение нисходящих магазинных распознавателей.
- •Описание перевода. Су-схемы.
- •Описание перевода. Т-грамматики.
- •17.Соответствие между т-грамматики и су-схемы.
- •Определение магазинного нисходящего преобразователя и его работа.
- •Построение нисходящего преобразователя.
- •20. Атрибутные грамматики. Типы атрибутов. Правила вычисления атрибутов.
- •Грамматики простого присваивания. Построение формы простого присваивания.
- •Правила работы нисходящего атрибутного преобразователя.
- •Построение нисходящего атрибутного преобразователя.
- •Программная реализация нисходящего атрибутного преобразователя.
Грамматики простого присваивания. Построение формы простого присваивания.
Форма простого присваивания АТ-грамматик
Вторым видом ограничений, накладываемых на АТ-грамматики, предназначенные для построения преобразователей, является запрещение использования в правилах вычисления атрибутов нетерминальных символов и некоторых атрибутов символов действия функциональных зависимостей. При выполнении этого запрета правила вычисления атрибутов должны иметь форму операторов присваивания с переменными в правой части. Грамматика с такими правилами называется АТ-грамматикой простого присваивания. Чтобы сократить число правил вычисления атрибутов, в таких грамматиках разрешается использовать правила не только в виде простых операторов присваивания 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 - атрибутности, то преобразовать такую грамматику невозможно.