brotikovskaya_420_task3 (домашние задания)

Домашнее  задание  №4  по  курсу  “Конструирование  компиляторов”  Построение  натурального  цикла  Entry  End  B1          01  i  <  1    02  j  <  0    03  goto  L5    B9                L5:  39  ifTrue  i  <  M    40  goto  L4  41  else  42  goto  L6  B2                  L4:  05  goto  L2  B3                  L7:  15  t2  <  *,  4,  j  16  t3  <  p[t2]    17  t4  <  *,  4,  i    18  t5  <  p[t4]      19  ifTrue  t3  !=  t5    20  goto  L1    21  else    22  goto  L3    B10          L6:    Бротиковская  Данута,  420  группа  Исходный  граф  потока  управления  End  Entry  B10  B1  B9  B2  B5                L2:          10  ifTrue  j  >  0    11  goto  L7    12  else  13  goto  L3    B4                L1:  07  t1  <  -­‐,  j,  1    08  j  <  d[t1]    B5  B6                  L3:  24  t6  <  *,  4,  j    25  t7  <  p[t6]    26  t8  <  *,  4,  i    27  t9  <  p[t8]    28  ifTrue  t7  =  t9    29  goto  L8    30  else    31  goto  L9    B8              L9:  35  t10  <  *,  4,  i    36  d[t10]  <  j    37  i  <  +,  i,  1  B3  B4  B6  B7  B7            L8:  33  j  <  +,  j,  1  B8  End  B10  Домашнее  задание  №4  по  курсу  “Конструирование  компиляторов”  Построение  натурального  цикла  Entry  Бротиковская  Данута,  420  группа  B1  B9  В  данной  программе  2  обратных  ребра  –      B4:B5  и  B8:B9  B2  B5  B3  B4  B6  B7  B8  Изначальный  ГПУ  (1)  End  B10  Домашнее  задание  №4  по  курсу  “Конструирование  компиляторов”  Построение  натурального  цикла  Entry  Бротиковская  Данута,  420  группа  B1  B9  B2  B5  B3  B4  B6  B7  B8  Изначальный  ГПУ  (1)  В  моей  программе  только  одно  обратное  ребро  –  B8:B9    •  Строим  инвертированный  граф  без  найденного  обратного  ребра  (2)  •  Помечаем  вершину  B8    End  Entry  B10  B1  B9  B2  B5  B3  B4  B6  B7  B8  Инвертированный  ГПУ  без  обратного  ребра  (1)  End  B10  Домашнее  задание  №4  по  курсу  “Конструирование  компиляторов”  Построение  натурального  цикла  Entry  Бротиковская  Данута,  420  группа  •  Проходим  поиском  в  глубину  по  инвертированному  графу  без  обратного  ребра  (2)  •  Каждую  посещенную  вершину  помечаем  •  Получаем  множество  помеченных  вершин  –  которые  входят  в  натуральный  цикл,  связанный  с  ребром  B8:B10      {B8,  B6,  B5,  B2,  B9,  B1,  B4,  B3,  B7}  B1  B9  B2  B5  B3  B4  B6  End  Entry  B10  B1  B9  B2  B5  B3  B4  B6  B7  B8  Изначальный  ГПУ  (1)  B7  B8  Инвертированный  ГПУ  без  обратного  ребра  (1)  End  B10  Домашнее  задание  №4  по  курсу  “Конструирование  компиляторов”  Построение  натурального  цикла  Entry  Бротиковская  Данута,  420  группа  B1  B9  B2  B5  B3  B4  B6  B7  B8  Изначальный  ГПУ  (1)  В  моей  программе  только  одно  обратное  ребро  –  B4:B5    •  Строим  инвертированный  граф  без  найденного  обратного  ребра  (2)  •  Помечаем  вершину  B4    End  Entry  B10  B1  B9  B2  B5  B3  B4  B6  B7  B8  Инвертированный  ГПУ  без  обратного  ребра  (1)  End  B10  Домашнее  задание  №4  по  курсу  “Конструирование  компиляторов”  Построение  натурального  цикла  Entry  Бротиковская  Данута,  420  группа  •  Проходим  поиском  в  глубину  по  инвертированному  графу  без  обратного  ребра  (2)  •  Каждую  посещенную  вершину  помечаем  •  Получаем  множество  помеченных  вершин  –  которые  входят  в  натуральный  цикл,  связанный  с  ребром  B4:B5      {B4,  B3,  B5}  B1  B9  B2  B5  B3  B4  B6  End  Entry  B10  B1  B9  B2  B5  B3  B4  B6  B7  B8  Изначальный  ГПУ  (1)  B7  B8  Инвертированный  ГПУ  без  обратного  ребра  (1)  End  B10  Домашнее  задание  №3  по  курсу  “Конструирование  компиляторов”  Построение  натурального  цикла  Entry  End  Entry  B1  B10  B1  •  По  полученному  множеству  вершин  строим  натуральный  цикл    •  В  итоге  найдено  2  натуральных  цикла  B9  B2  B9  B2  B5  B5  B3  B4  B3  B6  B4  B6  B7  B8  Натуральный  цикл  1  B7  B8  Натуральный  цикл  2  .