Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 106
Текст из файла (страница 106)
Если процедура А содержит определение вложенной процедуры В, то статическая глубина процедуры В равна 2. Длина статической цепочки, которую нужно пройти, чтобы добраться до нужного экземпляра активационной записи, содержащей нелокальную ссылку на переменную Х, в точности равна разности между статической глубиной процедуры, содержащей ссылку на переменную Х, и статической глубиной процедуры, содержащей объявление переменной Х. Эта разность называется глубиной вложении ссылки (пем)пй дерйг), иди смещением по цепочке (сйа!и о(Гзег).
Фактическую ссылку можно представить в виде пары (смешение по цепочке, локальное смещение), состоящей из целых чисел, где смешение по цепочке является количеством связей, которые отделяют нужный экземпляр активационной записи от ссылки на переменную (локальное смешение описано в разделе 9.3.2). В качестве примера рассмотрим следующую скелетную про~рамму: ргодгаж А; ргосвсЬзге В; ргоовс1иге С; вогяг 1 С вос1; 1 В епс1; ( А 406 Глава 9. Реализация подпрограмм Статические глубины процедур А, В и С равны О, ! и 2, соответственно.
Если бы проне- лура с ссылалась на переменную, обьявленную в процедуре А, то смешение по цепочке у этой ссылки равнялось бы 2 (статическая глубина процедуры С минус статическая глубина процедуры А). Если бы процедура С ссылалась на переменную, обьявленную в процедуре В, то смешение по цепочке у этой ссылки равнялось бы !. Обращения к локальным переменным обрабатываются с помощью того же самого механизма, при этом смешение по цепочке равно О. Для того чтобы проиллюстрировать полный процесс нелокального доступа, рассмотрим следующую скелетную программу на языке Рааса): ргодгал МА1М 2; чаг Х : Епседег; ргооеаиге В1680В! чег А, В, С : Епеедвгг ргоовс(цгв ЯУВ1; чаг А, 0: Епеедег; Ьедйл ( ЯУВ1 ) А := В + С; < 1 епа; ( 8((В1 ) ргооес(иге 8()В2(Х : Епеедег); чаг В, Е : Епгвдег( ргооес(цге ЯОВЗг чаг С, Е : Епгедег; Ьвдал ( 8()ВЗ ) ЯУВ1! Е:=В+А;< ела! ( ЯУВЗ ) Ьедйл ( 8()В2 ) ЯУВЗ( А := В + Ег < впс)г [ ЯОВ2 ) Ьвдйл (8168()В] ЯУВ2(7)г епа; [ 8168УВ) Ьвддл ( МА1И 2 ) В168УВг елс(; ( МА1И 2 Последовательность вызовов процедур такова: МА1М 2 вызывает В1680В.
В16ЯОВ вызывает ЯОВ2. 9.3. Реализация подпрограмм иа язмках, подобных языку А(.00(. ЯОВ2 вызывает Я(гВЗ. ЯУВЗ вызывает ЯУВ1. Состояние стека во время выполнения программы при достижении точки ! показано на рис. 9.9. стив ЭЗА Бсвг ! 1 1 1 1 и к ЭЗА ээаг ЭЭА кнсзэь ихгн г ( ЭЗА — экэеииир ээииси вкэиввиии Рис. 9.9.
Содержимое стево при дос- тижении точки! в прь раквне МА!И 2 Глава 9. Реализация подпрограмм В точке ! внутри процедуры ЯВВ1 происходит обращение к локальной переменной А, а не к нелокальной переменной А из процедуры В16ЯУВ. Пара (смешение по цепочке, локальное смещение), соответствующая этой ссылке на переменную А, равна (О, 3). Ссылка на переменную В относится к нелокальной переменной В из процедуры В16ЯОВ.
Эту ссылку можно представить в виде пары (), 4). Локальное смешение равно 4, поскольку смеше- ние. равное 3. соответствует первой локальной переменной (процедура В16ЯУВ не имеет параметров), Отметим, что если бы для простого поиска экземпляра записи активации, соответствующего объявлению переменной В, использовалась динамическая связь, то мы чзшли бы переменную В, объявленную в процедуре ЯОВ2, что было бы ошибкой. Если бы гара (1, 4) использовалась для поиска по динамической цепочке, то была бы найдена переченная Е из процедуры ЯОВЗ.
Статическая связь, однако, указывает на запись активации процедуры В1ЯЯБВ, соответствующую правильному экземпляру переменной В. Переменчзя В в процедуре ЯОВ2 не принадлежит среде ссылок в этой точке и (вполне законно) не доступна.
Обращение к переменной С в точке 1 относится к переменной С, определенной в зроцедуре В1СЯУВ, которой соответствует пара (1, 5). После того как процедура Я(!В1 завершит свою работу, экземпляр ее активационной записи будет удален из стека, а управление будет возвращено в процедуру Я(!ВЗ. Обращение к переменной Е в точке 2 относится к переменной, объявленной в процелуре 1:В2, поскольку эта процедура является ближайшим статическим предком, содержащим . бъявление этой переменной.
Ей соответствует пара (1. 4). Локальное смешение равно 4, потому что переменная В является первой переменной, обьявленной в процедуре ЯУВ1, з процедура ЯОВ2 имеет один параметр. Обращение к переменной А относится к переменной А. объявленной в процедуре В1СЯОВ, поскольку ни процелура ЯОВЗ, ни ее ста-ический предок ЯОВ2 не имеют объявлений переменной с именем А. Этой ссылке соответствует пара (2, 3). ' После того как процедура Я(!ВЗ закончит свою работу, экземпляр ее активацнонной гаписи будет удален из стека.
и в нем останутся только экземпляры записей активации зрограммы МА1!Ч 2, а также процедур В(ЯЯОВ и ЯЦВ2. В точке 3 внутри процедуры ."В2 обращение к переменной А относится к переменной А из процедуры В16ЯОВ, единственной из активных подпрограмм, имеющей объявление этой переменной. Этот доступ осуществляется с помощью пары (1, 3). В этой точке переменная !Э является неьнзимой, таким образом, обращение к ней было бы семантической ошибкой.
Эта ошибка южет быть обнаружена, когда компилятор попробует вычислить пару (смещение по це-очке, локальное смешение). Обращение к переменной Е относится к локальной переменной Е из процедуры ЯБВ2, которая является доступной с помощью пары (О, 5). Итак, обращения к переменной А в точках 1, 2 и 3 можно представить следующими -эрами целых чисел; (О, 3) (локальная) (2, 3) (на два уровня ниже) (1, 3) (на один уровень ниже) В этом месте вполне резонно спросить, как поддерживается статическая цепочка во ьгемя выполнения программы. Если такая поддержка является слишком сложной, то = акт, что такой доступ прост и эффективен, становится неважным.
В этом разделе мы не гзссчатрнваем параметры, передаваемые по имени, и параметры, являющиеся именами - зпрограмм. Статическая цепочка должна модифицироваться при каждом вызове подпрограммы и э звращении из нее. Часть, связанная с возвращением из подпрограммы, является тривиальной: когда подпрограмма завершает свою работу, ее активационная запись удаляется з стека.
После этого на вершине стека окажется экземпляр записи активации модуля, вызвавшего только что завершившуюся подпрограмму. Поскольку статическая цепочка, О.З. Реализация подпрограмм на языках, подобных языку АЛЛОЕ 409 начинающаяся этим экземпляром активацнонной записи, никогда не изменялась, она работает правильно, так же, как она работала до вызова другой подпрограммы.
Следовательно, никакие другие действия не нужны. Действия, которые необходимо выполнить при вызове подпрограммы, намного сложнее. Несмотря на то что соответствующая область видимости предка легко определяется во время компиляции, во время вызова должны быть найдены самые последние по времени создания экземпляры активационных записей, находящиеся в области видимости предка. Для этого проводится поиск экземпляра активационной записи по динамической цепочке, пока не будет найден первый экземпляр в области видимости предка. Однако этого можно избежать, если обрабатывать обьявления процедур и ссылки на них точно так же, как и для переменных.
Когда компилятор встречает вызов процедуры, помимо всего прочего, он определяет, в какой именно процедуре была объявлена данная процедура. Такая процедура должна быть статическим предком вызываемой процедуры. Затем компилятор вычисляет глубину вложения, или количество вложенных областей видимости между вызывающим модулем и процедурой, в которой объявлена вызываемая процедура. Эта информация записывается в память и становится доступной для вызова данной процедуры при выполнении программы. В момент вызова определяется статическая связь, содержащаяся в экземпляре активационной записи вызываемой процедуры.
Для этого следует переместиться вниз по статической цепочке вызывающего модуля на количество звеньев, равное глубине вложения, вычисляемой во время компиляции. Снова рассмотрим программу Нд1 В 2 и состояние стека, показанное на рис. 9.9. Обрабатывая вызов процедуры ЯВВ1 из процедуры БУВЗ, компилятор определяет, что глубина вложения процедуры ВВВЗ (вызывающего модуля) на два уровня меньше, чем глубина вложения процедуры, в которой объявлена вызываемая процелура ЯУВ1, т.е. В1680В. При вызове процелуры ЯБВ1 из процедуры ЯУВЗ зта информация используется для установления статической связи в экземпляре активацнонной записи процедуры ЯВВ1. Этой статической связи присваивается указатель на экземпляр активационной записи, на которую указывает вторая статическая связь в статической цепочке, считая от экземпляра активационной записи вызывающего модуля.
В этом случае вызывающим модулем является процедура ВУВ 3, статическая связь которой указывает на экземпляр активационной записи ее предка (т.е. ЗВВ2). Статическая связь экземпляра активационной записи процедуры ВБВ2 указывает на экземпляр записи активации процедуры В1ВЯБВ. Таким образом, статической связи нового экземпляра активационной записи процелуры БВВ1 присваивается указатель на экземпляр активационной записи процедуры В16ЯВВ. Этот метод работает при связывании любых процедур, кроме случая, когда в качестве параметров в процедуру передаются имена подпрограмм. Эта ситуация рассматривается в разделе 9.б. Один недостаток использования статической цепочки для доступа к нелокальным переменным заключается в том, что ссылки на переменные, находящиеся вне области видимости статического предка, выполняются неэффективно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
