Реферат: Проектирование трансляторов
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
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 Замечания по поводу "разреженных" массивов
В некоторых случаях, при хранении массивов по схеме векто-
ров Айлифа или подобной ей схеме с использованием дескрипторов
можно избежать хранения пустых, тривиальных или незаданных значе-
ний элементов. В этих случаях можно рассматривать пару "информа-
ционный элемент" - "значения индексов" как элемент информационно-
го множества, а задание значения (нетривиального) элементу масси-
ва - как пополнение множества, а задание неопределенного (или
тривиального) значения - как удаление элемента из множества.
Представление таких "неполных" (или "разреженных") массивов
реализуется как представление множеств.
3. ОРГАНИЗАЦИЯ ПАМЯТИ ВО ВРЕМЯ ТРАНСЛЯЦИИ
3.1 Проблемы распределения памяти
Распределение памяти для определенных программистом перемен-
ных в языках высокого уровня обычно бывает простым. Часто ло-
кальные переменные размещаются в памяти непосредственно после
Страницы: 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
