Вычислительные последовательности и корректность. Определение визита

Назовем вычислительной последовательностью [4] для дерева вывода t в AG последовательность вида:

cs = (n1, A1)(n2, A2)(n2, A2) ... (nr, Ar);

где

1. nj - внутренняя вершина t (в частности, корень);
2. если nj#nj + 1, то nj + 1 - отец, сын или брат nj ;
3. Aj - либо подмножество синтезируемых атрибутов nj , либо подмножество наследуемых атрибутов (то есть либо либо Aj
   
   S(Xnj )), Aj
   
   S(Xnj));
4. n1 = nr - корень дерева;
5. атрибуты Aj не зависят от Aj для i
   
   j;
6. рассмотрим какую-либо внутреннюю вершину nдерева t. Тогда вычислительную последовательность cs можно записать в следующем виде: cs = u1(n, B1)u2(n, B2) ... (n, Bh)uh+1, где подпоследовательности u1 ... uh+1 не содержат элементов вида (n, A). Тогда
   1. Bj
      
      I(Xn), если j нечетно;
   2. Bj
      
      S(Xn), если j четно,
   3. Uj
      
      [1, n], B = A(Xn) - вычисляются все атрибуты каждого символа X;
   4. Bi
      
      Bj = 0, если i#j - все атрибуты вычисляются по одному разу.
   5. пусть cs = cs1<n, Bj><n1, A1><n2, A2>...<n, Bj+1> cs2, если j нечетно (четно), то nj - вершины поддерева с корнем n (вершины t вне поддерева с корнем n).

Таким образом при входе "вниз" в поддерево вычисляются некоторые наследуемые атрибуты корня поддерева, при возврате из поддерева вычисляются некоторые синтезируемые атрибуты корня поддерева.

Назовем незацикленную атрибутную грамматику корректной, если для всякого еe атрибутированного дерева существует вычислительная последовательность.

Теорема B.4. Незацикленная атрибутная грамматика корректна тогда и только тогда, когда для каждого правила p : X0

X1 ... Xnp если aI(Xi), i[1, np], то имеется в точности одно семантическое правило, сопоставленное p и определяющее значение a(Xi), и если aS(X0), то имеется в точности одно семантическое правило, сопоставленное p и определяющее значение a(X0).

Теорема B.5. Сложность проверки незацикленной атрибутной грамматики на корректность линейна по размеру атрибутной грамматики.

Пусть t - дерево вывода и n - его внутренняя вершина. Рассмотрим вычислительную последовательность для t вида cs = cs1<n, B1>cs2<n, B2>cs3, где n входит в cs1 чeтное число раз, и не входит в cs2. Последовательность cs2 обходит поддерево с корнем n. Будем говорить, что <n, B1>cs2<n, B2> определяет визит в поддерево с корнем n и что вершина n в результате этого визита посещается один раз. Таким образом, если n входит в cs 2h раз, то n посещается h раз.

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

---

---