Одновизитные атрибутные грамматики

Интересный частный случай простых многовизитных грамматик представляют одновизитные грамматики (IV)[8].

Графом BG братьев правила p будем называть граф, вершинами которого являются символы правой части правила p : X0

X1 ... Xnp и из Xi в Xj идет дуга тогда и только тогда, когда какие-либо элементы I(Xj) зависят от каких-либо элементов S(Xi), i, j

[1, n]

Теорема B.12. Атрибутная грамматика является одновизитной тогда и только тогда, когда ни один из графов братьев BGp не содержит ориентированных циклов [9].

Из этой теоремы непосредственно следует

Теорема B.13. Задача определения того, является ли произвольная атрибутная грамматика одновизитной, полиномиальна.

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

Алгоритм B.6. Вычисление атрибутов в одновизитной грамматике.

procedure визит_в_поддерево (n); begin вычислить наследуемые атрибуты I(X); в соответствии с линейным порядком символов правой части правила do визит_в_поддерево (n); вычислить синтезируемые атрибуты S(X) end; begin визит_в_поддерево(r) {r - корень} end.

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

p : X0

X1 ... Xn (p)

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

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] то есть атрибут может зависеть только от наследуемых атрибутов символа левой части и синтезируемых атрибутов символов правой части (условие Бошмана). Кроме того, будем считать, что значение атрибутов терминальных символов - константы, то есть их значения определены, но для них нет семантических правил, определеяющих их значения.

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