АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

ИСКЛЮЧЕНИЕ ОБЩИХ ПОДВЫРАЖЕНИЙ

Читайте также:
  1. Выявление общих элементов в работе трех базальных комплексов
  2. Глава 1 Совокупность общих понятий системы налогообложения
  3. Глава 9 Структура общих способностей
  4. Графики постоянных, переменных и общих затрат
  5. Графики средних постоянных, средних переменных, средних общих и предельных затрат
  6. Доходы бюджета - поступающие в бюджет денежные средства, за исключением средств, являющихся в соответствии с Бюджетным Кодексом источниками финансирования дефицита бюджет.
  7. Исключение
  8. Исключение
  9. Кадастровые сведения являются общедоступными, за исключением кадастровых сведений, доступ к которым ограничен федеральным законом.
  10. Каков в общих чертах химический состав табачного дыма?
  11. Общее правило построения общих индексов.

 

Сразу оговоримся, что общие подвыражения должны быть идентичными, иначе машина вряд ли их обнаружит, а также они должны содержаться в одном операторе. Например, в программе

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).


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)