Главная » Просмотр файлов » А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий

А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 152

Файл №1114947 А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий) 152 страницаА.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947) страница 1522019-05-08СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 152)

Мы рассматриваем только "половинные*' решетки, в которых имеется только один из операторов сбора или объединения. Таким образом, рассматриваемые нами полурешетки являются ппирешеткаии сбора (шее( яепп1ап)сез). Можно также говорить о полуре1аел)ках объес)инения ((о)п зеш(1а(бсез), у которых существует только один оператор объединения; имеется ряд кни); в которых при анализе программ используется понятие полурешеток объединения.

Но поскольку традиционно литература. посвященная потокам данных говори г о решетках сбора, в данной книге мы поступим так же. опушены ребра от .т к Гп если на лиаграмме имеется иной путь от т, к Гь Таким обРазом, хотЯ (г)(,с1з,дз) < (И(), мы не изобРажаем это РебРо из-за наличиЯ, например, пути, идущего через (с1), а)з). Рис. 9.22. Решегка подмножеств определений 749 9,3. Основы анализа потока данных Решетки произведений Хотя на рис. 9.22 имеется только три определения, диаграмма решетки типичной программы может оказаться существенно большей. Множество значений потока данных является показательным множеством определений, и при наличии в программе п определений содержит 2" элементов. Однако определение достигает точки программы независимо от достнжимости других определений.

Таким образом, решеткуа определений можно рассматривать как полученную в резулыаге "произведения" простых решеток для каждого из определений. Если бы в программе имелось только одно определение 4, то решетка ильела бы два элемента— пустое множество (), являющееся верхним элементом, и нижний элемент (с1). Формально можно построить решетки произведений следующим образом. Предположим, что (А, ЛА) и (В, Лн) — (полу)решетки.

Решетка произведения 1ргос)пег 1арбсе) этих двух решеток определяется следующим образом. 1. Областью определения решетки произведения является А х В. 2. Оператор сбора Л решетки произведения определяется следующим образом. Если (а, Ь) и (а', Ь') являются элементами области определения решетки произведения, то (а, Ь) Л (а, Ь ) = (а Л 4 а, Ь Лн Ь ) (9.2) Очень просто выразить частичный порядок < для решетки произведения в терминах частичных порядков <4 и <н для А и В: (аз Ь) < (а', Ь') тогда и только тогда, когда а <4 а' и Ь <н Ь' 19.3) Чтобы понять, почему (9.3) следует из 19.2), заметим, что (а, Ь) Л (а', Ь') = (а Ли а, Ь Лн Ь') 'Здесь и далее мы часто опускаем приставку "полу", поскольку решетки наподобие рассматриваемой имеют оба оператора, даже если одним мы и не пользуемся.

Следует заметить, что на такой диаграмме ясно видны результаты операции сбора. Поскольку х Л у представляет собой наибольшую нижнюю границу, всегда имеется большее г, к которому ведут пути от х и у. Например, если х — (с)з), а у — (с1з), то л на рис. 9.22 представляет собой (Ны дз), что логично, так как оператор сбора представляет собой объединение. Верхний элемент множества всегда находится наверху в диаграмме, так что от элемента Т существуют пути к каждому из остальных элементов.

Аналогично нижний элемент находится внизу в решетке, и к этому элементу 3 имеется путь от каждого из остальных элементов. 750 Глава 9. Машинно-независимые оптимизации Можно задаться вопросом "При каких условиях (а Л4 а', Ь Лп Ь') = (а,6)?" Это соотношение выполняется в точности тогда, когда а ЛА а' = и и Ь Лн 6' = 6. Но эти два условия те же, что и а <л а' и Ь <и Ь'. Произведение решеток — операция ассоциативная, так что можно показать, что правила (9.2) и (9.3) распространяются на любое количество решеток, т.е. если даны решетки (А„Л;), г = 1,2,...,к, то произведение всех /с решеток в указанном порядке имеет область определения А, х Аз х х Аы оператор сбора, определяемгяй как (аыаз,...,аь) Л (ЬыЬз,...,Ьь) = (а1 Л Ьыаз Л Ьз,...,аь Л Ьь), и частичный порядок (аы аъ, аь) < (Ьы Ьг,..., Ьь) тогда и только тогда, когда а, < 6, для всех г Высота полурешетки Получить информацию о скорости сходимости алгоритма анализа потока данных можно путем изучения связанной с ним полурешетки.

Восходящей кепочкой в частично упорядоченном множестве (К, <) является последовательность, в которой хз < хз « .. х„. Высота полурешетки представляет собой наибольшее количество отношений < в восходящей цепочке, т.е. высота на единицу меньше количества элементов в такой цепочке. Например, высота полурешетки достигающих определений программы с п определениями равна и.

Показать сходимость итеративного алгоритма потока данных существенно проще, если полурешетка имеет конечную высоту. Ясно, что конечную высоту имеет полурешетка, состоящая из конечного множества значений; возможна также ситуация, когда решетка с бесконечным количеством значений также имеет конечную высоту. Соответствующим примером является решетка, используемая в алгоритме распространения констант, который будет подробно рассмотрен в разделе 9А.

