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



         

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


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

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

N \subseteq 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
j
np. Семантическими правилами называются функции fpjR, определ_нные для всех 1
p
m, 0
j
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
i
t. Другими словами, каждое семантическое правило отображает значения некоторых атрибутов символов
X_{p0}, X_{p1}, \ldots X_{p_{n_p}}
и значение некоторого атрибута символа
X_{p_j}
.

Грамматика (таблица 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 = {целые числа}.


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