А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 110

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 110)

Поскольку все эти три функции определены непосредственно внутри функции с глубиной вложенности 1, их глубины вложенности равны 2. Строки 7 — 11 раскрывают ряд деталей функции ди(с))зогп В строке 8 объявляется локальное значение и — опорный элемент разбиения. В строке 10 предполагается, что функция раггЫоп обращается как к массиву а, так и к опорному элементу н, а также вызывает функцию ехс)зонде. Поскольку функция рагйлоп определена внутри функции с глубиной вложенности 2, ее глубина вложенности 547 7.3. Доступ к нелокальным данным в стеке равна 3.

В строке 11 предполагается, что функция ди1сЬогг' обращается к переменным а и и, функции раппов и рекурсивно к самой себе. Строка 12 предполагает, что охватывающая функция зог! обращается к а и вызывает две процедуры — геаИАггау и уикЬогп и 7.3.5 Связи доступа Непосредственная реализация обычного статического правила области видимости для вложенных функций получается путем добавления к каждой записи активации указателя, называющегося связью доступа (ассеаз 1пй).

Если в исходном тексте процедура р непосредственно вложена в процедуру о, то связь доступа в каждой активации р указывает на последнюю активацию 9. Заметим, что глубина вложенности о должна быть ровно на единицу меньше глубины вложенности процедуры р. Связи доступа образуют цепочку от записи активации на вершине стека к последовательности активаций с монотонно уменьшающимися глубинами вложенности. Вдоль этой цепочки располагаются все активации, данные и процедуры которых доступны для текущей выполняющейся процедуры. Предположим, что на вершине стека находится процедура р, глубина вложенности которой — пр, и р требуется доступ к имени х, представляющему собой элемент, определенный в некоторой процедуре д, которая окружает р и имеет глубину вложенности пч.

Понятно, что пч < пр, причем равенство выполняется, только если р и д — одна и та же процедура. Поиск х начнем с записи активации для р на вершине стека и проследуем по связям доступа от записи активации к записи активации и„— пч раз. Таким образом мы доберемся до записи активации д, и это всегда будет самая последняя (наивысшая) запись активации для 9 из имеющихся в стеке. Эта запись активации содержит искомый элемент х.

Поскольку компилятору известна схема записи активации, х может быть найдено с некоторым фиксированным смещением от позиции в записи активации ц, на которую указывает последняя связь доступа. Пример 7.6. На рис. 7.11 показана последовательность состояний стека, которая может получиться при выполнении функции хогг на рис. 7.10. Как и ранее, имена функций представлены только их первыми буквами; на рисунке представлены некоторые данные, которые могут находиться в различных записях активации, а также связи доступа для каждой записи активации.

На рис. 7.11, а показана ситуация после того, как функция хоп вызвала функцию геа~йггау для загрузки входных данных в массив а и функцию дшс~Ьогг (1, 9) для сортировки массива. Связь доступа ди!сЬогг (1, 9) указывает на запись активации для хогг, но не потому, что хогг вызвала дшсЬогд а потому, что зог! — наиболее близкая вложенная функция, охватывающая дшс~Ьогг в программе на рис. 7.10. В последовательных шагах на рис.

7.!! показаны рекурсивный вызов дшсЬогг11,3), за которым следует вызов функции раггЖол, которая, в свою 548 Глава 7. Среды времени выполнения досзпупа 9)1,9) Связь доступа а) б) в) Рис. 7.! !. Связи доступа для поиска иелокальных данных очередь, вызывает функцию ехс)залпе. Обратите внимание, что связь доступа с7шс)схогг !1, 3) указывает на ю«г по той же причине, что и в случае с7шс)стог) (1, 9), На рис. 7.11, г связь доступа "перепрыгивает" через записи активации з7и)сзсяогг и рагШ)оп, поскольку функция ехсйаще вложена непосредственно в хогг.

Так и должно быть, поскольку ехсйаще требуется доступ только к массиву о, в котором данная функция должна обменять два элемента, определяемые параметрами )и 7. о 7.3.6 Работа со связями доступа Как определяются связи доступа? Простой случай — когда вызов представляет собой вызов некоторой процелуры по явно указанному имени. Более сложная ситуация — когда происходит вызов процедуры, переданной в качестве параметра. В этом случае конкретная вызываемая процедура становится известна только во время выполнения программы и глубина вложенности вызываемой процедуры может отличаться от вызова к вызову.

Давайте сначала рассмотрим случай, когда процедура 7 явным образом вызывает процедуру р. Возможны три ситуации. !. Процедура р имеет большую глубину вложенности, чем з). В таком случае р должна быть определена непосредственно в д, иначе вызов процедурой з7 оказывается не в пределах области видимости имени процедуры р. Таким образом, глубина вложенности процедуры р ровно на единицу больше глу- 7.3. Доступ к нелокальным данным в стеке бины вложенности д и связь доступа должна вести от р к д. В этом простом случае достаточно включить в последовательность вызова шац который помещает в связь доступа р указатель на запись активации д. Примером может служить вызов процедуры дшсЬогг процедурой догу на рис.

