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



             

Определение атрибутных грамматик


Пусть G - КС-грамматика: G = (T, N, P, Z), где T, N, P, Z, соответственно, множество терминальных символов, нетерминальных символов, множество правил вывода и аксиома грамматики. Правила вывода КС- грамматики будем записывать в виде

p : X0

X1 ... Xn (p)

и будем предполагать, что G - редуцированная КС- грамматика, то есть в ней нет нетерминальных символов, для которых не существует полного дерева вывода, в которое входит этот нетерминал. С каждым символом X

N
T свяжем множество A(X) атрибутов символа X. Некоторые из множеств A(x) могут быть пусты. Запись a(X) означает, что a
A(X).

С каждым правилом вывода p

P свяжем множество F семантических правил, имеющих следующую форму:

a0(i0) = fpa0(i0)(a1(i1), ... , aj(ij));

где ik

[0, np] - номер символа правила p, а ak(ik) - атрибут символа Xik, то есть ak(ik)
A(Xik). В таком случае будем говорить, что a0<i0> "зависит" от a1(i1), ... , aj(ij) или что a0(i0) "вычисляется по " a1(i1), ... , aj(ij). В частном случае j может быть равно нулю, тогда будем говорить, что атрибут a0(i0) "получает в качестве значения константу"

КС-грамматику, каждому символу которой сопоставлено множество атрибутов, а каждому правилу вывода - множество семантических правил, будем называть атрибутной грамматикой (AG).

Назовем атрибут a(X0) синтезируемым, если одному из правил вывода p : X0

X1 ... Xnp сопоставлено семантическое правило a(0) = fa(0)(...). Назовем атрибут a(Xi) наследуемым, если одному из правил вывода p : X0
X1 ... Xnp сопоставлено семантическое правило a(i) = fa(i)(...), I
[1, np]. Множество синтезируемых атрибутов символа X обозначим через S(X), наследуемых атрибутов - через I(X).

Пусть правилу вывода p : X0

X1 ... Xnp приписано семантическое правило a0(i0) = fpa0(i0)(a1(i1), ... , aj(ij)). Без снижения общности будем считать, что ak(ik)
I(X0)
npn = 1S(Xn), k
[1, j] то есть атрибут может зависеть только от наследуемых атрибутов символа левой части и синтезируемых атрибутов символов правой части (условие Бошмана). Кроме того, будем считать, что значение атрибутов терминальных символов - константы, то есть их значения определены, но для них нет семантических правил, определеяющих их значения.




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