А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 85
Текст из файла (страница 85)
Таким образом, если назначение главного атрибута состоит в представлении последовательности команд промежуточного кода, то этот код можно получить путем записи инструкций в конец массива объектов. Конечно, требования, перечисленные в разделе 5.5.2, применимы и к спискам; например, главные атрибуты должны собираться из других главных атрибутов путем конкатенации в соответствующем порядке. возможно, с другими элементами, не являющимися главными атрибу- тами, такими как строки 1аЬе1 или значения меток А1 и А2.
б) Главные атрибуты нетерминалов находятся в правиле в том же порядке, что и сами нетерминалы в теле продукции. Как следствие приведенных условий главный атрибут может быть построен путем добавления в конкатенацию элементов, не являющихся главными атрибутами. Для инкрементной генерации значений главных атрибутов нетерминалов в теле продукции можно основываться на рекурсивных вызовах их функций. Пример 5.22.
Можно модифицировать функцию, приведенную на рис. 5.29, таким образом, чтобы она выводила элементы трансляции Я.соЫе вместо возврата соответствующего значения. Такая измененная функция Я показана на рис. 5.31. На рис. 5.31 Я и С не имеют возвращаемых значений, поскольку их синтезируемые атрибуты генерируются путем печати. Обратите внимание на важность положений инструкций рплп сначала выводится 1аЪе1 Х,1, затем — код для С (который представляет собой то же, что и значение Ссоре на рис. 5.29), затем— 1аЪе1 72 и наконец — код из рекурсивного вызова для д (который представляет собой то же, что и значение Ясоне на рис.
5.29). Таким образом, код, выводимый этим вызовом Я, в точности такой же, как и значение, возвращаемое на рис. 5.29.д Кстати, можно внести те же изменения и в соответствующую СУТ вЂ” превратить построение главного атрибута в действия по выводу элементов этого атрибута. На рис.
5.32 показана СУТ из рис. 5.28, переделанная для генерации кода "на лету". 428 Глава 5. Синтаксически управляемая трансляция чо/й о'(1аЬе1 пехг) ( !аЬе1 Ы, 2,2; /* Локальные метки */ Н ( Текущий символ = токен тчЬНе ) ( Перемещение по входному потоку; Проверить наличие '(' во входной строке и перейти к новой позиции; Ы = пеи(); Т.2 = лен~О; рппг(" 1аЬе1", Ы); С(пехг, Т2); Проверить наличие ')' во входной строке и перейти к новой позиции; рг/пг(" 1аЬе1", Т,2); о(Т,!); е1зе /* Инструкции других видов */ Рнс.
5.3!. Генерация кода для конструкции югб!е синтаксическим анализатором методом рекурсивного спуска "на лету" Я вЂ” ччЬ1!е ( ( Ы = пен О; Е2 = пеи (); С./аие = клех/; С.ггие = Е2; рпп/("1аЪе1", Ы); ) С ) ( Яг.пехг = Ы; рппг("1аЬе1", 1,2); ) Яг Рнс. 5.32. СУТ для генерации "на лету" кода конструкции чч!н!е 5.5.3 Ь-атрибутные СУО и ЬЬ-синтаксический анализ Предположим, что (.-атрибутное СУО основано на 1.(.-грамматике и что мы конвертировали его в СУТ с действиями, вставленными в продукции, как описано в разделе 5.4.5. После этого можно выполнить трансляцию в процессе 1.(.-анализа путем расширения стека синтаксического анализатора таким образом, чтобы он хранил действия и некоторые данные, необходимые для вычисления атрибутов. Обычно данные представляют собой копии атрибутов. В дополнение к записям, представляющим терминалы и нетерминалы, стек синтаксического анализатора хранит записи действий (лег|оп-гесогЖ), представляющие выполняемые действия, и записи синтеза (зупгйез|ге-гесогг(з) для хранения синтезируемых атрибутов нетерминалов.
Управление атрибутами в стеке осуществляется в соответствии со следующими принципами. 429 5.5. Реализация Е-атрибутных СУО ° Наследуемые атрибуты нетерминала А помещаются в записи стека, представляющей данный нетерминал. Код для вычисления атрибутов обычно представляется записью действий непосредственно над записью стека для А; в действительности преобразование Е-атрибутного СУО в СУТ гарантирует, что запись действия будет находиться непосредственно над А.
° Синтезируемые атрибуты нетерминала А размещаются в отдельной записи синтеза, которая находится в стеке непосредственно под записью для А. Данная стратегия размещает записи различных типов в стеке синтаксического анализа, полагая, что такие вариантные типы записей корректно обрабатываются как подклассы класса "зались стека'*. На практике можно скомбинировать несколько записей в одну, но, пожалуй, пояснить идеи будет проше, если данные для различных целей будут храниться в различных записях. Записи действий содержат указатели на выполняемый код. Действия могут также появляться и в записях синтеза; эти действия обычно размещают копии синтезируемых атрибутов в других записях ниже по стеку, где значения этих атрибутов потребуются после того, как запись синтеза и ее атрибуты будут сняты со стека.
Бегло взглянем на ЬЕ-синтаксический анализ, чтобы понять необходимость создания временных копий атрибутов. Из раздела 4.4.4 известно, что управляемый таблицей синтаксического анализа ЕЕ-анализатор имитирует левое порождение. Если ы — входная строка, соответствие которой проверено до текущего момента, то в стеке хранится последовательность грамматических символов а, такая, что Я ~ юо, где Я вЂ” стартовый символ. Когда синтаксический анализатор выполняет 1тп раскрытие с использованием продукции А — В С, он заменяет А на вершине стека на В С. Предположим, что нетерминал С имеет наследуемый атрибут Сл.
В силу продукции А — В С наследуемый атрибут С.г может зависеть не только от наследуемых атрибутов А, но и от всех атрибутов В. Таким образом, перед тем, как вычислять атрибут Сл, следует полностью обработать В. Значит, все необходимыс для вычисления С.г атрибуты должны быть сохранены в записи действий, которые вычисляют С.г. В противном случае, когда синтаксический анализатор заменит А на вершине стека на В С, наследуемые атрибуты А просто исчезнут вместе с соответствуюшими записями в стеке.
Поскольку лежащее в основе СУΠ— Е-атрибутное, это гарантирует, что значения наследуемых атрибутов А доступны, когда А оказывается на вершине стека. Следовательно, эти значения доступны в момент копирования в записи действий, которые вычисляют наследуемые атрибуты С. Кроме того, нет никаких проблем с памятью для синтезируемых атрибутов А, так как они находятся в записи син- 430 Глава 5. Синтаксически управляемая трансляция теза, которая при раскрытии с использованием продукции А — В С остается в стеке, ниже В и С.
При обработке В можно выполнить действия (с помощью записи, находящейся в стеке непосредственно над В), которые копируют его наследуемые атрибуты для использования нетерминалом С, а после того, как В обработан, запись синтеза для В может скопировать его синтезируемые атрибуты для использования при необходимости нетерминалом С. Аналогично синтезируемые атрибуты А могут потребовать для вычисления их значений временных переменных, которые могут быть скопированы в запись синтеза для А после обработки В, а затем С. Вот общий принцип, который обеспечивает работоспособность всех описанных копирований атрибутов.
° Все копирования выполняются между записями, которые создаются в процессе одного раскрытия одного нетерминала. Таким образом, каждая из этих записей знает, где именно ниже в стеке находится каждая другая запись, и может безопасно копировать в них необходимые значения. Приведенный далее пример иллюстрирует реализацию наследуемых атрибутов в процессе 1.1.-синтаксического анализа путем аккуратного копирования значений атрибутов. В приведенном примере возможны сокращения и оптимизации, в частности в случае правил копирования, состоящих в присваивании значения одного атрибута другому. Однако пока что мы отложим этот вопрос до примера 5.24, в котором иллюстрируются записи синтеза. Пример 5.23. В этом примере реализуется представленная на рис.
5.32 СУТ, "на лету" генерирующая код для конструкции туЫ1е. В этой СУТ нет синтезируемых атрибутов, не считая фиктивных атрибутов, представляющих метки. На рис. 5.33, а показана ситуация, в которой для раскрытия Я используется продукция туЫ!е, поскольку очередным символом во входном потоке оказался символ иЫ!е. Запись на вершине стека — это запись для Я, которая содержит только наследуемый атрибут Б.пехб который, будем считать, имеет значение х.
Поскольку здесь выполняется нисходящий синтаксический анализ, вершина стека в соответствии с ранее принятыми соглашениями показана на рисунке слева. На рис. 5.33, 6 показана ситуация непосредственно после раскрытия Я. Перед нетерминалами С и Я1 имеются записи действий, соответствующие действиям лежащей в основе СУТ из рис. 5.32. Запись для С содержит место для наследуемых атрибутов ггие и ГаЬе, а запись для Яп как и все записи для Я, — место для атрибута пехь На рисунке значения этих полей показаны как?, поскольку пока что значения указанных атрибутов неизвестны.
Синтаксический анализатор распознает во входном потоке символы и Ы!е и ( и снимает их записи со стека. Теперь первая запись действий находится на вершине стека и должна быть выполнена. Эта запись содержит поле епехб предназначенное для хранения копии наследуемого атрибута Я.пехп Когда Я снимается 431 5.5. Реализация 1.-атрибутных СУО Вершина стека 5 аехт =х а) Вершина стека Е:~:Л С [ т Д дейстаие 5~ уале =? ап =? ап =? иьае аехт =? пие =? б) Рис.
5.33. Раскрытие Я в соответствии с продукцией для конструкции шЫ1е со стека, значение Б.пех? копируется в поле хпехг для использования в процессе вычисления наследуемых атрибутов С. Код первого действия генерирует новые значения для Ы и х,2, которые мы полагаем равными соответственно у и з. Следующий шаг делает с значением С.ггие.
Присваивание хгас/с ~го1? — 1] .ггие = Е2 записано с учетом знания о том, что оно будет выполняться только в тот момент, когда данная запись действий будет находиться на вершине стека, так что гор — 1 указывает на запись непосредственно под ней, т.е. запись для С. Затем первая запись действий копирует И в поле а11 второго действия, где это значение будет использовано при вычислении Яппехп Она также копирует 1,2 в поле а12 второго действия; это значение необходимо для корректного вывода, выполняемого этим действием.
Наконец, первая запись действий выводит ХаЬе1 у. Ситуация после завершения первого действия и снятия со стека его записи показана на рис. 5.34. Значения наследуемых атрибутов в записи С корректно установлены, как и значения временных переменных аП и а12 во второй записи действий. В этот момент раскрывается С и мы полагаем, что генерируется код, реализуюший этот тест, который содержит переходы к меткам х и с там, где это требуется.
После того как запись для С снимается со стека, на его вершине оказывается запись для ), что заставляет синтаксический анализатор проверять наличие ) во входном потоке. Когда выполняется действие из записи, находящейся в стеке над записью для Яп его код устанавливает $ппехг и выводит 1аЪе1 г. После этого на вершине 432 Глава 5. Синтаксически управляемая трансляция Вершина стека С 1 1 1 1действие 3, ад ге 1 нем=? Еаее г я уаае =к ап =у Рис. 5.34. Стек после завершения дей- ствия, находившегося в стеке над С стека оказывается запись для нетерминала Яы при раскрытии которого, как мы полагаем, выполняется корректная генерация кода, реализующего скрывающиеся за этим нетерминалом инструкции любых типов и переходящего к метке у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
