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


         

новые орграфы при помощи следующей


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



(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) "составлен" из
. По индукции и вследствие того, что при j
j' из D(Tj) в D(Tj' ) не проходит дуг вне Dp, дуги в
, составляющей рассматриваемый путь графа D(T), можно заменить соответствующими дугами в
, где
. Поэтому ориентированный граф, включаемый в S(Xp0) на базе
, просто совпадает с D'(T).

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

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

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


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