Реферат: Распределение памяти
VAR_PART = VAR_PART*d2 + второй индекс (j)
VAR_PART = VAR_PART*d3 + третий индекс (k)
.....
VAR_PART = VAR_PART*dn + n-й индекс (m)
Информационные векторы
В некоторых языках верхняя и нижняя границы массивов известны
во время трансляции, поэтому компилятор может выделить память для
массивов и сформировать команды, ссылающиеся на элементы массива,
┌────┬────┬────┐
│ L1 │ U1 │ d1 │
├────┼────┼────┤
│ L2 │ U2 │ d2 │
│ . │ . │ . │ Описание массива
│ . │ . │ . │ A[L1:U1,...,Ln:Un]
│ . │ . │ . │
│ Ln │ Un │ dn │
├────┼────┴────┤
│ n │CONSTPART│
├────┴─────────┤
│ BASELOC │
└──────────────┘
Рис. . Информационный вектор для массива
используя верхние и нижние границы и постоянные значения d1,d2,..
.,dn. В других языках это невозможно т.к. границы могут
вычисляться во время счета. Поэтому нужен описатель для массива,
содержащий необходимую информацию. Этот описатель для массива
называется допвектор ( dope vector ) или информационный вектор.
Информационный вектор имеет фиксированный размер, который
известен при компиляции, следовательно, память для него может
быть отведена во время компиляции в области данных, с которой
ассоциируется массив. Память для самого массива не может быть
отведена до тех пор, пока во время счета не выполнится вход в
блок, и котором описан массив. При входе в блок вычисляются
границы массива и производится обращение к программе
распределения памяти для массивов. Здесь же вносится в
информационный вектор необходимая информация.
Какая информация заносится в информационный вектор? Для
предложенной выше n-мерной схемы нам как минимум нужны d2,...dn
и CONST_PART. Если перед обращением к массиву нужно проверять
правильность задания индексов, то следует также занести в
информационный вектор значения верхних и нижних границ.
5. Память для структур
Существует несколько альтернатив для определения новых
типов данных как структур, составленных из типов данных,
определенных ранее. Величины такого типа мы называем
структурными величинами. Существуют различные подходы к
реализации этих конструкций. Отличия обычно касаются следующих
вопросов:
Как выделять память для структурных величин?
Как строить структурные величины?
Как ссылаться на компоненту структурной величины?
Как освобождать память?
Записи по Хоору
Определение нового типа данных имеет вид
RECORD <идентификатор> ( <компонента>,
<компонента>, . . . , <компонента> )
где каждая компонента имеет вид
<простой тип> <идентификатор>
Причем <простой тип> является одним из основных типов языка -
REAL, INTEGER, POINTER и т.д. Здесь во время компиляции известны
все характеристики всех компонент, включая тип данных, на которые
могут ссылаться указатели. Во время счета не нужны описатели ни
для самой структуры, ни для ее компонент, причем может быть
сгенерирована эффективная программа.
Любая структурная величина с n компонентами может храниться в
памяти в виде:
┌──────────────┬──────────────┬─────────┬──────────────┐
│ Компонента 1 │ Компонента 2 │ ... │ Компонента n │
└──────────────┴──────────────┴─────────┴──────────────┘
Поскольку при компиляции известны все характеристики, то
известен также объем памяти, необходимый для каждой компоненты,
и, следовательно, компилятор знает смещение каждой компоненты
относительно начала структурной величины. Для упрощения сбора
мусора лучше всего присвоить номер каждому типу данных ( включая
типы, определенные программистом) и иметь описатель для каждого
указателя. Описатель будет содержать номер, описывающий тип
величины, на которую в данный момент ссылается указатель.
Память для указателей и их описателей может быть выделена
компилятором в области данных, с которой они связаны; это не
трудно, так как они имеют фиксированную длину. Для хранения
текущих значений структурных величин может быть использована
отдельная статическая область данных и специальная программа для
выделения памяти в этой области. В рассматриваемых языках нет
явного оператора для освобождения памяти, так что, когда память
исчерпана, система обращается к программе "сбора мусора".
Заметим, что для того, чтобы иметь возможность обнаружить мусор,
нужно знать, где расположены все указатели, включая те, которые
являются компонентами структурных величин.
Структуры PL/1
Более сложную конструкцию имеют структуры, в которых
компоненты могут сами иметь подкомпоненты. Пример таких
структур - структуры языка PL/1. Такая структура есть дерево,
узлы которого связаны с именами компонент, а концевые узлы
имеют значения данных.
Если бы возможность иметь подкомпоненты была бы
единственным различием между записями по Хоору и структурами
PL/1 не было бы существенной разницы во время выполнения
программы; можно было бы разместить все компоненты и
подкомпоненты так, чтобы каждая имела фиксированное смещение
относительно начала структуры и это смещение было бы известно во
время компиляции. Однако в языке PL/1 существует еще два
расширения. С целью экономии памяти атрибут CELL для компоненты
требует, чтобы все ее подкомпоненты непременно занимали одно и
тоже место в памяти. В любое заданное время только одна из
нескольких переменных может иметь значение. Присваивание значения
подкомпоненте приводит к тому, что подкомпонента, к которой
обращались ранее утрачивает свое значение.
Подобная возможность вызовет осложнения во время компиляции,
но в действительности не очень изменяет код готовой программы,
если только объектная программа не должна проверять при каждом
обращении к подкомпоненте, что значение подкомпоненты
действительно существует.
Для другого расширения требуются более сложные
административные функции во время выполнения программы. В PL/1
корневой узел структурного дерева или любая из подкомпонент могут
быть снабжены размерностями.
Так как выражения, которые определяют границы изменения
индексов, должны быть вычислены при выполнении программы, для
них, как и в случае массивов, следует употреблятъ опители, или
информационные векторы. Т.е. нам необходимы информационные
векторы для всех компонент имеющих размерность большую единицы.
Структуры данных по Стендишу
Следующий шаг в развитии - структуры данных, которые не
могут быть реализованы эффективно, но которые богаче и мощнее.
Структуры данных предложенные Стендишом изменяются во время
работы программы. Динамически могут изменяться не только
размерности компонент, но и число компопонент и их типы.
Обычно во время компиляции ничего не известно, а все делается
во время выполнения программы на основе описателей, которые
сами строятся в это же время.
Во время выполнения программы необходимо хранить описатель
для каждой структурной величины. Действительно, этот описатель
аналогичен набору элементов таблицы символов, используемому
