Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 105
Текст из файла (страница 105)
( МА1Б 1 Последовательность вызовов процедур в этой программе такова: МА1И 1 вызывает В В вызывает А А вызывает С Содержимое стека в точках, отмеченных цифрами ], 2 и 3, показано на рис. 9.5. 400 Глава 9. Реализация подпрограмм В точке 1 в стеке содержатся только экземпляры записей активации программы . А1Н 1 и процелуры В. Когда процедура В вызывает процедуру А, в стек заносится экземпляр записи активации процедуры А. Когда процедура А вызывает процедуру С, в стек заносится экземпляр активации процедуры С. Когда выполнение процелуры С завершается, экземпляр ее записи активации удаляется из стека, а динамическая связь ислользуется лля переопределения указателя на вершину стека. Аналогичный процесс происходит, когда завершается выполнение процедур А и В. После возврата управления из зроцедуры В в программу ИА1Н 1 стек содержит только экземпляр записи активации программы ИА1И 1.
Заметим, что некоторые системы реализации языков программирования в действительности не хранят в стеке экземпляр записи активации главной про-рачмы, как это показано на рисунке. Однако описанная ситуация возможна, и это упгошает как саму реализацию, так и ее обсуждение. В данном примере и во всех осталь-ых примерах этой главы мы предполагаем, что стек увеличивается в порядке зозрастания адресов, зн а Рис. 9.5. Содерлгичое стека в трех точках проеранты Совокупность динамических связей, содержашихся в стеке в данный момент време- -'.. называется динамической цепочкой (дупапис сна|в), или цепочкой вызовов (сай .-зш). В ней описана динамическая история того, каким образом выполнение програм- .; застигло текущей точки, которая всегда находится в сегменте кода. экземпляр записи :.тнвации которою расположен на вершине стека.
Ссылки на локальные переменные = 3. Рволизоция подпрограмм ип языках, подобных языку А100~ могут быть представлены в коде с помощью смешения относительно начала записи активации в соответству)ошей локальной области видимости. Такое смещение называется локальным ()оса! оГГзе(). Локальное смешение переменной в записи активации можно определить во время компиляции, используя порядок, тип н размеры переменных, объявленных в процедуре, соспветствующей данной записи активации. Предположим для простоты, что все переменные в записи активации занимают по одной ячейке. Первую локальную переменную, объявленную в процедуре, можно разместить в ячейке, номер которой вычисляется следующим образом: три плюс количество параметров, считая со дна стека (первые три ячейки предназначены для хранения адреса возврата, статической связи и динамической связи). Вторая локальная переменная может быть размещена на одну ячейку ближе к вершине стека и так далее.
Например, рассмотрим предыдущую скелетную программу. В процедуре А локальное смещение переменной У равно 4. Аналогично, в процедуре В локальное смещение переменной Я равно 4, а переменная Т имеет локальное смешение, равное 5. 9.3.3. Рекурсия Рассмотрим следующий пример программы на языке С, в которой для вычисления факториала используется рекурсия: зпа йасгогда1(хпс п) < 1 хг (п <= 1) геапгп 1; в1вв гегигп (п * Гассогйа1(и — 1) ); < 2 'и() 1пс та1це; та1це = йасгогда1(30( < 1 Формат записи активации функции йассогда1 показан на рис. 9.6. Заметим, что запись имеет дополнительное поле для возвращаемого значения функции. и На рис. 9.7 показано содержимое стека, соответствующее трем разным ситуациям, когда выполнение программы достигает точки 1 в функции йассог1а1.
В каждом случае показана дополнительная активация функции с неопределенным возвращаемым значением. Первый экземпляр активационной записи функции содержит адрес возврата в вызывающую функцию вази. Остальные содержат адрес возврата в саму Рис. 9.б. Зались акенвафункшцо, соответствующий рекурсивным вызовам. ции функции Гасгогйа1 Глава 9. Реализация подпрограмм йяз трама эзя Расвппв первая амоса эээ иаз третий омыв вторая амоса Рис. 9.7. Содержимое стека в точке 1 функции Гасеогза1 доз 9.3. Реализация подпрограмм на языках, подобных языку АЮО1 первмя эзп типам й( з.оооп эзя 'осВпи еьамя эзя тзсесй 2( врмииа става рата твоа Вторая ЭЗП т пампе Первая Ээя тавола й( врмиив стив Впрапнл стаяв Значение фунщпи 1 и Трегнй ЭЗА Еас огса1 Возвраг (е Еассог а ! Значение функци» Парамвкр З п Второй ЭЭА Еаскогса1 Динамнческав связь Стачическаа свнэь Воавраг (е Епссогсас] нарвина осака Знвчвнмв функцмн Паренегр З Первый ЭЭА Еассогйа1 Днмаммчвская сваеь Сгагмческаа свагь Возврат (в паси ЗЗА ( Локальная перенанная чвние В точке 2 функции ;Ьосок Ь! В !очке 2 функции (ассо11а! грвгнй емкое Вмполнан мрвмй вмзов емполнвн вераина осака Второй ЭЗА Еассог1а1 Парный ЭЗА кассог1а1 ввранна скекв Вокальная переменное В значение ма1п ( чвннв В гочка Э функцм» маьп В точке 2 функции (ассог1а1 акорпй вмяоа амполнеи мончательнма рвкультакм ЗЗА — якземнлар эаписп акгмвацнн Рие.
9в. Еодерж(к!кое санеко во время виноянения функций п(а го и Гвссогйа Е Глааа 9. Реализация подпрограмм Паранегр Динамическая сваэь Сгатическая свакь Первнй ЭЗА Еаскогса1 ЭЗА Г значение оасп с На рис. 9.8 показано содержимое стека, соответствующее трем разным ситуациям, г"эгза выполнение программы достигает точки 2 в функции йасгог1а1. Точка 2 соответствует случаю, когда оператор гесиги уже выполнен, а запись активации из стека еше не удалена. Напомним, что код фумкции умножает текущее значение параметра и на :чачение, возвращаемое при рекурсивном вызове функции. При первом вызове функция .
з =-ог1а1 возвращает значение 1. В этом случае копия параметра и в экземпляре заэиси активации имеет значение 1. Результат, равный 1, передается второй активации функции йасгогза1 лля умножения на значение ее параметра и, равное 2. Значение 2 возвращается первой активации функции Гасгогза1 лля умножения на значение ее паачетра и, равное 3, что дает в результате значение б, которое затем возвращается в лервый вызов функции Йассогда1 в функции пази. 9.3.4. Механизмы реализации нелокальных ссылок Существуют два основных способа доступа к нелокальным переменным в языках со татнческим обзором данных: статические цепочки и индикаторы.
Оба эти способа деишьно изучаются в следующих разделах. Ссылка на нелокальную переменную требует выполнения двухэтапного процесса. Все -елокальные переменные содержатся в существующих экземплярах записей активации и, ;леловательно, находятся где-то в стеке. Для доступа к нелокальной переменной сначала -) жмо найти в стеке экземпляр записи активации, в котором содержится эта переменная. Затем следует использовать ее локальное смешение в экземпляре записи актияацин. Поиск нужного экземпляра записи активации представляет собой более интересную и -. аную проблему. Во-первых. заметим. что в данной подпрограмме видимыми и дос— иными являются только те переменные, которые объявлены в области видимости ста-лческих предков.
Во-вторых, если обращения к переменным статических предков нахочтся во вложенной процедуре, существование экземпляров записей активации всех этих -сезков гарантируется правилами семантики языков со статическим обзором данных: -"оцедуру можно вызвать, только если активны все программные модули. являющиеся :е статическими предками.
Если конкретный статический предок не активен, его локаль-ые переменные не связаны с ячейками памяти, следовательно, открывать доступ к ним -е имеет смысла. Заметим, что, хотя в стеке должен существовать экземпляр активацнонной записи -сеэка, эта запись не обязана соседствовать с экземпляром записи активации его потом. з Эта ситуация проиллюстрирована примером в разделе 9.3.4.1, Семантика ссылок на нелокальные переменные означает. что при поиске переменной =. вложенных областях видимости следует сначала найти ближайшее вложемное объяв'.нне.
Таким образом, лля обеспечения доступа к нелокальным ссылкам мы должны четь возможность находить в стеке все экземпляры активационных записей, соответст= .юших статическим предкам. Это наблюдение приводит к двум методам, описанным в .гезующих разделах. Мы откладываем рассмотрение вопросов, связанных с блоками. ло раздела 9.4, а в тавшейся части раздела 9.3 все области видимости определяются подпрограммами. ..скольку в языках С и С++ вложенные функции не допускаются (блоками создаются -.
лько статические области видимости), все изложенное в данном разделе к этим языкам относится. 9.3. Реализация подпрограмм ма языках, подобных языку АЮ01 Р.З.4.1. Статические цепочки Статическая цепочка — это цепочка статических связей, соединяющих некоторые экземпляры активационных записей в стеке. Во время выполнения процедуры Р статическая связь ее экземпляра активационной записи указывает на экземпляр активационной записи программного модуля, являющегося статическим предком процедуры Р. Статическая связь экземпляра записи активации предка, в свою очередь, указывает на экземпляр записи активации программного модуля, являющегося его статическим предком, если он существует. Таким образом, все статические предки выполняемой подпрограммы связываются в статическую цепочку в порядке ослабления родственных связей (первым является непосредственный предок, за ним— его предок и так далее).
Эту цепочку можно использовать для доступа к нелокальным переменным в языках со статическим обзором данных. Поиск нужного экземпляра записи активации, соответствующего нелокальной переменной, с помощью статических связей становится направленным. Чтобы найти экземпляр активационной записи, содержащий нелокальную переменную, следует в статической цепочке обнаружить экземпляр записи активации статического предка, содержащий эту переменную. Однако это можно сделать намного проще. Поскольку вложенные области видимости во время компиляции известны, компилятор может определить не только ссылку на нелокальную переменную, но и длину статической цепочки, которую нужно отмерить, чтобы достичь экземпляр записи активации, содержащий искомый нелокальный объект.
Будем называть статической глубиной (кайс дерг)з) целое число, связанное со статической областью видимости переменной и указывающее, насколько глубоко вложена эта область в самую внешнюю область видимости. У главной программы в языке Рааса! статическая глубина равна О. Если процедура А определяется только внутри главной программы, то ее статическая глубина равна 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
