CC_task2_Shcherbinina_424 (Практикум 2)
Описание файла
Файл "CC_task2_Shcherbinina_424" внутри архива находится в следующих папках: Практикум 2, отчеты. PDF-файл из архива "Практикум 2", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
В связи с тем, что после return i (37 строка)происходит выход из процедуры, i ← +, i, 1(38строка), выделим в блок X (B13), в который мыникогда не попадем.Блок A (B1)(1) i ← 0(2) j ← 0(3) k ← -1(4) p ← 0Блок B (B2)(5) L7:(6) ifFalse i < n goto L1Блок C (B3)(7) goto L2Блок D (B8)(21) L3:(22) ifFalse i > k goto L4Блок E (B9)(23) k ← i(24) goto L5Блок F (B11)(31) L4:(32) p ← + p, 1(33) p ← + p, nБлок G (B10)(25) L5:(26) k ← 5(27) t1 ← *, i, 4(28) t2 ← s[t1](29) t3 ← + t2, 1(30) s[t1] ← t3Блок H (B4)(8) L2:(9) t4 ← *, i, 4(10) t5 ← s[t4](11) t6 ← *, n, 4(12) t7 ← s[t6](13) ifTrue t5 < t7 goto L3;Блок I (B5)(14) ifFalse i <= k goto L6Блок J (B7)(17) print j(18) t4 ← *, k, 2(19) i ← +, t4, 1(20) goto L1Блок K (B6)(15) L6:(16) goto L7Блок L (B12)(34) L1:(35) return iБлок X (B13)(36) i ←+, i, 1B1B2B3B4B5B6B7B8B9B10B11B12B13gen1, 2, 3, 49, 10, 11, 1218, 192326, 27, 28, 29, 303336kill19, 23, 26, 33, 36181, 9, 363, 263, 2341, 19По итерационному методу будем вычислять Input и Output.
Out Bx 0 = (); In Bx 0 = ()1я итерация2я итерация3я итерацияIn B1 1 = Out EntryOut B1 1 = genB1 + (In B1 1 - killB1)= ()= (1,2,3,4)= ()= (1,2,3,4)= ()= (1,2,3,4)In B2 1 = Out B1 1 + Out B6 0Out B2 1 = genB2 + (In B2 1 - killB2)= (1,2,3,4)= (1,2,3,4)= (1,2,3,4,9,10,11,12)= (1,2,3,4,9,10,11,12)= (1,2,3,4,9,10,11,12,26,27,28,29,30)= (1,2,3,4,9,10,11,12,26,27,28,29,30)In B3 1 = Out B2 1Out B3 1 = genB3 + (In B3 1 - killB3)= (1,2,3,4)= (1,2,3,4)= (1,2,3,4,9,10,11,12)= (1,2,3,4,9,10,11,12)= (1,2,3,4,9,10,11,12,26,27,28,29,30)= (1,2,3,4,9,10,11,12,26,27,28,29,30)In B4 1 = Out B3 1 + Out B10 0Out B4 1 = genB4 + (In B4 1 - killB4)= (1,2,3,4)= (1,2,3,4,9,10,11,12)= (1,2,3,4,9,10,11,12,26,27,28,29,30)= (1,2,3,4,9,10,11,12,26,27,28,29,30)= (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)= (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)In B5 1 = Out B4 1Out B5 1 = genB5 + (In B5 1 - killB5)= (1,2,3,4,9,10,11,12)= (1,2,3,4,9,10,11,12)= (1,2,3,4,9,10,11,12,26,27,28,29,30)= (1,2,3,4,9,10,11,12,26,27,28,29,30)= (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)= (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)In B6 1 = Out B5 1Out B6 1 = genB6 + (In B6 1 - killB6)= (1,2,3,4,9,10,11,12)= (1,2,3,4,9,10,11,12)= (1,2,3,4,9,10,11,12,26,27,28,29,30)= (1,2,3,4,9,10,11,12,26,27,28,29,30)= (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)= (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)In B7 1 = Out B5 1Out B7 1 = genB7 + (In B7 1 - killB7)= (1,2,3,4,9,10,11,12)= (2,3,4,10,11,12,18,19)= (1,2,3,4,9,10,11,12,26,27,28,29,30) = (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)= (2,3,4,10,11,12,18,19,26,27,28,29,30) = (2,3,4,10,11,12,26,27,28,29,30,32,33)In B8 1 = Out B4 1Out B8 1 = genB8 + (In B8 1 - killB8)= (1,2,3,4,9,10,11,12)= (1,2,3,4,9,10,11,12)= (1,2,3,4,9,10,11,12,26,27,28,29,30)= (1,2,3,4,9,10,11,12,26,27,28,29,30)= (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)= (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)In B9 1 = Out B8 1Out B9 1 = genB9 + (In B9 1 - kill B9)= (1,2,3,4,9,10,11,12)= (1,2,4,9,10,11,12,23)= (1,2,3,4,9,10,11,12,26,27,28,29,30)= (1,2,4,9,10,11,12,23,27,28,29,30)=(1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)= (1,2,4,9,10,11,12,23,27,28,29,30,32,33)In B10 1 = Out B9 1 + Out B11 0= (1,2,4,9,10,11,12,23)= (1,2,3,4,9,10,11,12,23,27,28,29,30,32,33) = (1,2,4,9,10,11,12,23,27,28,29,30,32,33)Out B10 1 =genB10+(In B10 1 -kill B10) = (1,2,4,9,10,11,12,26,27,28,29,30) = (1,2,4,9,10,11,12,26,27,28,29,30,32,33) = (1,2,4,9,10,11,12,26,27,28,29,30,32,33)In B11 1 = Out B8 1= (1,2,3,4,9,10,11,12)Out B11 1 = genB11 + (In B11 1 - kill B11)= (1,2,3,9,10,11,12,32,33)= (1,2,3,4,9,10,11,12,26,27,28,29,30) = (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)= (1,2,3,9,10,11,12,26,27,28,29,30,32,33)= (1,2,3,9,10,11,12,26,27,28,29,30,32,33)In B12 1 = Out B2 1 + Out B7 1= (1,2,3,4,10,11,12,18,19)Out B12 1 = genB12 + (In B12 1 - kill B12) = (1,2,3,4,10,11,12,18,19)= (1,2,3,4,9,10,11,12,18,19,26,27,28,29,30) =(1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)= (1,2,3,4,9,10,11,12,18,19,26,27,28,29,30) =(1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)In B13 1Out B13 1= ()= (36)= ()= (36)= ()= (36)Изменения в 4й итерацииIn B2 = (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)Out B2 = -//In B3 = (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)Out B3 = -//-5я итерация совпадает с 4й итерацией => итерационный процесс остановился =>Input B1 = ()Input B2 = (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)Input B3 = (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)Input B4 = (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)Input B5 = (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)Input B6 = (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)Input B7 = (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)Input B8 = (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)Input B9 = (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)Input B10 = (1,2,4,9,10,11,12,23,27,28,29,30,32,33)Input B11 = (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)Input B12 = (1,2,3,4,9,10,11,12,26,27,28,29,30,32,33)Input B13 = ()Вычислим Output для каждого блока.
Для начала вычислим def и use для каждого блока:defuseIn Exit = (), In Bi 0 = ()B11,2,3,4B21B3B49,10,11,121B51,3,26B6B718,192,3,26B81,3,26B9231B1026,27,28,29,301B11324,33B121,19B1336-1я итерация2я итерация3я итерация4я итерация5я итерацияOut B13 = In ExitIn B13 = useB13 + (Out B13 - defB13)= ()= ()= ()= ()= ()= ()= ()= ()= ()= ()Out B12 = In ExitIn B12 = useB12 + (Out B12 - defB12)= ()= (1,19)= ()= (1,19)= ()= (1,19)= ()= (1,19)= ()= (1,19)Out B11 = In B10In B11 = useB11 + (Out B11 - defB11)= ()= (4,33)= (1)= (1,4,33)= (1,2,3,4,33)= (1,2,3,4,33)= (1,2,3,4,19,33)= (1,2,3,4,19,33)= (1,2,3,4,19,33)= (1,2,3,4,19,33)Out B10 = In B4In B10 = useB10 + (Out B10 - defB10)= ()= (1)= (1,2,3,4,26,33)= (1,2,3,4,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,33)-//-//-Out B9 = In B10In B9 = useB9 + (Out B9 - defB9)= (1)= (1)= (1,2,3,4,33)= (1,2,3,4,33)= (1,2,3,4,19,33)= (1,2,3,4,19,33)= (1,2,3,4,19,33)= (1,2,3,4,19,33)-//-//-Out B8 = In B9 + In B11In B8 = useB8 + (Out B8 - defB8)= (1,4,33)= (1,3,4,26,33)= (1,2,3,4,33)= (1,2,3,4,26,33)= (1,2,3,4,19,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,33)= (1,2,3,4,19,26,33)-//-//-Out B7 = In B12In B7 = useB7 + (Out B7 - defB7)= (1,19)= (1,2,3,26)= (1,19)= (1,2,3,26)= (1,19)= (1,2,3,26)= (1,19)= (1,2,3,26)-//-//-Out B6 = In B2In B6 = useB6 + (Out B6 - defB6)= ()= ()= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)-//-//-Out B5 = In B6 + In B7In B5 = useB5 + (Out B5 - defB5)= (1,2,3,26)= (1,2,3,26)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)-//-//-Out B4 = In B5 + In B8In B4 == (1,2,3,4,26,33)= (1,2,3,4,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)-//-//-Out B3 = In B4In B3= (1,2,3,4,26,33)= (1,2,3,4,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)-//-//-Out B2 = In B3 + In B12In B2 == (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)= (1,2,3,4,19,26,33)-//-//-Out B1 = In B2In B1 == (1,2,3,4,19,26,33)= (19,26,33)= (1,2,3,4,19,26,33)= (19,26,33)= (1,2,3,4,19,26,33)= (19,26,33)= (1,2,3,4,19,26,33)= (19,26,33)-//-//-5я итерация совпадает с 4й итерацией => итерационный процесс остановился =>Output B1 = (1,2,3,4,19,26,33)Output B2 = (1,2,3,4,19,26,33)Output B3 = (1,2,3,4,19,26,33)Output B4 = (1,2,3,4,19,26,33)Output B5 = (1,2,3,4,19,26,33)Output B6 = (1,2,3,4,19,26,33)Output B7 = (1,19)Output B8 = (1,2,3,4,19,33)Output B9 = (1,2,3,4,19,33)Output B10 = (1,2,3,4,19,26,33)Output B11 = (1,2,3,4,19,33)Output B12 = ()Output B13 = ().
