Выделение памяти под рамку в процессе трансляции

1.2 Выделение памяти под рамку в процессе трансляции

Динамическая рабочая память должна распределяться во время

прогона, статическая же может распределяться во время компиляции.

Объем статической рабочей памяти, который должен выделяться каж-

дой рамке, определяться не рабочей памятью, требуемой в конце

каждого блока (обычно она является нулем), а МАКСИМАЛЬНОЙ рабо-

чей памятью, требуемой в любой точке внутри блока. Для статичес-

кой рабочей памяти эту величину можно установить в процессе ком-

пиляции, если в фазе распределения памяти мы ассоциируем с рабо-

чей стековой областью текущей рамки два указателя, причем один из

них указывает на текущую границу статической рабочей памяти, а

другой - на максимальный размер, до которого она выросла при ра-

боте с текущим блоком. Именно значение этого второго указателя

при выходе из блока и дает объем статического рабочего стека,

включаемого в соответствующую рамку.

2. ПРЕДСТАВЛЕНИЕ МАССИВОВ

2.1 Прямоугольные массивы

Простейшие массивы (одномерные) естественно представляются

векторами, т.к. они хорошо согласуются в том смысле, что для по-

лучения относительного адреса элемента массива в векторе надо вы-

честь нижнюю границу по измерению из индекса элемента.

Из многомерных массивов рассмотрим сначала прямоугольные. Их

также возможно представлять векторами. Для реализации выборки или

засылки в массив надо получить относительный адрес нужного эле-

мента в векторе по значениям индексов этого элемента.

Предполагая линейное расположение всех точек n-мерного прос-

транства (n - размерность), соответствующего массиву, мы можем

считать первые измерения старшими и тогда рядом располагаются

элементы, соседние по последнему измерению - так называемый

ПРЯМОЙ порядок, либо наоборот - ОБРАТНЫЙ порядок. Например, в

языке Алгамс поддерживается прямой порядок, в Фортране - обрат-

ный, а в АЛГОЛе-60 представление многомерных массивов никак не

фиксируется.

Когда в программе выбирается конкретный элемент массива, его

адрес внутри динамической части должен вычисляться в процессе

прогона. Рассмотрим массив:

[1:10,-5:5] int Table

Будем считать, что элементы записаны в лексикографическом

порядке индексов, т.е. элементы хранятся в следующем порядке:

Table[1,-5], Table[1,-4] ......... Table[1,5],

Table[2,-5], Table[2,-4] ......... Table[2,5],

.

.

.

Table[10,-5], ...................... Table[10,5]

Адрес конкретного элемента вычисляется как смещение по отно-

шению к базовому адресу (адресу первого элемента) массива:

ADDR(Table[I,J])=ADDR(Table[l1,l2])+(u2-l2+1)*(I-l1)+(J-l2)

Здесь l1 и u1 - нижняя и верхняя границы первой размерности

и т.д. и считается, что каждый элемент массива занимает единицу

объема памяти.

Для трехмерного массива соответствующая формула имеет вид:

ADDR(Table[I,J,K])=ADDR(Table[l1,l2,l3])+

(u2-l2+1)*(u3-l3+1)(I-l1)+

(u3-l3+1)*(J-l2)+K-l3

Выражение (ui-li+1) задает число различных значений, кото-

рые может принимать i-индекс.

Значение произведения (u2-l2+1)*(u3-l3+1) представляет со-

бой число различных пар значений, которые могут принимать второй

и третий индексы, а также расстояние между элементами массива,

отличающимися только на одну единицу в первом индексе.

Расстояние между элементами, отличающимися на 1 в i-индексе,

известно как i-й шаг. Так, в приведенном выше примере первый шаг

s1 состовляет (u2-l2+1)*(u3-l3+1). Второй шаг s2 равен (u3-l3+1).

Третий шаг s3 составляет 1.

Ясно, что вычисление адресов элементов массива в процессе

прогона может занимать много времени. Поэтому рекомендуется при

программировании по возможности избегать выборки из массивов,

особенно из многомерных. Тем не менее, шаги могут вычисляться

только один раз и храниться в статической части массива наряду с

границами. Такая статическая информация часто называется описате-

лем массива. В этой же части массива наряду с нижней и верхней

границами и шагом для каждой размерности может храниться указа-

тель на элементы массива. Нижняя и верхняя границы требуются для

проверки правильности нахождения индексов в пределах границ, а

