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

Описатель

proc(real, int) bool,

выражающий значение вида «процедура-с-вещественными-и-целочисленными-параметрами-дающая-логический-результат» может быть представлена структурой с отдельными указателями на список параметров и результат (рис. 7.3).

 

proc				Real			int
bool

Рис. 7.3. Структура процедуры

Аналогичным образом вид

struct(int(i), struct(int j, bool y), real r)

может быть представлен так, как показано на рис. 7.4.

struct
int	i			struct				real	r
				int	J			bool	y

Рис 7.4. Структура типа struct

Каждая ячейка имеет два (возможно пустых) указателя; вертикальный указатель используется в случае структурных, объединенных и процедурных видов.

С помощью рассмотренного метода представления видов компилятор может легко выполнять следующие операции:

1)  нахождение вида результата процедуры;

2)  выбор структуры поля;

3)  разыменование значения, т. е. замену адреса значением в адресе;

4)  векторизацию, т. е. построение линейной структуры для любого массива.

Контрольные вопросы

1.  Понятие прохода компилятора, необходимость использования нескольких проходов при компиляции.

2.  Назначение таблицы символов.

3.  Методы организации таблицы символов.

4.  Хеширование, разрешение конфликтов при хешировании.

5.  Сцепление элементов и бинарное дерево.

6.  Назначение таблицы видов.

7.  Способы организации таблицы видов.

9.  Распределение памяти

9.1.  Стек времени прогона

После выяснения структуры программы необходимо выделить место в памяти для внесения значений переменных и поместить соответствующие адреса в таблицу символов. Фаза распределения памяти практически не зависит от языка и машины и одинакова для большинства языков, имеющих блочную структуру. Распределение памяти заключается в отображении значений, появляющихся в программе, на запоминающее устройство машины. Если реализуемый язык имеет блочную структуру, а ЭВМ имеет линейную память, то наиболее подходящим устройством, на котором будет базироваться распределение памяти, является стек или память магазинного типа.

Каждой программе для хранения значений переменных и промежуточный значений выражений необходим определенный объем памяти. Например, если идентификатор описывается как

int x,

т. е. х может принимать значение типа целого, то компилятору необходимо выделить память для х. Иными словами, компилятор должен выделить достаточно места, чтобы записать любое целое число. Аналогично, если у описывается как

struct (int number, real size, bool n) y,

то компилятор обеспечивает для значения у память с объемом, достаточным для хранения в нем целого, вещественного и логического значения. В обоих случаях компилятор не должен испытывать затруднений в вычислении требуемого объема памяти. Если z описывается

int z[10],

то объем памяти, необходимый для хранения всех элементов z, в 10 раз больше памяти для записи одного целого значения. Однако, если бы w был описан в виде

int w[n],

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

Память нужна также для промежуточных результатов и констант. Например, при вычислении выражения a + c ´ d сначала вычисляется c ´ d, причем значение запоминается в машине, а затем выполняется сложение. Память, используемая для хранения результатов, называется рабочей. Рабочая память может быть статической и динамической.

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

INTEGER A, B, X, Y

выделяется память, как это показано на рис. 8.1.

A	B	X	Y

Рис. 8.1. Распределение памяти для Фортрана

Такая схема не учитывает тот факт, что рабочая память используется неоднократно и весьма неэффективна для языка с блочной структурой.

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

Пусть имеется программа вида:

begin real x, y

.

.

.

begin int c, d

.

.

.

end

begin char p, q

.

.

.

end

.

.

.

end

На рис. 8.2 показаны «моментальные снимки» стека времени прогона на различных этапах ее выполнения.

		d		q
		c		p
y		y		y
x		x		x
(1)		(2)		(3)

Рис. 8.2. Стек времени прогона

На рис. 8.2 изображено место, занимаемое значениями идентификаторов во время прогона. Часть стека, соответствующую определенному блоку, называют рамкой стека. Указатель стека показывает на его первый свободный элемент.

Кроме указателя стека требуется также указатель на дно текущей рамки (указатель рамки). При входе в блок этот указатель устанавливается равным текущему значению указателя стека. При выходе из блока сначала указатель стека устанавливается равным значению, соответствующему включающему блоку. Указатель рамки включающего блока может храниться в нижней части текущей рамки стека, образуя часть статической цепи или массива, который называется дисплеем. Его можно использовать для хранения во время прогона указателей на начало рамок стека, соответствующих всем текущим блокам (рис. 8.3).

			q
			p
			x
ДИСПЛЕЙ			y	СТЕК

Рис. 8.3. Система «дисплей-стек»

Это упрощает настройку указателя при выходе из блока.

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

Рассмотрим пример программы:

begin int n; read(n);

int numbers[n];

real p;

begin real x, y;

Место для numbers должно выделяться в первой рамке стека, а для х и у – в рамке над ней. Но во время компиляции неизвестно, где должна начинаться вторая рамка, так как неизвестен размер чисел. Одно из решений в этой ситуации – иметь два стека: один для статической памяти, распределяемой в процессе компиляции, а другой для динамической памяти, распределяемой в процессе прогона.