Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 63
Текст из файла (страница 63)
Д Т, Пгреимгкозиние Ясна, что поскольку речь идет о значении блока З =(Р, /, 1/), имена переменных, которым пр~свавваются значения, несучцественны. Предположим, что операторам 5, в Р является А 335 Гл и ОптимизАиия кодА ил ОптимизАиия линейноГО ьчлсткА ОВ,...
В, и переменная С не активна в области действия оператора 5, Тогда ыожио положить Я' =-(Р', /, 6'), где Р' †э Р, в ко~ором оператор 5, зачсиеи на С ОН, ... В„ а все вхождения А в области действии оператора 5, заменены на С. Если 6 лежит в области действия оператора 5„ то Си зто 6, в котором переменная А заменена иа С. Б противном случае 6'.:- 6. П реобразоаащ1е Т, Отображает Я и 21'. Пример !1,б.
Пусть Я =-(Р, (Л, В), (Р)), где Р состоит на Т ААВ Т Т вЂ” А Р ТьТ Одно применение Т„позволяет нзмеипть имя переменной Т, которой присваивзется зиаченяе первым оператором, на 5 Таким образом, Т, отображает Я в 33'=(Р', (А, В), (Р)), где Р' состоит нз 5 ААВ Т 5 — , 'А Р ТАТ Отметим, что переменная Т заменена на 5 только в первом операторе присваивания. Гд ТР Перестаиоака Пусть Я =(Р, /, 6) — блан, в котором оператором 5, является А ОВ,...В„оператором5г., явлнетсяС ОР,,Р„А нс совпадает на с одной из переменных С, Р,,..., Р, и С не совпадает пи с одной из переменных Л,В,,..., Н,. Тогда преобразование Т, отображает блок Я в Я'=(Р', I, 6), где Р' — это Р, в котором 5, и 5ГА, персставлены.
Пример 11.О. Пусть Я=(Р, (А, В), (Р, 6)), где Р состоит из Р А+В 0 ААВ Можно применить Т, и отобразить Я в (Р', (А, Н), (Р, 6)), где Р' состоит из 6 А»В Р— А -Г В Однако с помощью Т, нельзя отобразить блок Я,=(Р„(А, В), (Р, 6)), где Р, состоит из Р А ' В 6 -РиА ЗЗА в блок Я,=(РО (А, В), (Р, 6)), где Р, состоит из 6 РиА Р А+В Б самом деле, в этом случае Я, даже не блок, потому что переменная Р используется, не будучи предиарнтеиъно определен.
ной () Определим теперь некоторые отношения зкпивален~ности, связанные с действиями четырех определенных выше преобразонанпй. Опрелелеиие. Пусть 5 - подмножество многкегтаа (1, 2, 3, 4). Будем пясать Я, =>АЯ.„ ссли одно првменеиве преобразоааиия Т, перевалит Я, в Я„ причем г 6 5. Булем писать Я, иьЯИ если существует такая последовательность блоков а„ ..., и.„, что (1) О„=ЯО (2) и"„=Я„ (3) длк каждого С 3 <1 л, либо а,=>зв,А„либо ьт,~зйг Такам образом, иэ — это наименьшее Отношение эквивалентности, содержащее ~з и отрангак~щее идею о том, что преобразования могут применяться в любом направлении.
Соглашение. Подмножества (1, 2, 3, 4) будем изображать без СКОбОК, таК Чта, НАПРИМЕР, =>ИЛГ бУДЕМ ЗаПИСЫВатЬ ~г А Теперь мы хотим поиазать, что блоки Я, и Я, эквивалентны тогда и тотько ~огда, когда сущестиу'ет последовательность преобразований, включающая в себя только преобразования Т, --Т,, которая отображает Я, в Я, Иными словамн, Я, =-Я, тогда и только тогда, когда Я, ФФ Я, Достаточность условия проверяется легко: надо лишь показать, что каждое отдельное преобразование сохраняет значение блока.
Теорема 11.1. Если Я,=Ь...,Я„то Я,:=--я,. Доказательство. Упражнение. Читатель должен также показать, что для Р в преобразовании Т„можно выбрагь побое новое имя, как это угверждалось в описании преобразования. Слегштвиет Если Я, ев Я,, то .З, = — ЯА. Ез Б равд. 11.1,4 будет доказано обращение этого утверждевня. ззг ГЛ И ОПТИЫИЗЛ!ДИЯ КОДЛ и 4. Оптилтизлиия лингннаго учлсткд 11.1.3. Графические представление блоков В настоящем разделе мы покажем, что для каждого блока Я в (Р,1, В)можно найти ориентированный апиклнческий граф О, естественным образом представляюшив Я.
Каждый лист графа 0 соответствует одной входной переменной в 1, а каждая его внутренняя вершнва — апсрагору из Р. К ориентироаанныч аинклнческим графам легко применяются преобразования блоков, рассматревные з предыдущем разделе. Определение. Пусть Я вЂ . (Р, 1, В) †бл. Построим из Я помеченный упорядоченный граф ') В (М): (1) Пусть Р= 50 ...; 5„ (2) Для канадой переменной А 61 образуем вершпну с меткой А и будем называть ее последним олргдглглисм для А. (3) Для/= 1, 2, ..., Оделяем следующее. Пуст оператором 5, является А ВВ, ... В,.
Обрвзуем нову~а вергпнну, помеченную О, из которой выходят г ориентированных дуг. !!усть /-я дуга (при упоркдаченви дуг слева направо) указывает на последнее определение для Ву, 1 "1<г. Новая вершина, помечеипая й, становится последним определением для А. Эта вершина своазстгтоуст оператор> 5, в Р. (4) После шага (3) вершины, являющиеся наследиями определешэямн выходных переменных, в дальнейшем помечаются как „выделенные".
Выделенные вершины будем эшображать двойными кружками. Пример 11.7. Пусть Я =(Р, (А, В), (Р, 6)) †бл, в котаром Р состоит нз оператарон Т А В Р АьТ Т Вд-Р 6 ВьТ Граф 0(Я) изображен на рис. П.!. Отметим, что на рис, П.) четыре оператора из Я соот. ветствуют па порядку вершинам л„лю лэ, л,. Отметим такуке, Чта ПРЯМЫМ ПатаМКОМ аЕРШИПЫ ГГ, ЯВЛЯЕтеа Лю а НЕ Ли Паскольку при создании вершины л, вершина л, была последним определением для Т.
() Каждый граф естественным образоы представляет класс эквивалентности отношения еь. Иными словами, если блок Я, с помощью некоторой последовательности преобразований Т, и 7', ') до кокдь этого я з следующем рьэдсье оод словом „граф" будем иод. рзэуиевать „орньдтзроьаьзмй аиикдкчь«дьй граф".— Орки. ргд. зза можно отобразить в блок Яю то блоки Я, и дд, имеют тот же граф, и обратно. Одна часть этого утверждении лает приведеин)чо ниже лемму, доказательства которой чается в использовании Определений и предоставляется читателю.
Лемма 11.1. Если Я, ы! Аи яь, то 0(Я«)=0(Я,). Доиазательство.Упражнение. Сд олин и состан- заклю- 44 Доказательство. Упражнение. Следукущаэ« теорема поназывает, чта два блока имеют один и тот же граф тогда н только тогда, когда один из них можно преобразовать в другой переименованием и перестановкой Теорема 11.2. 0(13,) —.0(Я„) тогда и то,эько лэогдо, ког«)а Я, еаЯО Доказательство. Достаточность следует из леммы 11.1. Для доказательства необходииости рассмотрим два блока Я,= = (Р„ /О В,) и Я„= (Рю /ю О,), дл Я котоРых В (Я,) = 0 (Я,) — О. Поскольку графы одинаковы, входные множества должны совпа- Ззо Следствие. Если Я, доЯО то 0 (Я,) =- О!Я ).
Г) Доказательство обратнога утверждения более трудно. Для него понадобятся л, еше одна определенне и лемма. Определение. Блок Я = (Р, /, В) называют открьилым, если (1) нн один из операторов в Р не имеет вида А а, где АБ/, (2) в Р нет двух Операторов, присваи- ркс.
ы !. прнчер орден. вающих значение одной н той же пере. тзрььь~пюго ьиьддьче. ского гр*сю, меннон. В открытом блоке Я = (Р, 1, В) все операторы 54 из Р присваивают значения различным переменным Хг, не входящим в !. В лемме 1!.2 утверждается, что открытый блок всегда можно получить переименованием переменных с помощью только преобразования 7',. Лемма П.2. Пусть Я =(Р, 1, В) — блок. Тогда суи!е«тоугт такой экзиаилгнлтыэ открытый блок Я'=-(Р', 1, В'), что гл и.
оптимизлния кадя дать, так что можно положить 1, = 1, =- П Кроме тога, число операторов в Р, в Р, должно быть одинаковым, так что можно положить Р, =. 5,;...;5„и Р,= Ьг,,... 1)7„. С помощью переименования Т, можно построить два откры- тыхблокаЯ; =(Р;,1;, 0;) и Яг' —.. (Р:,1;,0;) садним н темжемножеством переменных, которым прнсваиваются значении, причем (1) Я( езЯ, (2) Я; еэЯа (3) если Р, =5;:...;5„и Р;=)7;1...)В;„то 5; и В) осуществляют присванвание одной и той же переменной тогда и только тогда, когда им соответствует одна и та же вершина в 0 (Из следствия леммы 11.1 видно, чта 0 (Я;) †.
0 (Я;) = О.) Прн создании огкрьпых блоков сначала всем переменным блоков Я, н Я., даем поные имена. Затем можно снова воспользоваться перевменоваинем, чтобы удоплетпорить >с !овню (3). Будем теперь строить такую последовательность блоков йа ..., 6„, что (4) Ф, =Я;, (3) 6„=-Я:, (б) бг аубг„для 0<1<и, (7] операторами в йг являются Р;; ...; Р;, за которыми еле. дуют операторы из 5,; ...; З„не осуществляющие присваиваний тем переменным, которытг уже присвоены значения одним из операторов )7;1... 1Р(. Ясно, что 0(Я,) =0 и операторы, определяющие одни и те же переменные в 6г и Я;, порождают одинаковые вершины в О.
Начнем с ьь= — Я;, Условие (7) удовлетворяется трнвиальна. Предположим, что мы уже постраилк Яг, ! О, Список операторов нз 6г можно записать как )7; 1 ...; )7;.; 5;.; ...; 5; и в нем операторы 5;,, 5;, удовлетворшот условию (7). По определению Р; и Р, 'найдетсн оператор 5;, осуунествляю. щнй првсваивапис той же переменной, что и В о Поскольку 5,' и В;, соответствуют одной и той же вершине в О, та 5' ссылается только на переменные из ! иая па те, которым присваивз~отся значения опера~орами )7;1 ..
л Щ, а в действитслыюсти В„, =5;.. Таким образом, повторяя Т„можно поггавигь 5; перед всеми ач1...15; . В результате будет блок Ыг;, условия (6) и (7) легко проверяются. зэа нл. оптимизлния линеииаго хчхстКх Когда в условии (7) (=п, получаем условие (3). Итак, откуда Я, аэЯ,. Следствие. Если 0(Я,) =0(Я,), та ЯгмэЯт. Д о к а аз тел ь от в о. Следует непосредственна из теорем 1!.1 я 1 !.2. В силу этого следствия граф можно снабдить значением, а именно значением любого блока, имеющего данный граф.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
