Пример 7.3.

На рис. 7.2 показан пример генерирования команд для уже известной нам строки ПОЛИЗа AB@CD*++.

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

ПОЛИЗ является прекрасной иллюстрацией для внутренней (промежуточной) формы представления исходной программы. Алгоритмы интерпретации ПОЛИЗа и генерации команд по ПОЛИЗу предельно просты, но с точки зрения машинно–независимой оптимизации эта форма не совсем удобна. Идеальными здесь являются представления бинарных операций в виде тетрад (четверок):

< оператор>, < операнд ₁>, < операнд ₂>, < результат>,

где < операнд ₁> и < операнд ₂> специфицируют аргументы, а < результат> – результат выполнения оператора над аргументами. Таким образом, A*B мы могли бы представить, как

*, A, B, M,

где M – некоторая временная переменная, которой присваивается результат вычисления A*B. Аналогично A*B+C*D представляется в виде следующей последовательности тетрад:

*, A, B, M1

*, C, D, M2

+, M1, M2, M3

Важно отметить, что в отличии от обычной инфиксной записи тетрады располагаются в том порядке, в котором они должны выполняться. Унарные операторы также оформляются в виде тетрад, но < операнд ₂> остается в них пустым. Так, вместо -A появится тетрада “-, A,, M”, что означает “присвоить M значение -A”. Унарный минус, также как и в ПОЛИЗе, мы могли бы заменить другим символом (кодом), чтобы отличать его от бинарного.

Кроме традиционной арифметики в виде тетрад можно представить и любой другой оператор, имевший место в польской записи. Оператор присваивания A: =B представим в виде тетрады “: =, B,, A ”, а оператор УПЛ запишется в виде тетрады “ УПЛ, < выр>, < m>, ”, где < m> – номер тетрады, на которую будет осуществляться переход, если значение логического выражения (< выр>) – равно нулю (ложно).

К недостаткам тетрад можно отнести большое количество временных переменных, требующих описания. Эти проблемы полностью отпадают при использовании триад (троек), которые имеют следующую форму:

< оператор> < операнд ₁>, < операнд ₂>

В триаде нет поля для результата. Если позднее какой–либо операнд окажется результатом данной операции, то он будет непосредственно на нее ссылаться (на операцию, а точнее соответствующую триаду). Например, выражение A+B*C будет представлено следующим образом:

(1) * B, C

(2) + A, (1)

Здесь (1) – ссылка на результат первой триады, а не константа, равная 1. Выражение 1+B*C будет записываться так:

(1) * B, C

(2) + 1, (1)

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

Достоинства использования тетрад и триад с точки зрения машинно–независимой оптимизации по сравнению с ПОЛИЗом очевидны. Представляя их в виде таблицы (односвязного или двухсвязного списка), тетрады или триады можно легко переставлять или удалять “лишние”.