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

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

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

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий