А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 90
Текст из файла (страница 90)
6.3, повторен на рис. 6.8 вместе с соответствующей последовательностью команд трехадресного кода. о 62.1 Адреса и команды Трехадресный код построен на основе двух концепций: адресов и команд. В объектно-ориентированных терминах эти концепции соответствуют классам, а различные виды адресов и команд — подклассам. В качестве альтернативы 451 6.2. Трехадресный код Ь вЂ” с с,= с,= а аес, г.,+с, Ь с б) трекадресный код а) Ориентированный ециквический граф Рнс. 6.8. Ориентированный ацнклнческий граф и со- ответствующий ему трехадресный код ° Имя.
Для удобства мы позволяем именам исходной программы появляться в трехадресном коде в виде адресов. При реализации исходное имя заменяется указателем на запись в таблице символов, в которой хранится вся информация об имени. ° Константа. На практике компилятор должен работать со многими различными типами констант и переменных. Преобразования типов внутри выражений рассматриваются в разделе 6.5.2. ° Генерируемые компилятором временные переменные. Оказывается полезным, в особенности в оптимизирующих компиляторах, создание имен, отличающихся друг от друга, всякий раз, когда требуется временная переменная.
Эти временные переменные могут комбинироваться при наличии такой возможности в процессе назначения переменным регистров и памяти. Теперь рассмотрим распространенные трехадресные команды, использующиеся в оставшейся части этой книги. Символьные метки используются в командах, изменяющих поток управления. Символьная метка представляет индекс трехадресной команды в последовательности таких команд.
Фактические индексы могут быть заменены метками либо при дополнительном проходе по коду, либо с использованием метода обратных поправок (Ьас)сра1сЬ1пд), который рассматривается в разделе 6.7. Ниже перечислены наиболее распространенные виды трехадресных команд. 1.
Команды присваивания вида х = у ор с, где ор — бинарная арифметическая или логическая операция, а х, у и е — адреса. трехадресный код может быть реализован при помощи записей с полями для адресов; в разделе 6.2.2 вкратце обсуждаются записи, называющиеся четверками и тройками. Адрес может быть одним из следующего списка. 452 Глава 6.
Генерация промежуточного кода 2. Присваивание вида х = ор у„где ор — унарная операция. Основные унарные операции включают унарный минус, логическое отрицание и операторы преобразования, которые, например, преобразуют целое число в число с плавающей точкой. 3. Команды копирования вида х = у, в которых х присваивается значение у. 4. Безусловный переход дого Ь. После этой команды будет выполнена трех- адресная команда с меткой Ь.
5. Условный переход вида 1й х досо Ь и 1ГРа1ае х досо Ь. Эти команды приводят к тому, что следующей выполняется команда Ь, если значение х соответственно истинно или ложно. В противном случае, как обычно, выполняется команда, следующая за командой условного перехода. 6. Условные переходы вида 1й х ге7ор у досо Ь, которые применяют оператор отношения (<, ==, >= и т.п.) к х и у, и следующей выполняется команда с меткой Ь, если отношение х ге7ор у истинно. В противном случае выполняется команда, следующая за условным переходом.
7. Вызовы процедур и возврат из них реализуются при помощи команд рагат х для передачи параметров; саП р, и и у = саП р,и для вызова соответственно процедур и функций; а также гегигп у, где у — необязательное возвращаемое значение. Обычно они используются в виде приведенной ниже последовательности трехадресных команд: рагат х1 рагат хз рагаж х„ са11 р,и Данная последовательность генерируется в качестве части вызова процедуры р (хы хз,..., х„). Целое число и указывает количество фактических параметров в саП р, и и не является излишним в силу того, что вызовы могут быть вложенными. Иначе говоря, некоторые из первых инструкций рагаж могут быть параметрами для вызова, который будет выполнен после того, как р вернет значение; это значение станет еще одним параметром более позднего вызова.
Реализация вызовов процедур описана в разделе 6.9. 8. Индексированные присваивания вида х = у [г] и х [г[ = у. Команда х = у [г[ присваивает х значение, находящееся в г-й ячейке памяти по отношению 453 6.2. Трехадресный код к у. Команда х [з] = у заносит в з-ю по отношению к х ячейку памяти значение у. 9. Присваивание адресов и указателей вида х = Йу, х = *у и *х = у. Команда х = Йу устанавливает г-значение х равным положению (1-значению) у в памятиг. Предположительно у представляет собой имя, возможно, временное, обозначающее выражение с 1-значением наподобие А]з]]з], а х— имя указателя или временное имя.
В команде х = *у под у подразумевается указатель или временная переменная, г-значение которой представляет собой местоположение ячейки памяти. В результате г-значение х становится равным содержимому этой ячейки. И наконец, команда вх = у устанавливает г-значение объекта, указываемого х, равным г-значению у.
Пример 6.5. Рассмотрим инструкцию с[о з = х+1з зя[зх1е (а[х] < тт)з На рис. 6.9 показаны две возможные трансляции этой инструкции. Трансляция а использует символьную метку 1ч связанную с первой командой. Трансляция б указывает номера позиций команд, произвольным образом начиная отсчет со 100. В обоих случаях последней командой является команда условного перехода к первой команде. Умножение х*8 требуется для массива элементов, каждый из которых занимает 8 единиц памяти. сз 100: с;з = з + 1 101: з. = б, 102: г.г = х * 8 103: ьз = а [ ~г 104: хГ гз < тг доТо 100 б) Номера позиций 1.: Г,=я+1 — 11 — * 8 гз = в [ тг хй Гз < зт до~о Ь а) Символьные метки Рис. 6.9. Два способа назначения меток трехадресным командам 'Ь и т-значения, яак указано в разделе 2.8.3, могут использоваться соответственно в левой и правой частях присваиваний.
Выбор доступных операторов представляет собой важный вопрос при проектировании промежуточного представления. Очевидно, что множество операторов должно быть достаточно богатым для реализации операций исходного языка. Операторы, близкие к машинным командам, облегчают реализацию промежуточного кода на целевой машине.
Однако, если начальная стадия должна генерировать длинные последовательности команд для некоторых операций исходного языка, 454 Глава б. Генерация промежуточного кода то от оптимизатора и генератора кода потребуется большее количество работы для прояснения структуры и генерации эффективного кода для таких операций. 6.2.2 Четверки Описание трехадресных команд определяет компоненты команд каждого вида, но не указывает, как эти команды должны быть представлены в структуре данных. В компиляторе эти команды могут быть реализованы как объекты или как записи с полями для операторов и операндов. Три такие представления называются четверками, тройками и косвенными тройками. Четверка (Чцадгцр!е) имеет четыре поля с именами ор, агн,, агл2 и гези16 Поле ор содержит внутренний код оператора.
Например, трехадресная команда х = у+ г представима путем размещения + в ор, у в азы г в агн2 и х в гези1п Из этого правила имеется несколько исключений. 1. Команды с унарными операторами наподобие х = втхппв у или х = у не используют агн2. Заметим, что в случае команды копирования х = у поле ор равно =, в то время как для большинства других операций оператор присваивания подразумевается неявно. 2. Операторы наподобие рахат не используют ни агл2, ни гези1Л 3. Условные и безусловные переходы помещают в поле гезий целевую метку. Пример 6.6. Трехадресный код для присваивания а=Ь*-с+Ь*-с; показан на рис.
6.10, а. Дпя отличия унарного оператора "минус" (как в случае -с) от бинарного оператора "минус" (как в случае Ь-с) используется специальный оператор жзппв. Заметим, что трехадресная команда унарного минуса использует только два адреса, как и команда копирования а = с5. ор агу, а~уз гези11 ~1 = втхппв с С2=Ъ * сз = п~хпцв с с4=Ь * Ьз Ь5 т2 + Ь4 а =п5 б) Четверки а) Трехадресный код Рис. 6.10.
Трехадресный код и его представление с использованием четверок 455 6.2. Трехалресный код Четверки на рис. 6.10, б реализуют трехадресный код, приведенный на рис. 6.10, а. а Для удобочитаемости на рис. 6.10, б мы использовали в полях агя,, агя и гезий фактические идентификаторы а, Ь и а, а не указатели на соответствующие записи таблицы символов. Временные имена могут быть либо внесены в таблицу символов так же, как и имена, определенные программистом, либо реализованы в виде объектов класса Тетр с собственными методами.
6.2.3 Тройки Тройки состоят только из трех полей — ор, агя, и агяз. Заметим, что на рис. 6.10, б поле гезий используется, в основном, для временных имен. Используя тройки, мы обращаемся к результату операции х ор у по ее позиции, а не при помощи явного временного имени. Таким образом, вместо временной переменной 11 на рис. 6.!О, б представление с использованием троек булет обращаться к позиции (0). Числа в скобках представляют указатели в пределах структуры троек. В разделе 6.1.2 позиции или указатели на позиции получили название "номера значений". Тройки эквивалентны сигнатурам из алгоритма 6.3. Следовательно, ориентированный ациклический граф и представление с использованием троек эквивалентны.
Эта эквивалентность ограничивается выражениями из-за существенного отличия представления потока управления вариантами синтаксических деревьев и трехадресным кодом. Пример 6.7. Синтаксическое дерево и тройки на рис. 6.11 соответствуют трехадресному коду и четверкам на рис. 6.10. В представлении с использованием троек на рис. 6.11, б команда копирования а = сь закодирована в тройке путем размещения а в поле агя, и (4) в поле агяз. а Тернарные операции наподобие х 11] = у требуют двух записей в структуре тройки; например, можно поместить х и 1 в одну тройку, а у — в другую. Аналогично х = у (г] можно реализовать, рассматривая эту операцию так, как если бы это были две команды, 1 = у [1] и х = 1, где 1 — временная переменная, сгенерированная компилятором.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
