Материалы представленные на сайте исключительно с целью ознакомления пользователям Интернета и не преследуют коммерческих целей или нарушение авторских прав.
© 2018 - 2024
Абстрактный пустой оператор – это оператор, который «ничего не делает, ничего не меняет». Можно говорить о пустом операторе присваивания, либо пустом условном операторе, либо пустом операторе цикла. Но абстрактный пустой оператор лучше всего представлять себе, как пустой блочный оператор – блочный оператор, не содержащий ни одного оператора. Абстрактный пустой оператор будем обозначать EMPTY.
Пример 39. Следующий оператор присваивания не изменяет состояния памяти
X = X
Но вряд ли стоит этот оператор отождествлять с абстрактным пустым оператором, поскольку данное присваивание, если его не удалить, обращается к памяти и может потребовать регистр.
Пустой блочный оператор не обращается ни к какой памяти и, в зависимости от языка программирования FORTPAN, PASCAL или C, может иметь вид
CONTINUE
BEGIN
END
{
}
Можно считать, что EMPTY – это и есть пустой блочный оператор.
От языка следует потребовать, чтобы пустой блочный оператор не изменял состояние памяти программы и «не менял передачи управления».
Блочный оператор – имеет синтаксис скобок и содержит конкатенацию каких-либо операторов.
Пустой оператор присваивания. Это оператор присваивания, который не меняет состояния памяти. Например,
x = x
Аксиома. Если в программе пустой оператор присваивания заменить пустым блочным оператором EMPTY, то получится программа, эквивалентная исходной.
Пустой условный оператор – это условный оператор, у которого на ветках стоят пустые операторы.
IF P THEN
EMPTY
ELSE
EMPTY
ENDIF
или
IF P THEN
EMPTY
ENDIF
Аксиома. Если в программе пустой условный оператор заменить пустым блочным оператором EMPTY, то получится программа, эквивалентная исходной.
Пустой оператор цикла – это либо цикл с пустым заголовком, либо цикл с пустым телом. (Под оператором цикла понимается цикл DO языка ФОРТРАН).
Цикл с пустым телом – это оператор цикла с конечным числом итераций, у которого тело цикла – пустой оператор.
Цикл с пустым заголовком – это оператор цикла с нулевым количеством итераций.
Аксиома. Если в программе цикл с пустым заголовком заменить пустым блочным оператором EMPTY, то получится программа, эквивалентная исходной.
Отметим, что для циклов с пустым телом используются языки программирования, удовлетворяющие одной из следующих двух аксиом.
Аксиома. Если в программе цикл с пустым телом заменить пустым блочным оператором EMPTY, то получится программа, эквивалентная исходной.
Аксиома. Если в программе цикл с пустым телом заменить присваиванием счетчику цикла значения последней итерации, то получится программа, эквивалентная исходной.
Для привычных для нас языков программирования семантика соответствующих операторов обеспечивает выполнение этих аксиом пустых операторов.
Абстрактный пустой оператор можно формально определить следующим свойством
Аксиома (об удалении пустого оператора). Предположим, что пустой оператор входит в конкатенацию в блочном операторе и не является единственным оператором этого блока. Пусть в управляющем графе программы на этот оператор ведет только одна дуга, определенная конкатенацией (нет передач управления на метку этого оператора). Тогда удаление этого оператора приводит к программе, эквивалентной исходной.
Вставка пустого оператора является преобразованием, обратным к удалению. Поэтому условие вставки можно сформулировать следующим образом.
Теорема 25 . (о вставке пустого оператора). Если после вставки пустого оператора его удаление является эквивалентным преобразованием, то вставка является эквивалентным преобразованием.
Доказательство очевидно.
Замечание. При вставке нового оператора присваивания следует обратить внимание на корректность. Нельзя вставить оператор с неописанной меткой или с меткой, которая уже существует у некоторого оператора.
Теорема 26. (о замене оператора присваивания пустым оператором). Предположим, что генератор оператора присваивания не используется никакими использованиями, т.е. в графе информационных зависимостей из этого генератора нет дуг. Тогда этот оператор присваивания можно заменить пустым оператором (сохранив метку, если такая была) и новая программа будет эквивалентна исходной.
Доказательство вытекает из определения эквивалентности программ.
Теорема 27. (о замене оператора присваивания пустым оператором). Пустой оператор можно заменить оператором присваивания, генератор которого нигде не используется (сохранив метку, если такая была) и новая программа будет эквивалентна исходной.
Доказательство вытекает из предыдущей теоремы.
Теорема 28 . (об удалении оператора присваивания). Предположим, что оператор присваивания входит в блочный оператор и не является единственным оператором этого блока. Предположим, что на этот оператор ведет только одна передача управления, определенная конкатенацией, и из этого оператора ведет только одна передача управления (тоже определенная конкатенацией). Предположим, что генератор этого оператора присваивания нигде не используется. Тогда удаление этого оператора приводит к программе, эквивалентной исходной.
Доказательство вытекает из теоремы об удалении пустого оператора и теоремы о замене присваивания пустым оператором.
Вставка оператора является преобразованием, обратным к удалению. Поэтому условие вставки можно сформулировать следующим образом.
Теорема 29 . Если после вставки оператора присваивания его удаление является эквивалентным преобразованием, то и вставка является эквивалентным преобразованием.
Доказательство очевидно.
Замечание. При вставке нового оператора присваивания следует обратить внимание на корректность. Нельзя вставить оператор с неописанной меткой или с меткой, которая уже существует у некоторого оператора.
Теоремы об удалении/вставке оператора присваивания можно очевидным образом обобщить на случай фрагмента программы.
Теорема 30 . (об удалении фрагмента программы). Предположим, что фрагмент программы входит в блочный оператор и этот блок содержит еще хотя бы один оператор. Предположим, что у этого фрагмента есть единственный вход и единственный выход и они определяются конкатенацией. Предположим, что из вхождений этого фрагмента не выходят дуги истинной информационной зависимости (то есть генераторы этого фрагмента не используются за его пределами). Тогда удаление этого оператора приводит к программе, эквивалентной исходной.
Теорема 31 . Если после вставки фрагмента программы его удаление является эквивалентным преобразованием, то и вставка является эквивалентным преобразованием.
Пример 40. Фрагмент программы
T = A+B
X = T+C
Y = T-C
write(Y)
равносилен следующему
T = A+B
Y = T-C
write(Y)
Конец примера.
Пример 41. Фрагмент программы
DO 99 I = 1, N
IF (X > N) goto 88
T = I*A
X = T+C
Y = T-C
99 write(Y)
НЕ равносилен следующему
DO 99 I = 1, N
IF (X > N) goto 88
T = I*A
Y = T-C
99 write(Y)
(Из генератора удаляемого оператора выходит дуга информационной зависимости).
Конец примера.
Пример 42. Фрагмент программы
IF (X > N)
D = T+C
T = I*A
Y = T-C
99 write(Y)
НЕ равносилен следующему
IF (X > N)
T = I*A
Y = T-C
99 write(Y)
поскольку удаляемый оператор принадлежит фрагменту с двумя входами. Удаление оператора меняет зону действия условного оператора.
Конец примера.
Дата: 2018-12-21, просмотров: 453.