Дополнительные материалы - Атрибутные грамматики

1. Дополнительные материалы: Атрибутные грамматики

Введение

Среди всех формальных методов описания языков программирования атрибутные грамматики получили, по- видимому, наибольшую известность и распространение. Причиной этого является то, что формализм атрибутных грамматик основывается на дереве разбора программы в КС-грамматике, что сближает его с хорошо разработанной теорией и практикой построения трансляторов. Вместе с тем выяснилось, что реализация вычислителей для атрибутных грамматик общего вида сталкивается с большими трудностями. В связи с этим было сделано множество попыток рассматривать те или иные классы атрибутных грамматик, обладающими "хорошими" свойствами. К числу таких свойств относятся, прежде всего, простота алгоритма проверки атрибутной грамматики на зацикленность и простота алгоритма вычисления атрибутов для атрибутных грамматик данного класса. В предлагаемой статье дается обзор работ, посвященных этим вопросам.

Определение атрибутных грамматик

Пусть G - КС-грамматика: G = (T, N, P, Z), где T, N, P, Z, соответственно, множество терминальных символов, нетерминальных символов, множество правил вывода и аксиома грамматики. Правила вывода КС- грамматики будем записывать в виде

p : X₀X₁ ... X_n (p)

Рекомендуемые материалы

и будем предполагать, что G - редуцированная КС- грамматика, то есть в ней нет нетерминальных символов, для которых не существует полного дерева вывода, в которое входит этот нетерминал. С каждым символом XN T свяжем множество A(X) атрибутов символа X. Некоторые из множеств A(x) могут быть пусты. Запись a(X) означает, что aA(X).

С каждым правилом вывода pP свяжем множество F семантических правил, имеющих следующую форму:

a₀(i₀) = fpa₀(i₀)(a₁(i₁), ... , a_j(i_j));

где i_k[0, n_p] - номер символа правила p, а a_k(i_k) - атрибут символа Xi_k, то есть a_k(i_k)A(Xi_k). В таком случае будем говорить, что a₀<i₀> "зависит" от a₁(i₁), ... , aj(i_j) или что a₀(i₀) "вычисляется по " a₁(i₁), ... , a_j(i_j). В частном случае j может быть равно нулю, тогда будем говорить, что атрибут a₀(i₀) "получает в качестве значения константу"

КС-грамматику, каждому символу которой сопоставлено множество атрибутов, а каждому правилу вывода - множество семантических правил, будем называть атрибутной грамматикой (AG).

Назовем атрибут a(X₀) синтезируемым, если одному из правил вывода p : X₀X₁ ... Xn_p сопоставлено семантическое правило a(0) = fa(0)(...). Назовем атрибут a(X_i) наследуемым, если одному из правил вывода p : X₀X₁ ... Xn_p сопоставлено семантическое правило a(i) = fa(i)(...), I[1, n_p]. Множество синтезируемых атрибутов символа X обозначим через S(X), наследуемых атрибутов - через I(X).

Пусть правилу вывода p : X₀X₁ ... Xn_p приписано семантическое правило a₀(i₀) = fpa₀(i₀)(a₁(i₁), ... , a_j(i_j)). Без снижения общности будем считать, что a_k(i_k)I(X₀) np_n = 1S(X_n), k[1, j] то есть атрибут может зависеть только от наследуемых атрибутов символа левой части и синтезируемых атрибутов символов правой части (условие Бошмана). Кроме того, будем считать, что значение атрибутов терминальных символов - константы, то есть их значения определены, но для них нет семантических правил, определеяющих их значения.

Атрибутированное дерево разбора

Если дана атрибутная грамматика AG и цепочка, принадлежащая языку, определяемому G, то можно построить дерево разбора этой цепочки в грамматике G. В этом дереве каждая вершина помечена символом грамматики G. Припишем теперь каждой вершине множество атрибутов, сопоставленных символу, которым помечена эта вершина. Атрибуты, сопоставленные вхождениям символов в дерево разбора, будем называть вхождениями атрибутов в дерево разбора, а дерево с сопоставленными каждой вершине атрибутами - атрибутированным деревом разбора.

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

