 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
ИСКЛЮЧЕНИЕ ОБЩИХ ПОДВЫРАЖЕНИЙ
Сразу оговоримся, что общие подвыражения должны быть идентичными, иначе машина вряд ли их обнаружит, а также они должны содержаться в одном операторе. Например, в программе
X:=A*(B - C); B:=B / 2; Y:=A*(B - C - 100);
мы не сможем исключить одинаковые элементы матрицы тетрад, соответствующие подвыражению B-C, поскольку значение B изменяется между вычислениями двух выражений.
Надо также учесть тот факт, что в большинстве языков программирования есть возможность написать собственные программы обработки прерываний, которые способны изменить значения переменных в любой момент времени. Это может привести к тому, что два подвыражения будут неэквивалентными, даже в случае их расположения в одном операторе.
Рассмотрим работу алгоритма исключения общих подвыражений на конкретном примере. Пусть нам задан следующий фрагмент программы:
B:=A; A:=C*D*(D*C+B);
Матрица тетрад для этого фрагмента представлена на рис. 7.1 а.
Алгоритм исключения общих подвыражений может быть следующим:
1). Упорядочить операнды симметричных операций в лексикографическом порядке, проверяя каждый элемент и меняя их местами, если они не упорядочены (в нашем примере изменяются только тетрады с номерами 3 и 4).
2). Найти границы операторов - в данном случае конец каждого блока характеризуется тетрадой с операцией присваивания - ‘ := ’. После шагов 1) и 2) матрица примет вид, представленный на рис. 7.1 б.
3). Найти общие подвыражения (совпадающие тетрады) и исключить одно из них (в нашем примере совпадают тетрады 2, 3 и мы исключаем третью тетраду, соединяя в цепочку тетрады с номерами 2 и 4). Если одинаковых тетрад не обнаружено перейти к пункту 6) алгоритма.
4). В результирующей матрице отразить исключение элемента, изменив ссылки на его результат (в нашем случае все ссылки к M2 меняются ссылками к M1). После шагов 3) и 4) мы получим матрицу представленную на рис. 7.1 в).
5). Повторить шаги 1) - 4) алгоритма.
6). Исключить из таблицы идентификаторов все элементы временной памяти, которые нам больше не нужны (в рассматриваемом примере элемент M2).
Поиск по сайту: