РАСПРЕДЕЛЕНИЕ ПАМЯТИ ВО ВРЕМЯ ТРАНСЛЯЦИИ
1. ДИСПЛЕЙ
1.1 Взаимодействие Дисплея и стека
После выяснения структуры (и значения) программы необходимо
выделить место в памяти для значений переменных и т.п. и помес-
тить соответствующие адреса, где это необходимо, в таблицу симво-
лов. Фаза распределения памяти почти не зависит от языка и маши-
ны и практически одинакова для подавляющего большинства языков,
имеющих блочную структуру и реализуемых на многих типичных ЭВМ.
Распределение памяти, по существу, заключается в отображении зна-
чений, появляющихся в программе, на запоминающем устройстве маши-
ны. Если допустить, что мы реализуем типичный язык с блочной
структурой, а машина имеет линейное запоминающее устройство, то
наиболее подходящим устройством, на котором мы будем базировать
распределение памяти, представляет стек или память магазинного
типа.
Ниже мы рассмотрим классическую структуру стека времени про-
гона для локального распределения памяти и покажем, как можно
произвести глобальное распределение памяти в отдельной области,
называемой "кучей".
В каждом компиляторе предусмотрена схема распределения памя-
ти, которая до некоторой степени зависит от компилируемого языка.
В Фортране память, выделенная для значений идентификаторов, ни-
когда не освобождается, так что здесь подходящей структурой для
нее является одномерный массив. Если считается, что массив имеет
левую и правую стороны, память можно выделять слево направо. При
этом применяется указатель, показывающий первый свободный эле-
мент в массиве. Например, в результате описания
INTEGER A,B,X,Y
выделяется память, как показано на рис. 20.1.
ЪДДДВДДДВДДДВДДДВДДДДДДДДДДДДДДД
і A і B і X і Y і
АДДДБДДДБДДДБДДДБДДДДДДДДДДДДДДД
^
і
Рис. 20.1 Схема выделения памяти в Фортране
Такая схема не учитывает тот факт, что рабочая память (па-
мять для промежуточных результатов) используется неоднократно и
весьма неэффективна (в смысле использования объема памяти) для
языка с блочной структурой.
В языке, имеющем блочную структуру, память обычно высвобож-
дается при выходе из блока, которому она выделена. В этом случае
оптимальным решением было бы разрешить указателю в вышеприведен-
ном примере отодвигаться обратно влево при высвобождении памяти.
Такой механизм распределения эквивалентен стеку времени прогона
или памяти магазинного типа, хотя принято показывать стек запол-
няющимся снизу вверх.
і і і і і і (1) begin real x,y
і і і і і і .
і і ГДДДґ ГДДДґ .
і і і d і і q і .
і і ГДДДґ ГДДДґ (2) begin int c,d
і і і c і і p і .
ГДДДґ ГДДДґ ГДДДґ .
і і і і і і end;
і і і і і і (3) begin int p,q
і Y і і Y і і Y і
ГДДДґ ГДДДґ ГДДДґ .
і і і і і і .
і і і і і і end;
і X і і X і і X і .
АДДДЩ АДДДЩ АДДДЩ .
end.
(1) (2) (3)
Рис. 20.2 Схема распределения памяти под переменные в раз-
личные моменты в программе на языке с блочной структурой
На рис. 20.2 показаны "моментальные снимки" стека фрагмента
программы во время прогона.
Часть стека, соответствующую определенному блоку, называют
РАМКОЙ стека. Считается, что указатель стека показывает на его
первый свободный элемент.
Кроме указателя стека, требуется также указатель на дно те-
кущей рамки (УКАЗАТЕЛЬ РАМКИ). При входе в блок этот указатель
устанавливается равным текущему значению указателя стека. При вы-
ходе из блока сначала указатель стека устанавливается равным зна-
чению, соответствующему включающему блоку.
Указатель рамки включающего блока может храниться в нижней
части текущей рамки стека, образуя часть статической цепи или
(как мы будем считать) массива, который называется ДИСПЛЕЕМ.
Его можно использовать для хранения во время прогона указа-
телей на начало рамок стека, соответствующих всем текущим блокам
(рис. 20.3).
і і
і і
і і
і і ГДДДґ
і і і q і
і і ГДДДґ
і і і p і
і і /ДДД> ГДДДґ
і і / і і
ГДДґ / і Y і
і іДД/ ГДДДґ
ГДДґ і і
і іДДДДДДДДД> і X і
АДДЩ АДДДЩ
Дисплей Стек
Рис. 20.3 Схема связи Ди9.zi$u
Текущая страница: 1
|
