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



             

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


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

D^*_p
обозначим граф Dp[IOX1, ..., IOX n p].

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

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

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


Рис. B.1. 

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

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

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

\begin{align*} &\text{begin Положить $IOx := \{A(X)\}$} \\ &\text{\;для каждого $X \in N$, \{граф без дуг\}}\\ &\text{while имеется правило $p$ с левой частью $X$ такое, что в}\\ &\text{\;\;$D^*_p$ есть путь из $i$ в $s$, $i \in I(X),$}\\ &\text{\;\;$s \in S(X), но в IOx нет дуги из i в s$}\\ &\text{\;do добавить эту дугу в $IOx$}\\ &\text{end end:} \end{align*}

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

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

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


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