Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 123
Текст из файла (страница 123)
Затем он генерирует код перехода по указателю статической цепи столько раз, сколько насчитано включающих сред, чтобы достичь той записи активации, в которой содержится ассоциация для переменной Х. Это позволяет избежать хранения имени идентификатора в стеке во время выполнсшш, как отмечалось ранее. Описанная схема является исключительно эффективной реализацией, обычно требующей и обращений к указателю статической цепи для доступа к переменной, которая объявлена на уровне )г, а используется на уровне и ч-,гг. В большинстве языков программирования глубина вложенности подпрограмм не превышает ч — 5 уровней (типнчная имеет 2-3 уровня), поэтому значение и редко превышает 1 илн 2, но в таких языках, как, например, Разов!, глубина уровней вложенности может быть 9.4.
Явно определяемая общая среда 447 произвольной. Однако мы можем сделать еще лучше — организовать доступ к пра- вильной среде, выполнив всего одну ссылку на указатель статической цепи, как кратко описано ниже, Запись активации для Ма~я Х У 0СР Запись активации для Р ЗСР Х 0СР Запись активации для 0 ЗСР Х ----~ 0СР Запись активации для и ЗСР У 0СР— указатель динамическои цепи ЗСР— указатель статическои цепи Пунктирная линия изображает динамическую цепочку Сплошная пиния изображает статическую цепочку Рис. 9.1 3.
Центральный стек во время выполнения программы Метод статической цепи з1~ачитсльно упрощает вход и выход из подпрограмм. Ко~ да вызывастгя какая-либо подпрограмма, па всрпщ не стека создается ес за1 ишь активации. В этот момент в пей должен быть размещен соответствующий указатель статической цепи, указывающий на запись активации, расположенную ниже в стеке.
При вгяходс нз подпрограммы требуется только удалить из стека запись активации обьгщы м образом; не нужно выполнять никаких специальных действий, связанных с указателем статической цепи. Как мы можем определить соответствующий указатель статической цепи, который следует установить при входе в подпрограмму? Предположим, что подирограммай вызвана из и и й определена в тексте исходной программы, непосредственно вложенной в ла1п, как па рис. 9.12. Когда во время выполнения программы происходит вход в К, то соответствуюпи1й указатель статической цепи указывает назад на запись активации подпрограммы г1а1п. В точке вызова на вершине стека пахо- 448 Глава 9.
Управление подпрограммами дится запись активации подпрограммы О, и запись активации подпрограммы й должна быть помещена на вершину стека над записью активации подпрограммы О. Как же определить, что правильный указатель статический цепи — это указатель на Иат л? Обратите внимание на то, что ссылка на идентификатор й, имя подпрограммы, в операторе вызова подпрограммы й в 0 является нелокальной.
Если определено (во время компиляции), что идентификатор й должен быть объявлен на один уровень вложенности раньше расположения оператора вызова подпрограммы й в 0, тогда во время выполнения указатель статической цепи для й должен указывать на запись активации, расположенную на один шаг впереди' относительно расположения записи активации подпрограммы 0 в статической цепи. Таким образом, в точке вызова подпрограммы й в 0 указатель статической цепи для й можно определить как указатель на запись активации подпрограммы Мати, так как именно ее запись активации расположена на один шаг впереди относительно записи активации подпрограммы 0 в статической цепи, Эта ситуация в точности соответствует той, при которой имя й было бы определено как локальная перетиенная в Иа1л, на которую суцтествовала бы нелокальная ссылка в подпрограмме 0, за исключением того, что после перехода по статической цепи от 0 до соответствующей записи активации не требуется добавлять смещение.
Вместо этого найденная запись активации становится целевым объектом указателя статической цепи подпрограммы й после создания ее записи активации. Реализация дисплея. Чтобы разобраться, как можно улучшить реализацию статической цепи для доступа к нелокачьным ссылкам, нам понадобится несколько предварительных наблюдений. 1. Для любой подпрограммы й во время ее выполнения (когда ее таблица локальной среды находится на вершине стека) длина статической цепи, ведущей от локальной таблицы полпрограммы й вниз по стеку (и в конечном счете к таблице главной программы), посглояяяа и просто равна глубине статической вложенности определения подпрограммы й в исходной программе во время компиляции.
Эта длина не меняется во время выполнения программы. Если, например, определение й содержится в блоке, который расположен непосредственно внутри самого внегпнего блока програьтмы, то длина статической цепи для й во время выполнения всегда равна 3 — в нее входят локальная таблица для й, таблица для содержащего й блока и таблица для самого внешнего блока (главная программа).
На рис. 9.13 и в листинге 9.10, например, длина статической цепи для й всегда равна 2. 2. В этой цепи постояшюй длины нслокальная ссылка всегда будет разрешаться точно в одной и той же точке цепи. Например, иа рис. 9.13 иелокальная ссылка на нмя л' из подпрограммы й всегда будет разрешена во второй таблице цепи. Этот факт является простым следствием статической структуры программы. Количество уровней статической вложенности, которые необходимо пройти от определения подпрограммы й, чтобы найти объявление для ь', фиксируется во время компиляции и затем не изменяется.
Паиоиипм, ~та и статической цепи первой является запись активации текущей выиолияел1ой ирогра м м ьь а ~ ~ослеп пей — запись акт и павии главной программ ьь Позтому по стат ичее кой цепи мы Лвижемси виорел! — Приве ч. науч, рсгй 9.4. Явно определяемая общая среда 449 3. Позиция в цепи, где будет разрешена нелокальная ссылка, может быть определена прн компиляции. Этот факт мы использовали при подсчете количества указателей статической цепи, которое нам надо было пройти, в рассмотренной ранее реализации статической цепи, Например, во время компиляции мы можем определить, что во время выполнения ссылка на М в к будет найдена во второй таблице вперед по статической цепи.
Кроме того, во время компиляции нам известно относительное местоположение 11 в этой локальной таблице. Так, например, во время компиляции мы можем сделать вывод, что во время выполнения ассоциация для М будет второй записью во второй таблице, отсчитываемой вперед по статической цепи. Базис для разработки эффективной операции обработки ссылок теперь очеви- ден.
Вместо того чтобы явным образом осуществлять поиск идентификатора впе- ред по статической цепи, нужно только пропустить в ней фиксированное количе- ство таблиц, а затем применить формулу «базовый адрес + смещение» для выбора нужной записи таблицы. Во время выполнения мы представляем идентификатор парой значений (позиция в цепи, смешение). Например, если идентификатор х, ссылка на который встречается в подпрограмме К, находится в третьей впереди по цепи записи первой таблицы, тогда в скомпилированном коде для 9 идентифика- тор Х может быть представлен парой (1, 3). Такое представление позволяет испол ь- зовать довольно простой алгоритл~ разрешения ссылок. В этой реализации текущая статическая цепь копируется в отдельный вектор, называемый дисплеем, на входе в каждую подпрограмму. Дисплей хранится от- дельно от центрального стека и часто реализуется с помощью быстрых регистров.
В каждой конкретной точке во время выполнения дисплей содержит такую же последовательностьуказателей,которая встречается и в статической цепиподпро- граммы, выполняемой в данный момент. Рис. 9.14 иллюстрирует дисплей для про- граммы, приведенной в листинге 9.10. Разрешение ссылок с использованием дисплея чрезвычайно просто. Приме- ним несколько модифицированное представление идентификаторов во время вы- полнения. Мы по-прежнему будем использовать пары целых чисел, но теперь первое число в паре (например, 3 в (3, 2)) будет означать количество шагов, кото- рые надо сделать назад от конца цепи до соответствующей записи активации (а не вперед от начала цени, как было раньше).
Второе число в этой паре по-пре- жнему представляет собой смещение в записи активации. Теперь, если нелокал ь- ная ссылка представлена в виде (3, 10), то соответствующая ассоциация находит- ся за два шага. 1. Первый элемент пары (то есть число 3) будем считать индексом в дисплее. Оператор Ьаэе абгеээ - й эр1ау[31 присваивает переменной Ьазе абгезз указатель на базовый адрес соответствующей записи активации.
2. Позицию искомой записи таблицы вычисляем как «базовый адрес + смещениеь, в данном случае Ьазе абгегэ + 10. Обычно эти два шага объединяют в один, используя косвенную адресацию че- рез элементы дисплея. Если во время выполнения дисплей реализован в быстрых регистрах, то при разрешении каждой ссылки на идентификатор требуется только одно обращение к памяти, 450 Глава 9. Управление подпрограммами В дисплее содержится статическая цепь для выполняемой в данный момент подпрограммы Дисплей Центральный стек ' сохраняемые, как и раньше, в центральном стеке, для перехода в дисплей при входе и выходе нз подпрограммы Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