9.3.2 Передаточные функции Семейство передаточных функций Е: Ъ' — 1' в структуре патока данных обладает следующими свойствами. 1. Г содержит тождественную функцию 1, такую, что 1(х) = х для всех х из Ъ'. 2. Е замкнуто относительно композиции, т.е. для любых двух функций г" и д из Е функция 6, определяемая как 6 (х) = д (г' (з)), также принадлежит Е. 751 9.3. Основы анализа потока данных Пример 9.19.

В случае достигающих определений тождественная функция г представляет собой частный случай, когда лен и й!1 являются пустыми множествами. Замкнутость относительно композиции фактически была показана в разделе 9.2.4; вкратце повторим здесь это доказательство. Предположим, что у нас есть функции !~ (х) = С10 (х — К ) и !г(х) = Сг 0 (х — Кг) Тогда Ь (Л (х)) = Сг 0 ((С10 (х — К|)) — Кг) Правая часть приведенной формулы алгебраически эквивалентна (С, 0 (С1 — Кг) ) 0 (х — (К1 0 Кг) ) Если положить К = К1 0 Кг и С = Сг 0 (С1 — Кг), то композиция функций !1 и !г принимает вид ! (х) = С О (х — К), что делает ее принадлежащей семейству К. Если рассмотреть доступные выражения, то можно применить те же аргументы, которые использованы для достигающих определений, и показать как наличие тождественной функции в семействе Г, так и его замкнутость относительно композиции.

и Монотонные структуры Чтобы итеративный алгоритм потока данных работал, структура потока данных должна удовлетворять еще одному условию. Мы говорим, что структура монотонна, если при применении любой передаточной функции ! из г к двум членам г', первый из которых не превышает второй, полученный результат для первого члена не превышает результат вычислений для второго члена. Формально структура потока данных (27, г', 'г", Л) монотонна, если из х < у следует ! (х) < ! (у) для всех х и у из Ъ' и ! из г (9.4) Монотонность может быть определена и следующим эквивалентным образом: !(хну) < !(х) Л !(у) для всех х и у из Ъ' и ! из г (9.5) Уравнение (9.5) гласит, что если собрать два значения и применить передаточную функцию !, то результат не превзойдет результат, полученный путем применения ! к отдельным значениям с последующим их сбором.

Эти два определения монотонности кажутся слишком различными, так что они оба оказываются весьма полезны — в разных ситуациях мы будем пользоваться разными определениями. Ниже приведен набросок доказательства их эквивалентности. 752 Глава 9. Машинно-независимые оптимизации Сначала выведем (9.5) из (9.4). Поскольку х Л у представляет собой наибольшую нижнюю границу х и у, мы знаем, что хЛу<хихЛу<у Таким образом, согласно (9.4) 1 (х Л у) < 1(х) и 1 (х Л у) < ) (р) Поскольку 1" (х) Л 1 (у) представляет собой наибольшую нижнюю границу 1'(х) и 1' (у), мы получаем (9.5). Теперь предположим, что выполняется (9.5), и докажем, что при этом выполняется (9.4). Мы принимаем, по .г < р, и используем (9.5) для того, чтобы заключить, что 1' (х) < 1' (у), что докажет (9.4). Уравнение (9.5) гласиг, что 1(.гЛу) < 1(х)Л /,'р) Но поскольку мы предположили, что з '- у, но определению .г л у -: х.

Таким образом, (9.5) приходит к виду / (т) < 1 (х) Л 1 (у) Поскольку 1 (х) Л 1' (у) представляет собой наиболыную нижнюю границу 1'(х) и 1' (у), мы знаем, что 1' (х) Л 1' (у) < 1' (у). Таким образом. Х (х) : Х (х) ' 1'(у) < 1 (у) и из (9.5) следует (9.4). Дистрибутивные структуры Зачастую структура удовлетворяет более строгому, чем (9 5), условию, которое мы называем условием дисв~рнбутнвносвш: Г (х Л и) =- Г (х) л Г (у) для всех:г и у из 1' и,г из К Безусловно, если а = б, то в соответствии со свойством ндемпотентности иЛБ = о.

так что а < 6. Таким образом, листрибутнвность влечет за собой монотонность (однако обратное неверно). Пример 9.20. Пусть р и х — множества определений в структуре достигающих определений. Пусть 1' — функция, определяемая уравнением Г (х) =- С 0 (х — К) для некоторых множеств определений С и К. Можно убедиться, что структура достигающих определений удовлетворяет условию дистрибутивности, проверив, что С 0 ((у 0 ") — К) = (С 0 (у — К)) 0 (С 0 (г — К)) 753 9.3. Основы анализа потока данных Зто уравнение только кажется страшным. Начнем с определений, входящих в С. Очевидно, что эти определения входят в множества, определяемые как левой, так и правой частями уравнения.

Таким образом, необходимо рассмотреть толы<о определения, не входящие в С. В этом случае можно убрать С из уравнения и проверить выполнение уравнения (у О .) — К =- (р — К) О (- — К) Это тождество элементарно проверяется при помощи диаграммы Вепна. 9.3.3 Итеративный алгоритм в обобщенной структуре Можно обобщить алгоритм 9.11 для работы с большим количеством задач потоков данных. Алгоритм 9.21.

Характеристики

Список файлов книги

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6439
Авторов
на СтудИзбе
306
Средний доход
с одного платного файла
Обучение Подробнее