Теория языков программирования методов трансляции (стр. 34 )

Рис. 11.31. TRANS(Ij, sj).

4)  (а) GEN(ℬ, s) = GEN(ℬ), если s - последний оператор в ℬ.

(б) GEN(I, s) - множество таких операторов d Î P, что существует путь без циклов I1, I2,…, Ik, состоящих исключительно из вершин в I, и такая последовательность выходов s1, s2, …, sk для I1, I2,…, Ik, соответственно, что

(i)  d Î GEN(I, s),

(ii)  в F0 участок sj является прямым предком входа для Ij+1 при 1 £ j < k,

(iii)  d Î TRANS(Ij, sj) при 2 £ j £ k,

(iv)  sk = s.

Таким образом, TRANS(I, sj) – это множество определений, которое можно передать с входа I на выход s без переопределения в I. GEN(I, s) – это множество определений I, которые без переопределений могут достичь s.

Пример. Рассмотрим F0 на рис 11.29 и F1 и F2 на рис. 11.30. В F1 интервал I2 это {ℬ2, ℬ3, ℬ4}, и он имеет выход S9. Таким образом, IN(I2) = IN(ℬ2) = {S1, S2, S3, S8} и OUT(I2, s) = OUT(ℬ2) = {S3, S8}.

TRANS(I2, S9) = Æ.

GEN(I2, S9) содержит S8, поскольку существует последовательность участков, состоящая только из ℬ2, в которой S8 Î GEN(ℬ3, S9). Кроме того, S3 Î GEN(I2, S9) , поскольку существует последовательность участков ℬ2, ℬ3 с выходом на S5 и S9. Это означает, что S3 Î GEN(ℬ2, S5), ℬ2 – прямой предок участка ℬ3, S3 Î GEN(ℬ3, S9).

На основании этих определений дадим алгоритм вычисления IN(ℬ) для всех участков программы P. Он обрабатывает программы только со сводимыми графами управления.

Алгоритм вычисления функции IN.

Вход. Сводимый граф F0 для программы P.

Выход. IN(ℬ) для каждого участка ℬ Î P.

Метод.

1)  Пусть F0, F1,…, Fk - производная последовательность от F0. Вычислим TRANS(ℬ) и GEN(ℬ) для всех участков ℬ из F0.

2)  Для i = 1, 2, …, k последовательно вычисляем TRANS(I, s) и GEN(I, s) для всех интервалов порядка i и выходов s для I. Рекурсивное определение этих функций гарантирует, что это можно сделать.

3)  Полагаем IN(I) = Æ, где I – одиночный интервал порядка k. Устанавливаем i=k.

4)  Для всех интервалов порядка i выполняем следующее. Пусть I = {I1, …, In} – интервал порядка i (I1, …, In – интервалы порядка i-1 или участки, если i=1). Можно считать, что эти интервалы перечислены в том порядке, в котором из них составлен интервал I в алгоритме определения непересекающихся интервалов. Иными словами, I1 – это заголовок и для каждого j > 1 множество {I1, …, Ij-1} содержит все вершины из Fi-1, являющиеся прямыми предками интервала Ij.

(а) Пусть s1, s2, …, sr – выходы интервала I, каждый из которых принадлежит участку в F0, являющемуся прямым предком входа для I. Полагаем

IN(I1) = IN(I) È GEN(I, si)

(б) Для всех s Î I1 полагаем

OUT(I1, s) = (IN(I1) Ç TRANS(I1, s) È GEN(I, s))

(в) Для j=2, 3, …, n пусть sr1, sr2, …, srkr – выходы интервала Ir, 1 £ r < j, каждый из которых принадлежит участку в F0, являющемуся прямым предком для входа Ir. Полагаем

IN(Ij) = OUT(Ir, srl)

OUT(Ij, s) = (IN(Ij) Ç TRANS(Ij, s)) È GEN(Ij, s)

для всех интервалов, входящих в Ij.

5)  Если i = 1 остановиться. В противном случае уменьшить i на 1 и вернуться к шагу 4).

