Теория языков программирования методов трансляции (стр. 25 )

(а) Константа 0 нейтральна относительно сложения. Нейтрально и любое выражение, имеющее значение 0, Например, a - a, a * 0, (-a) + a.

(б) Константа 1 нейтральна относительно умножения.

(в) Логическая константа истина нейтральна относительно конъюнкции (т. е. a Ù истина = a для всех a).

(г) Логическая константа ложь нейтральна относительно дизъюнкции (т. е. a Ú ложь = a для всех a).

Если A – множество алгебраических законов, будем говорить, что выражение a эквивалентно выражению b относительно A (и писать a ºA b), если a можно преобразовать в b, применяя только алгебраические законы A.

Пример. Рассмотрим выражение

A * (B * C) + (B * A) * D +A * E.

С помощью ассоциативного закона умножения можно записать A*(B*C) в виде (A*B)* C. С помощью коммутативного закона умножения можно записать B*A в виде A*B. Применяя дистрибутивный закон, все выражение можно записать

(A * B)* (C + D) +A * E.

Наконец, применяя ассоциативный закон к первому слагаемому, затем дистрибутивный закон, можно записать выражение как

(A * (B * (C + D) + E).

Таким образом, это выражение эквивалентно исходному относительно ассоциативного, коммутативного и дистрибутивного законов умножения и сложения. Одного оно вычисляется только двумя умножениями и двумя сложениями, в то время как для исходного требовалось пять умножений и два сложения.

Определение эквивалентности относительно множества алгебраических законов A можно распространить и на блоки. Будем говорить, что блоки ℬ1 и ℬ2 эквивалентны относительно A (и писать ℬ1 ºA ℬ2), если существует такое выражение b Î v(ℬ2), что a ºA b, и обратно.

Пример. Если сложение коммутативно, то преобразование блоков, соответствующее этому алгебраическому закону, позволяет заменять в блоке оператор вида X A+B на оператор X B+A. Соответствующие преобразования графа позволяют заменить всюду в графе структуру

Если дан конечный набор алгебраических законов и соответствующие преобразования блоков, то для нахождения оптимального блока, эквивалентного данному, желательно было бы применять их вместе с топологическими преобразованиями. К сожалению, для конкретного набора алгебраических законов может не быть эффективного способа применения этих преобразований для нахождения оптимального блока.

Обычный подход к решению этого вопроса заключается в том, что алгебраические преобразования применяют в ограниченном виде, надеясь сделать больше «упрощений» выражений и выработать, возможно, большее число общих подвыражений. В типичной схеме bqa заменяется на aqb, если q - коммутативная бинарная операция, а a предшествует b при некотором лексикографическом упорядочении имен переменных. Если q - ассоциативная и коммутативная бинарная операция, то a1qa2q…qan можно преобразовав, располагая имена a1,…, an в лексикографическом порядке и группирую их слева направо.

Пример. Рассмотрим блок ℬ = (P, I, {Y}), где I = {A, B, C, D, E, F}, а P – последовательность операторов

X1 B-C

X2 A*X1

X3 E*F

X4 D*X3

Y X2*X3

Блок ℬ вычисляет выражение

Y = (A * (B – C)) * (D * (E * F)).

Граф для ℬ приведен на рис. 11.5.

Рис. 11.5. Граф для ℬ.

Предположим, что для ℬ генерируется программа на языке ассемблера и используются введенные нами ранее функции оценки. Применяя к ℬ коммутативные и ассоциативные преобразования для умножения проведем последовательное преобразование программы.

Полагая, что умножения ассоциативно, можно заменить два оператора в ℬ

X3 E*F

X4 D*X3

на три оператор

X3 E*F

X3¢ D*E

X4 X3¢*F

Теперь оператор X3 E*F бесполезен, и его можно удалить преобразованием T1. Затем с помощью ассоциативного преобразования можно заменить операторы

X4 X3¢*F

Y X2*X3

на

X4 X3¢*F

X4¢ X2* X3¢

Y X4¢* F

Оператор X4 X3¢*F теперь бесполезен, и его можно удалить. Таким образом имеем пять операторов

X1 B-C

X2 A*X1

X3¢ D*E

X4¢ X2* X3¢

Y X4¢* F

Если применить ассоциативные преобразования еще раз к третьему и четвертому оператору, получим

X1 B-C

X2 A*X1

X3² X2*D

X4¢ X3²*E

Y X4¢* F

Наконец, если предположить, что умножение коммутативно, можно переставить операнды второго оператора и получить блок ℬ¢:

X1 B-C

X2 X1* A

X3² X2*D

X4¢ X3²*E

Y X4¢* F

Граф для ℬ¢ изображен на рис. 11.6. Блок ℬ¢ имеет оценку 7, самую нижнюю возможную оценку для исходной программы.

Рис.11.6. Граф ℬ¢.

6.2.  Арифметические выражения

Входом для любого генератора кода служит блок, состоящий из последовательности операторов присвоения. Выходом – эквивалентная программа на языке ассемблера.

Желательно, чтобы результирующая программа на языке ассемблера была бы «хорошей» относительно некоторой оценки, такой, например, как число команд ассемблера или число обращений к памяти.

В данном разделе мы будем рассматривать эффективный алгоритм генерации кода для ограниченного класса блоков, а именно блоков, представляющих собой одно выражение без одинаковых операндов. Предположение об отсутствии одинаковых операндов, естественно, не реально, но часто бывает весьма хорошим первым приближением.

Блок, представляющий одно выражение, имеет только одну выходную переменную. Ограничение, состоящее в том, что выражение не имеет одинаковых операндов, эквивалентно требованию, чтобы граф для этого выражения был деревом.

Для удобства будем предполагать, что все операции бинарные. Код на языке ассемблера будем генерировать для машины с N сумматорами, где N ³ 1. Оценкой будет длина программы (т. е. число команд).

6.2.1.  Модель машины

Рассмотрим машину с N ³ 1 универсальными сумматорами и командами четырех типов.

Определение. Командой языка ассемблера называется цепочка символов одного из четырех типов:

LOAD M, A

STORE A, M

OP q A, M, B

OP q A, B, C.

В этих командах M – ячейка памяти, A, B, C – имена сумматоров (возможно одинаковые). OP q - это код бинарной операции q. Предполагается, что каждой операции q соответствует машинная команда 3) или 4). Эти команды выполняют следующие действия.

