Теория и реализация языков программирования



         

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


Типичным примером правил вывода служит четв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

:V
1x ... x V
t
V

все атрибуты

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

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




Содержание  Назад  Вперед