Курсовая Лексический анализатор. Краткий курс лекций. Курс лекций по спецкурсу Методы трансляции
![]()
|
Задача распределения памяти для данных. Статическое |
адрес | метка | 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 и.полученному в результате анализа хода выполнения программы.
Статическое распределение памяти накладывает некоторые ограничения на синтаксис входного языка:
не допускается использование массивов с переменными границами, объем которых можно определить лишь в момент входа в блок;
не допускается использование рекурсивных процедур, т.е. процедур, вызывающих самих себя, т.к. каждый повторный вход в них требует нового выделения памяти для данных, а количество входов при трансляции неизвестно.