В.А. Овчинников, Г.С. Иванова
4
Для контекстно свободных оптимизирующих преобразований
условия допустимости тождественно истинны. С точки зрения про-
стоты реализации контекстно свободные оптимизирующие преобра-
зования представляют наибольший интерес для практики.
Примером контекстно свободного преобразования может слу-
жить замена операции сравнения множеств, записанной в виде
1
2
i
X X x
, на операцию
1
2
\
i
X x X
. Здесь и далее «
» — символ
операции конкатенации.
Контекстно зависимым преобразованием является замена
2
1
\
X X X
на
2
2
\
i
X X x
, которая может быть выполнена, если
перед определением
X
2
как
1
\
X X
в алгоритме осуществляется опе-
рация
1
1
i
X X x
.
В ряде случаев, в том числе при ориентации на асимптотические
оценки вычислительной сложности, эффективность трансформации
алгоритма может быть доказана посредством анализа заменяемого и
заменяющего фрагментов при синтезе последнего. Такими преобра-
зованиями являются обе указанные выше замены.
Широкое применение способов снижения вычислительной слож-
ности требует создания библиотеки конкретных, часто встречающих-
ся оптимизирующих преобразований и их формализации. Набор
формальных описаний оптимизирующих преобразований позволит
создать средство их автоматического или автоматизированного вы-
полнения — оптимизатор.
Для автоматического выполнения оптимизирующих преобразо-
ваний необходимо:
• определить в алгоритме фрагмент, аналогичный заменяемому
данного оптимизирующего преобразования;
• проверить выполнение условий контекстной зависимости;
• интерпретировать заменяющий фрагмент;
• оценить эффективность трансформации алгоритма;
• заместить найденный фрагмент полученным.
Проверку наличия в алгоритме фрагмента — аналога заменяемо-
го данного оптимизирующего преобразования — будем называть
условием существования.
Таким образом, формальное описание оптимизирующего преоб-
разования должно позволять по описанию алгоритма в операциях над
графами и/или множествами проверять указанные выше условия и в
случае положительного исхода конструировать заменяющий фраг-
мент по его синтаксическому описанию.
Формальное описание оптимизирующих преобразований и
правил трансформации алгоритмов.
Формальное описание
опти-
мизирующего преобразования должно задавать синтаксис заменяе-
