А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 91
Текст из файла (страница 91)
Обратите внимание, что временная переменная 1 в действительности в тройке не появляется, поскольку обращения к временным значениям выполняются с использованием их позиций в структуре троек. Преимущество четверок над тройками проявляется в оптимизирующих компиляторах, где зачастую применяется перемещение команд. В случае четверок при перемещении команды, которая вычисляет временное значение 1, не требуется внесение изменений в команды, которые используют 1.
В случае троек обращение к результату операции выполняется с использованием ее позиции, так что перемещение команды может потребовать изменения всех ссылок на ее результат. 456 Глава 6. Генерация промежуточного кода ор агК1 агйг Г ' Г у* Ь ваяя Ь яшвя с с б) Тройки а) Синтаксическое дерево Рнс. 6.1!.
Представления а = Ь * — с+ 6 * — с Зачем нужны команды копирования Простой алгоритм трансляции выражений генерирует для присваиваний команды копирования, как на рис. 6.10, а, где Кв копируется в а вместо непосредственного присваивания сг + с4 переменной а. Каждое подвыражение обычно получает собственную новую переменную для хранения его результата, и только при обработке оператора присваивания = становится известно, куда следует поместить значение полного выражения.
Проход оптимизации, возможно, с использованием ориентированного ациклического графа из раздела 6.1.1 в качестве промежуточного представления может определить, что переменная гз может быть заменена на а. Эта проблема не возникает прн использовании косвенных троек, которые будут рассмотрены далее. Косвенные тройки состоят не из списка самих троек, а из списка указателей на тройки. Например, используем массив 1лзггисйол для перечисления указателей на тройки в требуемом порядке. Тогда тройки на рис.
6.11, б могут быть представлены так, как показано на рис. 6.12. При использовании косвенных троек оптимизирующий компилятор может перемещать команды путем переупорядочивания списка 1лз1гисйол, никак не влияя на сами тройки. При реализации на 1ача массив объектов команд аналогичен представлению с косвенными тройками, поскольку зача рассматривает массив элементов как ссылки на объекты. 457 6.2. Трехалресный код 1пвь"исаоп ор аг81 агяз Рис. 6.12. Представление трехадресного кода с приме- нением косвенных троек 6.2.4 Представление в виде статических единственных Присваиваний Представление в виде статических единственных присваиваний 1СЕП) является промежуточным представлением, которое облегчает некоторые из оптимизаций кода.
СЕП отличается от трехадресного кода. Первое отличие заключается в том, что все присваивания в СЕП выполняются для переменных с различными именами; отсюда следует название единсгпвенного присваивания. На рис. 6.13 показана одна и та же промежуточная программа в трехадресном коде и в виде статических единственных присваиваний. Обратите внимание на индексы, которые отличают каждое определение переменных р н Ч в СЕП-представлении.
р= а+Ь Ч=Р Р=Ч* рз =а+Ь Ч1 = р| — с Рз Ч1 * с1 р=е — р Рз = е — Рг Ч=Р+Ч а) Трехадресный код Чз = Рз + Ч1 б) СЕП-представление Рнс. 6.13. Промежуточная программа в виде трехадресного кода н в виде СЕП-представленвя Одна и та же переменная может быть определена в программе в двух разных путях потока управления. Например, исходная программа 35 36 37 38 39 40 1Е ( Й1ад ) х -1; е1не х = 1; у=х*а; Глава 6. Генерация промежуточного кода содержит два пути потока управления, в которых определяется переменная х. Если воспользоваться различными именами для х в истинной и ложной частях условной конструкции, то какое имя должно использоваться в присваивании у = х * а? Здесь в игру вступает второе отличие СЕП. СЕП использует для комбинации двух определений х соглашение о записи, именуемой ф-функцией: 1й(й1ад)х1=-1;е1вех2=1; хз = ф(х1, х2) 1 Здесь ф [х1, х2) имеет значение х1, если поток управления проходит по истинной части условной конструкции, и х2 — если по ложной части.
Иначе говоря, ф-функция возвращает значение своего аргумента, соответствующее пути потока управления, который был пройден до команды присваивания с участием ффункции. 6.2.5 Упражнения к разделу 6.2 Упражнение 6.2.1. Транслируйте выражение а + — [6 — с) в а) синтаксическое дерево; б) четверки; в) тройки; г) косвенные тройки. Упражнение 6.2.2. Повторите упражнение 6.2.1 для следую1цих инструкций при- сваивания: 1) а = Ь[1) + с[Э) й) а[1) = Ь*с — Ь*с) 1й) х = й(у+1) + 2 Ы) х = *р + г,у ! Упражнение 6.2.3.
Покажите, как преобразовать последовательность трехадресных кодов в последовательность, в которой каждая определяемая переменная получает уникальное имя. 459 6«к Типы н объявления б.З Типы и объявления Применение типов может быть разбито на две группы. ° Проверка типов использует логические правила для того, чтобы судить о поведении программы при ее выполнении. В частности, проверяется, что типы операндов соответствуют типам, требующимся для данного оператора. Например, оператор йй в Зама требует, чтобы оба его операнда были булевыми; результат также должен принадлежать этому типу. ° Прииенение в трансляции.
По типу переменной компилятор может определить, какое количество памяти требуется для данного имени в процессе выполнения программы. Информация о типе необходима, помимо прочего, также для вычисления адреса при обращении к элементу массива, для вставки явного преобразования типов и для выбора верной версии арифметического оператора. В этом разделе мы рассмотрим типы и размещение в памяти имен, объявленных в процедуре или классе.
Реальное распределение памяти для вызова процедуры или объекта происходит во время работы программы, когда вызывается процедура или создается объект. Однако при рассмотрении локальных объявлений во время компиляции можно определить относительные адреса имен или компонентов структур данных, которые представляют собой смещение от начала области данных. 6.3.1 Выражения типов Типы имеют структуру, которую мы представим с использованием выражений типов ([уре ехргезз1опз).
Выражение типа либо представляет собой фундаментальный тип, либо образуется путем применения оператора, называющегося конструктором типа, к выражению типа. Множество фундаментальных типов и конструкторов зависит от конкретного языка. Пример 6.8. Тип массива хпс [21 [31 можно прочесть как "массив из 2 массивов из 3 целых чисел каждый" и записать как выражение типа а««ау(2, а««ау(3, [пгеяе«)). Этот тип представлен деревом на рис. 6.14. Оператор а««ау принимает два параметра, число и тип.
Мы будем использовать следующее определение выражений типа. ° Фундаментальный тип является выражением типа. Типичные фундаментальные типы языка включают Ьоо[еап, сйа«, тге8е«и кои[; последний тип означает "отсутствие значения". ° Имя типа является выражением типа. 460 Глава 6. Генерация промежуточного кода ап ау мгеяег Рис.
6.14. Выражение типа для Ель[21[31 ° Выражение типа может быть образовано путем применения конструктора типа ап.ау к числу и выражению типа. ° Запись представляет собой структуру данных с именованными полямн. Выражение типа может быть образовано путем применения конструктора типа гесогс[ к именам полей и их типам. Типы записи будут реализованы в разделе 6.3.
6 путем применения конструктора гесогс[ к таблице символов, содержащей записи для полей. ° Выражение типа может быть образовано путем использования конструктора — для типов функций. Запись а — 1 означает "функция, принимающая тип в и возвращающая тип Г. Типы функций будут полезны при проверке типов, которая рассматривается в разделе 6.5. ° Если л и г являются выражениями типов, то их декартово произведение л х 1 представляет собой выражение типа. Произведения введены для полноты; они могут использоваться для представления списка илн кортежа типов [например, параметров функции). Будем считать, что оператор х левоассоциативен и что он имеет более высокий приоритет, чем — . ° Выражения типов могут содержать переменные, значениями которых являются выражения типов.
Переменные типов, сгенерированные компилятором, будут использоваться в разделе 6.5.4. Удобным способом представления выражений типов является использование графов. Метод номера значения из раздела 6.1.2 может быть адаптирован для построения ориентированного ациклического графа для выражений типов, внутренние узлы которого соответствуют конструкторам типов, а листья — фундаментальным типам, именам типов и переменным типов; см., например, дерево на рис.
6.14з. Поскольку имена типов обозначают выражения типов, они могут приводить к неявным циклам [см. врезку "Имена типов и рекурсивные типы"). Если ребра к именам типов перенаправлены к выражениям типов, обозначаемым этими именами, то получаюгцийся в результате граф может содержать циклы из-за наличия рекурсивных типов. 461 6,3. Типы и объявления Имена типов и рекурсивные типы После определения класса его имя может использоваться в С++ или )аяа как имя типа; например, рассмотрим нос)е из следующего фрагмента программы: рпЬ11с с1азз Нос)е ( ) рпЫтс нос)е и; Имена могут использоваться для определения рекурсивных типов, которые требуются для структур данных, таких как связанные списки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
