Теория и реализация языков программирования
Одновизитные атрибутные грамматики
Интересный частный случай простых многовизитных грамматик представляют одновизитные грамматики (IV)[8].
Графом BG братьев правила p будем называть граф, вершинами которого являются символы правой части правила p : X0
Теорема 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
и будем предполагать, что G - редуцированная КС- грамматика, то есть в ней нет нетерминальных символов, для которых не существует полного дерева вывода, в которое входит этот нетерминал. С каждым символом X
С каждым правилом вывода p
a0(i0) = fpa0(i0)(a1(i1), ... , aj(ij));
где ik
КС-грамматику, каждому символу которой сопоставлено множество атрибутов, а каждому правилу вывода - множество семантических правил, будем называть атрибутной грамматикой (AG).
Назовем атрибут a(X0) синтезируемым, если одному из правил вывода p : X0
Пусть правилу вывода p : X0
