А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 28
Текст из файла (страница 28)
2.38. Использование таблицы символов лля трансляции языка с блоками ннместо явного сохранения и восстановления таблиц можно добавить статические операции внесения а стек и снятия со стека риля и рор к классу Епхг. символов образуют стек; восстановление сохраненного значения ~ор снимает со стека объявления в блоке.'з Таким образом, объявления в блоке не видны вне зтого блока.
Объявление, Ыес7л $уре Ы, приводит к новой записи для объявленного идентификатора. Полагаем, что токены $уре и Ы имеют связанные с ними атрибуты, которые представляют собой соответственно тип и лексему объявляемого идентификатора. Нас не интересуют все поля объекта л, но мы полагаем, что у него имеется поле ~уре, которое дает нам тип соответствующего идентификатора. Мы создаем новый объект л и определяем его свойство типа путем присваивания 13б Глава 2. Простой синтаксически управляемый транслятор я.~уре = Фуре.1ехегие. Запись помещается в верхнюю таблицу символов при помощи вызова гор.риг1~ЙЛехете, з). Семантическое действие в продукции уастог — ~ И использует таблицу символов для получения записи, соответствующей идентификатору.
Операция лег выполняет поиск первой записи в цепочке таблиц, начиная с таблицы гор. Полученная запись содержит всю необходимую информацию об идентификаторе, такую, например, как его тип. о 2.8 Генерация промежуточного кода Начальная стадия компилятора строит промежуточное представление исходной программы, на основании которого заключительная стадия генерирует целевую программу. В этом разделе мы рассмотрим промежуточное представление для выражений и инструкций и приведем учебные примеры получения таких представлений. 2.8.1 Два вида промежуточных представлений Как говорилось в разделе 2.1 и, в частности, было показано на рис.
2.4, основными промежуточными представлениями являются: ° деревья, включая деревья разбора и (абстрактные) синтаксические деревья; ° линейные представления, в частности "трехадресный код". С абстрактными синтаксическими деревьями, или просто синтаксическими деревьями, вы встречались в разделе 2.5.1, а в разделе 5.3.1 они будут изучаться более формализовано.
В процессе синтаксического анализа для представления важных программных конструкций создаются узлы синтаксического дерева. В процессе анализа к ним добавляется различная информация в виде атрибутов, связанных с этими узлами. Выбор атрибутов зависит от выполняемой трансляции.
Трехадресный код, в свою очередь, представляет собой последовательность элементарных программных шагов, таких как, например, сложение двух величин. В отличие от деревьев, здесь нет иерархической структуры. Как мы увидим в главе 9, такое представление становится необходимым, если мы намерены выполнять сколько-нибудь существенную оптимизацию кода. В этом случае мы разбиваем длинную последовательность трехадресных инструкций, образующую программу, на "базовые блоки", которые представляют собой последовательности инструкций, всегда выполняющихся одна за другой, без ветвления.
В дополнение к созданию промежуточного представления на начальной стадии проверяется, что исходная программа следует синтаксическим и семантическим правилам исходного языка. Такая проверка называется стаатической; в об- '2.8. Генерация промежуточного кода щем случае "статический" означает "выполняемый компилятором".' з Статическая проверка гарантирует, что определенные виды программных ошибок, включая несоответствие типов, обнаруживаются во время компиляции.
Компилятор может строить синтаксическое дерево одновременно с генерацией трехадресного кода. Однако обычно компиляторы генерируют трехадресный код в то время, когда синтаксический анализатор "делает вид", что строит дерево, ио без явного построения завершенного синтаксического дерева. Вместо этого компилятор хранит узлы и их атрибуты, необходимые для семантических проверок или иных целей, вместе со структурами данных, необходимых для синтаксического анализа. При этом части синтаксического дерева, требующиеся для построения трехадресного кода, оказываются доступными в тот момент, когда это необходимо, но, когда потребность в них отпадает, они уничтожаются.
Детальнее об этом мы поговорим в главе 5. 2.8.2 Построение синтаксических деревьев Сначала мы приведем схему трансляции для построения синтаксических деревьев, а позже, в разделе 2.8.4, покажем, как эта схема может быть модифицирована для получения трехадресного кода вместе с синтаксическим деревом (или вместо него). Вспомним из раздела 2.5.1, что синтаксическое дерево Г Е> Ез представляет выражение, образованное применением оператора ор к подвыражениям, представленным узлами Ег и Ез. Синтаксические деревья могут быть построены для любой конструкции, а не только для выражений. Каждая конструкция представлена узлом, дочерние узлы которого представляют семантически значащие компоненты конструкции.
Например, семантически значащими компонентами цикла майе языка программирования С ъвп1!е ( ехрг ) лгпгг пв противоположность этому "динамический" означает "во время выполнения программы". Многие языки выполняют также определенные динамические проверки. Например, объентно-ориентированные языки программирования наподобие затя иногда должны выполнять проверку типов в процессе выполнения программы, поскольку метод, применяемый к объекту, может зависеть от конкретного подкласса этого объекта. 138 Глава 2. Простой синтаксически управляемый транслятор являются выражение ехрг и инструкция ягпзг.ы Узел синтаксического дерева для такой конструкции содержит оператор, который мы назовем иЫ!е, и имеет два дочерних узла — синтаксические деревья для ех!зг и лпип Схема трансляции, приведенная на рис.
2.39, строит синтаксические деревья для представительного, но очень ограниченного языка выражений и инструкций. Все нетерминалы в схеме трансляции имеют атрибут п, который является узлом синтаксического дерева. Узлы реализованы как объекты класса зУос!е. Класс зУос!е имеет два непосредственных подкласса: Ехрг для выражений всех видов и Еппг для всех видов инструкций. Каждый тип инструкции имеет соответствующий подкласс класса Егтб например, оператор твЫ!е соответствует подклассу И'лз!е.
Узел синтаксического дерева для оператора твЫ1е с дочерними узлами гс и р создается при помощи псевдокода певв И'/з!(е (х, у) Этот псевдокод создает объект класса и'Ые путем вызова конструктора И'Ьз!е, имеющего то же имя, что и имя класса. Параметры конструктора соответствуют операндам в абстрактном синтаксисе, так же как сам конструктор соответствует оператору.
При детальном рассмотрении кода в приложении А будут изучены методы этой иерархии классов; здесь же мы ограничимся только неформальным рассмотрением нескольких методов. Мы по очереди рассмотрим все продукции и правила, показанные на рис. 2.39. Первыми будут рассмотрены продукции, определяющие различные типы инструкций, после чего последуют продукции, определяющие наши ограниченные типы выражений. Синтаксические деревья для инструкций Для каждого вида инструкций в абстрактном синтаксисе определяется свой оператор. Для конструкций, которые начинаются с ключевого слова, в качестве оператора будет использоваться само ключевое слово. Таким образом, существуют оператор твЫ!е для цикла ьтЫ!е и оператор до для цикла до-укЫ!е. Условные конструкции могут обрабатываться путем определения двух операторов, зТе1яе и 11, для инструкции 11 соответственно с частью е!зе и без нее.
В нашем простом учебном языке мы не используем е!яе, так что у нас имеются только инструкции !б Добавление е1яе представляет определенную сложность н будет рассмотрено в разделе 4.8.2. Каждый оператор инструкции имеет соответствующий класс с тем же именем, но с прописной первой буквой; например, оператору 11 соответствует класс !!: Кро- ' Правая скобка служит исклгочитсльно лля отлеления выражения от ннструкпии.
Левая скобка фактически не имеет значения; оиа нужна только лля красоты, поскольку без нее программа иа Г попускала бы наличие нссбалансированныя скобок. 139 2.8. Генерация промежуточного кода р«оегат — Ыос)! ( гепцп Ыос!гт; ) Ыос)г — '(' х1т!в ')' ( Ыос)ги = г1т1жи; ) ( е!твьп = пеяг Яе!! (!!тамп, егт1.п); ) ( х!т!е.п = пиП; ) згт11 — е!т!х1 егт1 Е = пеи Е)о (е1т11.п, ехрг.п); ) =Ы Ыосl! ( ехрг.п = петя Аех!еи ('= ', ге1.п, ехрг,.п); ) ( ехр«.п = ге1.и; ) ехрг — ге1 = ехр«, ге1 ( ге1.п = пеи' !!е1('< ', ге!1.п, агЫ.п) ) ( ге!.п = петя Яе! ('<', ге!ып, ай1.п)' ) ( ге1.и = а<Ы.и; ) «е! — ге!! < а!Ы ге!1 <= а!И агЫ ( агЫ.п = пеи Ор('+',агЫ1.п,гегт.п); ) ( а<И.п = гегт.п; ) а~Ы вЂ” а!И! + 1епи !епи гепи — (е«т! * !ос!о« ( !епи.п = пеяг Ор( а',ге«т1.п,1ас1ог.п); ) !пего« ( !епи.п = !ос!о«.п; ) ~ас1ог — ( ехр«) пигп ( (ас1о«.п = ехрг.п; ) ( (ос!о«.п = печ' Хит (пигп.га1ие); ) Рис.
2.39. Построение синтаксических деревьев для выражений и инструкций ме того,мы определяем подкласс 5ед, который представляет последовательность инструкций. Этот подкласс соответствует нетерминалу грамматики юи!ж Каж- дый из упомянутых классов является подклассом Е!т1, который, в свою очередь, является подклассом Мог!е. ехру; ( х1т1.п П ( ехрг ) е1т11 ( е!т1.п иЬИе ( ехр! ) вон!1 ( е!т1.п до е!т11 ягпйе ( ехрг ) ( х1т1.п ( згтг.п = петч Еиа1 (ехрг.п); ) = петя 1~(ехрг.п,х!т1ып); ) = петя ИЪ!1е (ехр«.п, з1т11.п); ) 140 Глава 2. Простой синтаксически управляемый транслятор Схема трансляции на рис. 2.39 иллюстрирует построение узлов синтаксического дерева. Примером типичного правила может служить правило для инструкции!П х1т1 — зт ( ехрг ) мт11 ( ит1.п = пеи 1~(ехрг.п, я1гп1ь.п) ) Значащими компонентами инструкции И являются ехрг и ит1ь Семантическое действие определяет узел з1т1.п как новый объект подкласса ~~: Код конструктора 1~; не показанный здесь, создает новый узел с меткой (Г и узлами ехргп и хпп1ь а в качестве дочерних.
Выражения не начинаются с ключевого слова, так что для представления выражений, которые являются инструкциями, определен новый класс Ета1, являющийся подклассом Е1т1. Вот соответствующее правило: хлп1 — ехрг 1 ( йт1.п = пеи ета1(ехрг.);; ) Представление блоков в сиитаксических деревьях Оставшаяся конструкция на рис. 2.39 — это блок, который состоит из последовательности инструкций. Рассмотрим правила, относящиеся к блоку: з1п11 — Ыос/с ( Ит1. и = Ыос1сп; ) ЫосК вЂ” '(' з1п11з ') ' ( Ыос(сп = зппсьп; ) Первое правило гласит, что если инструкция представляет собой блок, то она имеет то же синтаксическое дерево, что и блок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
