Cтраница 1
Центральная таблица устроена так, что в любой момент по время выполнения программы она содержит все активные в этот момент ассоциации идентификаторов независимо от того, локальные они или нет. Если принять, опять-таки для простоты, что множество всех идентификаторов, на которые ссылаются подпрограммы, может быть определено при трансляции, то при начальной установке центральной таблицы в нее следует включить по одному элементу для каждого идентификатора, независимо от числа подпрограмм, в которых встречается этот идентификатор. Каждый элемент таблицы содержит также флаг активности, указывающий, имеет ли данный идентификатор активную ассоциацию, и, кроме того, в элементе отведено место для указателя на объект ассоциации. [1]
Центральная таблица среды применяется во многих вариантах. На рассмотренном методе моделирования основана реализация языка Снобол 4, описанная в гл. Другие варианты рассматриваются в упражнениях в конце этой главы. [2]
Каждый элем-ент центральной таблицы ц поч-ек содержит саму цепочку и указатель на ее значение. Когда во время выполнения программы создается новая цепочка, центральная таблица просматривается, чтобы выяснить, не была ли эта цепочка ранее внесена в таблицу. Если была, то используется указатель на найденный элемент таблицы. Эта простая схема вносит в язык значительную гибкость; она позволяет во время выполнения создавать при желании новые переменные. Ее недостаток заключается в стоимости поиска по таблице каждый раз, когда создается новая цепочка. Поскольку многие инструкции Снобола 4 создают новые цепочки, поиск по таблице происходит часто. Обычным представлением для центральной таблицы является хеш-таблица с дополнительным пространством для обработки коллизий. [3]
Каждый элемент центральной таблицы состоит из цепочки литер и указателя. Обычно ввиду частых - обращений к этой таблице она имеет структуру хеш-таблицы фиксированного размера, каждый элемент которой представляет собой блок, содержащий все элементы с одинаковым хеш-индексом. Значением цепочки в такой таблице может быть указатель на другую цепочку в этой таблице, число или указатель на массив, таблицу ( список свойств), образец или структуру данных определяемого программистом типа. Цепочки и их значения записываются в кучу, но основная хеш-таблица ( содержащая указатели на блоки в куче) расположена в статической области. [4]
Основным результатом использования центральной таблицы цепочек для представления среды ссылок является то, что нелокальные ссылки подчиняются правилу последней ассоциации. При входе в подпрограмму текущие ассоциации для всех локальных идентификаторов деактивируются, при выходе они восстанавливаются; все же остальные идентификаторы сохраняют существующие ( и, следовательно, последние) ассоциации. [5]
Объясните, почему цепочки в центральной таблице, к которым нет путей, могут собираться как мусор, только если они имеют пустое значение. [6]
Объясните, какие изменения происходят в центральной таблице цепочек ( содержащей значения X и Y) в результате выполнения каждой из этих инструкций. [7]
Цепочка всегда представляется ссылкой на описывающий ее элемент центральной таблицы. Так, если X - простая переменная, имеющая значением цепочку ABY, то значением X будет на самом деле указатель на элемент ABY в центральной таблице. Но, кроме того, поскольку X тоже цепочка, она сама является элементом центральной таблицы. Если Y - другая переменная, значение которой - цепочка X, то значением Y будет указатель на элемент X в центральной таблице. [8]
В реализациях Лиспа иногда используется некий вариант метода центральной таблицы среды ссылок из разд. С каждым идентификатором ( атомом в Лиспе) связывается небольшой отдельный стек ( обычно он является частью списка свойств идентификатора), который содержит все ассоциации этого идентификатора. Текущая ассоциация находится на вершине этого стека; остальные элементы стека представляют неактивные ассоциации. При входе в подпрограмму, в которой имеется новая ассоциация для X, эта новая ассоциация помещается на вершину стека ассоциаций для X При выходе из подпрограммы верхний элемент стека для X просто удаляется, при этом восстанавливается старая ассоциация. [9]
Разберите достоинства и недостатки этого метода в сравнении с методом центральной таблицы, описанным в разд. [10]
В реализации Снобола 4, описанной в этой главе, цепочки вносятся в центральную таблицу в момент их создания. Цепочки без ассоциаций могли бы храниться во временной памяти лишь до тех пор, пока они не станут мусором и их можно будет уничтожить, Укажите достоинства и недостатки этого метода. [11]
Среда ссылок, существующая в каждый момент выполнения Снобол-программы, тесно связана с центральной таблицей цепочек, используемой для записи цепочек литер. Поскольку цепочки рассматриваются в то же время как имена простых переменных, то любая цепочка в центральной таблице может иметь ассоциацию и на нее можно сослаться. Конечно, текст программы содержит только определенные идентификаторы переменных, которые были известны после написания программы. [12]
Указатель на этот массив, возвращаемый функцией ARRAY, немедленно присваивается переменной X, хранящейся в центральной таблице цепочек. Последующая ссылка на Х3) позволяет обычным образом обратиться к третьему элементу этого массива. [13]
Семантические анализаторы взаимодействуют между собой посредством информации, хранящейся в различных структурах данных, в частности в центральной таблице символов. Например, семантический анализатор, обрабатывающий описания типа для простых переменных, делает зачастую очень мало кроме того, что просто вносит описанные типы в таблицу символов. Позже семантический анализатор, обрабатывающий арифметические выражения, может использовать описанные типы для включения соответствующих специфических типов арифметических операций в объектный код. [14]
Этот новый метод обобщает все методы моделирования локальных сред предыдущего раздела - и в отличие от них использует центральную таблицу, общую для всех подпрограмм: центральную таблицу среды ссылок. Для простоты мы рассмотрим здесь случай, когда локальные ассоциации не сохраняются между вызовами, а уничтожаются и создаются в центральном стеке. Это обычная ситуация; противоположный случай с сохранением локальных сред рассмотрен в упр. [15]