Реферат: Проектирование трансляторов
└───┘ └───┘ └───┘ .
end.
(1) (2) (3)
Рис. 20.2 Схема распределения памяти под переменные в раз-
личные моменты в программе на языке с блочной структурой
На рис. 20.2 показаны "моментальные снимки" стека фрагмента
программы во время прогона.
Часть стека, соответствующую определенному блоку, называют
РАМКОЙ стека. Считается, что указатель стека показывает на его
первый свободный элемент.
Кроме указателя стека, требуется также указатель на дно те-
кущей рамки (УКАЗАТЕЛЬ РАМКИ). При входе в блок этот указатель
устанавливается равным текущему значению указателя стека. При вы-
ходе из блока сначала указатель стека устанавливается равным зна-
чению, соответствующему включающему блоку.
Указатель рамки включающего блока может храниться в нижней
части текущей рамки стека, образуя часть статической цепи или
(как мы будем считать) массива, который называется ДИСПЛЕЕМ.
Его можно использовать для хранения во время прогона указа-
телей на начало рамок стека, соответствующих всем текущим блокам
(рис. 20.3).
│ │
│ │
│ │
│ │ ├───┤
│ │ │ q │
│ │ ├───┤
│ │ │ p │
│ │ /───> ├───┤
│ │ / │ │
├──┤ / │ Y │
│ │──/ ├───┤
├──┤ │ │
│ │─────────> │ X │
└──┘ └───┘
Дисплей Стек
Рис. 20.3 Схема связи Дисплея и стека во время выполнения
без учета динамически выделяемой памяти
Это несколько упрощает перенастройку указателя рамки при вы-
ходе из блока.
Если бы вся память была статической, адреса времени прогона
могли бы распределяться во время компиляции, и значения элемен-
тов дисплея также были бы известны во время компиляции.
Рассмотрим следующий отрезок программы на языке Алгол-60:
...
begin int n; read(n);
[1:n] int numbers;
real p;
begin real x,y;
...
Место для numbers должно выделяться в первой рамке стека, а
для x и y - в рамке над ней. Но во время компиляции неизвестно,
где должна начинаться вторая рамка, так как не известен размер
чисел.
Одно из решений в этой ситуации - иметь два стека: один для
статической памяти, распределяемой в процессе компиляции, а дру-
гой - для динамической памяти, распределяемой в процессе прогона.
Однако этого обычно не делают, возможно, из-за тех проблем, кото-
рые возникают в связи с наличием более чем одного увеличивающего-
ся и уменьшающегося стека во время прогона.
Другое решение заключается в том, чтобы при компиляции выде-
лять статическую память в каждом блоке в начале каждой рамки, а
при прогоне - динамическую память над статической в каждой рамке.
Это значит, что когда происходит компиляция, мы все еще не знаем,
где начинаются рамки (кроме первой), но можем распределять стати-
ческие адреса относительно начала определенной рамки. При прого-
не точный размер рамок, соответствующих включающим блокам, извес-
тен, так что при входе в блок нужный элемент дисплея всегда мож-
но установить так, чтобы он указывал на начало новой рамки (рис.
20.4).
│ Рамка 2
│ │ │
│ │ │
│ │ /
├───────┤ \
│ y │ Динами- │
├───────┤ │
│ x │ ческая │
/───> ├───────┤ │
│ │ / │ Числа │ память > Рамка 1
│ │ / │ │ │
├─────┤ / ├───────┤ - - - - │
│ │/ │ p │ Стати- │
├─────┤ ├───────┤ ческая │
│ │──\ │ n │ память │
└─────┘ \────> └───────┘ /
Дисплей Стек
Рис. 20.4 Схема связи Дисплея и стека во время выполнения с
учетом динамически выделяемой памяти
На этом рисунке массив занимает только динамическую память.
Однако некоторая информация о массиве обычно известна во время
компиляции, например, его размерность (а следовательно, и число
границ - две на каждую размерность), и при выборке определенного
элемента массива она может потребоваться. Во многих языках сами
границы могут быть не известны при компиляции, но почти наверня-
ка мы знаем их число, и для значений этих границ можно выделить
статическую память. Тогда мы вправе считать, что массив состоит
из статической и динамической частей. Статическая часть массива
может размещаться в статической части рамки, а динамическая - в
динамической. Кроме информации о границах, в статической части
может храниться указатель на сами элементы массива. Модифицируем
рис. 20.4 в рис. 20.5 с учетом этих особенностей.
│ Рамка 2
│ │ │
│ │ │
│ │ /
├────────┤ \
│ y │ Динами- │
├────────┤ │
│ x │ ческая │
/───> ├────────┤ │
│ │ / │Элемен- │ часть > Рамка 1
│ │ / │ты чисел│ │
├─────┤ / ┌─> ├────────┤ - - - - │
│ │/ │ │ p │ Стати- │
│ │ │ ├────────┤ │
│ │ │ │ Стат. │ │
│ │ └───│ часть │ ческая │
│ │ │ чисел │ │
├─────┤ ├────────┤ │
│ │──\ │ n │ часть │
└─────┘ \────> └────────┘ /
Дисплей Стек
Рис. 20.5 Схема связи Дисплея и стека во время выполнения с
учетом представления массивов в виде статической и динамической
частей
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
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23
