Формальные свойства

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

Пусть имеется КС-грамматика G = (V, N, S, P), где V - (конечный) алфавит терминальных и нетерминальных символов;

- множество нетерминальных символов; S

N - "начальный "символ, не входящий в правые части правил, и P - множество правил.

Семантические правила дополняют G следующим образом. С каждым символом X

V связывается конечное множество атрибутов A(X). A(X) разбивается на два непересекающихся множества: множество синтезированных атрибутов A0(X) и множество унаследованных атрибутов A1(X). Множество A1(S) должно быть пустым (то есть начальный символ S не должен иметь унаследованных атрибутов); аналогично, множество A0(X) пусто, если X - терминальный символ. Каждый атрибут R из множества A(X) имеет (возможно, бесконечное) множество значений VR. Для каждого вхождения X в дерево вывода семантические правила позволяют определить одно значение из множества VR для соответствующего атрибута.

Пусть P состоит из m правил, и пусть p-е правило имеет вид

Xp0

Xp1Xp2...Xpnp ;

Пример 2.1.

(html, txt)

где np > 0, Xp0

N и Xpj

V для 1

np. Семантическими правилами называются функции fpjR, определ_нные для всех 1

m, 0

np и некоторых

A0(Xpj), если j = 0, или

A1(Xpj), если j > 0. Каждая такая функция представляет собой отображение из V

1 x V

2 x ... x V

t в VR для некоторого t = t(p, j,

) > 0, где все

i =

i(p, j,

) являются атрибутами некоторых Xpki , при 0

ki = ki(p, j,

)

np, 1

t. Другими словами, каждое семантическое правило отображает значения некоторых атрибутов символов

и значение некоторого атрибута символа

Грамматика (таблица 1.1), например, представляется в виде G = ({0, 1, ".", B, L, N}, {B, L, N}, N, {B

0, B

1, L

B, L

LB, N

L, N

L.L}).

Атрибутами здесь являются

A0(B) = {v}, A1(B) = {s}; A0(L) = {v, l}, A1(L) = {s}; A0(N) = {v}, A1(N) =

и A0(x) = A1(x) =

для x

{0, 1, .}. Множествами значений атрибутов будут Vv ={рациональные числа}, Vs = Vl = {целые числа}.
Типичным примером правил вывода служит четвeртое правило X40

X41X42 , где n4 = 2, X40 = X41 = L, X42 = B. Так же типично и семантическое правило f40v, соответствующее этому правилу вывода. Оно определяет v(X40) через другие атрибуты; в данном случае f40v отображает Vv x Vv в Vv согласно формуле f40v(x, y) = x + y. (Это есть не что иное, как правило v(L1) = v(L2) + v(B) из (таблица 1.1); используя довольно громоздкую запись, введeнную в предыдущем абзаце, получим:

t(4, 0, v) = 2,

1(4, 0, v) =

2(4, 0, v) = v, k1(4, 0, v) = 1, k2(4, 0, v) = 2).

Семантические правила используются для сопоставления цепочкам КС языка"значения" следующим образом1)

. Для любого вывода терминальной цепочки t из S при помощи синтаксических правил построим обычное дерево вывода. А именно, корнем дерева будет S, а каждый узел помечается либо терминальным символом, либо нетерминалом Xp0, соответствующим применению p-го правила для некоторого p; в последнем случае у этого узла будет np непосредственных потомков.

Рис. 2.2.

Пусть теперь X - метка некоторого узла дерева и пусть R

A(X) - атрибут символа X. Если

A0(X), то X = Xp0 для некоторого p, если же

A1(X), то X = Xpj для некоторых j и p. В обоих случаях дерево "в районе" этого узла имеет вид (рис. 2.2). По определению атрибут

имеет в этом узле значение v, если в соответствующем семантическом правиле

fpj

1x ... x V

все атрибуты

1, ... ,

t уже определены и имеют в узлах с метками Xpk1 , ... , Xpkt значения v1, ... , vt соответственно, а v = fpj

(v1, ... , vt). Процесс вычисления атрибутов на дереве продолжается до тех пор, пока нельзя будет вычислить больше ни одного атрибута. Вычисленные в результате атрибуты корня дерева представляют собой "значение", соответствующее данному дереву вывода (рис. 1.6).

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

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

Отметим, что этот метод определения семантики обладает такой же мощностью, как и всякий другой возможный метод, в том смысле, что значение любого атрибута в любом узле может произвольным образом зависеть от структуры всего дерева. Предположим, например, что в КС грамматике всем символам, кроме S, приписано по два унаследованных атрибута: l ("положение") и t ("дерево"), а всем нетерминалам, кроме того, по одному синтезированному атрибуту s ("поддерево"). Значениями l будут конечные последовательности положительных целых чисел

, определяющие местонахождение узла в дереве в соответствии с системой обозначения Дьюи. Атрибуты t и s представляют собой множество упорядоченных пар (l, X), где l - положение узла, а X - символ грамматики, обозначающий метку узла с положением l. Семантическими правилами для каждого синтаксического правила (пример 2.1) служат

(2.4)

Следовательно, для дерева (рис. 1.2), например, мы имеем

s(N) = {(1, L), (2, ?), (3, L), (1.1, L), (1.2, B), (3.1, L), (3.2, B), (1.1.1, L), (1.1.2, B), (1.2.1, 1), (3.1.1, B), (3.2.1, 1), (1.1.1.1, L), (1.1.1.2, B), (1.1.2.1, 0), (3.1.1.1, 0), (1.1.1.1.1, B), (1.1.1.2.1, 1), (1.1.1.1.2.1, 1)}.

Ясно, что эта запись содержит всю информацию о дереве вывода. Согласно семантическим правилам (2.4), атрибут t во всех узлах (кроме корня) представляет собой множество, характеризующее всe дерево вывода; атрибут l определяет местонахождение этих узлов. Отсюда сразу следует, что любая мыслимая функция, определ_нная на дереве вывода, может быть представлена как атрибут произвольного узла, поскольку эта функция имеет вид f(t, l), для некоторого f. Аналогично, можно показать, что для определения значения, связанного с произвольным деревом вывода, достаточно только синтезированных атрибутов, поскольку синтезированный атрибут w, вычисляемый по формуле

(2.5)

в корне дерева полностью определяет всe дерево3)

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

Содержание раздела