Проектирование трансляторов
Дисплей Стек
Рис. 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)+