Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 108
Текст из файла (страница 108)
лолжны быть временно улалены, поскольку оии не принадлежат среде ссылок подпрограммы 5()В(. Однако в действительности должен быть удален только один из этих указателей, соответствующий подпрограмме Я()В2. Указатель, соответствующий подпрограмме Я()ВЗ, может оставаться в индикаторе. Ссылки на переменные в подпргнрамме я()В1 не будут использовать индикаторный указатель, соответствующий подпрограмме Я()ВЗ, поскольку переменные подпрограммы Я()ВЗ не видны в подпрограмме ЯВВ1. Таким образом, можно совершенно спокойно оставить этот указатель в индикаторе. Компилятор не будет генерировать код, имеющий доступ к элементам индикатора, находящимся выше элементов, соответствующих текущей активной подпрограмме. Глава 9. Реализация подпрограмм Я!Я Индикатор Стек ИндикатоР ЭЗА — экзеыплир записи итивацин ЭЗА — экэеыппкр эвкиси активации Стек Индикатср Стек Индикатср а]нлтн 4 выэываетвтоЯзвт втсЯцввыэываетЯцвх яцяз аызываетязяз д) яивз вызывает яцят ЗЗА — ыэеыплир записи актитцни Рис.
9.14. Изченеттие индикатора в ситуации, при которой вызывоюигая подпрограмма ичеет большую статическую глубину, чкч вызываемая под- програ ыма (ЦЫ > Рзт)) Р.З. Реапнзацня подпрограмм на языках, подобных языку АкСз01 4з5 Рис. 9.12. Состояние стека и ин- дикатора перед тем, как подпро- грачма 5УВ1 вызовет подпро- грачму 5УВ4 в программе МА1те 4; пунктирные линии ука- зывают на неактивные указатели Рис.
9.13. Состояние стека и ин- дикатора посте того, как подпро- грамма 5УВ1 вызовет подпро- граткчу 5УВ4 в программе 14А114 4 фэд < Рэт)) Пврвывнныв бана нвринвнныв Рис. 9.!5. Хранение переиенных, объявленных в блоке, в случае, когда блоки не рассыатриваются как процедуры без параметров 9.5. Реализация методов динамического обзора данных Существуют, по крайней мере, два вида доступа к иелокальиым переменным в языках с динамическим обзором данных: глубокий доступ и теневой доступ.
Отметим, что ии глубокий, ии теневой доступ ие связаны с понятиями глубокого и теневого связывания. Основное отличие между связыванием и доступом здесь состоит в том, что глубокое и теневое связывания приводят к разным с точки зрения семантики результатам, а глубокий и теневой доступ — иет. мв Гдово 9. Реализация подпрограмм 9.5.1. Глубокий достузз Когда программа на некотором языке с динамическим обзором данных обращается к - ..зокальной переменной, можно выполнить поиск объявления этой переменной в других -: -программах, активных в данный момент. начиная с подпрограммы, вызванной рань- : всех. Эта концепция чем-то напоминает доступ к нелокальным переменным в языках ;: статическим обзором ланных, за исключением того, что отслеживается динамическая, .- .е статическая цепочка.
Динамическая цепочка связывает в одно целое экземпляры за-.сей активации всех подпрограмм в порядке, обратном порядку их активации. Следова-:льно, динамическая цепочка — это именно то, что нужно для доступа к нелокальным -зременным в языках с динамическим обзором данных. Этот метод называется глубоким доступом (аеер ассезз), потому что он может потребовать глубокого поиска в стеке. Рассмотрим следующий пример программы: ркооеапке С; з.пкедек х, гг Ьедхп х: и+ т; а; ркооеацке В; зпседек н, хг Ьедьп а; ркооеапке А; ьпкедек т, н; Ьедхп а; ркооеапке МА1И б; ьпседек ч, иг Ьедхп Эта программа внешне похожа на программу, написанную на языке А~ 601 однако здесь не подразумевается никакой конкретный язык программирования. Предположим, -:то в ходе выполнения программы возникла следующая последовательность вызовов подпрограмм: УА1И б вызывает А . вызывает А А вызывает В В вызывает С На рнс.
9.1б показано состояние стека в ходе выполнения процедуры С после этой последовательности вызовов. Отметим, что в экземпляре активационной записи нет статических связей, которые в языках с динамическим обзором данных не нужны. 9.5. Реализация методов динамического обзора данных Локальная переменнал ЭЗА с Динамическая салль Возврат (а в > Локальная переменная Локальная тмременная Динамическая связь Возврат (а А > Локальная переменная Локальная переменная ЭЗА Динамическая связь Возарат(а л) Локальная переменнал Локальная переменная ЭЗА А Динамическая связь Возарат~ачлтн е~ эи ( Локыьная переменная Локальная переменная ЭЗА — зкземпллр записи актияации Рис.
9.!б. Соололчте сатена програлмтм на языке с динамическим обзора» данных 420 Глава 9. Рвплизпция подпрограмм Рассмотрим обращения к переменным х, ц и тт в процедуре С, Сначала обнаруживается ссылка на переменную х в экземпляре записи активашш процедуры С. Поиск ссылки на переменную ц производится во всех экземплярах активационных записей в стеке, поскольку единственная переменная с этны именем существует только в программе Глд=м б. Для этого приходится отслеживать четыре динамические связи и проверять десять илтен переменных. Ссылка на переменную и обнаруживается в самом последнем по времени создания экземпляре активационной записи процедуры ть (ближайший экземпляр в динамической цепочке). Между методом глубокого доступа к нелокальной переменной в языках с динамическим обзором данных и методом статических цепочек в языках со статическим обзором данных существуют два важных различия.
Во-первых, в языках с линаьтическим обзором данных нельзя во время компиляции определить длину цепочки. по которой производится поиск. Нужно осуществлять поиск во всех экземплярах активациоиных записей в цепочке, пока не обнаружится первый зкзелтпляр, содержащий ссылку на искомую переменную. Это — одна из причин, по которым протраммы на языках с динамическим обзором ланных выполняются медленнее, чем программы на языках со статическим обзором данных. Во-вторых.
активационные записи должны хранить имена переменных : »гчо, чтобы их можно было найти, в зо время как в реализациях языков со стазнче.,".» обзором данных требуется хранить только нх значения. (Имена при статическом -, с не нужны, поскольку все переменные представляются в виде пар (смешсние в не- -че. »»охальное смешение).) 9.5.2. Теневой доступ Теневой поступ (з)»аИочч ассеая) — зто метод, альтернативный с точки зрения реалии .нп. но не семантики. Как указывалось выше. глубокий и теневой лосгуп нчсют иден- чн)ю семантику. При теневом доступе переменные. объявленные в полпрограчмах, не -знптся в их активационных записях.
Г)оскольку прн динамическом обзоре в каждый : мент времени сушествуст. по крайней мере. одна видимая копия переменной с указан- .-:ы именем, можно использовать совершенно другой подход. »)лнн нз вар»шитов:с»е. го зосэупа — - отдельный стек лля каждого имени переменной во всей программе, Ка- ый раз новая переменная с конкретным именем создается с помошью обьявления в - » нше активации полпрограл»мы, и для этой переменной в соответствуюшем стеке выле-кстся ячейка пал»яти. Каждая ссылка на это имя означает ссылку на переменную, нахо:ч ц)юся на вершине стека, связанного с этим именем, посколькч вершина создается по.;.дней. По завершении работы подпрограммы время жизни ее локальных переменных : зканчивается, а стеки.
соответствуюшие их именам. вытазкиваются. Этот метод способ- ..в)ет очень быстрому доступу к переменныч. однако поддержка стеков при входе в —. зпрограммы и выходе из них требует затрат. На рис. 9.)7 показаны стеки, соответствующие переменнь»л» из ранее приведенного : нчера программы в ситуации, аналогичной показанной на рнс. 9 ) 6. Кроме того. при теневом доступе можно использовать центрапьну»о таблицу, в которой :=.и каждого имени переменной, появляюшейся в программе. предусмотрена отлсльная : »едка.
Вместе с каждым элементом этой таблицы хранится бнт, называемый активным, ° оторый указывает. связано лн данное ил»я с какой-то переменной в настояцшй момент. Та- ~ нч образом. любой доступ к любой переменной может быть осушествлен с помошью .мешения в центральной таблице.
Это смешение является статическим. так что доступ =олжен быль быстрым. Реализации языка б)ЧОВО). используют именно этот подход. ч х (В пчвйкак стека указаны имена про»рпммнык модулей. содориощик обнимании переменной) Рис. 9.17. Один из гиетодои исппльзопанил тенепого доступа при ргазизаиии динамического обзора данных Центральная таблица поддерживается довольно просто.
При вызове подпрограммы -ребуется, чтобы все ее локальные переменные были логически размещены в центральной таблице. Если позиция новой переменной в центральной таблице уже является ак- 421 9.5. Реализация методов динамического обзора данных тивной. т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
