А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 95
Текст из файла (страница 95)
475 6.4. Трансляция выражений е.аИг = С, с Папау = а дгуре = тгеяег = азгпу(2, апау(3,!агеяег)) 1 Е. аааг = с Рис. 6.23. Аннотированное дерево разбора для выражения с+а['][2] — * 12 — з * 4 Сз = С1 + С2 С, = а [ Сз ] Са с + С4 Рнс. 6.24. Трехадресный код для выражения с+а [11 [з ] 6.4.5 Упражнения к разделу 6.4 Упражнение 6.4.1. Добавьте к трансляции на рис. 6.19 правила для следующих продукций: а) Е- Е)*Е2', б) Š— +Е1 [унарный плюс). ложении, что размер целого числа равен 4. Тип а [ 1 ] — аггпу [3, (упеяег), а размер ю, = 12. Тип а[1] [з ] — тгеяет.
Аннотированное дерево разбора для выражения с+а[1] [з ] показано на рис. 6.23. Выражение транслируется в последовательность трехадресных команд на рис. 6.24. Как обычно, имя каждого идентификатора используется для обращения к его записи в таблице символов. и 476 Глава 6. Генерация промежуточного кода Упражнение 6.4.2. Повторите упражнение 6.4.1 для инкрементной трансляции на рис. 6.20. Упражнение 6.4.3. Воспользуйтесь трансляцией на рис.
6.22 для следующих при- сваиваний: а) х = а[11 + Ь[31 б) х = а [ 1) [ З ) + Ь [ з.) [ э ) ! в) х = а[Ь[11 [3] [ [с[!с)) ! Упражнение 6.4.4. Преобразуйте трансляцию на рис. 6.22 для обращения к массивам в стиле Рогггап, т.е. к Ы [Е„Ез,..., Е„] в и-мерном случае. Упражнение 6.4.5. Обобщите формулу (6.7) для многомерных массивов и укажите, какие значения могут храниться в таблице символов и использоваться для вычисления смещений. Рассмотрите следующие случаи.
а) Двумерный массив А, хранящийся построчно. Первое измерение имеет индексы от !г до Ьг, второе — от 1з до Ьз. Размер одного элемента массива равен гл. б) То же, что и в п. а, но массив хранится постолбцово. ! в) )е-мерный массив А, хранящийся построчно.
Размер одного элемента массива равен и. з-е измерение имеет индексы от ! до Ь . ! г) То же, что и в п. а, но массив хранится постолбцово. Упражнение 6.4.6. Массив целых чисел А [г,Я имеет индекс ! со значениями в диапазоне от 1 до 10 и индекс у' со значениями от 1 до 20. Размер каждого целого числа — 4 байта. Предположим, что массив А хранится построчно, начиная с байта О. Найдите положения следующих элементов массива: а) А[5,5]; б) А[10,8]; в) А[3,17]. Упражнение 6.4.7. Выполните упражнение 6.4.6, считая, что массив А размеща- ется в памяти постолбцово. Упражнение 6.4.8. Массив действительных чисел А[!, !',)е] имеет индекс ! со значениями в диапазоне от ! до 4, индекс у со значениями от 0 до 4 и индекс Ь со значениями от 5 до 1О. Размер каждого действительного числа — 8 байт.
Предположим, что массив А хранится построчно, начиная с байта О. Найдите положения следующих элементов массива: а) А[3,4,5]; б) А[1,2,7]; в) А[4,3,9]. Упражнение 6.4.9. Выполните упражнение 6.4.8, считая, что массив А размещается в памяти постолбцово. 477 6.5. Проверка типов Символьные размеры типов Промежуточный код должен быть относительно независимым от целевой машины, так что оптимизатор не должен сильно изменяться при замене генератора кода генератором для другой целевой машины. Однако, как показывают вычисления размеров типов, схема трансляции зависит от встроенных фундаментальных типов.
Так, в примере 6.12 предполагается, что размер каждого элемента целочисленного массива — 4 байт. Некоторые промежуточные коды, например Р-код для Рааса!, предоставляют генератору кода определять размер элемента массива, так что промежуточный код не зависит от размера машинного слова. В нашей схеме трансляции мы можем добиться того же эффекта, заменяя значение 4 (размер целого числа) символьной константой. 6.5 Проверка типов Для выполнения проверки типов (гуре спеск)пй) компилятор должен назначить каждому компоненту исходной программы выражение типа.
Затем компилятор должен определить, удовлетворяют ли эти выражения типов набору логических правил, которые называются системой типов исходного языка программирования. Проверка типов потенциально способна находить ошибки в программах. В принципе, любая проверка может выполняться динамически, если целевой код хранит не только значение элемента, но и его тип. Надежная система типов (яоипд гуре яуягеш) устраняет необходимость динамической проверки типов во избежание связанных с ними ошибок, так как позволяет нам статически определить, что такие ошибки не могут возникнуть в процессе работы программы. Реализация языка является строго типизированной, если компилятор гарантирует, что скомпилированная программа будет выполняться без ошибок, связанных с типами.
Идеи проверки типов используются не только для компиляции, но и для повышения безопасности систем, допускающих импорт и выполнение программных модулей. Программы 1аяа компилируются в машинно-независимый байт-код, который включает детальную информацию о типах операций. Импортируемый код перед выполнением проходит проверку, чтобы избежать как случайных ошибок, так и предумышленных злонамеренных действий. 6.5.1 Правила проверки типов Проверка типов может принимать два вида: синтеза и выведения. Синтез типа (гуре яупгЬея)я) строит тип выражения из типов его подвыражений.
Он требует, чтобы имена были объявлены до их использования. Тип Е1 + Ьз определяется 478 Глава б. Генерация промежуточного кода в терминах типов Ез и Ез. Типичное правило синтеза типа имеет вид И Г имеет тип а — г апгз х имеет тип а, Феп выражение Г" (х) имеет тип г (6.8) Здесь т н Г" означают выражения, а л — г — функцию от а, возвращающую г. Это правило для функций с одним аргументом переносится на функции с несколькими аргументами. Правило (6.8) может быть распространено на Ез + Ез путем рассмотрения сложения как применения функции азЫ(Ег, Ез)~. Вьзведеиие цзина (гуре зпГегепсе) определяет тип языковой конструкции из способа ее использования.
Забегая вперед, к примерам из раздела 6.5.4, рассмотрим функцию ппВ, предназначенную для проверки, является ли список пустым. Тогда исходя из использования этой функции пиВ (т) можно сказать, что х должно быть списком. Тнп элементов г неизвестен; все, что мы знаем, — это то, что т должно быть списком элементов некоторого типа, в настоящий момент неизвестного. Говорить о неизвестных типах нам позволяют переменные, представляющие выражения типов. Будем использовать греческие буквы гг,,З,... для переменных типа в выражениях типов.
Типичное правило для вывода типа имеет вид Ы Г (х) является выражением, Феп Г" имеет тип а — Д для некоторых гт и Д апгз х имеет тип гг 6.5.2 Преобразования типов Рассмотрим выражение наподобие з+ г, где х имеет тип числа с плавающей точкой, а з — целочисленный тип. Поскольку представление целых чисел и чисел с плавающей точкой в компьютере различно и для операций с целыми числами и числами с плавающей точкой используются различные машинные команды, компилятору может потребоваться преобразовать один из операндов оператора +, Термин "синтез" будет применяться, даже если при определении типов используется некоторая контекстная информация.
В случае перегруженных функций, когда одно и то же имя относится более чем к одной функции, в некоторых языках программирования может потребоваться рассмотрение контекста Ез + Ез. Выведение типов необходимо в языках наподобие М1., которые проверяют типы, но не требуют объявления имен. В этом разделе мы рассмотрим проверку типов выражений.
Правила для проверки инструкций аналогичны правилам для выражений. Например, мы рассматриваем условную инструкцию "Ы (Е) В;" как если бы это было применение функции К к Е и Я. Используем для обозначения отсутствия значения специальный тип гоЫ. Тогда функция з1' должна применяться к аргументам типа Ьоо1еап и цоЫ; результат ее применения имеет тип коим 479 6.5.
Проверка типов чтобы гарантировать, что оба операнда при выполнении сложения имеют один и тот же тип. Предположим, что целые числа при необходимости преобразуются в числа с плавающей точкой с использованием унарного оператора ( й1оат.) . Например, в приведенном ниже коде для выражения 2*3. 14 целое число 2 преобразуется в число с плавающей точкой: (й1оаГ) 2 тз = г1 * 3.14 Мы можем расширить такие примеры, рассматривая разные версии операторов для целых чисел и для чисел с плавающей точкой, например йпт.* для умножения целых чисел и й1оас* для умножения чисел с плавающей точкой. Синтез типов будет проиллюстрирован путем расширения схемы из раздела 6.4.2 для трансляции выражений.
Введем дополнительный атрибут ЕЛуре, который может принимать значение 1лгеяег или йоак Правило, связанное с продукцией Š— Е1 + Ез, строит псевдокод 1т (е1 луре = тгенег апд ез луре = тгедег) елуре = 1ягедег; е)зе!(' (е1 луре =л)оаг апб езлуре = 1пгедег) При увеличении количества типов, которые могут быть преобразованы, резко растет количество случаев, которые должны быть рассмотрены. Следовательно, для большого количества типов становится важной аккуратная организация семантических действий.
Правила преобразования типов варьируются от языка к языку. Правила языка программирования 1ача, показанные на рис. 6.25, различают расширяющие преобразования, предназначенные для сохранения информации, и сужающие преобразования, которые могут приводить к потере информации. Расширяющие преобразования показаны в иерархии на рис. 6.25, а: любой тип в иерархии может быть расширен до типа, находящегося в иерархии выше. Таким образом, сЬаг может быть расширен до 1лг или роад но не может быть расширен до зЬогк Сужающие правила представлены графом на рис. 6.25, б: тип в может быть сужен до типа г„если в графе имеется путь от в до г. Заметим, что сЬаг, вЬог1 и буге попарно преобразуемы друг в друга.
Преобразование из одного типа в другой называется неявным, если оно выполняется компилятором автоматически. Неявные преобразования типов во многих языках ограничены расширяюшими преобразованиями. Преобразование называется явным, если программист должен что-то написать для того, чтобы такое преобразование было выполнено.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
