Реферат: Проектирование трансляторов
боте с текущим блоком. Именно значение этого второго указателя
при выходе из блока и дает объем статического рабочего стека,
включаемого в соответствующую рамку.
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┌─┬─┬─┬─┬─┬─┬───┬────┬─┬─┬─┬─┬─┬─┬───┬────┬─┬─┬─┬─┬─┬─┬────┬───┐
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