Пример. Применим данный алгоритм к графу управления на рис. 11.29. Для четырех участков в F0 GEN и TRANS вычисляются просто. Результаты приведены в табл. 11.6.

Таблица 11.6.

Участок	GEN	TRANS
ℬ1 ℬ2 ℬ3 ℬ4	{S1, S2} {S3, S4} {S8} Æ	Æ Æ {S2, S3} {S1, S2, S3, S4, S8}

Поскольку ℬ3 определяет только переменную I ℬ3 «убивает» предыдущие ее определения, но передает определение переменной J, а именно S2 и S3. Поскольку никакой из участков не определяет переменную дважды, все операторы внутри участка принадлежат множеству GEN для данного участка.

Интервал I1, состоящий из одного участка ℬ1, имеет один выход – оператор S2. Так как пути в I1 тривиальны, то GEN(I1, S2) = {S1, S2} и TRANS(I1, S2) = Æ.

Интервал I2 имеет один выход S9. GEN(I2, S9) = {S3, S8} и TRANS(I2, S9) = Æ.

Теперь можно начать вычисление функции IN. Первоначально IN(I3) = Æ. Затем к двум подынтервалам в I3 можно применить шаг 4) алгоритма. Это можно сделать только в порядке I1, I2. На шаге 4а) вычисляем IN(I1) = IN(I3) = Æ, на шаге 4в) –

OUT(I1, S2) = (IN(I1) Ç TRANS(I1, S2)) È GEN(I1, S2) = {S1, S2}.

Далее, на шаге 4в)

IN(I2) = OUT(I1, S2) = {S1, S2}.

Проходя по интервалам порядка 1, мы должны рассмотреть составляющие для I1 и I2. Интервал I2 состоит из участков ℬ2, ℬ3 и ℬ4, которые в таком порядке и можно рассматривать. На шаге 4а)

IN(ℬ2) = IN(I2) È GEN(I1, S9) = {S1, S2, S3, S8}.

На шаге 4б)

OUT(ℬ2, S5) = IN(ℬ2) Ç TRANS(ℬ2, S5)) È GEN(ℬ2, S5) = {S3, S4}.

Поскольку S5 ведет к ℬ3, находим

IN(ℬ3) = OUT(ℬ2, S5) = {S3, S4},

а так как S5 ведет к ℬ4, то

IN(ℬ4) = OUT(ℬ2, S5) = {S3, S4}.

И так,

IN(ℬ1) = Æ

IN(ℬ2) = {S1, S2, S3, S8}.

IN(ℬ3) = {S3, S4}

IN(ℬ4) = {S3, S4}.

Индукцией по порядку интервалов можно доказать, что

1)  TRANS(I, s) – множество таких операторов определений d Î P, что существует путь из первого оператора заголовка для I вплоть до s, вдоль которого ни один из операторов не переопределяет переменную, определенную в d,

2)  GEN(I, s) - множество таких операторов определений d, что существует путь из d в s, вдоль которого ни один из операторов не переопределяет переменную, определенную в d.

Индукцией по числу переменных шага 4) можно показать, что

если для вычисления IN(Ij) применяется шаг 4), то IN(Ij) – множество таких определений d, что существует путь из d во вход Ij, вдоль которого ни один из операторов не переопределяет переменную, определенную в d, а OUT(Ij, s) – множество таких d в s, вдоль которого ни один из операторов не переопределяет переменную, определенную в d.

Заключительная теорема. Для всех линейных участков ℬ Î P множество IN(ℬ) – это множество определений d, что в F0 существует путь из d в первый оператор участка ℬ, вдоль которого ни один из операторов не переопределяет переменную, определенную в d.

6.4.3.  Несводимые графы управления

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

Пример. Рассмотрим несводимый граф управления на рис. 11.28. Вершину n3 можно расщепить на две копии n3¢ и n3², получив граф F¢, изображенный на рис. 11.32.

Рис. 11.32. Расщепленный граф управления.

Рис. 11.33. Первый производный граф

Интервалы для графа F¢ будут