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



         

Проверка на зацикленность - часть 3


Будем добавлять к множествам S(X) новые орграфы при помощи следующей процедуры до тех пор, пока в S(X) не перестанут появляться новые элементы. Выберем целое p; 1
p
m и для каждого j, 1
j
np, выберем орграф D0j
S(Xpj). Затем добавим в S(Xp0) орграф с множеством узлов A(Xpo), обладающий тем свойством, что в нeм дуга от
к
0 идeт тогда и только тогда, когда в орграфе

 D_p[D'_1, \ldots , D'_{n_p}]

(3.5)

существует ориентированный путь из (Xp0;

) в (Xp0;
'): Ясно, что этот процесс рано или поздно закончится и новые орграфы перестанут порождаться, поскольку вообще существует лишь конечное число ориентированных графов. В случае грамматики (таблица 1.1) алгоритм построит следующие множества:


Пусть T - дерево вывода с корнем X, и пусть D'(T) - ориентированный граф с множеством узлов A(X), у которого есть дуга из

в
' тогда и только тогда, когда в D(T) существует ориентированный путь из (X,
) в (X,
'). Покажем, что после окончания работы описанного выше алгоритма для всех X
V S(X) - это множество всех D'(T), где T - дерево вывода с корнем X 1)

. Действительно, построение не добавляет к S(X) новых ориентированных графов, не являющихся D'(T). Алгоритм можно даже легко обобщить так, чтобы для каждого графа из S(X) он печатал на выходе соответствующее дерево вывода T. Обратно, если T - дерево вывода, мы можем показать индукцией по числу узлов дерева T, что D'(T) принадлежит некоторому множеству S(X). В противном случае T должно иметь вид (3.3) и D(T) "составлен" из

 D_pD(T_1), \ldots, D(T_{n_p} )
. По индукции и вследствие того, что при j
j' из D(Tj) в D(Tj' ) не проходит дуг вне Dp, дуги в
 D_pD(T_1), \ldots, D(T_{n_p} )
, составляющей рассматриваемый путь графа D(T), можно заменить соответствующими дугами в
D_p[D'1, \ldots D'_{n_p} ]
, где
D'_j \in S(X_{pj}), 1 \leq j \leq n_p
. Поэтому ориентированный граф, включаемый в S(Xp0) на базе
D_p[D'1, \ldots , D'_{n_p} ]
, просто совпадает с D'(T).

Вышеприведeнный алгоритм решает задачу, поставленную в этом разделе.

Теорема. Семантические правила, добавленные к грамматике так, как это сделано в разд. 2, являются корректными тогда и только тогда, когда ни один из ориентированных графов (3.5) ни при каком выборе p и

D'_1 \in S(X_{p1}), \ldots , D'_{n_p} \in S(X_{n_p} )
не содержит ориентированных циклов.

Доказательство. Если (3.5) содержит ориентированный цикл, то, как было показано выше, некоторый D(T) содержит ориентированный цикл. Наоборот, если T - дерево с наименьшим возможным числом улов, такое, что D(T) содержит ориентированный цикл, то T должно иметь вид (рис. 3.3), а D(T) "составляется" из

D_p; D(T_1), \ldots , D(T_{n_p} )
. Из минимальности T следует, что ориентированный цикл включает по меньшей мере одну дугу графа Dp, и, следовательно, можно, рассуждая, как выше, все дуги, образующие этот цикл и лежащие в одном из графов
D(T_1) , \ldots , D(T_{n_p} )
, заменить дугами графа (3.5).




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