7. ! 1, а или вызов процедуры рагйуюп процедурой дшсЬогу на рис. 7.11, и. 2. Вызов рекурсивен, т.е. д = р.з Вэтом случае связьдоступадля новой записи активации та же, что и запись активации ниже нее в стеке. Примером может служить вызов процедуры дите!свот!(1,3) процедурой диусЪашт(1,9) на рис. 7.!1, 6.

3. Глубина вложенности пр процедуры р меньше глубины вложенности ыч процедуры д. Для того чтобы вызов в д находился в области видимости имени р, процедура д должна быть вложена в некоторую процедуру г, а р должна быть процедурой, определенной непосредственно в и, Тогда верхняя запись активации г будет найдена после прохождения пч — пр -' 1 звеньев цепочки связей доступа, начинающейся в записи активации д. После этого связь активации р должна вести к упомянутой активации г.~ Пример 7.7.

В качестве примера третьей ситуации рассмотрим переход от рис. 7.!1, в к рис. 7.11, г. Глубина вложенности вызванной функции ехс1запле равна 2, что на единицу меньше глубины вложенности вызывающей функции риг11йоп, равной 3. Таким образом, мы начинаем с записи активации для ригШюп и проходим по 3 — 2 + 1 = 2 связям доступа, что приводит нас от записи активации для рагШюп через запись активации дшс!!дог! (1, 3) к записи активации яогп Следовательно, связь доступа для ехсйапде должна вести к записи активации для гюгд что мы и видим на рис.

7.11, г. Эквивалентный способ состоит в следовании по и„— п„звеньям цепочки связей доступа с последующим копированием связи доступа из найденной записи активации. В нашем примере мы должны пройти одно звено цепочки, попадая в запись активации для ди1сЬог! (1, 3), после чего скопировать из нес связь доступа, ведущую к хогг. Обратите внимание, что эта связь оказывается корректной для процедуры ехгйигзле, несмотря на то, что последняя находится вне области видимости дшс/сгогд являясь для нее "братской" функцией по вложенности в гюгп ы 'В М1.

возможны взаимно рекурсивные функции, обрабатываемые аналогично. Правило из третьей ситуации распространяется и на случай, когда и = пч, те. котла вьповы не взаимно рекурсивны, но находятся на одном уровне ыюжснности. Таким образом, ситуация 2 по сути является частным случаем ситуации 3. — Прим. лед. 550 Глава 7. Среды времени выполнения 7.3.7 Связи доступа для процедур, являющихся параметрами Когда процедура р передается процедуре д в качестве параметра, а затем процедура д вызывает этот параметр (таким образом вызывая р в данной активации ц), вполне возможно, что д не известен контекст, в котором р появляется в программе. Если это так, то д не известно, как установить связь доступа для р.

Решение этой проблемы в следующем: при использовании процедуры в качестве параметра вызывающая процедура должна передать наряду с именем процедуры корректную связь доступа. Вызывающей процедуре всегда известна эта связь, поскольку, если р передается процедурой г как фактический параметр, р должна быть именем, доступным для г, а следовательно, г может определить связь доступа для р так же, как если бы эта процедура была вызвана ею непосредственно, т.е. с использованием правил для построения связи доступа из раздела 7.3.6. Пример 7.8. На рис.

7.12 приведен набросок МЬ-функции а, которая имеет вложенные функции б и с. Функция 6 получает параметр-функцию 1, которую затем вызывает. Функция с определяет в себе функцию г(, а затем вызывает б, передавая ей фактический параметр д. 1цп а(х) 1ее йцп Ъ(й) йпп с(у) 1ес йип с)(г) з.п Ъ(с)) епс( тп с(1) епг) ! Рис.

7. ! 2. Набросок программы МЬ, использующей передачу функции в качестве параметра Рассмотрим, что происходит при выполнении а. Сначала а вызывает с, так что мы размещаем запись активации для с в стеке над а. Связь доступа для с указывает на запись для а, поскольку с определена непосредственно в а. Затем с вызывает б (0). Последовательность вызова настраивает запись активации б так, как показано на рис.

7.! 3, а. 551 7.3. Доступ к нелокальным данным в стеке б) Рнс. 7.! 3. Фактический параметр включает связь доступа В этой записи активации находится фактический параметр Н и его связь доступа, которые вместе образуют значение формального параметра 7" в записи активации для Ь. Заметим, что функция д известна функции с, поскольку д определена в с, а следовательно, с передает в качестве связи доступа указатель на собственную запись активации. Не имеет значения, где именно была определена й; если с находится в области видимости этого определения, то должно быть применимо одно из трех правил раздела 7.3.6 и с может предоставить необходимую связь доступа.

Характеристики

Список файлов книги