Атрибутные транслирующие грамматики

Атрибутная транслирующая грамматика - это транслирующая грамматика, к которой добавляются следующие определения:

1. Любой входной символ, символ действия или нетерминальный символ имеет конечное множество атрибутов. Любой атрибут имеет (возможно бесконечное) множество допустимых значений.

2. Все атрибуты нетерминальных символов и символов действия делятся на наследуемые и синтезируемые.

3. Правила вычисления наследуемых нетерминалов определяются следующим образом:

а) любому вхождению наследуемого атрибута в правую часть данной продукции сопоставляется правило вычисления значения этого атрибута как функции некоторых других атрибутов символов, входящих в правую или левую часть данной продукции;

б) задается начальное значение каждого наследуемого атрибута начального символа.

4. Правила вычисления синтезируемых атрибутов определяются следующим образом:

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

б) каждому синтезируемому атрибуту символа действия сопоставляется правило вычисления значения этого атрибута как функции некоторых других атрибутов этого символа действия.

В пункте 1 данного определения говорится о том, что входные символы, символы действия и нетерминалы должны быть атрибутными. Описывая грамматику, атрибуты записываются в виде индексов.

Пример: X_p,q,r®b_sY_y,uZ_v,w. Пусть q, r - синтезируемые атрибуты, следовательно, они вычисляются на шаге 4а. Пусть y, v - наследуемые атрибуты, следовательно, они вычисляются на шаге 3а. Формулы вычисления атрибутов: qsin(u+w), (r,v) s*u, yp. В данном случае «» эквивалентен «получить значение».

Атрибутные транслирующие грамматики используются для определения атрибутных деревьев вывода, а затем - атрибутной последовательности актов и атрибутных переводов. Под обратной стрелкой подразумевается оператор присваивания. Левая часть каждого присваивания - это либо один атрибут, либо список атрибутов, заключенных в скобки. Правая часть - всегда будет некоторым выражением. Эта запись означает, что значение выражения правой части нужно присвоить каждому атрибуту, входящему в левую часть. Так, второе из данных правил присваивает произведение s*u обоим атрибутам r и v.

Алгоритм построения атрибутного дерева вывода:

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

2. Присвоить значения атрибутам входных символов, входящих в дерево вывода.

3. Присвоить начальные значения наследуемым атрибутам начального символа дерева вывода.

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

5. Если выполнение шага 4 приведет к тому, что значение всех атрибутов всех символов дерева окажутся вычисленными, то полученное дерево называется завершенным. В противном случае мы называем дерево незавершенным.

Замечание:

1. Пункты 3 и 4 определения атрибутной грамматики гарантируют, что для любого атрибута нетерминального символа или символа действия имеется соответствующее правило вычисления. Так как любой символ дерева вывода либо входит в правую часть некоторой продукции (т.е. продукции, соединяющей этот символ с его предком в дереве), либо является вершиной дерева (начальным символов), то любой наследуемый атрибут данного символа должен иметь правило, согласно одному из правил пункта 3. Так как любой нетерминальный символ дерева вывода входит в левую часть некоторой продукции, то правила пункта 4а гарантируют наличие правила вычисления для любого синтезируемого нетерминального атрибута. Правила пункта 4б гарантируют наличие правила для любого синтезируемого атрибута символа действия.

2. Хотя для каждого атрибута, входящего в дерево вывода, существует правило его вычисления, нет никакой гарантии, что его значение действительно можно вычислить и таким образом получить завершенное дерево. Так как правило можно применять только после того, как получены все его аргументы, между атрибутами может возникнуть круговая зависимость.

Если атрибутная грамматика такова, что шаги 1-5 процедуры построения дерева всегда дают в итоге завершенное дерево, то она называется вполне определенной или корректной. При проектировании компиляторов используют только вполне определенные грамматики.

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

Атрибутная последовательность действия данной атрибутной последовательности актов называются переводом атрибутной входной грамматики.

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

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

Вопросы и упражнения

1.Что понимается под атрибутной транслирующей грамматикой?

2.По каким правилам определяются наследуемые и синтезируемые атрибуты?

3.Что такое завершенное дерево вывода?

4. Какая грамматика считается корректной?

6. Что понимают под атрибутным переводом?

7. Как Вы думаете, для описания трансляторов с каких типов языков программирования удобно использовать атрибутные транслирующие грамматики?