1)  LOAD M, A помещает содержимое ячейки памяти M на сумматор A.

2)  STORE A, M помещает содержимое сумматора A в ячейку памяти M.

3)  OP q A, M, B применяет бинарную операцию q к содержимому сумматора A и ячейки памяти M, а результат помещает на сумматор B.

4)  OP q A, B, C применяет бинарную операцию q к содержимому сумматоров A и B, а результат помещает на сумматор C.

Программой на языке ассемблера будем называть последовательность команд языка ассемблера.

Если P = I1; I2; …; In – программа, то можно определить значение vt(R) регистра R последней команды t (под регистром понимается сумматор или ячейка памяти):

1)  v0(R) равно R если R – это ячейка памяти, и не определено, если R – сумматор,

2)  если It – это LOAD M, A, то vt(A) = vt-1(M),

3)  если It – это STORE A, M, то vt(M) = vt-1(A),

4)  если It – это OP q A, B, C, то vt(С) = q vt-1(A) vt-1(R),

5)  если vt(R) не определено по 2) – 4), а vt-1(R) определено, то vt(R) = vt-1(R); в противном случае vt(R) не определено.

Команды LOAD и STORE передают значения с одного регистра на другой, оставляя их в исходном регистре. Операции перемещают вычисленное значение на сумматор, определенный третьим аргументом, не меняя остальных регистров. Будем говорить, что программа P вычисляет выражение a, помещая результат на сумматор A, если после последнего оператора из P сумматор A имеет значение a.

Пример. Рассмотрим программу на языке ассемблера с двумя сумматорами A и B, значения которых после каждой команды приведены в табл. 11.3.

Таблица 11.3.

	v(A)	v(B)
LOAD X, A ADD A, Y, B LOAD Z, B MULT B, A, A	X X + Y X + Y Z * (X +Y)	не определено не определено Z Z

Значение сумматора A в конце программы соответствует выражению Z*(X +Y). Таким образом, эта программа вычисляет Z * (X +Y), помещая результат на сумматор A.