Проектирование трансляторов

└──┘ └───┘

Дисплей Стек


Рис. 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)+

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: