Теория и реализация языков программирования
Чистые многовизитные грамматики
Будем говорить, что атрибутированное дерево k-визитно, если существует вычислительная последовательность cs для t такая, что никакая вершина n из t не посещается более k раз.
Атрибутная грамматика называется чистой k-визитной (PMV ), если каждое атрибутированное дерево вывода t в AG k-визитно [5, 7].
Теорема B.6. Для всякой корректной атрибутной грамматики существует k такое, что грамматика является чистой k-визитной.
На самом деле это k не превосходит максимального по всем символам грамматики числа синтезируемых или наследуемых атрибутов.
Следствием этого являются две следующие теоремы.
Теорема B.7. Сложность задачи определения того, является ли произвольная атрибутная грамматика чистой k-визитной для какого-нибудь k > 0, экспоненциальна.
Эта задача просто совпадает с задачей определения корректности атрибутной грамматики.
Теорема B.8. Сложность задачи определения того, является ли произвольная атрибутная грамматика чистой k-визитной для фиксированного k также экспоненциальна.
Атрибуты всякого дерева t чистой k-визитной атрибутной грамматики можно вычислить с помощью следующего алгоритма:
Алгоритм B.2. Вычисление атрибутов чистой k- визитной атрибутной грамматики
procedure визит_в_поддерево (n, i); {n - корень поддерева; i - номер визита в это поддерево} {Предполагается, что в вершине n применено правило вывода p} begin вычислить некоторые наследуемые атрибуты Xn; {эти атрибуты определяются <nj1, A> для начала i-го визита в соответствующей вычислительной последовательности} визит_в_поддерево (n, i); {Xnij - символ правой части правила pg . . . визит_в_поддерево (njl, ijl); вычислить некоторые синтезируемые атрибуты Xn end; begin for j := 1 to k do визит_в_поддерево(r, j) {r - корень дерева} end end.
В зависимости от того, какие ограничения будут накладываться на порядок посещения вершин и выбор атрибутов, вычисляемых на том или ином визите, будут получаться те или иные классы атрибутных грамматик.