шаги и нижние границы - при обращении к конкретным элементам мас-

сива.

2.2 Обращение к элементам массива с помощью векторов Айлифа

Айлиф разработал свой способ обращения к элементам массивов.

Этот способ требует для хранения массива больше памяти, но зато

обращение к элементу выполняется быстрее. Вместе с каждым масси-

вом хранится набор указателей. Так, например, массив, определен-

ный как

B[4:6,-2:1,0:1]

хранился бы в виде структуры, представленной ниже на рис.

20.6.

┌──────┐ ─ ─ ─ ─ i

С │ ──┼───────────────────────────> │ │ (0)

└──────┘ D ─ ─ ─ ─

│ │ (1)

─ ─ ─ ─

│ │ (2)

─ ─ ─ ─

│ │ (3)

┌───────┐

┌─────────────────────────────┼── │ 4

│ ├───────┤

│ ┌────────┼── │ 5

 │ │ ├───────┤

│ │ │ │ 6

│ │ └────┼──┘

│ │ │

 │ │ │ j

│ │ │

│ │ │

│ │ └──────┐

E │ F │ G │

┌─────┐ │ ┌─────┐ │ ┌─────┐ │

┌─────────┼─ │ │ ┌─────────┼─ │ │ ┌─────────┼─ │ │-2

│ ├─────┤ │ │ ├─────┤ │ │ ├─────┤ │

│ ┌─────┼─ │ │ │ ┌─────┼─ │ │ │ ┌─────┼─ │ │-1

│ │ ├─────┤ │ │ │ ├─────┤ │ │ │ ├─────┤ │

│ │ ┌─┼─ │<─┘ │ │ ┌─┼─ │<─┘ │ │ ┌─┼─ │<─┘ 0

│ │ │ ├─────┤ │ │ │ ├─────┤ │ │ │ ├─────┤

│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ 1

│ │ │ └───┼─┘ │ │ │ └───┼─┘ │ │ │ └───┼─┘

│ │ │ │ │ │ │ │ │ │ │ │

H┌─┬─┬─┬─┬─┬─┬───┬────┬─┬─┬─┬─┬─┬─┬───┬────┬─┬─┬─┬─┬─┬─┬────┬───┐

 │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │

k└─┴─┴─┴─┴─┴─┴───┴────┴─┴─┴─┴─┴─┴─┴───┴────┴─┴─┴─┴─┴─┴─┴────┴───┘

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Рис. 20.6 Схема обращения к элементам массива с помощью век-

торов Айлифа

 Пусть запись вида (B+5) означает содержимое по адресу B+5.

Тогда к элементу B[i,j,k] можно обратиться следующим образом:

(((C)+i)+j)+k

При этом выбирается содержимое ячейки C и к нему прибавляет-

ся значение индекса i, затем по полученному в результате этого

адресу выбирается содержимое, которое дает указатель на следую-

щий более низкий уровень, и т.д.

Важно отметить, что при данном способе обращения к элементу

массива не требуется выполнения операций умножения. Вместе с тем

в рассмотренном примере, кроме вектора для хранения массива, тре-

буется еще один вектор длины 3 и три вектора длины 4, и таким об-

разом, вместо 24 элементов требуется 39. Этот метод оказывается

наиболее экономичным, когда диапазоны изменения индексов увеличи-

ваются от первого к последнему. Наименее всего этот метод эффек-

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

В приведенном примере не производилось проверки корректнос-

ти индекса. Это может быть достигнуто путем хранения вместе с

каждым элементом вектора Айлифа граничной пары для соответствую-

щего индекса. Правда, в случае прямоугольного массива это могло

бы оказаться неэкономичным. У каждого из элементов векторов E,F и

G в рассматриваемом примере были бы одинаковые граничные пары.

Однако следует обратить внимание на то, что с каждым из этих эле-

ментов могли бы быть связаны и различные граничные пары, что да-

ло бы возможность, используя векторы Айлифа, обращаться к масси-

вам со значительно более сложной структурой.

Так, например, на рис. 20.7 показан набор векторов Айлифа,

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

хранятся в следующем порядке:

B[4,-1,-1] B[5,1,2] B[6,0,0]

B[4,-1, 0] B[5,2,2] B[6,0,1]

B[4,-1, 1] B[5,2,3] B[6,0,2]

B[4,-1, 2] B[5,3,2] B[6,0,3]

B[4, 0, 0] B[5,3,3] B[6,0,4]

