А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 27
Текст из файла (страница 27)
объявление идентификатора х следует искать путем исследования блоков изнутри наружу, начиная с блока, в котором находится интересующий нас идентификатор з. Пример 2.15. В приведенном далее псевдокоде нижние индексы используются для того, чтобы отличать разные объявления одного и того же идентификатора: !3! 2.7. Таблицы символов Оптимизация таблиц символов для блоков Реализация таблиц символов для блоков может использовать преимущества правила последнего вложения. Вложение гарантирует, что цепочка применяемых таблиц символов образует стек. На вершине стека находится таблица для текущего блока. Ниже в стеке располагаются таблицы охватывающих блоков. Таким образом, таблицы символов могут выделяться и освобождаться с использованием стековых методов.
Некоторые компиляторы поддерживают единую хеш-таблицу доступных записей, т.е. записей, которые не скрыты объявлениями во вложенном блоке. Такая хеш-таблнца обеспечивает, по сути, константное время поиска ценой вставки и удаления записей при входе в блок и выходе из него.
При выходе из блока В компилятор должен отменить все изменения, внесенные в хештаблицу обьявлениями в блоке В. Это можно сделать при помощи вспомогательного стека для отслеживания изменений в хеш-таблице при обработке блока В. 1) ! !п! хы !и! уб 2) ! !п! шз', Ьоо! уз', !п! гз,' 3) шз ''', ''' х! 4) 5) юо ' т1 ' у1 ") ) У2'' ° ''' зз'' Индексы не являются частью идентификаторов; фактически это номера строк объявлений, относящихся к тому или иному идентификатору.
Так, все встречающиеся в фрагменте идентификаторы к находятся в области видимости объявления в строке 1. Появление у в строке 3 относится к области видимости обьявления у в строке 2, поскольку переменная у переобъявлена во внутреннем блоке. Однако появление у в строке 5 находится в области видимости объявления у в строке 1. Появление ы в строке 5, по-видимому, относится к области видимости объявления и вне этого программного фрагмента; индекс О этой переменной означает глобальное или внешнее по отношению к текущему блоку обьявление.
Наконец, переменная з объявлена и используется внутри вложенного блока, но не может использоваться в строке 5, поскольку вложенное объявление применимо только к вложенному блоку. а 132 Глава 2. Простой синтаксически управляемый транслятор Правило последнего вложения для блоков может быть реализовано при помощи цепочек таблиц символов, когда таблица для вложенного блока указывает на таблицу для охватывающего блока.
Пример 2.16. На рис. 2.36 приведены таблицы символов для псевдокода в примере 2.15. Здесь Вг — блок, начинающийся в строке 1, а Вз — блок, начинающийся в строке 2. На вершине рисунка показана дополнительная таблица символов Во для всех глобальных объявлений или обьявлений по умолчанию, предоставляемых языком программирования.
Во время анализа строк 2-4 среда представлена ссылкой на самую нижнюю таблицу символов — для блока Вз. При переходе к строке 5 таблица символов для Вз становится недоступной, и среда ссылается не на нее, а на таблицу символов для блока Вп из которой можно достичь глобальной таблицы символов, но не таблицы символов для блока Вз. о Вк Рис. 2.36. Цепочки таблиц символов для примера 2.15 Реализация цепочки таблиц символов на языке программирования 1ача, показанная на рис. 2.37, определяет класс Епч (от "епч1гопгпепг" — "среда'*)." Класс Епч поддерживает три операции. ° Создание новой таблицы символов. Конструктор Епч1р) в строках 6 — 8 на рис.
2.37 создает обьект Епч с хеш-таблицей ТаЬ1е. Объект вставляется в цепочку при помощи присваивания параметра р полю ргеч. Хотя, строго говоря, цепочку образуют объекты Епч, удобнее говорить о цепочке таблиц. ° Размещение новой записи в текущей таблице. Хеш-таблица хранит пары "ключ — значение", где — ключ представляет собой строку или ссылку на строку; в качестве ключей можно использовать также ссылки на объекты токенов; ""Среда" — еше один термин для коллекции таблиц символов, имеющих отношение к данной точке программы.
133 2.7. Таблицы символов — значение представляет собой запись с типом ЯугаЬо1; код в строках 9 — 11 не требует знания структуры записи, т.е. он не зависит от полей и методов класса ЯувЬо1. ° Получение записи для идентификатора путем поиска в цепочке таблиц, начиная с таблицы для текущего блока. Код для этой операции в строках 12 — 18 возвращает либо запись таблицы символов, либо значение пц11. I l Файл Елцуага 1) рас)саде вувЬо1в; 2) 1врогс 3ача.иг11.*г 3) рцЬ11с с1авв Епч ( 4) рг1часе НавЬГаЬ1е саЬ1ег 5) ргосессег) Епч ргеч; 6) рцЬ11с Епч(Епч р) ( 7) ГаЪ1е = пеи НавЬГаЬ1е()г ргеч = р; 8) ) 9) рцЬ11с чо1с) рцс(Ясгтпд в, ЯувЬо1 вув) ( 10) ГаЬ1е.рцс(в, вув); 11) ) 12) рцЬ11с ЯувЬо1 дес(Ясгупд в) 13) аког( Епч е = Г)ттвг е 1= пц11; е = е.ргеч ) ( 14) ЯувЬо1 коппс( = (ЯупгЬо1)(е.ГаЬ1е.дес(в))г 15) 1й( коппс) 1= пп11 ) гесигп коппс)г 16) 17) геСпгп пп11г 18) ) 19) Рис.
2.37. Класс Епч реализует цепочку таблиц символов 2.7.2 Использование таблиц символов В сущности, роль таблицы символов заключается в передаче информации от объявлений к использованиям. Семантические действия "помещают" информацию об идентификаторе х в таблицу символов при анализе объявления х.
Позже Объединение таблиц символов в цепочки дает в результате древовидную структуру, поскольку в охватывающий блок может быть вложено несколько блоков. Пунктирные линии на рис. 2.36 — это напоминание о том, что связанные в цепочки таблицы символов могут образовывать дерево.
134 Глава 2. Простой синтаксически управляемый транслятор семантическое действие, связанное с продукцией наподобие гас(о« вЂ” Ы, "получает" информацию об идентификаторе из таблицы символов. Поскольку трансляция выражения Е1 ор Ез для типичного оператора ор зависит только от трансляций Е1 и Ез и не зависит непосредственно от таблицы символов, можно добавить любое количество операторов без изменения основного потока информации от объявлений к использованиям через таблицу символов.
Пример 2.17. Схема трансляции на рис. 2.38 иллюстрирует применение класса Епч. Схема трансляции концентрируется на областях видимости, объявлениях и использованиях и реализует трансляцию, описанную в примере 2.!4. Как упоминалось ранее, для входной строки ( з.пг х; сЬаг у; ( Ьоо1 у; х; у; ) х; у; ) схема трансляции удаляет объявления и дает строку ( ( х:1пс; у:Ьоо1; ) х:з.пг; угойаг; ) Тела продукций на рис. 2.38 выровнены так, чтобы грамматические символы находились в одном столбце, а все действия — в другом. В результате компоненты тела продукции часто растягиваются на несколько строк.
Рассмотрим теперь семантические действия. Схема трансляции создает и уничтожает таблицы символов соответственно при входе в блок и выходе из него. Переменная гор означает верхнюю таблицу, располагающуюся в заголовке цепочки таблиц. Первая продукция грамматики — рго8гат — ЫосА. Семантическое действие перед Ыос)) инициализирует переменную гор значением пнй, т.е. никаких записей пока нет.
Вторая продукция, Ыос)) — '('Ыесйатм')', содержит действия при входе в блок и выходе из него. При входе в блок, до ЫесЬ, семантическое действие сохраняет ссылку на текущую таблицу с использованием локальной переменной затеи'. Для каждого применения этой продукции используется своя локальная переменная затеи', отличная от локальных переменных для других применений данной продукции. В синтаксическом анализаторе, работающем по методу рекурсивного спуска, переменная затес( локальна для процедуры Ыос(с Локальные переменные в рекурсивных функциях рассматриваются в разделе 7.2. Код гор = пезт Епт(гор). присваивает переменной (ор вновь созданную таблицу символов, которая соединена с предыдущим значением гор, непосредственно перед входом в блок.
Переменная гор представляет собой объект класса Епт; код конструктора Епт приведен на рис. 2.37. При выходе из блока, после ') *, семантическое действие восстанавливает сохраненное при входе в блок значение переменной гор. По существу, таблицы 2.7. Таблицы символов ( гор = ппП; ) рта агат Ыосй Ыоск ( лаоегг' =!ор; гор = пеи ЕЙ4!ор); рппГ(н ( и); ) ( ~ор = лакее(; рпцз(и ) "); ) с(есЬ латы ') с(есЬ вЂ” г Нес 7л г(ес! е Ас( — 1уре Ы; ( л = пеи Юртой л.~уре = 1уре.lехете гор.риг(Ы.гехете, л); ) хйиЬ вЂ” г линия ХГтГ хстг — г Ыос7г 7асгог ( рпп1(на о); ) ( л = гор.ее~(Ы./ехете); рпцз(И./ехете); рпп!(": "); рппг(лемуре); ) /астор — Ы Рнс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
