Курсовая Лексический анализатор. Краткий курс лекций. Курс лекций по спецкурсу Методы трансляции

• Название: Курс лекций по спецкурсу Методы трансляции
• Анкор: Курсовая Лексический анализатор
• Дата: 29.12.2019
• Размер: 0.64 Mb.
• Имя файла: Краткий курс лекций.doc
• Тип: Курс лекций; #102547
• страница: 18 из 19

Задача распределения памяти для данных. Статическое
распределение памяти

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

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

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

Существуют два метода распределения памяти: статическое и динамическое. Какой из них выбирается при создании компилятора, зависит от синтаксиса входного языка, архитектуры ЭВМ, задач, которые ставят перед собой разработчики компилятора. Как правило, в компиляторах используют оба метода распределения, причем основным является метод динамического распределения.

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

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

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

Пример программы с блочной структурой на языке C:

main() ────────────┐

{ int a,b; m1: │

{ int a1,b1; m2: ──────┐ │

─┐ │ │

{ int d; m3: ... ; } │BL3 │ │

─┤ │BL2 │

m4:{ int d1; m5: ... ; } │BL4 │ │

─┘ │ │BL1

m6: ... ; │ │

} ──────┤ │

m7:{int f,e; m8: ... ; } │BL5 │

──────┘ │

m9: ... ; │

} ────────────┘

Допустим, память для данных распределяется с адреса k, и длина переменных типа int – 4 байта. Тогда состояние памяти при выполнении программы меняется в зависимости от видимости переменных:

адрес	метка	m1	m2	m3	m4	m5	m6	m7	m8	m9
k+0		a	a	a	a	a	a	a	a	a
k+4		b	b	b	b	b	b	b	b	b
k+8			a1	a1	a1	a1	a1		f
k+12			b1	b1	B1	b1	b1		e
k+16				d		d1

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

Блочная структура программы может быть представлена в виде дерева:



уровень 1


уровень 2

уровень 3

Узлы дерева соответствуют блокам и расположены на разных уровнях. Внешнему блоку приписан уровень 1. Блоку, содержащемуся в блоке уровня r, приписывается уровень r+1.

Статическое распределение памяти для данных проводится в два этапа. На первом этапе выделяется секция памяти каждому блоку, на втором – назначаются адреса переменным внутри блока.

На первом этапе распределения памяти каждому блоку программы присваивается номер i в соответствии с последовательностью их описания в программе. Определяются величины n[i] – размер секции памяти i-го блока (n[1] = n[2] = n[5] = 8 байт, n[3] = n[4] = 4 байта) и строится таблица блоков.

Для приведенного примера программы таблица блоков имеет вид:

Номер блока	Уровень блока (УБ[i])	Объем памяти для блока (n[i])
1	1	8
2	2	8
3	3	4
4	3	4
5	2	8

Затем по таблице блоков определяются адреса начала секций памяти для блоков (A[i]). Для первого блока принимается A[1] = k – адрес начала области данных программы. Для каждого последующего блока i величина A[i] определяется как

A[i] = A[m] + n[m], где m = max(j | УБ[j]<УБ[i], j
То есть, для определения m последовательно просматриваются строки таблицы блоков j = i-1,i-2,...,1 и ищется первая строка, для которой УБ[j] < УБ[i].

Результат реализации этого алгоритма представлен ниже:

Адрес начала секции блока (A[i])

k

k + 8

k + 16

k + 16

k + 8

На втором этапе секция данных каждого блока распределяется по отдельным переменным и массивам. Для каждого блока выделяются счетчики T[i], указывающие текущий адрес в секции. Первоначально T[i] = A[i].

Просматривается таблица идентификаторов и для каждой переменной или массива извлекается номер блока – i и длина переменной – d. Величина T[i] принимается в качестве адреса переменной и корректируется T[i] = T[i] + d.

Результат распределения памяти для переменных:

Переменная	Номер блока	Длина	Адрес	T[1]	T[2]	T[3]	T[4]	T[5]
				k	k+8	k+16	k+16	k+8
a	1	4	k	k+4
b	1	4	k+4	k+8
a1	2	4	k+8		k+12
b1	2	4	k+12		k+16
d	3	4	k+16			k+20
d1	4	4	k+16				k+20
f	5	4	k+8					k+12
e		4	k+12					k+16

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

Статическое распределение памяти накладывает некоторые ограничения на синтаксис входного языка:

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