А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 223
Текст из файла (страница 223)
Тогда мы можем использовать правило 5 с В = бп АГ = 2, Р = Р, Т = и1 и Х, Равным либо х, либо Гп что позволаег вывести ЫеД(бм 2, х) и ЫеДбп 2, у). Аналогично можно вывести такой же факт и для любой другой переменной, тип которой — либо 1пг, либо приводимый к нему. и 12.3.4 Выполнение программы Ра1а1оа Каждое множество правил Ра1а1ой определяет отношения для его !РВ-предикатов как функции отношений, которые задаются для ЕРВ-предикатов. Начнем с предположения о том, что множество 1РВ-предикатов пустое (т.е. для всех возможных аргументов !РВ-предикаты ложны).
Затем, многократно применяя правила, будем выводить новые факты, когда того от нас будут требовать правила программы. Когда этот процесс сойдется, выполнение программы завершится, а ее вывод образуют полученные 1РВ-отношения. Этот процесс формализуется следующим алгоритмом, подобным итеративным алгоритмам, рассматривавшимся в главе 9. 1089 !2.3, Логическое представление потока данных Алгоритм 12.15. Простое вычисление программ Ра!а1о8 Вход: программа Ра!а!о8 и множества фактов для каждого ЕРВ-предиката. Выход: множества фактов для каждого 1РВ-предиката. Метод: пусть для каждого предиката р в программе ˄— отношение фактов, истинных для данного предиката.
Если р — ЕРВ-предикат, то Л является множеством фактов, задаваемых этим предикатом. Если же р — 1РВ-предикат, мы вычисляем Л, выполняя алгоритм, приведенный на рис. 12.16. и (ог (каждый 1РВ-предикат р) Лр —— О; зтЫ!е (имеются изменения в Л ) ( рассмотрим все возможные подстановки констант вместо переменных во всех правилах; определим для каждой подстановки, являются ли все подцепи тела истинными, используя текущее множество Л„ для определения истинности ЕРВ- и 1РВ-предикатов; 11 (подстановка делает тело правила истинным) добавляем заголовок в Лч, где д — предикат заголовка; Рис.
! 2. ! 6. Вычисление программы Ра!а!оя Пример 12,1б. Программа в примере 12.12 вычисляет пути в графе. Чтобы применить к ней алгоритм 12.15, начнем с ЕРВ-предиката еИ8е, выполняющегося для всех ребер графа, и пустого отношения для предиката рай.
На первом шаге правило 2 ничего нам не дает, поскольку факты рай пока что отсутствуют. Однако правило 1 заставляет все факты еда стать фактами рай. Иначе говоря, после первого цикла мы знаем, что рай (а, 6) истинно тогда и только тогда, когда существует ребро от а до 6. На втором шаге правило 1 не дает новых фактов, поскольку ЕРВ-отношение е~фе никогда не изменяется. Однако теперь правило 2 позволяет нам собрать по два пути длиной 1 для образования путей длиной 2, т.е. после второго цикла рай (а, Ь) истинно тогда и только тогда, когда от а к 6 существует путь длиной 1 или 2. Аналогично на третьем шаге комбинируются пути длиной 2 или менее для получения всех путей длиной не более 4. На четвертом шаге выполняется поиск путей длиной до 8, и в общем случае после 1-го шага рай (а, 6) истинно тогда и только тогда, когда существует путь от а в 6 длиной не более 2' и 1090 Глава 12.
Межпроцедурный анализ Инкрементное вычисление множеств Инкрементно могут быть решены и задачи потоков данных в формулировке с использованием теории множеств. Например, в случае достигающих определений определение может быть вновь открыто в пч 1В] на ~',-м цикле, только если оно было только что найдено в опт 1Р] некоторого предшественника Р базового блока В.
Причина, по которой мы не пытались инкрементно решать задачи потоков данных, заключается в эффекгивности реализации множеств при помощи векторов битов. В общем случае оказывается проще пройти по всем векторам, чем выяснять, является ли некоторый факт новым. 12.3.5 Инкрементное вычисление программ Ра1а!ор Возможно повышение эффективности алгоритма 12.15. Заметим, что новый 1РВ-факт на шаге 1 может быть открыт, только если он является результатом подстановки констант в правило, такое, что как минимум одна из подцелей становится фактом, открытым на предыдущем шаге 1 — 1.
Доказательство этого утверждения заключается в том, что если бы все факты подцелей были известны на шаге 1 — 2, то "новые" факты должны бы были быть открыты при помощи той же подстановки констант на шаге 1 — 1. Чтобы воспользоваться этим наблюдением, введем для каждого 1РВ-предиката р предикат пеи Р, который выполняется только для вновь открытых р-фактов из предыдущего шага. Каждое правило, которое содержит среди своих подцелей один или несколько 1РВ-предикатов, заменяется набором правил. Каждое правило в наборе образуется заменой на пеи Д ровно одного вхождения некоторого 1РВ- предиката о в тело.
Наконец, для всех правил предикат заголовка 6 заменяется на пеиг1. Получающиеся в результате правила назовем инкречепгплой 4эорной. Отношения для каждого 1РВ-предиката р накапливают все р-факты, как и в алгоритме 12.15. В одном цикле делается следующее. 1. Правила применяются для вычисления предикатов пеи Р. 2. Из пезеР вычитается р, тем самым обеспечивается истинная новизна фактов в пезеР. 3. Добавляем в р все факгы из пезеР. 4.
Делаем для следующего цикла все отношения пен Х пустыми множествами. Эти идеи формализованы в алгоритме !2.18, но перед тем как перейти к нему, рассмотрим еше один пример. 1091 12.3. Логическое представление потока данных Пример 12.17. Вновь вернемся к программе Оа!а!о8 из примера 12.12. Соответствующая инкрементная форма правил приведена на рис. 12.17. Правило 1 не претерпело изменений, за исключением заголовка, поскольку 1ОВ-подцелей в теле этого правила нет. Однако правило 2 с двумя 1ОВ-подцелями превратилось в два разных правила. В каждом из них одно из вхождений рай в тело правила заменено на пеыРай. Вместе эти правила выражают идею, что как минимум один из двух соединяемых правилом путей должен быть открыт на предыдущем шаге.о 1) пеи Рай(Х, У): — ед8е(Х, У) 2а) пеыРай(Х, У): — рай(Х, Е) й певРай(Х, У) 2Ь) пенРай(Х, У): — пеюРагп(Х, Е) ь рай(а, У) Рис.
12.! 7. Инкрементные правила для программы Оа!а!ок для путей в графе Алгоритм 12.18. Инкрементное вычисление программы Оа!а!о8 Вход: программа Оа!а1о8 и множества фактов для каждого ЕОВ-предиката. ВыХОд: множества фактов для каждого 1ОВ-предиката. МЕТОД: пусть для каждого предиката р в программе Лт — отношение фактов, истинных для данного предиката. Если р — ЕОВ-предикат, то 77т является множеством фактов, задаваемых этим предикатом.
Если же р — 1ОВ-предикат, мы вычисляем В . Кроме того, пусть )т„,„р для каждого 1ОВ-предиката р является отношением из "новых" фактов для предиката р. 1. Преобразуем правила в описанную ранее инкрементную форму. 2. Выполняем алгоритм, приведенный иа рис. 12.18. 12.3.6 Проблематичные правила Ра1а1ои Имеются как некоторые правила Оа!а!о8, так и программы, которые технически не имеют смысла и не должны использоваться.
Две наиболее важные опасности заключаются в следующем. 1. Небезопасные правила. Это правила, в заголовках которых находятся переменные, не появляющиеся в теле таким образом, чтобы они могли принимать только значения из ЕОВ. 1092 Глава 12.
Межпроцедурный анализ 1ог (каждый ЮВ-предикат р) ( В =и; )1пеаР— О гереат ( рассмотрим все возможные подстановки констант вместо переменных во всех правилах; определим для каждой подстановки, являются ли все подцепи тела истинными, используя текущие множества В и г1„,„р для определения истинности ЕРВ- и 10В-предикатов; 11 (подстановка делает тело правила истинным) добавляем заголовок в 11„,„н, где и — предикат заголовка; 1ог (каждый предикат р) ( Лпеп~г = )1пе~еР Вр Рер = ))и 1-1 )1пееР1 ) цпб! (все В„,„р — пустые); Рнс. 12.18.
Вычисление программы Раеа!о8 2. Оестратифицированные программы. Это множества правил, в которых имеется рекурсия, включающая отрицание. Далее мы рассмотрим обе эти опасности. Безопасность правил Любая переменная, которая появляется в заголовке правила, должна иметься и в его теле. Более того, она должна находиться в подцели, которая является либо обычным 1РВ, либо ЕРВ-атомом.
Неприемлемо, если переменная находится только в атоме-отрицании или только в операторе сравнения. Данная стратегия применяется для того, чтобы избежать правил, которые приведут нас к выводу бесконечного количества фактов. Пример 12.19. Правило р(Х, У): — д(Я) а НОт г(Х) а Х ~ У небезопасно по двум причинам. Переменная Х находится только в отрицании подцели т (Х) и в сравнении Х ф 1'.
У находится только в сравнении. Следствием этого является то, что предикат р истинен для бесконечного количества пар (Х, У), лишь бы г (Х) было ложно, а У отличалось от Х. П 1093 12.3. Логическое представление потока данных Стратифнцнрованный Па1а!ои Чтобы программа имела смысл, рекурсия н отрицание должны быть разделены.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