Для каждого синтаксического правила pP определим D(p) - граф зависимостей атрибутов символов, входящих в правило p, как ориентированный граф, вершинами которого служат атрибуты символов, входящих в правило p, и в котором идет дуга из вершины b(i) в вершину a(j) тогда и только тогда, когда синтаксическому правилу p сопоставлено семантическое правило

a(j) = fpa(j)(... , b(i), ...), i, j[0, n]:

Граф зависимостей D(t) дерева разбора t цепочки, принадлежащей языку грамматики G, определим как ориентированный граф, полученный объединением графов зависимостей всех примененных в t синтаксических правил.

Незацикленные атрибутные грамматики

Атрибутная грамматика называется незацикленной, если графы зависимостей деревьев всех цепочек, принадлежащих языку, определяемому грамматикой G, не содержат циклов, и зацикленной, если существует хотя бы одна цепочка, принадлежащая языку, для дерева разбора которой граф D(t) содержит ориентированный цикл.

Теорема B.1. Задача определения того, является ли данная атрибутная грамматика зацикленной, имеет экспоненциальную временную сложность, то есть существует константа c > 0 такая, что любой алгоритм, проверяющий на зацикленность произвольную атрибутную грамматику размера n, должен работать более, чем 2cn/log n шагов на бесконечно большом числе грамматик [1, 2].

Кнутом [3] был предложен алгоритм проверки атрибутных грамматик на зацикленность.

Пусть D(p) - граф зависимостей атрибутов правила вывода p, а Gi - произвольный ориентированный граф, вершинами которого служат атрибуты символа Xi правой части правила вывода p. Обозначим ориентированный граф, полученный из D(p) добавлением дуг, идущих из b(i) в a(i), если в графе G_i есть дуга из b в a. Через Γобозначим множество ориентированных графов с вершинами - атрибутами символа X, через - ориентированный граф, вершинами которого служат атрибуты символа X в правиле вывода p : X₀X₁ ... X_np и в котором идет дуга из вершины b в вершину a тогда и только тогда, когда в есть путь из b(0) в a(0).

Алгоритм B.1. (Алгоритм Кнута). Проверка атрибутной грамматики на зацикленность.

Теорема B.2. Атрибутная грамматика AG незациклена тогда и только тогда, когда ни один из графов D_p[G₁ ... Gn_p] не содержит ориентированных циклов, то есть когда алгоритм B.1. заканчивается со значением cycle = false.

Теорема B.3. Алгоритм Кнута проверки на зацикленность атрибутной грамматики размера n требует в общем случае exp(cn²) шагов.

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

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

c_s = (n₁, A₁)(n₂, A₂)(n₂, A₂) ... (n_r, A_r);

где

1. n_j - внутренняя вершина t (в частности, корень);
2. если n_j#n_j + 1, то n_j + 1 - отец, сын или брат n_j ;
3. A_j - либо подмножество синтезируемых атрибутов n_j , либо подмножество наследуемых атрибутов (то есть либо либо A_jS(Xn_j )), A_jS(Xn_j));
4. n₁ = n_r - корень дерева;
5. атрибуты A_j не зависят от A_j для i j;
6. рассмотрим какую-либо внутреннюю вершину nдерева t. Тогда вычислительную последовательность cs можно записать в следующем виде: c_s = u₁(n, B₁)u₂(n, B₂) ... (n, B_h)u_h+1, где подпоследовательности u₁ ... u_h+1 не содержат элементов вида (n, A). Тогда
1. B_j I(X_n), если j нечетно;
2. B_j S(X_n), если j четно,
3. U_j[1, n], B = A(X_n) - вычисляются все атрибуты каждого символа X;
4. B_i B_j = 0, если i#j - все атрибуты вычисляются по одному разу.
5. пусть c_s = c_s1<n, B_j><n₁, A₁><n₂, A₂>...<n, B_j+1> c_s2, если j нечетно (четно), то n_j - вершины поддерева с корнем n (вершины t вне поддерева с корнем n).

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

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

