Выбрать главу

Память бланков точно так же требует большего внимания, чем ей уделялось в предшествующем изложении. Поскольку как имя, так и тело бланка представляют собой цепочки, имеет смысл хранить их вместе в некоторой разновидности памяти для цепочек. Необходимо также место, где хранились бы указатель бланка и метки сегментов; кроме того, нужно уметь находить бланки. В такой ситуации проще всего выделить достаточно большое пространство бланков и хранить бланки в виде связанного списка. У каждого бланка будет головная часть фиксированного размера; она будет включать указатель на следующий бланк, указатель бланка, начальную позицию и длину имени бланка, а также начало и длину тела. Имя и тело можно хранить сразу вслед за головной частью, а метку сегмента можно представлять некоторой парой литер, окружающих целое число (конечно, необходимо иметь какой-либо другой способ изобразить литеры метки как обычные литеры). Для выполнения поиска бланка можно пройти по списку бланков, а для исключения бланка можно удалить его из списка с помощью перестановки указателей, а затем передвинуть окружающие бланки, чтобы заполнить образовавшуюся дыру. Существуют и другие способы организации памяти бланков; каждому способу присущи свои достоинства и недостатки.

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

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