А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 92
Текст из файла (страница 92)
Псевдокод для элемента списка с1азз Се11 1 тпс тпто; Се11 цех~; ) определяет рекурсивный тип Се11 как класс, который содержит поле тпго и поле пехс типа Се11. Подобные рекурсивные типы могут быть определены в С с использованием записей и указателей. Методы, описанные в этой главе, переносятся и на рекурсивные типы. 6.3.2 Эквивалентность типов Когда два выражения типов эквивалентны? Многие правила проверки типов имеют вид "если два выражения типов эквивалентны, то вернуть некоторый тип, иначе сообщить об ошибке". Потенциальные неоднозначности возникают, когда имена, назначаемые выражениям типов, затем используются в последующих выражениях типов.
Ключевой вопрос состоит в том, является ли имя в выражении типа именем или оно представляет собой сокращение для другого выражения типа. Если выражения типов представлены графами, два типа структурно эквивалентны тогда и только тогда, когда выполняется одно из следующих условий. ° Они представляют собой один и тот же фундаментальный тип. ° Они образованы путем применения одного и того же конструктора к структурно эквивалентным типам.
° Один тип представляет собой имя, обозначающее другой тип. Если имена типов рассматривать как обозначающие сами себя, то первые два условия в приведенном списке приводят к именной эквивалентности выражений типов. 462 Глава 6. Генерация промежуточного кода При использовании алгоритма 6.3 выражения, эквивалентные в смысле имен, получают одинаковые номера значений. Структурная эквивалентность может быть проверена с использованием алгоритма унификации из раздела 6.5.5.
6.3.3 Объявления Будем рассматривать типы и объявления с использованием упрощенной грамматики, которая объявляет имена по одному; объявления со списками имен могут обрабатываться так, как рассматривалось в примере 5.10. Грамматика выглядит следующим образом: Р ~ Т 1г) 1 Р Т вЂ” В С ! гееоп1 '1' Р ')'  — 1пг ~ аоаг С вЂ” е )1ппщ1 С Фрагмент приведенной выше грамматики, который работает с фундаментальными типами и массивами, использовался для иллюстрации наследуемых атрибутов в разделе 5.3.2.
Отличие в этом разделе заключается в том, что мы рассматриваем как сами типы, так и размещение в памяти. Нетерминал Р генерирует последовательность обьявлений. Нетерминал Т генерирует фундаментальные типы, массивы и записи. Нетерминал В генерирует один из фундаментальных типов 1пт н аоак Нетерминал С (компонент) генерирует строки из нуля или нескольких целых чисел, каждое из которых размещено в квадратных скобках. Тип массива состоит из фундаментального типа, определяемого В, за которым следуют компоненты массива, определяемые нетерминалом С. Тип записи (вторая продукция для Т) представляет собой последовательность объявлений полей записи, заключенную в фигурные скобки.
6.3.4 Размещение локальных имен в памяти Исходя из типа имени можно определить количество памяти, требующееся для данного имени в процессе выполнения программы. Во время компиляции эти величины могут использоваться для назначения каждому имени относительного адреса. Тип и относительный адрес хранятся в записи таблицы символов для данного имени. Данные переменной длины, такие как строки, или данные, размер которых невозможно определить до начала работы программы, такие как динамические массивы, обрабатываются путем резервирования известного фиксированного количества памяти для указателя на данные.
Управление памятью во время выполнения программы рассматривается в главе 7. Предположим, что память состоит из блоков смежных байтов, где байт представляет собой наименьшую единицу адресуемой памяти. Обычно байт состоит 463 6.3. Типы н объявления Выравнивание адресов На размещение в памяти объектов данных сильно влияют ограничения на адреса, имеющиеся у целевой машины. Например, команда сложения целых чисел может ожидать, что эти целые числа выровнены (а118пед), т.е. размещены в определенных позициях памяти, как, например, по адресу, делящемуся на 4. Хотя массив из 10 символов требует достаточного количества памяти для хранения 10 символов, компилятор может выделить для него 12 байт— очередное кратное 4 число, — оставляя неиспользованными 2 байта. Такая память, остающаяся неиспользованной из-за выравнивания, называется заполнением (радйпй).
Когда вопросы экономии памяти выходят на первый план, компилятор может упаковать данные так, чтобы заполнения не было, однако при этом в процессе работы программы могут потребоваться дополнительные команды для позиционирования упакованных данных с тем, чтобы программа могла работать с ними так, как если бы они были корректно выровнены. из восьми битов, а несколько байтов образуют машинное слово. Многобайтные объекты хранятся в памяти в последовательных байтах, и адрес объекта представляет собой адрес его первою байта. Размер (ск(гйЬ) типа равен количеству единиц памяти, необходимому для хранения объекта данного типа. Фундаментальные типы, такие как символы, целые числа и числа с плавающей точкой, требуют целого количества байтов.
Для простоты обращения память для агрегатов, таких как массивы и классы, выделяется в виде одного непрерывного блока байтова, Схема трансляции (СУТ) на рис. 6.15 вычисляет типы и их размеры для фундаментальных типов и массивов; записи будут рассматриваться в разделе 6.3.6. СУТ использует синтезируемые атрибуты 1уре и нЫй для каждого нетерминала и переменные 1 и го для передачи информации о типе и размере от узла В в дереве разбора к узлу продукции С вЂ” щ В синтаксически управляемом определении 1 и и представляют собой наследуемые атрибуты С.
Тело Т-продукции состоит из нетерминала В, действия и нетерминала С, который показан в следующей строке. Действие между В и С устанавливает 1 равным В.гуре, а зо — равным В.иЫггг. Если  — !пг, то В.0ре устанавливается равным злгедег, а В.зггой — равным 4, размеру целого числа. Аналогично если  — йоат, то В 0ре становится равным г)оай а В.иЫгп — 8, размеру числа с плаваюгцей точкой. Распределение памяти длл указателей а С н С-ь+ упрощается, если асе указателя имеют олинакоаыс размеры.
Причина этого а том, что память длл указателей может быть выделена до того, как станет известен тнп объекта, на который он может указывать. 464 Глава 6. Генерация промежуточного кода ( 1 = В.1уре; и = ВмЫ1Б; ) Т вЂ” В В - 1пт  — 1)оа1 С вЂ” ~ е ( В.1уре = !л1едег; В.ыЫ1!1 = 4; ) ( Влуре =Яоа1; В тчЫй = 8; ) ( С.1уре = 1; С.н Ы1Ь = 1е; ) С вЂ” ( пшп ) С1 ( аггау(пнш.ча!ие, С1.1уре); СлтЫ1!1 = пнш.ча!ие х Ст мЫ1)з; ) Рис. 6.15. Вычисление типов и нх размеров Пример 6.9. Дерево разбора для выражения зп~ [2) ( 3) показано на рис. 6.16 пунктиром.
Сплошные линии показывают, каким образом тип и размер передаются от В вниз по цепочке С при помощи переменных ! и ю, а затем возвращаются вверх по цепочке в виде синтезируемых атрибутов 1уре и нЫ1л. Переменные 1 и ю получают значения В.1уре и ВлчЫй перед тем, как будет исследовано поддерево с узлами С. Значения ! и то используются в узле С вЂ” е для начала вычисления синтезируемых атрибутов вверх по цепочке из узлов С. а 6.3.5 Последовательности обьявлений Языки, такие как С и Ьача, позволяют обрабатывать все объявления в одной процедуре как группу. Эти объявления могут быть рассредоточены в пределах процедуры )ача, но при этом все они обрабатываются в ходе анализа данной Продукции для С определяют, генерирует ли Т базовый тип или тип массива. Если С вЂ” е, то ! становится равным С.1уре, а то — С.н Ы1!1. В противном случае С определяет компонент массива.
Действие для С вЂ” [ ппш ] С1 образует С.1уре путем применения конструктора типа аггау к операндам пшп ча!ие и С1 луре. Например, результатом применения актау может быть древовидная структура наподобие показанной на рис. 6.14. Размер массива получается путем умножения размера элемента на количество элементов массива. Если адреса последовательных целых чисел отличаются на 4, то вычисление адреса для массива целых чисел будет включать умножения на 4.
Такие умножения предоставляют широкие возможности для оптимизации, так что лучше, если начальная стадия компиляции делает их явными. В этой главе мы игнорируем машинно-зависимые вопросы, такие как выравнивание объектов данных на границу слова. 465 6.3. Типы и обьявления аллу(2, аггау(3, (лгехег)) 24 гуре = аггау(2, аггау(3, гагехег)) л(егь = 24 гуре = л(Фм = В ! = (лгехег гуре = гигехег л = 4 ланга =4 !лгехег) (2! (а! е = (лгехег 6=4 Рис.
6. 16. Синтаксически управляемая трансляция типов массивов процедуры. Поэтому можно воспользоваться переменной, скажем, офег, для отслеживания следующею доступного относительного адреса. Схема трансляции на рис. 6.17 работает с последовательностями объявлений вида Т Ы, где Т генерирует тип, как на рис. 6.15. Перед рассмотрением первого объявления значение офе! равно О. Когда встречается новое имя х, оно вносится в таблицу символов со своим относительным адресом, равным текущему значению офе(, которое после этого увеличиваегся на размер х. ( офе! = О; ) Р— Т Ы ! ( (ор.рпг(16.!ехете, Т.(уре, офе!); офе! = о)!Ве(+ Т.ъа((7()(; ) Р( Р Рис. 6. !7. Вычисление относительных адресов объявленных имен Семантическое действие в продукции Р— Т Ы; Р( создает запись таблицы символов, выполняя (ор.рп! (Ы.!ехете, Т.(уре, офе!).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