B[4, 0, 1] B[5,3,4] B[6,0,5]

B[4, 0, 2] B[5,3,5]

B[4, 0, 3]

B[4, 0, 4]

B[4, 0, 5]

B[4, 0, 6]

┌─────┬─┬─┐

│ │4│6│

└──┼──┴─┴─┘ ─ ─ ─ ─ ─

└────────────────────────────> │ │

─ ─ ─ ─ ─

│ │

─ ─ ─ ─ ─

│ │

─ ─ ─ ─ ─

│ │

┌────┬──┬──┐

┌──────────────────────────────┼── │-1│ 0│

│ ├────┼──┼──┤

 │ ┌────────┼── │ 1│ 3│

│ │ ├────┼──┼──┤

│ │ │ │ 0│ 0│

│ │ └─┼──┴──┴──┘

 │ │ │

│ │ │

│ ─ ─ ─ ─ ─ ─ │ ┌─────┘

│ │ │<──┘ │

│ ┌─────┬──┬──┐ │

 │ ┌───┼─ │ 2│ 2│ │

┌─────┬──┬──┐ │ │ ├─────┼──┼──┤ ┌─────┬───┬──┐

┌─┼─ │-1│ 2│ │ │┌──┼─ │ 2│ 3│ ┌┼─ │ 0│ 5│

│ ├─────┼──┼──┤ │ ││ ├─────┼──┼──┤ │└─────┴───┴──┘

│ │ │ 0│ 6│<┘ ││ │ │ 2│ 5│ │

│ └───┼─┴──┴──┘ ││ └─┼───┴──┴──┘ │

│ │ ┌─┘│ │ │

│ │ │ ┌┘ ┌─┘ ┌────┘

│ │ │ │ │ │

│ │ │ │ │ │

┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐

│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │

└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘

Рис. 20.7 Пример векторов Айлифа для трехмерного массива

сложной структуры

2.3 Замечания по поводу "разреженных" массивов

В некоторых случаях, при хранении массивов по схеме векто-

ров Айлифа или подобной ей схеме с использованием дескрипторов

можно избежать хранения пустых, тривиальных или незаданных значе-

ний элементов. В этих случаях можно рассматривать пару "информа-

ционный элемент" - "значения индексов" как элемент информационно-

го множества, а задание значения (нетривиального) элементу масси-

ва - как пополнение множества, а задание неопределенного (или

тривиального) значения - как удаление элемента из множества.

Представление таких "неполных" (или "разреженных") массивов

реализуется как представление множеств.

Похожие работы

Программное обеспечение удалённого доступа к технической документации

Скачать

84334

30

0

... работы. В ходе работы над дипломным проектом разработан транслятор. Проблема создания такого транслятора является очень актуальной, т.к. многим пользователям САПР необходимо доступ к технической документацию, которую удобнее хранить на удаленных серверах в формате HTML. Поэтому степень положительного эффекта от выполнения дипломного проекта научно-исследовательского характера 1=6.5. В ...

Андрей Петрович Ершов (1931-1988)

Скачать

50249

0

1

... направления, активно развиваемого сейчас в разных коллективах и странах. Отталкиваясь от трансформационной модели смешанных вычислений и от своих работ в области трансляции и оптимизации программ, Ершов определяет концепцию трансформационной машины. Трансформационная машина есть абстрактное вычислительное устройство, выполняющее программы в некотором "сверхязыке", действиями которого являются ...

Программа–конструктор для построения МП–транслятора по его параметрам с последующей проверкой задаваемых пользователем цепочек

Скачать

36295

1

7

... 166, 16 Mb RAM, Windows 95 Вывод   В ходе разработки курсового проекта я ближе ознакомился с теорией МП- трансляторов, научился писать программы - конструкторы для построения МП – транслятора по его параметрам с последующей проверкой задаваемых цепочек, закрепил знания по системному программированию. Разрабатывая программу, я научился применять знания дискретной математике, что облегчает ...

Технологии проектирования в инженерных средах

Скачать

141647

0

0

... позволяет связывать твёрдотельные модели, сборки или чертежи, созданные с помощью SolidWorks 97, с файлами других приложений, что значительно расширяет возможности автоматизации процесса проектирования. С помощью технологии OLE можно использовать информацию, полученную в других приложениях Windows, для управления моделями и чертежами SolidWorks. Например, размеры модели могут быть рассчитаны в ...