А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 94
Текст из файла (страница 94)
470 Глава 6. Генерация промежуточного кода продукции использует функцию гор.лег для определения адреса идентификатора, представленного И, как и в правилах для продукции Š— И. Я.сое)е состоит из команд для вычисления значения Е в адрес Е.агЫг, после чего следует присваивание с использованием адреса гор.дег(Ыуехете) для данного экземпляра Ы. Пример 6.11. Синтаксически управляемое определение на рис.
6.19 транслиру- ет инструкцию присваивания а = Ь + — сг в последовательность трехадресных команд = га1пца с 02 )э + Ь1 а Ь2 б.4.2 Инкрементная транеляция Я вЂ” ~ Ы = Е; 1 дел( гор.деК162ехете) '=' Е.айй); ) Š— Е1 + Е2 1 Е.агЫг = печк Тетр (); яел1Е.агЫг '=' ЕыагЫг '+' Ет.агЫг): ) — Е1 1 Е.агЫг = петя Тетр О; реп(Е.агЫг '=' 'пнппв' ЕьагЫг); ) ( Ег ) 1 Е.агЫг = Е|.агЫг; ) Ы 1 Ь.ааЫг = гор.дег1 И.1ехете); ) Рис. 6.20. Инкрементная генерация трехадресного кода для выражений Схема трансляции на рис. 6.20 генерирует тот же код, что и синтаксически управляемое определение на рис.
6.19. В случае инкрементного подхода атрибут Атрибуты-коды могут быть очень длинными строками, так что обычно они генерируются инкрементно, как обсуждалось в разделе 5.5.2. Таким образом, вместо построения Е.сойе так, как показано на рис. 6.19, можно расположить действия таким образом, чтобы они генерировали только новые трехадресные команды, как это сделано в схеме трансляции на рис. 6.20. При инкрементном подходе дел не только конструирует трехадресную команду, но и добавляет ее к последовательности уже сгенерированных команд. Эта последовательность может как остаться в памяти для дальнейшей обработки, так и быть инкрементно выведена.
471 6.4. Трансляция выражений сос1е не используется, поскольку существует единственная последовательность команд, создаваемая последовательными вызовами дел. Например, семантическое правило для Š— Е| + Ез на рис. 6.20 просто вызывает дел для генерации команды сложения; команды вычисления Е, в ЕыагЫг и Ез в Ез.аеЫг к этому моменту уже сгенерированы.
Подход, представленный на рис. 6.20, может использоваться также и для построения синтаксического дерева. Новое семантическое действие для Š— Е~ + + Ез создает узел с использованием конструктора: Š— Е1 + Ез 1Е.агЫг = пен Моде (' + ', Еыай1г, Ез.а~Ыг) ) Здесь атрибут аеЫг представляет адрес узла, а не переменной или константы.
6.4.3 Адресация элементов массива Быстрое обращение к элементам массива легко осуществимо, когда они хранятся в блоке смежных ячеек памяти. В С и 1ача элементы массива из и элементов нумеруются как О, 1....., п — 1. Если размер каящого элемента массива равен ю, то 1-й элемент массива А начинается в ячейке Ьаяе+1 х ю (6.2) Здесь Ьазе — относительный адрес памяти, выделенной для массива, т.е. Ьаяе— относительный адрес А [О]. Формула (6.2) обобщается на два и более измерений. В случае двух измерений в С мы записываем элемент 1з в строке 11 как А [11] [1з].
Пусть ю1 — размер строки, а юз — размер элемента в строке. Относительный адрес А [11] [1з] в таком случае может быть вычислен по формуле Ьаяе+ 11 х ю1+ 1з х юз (6.3) В случае й размерностей формула принимает вид Ьаге+ 11 х ю1+1з х юз+ +1ь х юь (6.4) Здесь ю, 1 < 2 < /с, представляет собой обобщение ю1 и юз из (6.3). Относительный адрес может быть вычислен и иначе, с использованием количества элементов и в каждой из размерностей з массива и размера ю = юь одного элемента массива. В случае двух размерностей (т.е.
Ь = 2 и ю = юз) начальная ячейка А [11] [1з] вычисляется как Ьаяе + (11 х пз + 1з ) х ю (6.5) В случае й размерностей тот же адрес, что и в формуле (6.4), вычисляется как Ьазе+ Н . ((г~ х пз+ 1з) х пз+ 1з) .) х пя +)я) х ю (6.6) 472 Глава 6. Генерация промежуточного кода Вообще говоря, массивы не обязаны нумероваться начиная с нулевого элемента. Например, в одномерном массиве элементы могут иметь номера 1ои, 1отн+ 1, ..., Ь)яЬ, а Ьаве может быть относительным адресом элемента А [1ои]. Формула (6.2) для адреса А [г[ при этом заменяется следующей: Ьаве+ (т — !оит) х нт (6.7) у Первый столбец Второй столбец Третий столбец Первая строка Вторая строка б) Постолбцовое размещение а) Построчное размещение Рнс.
6.2). Схемы размещения двумерного массива Можно обобщить построчное и постолбцовое размещение для многих измерений. Обобщение построчной формы заключается в хранении элементов таким образом, что при сканировании блока памяти правый индекс меняется наиболее быстро; постолбцовое размещение, напротив, приводит к наиболее быстрому изменению левого индекса. Выражения (6.2) и (6.7) могут быть переписаны в виде т х и+ с, где подвыражение с = Ьаве — 1отн х ш может быть предвычислено в процессе компиляции. Заметим, что с = Ьате при 1ои = О. Будем считать, что с хранится в записи таблицы символов для А, так что относительный адрес А [г[ получается путем простого добавления т х ш к с. Предвычисления в процессе компиляции могут применяться и для адресов элементов многомерных массивов; см.
упражнение 6.4.5. Однако существует одна ситуация, в которой не может использоваться предвычисление в процессе компиляции: в случае динамического размера массива. Если мы не знаем значений !ото и Ь)ВЬ (или их многомерных обобщений) в процессе компиляции, то не можем вычислить и такие константы, как с. В таком случае формула типа (6.7) должна вычисляться в процессе выполнения программы так, как она записана.
Приведенные выше вычисления адресов основаны на построчной схеме размещения массивов, используемой в С. Двумерный массив обычно хранится одним из двух способов, либо построчно (тото-ша)ог), либо постолбт)ово (со!пшп-ша)ог). На рис. 6.2) показано построчное (а) и постолбцовое (б) размещение массива А размером 2 х 3. Постолбцовое размещение используется в языках семейства Бог)тап.
473 6.4. Трансляция выражений 6.4.4 Трансляция обращений к массиву Главная проблема при генерации кода для обращения к массивам состоит в связывании формул вычисления адресов из раздела 6.4.3 с грамматикой для обращения к массивам. Пусть нетерминал Е генерирует имя массива с последовательностью индексных выражений: Š— Б 1Е] ] Ы ]Е] Как в С и 1ака, будем считать, что наименьший номер элемента массива равен О. Будем вычислять адрес, исходя из размеров с использованием формулы (6.4), а не из количества элементов, как в (6.6). Схема трансляции на рис.
6.22 генерирует трехадресный код для выражений с обращениями к массивам. Она состоит из продукций и семантических действий, представленных на рис. 6.20, к которым добавлены продукции, включающие нетерминал Е. Нетерминал Е имеет три синтезируемых атрибута. 1. Е.агИг обозначает временную переменную, использующуюся при вычислении смещения для обращения к массиву путем суммирования членов 1, х ш, как в (6.4).
2. Е.ап.ау — это указатель на запись таблицы символов для имени массива. Базовый адрес массива Е.апау.Ьахе используется для определения фактичесюго 1-значения ссылки на массив после анализа всех индексных выражений. 3. Е.Оре представляет собой тип подмассива, сгенерированного Е. Считаем, что размер любого типа 1 равен 1.и Ый.
В качестве атрибутов используются типы, а не размеры, поскольку в любом случае потребуется обеспечить проверку типов. Считаем также, что для любого типа 1 значение 1.е1ет дает тип элемента. Продукция Я вЂ” Ы = Е; представляет присваивание переменной, не являющейся элементом массива и обрабатываемой, как обычно. Семантические действия для Я вЂ” Б = Е; генерируют команду индексированного копирования, которая присваивает значение выражения Е ячейке памяти, указываемой ссылкой на массив Е. Вспомним, что атрибут Е.аггау дает нам запись таблицы символов для указанного массива.
Базовый адрес массива — адрес его нулевого элемента — равен Е.аггау.Ьпге. Атрибут Е.а~Ыг обозначает временную переменную, хранящую смещение для обращения к массиву, генерируемому Е. Таким образом, искомая ячейка памяти для обращения к массиву — Е.а«гау.Ьазе [Е.асЫг]. Сгенерированная юманда копирует г-значение из адреса Е.айаг в ячейку памяти для Е. Продукции Š— Е, + Ез и Š— Ы те же, что и ранее.
Семантическое действие для новой продукции Š— Е генерирует код для копирования значения 474 Глава 6. Генерация промежуточного кода Я вЂ” Ы = Е; [ дел[ гор.деН[йЛехете) '=' Е.аййг)' ) Е = Е; [ яеп(1..аййг.Ьазе '[' 1.аййг ']' '=' Е.аййг); ) Š— Е1 + Ев [ Е.аййг = пете Тетр(); яеп(Е,аййг '=' Епаййг '+' Ез.аййг); ) Ы [ Е.аййг = гор.дег(и$Лехете); ) [ Е.айй = пезт Тетр (); ееп(Е.аййг '=' й.аггау.Ьаее '[' Т.аййг ']'); ) [ Й.аггау = гор.Кег[1ЙЛехете); Л Луре = Л .аггауЛуре.е!ет; Ь.аййг = петя Тетр (); яеп(1.аййг '=' Е.аййг 'э' Т.гуре и ]йгЬ)' ) Š— Ы[Е] Т 1 [ Е ] [ Ь.аггау = Т паггау; ЬЛУРе = Ег.ГУРе.е1ет; 1 = петя Тетр (); 1.аййг = пеи Тетр(); яеп(1 '=' Е.аййг '*' Т..гуре иййгЬ) ) яеп(1.аййг '=' Т1.аййг '+' 1); ) Рис. 6.22.
Семантические действия для работы с массивами Пример 6.12. Пусть а — массив целых чисел размером 2 х 3 и пусть с, з и з— целые числа. Тип а — аггау [2, аггау [3, 1пгеяег)). Его размер т равен 24 в предпо- из ячейки памяти, описываемой Ь, в новую временную переменную. Эта ячейка памяти, как указывалось при рассмотрении продукции Я вЂ” Е = Е;, представляет собой Ь.аггау.Ьаяе [Т,.аййг]. Как и ранее, атрибут Е.аггау дает имя массива, а Т,.аггау.Ьазе — его базовый адрес. Атрибут Т,.аййг обозначает переменную, в которой хранится значение смещения. Код для обращения к массиву помещает гзначение из ячейки памяти, которая вычисляется по заданным базовому адресу и смещению, в новую временную переменную, представленную атрибутом Е.аййг.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
