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