Структуры данных, с которыми должна работать и которые должна формировать проектируемая программная система, условно можно разбить на два класса: внешние и внутренние. Ко внешним данным отнесем те, что доступны внешнему пользователю системы: на входе – текст исходной программы и указание способа формирования области видимости символических имен; на выходе – представленная в соответствии с вариантом задания информация о видимых именах на этапе компиляции и на этапе выполнения исходной программы.
Внутренние структуры, формируемые компилирующей частью системы, можно представить, например, в виде следующей системы таблиц: таблицы блоков, таблиц локальных имен блоков, таблицы исполняемых кодов блоков.
Таблица блоков в такой системе структур данных должна рассматриваться как основная, с помощью которой остальные таблицы разбиваются на подтаблицы – по одной для каждого блока. Формат записи таблицы блоков может иметь вид:
| Имя блока (ключ) | Ссылка на таблицу локальных имен | Ссылка на исполняемый код |
В таблицах имен полем ключа является поле символического имени; остальные поля записи таблицы имен могут содержать данные о типе имени (например: переменная, параметр, функция; если переменная – какого типа; если параметр – как передается и т.д.).
Таблица исполняемых кодов, или точнее – массив кодов, может быть организована в виде массива строк, каждая из которых является исполняемым оператором исходной программы.
Принадлежность фрагментов таблицы имен и массива исполняемых кодов отдельным поименованным блокам, как уже говорилось выше, указывается в таблице имен блоков, например, - в виде диапазонов значений индексов элементов, соответственно, таблицы имен и массива исполняемых кодов.
Пример содержания внутренних структур, сформированных компилирующей частью системы
Текст исходной программы (внешние данные)
program main;
var a,b;
procedure c(var d;e);
var a;
begin
end; {c}
procedure d(var e;f);
var b;
begin
c(b,f);
end; {d}
procedure g(h,var i);
var c;
procedure j(var k);
begin
end; {j}
begin
j(c);
d(h,c);
end; {g}
begin
d(a,b);
g(a,b);
end. {main}
Таблица имен блоков (внутренние данные)
| Имя блока | Ссылка на таблицу имен | Ссылка на исполняемый код |
| main | 1¸5 | 1¸3 |
| c | 6¸8 | 4¸4 |
| d | 9¸11 | 5¸6 |
| g | 12¸15 | 7¸9 |
| j | 16¸16 | 10¸10 |
Таблицы имен (внутренние данные)
| имя | тип | |
| a | var | |
| b | var | |
| c | proc | |
| d | proc | |
| g | proc | |
| d | paramv | |
| e | param | |
| a | var | |
| e | paramv | |
| f | param | |
| b | var | |
| h | param | |
| i | paramv | |
| c | var | |
| j | proc | |
| k | paramv |
Исполняемый код (внутренние данные)
| d(a,b) | |
| g(a,b) | |
| stop | |
| return | |
| c(b,f) | |
| return | |
| j(c) | |
| d(h,c) | |
| return | |
| return |
Внешние выходные структуры компилирующей части системы – это таблицы символических имен для каждого блока программы. Они могут формироваться одновременно с вышеописанными внутренними структурами. В случае динамического формирования области видимости имен эти таблицы – просто фрагменты, из которых сформирована внутренняя таблица локальных имен. В случае статического формирования области видимости неоценимую помощь в построении таких таблиц окажет так называемый стек времени компиляции. Запись такого стека – это символическое имя со своими атрибутами. В процессе просмотра исходной программы при обнаружении начала описания блока (в нашем примере это – procedure или program) компилятор заносит в стек все локальные имена этого блока, а при обнаружении конца описания блока (в нашем примере это - end) компилятор удаляет из стека все локальные имена этого блока. Таблица имен блока формируется в момент рассмотрения компилятором этого блока. В нее записываются по одному все имена, находящиеся в этот момент в стеке.
Примеры содержания стека времени компиляции
1) Рассмотрение блока c
Содержание стека Таблица имен блока c
| a var | c | a | var | c |
| c param | c | e | param | c |
| d paramv | c | d | paramv | c |
| b var | main | b | var | main |
| a var | main |
2) Рассмотрение блока d
Содержание стека Таблица имен блока d
| b var | d | b | var | d |
| f param | d | f | param | d |
| e paramv | d | e | paramv | d |
| c proc | main | c | proc | main |
| b var | main | a | var | main |
| a var | main |
При моделировании процесса выполнения программы аналогично формированию стека времени компиляции формируется стек времени выполнения программы (еще одна внутренняя структура). Занесение данных в стек происходит при обнаружении оператора вызова блока, удаление – при обнаружении оператора возврата из блока (в нашем примере это - return). В условиях динамического формирования области видимости имен текущее содержание такого стека позволяет определить видимые в исполняемом блоке имена аналогично тому, как это определяется по стеку времени компиляции в условиях статического формирования области видимости.
Помимо записей о символических именах, в стек времени выполнения должны заноситься записи о точках возврата, т.е. об адресах операторов, к которым следует переходить при выполнении операторов типа return. С этой целью следует завести так называемый указатель адреса команды (IP), текущим значением которого всегда будет индекс элемента массива исполняемого кода, который (элемент) содержит текущую исполняемую команду. При выполнении команды (оператора) вызова блока значение этого указателя , увеличенное на единицу, заносится в стек времени выполнения в качестве точки возврата, а сам указатель приобретает новое значение, которое выбирается из записи таблицы имен блоков, соответствующей вызванному блоку (графа «ссылка на исполняемый код»). При исполнении команды типа return указатель IP приобретает значение, выбранное из вершины стека.
Пример содержания стека времени выполнения
Выполнение блока main
IP=1
Команда d(a,b)
Содержание стека
| g proc | main |
| d proc | main |
| c proc | main |
| b var | main |
| a var | main |
| 0 return | адрес возврата (останова) |
Выполнение блока d
IP=5
Команда c(b,f)
Содержание стека
| e param | d |
| f param | d |
| b var | d |
| 2 return | адрес возврата |
| g proc | main |
| d proc | main |
| c proc | main |
| b var | main |
| a var | main |
| 0 return | адрес возврата (останова) |
Выполнение блока c
IP=4
Команда return
Содержание стека
| a var | c |
| e param | c |
| d paramv | c |
| 6 return | адрес возврата |
| e param | d |
| f param | d |
| b var | d |
| 2 return | адрес возврата |
| g proc | main |
| d proc | main |
| c proc | main |
| b var | main |
| a var | main |
| 0 return | адрес возврата (останова) |
Выполнение блока d
IP=6
Команда return
Содержание стека
| e param | d |
| f param | d |
| b var | d |
| 2 return | адрес возврата |
| g proc | main |
| d proc | main |
| c proc | main |
| b var | main |
| a var | main |
| 0 return | адрес возврата (останова) |
И т.д.