Вынесение инвариантных вычислений за пределы области цикла
Операция называется инвариантной в цикле, если ни один из ее операндов не изменяется во время работы этого цикла /1-3/.
Упростим выполнение преобразования этого типа в рамках лабораторной работы тем, что будем считать известным список переменных, инвариантных в оптимизируемом цикле. Тогда для выявления инвариантных операций (триад) можно воспользоваться алгоритмом распространения констант на LOOP-участке цикла. Поскольку вычисление значения инвариантной триады не всегда представляется возможным, вместо замены ее триадой типа С К _ будем помечать ее символом "С". Таблица Т значений переменных, используемая алгоритмом распространения констант, очевидно, будет в этом случае представлять собой просто список обнаруженных инвариантных переменных.
Пример.
Об'ектный код
INIT := I 1 Заданный список инвариантных
:= S 0 переменных: A,B.
LOOP + A B
:= K T3
* K I
+ S T5
:= S T6
INCR . . .
В процессе преобразований список инвариантных переменных пополнится переменной К, а триады Т3 и Т4 будут отмечены символом "C".После их вынесения за LOOP-участок получим:
INIT := I 1
:= S 0
+ A B
LOOP * T3 I
+ S T4
:= S T5
INCR . . .
Задание на лабораторную работу
Разработать процедуру оптимизации объектного кода, представленного в виде последовательности триад. Способ оптимизации и язык программирования выбрать из таблицы 1 в соответствии с заданным вариантом.
|
|
|
Таблица 6.1.
| Номер варианта | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Код задания | 1п | 2п | 3п | 4п | 5п | 6п | 1с | 2с | 3с | 4с | 5с | 6с |
_______________________
Код задания состоит из двух компонент. Первая определяет вид оптимизирующего преобразования:
1-удаление общих подвыражений;
2-удаление мертвых переменных;
3-распространение констант;
4-удаление лишних переменных;
5-удаление индуктивных переменных;
6-вынесение инвариантных вычислений за пределы цикла;
вторая-язык программирования: П-паскаль, С-си.
Содержание отчета
6.3.1.Постановка задачи.
6.3.2.Спецификация процедуры.
6.3.3.Текст программы.
6.3.4.Описание тестовых примеров.
6.3.5.Распечатка результатов.
ЛАБОРАТОРНАЯ РАБОТА № 7 ТРАНСЛЯЦИЯ ВЫРАЖЕНИЙ
Цель работы: изучение методов трансляции выражений в польскую инверсную запись (ПОЛИЗ).
Теоретические сведения
В настоящее время широко используется в трансляторах метод трансляции выражений, основанный на использовании ПОЛИЗ, названный так в честь польского математика Я. Лукашевича.
|
|
|
Эта запись обладает следующими свойствами:
1. Операнды в ПОЛИЗ располагаются в том порядке, что и в обычной (инфиксной) записи.
2. Знаки операций встречаются в том порядке, в котором нужно выполнить соответствующие действия.
3. Знак каждой операции записывается после соответствующих операндов.
Например, выражение (1) в ПОЛИЗ представляется выражением (2):
a + Ь * с – d / ( а + Ь ) (1)
а Ь с * + d а Ь + / - (2)
Перевод простых арифметических и логических выражений в ПОЛИЗ.
Известно несколько методов получения ПОЛИЗ. Обзор различных методов приведен в [1]. Один из наиболее аффективных методов предложен в 1960 г. голландским ученым Е.В.Дейкстрой [2]. Этот метод основан на использовании стека с приоритетами, позволяющего изменить порядок следования знаков операций в выражении так, что получается ПОЛИЗ. Простейший вариант этого метода применим только к простым арифметическим и логическим выражениям, содержащим простые переменные, знаки арифметических и логических операций, знаки операций отношения и круглые скобки.
|
|
|
Каждому ограничителю, входящему в выражение, присваивается приоритет. Для знаков операции приоритеты возрастают в порядке, обратном старшинству операций. Скобки имеют низший приоритет.
Арифметическое или логическое выражение рассматривается как входная строка символов. Входная строка рассматривается слева направо. Операнды переписываются в выходную строку, а знаки операций помещаются вначале в стек операций.
Если приоритет входного знака равен нулю или больше приоритета знака, находящегося в вершине стека, то новый знак добавляется к вершине стека. В противном случае из стека "выталкивается" и переписывается в выходную строку знак, находящийся в вершине, а также следующие за ним знаки с приоритетами большими или равными приоритету входного знака. После этого входной знак добавляется к вершине стека.
Особенности имеет лишь обработка скобок. Открывающаяся круглая скобка, имеющая "особый" приоритет нуль, просто записывается в вершину стека и не выталкивает ни одного знака. В то же время ее не может вытолкнуть ни один знак, кроме закрывающей скобки.
Закрывающая скобка имеет приоритет 1, не превосходящий приоритет любой операции. Поэтому появление закрывающей скобки вызывает выталкивание всех знаков до ближайшей открывающей скобки включительно. В стек закрывающая скобка не записывается. Открывающая и закрывающая скобки как бы взаимно уничтожаются и в выходную строку не переносятся.
|
|
|
После просмотра всех символов входной cтроки происходит выталкивание всех оставшихся в стеке символов и дописывание их к выходной строке.
Пример 1. Перевести в обратную польскую запись выражение
a + Ь * c – d / ( а + Ь )
Решение показано в табл.7.1.
Таблица 7.1
Дата добавления: 2019-02-12; просмотров: 261; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!