5.6. Опс для стандартных операторов

Наряду с рассмотренными типами операторов в языке программирования, как правило, имеются такие стандартные операторы, как операторы ввода и вывода. Рассмотрим пример таких операторов.

Пример 18. Расширим грамматику, рассмотренную в примере 17, задав операторы ввода и вывода порождающими правилами, начинающимися с нетерминала A:

A → read (aH) | write (S)

При работе анализатора, если верхний символ в магазине будет A, то при входном символе read в магазин будет копироваться последовательность: read (aH), а в дополнительный магазин: □□a□<r>. При входном символе read в магазин будет копироваться последовательность: write (S), а в дополнительный магазин: □□□<w>. Здесь <r> и <w> обозначают соответственно операции чтения входного значения с устройства ввода в переменную (возможно, с индексом) и записи значения арифметического выражения на устройство вывода. Обе такие операции при вычислении требуют в магазине одного операнда.

Так, например, по входной цепочке:

begin read(i); read(M[i]); write(M[i]*i) end

будет сгенерирована ОПС:

i <r> M i <i> <r> M i <i> i * <r>

При вычислении по этой ОПС содержимое магазина интерпретатора будет изменяться таким образом:

i	Операция <r> – чтение (ввод)

M

i

Операция <i> – индексирование

M[i]	Операция <r> – чтение

M

i

Операция <i> – индексирование

M[i]

i

Операция * – умножение

M[i]*i

Операция <w> – запись (вывод)

Конец примера.

5.7. Распределение памяти и описание переменных

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

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

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

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

Пример 19. Расширим грамматику, рассмотренную в примере 18, пере­опре­делив начальный нетерминал, который задает структуру всей программы, включая описания. Новый начальный нетерминал P определяет программу, состоящую из совокупности описаний, после которых записана последовательность операторов, взятая в операторные скобки begin – end:

P → int R P | int1 R P | int2 R P | begin Q end

R → a M

M → , a M | ;

Здесь в описаниях предусмотрены три типа переменных: целый (int), одномерный массив целых (int1) и двумерный массив целых (int2). Размеры массивов определяются в процессе выполнения программы. Для выделения памяти предусмотрены следующие стандартные операторы:

A → mem1 (a, S) | mem2 (a, S, S)

Оператор mem1 выделяет память одномерному массиву, второй параметр – размер массива, Оператор mem2 – двумерному массиву, второй и третий параметры – размеры массива по первому и второму измерению соответственно. Нумерация элементов массивов – с нуля.

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

Правая часть правила	Запись в доп. магазин
int R P  int1 R P int2 R P begin Q end a M , a M ; mem1 (a, S) mem2 (a, S, S)	<11>□□ <12>□□ <13>□□ <14>□<15> <16>□ □<16>□ □ □□ a □□<m1> □□ a □□□□<m2>

Рассмотрим выполняющиеся при этом семантические программы.

Программа <11>.

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

Программа <12>.

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

Программа <13>.

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

Программа <14>.

1. Завершение формирования таблиц переменных.

2. Генерация в ОПС операций выделения памяти блоками для каждого из типов переменных:

– для типа int – в виде массива целых, каждая переменная в нем занимает отдельный элемент и ей приписан номер;

– для типа int1 и int2 – в виде массива структур (паспортов), в которых записывается размерность по одному или двум измерениям соответственно, а также ссылка на адрес будущего размещения массива в памяти.

3. Генерация в ОПС операций обнуления массивов структур для переменных типа int1 и int2.

Программа <15>.

Генерация в ОПС операций освобождения всех выделенных в процессе выполнения программы блоков памяти.

Программа <16>.

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

2. Если ошибки нет, то добавление имени переменной в одну из таблиц переменных (на которую было ранее переключение).

Конец семантических программ.

Операции <m1> и <m2>, генерируемые в ОПС при анализе операторов mem1 и mem2, при работе интерпретатора должны выполнять следующие действия. Вначале проверяется, не выделялась ли раньше память для переменной, указанной в первом операнде. Если да, то выдается сообщение об ошибке, а если нет, то выделяется (по запросу к операционной системе) требуемая память, после чего в паспорт массива записывается ссылка (адрес) на нулевой элемент массива, а также размерность по одному или двум измерениям соответственно.

Конец примера.