Теорема B.4. Незацикленная атрибутная грамматика корректна тогда и только тогда, когда для каждого правила p : X₀X₁ ... X_np если aI(X_i), i[1, n_p], то имеется в точности одно семантическое правило, сопоставленное p и определяющее значение a(X_i), и если aS(X₀), то имеется в точности одно семантическое правило, сопоставленное p и определяющее значение a(X₀).

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

Пусть t - дерево вывода и n - его внутренняя вершина. Рассмотрим вычислительную последовательность для t вида c_s = c_s1<n, B₁>c_s2<n, B₂>c_s3, где n входит в c_s1 чeтное число раз, и не входит в c_s2. Последовательность c_s2 обходит поддерево с корнем n. Будем говорить, что <n, B₁>c_s2<n, B₂> определяет визит в поддерево с корнем _n и что вершина n в результате этого визита посещается один раз. Таким образом, если n входит в c_s 2h раз, то n посещается h раз.

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

Будем говорить, что атрибутированное дерево k-визитно, если существует вычислительная последовательность c_s для 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);

{X_nij - символ правой части правила pg

.

.

.

визит_в_поддерево (njl, ijl);

вычислить некоторые синтезируемые атрибуты Xn

end;

begin for j := 1 to k do визит_в_поддерево(r, j)

  {r - корень дерева}

end end.

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

Абсолютно незацикленные атрибутные грамматики

Обозначим IOx ориентированный граф, вершинами которого являются атрибуты символа X и из вершины b идет дуга в вершину a тогда и только тогда, когда в атрибутной грамматике AG существует такое поддерево с корнем X, что в графе зависимостей этого поддерева существует путь из b в a. Через обозначим граф D_p[IOX₁, ..., IOX n _p].

Атрибутная грамматика называется абсолютно незацикленной (ANC), если ни один из графов D не содержит ориентированных циклов [6].

Абсолютно незацикленные атрибутные грамматики образуют собственный подкласс незацикленных атрибутных грамматик.

Пример B.1. Незацикленная атрибутная грамматика, не являющаяся абсолютно незацикленной (рис. B.1.).

Рис. B.1.

Эта грамматика порождает всего два слова b и bb. Каждое из двух деревьев порождает незацикленные графы зависимостей, однако грамматика не является абсолютно незацикленной. Происходит это от того, что зависимости, реализуемые в разных деревьях, "накладываются" на один граф IO.

Для построения графов IO имеется простой полиномиальный алгоритм:

Алгоритм B.3. Построение графов IO атрибутной грамматики AG.

Поскольку этот алгоритм полиномиален и задача определения наличия ориентированных циклов в графе также полиномиальна, справедлива следующая теорема:

Теорема B.9. Задача определения, является ли данная атрибутная грамматика абсолютно незацикленной, полиномиальна по длине атрибутной грамматики. Абсолютно незацикленные атрибутные грамматики интересны тем, что для них имеется полиномиальный алгоритм планирования визитов.

Обозначим через A(p) множество атрибутов символов синтаксического правила p. Рассмотрим атрибутированное дерево t в AG и некоторую его внутреннюю вершину n, в которой применено правило вывода p. В каждый момент времени в процессе вычисления атрибутов дерева t каким- либо алгоритмом вычисления какие-то атрибуты из A(p) вычислены, а какие-то нет. Назовем состоянием правила, примененного в дереве вывода, множество вычисленных атрибутов символов, входящих в это правило. Начальным состоянием для каждого правила является множество {a<k> j XkT}.

План - это последовательность инструкций вида fpa<k> или V ISIT (k, I), где , если k - номер символа правой части правила p. I называется входным множеством. План всегда завершается инструкцией - перевести правило p в состояние A. Инструкция fpa<k> вычисляет атрибут a<k>, V ISIT(k, I) осуществляет визит в поддерево k-го символа правой части со значениями наследуемых атрибутов I этого символа, инструкция S изменяет состояние правила.

Обозначим Dpa<k> - множество аргументов семантического правила fpa<k>. Будем говорить, что семантическое правило f готово к вычислению в состоянии A правила p, если a<k> A, но .

Если p : X₀X₁ ... X_np и правило p находится в состоянии A, то результатом k-го поддерева, k[1, n_p], будем называть множество {a<k> j a<k> A, aS(Xk) и для каждого i<j>, для которого есть дуга из i<j> в a<k> в IOXk, i<j>A} (предполагается, что у каждого нетерминала есть хотя бы один синтезируемый атрибут).

Планирование осуществляется нижеследующим алгоритмом. Результат работы алгоритма заносится в двумерный массив EVAL, одним входом в который служит состояние правила, другим - входное множество. Строка - это строка инструкций Stv - вектор состояний правил; он передается как аргумент процедуре PLAN, затем дублируется внутри процедуры PLAN и обращение к PLAN меняет значение своего аргумента в точке вызова (что обозначено знаком var перед параметром Stv процедуры PLAN). Если для некоторого элемента таблицы EVAL в процедуре PLAN начато построение плана, то этот элемент метится значком @, чтобы избежать бесконечной рекурсии. Будем говорить, что функция f готова к вычислению, если все еe аргументы определены, но атрибут, который она вычисляет не определeн.

Алгоритм B.4. Построение планов для каждого возможного состояния каждого правила.

var EVAL : array[состояние, входное множество] of строка;

   St : array [1 .. P] of состояние;

   fP - число синтаксических правил}

   procedure PLAN( p, I, var Stv);

      {p - номер синтаксического правила, I - входное

      множество, Stv - вектор состояния правил}

      var S : строка {строящийся план};

      LStv : array [1 .. p] of состояние;

      {локальный вектор состояния правил}

      A : set of атрибут;{состояние правила p}

      stop: boolean;

   begin

      if (EVAL [Stv[p], I] пуст)

      then

      A := I [ Stv[p], s := пусто , LStv := Stv;

      stop := false, EVAL [Stv[p], I] :='@'

      repeat

         if ( fpa<k> готовая к вычислению)

         then

            s := s || fpa<k>, A := A + a<k>

         else

      if ( поддерево k, результат Y которого не пуст)

      then

         s := s || V ISIT(k, I(X_k)  A), A := AUY ;

         for p_i : X_ku do

         PLAN(p_i, I(X_k)  A, LStv)

         {в этой точке меняется значение LStv[p_i]}

         end

      else stop := true

      end end

      until stop;

      EVAL [Stv[p], I] := s || st(A), Stv := A

      {Stv[p] меняется в точке вызова}

      end end;

   {тело программы} begin for I := 1 to p do

      St[i] := множество атрибутов терминалов правила i;

      PLAN({}, {}, St)

   end end.

Вычисление атрибутов на дереве t заключается в выполнении построенных планов в соответствии с изменениями состояний правил и осуществляется следующей программой:

begin каждое правило дерева t перевести

в начальное состояние,

определяемое множеством атрибутов терминалов;

V ISIT(корень, {})

end.

Простые многовизитные атрибутные грамматики

Атрибутная грамматика называется простой k-визитной, если для каждого нетерминала XV существует разбиение A1(X), ... , Am(X) множества атрибутов A(X), где m[1, k] и m может зависеть от X, то есть m = m(X), такое, что для любого дерева вывода t слова из G существует вычислительная последовательность, при которой для любого вхождения X в t все атрибуты Aj(X) вычисляются при выполнении j-го визита в поддерево c корнем X для всех j[1;m(X)] [7].

Атрибутная грамматика называется простой многовизитной (SMV ), если она является простой k-визитной для какого-нибудь k.

Существуют абсолютно незацикленные атрибутные грамматики, не являющиеся простыми многовизитными.

Пример B.2. Здесь атрибуты a и b символа A левого поддерева вычисляются на первом визите, а x и y - на втором. Для символа A правого поддерева наоборот - атрибуты x и y вычисляются на первом визите, a и b - на втором ( рис. B.2).

Рис. B.2.

Теорема B.10. Всякая простая k-визитная грамматика является абсолютно незацикленной [7].

Теорема B.11. Задача определения того, является ли произвольная атрибутная грамматика простой многовизитной, NP-полна [7]. Мало того, NP-полна даже задача определения простой 2-визитности [7] Если для каждого символа дано разбиение его атрибутов по визитам, то алгоритм вычисления атрибутов дерева принимает следующий вид:.

Алгоритм B.5. Вычисление атрибутов в простой многовизитной грамматике.

procedure визит_в_поддерево(n, i);

begin вычислить наследуемые атрибуты I(X_n);

 визит_в_поддерево (nj1, ij1);

 ...

 визит_в_поддерево (njm, ijm);

 вычислить синтезируемые атрибуты S(X_n)

end;

beginforj := 1tok(Xr)do

 визит_в_поддерево (r, j){r - корень}

end:

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

Интересный частный случай простых многовизитных грамматик представляют одновизитные грамматики (IV)[8].

Графом BG братьев правила p будем называть граф, вершинами которого являются символы правой части правила p : X₀X₁ ... X_np и из 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.

Многопроходные грамматики

Пусть на последовательность визитов наложено такое ограничение, чтобы они образовали последовательные обходы дерева разбора либо сверху-вниз слева-направо, либо сверху- вниз справа-налево.

Атрибутная грамматика называется чистой k- проходной в обоих направлениях, если существует такая последовательность из k обходов <d1 ... dl> (каждое di - либо справа-налево, либо слева-направо), что атрибуты любого дерева вывода могут быть вычислены в результате выполнения этой последовательности обходов [5].

Атрибутная грамматика называется чистой многопроходной в обоих направлениях (PBD), если она является чистой k-проходной в обоих направлениях для какого-нибудь k.

Пример B.3. Существуют атрибутные грамматики, не являющимися чистыми многопроходными ни для какого k ( рис. B.3).

Рис. B.3.

Число необходимых проходов в этом примере зависит от глубины дерева и может быть сколь угодно большим.

Очевидно, что грамматика примера рис. B.1 не является чистой многопроходной и нетрудно видеть, что грамматика примера рис. B.1 является абсолютно незацикленной.

Теорема B.14. Задача определения того, является ли произвольная атрибутная грамматика чистой многопроходной в обоих направлениях, зависит экспоненцально от размера атрибутной грамматики.

Атрибутная грамматика называется чистой k-проходной слева-направо, если атрибуты любого дерева вывода в ней могут быть вычислены за k обходов дерева вывода слева- направо [2, 5].

Атрибутная грамматика называется чистой многопроходной слева-направо (PLR), если она является чистой k-проходной слева-направо для какого-нибудь k.

Теорема B.15. Задача определения того, является ли произвольная атрибутная грамматика чистой многопроходной слева-направо, зависит экспоненциально от размера атрибутной грамматики.

Пример B.4. Существуют атрибутные грамматики, вычисляющиеся в обоих направлениях, но не вычисляющиеся в одном ( рис. B.4).

Рис. B.4.

Атрибутная грамматика называется простой k- проходной в обоих направлениях, если существует такая последовательность обходов и такое разбиение атрибутов A1(X), ... , Am(X), m = m(X), m[1, k], каждого символа, что все атрибуты из множества Ai(X) вычисляются на i-ом проходе дерева [5].

Атрибутная грамматика называется простой многопроходной в обоих направлениях (SBD), если она является простой k-проходной в обоих направлениях для какого-нибудь k.

Грамматика примера 9.2 является простой многопроходной в обоих направлениях, но не является чистой многопроходной слева-направо. Грамматика примера 9.3 является чистой многопроходной слева-направо, но не является простой многопроходной в обоих направлениях. Так что между классами PLR и SBD нет отношения включения.

Теорема B.16. Задача проверки того, является ли произвольная атрибутная грамматика простой k- проходной в обоих направлениях, полиномиально сложна [5].

Пример B.5. Существуют грамматики, являющиеся чистыми многопроходными, но не являющиеся простыми многопроходными ( рис. B.5).

Рис. B.5.

Атрибутная грамматика называется простой k-проходной слева-направо, если существует такое разбиение атрибутов каждого символа A1(X), ..., Am(X), m = m(X), m[1, k]; что все атрибуты из множества Ai(X) вычисляются на i-ом обходе дерева слева-направо сверху-вниз.

Атрибутная грамматика называется простой многопроходной слева-направо (SLR), если она является простой k-проходной слева-направо для какого-нибудь k.

Пример B.6. Эта грамматика является простой однопроходной справа-налево, но не является простой однопроходной слева-направо ( рис. B.6).

Рис. B.6.

Будем говорить, что между атрибутами a и b имеет место отношение prec, если существует правило вывода p : X₀X₁ ... X_np с вхождениями атрибутов a<j> и b<k> такое, что a<j> используется в качестве аргумента при вычислении вхождения b<k>.

Между атрибутами a и b имеет место отношение L, если aprecb и для каждого правила вывода p : X₀X₁ ... X_np с вхождениями атрибутов a<j> и b<k> такими, что b<k> зависит от a<j>, имеет место j<k.

Графом LR-предшествования для AG назовем граф, вершинами которого являются атрибуты всех символов AG и из вершины a в вершину b идет дуга, тогда и только тогда, когда имеет место отношение aprecb. Если имеет место отношение aLb, то дуга (a, b) помечена меткой L, иначе она помечена меткой L. Приведем алгоритм проверки принадлежности классу SLR, который одновременно производит разбиение (если это возможно) атрибутов каждого символа по обходам.

Алгоритм B.7.

* Построение функции проходов pass(a) атрибутов

символов,

* дающей либо минимальный номер прохода, на котором

атрибут

* может быть вычислен, либо неопределено,

* если атрибут не может быть занесен ни в

* один из элементов разбиения A(X), aA(X).

begin строим граф LR предшествования для AG;

Полагаем COST(a) неопредел_нной для всех вершин a;

m := -1, repeat m := m + 1;

Положить COST(a) равной m для всех вершин,

  для которых COST(a) неопределено;

repeat для вершины a такой, что COST(a) = m

  положить COST(a) неопредел_нным;

Если существует вершина b и дуга (b, a) такие, что

  (COST(b) = m) and (B, a) имеет метку L)

  or (COST(b) неопределено)

  until нельзя найти такой вершины a,

    что COST(a) можно сделать неопредел_нным;

  until либо для всех a COST(a) вычислена,

  либо не существует вершины b такой,

    что COST(b) = m, для всех aA

  if (COST(a) определено)

    then pass(a) := COST(a) + 1

    else pass(a) := неопределено

  end

end.

Этот алгоритм легко обобщается на простые многопроходные в обоих направлениях атрибутные грамматики [5].

Совсем простым частным случаем LR многопроходных атрибутных грамматик являются однопроходные атрибутные грамматики.

Теорема B.17. Атрибутная грамматика является LR однопроходной тогда и только тогда, когда ни один из графов братьев для правил вывода не содержит дуг из X в X для i j.

Вам также может быть полезна лекция "9 - Систематическая картотека статей".

Таким образом между рассмотренными классами атрибутных грамматик имеет место включение, показанное на рис. B.7:

Рис. B.7.