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



             

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


Начальным состоянием для каждого правила является множество {a<k> j Xk
T}.

План - это последовательность инструкций вида fpa<k> или V ISIT (k, I), где

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

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

A, но
Dpa<k> \subset A
.

Если p : X0

X1 ... Xnp и правило p находится в состоянии A, то результатом k-го поддерева, k
[1, np], будем называть множество {a<k> j a<k>
A, a
S(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 ..


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