А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 230
Текст из файла (страница 230)
На рис. 12.32 схематически представлены описанные преобразования. 1119 12.7. Реализация 1за1а1оа с применением В130 б) Слияние узлов а) Сокращенное выинеленне Рис. 12.32. Преобразования В13Р 12.7.3 Представление отношений при помощи ВРР Отношения, с которыми мы работаем, имеют компоненты, взятые из "областей определений". Область определения компонента отношения — множество возможных значений, которые в этом компоненте могут принимать кортежи. Например, отношение ргз (Г, Н) имеет в качестве области определения первого компонента все переменные программы, а в качестве второго — все инструкции, создающие новые обьекты. Если домен имеет более 2" ' возможных значений, но не более 2', то для представления значений этого домена требуется п бит или булевых переменных.
Таким образом, кортеж в отношении может рассматриваться как присваивание истинности переменным, представляющим значения из области определения для каждого компонента кортежа. Отношение можно рассматривать как булеву функцию, которая возвращает значение "истинно*' для всех тех присваиваний, которые представляют кортежи отношения. Пример 12.28 должен пояснить сказанное. Пример 12.28. Рассмотрим отношение т1А, В), такое, что область определения и А, и  — (а, 6, с, сЦ. Закодируем а битами 00, Ь вЂ” 01, с — 10 и д — ! 1. Пусть кортежи отношения г представляют собой Воспользуемся булевыми переменными шж для кодирования первого (А) компонента и переменными ра — для кодирования второго (В) компонента. Тогда отношение г превращается в иго Глава 12.
Межпроцедурный анализ Иначе говоря, отношение г преобразовано в булеву функцию, истинную для трех наборов параметров — шхуз = 0001, 0010 и 1110. Заметим, что именно эти три последовательности битов встречаются в качестве меток на путях от корня к листу 1 на рис. 12.31, т.е. ВПП на этом рисунке представляет описанное выше отношение г. о 12.7.4 Операции отношений и ВРР-операции Теперь посмотрим, как представить отношения в виде диаграмм бинарного выбора. Однако для реализации алгоритма наподобие алгоритма 12.18 (инкрементное вычисление Па1а!о8-программ) нам надо уметь работать с В!ЗП так, чтобы наши действия отражали работу с самими отношениями. Вот основные операции, которые мы должны выполнять над отношениями. !.
Инициализация. Мы должны создавать В!э!э, которые представляют единственный кортеж отношения. Мы будем затем связывать их в ВП13, представляющие большие отношения при помощи объединения. 2. Объединение. Чтобы получить объединение отношений, мы применяем логическое ИЛИ к булевым функциям„представляющим отношения. Эта операция нужна не только для построения начальных отношений, но и для объединения результатов нескольких правил для одного и того же заголовка предиката и для накопления новых фактов в множествах старых фактов, как в случае инкрементного алгоритма 12.! 8. 3.
Проекция. При вычислении тела правила мы должны строить заголовок отношения, который вытекает из истинных кортежей тела. В терминах ВПП, которая представляет отношение, мы должны удалить узлы, помеченные теми булевыми переменными, которые не представляют компонентов заголовка. Может также потребоваться переименовать переменные в ВИЭ для соответствия булевым переменным компонентов отношения заголовка. 4. Соединение. Чтобы найти значения переменных, которые делают тело правила истинным, нам надо "соединить" отношения, соответствующие каждой из подцелей. Предположим, например, что у нас есть две подцепив г(А,В) й я(В,С). Соелинение отношений для этих подцелей представляет собой множество троек (а, 6, с), таких, что (а, б) является кортежем 1!2! 12.7.
Реализация Ра)а!оя с врнмененнем ВРР в отношении для г, а (о, с) — кортежем в отношении для а. Мы увидим, что после переименования булевых переменных в ВРР, такого, что компоненты для двух В согласуются по именам переменных, данная операция над ВРР аналогична операции логического И, которая, в свою очередь, похожа на операцию ИЛИ, реализующую объединение. Диаграммы бинарного выбора для отдельных кортежей Чтобы инициализировать отношение, нам нужен способ построить ВРР для функции, которая истиннадля единственного набора значений. Предположим, что у нас есть булевы переменные х), хз,..., х„, имеющие значения а), аз,..., а„, где каждое а, равно 0 или 1.
Для каждого х, ВРР будет иметь один узел Хь Если а; = О, то верхнее ребро из Д!, ведет в лист О, а нижнее ведет в Ж, ).) или, если 1 = п, в лист 1. Если сн = 1, то справедливо то же самое, но с заменой верхнего ребра нижним, и наоборот. Такая стратегия дает нам ВРР, которая проверяет, имеет ли каждая переменная х, (г = 1, 2,..., п) корректное значение. Если обнаруживается некорректное значение, мы переходим непосредственно в лист О. Лист 1 достигается только в том случае, когда все переменные имеют корректное значение.
В качестве примера взгляните на рис. 12.33, б. Показанная здесь ВРР представляет функцию, которая истинна тогда и только тогда, когда х = у = О, т.е. ее истинный набор значений — 00. ) о б) а) Рис. 12.33. Построение ВРР для логического ИЛИ Объединение Приведем подробное описание алгоритма, дающего логическое ИЛИ двух ВРР, т.е. объединения отношений, представленных этими ВРР.
П22 Глава 12. Межпроцелурный анализ Алгоритм 12.29. Объединение двух В!313 ВХОД: две упорядоченные В!313 с одним и тем же множеством переменных в одном и том же порядке. Вых0д: В013, представляющая функцию, которая является логическим ИЛИ двух булевых функций, представленных входными В013. Мптод: ниже описана рекурсивная процедура обьединения двух В13П. Применяется индукция по размеру множества переменных, участвующих в обеих В13П. Блзипл нуль переменных.
Обе ВП13 представляют собой листья, помеченные О либо !. Выходом является лист 1, если хотя бы один из входов равен 1, и О, если оба входа равны О. Индукция: предположим, что в двух В13Р найдено й переменных, ум уз,..., уы Выполняем следующее. 1. При необходимости используем обращение сокращенного вычисления для добавления нового корня, с тем чтобы оба В!30 имели корень с меткой дп 2. Пусть корнями являются узлы !т' и М, их нижними дочерними узлами— узлы !Уо и Мо, а верхними дочерними узлами — !У~ и Мп Рекурсивно применяем данный алгоритм к диаграммам с корнями !Уо и Мо, а также к диаграммам с корнями !Уз и Мы Первая из этих диаграмм представляет функцию, которая возвращает значение "истина" для тех истинных наборов данных, у которых у~ — — О, а вторая — для у! = 1.
3. Создаем новый корневой узел с меткой уп Его нижним дочерним узлом является корень первой рекурсивно построенной В!30, а верхним дочерним узлом является корень второй рекурсивно построенной ВР13. 4. Выполняем слияние листьев с метками О и с метками 1 в построенной объединенной В!313. 5. Применяем, где это возможно, сокращенные вычисления и слияние для упрощения В13П. о Пример 12.30. На рис. 12.33, а и б приведены две простые В013. Первая представляет функцию х ОК у, а вторая — функцию в10Т к А!90 НОТ у. Заметим, что логическое ИЛИ, примененное к этим функциям, дает функцию 1, т.е. функцию, всегда возвращающую значение "истина". Чтобы применить алгоритм 12.29 к этим диаграммам, рассмотрим нижние и верхние дочерние узлы двух корней, начав с верхних.
Верхний дочерний узел корня на рис. 12.33, а — 1, а на рис. 12.33, б — О. Поскольку оба дочерних узла находятся на уровне листьев, мы не должны вставлять узлы с меткой у вдоль каждого ребра, хотя результат при этом получился бы г!23 ! 2.7. Реализация Оа1а1од с применением В!7!з тот же самый. Базисный случай для объединения О и 1 заключается в получении листа с меткой 1, который становится верхним дочерним узлом нового корня. Нижние дочерние узлы на рис.
12.33, а и б имеют метки у, так что мы можем вычислить объединение В13Р рекурсивно. Нижними дочерними узлами узлов у являются О и 1, так что комбинацией их нижних дочерних узлов является лист 1. Аналогично верхними дочерними узлами узлов у являются О и 1, так что комбинацией их верхних дочерних узлов также является лист 1.
при добавлении нового корня х мы получаем В!313, показанную на рис. 12.33, в. Но зто не все, поскольку В13Р на рис. 12.33, в можно упростить. У узла с меткой у оба дочерних узла представляют собой лист 1, так что узел у можно удалить и сделать лист 1 нижним дочерним узлом корня.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
