Теория и реализация языков программирования

         

Чистые многовизитные грамматики


Будем говорить, что атрибутированное дерево 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.

В зависимости от того, какие ограничения будут накладываться на порядок посещения вершин и выбор атрибутов, вычисляемых на том или ином визите, будут получаться те или иные классы атрибутных грамматик.



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