Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 81
Текст из файла (страница 81)
анализ пОтОкА данных (3) Полагаем (Х(Г)=ог, где( — одиночный интервал парадна й. Устанавливаем г = й. (4) Лля всех интервалов порядка 1 выполняем следующее. Пусть Г =-(Г„ ..., Г,) — интервал порядка 1 (Г„ ..., Г„ — ин. тервалы порядка 1 — 1 или участки, если с =- 1),Можно считать, чта эти подынтервалы перечислены в том порядке, в котором иэ них составлялся интервал Г в алгоритме 11.8. Иными словами, Г, †э заголовок и для каждого 1 > 1 множество (Г„ ..., Г г) содержит все вершины из Р, „являющиеся прямымн предкзмк интервала 11. (а) Пусть з„зо ..., з,— выходы интервала Г, каждый иэ которых прийадлежит участку в Р„являющемуся прямым предкам входа для Г. Полагаем РХ(ГВ-!Х(Г) () () ОЕХ(Г, А г=) (б) Лля всех выходов з Е Г,') полагаем ОПТ(Г„з) =(!Х()г) Г) ТКАХ5()„з)) () 6ЕХ(Г„з) (в) Лля )=2, .
„и пусть зао зго ...,з,,— выходы иятервала Г„! ~г ( Г, каждый из которых принадлежит участку в Р„являющемуся прямым предком входа для ГГ. Полагаем УХ(Г,) - („) О()Т (Г„ .ж) О()Т(11, з) = (1Х(11) () ТКАХ5(ГР з)) 0 ОЕХ(11, з) для всех выходов з интервала Гг. (3) Если 1=1, остановиться. В противном случае уменьшить 1 на 1 н вернуться к шагу (4). С) Пример 11.43. Применим алгоритм 11.7 к графу управления на рис. !1.41.
Лля четырех участков в Р, СТЕХ и ТКАХ5 вычисляются просто. Результаты вычислений приведены в табл. 11.9. Табзаеа 11 Э ') Если ннщреси имеет дез выхода, ведущих к одному н таму же сас. днащеиу антареалу, та ид диа нрфеигнвнастн енпаанения можно „слить". „Слияние" состоит е абьсзннсннн функций ЦЕМ н Тйдыз. 437 гл !! оптимизьпия подь Например, поскольку З, определяет талька переменную 1, Я, „убивает" предыдущие ее определения, но передает определения переменной г', а именно 52 и 53. Поскольку никакои из участков не определяет переменную дважды, все операторы определения внутри участка принадлежат множеству ОЕХ для давного участка. Заметим, что интервал !„ состоящий из одного участка З, ! имеет адин выход — оператор 52, Так как пути в Г, тривиальны, то ОЕХ(1„52) —.
(51, 52) и ТВАХЗ(1„52) — И. Интервал 1, имеет выход 59. В йримерс 11.44 мы видели, что ОЕХ(ГА, 59) = (53, 58) и ТКАХЗ(1„59) =- О. Теперь можно начать вычисление функдни ГХ. Как н требуется, 1Х(1,)=-0. Затеь! к двум подьгнтервалам в Г, можно применить шаг (4) алгоритма 11.7. Зто можно сделать только в порядке Г„Г,. На шаге (4а) вычисляем 1Х(1,)=ГХ(Г,) = О, а не шаге (4б)-— ОНТ(7„52) = (ГХ(Г,) В ТВАХЗ(7„52)) 0 ОЕХ(1„52) = (51, 52) Далее, на шаге (4в) (Х(У„)=ОЕТ(1„52) = (51, 52) Проходя по интервалам порядка 1, мы должны рассмотреть составляющие для 1, и !,. Интервал Г, состоит тальио из Я„ так что вычисляем !Х(Я,) = Е(. Интервал Г, состоит из участ.
ков Зм З, и З„которые в такам порядке и можно рассматривать. На шаге (4а) ! Х(Я!) = !Х(Г,) В СЕХ(1„59) = (51, 52, 53, 58) На шаге (46) 0()Т(Я„58) =-(ГХ(Я ) В ТВАХЗ(Я„58)) 0 ОЕХ(Зм 58) =(53, 54) Поскольку 58 ведет к Я„находим !Х(З,) = ОНТ(Ям 58) = (53, 54) а так кан 58 также ведет к З„то 1Х(Я,) —. ОНТ(Я„56) = (53, 54) Итак !Х(З,) = О ГХ(З*) — (51, 52, 53, 58) (Х(З,) = (53, 54) !Х(З,) =-.
(53, 54) ГЗ Индукпией па порядку интервала Г можно доказать, что (1) ТВАХЗ(1, а) — множество таких операторов определений дЕР, что существует путь нз первого оператора заголовка для Азз !!л. АнАлиз патакА денных Г аплот~ до а, вдоль которого ии один из операторов не пере- апредслнет персменную, определенную в д, (2) ОЕХ(1, е) †множест таких определений д, что сущест- вует пусь из д в е, вдоль которого ни один из операторов не персопределяет переменную, опрелеленную в щ Индукцией по числу применений шага (4) алгоритма 11. ма 1.7 можно доказатэь что (11.4.1) если для вычисления ГХ(ГА) применяется шаг (4), то !Х(Р) — множество таких определений д, что суще.
А ствует путь из д во вход для (г, вдоль которого ни адин из операторов не переопределяет переменную, определенную в д, а ОГГТ((м е) — множество танях д, что существует путь из д в з, вдоль которого ни адин нз операторов не переопределяет переменную, одределенную в д. Частным случаем утверждения (11.4.1), когда Г! — участок, является следующая теорема. Теорема 11.14. Для есех липеинмх участков З Е Р множество !Х(Я) е оыоритме 11.7 — зто мпожеспию токах определепиа д, юпо е Рь сУи(естерет пУть из д е пеРеь!л опеРоп!оР Участка Я, вдоль которого ни один из операторов пе переопределхет пере- менную, определенную е д. Е) 11Щ.Э.
Нвсводнмыв граФы управления Поскольку не каждый граф управления сводим, введем еще одно понятие, называемое расщеплением вершин, позволяю!дее обобщить алгоритм !1.7 иа все графы управления. Вершина, в которую входит более одной дуги, „расщепляется" на несколь. ко одинаковых копий, по одной на каждую входящую лугу. Таким абрагом, каждая копия имеет единственную входящую дугу и становится частью интервала для вершины, нз которой идет зта дуга. Позтому расщепление вершины с последующим постраевием интервала умен~тает число вершин графа по крайней мере па 1. Повторяя, если необходимо, этот пропесс, можно превратить любой несводимый граф управления в сводимый.
Пример 11.46. Рассмотрим несводимый граф управления на рис. 11.40, Всрп!пну п, можно расщепить на две нанни и, 'и и,", получив граф Р', изображенный на рис. 11.44, Ингерваламн для Р' будут 1, =- 7(п,) = (п„п,*) !(и') гл,н, оптнмнз»ция кодл Первый производный от Р' граф Р; имеет две вершины (рнс. ! 1.
45). Таким Второй производный граф состоит нэ единственной верш им образом, с помощью расщепления вершин мы превратили Р в сводимый граф управлении Р . Е/ Рнс. 11 вь Рлсщеплин- Рис. 11.45. Первый ный гриф тир»плинии проня»ихний граф. Дадим теперь молнфнцированный вариант алгоритма 11.7, учитывающий этот яовый метод, Начнем с простого полезного замечания. /(емца 11.15. Если С вЂ” граф управления и /(6]=6, та любая вершина л, отличная от напальной, гллггт ла крайней мере двг входящие дуги; ии одна из иих нг нххадг»т из л.
Доказательство. Все дуги, выходящие из некоторой верли . шины и входящие в иее же, исчезают при построении инте в. Поэтому предположим, чта вершина л имеет толька одну входящую дугу, выходящую из другой вершины лг. Тогда а принадлежит /(лг), Если !(6)=6, то вершина т в конце концов появляется в списке заголовков алгоритма 11.6. Но тогда и заносится в /(т), так что /(6) не может совпасть с 6. Алгоритм 11.8, Общее вычисление функции !Х. Вход. Произвольный граф управления Р программы Р.
Вытд. !Х(Я) для кгждого участка Я из Р. Мгтад. (1) Для каждого участка д/ Е Р вычисляем ОЕХ(Ю) и Т(( А ХЗ(й/). Затем к Р рекурсивно применяем шаг (2). Входам для шага (2) служит граф управления С вместе с ОЕХ(/,5) и ТКАХЗ(!,А), известнымн для каждой вершины /Е 6 и кажлого выхода з интервала /. Выходом шага (2) служит (Х(/) для каждой верши нны 11 4 АНАЛИЗ ОО1ОКА ДАННЫХ (2) (а) Пусть С вЂ” вход для этого шага и 6, Са ..., 6» — его производная последовательность. Если 6„ †одиночн вершина, продолжаем в точности так же, как в алгоритме 11.7. Если 6» — не одиночная вершина, то для всех вершин в СО ..., 6„можно вычислить ОЕХ и ТЙАХЗ, как в алгоритме 11.7. Тогда по лемме 11.15 6» содержит некоторуи» вершину, отличную от начальной, в которую входит более одной дуги.
Выберем одну ив таких вершин l. Если в / входит / дуг, заменяем / новыми вершинами /о В каждую из /а, .., /! входит по одной дуге, все они выходят нч различных вершин, из которых ранее шли дуги в /. (б] Для каждого выхода з интервала / порождаем выход зг длн 1(((( и считаем, что в Р есть луга, ведущан нэ каждого 3, во вход каждой вершины, с которой в связан в 6 .ОпределяемОЕХ(/Озг) =.ОЕХ(/, з) и ТЙАХЗ(/1, з;] =.
= ТКАХЬ(/, з] для 1(/(/. Результирующий граф обозначим 6'. (в) Применим шаг (2) к 6'. функция 1Х будет рекурснвна. 1 вычисляться длн 6'. Затем, полагая 1Х(/) = 6 1Х(!,) 1= 1 вычисляем 1Х для вершин из 6,. Никакие другие изменения для 1Х не требуются. (г) Как и в алгоритме 11.7, вычисляем )Х для С по !Х для С». (3) После завершения шага (2) функция (Х будет вычислена. для каждого участка из Р. Эта информация и образует выход алгоритма. (З Пример 11.47.
Рассмотрим граф управленняр, на рис. 11Аб,а. Можно вычислить граф Р',= !(Р,), изображенный на рис. 11.46,5. Однако /(Р,]= Р„ тан что индо применять процедуру расще. пления вершин шага (2). Пусть (н„а,) — вершина !, которая расщепляется на /, н /,. Результат показан на рнс. 11.47. Свяжем л, с !„а (а„а») с /,. На рисунке изображены дуги из /, и /, в (н„л,). В действительности каждый выход длн / дублируется— один для /, и один для !,.
С ахалая лля (л„п,) связаны именно продублнрованные выходы, и этот факт на рйс. 11.47 представлен двумя дугами. Отметим, чта граф на рис. 11.47 — сводимый, С) Теорема 1!.15. Алгоритм 11.8 всегда заканчивается. Доказательство. По лемме 11.15 каждое обращение к. шагу (2) осуществляется либо на сводимом графе, н в этом случае можно быть уверенным, чта вычисление закончится; ли. бо на вершине /, которую можно расщепить. Заметим, что каждый из интервалов /„..., /, порождаемых на шаге (2), имеет елин- 445 гл и оптимизьцня кодл п.4 Анелиз ООТОкА денные Рее. ! !.47.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
