Теория языков программирования методов трансляции (стр. 39 )

Другое решение заключается в том, чтобы при компиляции выделять статическую память в каждом блоке в начале каждой рамки, а при прогоне – динамическую память над статической в каждой рамке. Это значит, что когда происходит компиляция, неизвестно, где начинаются рамки, но можно распределить статические адреса относительно начала определенной рамки. При прогоне точный размер рамок, соответствующих включающим блокам, известен, так что при входе в блок нужный элемент дисплея всегда можно установить так, чтобы он указывал на начало новой рамки (рис. 8.4).

						Рамка 2
		у
		х
		Числа		Динамическая часть		Рамка 1
		p		Статическая часть
		n
Дисплей	Стек

Рис. 8.4. Стек прогона для массива

В этой структуре массив занимает только динамическую память. Однако некоторая информация о массиве известна во время компиляции, например его размерность (а, следовательно, и число границ – две на каждую размерность), и при выборке определенного элемента массива она может потребоваться. В некоторых языках сами границы могут быть неизвестны при компиляции, но всегда известно их число, и для значений этих границ можно выделить статическую память. Тогда можно считать, что массив состоит из статической и динамической частей. Статическая часть массива может размещаться в статической части рамки, а динамическая – в динамической. Кроме информации о границах, в статической части может храниться указатель на сами элементы массива (рис. 8.5).

						Рамка 2
		у
		х
		Элементы чисел		Динамическая часть		Рамка 1
	p		Статиче
			Статическая часть чисел		ская часть
		n
Дисплей	Стек

Рис. 8.5. Модифицированный стек прогона для массива

Когда в программе выбирается конкретный элемент массива, его адрес внутри динамической памяти должен вычисляться в процессе прогона. Пусть имеется массив

int table[1:10, -5:5].

Будем считать, что элементы массива записаны в лексикографическом порядке индексов, т. е. элементы таблицы хранятся в следующем порядке:

table[1, -5], table[1, -4]………. table[1, 5],

table[2, -5], table[2, -4]………. table[1, 5],

.

.

.

table[10, -5], table[10, -4]………. table[10, 5].

Адрес конкретного элемента вычисляется как смещение по отношению к базовому адресу (адресу первого элемента) массива:

Здесь и - нижняя и верхняя границы первой размерности и т. д. и считается, что элемент массива занимает единицу объема памяти.

Выражение задает число различных значений, которые может принимать i-й индекс. Расстояние между элементами, отличающимися на единицу в i-м индексе, называется i-й шагом и обозначается . Пример шагов массива (рис. 8.6):

int N[1:5, 1:5, 1:5]

N[1,1,1] N[1,1,2]..N[1,1,5] N[1,2,1]… N[2,1,1] …N[5,5,5]
	s1
	s2
		s3

Рис. 8.6. Схема смещений

Если бы каждый элемент массива занимал объем памяти r, то эти шаги получили бы умножением всех вышеприведенных величин на r.

Ясно, что вычисление адресов элементов массива в процессе прогона может занимать много времени. Но шаги могут вычисляться только один раз и храниться в статической части массива наряду с границами. Такая статическая информация называется описателем массива.

Во многих языках все идентификаторы должны описываться в блоке, прежде чем можно будет вычислять какие-либо выражения. Отсюда следует, что рабочую память нужно выделять в конкретной рамке стека, над памятью, предусмотренной для значений, соответствующих идентификаторам (называемой стеком идентификаторов). Обычно статическая рабочая память выделяется в вершине статического стека идентификаторов, динамическая рабочая память – в вершине динамического стека идентификаторов.

В процессе компиляции статический стек идентификаторов растет по мере объявления идентификаторов. Вместе с тем, статический рабочий стек может не только увеличиваться в размерах, но и уменьшаться. Пример:

x=a+b´ c.

При вычислении выражения (a+b´ c) потребуется рабочая память, чтобы записать b´ c перед сложением. Ту же самую рабочую память можно использовать для хранения результатов сложения. Однако после осуществления операции присвоения этот объем памяти можно освободить, так как он уже не нужен.

Динамическая память должна распределяться во время прогона, статическая же распределяется во время компиляции. Объем статической рабочей памяти, который должен выделяться каждой рамке, определяется не рабочей памятью, требуемой в конце блока, а максимальной рабочей памятью, требуемой любой точке внутри блока. Для статической рабочей памяти эту величину можно установить в процессе компиляции.

9.2.  Методы вызова параметров

При распределении памяти в процессе компиляции и прогона необходимо организовать выделение памяти под переменные, объявленные в процедурах. Объем выделяемой памяти зависит от метода сообщения между фактическим параметром в вызове процедуры, и формальным параметром в описании процедуры. В различных языках используются различные методы «вызова параметров»; большинство языков предоставляет программисту возможность выбора по меньшей мере одного из двух методов.

Вызов по значению

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

Вызов по имени

Этот метод заключается в текстуальной замене формального параметра в теле процедуры фактическим параметром перед выполнением тела процедуры. Там, где фактическим параметром является выражение, оно должно вычисляться всякий раз, когда в теле процедуры появляется соответствующий формальный параметр. Это – дорогой метод. С точки зрения реализации аналогичный результат можно получить с помощью специальной подпрограммы времени прогона для вычисления соответствующего фактического параметра. Вызов такой подпрограммы эффективно заменит каждое появление формального параметра в теле процедуры.

Вызов по результату

Как и в вызове по значению, при входе в процедуру выделяется память для значения формального параметра. Однако никакое начальное значение формальному параметру не присваивается. Тело процедуры может осуществлять присвоение значения формальному параметру, а при выходе из процедуры значение, которое в этот момент имеет формальный параметр, присваивается фактическому параметру.

Вызов по значению и результату

Этот метод представляет собой комбинацию вызова по значению и вызова по результату. Копирование происходит при входе в процедуру и при выходе из нее.

Вызов по ссылке

Здесь за адрес формального параметра принимается адрес фактического параметра, если последний не является выражением. В противном случае выражение вычисляется, и его значение помещается по адресу, выделенному для формального параметра. При таком методе получается тот же результат, что и при вызове по значению для выражений. Вызов по ссылке считается хорошим компромиссным решением и осуществлен во многих языках.