Генерирование команд по ПОЛИЗу

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

Алгоритм генерации команд состоит в том, что строка ПОЛИЗа просматривается один раз слева направо и при встрече операндами (идентификаторами или константами) их имена (символические значения, адреса) заносятся в стек. При встрече с оператором из таблицы выбирается соответствующая ему кодовая продукция. В нее подставляются имена (адреса) операндов, извлеченные из стека, а так же сформированное имя (адрес) результата. Последнее имя замещает операнды данного оператора в стеке, а сформированная продукция помещается в выходной файл. Ниже все примеры даются с использованием языка ассемблера для IBM PC (процессор Intel 8x86). Если Вы еще не знакомы с этим языком, то надеемся, что комментарии к командам позволят понять их смысл.

Пример 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)

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

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

Поиск по сайту: