А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 96
Текст из файла (страница 96)
Семантические действия для проверки Š— Е1 + Ез используют две функции. 480 Глава 6. Генерация промежуточного кода в) Расширяющие преобразования б) Сумающие преобрвзоввния Рис. 6.25. Преобразования примитивных типов 3ача 1. Функция глах (с), Ьз) принимает два типа, Ь) и Ьз, и возвращает максимальный из этих двух типов (или их наименьшую верхнюю границу) в иерархии расширения. Она объявляет об ошибке, если либо г), либо гз нет в иерархии, например если тип является массивом или указателем.
2. Функция зозс(еп (а,(,ш) генерирует преобразование типов при необходимости расширения значения по адресу а типа Ь в значение типа и. Если типы Ь и пг совпадают, просто возвращается значение, хранящееся по адресу а. В противном случае генерируется команда, выполняющая преобразование и помещающая результат во временную переменную, которая и возвращается функцией. Псевдокод функции игЫел в предположении, что единственные имеющиеся типы — (лгейег и77оаб показан на рис.
6.26. Айй- зч(с(ел(АйБ. а, Туре Ь, Туре и) И ( Ь = ш ) гетпгп а; е!ае (Г ( г = (л!е8ег апй и =Яоаг ) ( гетр = пеи Тетр(); яеп(гетр '=' '(йоат)' а); гетпгп гетр; е)яе еггог; Рис. 6,26. Псевдокод функции игсгеп Семантическое действие для Š— Е) + Ез на рис, 6.27 иллюстрирует, каким образом преобразования типов могут быть добавлены в схему трансляции выражений на рис.
6.20. В семантическом действии временная переменная а) ДоиЫе ! Тгааг lоое Г ', гяоп сваг Ьуге аоиЫе р )соя сваг и- гьогг ~- Ьуге 481 6.5. Проверка типов представляет собой либо ЕыаИт (если тип Е, не требуется преобразовывать в тнп Е), либо новую временную переменную, возвращаемую функцией наел, если такое преобразование необходимо. Аналогично аз представляет собой либо Ез.аг(ат, либо новую временную переменную, хранящую преобразованное значение Ез. Если оба типа равны (пгеяет или оба типа — )(оад то преобразование не требуется. Однако в общем случае может оказаться, что единственным способом сложить значения двух разных типов является их преобразование в третий тип.
( Е.(уре = так(Е1.(уре, Ез.(уре)' а1 — — треп(ЕыасЫт, Е1.гуре, Е.гуре) аз = нйеп(Ез.аг(г(т, Ез.гуре, Е.гуре); Е.аМт = пезч Тетр(); реп(Е.аг(г(т '=' а1 '+' аз); ) Š— Е1 + Ез Рнс. 6.27. Добавление преобразований типов в вычисление выражения 6.5.3 Перегрузка функций и операторов Пример 6.13. Оператор + в 1ача означает либо конкатенацию строк, либо сложе- ние в зависимости от типов его операндов. Перегруженными могут быть н поль- зовательские функции, как в случае чо1с( егг() ( ) чоз.б егг(ЯГгз.пд в) ( Обратите внимание, что выбрать требующуюся функцию егг из двух ее вариантов можно на основании передаваемых функции аргументов. и Ниже приведено правило синтеза типа для перегруженных функций: (Г ( можетиметьтипв, — г„1<( <п,где в; фв, при(~ ) апп г имеет тип вь для некоторого 1 < Й < и, Гпеп выражение ~(г) имеет тип (ь (6. 10) Для разрешения перегрузки на основании типов аргументов к выражениям типа может быть применен метод номера значения из раздела 6.1.2.
В ориентированном ациклнческом графе, представляющем выражение типа, каждому узлу Перегруженный (очег!сайед) символ имеет различные значения в зависимости от контекста. Перегрузка разрешается (гено!чей), когда для каясдого появления имени однозначно определяется его единственное значение. В этом разделе мы ограничимся перегрузкой, которая может быть разрешена путем рассмотрения аргументов функции, как в языке программирования )ача. 482 Глава 6.
Генерация промежуточного кода назначается целочисленный индекс, называющийся номером значения. Применяя алгоритм 6.3, строим сигнатуру узла, состоящую из его метки и номеров значений его дочерних узлов в порядке слева направо. Сигнатура функции состоит из имени функции и типов ее аргументов. Утверждение, что можно выполнить разрешение перегрузки на основании типов аргументов, эквивалентно утверждению, что можно выполнить разрешение перегрузки на основании сигнатур.
Не всегда возможно выполнить разрешение перегрузки, рассматривая только аргументы функции. В языке программирования Аба отдельное подвыражение может иметь множество возможных типов, для выбора единственного среди которых контекст должен предоставлять достаточное количество информации (см. упражнение 6.5.2). 6.5.4 Выведение типа и полиморфные функции Выведение типа полезно в языках наподобие М(., которые строго типизированы, но не требуют объявления имен до их использования.
Выведение типов гарантирует согласованность использования имен. Термин "полиморфность" относится к любому фрагменту кода, который может быть выполнен с аргументами разных типов. В этом разделе мы рассмотрим параметрический полиморфизм, характеризующийся параметрами или переменными типа.
На рис. 6.28 приведен работающий фрагмент программы на языке программирования М(,, в котором определяется функция 1епйй. Тип !еп8й может быть описан как "для любого типа а !елей отображает список элементов типа о на целое число". Тип!еп8й(х) = И пиП(х) тйеп 0 е1яе 1еп8!й(!1(х)) + 1 Рис.
6.28. Программа М1. для определения длины списка Пример 6.14. На рис. 6.28 ключевое слово Тцп указывает определение функции; функции могут быть рекурсивными. Приведенный фрагмент определяет функцию !елей с одним параметром х. Тело функции состоит из условного выражения. Предопределенная функция пиИ проверяет, является ли список пустым, а предопределенная функция !1 (от "1а1Г* — "хвост") возвращает остаток списка после удаления из него первого элемента.
Функция 1еп8й определяет длину, или количество элементов, списка х. Все элементы списка должны иметь один и тот же тип, но функция 1еп8Й может быть применена к спискам с разными типами элементов. В приведенном далее выражении 1еп8!й применяется к спискам двух различных типов (элементы списка заключены в квадратные скобки): 1еп8й ([" впп", "топ", "сне "]) + !елей((10,9,8,7() (6.11) 483 6.5. Проверка типов Список строк имеет длину 3, а список целых чисел — длину 4, так что вычисление выражения (6. ! !) дает 7.
и Использование символа Ч (читается как "для любого типа") и конструктора типа 11зг дает возможность записать тип функции 1елдй как чгг.йтг (а) — ~ тгейег (6. ! 2) Символ Ч представляет собой кваншор всеобщности (цп(кегза! цала!(бег), а переменная, к которой он применяется, называется связанной (Ьоипд) с ннм. Такие переменные могут быть переименованы, если только переименованию подвергаются все вхождения данной переменной. Таким образом, выражение типа Чэ.1иг (17) — тге8ег эквивалентно выражению (6.!2). 0 выражении типа с символом Ч мы будем неформально говорить как о "полиморфном типе". Всякий раз, когда применяется полиморфная функция, ее связанная переменная типа может описывать иной тип. В процессе проверки типов при каждом применении полиморфного типа мы заменяем связанную переменную новой переменной н убираем квантор общности. В следующем примере неформально выводится тнп 1епдгй с неявным применением правил вывода наподобие (6.9), которые повторены ниже: (Т,1 (т) является выражением, тйеп 7" имеет тип а — Д для некоторых о и Д апг! х имеет тип а Пример 6.15.
Абстрактное синтаксическое дерево на рис. 6.29 представляет определение 1елдй на рис. 6.28. Корень дерева с меткой (пп представляет определение функции. Прочие узлы, не являющиеся листьями, можно рассматривать как применения функции. Узел, помеченный +, представляет применение оператора + к паре дочерних узлов. Аналогично узел с меткой П представляет применение оператора Ы к тройке, образованной дочерними узлами (для проверки типов нс имеет значения, что будет вычислена только одна из частей, Феп или е)яе, но не обе).
Из тела функции 1ел8й мы можем вывести ее тип. Рассмотрим узлы, дочерние по отношению к узлу )Т, слева направо. Поскольку ли1! применяется к спискам, к должно быть таковым. Используем переменную гг в качестве заменителя типа элемента списка, т.е. х имеет тип "список гг". Если лиП (а) истинно, то 1ещгй (х) равно О. Таким образом, тип 1еп8й должен быть "функция от списка а, возвращающая целое число". Этот выведенный тип согласуется с использованием функции 1ел8Й в части е(яе,!елдй (11 (х)) + !.
Глава 6. Генерация промежуточного кола пил х аррасу ! !ехям арр!у л х Рис. 6.29. Абстрактное синтаксическое дерево для определения функции на рис. 6.28 Подстановки, экземпляры и унификация Если г представляет собой выражение типа, а Я вЂ” подстановку (отображение переменной типа на выражение типа), то результат последовательной замены всех вхождений каждой переменной типа о в ~ на Я (о) будем записывать как Я(Г). Я(т) называется экземпляром 1. Например, Йх1 (шгедег) представляет собой экземпляр ййг (а), посколыгу это выражение представляет собой результат подстановки Гл~едег вместо а в йз~ (о). Заметим, однако, что тгедег — роа~ экземпляром о — о не является, поскольку подстановка должна заменять все вхождения о одним и тем же выражением типа. Подстановка Я является уннфикаторам выражений типа г1 и 1з, если Я (1з) = Я (1з).
Я является наиболее общим унификатором 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}
