Решение (домашние задания)
Описание файла
Файл "Решение" внутри архива находится в следующих папках: домашние задания, Домашние задания (avasite), домашнее задание 1. Текстовый-файл из архива "домашние задания", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр текстового-файла онлайн
Блок 1
01 L1: - НББ
02 t1 < +, l, r
03 m < /, t1, 2
04 t2 < *, 4, m
05 t3 < a[t2]
06 ifTrue t3 == v
07 goto L2
08 else
09 goto L3
Блок 2
10 L2: - НББ
11 t4 < m;
12 return t4;
Блок 3
13 L3: - НББ
14 t5 < *, 4, m
15 t6 < +, a, t5
16 t7 < a[t6]
17 ifTrue t7 > v
18 goto L4
19 else
20 goto L5
Блок 4
21 L4: - НББ
22 r < -, m, l
Блок 5
23 L5: - НББ
24 l < +, m, 1
Блок 6
25 L6: - НББ
26 ifTrue r >= l
27 goto L1
28 else
29 goto L7
Блок 7
30 L7: - НББ
31 t4 < -1
32 return t4
граф потока управления можно посмотреть в файле graph.png построенному при помощи graphviz по файлу graph.txt
команды return xxx; не были обработаны никаким специальным образом. (не нашёл примера в слайдах для специальной обработки, но нашёл фразу о том, что после окончания блока - мы автоматически переходим в следующий за ним блок, так и было сделано)
//====================================== ======================================== ======================================== ====
//====================================== ======================================== ======================================== ====
//====================================== ======================================== ======================================== ====
Применим теперь алгоритм "Достигающие определения", чтобы вычислить Input и Output для каждого блока:
//====================================== ======================================== ======================================== ====
Вычислим Input для каждого блока
для начала вычислим kill и gen для каждого блока:
(t1, t2, t3, t4, t5, t6, t7, l, r, m, v, a)
Bx (gen) (kill)
B1 (2, 3, 4, 5) ()
B2 (11) (31)
B3 (14, 15, 16) ()
B4 (22) ()
B5 (24) ()
B6 () ()
B7 (31) (11)
По итерационному методу будет вчислять Input и Output
Out Bx 0 = (пусто) (0 - тут номер итерации)
In Bx 0 = ()
ниже - 1-я итерация ниже - 2-я итерация ниже должна быть 3-я итерация, но она полностью совпадает со 2-й, а значит итерационный процесс - остановился
In B1 1 = Out Entry + Out B6 0 = () = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
Out B1 1 = genB1 + (In B1 1 - killB1) = (2, 3, 4, 5) + In B1 1 = (2, 3, 4, 5) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
In B2 1 = Out B1 1 = (2, 3, 4, 5) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
Out B2 2 = genB2 + (In B2 1 - killB2) = (11) + (In B2 1 - (31)) = (2, 3, 4, 5, 11) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
In B3 1 = Out B1 1 + Out B2 1 = (2, 3, 4, 5, 11) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
Out B3 1 = genB3 + (In B3 1 - killB3) = (14, 15, 16) + In B3 1 = (2, 3, 4, 5, 11, 14, 15, 16) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
In B4 1 = Out B3 1 = (2, 3, 4, 5, 11, 14, 15, 16) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
Out B4 1 = genB4 + (In B4 1 - killB4) = (22) + In B4 1 = (2, 3, 4, 5, 11, 14, 15, 16, 22) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
In B5 1 = Out B3 1 + Out B4 1 = (2, 3, 4, 5, 11, 14, 15, 16, 22) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
Out B5 1 = genB5 + (In B5 1 - killB5) = (24) + In B5 1 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
In B6 1 = Out B5 1 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
Out B6 1 = genB6 + (In B6 1 - killB6) = In B6 1 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
In B7 1 = Out B6 1 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24) = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
Out B7 1 = genB7 + (In B7 1 - killB7) = (31) + (In B7 1 - (11)) = (2, 3, 4, 5, 14, 15, 16, 22, 24, 31) = (2, 3, 4, 5, 14, 15, 16, 22, 24, 31)
Input B1 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
Input B2 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
Input B3 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
Input B4 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
Input B5 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
Input B6 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
Input B7 = (2, 3, 4, 5, 11, 14, 15, 16, 22, 24)
//====================================== ======================================== ======================================== ====
Вычислим Output для каждого блока
для начала вычислим def и use для каждого блока:
Bx use def
B1 (22, 24) (2, 3, 4, 5)
B2 (3) (11)
B3 (3) (14, 15, 16)
B4 (3, 24) (22)
B5 (3) (24)
B6 (22, 24) ()
B7 () (31)
In exit 0 = ()
ниже 1-я итер. ниже 2-я итер. ниже 3-я итер., но она совпадает со 2-й, а значит процесс останавливается
Out B7 = In exit = ()
In B7 = useB7 + (Out B7 - defB7) = Out B7 - 31 = ()
Out B6 = In B1 + In B7 = () = (3, 22, 24)
In B6 = useB6 + (Out B6 - defB6) = (22, 24) + Out B6 = (22, 24) = (3, 22, 24)
Out B5 = In B6 = (22, 24) = (3, 22, 24)
In B5 = useB5 + (Out B5 - defB5) = (3) + (Out B5 - (24)) = (3, 22) = (3, 22)
Out B4 = In B5 = (3, 22) = (3, 22)
In B4 = useB4 + (Out B4 - defB4) = (3, 24) + (Out B4 - (22)) = (3, 24) = (3, 24)
Out B3 = In B4 + In B5 = (3, 22, 24) = (3, 22, 24)
In B3 = useB3 + (Out B3 - defB3) = (3) + (out B3 - (14, 15, 16)) = (3, 22, 24) = (3, 22, 24)
Out B2 = In B3 = (3, 22, 24) = (3, 22, 24)
In B2 = useB2 + (Out B2 - defB2) = (3) + (Out B2 - (11)) = (3, 22, 24) = (3, 22, 24)
Out B1 = In B2 + In B3 = (3, 22, 24) = (3, 22, 24)
In B1 = useB1 + (Out B1 - defB1) = (22, 24) + (Out B1 - (2,3,4,5)) = (3, 22, 24) = (3, 22, 24)
Output B1 = (3, 22, 24)
Output B2 = (3, 22, 24)
Output B3 = (3, 22, 24)
Output B4 = (3, 22)
Output B5 = (3, 22, 24)
Output B6 = (3, 22, 24)
Output B7 = ()
//====================================== ======================================== ======================================== ====
Тут ниже ошибка была, переделано и написано выше
//====================================== ======================================== ======================================== ====
Вычислим Output для каждого блока
для начала вычислим def и use для каждого блока:
Bx use def
B1 (22, 24) (т.к. l, r, a, v - используются в блоке до того, как они определены в этом блоке и их можно достигнуть следуя в графе против шерсти) (2, 5, 6) (потому что это там где используются неопределённые переменные)
B2 (3) (m) (11)