Теория и реализация языков программирования
Одновизитные атрибутные грамматики
Интересный частный случай простых многовизитных грамматик представляют одновизитные грамматики (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.