E _t синтезированный t

R _{p, t} унаследованный p синтезированный t

Атрибуты операционных символов – унаследованные

1. S i _p1 = E _q1 {ПРИСВОИТЬ} _{p2, q2}

P2 p1

q2 q1

(2) E _t2 i _p1 R _{p2, t1}

p2 p1

t2 t1

(3) R _{p1, t2} + i _q1 {СЛОЖИТЬ} _{p2, q2, r1}R _{r2, t1}

r1 , r2 GETNEW

p2 p1

q2 q1

t2 t1

(4) R _{p1, t2} i _q1 {УМНОЖИТЬ} _{p2, q2, r1}R _{r2, t1}

r1 , r2 GETNEW

p2 p1

q2 q1

t2 t1

(5) R _{p1, t2}

p2 p1

Рис. 3.9

На рис. 3.10 приведено атрибутное дерево вывода в АТ-грамматике G₅^А, соответствующее входной цепочке i ₅ = i ₇ + i ₂ i ₃ при условии, что процедура GETNEW выдает последовательные адреса ячеек, начиная с адреса 100. Заметим (см. рис. 3.9), что при применении правила (5) синтезированному атрибуту нетерминала R присваивается значение его унаследованного атрибута. Затем это зна­чение передается вверх по дереву вывода как синтезированный атрибут нетерминала из левой части правил (4), (3) и (2) и используется в качестве второго атрибута операционного символа {ПРИСВОИТЬ}.

Определение. Последовательность атрибутных входных и операционных сим­волов, полученная по атрибутному дереву вывода в АТ-грамматике, называется атрибутной активной цепочкой.

Определение. Множество пар, первым элементом которых является атрибутная входная цепочка, а вторым элементом – атрибутная последовательность операцион­ных символов атрибутной активной цепочки, называется атрибутным переводом (G^A), определяемым АТ-грамматикой.

Например, грамматика G₅^А для входной цепочки i ₅ = i ₇ + i ₂ i ₃ определяет следующую атрибутную последовательность операцион­ных символов:

{ СЛОЖИТЬ } _{7, 2, 100} { УМНОЖИТЬ} _{100, 3, 101} { ПРИСВОИТЬ } _{5, 101} .

Определение. Дерево вывода в АТ-грамматике на­зывается завершенным, если в результате применения процедуры построения дерева значения всех атрибутов всех символов ока­жутся вычисленными.

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

Определение. АТ-грамматика называется коррект­ной тогда и только тогда, когда в результате применения опи­санной процедуры построения атрибутного дерева вывода получа­ется завершенное дерево.

Рассмотрим два подкласса корректных АТ-грамматик, которые часто используются при проектировании компиляторов: L-атри­бутные транслирующие грамматики и S-атрибутные транслирующие грамматики.

3.2.4. L- и s-атрибутные транслирующие грамматики

Определение. АТ-грамматика называется L-атрибутной тогда и только тогда, когда выполняются следующие условия:

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

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

3. Аргументами правила вычисления значения синтезированно­го атрибута операционного символа могут быть только унаследо­ванные атрибуты этого символа.

Является ли заданная АТ-грамматика L-атрибутной, можно про­верить, независимо исследуя каждое правило вывода и каждое правило вычисления значения атрибута.

Примером L-атрибутной транслирующей грамматики является грамматика G₅^А (см. рис. 3.9).

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

В L-атрибутной транслирующей грамматике атрибуты символов А, В и С из правила вывода А ВС можно вычислять в следующем порядке:

• унаследованные атрибуты символа А;

• унаследованные атрибуты символа B;

• синтезированные атрибуты символа В;

• унаследованные атрибуты символа С;

• синтезированные атрибуты символа С;

• синтезированные атрибуты символа А.

Определение. АТ-грамматика называется S-атрибутной тогда и только тогда, когда она является L-атрибутной и все атрибуты нетерминалов – синтезированные.