Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 16
Текст из файла (страница 16)
Обращение кэлементам массива может означать использование операции умножения99при вычислении индексов, что может замедлить исполнение. Наилучшим,по-видимому, является механизм доступа по указателям и использованиефакта магазинной организации памяти в компиляторе. Для этогопроцедура выделения памяти выдает необходимый кусок из подрядидущей памяти, а при выходе из процедуры вся память, связанная с этойпроцедурой, освобождается простой перестановкой указателя свободнойпамяти в состояние перед началом обработки процедуры.
В чистом видеэто не всегда, однако, возможно. Например, локальный модуль в Модуле-2может экспортировать некоторые объекты наружу. При этом схемуреализации приходится "подгонять" под механизм распределения памяти.В данном случае, например, необходимо экспортированные объектывынести в среду охватывающего блока и свернуть блок локального модуля.100Глава 7. Промежуточные представления программыВ процессе трансляции программы часто используют промежуточноепредставление (ПП) программы, предназначенное прежде всего дляудобства генерации кода и/или проведения различных оптимизацийпрограммы. Сама форма ПП зависит от целей его использования.Наиболее часто используемыми формами ПП является ориентированныйграф (или, в частности, абстрактное синтаксическое дерево), тройки,четверки, префиксная или постфиксная запись, атрибутированноеабстрактное дерево.7.1.
Представление в виде ориентированного графаПростейшейформойпромежуточногопредставленияявляетсясинтаксическое дерево программы. Более полную информацию о входнойпрограмме дает ориентированный ациклический граф (ОАГ), в котором водну вершину объединены вершины синтаксического дерева,представляющие общие подвыражения. Синтаксическое дерево и ОАГ дляоператора присваивания a:=b*-c+b*-c приведены на рис. 7.1.На рис.
7.2. приведены два представления в памяти синтаксическогодерева на рис. 7.1.а). Каждая вершина кодируется записью с полем дляоперации и полями для указателей на потомков. На рис. 7.2.б) вершиныразмещены в массиве записей и индексом (или входом) вершины служитуказатель на нее.7.2. Трехадресный кодТрехадресный код- это последовательность операторов вида x:= y op z, гдеx,y и z - имена, константы или сгенерированные компилятором временныеобъекты. Здесь op - двуместная операция, например операция плавающейили фиксированной арифметики, логическая или побитовая.
В правуючасть может входить только один знак операции.101:=:=/\/ \a+/ \/\**/ \/ \/\ /\b- b||||cc/\/ \a+/ \||\ /*/ \/\b||а)cб)Рис. 7.110 :=9ida7+3*8*0id b4id b2-6-1id c5id c0idb1idc2-13*04idb5idc6-57+388*469ida10:=927Рис. 7.2Составные выражения должны быть разбиты на подвыражения, при этоммогут появиться временные имена (переменные). Смысл термина"трехадресный код" в том, что каждый оператор обычно имеет три адреса:два для операндов и один для результата.
Трехадресный код - этолинеаризованное представление синтаксического дерева или ОАГ, вкотором явные имена соответствуют внутренним вершинам дерева или102графа. Например, выражение x+y*z может быть протранслировано впоследовательность операторовt1:=y*zt2:=x+t1где t1 и t2 - имена, сгенерированные компилятором.В виде трехадресного кода представляются не только двуместныеоперации, входящие в выражения. В таком же виде представляютсяоператоры управления программы и одноместные операции.
В этом случаенекоторые из компонент трехадресного кода могут не использоваться.Например, условный операторif A>B then S1 else S2может быть представлен следующим кодом:t:=A-BJGT t,S2.....Здесь JGT - двуместная операция условного перехода, не вырабатывающаярезультата.Разбиение арифметических выражений и операторов управленияделает трехадресный код удобным при генерации машинного кода иоптимизации.Использованиеименпромежуточныхзначений,вычисляемых в программе, позволяет легко переупорядочиватьтрехадресный код.t1 := -ct2 := b * t1t3 := -ct4 := b * t3t5 := t2 + t1a := t5t1 := -ct2 := b * t1t5 := t2 + t2a := t5а)б)Рис.
7.3Представления синтаксического дерева и графа рис. 7.1 в видетрехадресного кода дано на рис. 7.3.а) и 7.3.б), соответственно.Трехадресный код - это абстрактная форма промежуточного кода. Вреализации трехадресный код может быть представлен записями с полямидля операции и операндов. Рассмотрим три реализации трехадресногокода: четверки, тройки и косвенные тройки.103Четверка - это запись с четырьмя полями, которые будем называтьop, arg1, arg2 и result. Поле op содержит код операции. В операторах сунарными операциями типа x:=-y или x:=y arg2 не используется. Внекоторых операциях (типа "передать параметр") могут не использоватьсяни arg2, ни result. Условные и безусловные переходы помещают в resultметку перехода.
На рис. 7.4 приведены четверки для a:=b*-c+b*-c. Ониполучены из трехадресного кода рис. 7.3.а.Обычно содержимое полей arg1, arg2 и result - это указатели навходы таблицы символов для имен, представляемых этими полями.Временные имена вносятся в таблицу символов по мере их генерации.Чтобы избежать внесения новых имен в таблицу символов, навременное значение можно ссылаться, используя позицию вычисляющегоего оператора. В этом случае трехадресные операторы могут бытьпредставлены записями только с тремя полями: op, arg1 и arg2, как этопоказано на рис. 7.4.б.
Поля arg1 и arg2 - это либо указатели на таблицусимволов (для имен, определенных программистом, или констант), либоуказатели на тройки (для временных значений). Такой способпредставления трехадресного кода называют тройками. Тройкисоответствуют представлению синтаксического дерева или ОАГ спомощью массива вершин.Числа в скобках - это указатели на тройки, а имена - это указатели натаблицу символов.
На практике информация, необходимая дляинтерпретации различного типа входов в поля arg1 и arg2, кодируется вполе op или дополнительных полях. Тройки рис. 7.4.б соответствуютчетверкам рис. 7.4.а.op arg1(0)(1)(2)(3)(4)(5)**+:=cbcbt2t5arg2t1t3t4resultop arg1 arg2t1t2t3t4t5a(0)(1)(2)(3)(4)(5)а) четверки**+:=cbcb(1)a(0)(2)(3)(4)б) тройкиРис. 7.4Для представления тройками трехместной операции типа x[i]:=yтребуется два входа, как это показано на рис.
7.5.а, представление x:=y[i]двумя операциями показано на рис. 7.5.б.104oparg1(0) []=(1) :=xarg2I(0)yoparg1 arg2(0) =[] y(1) :=а) x[i]:=yix(0)б) x:=y[i]Рис. 7.5Трехадресный код может быть представлен не списком троек, а спискомуказателей на них. Такая реализация обычно называется косвеннымитройками. Например, тройки рис. 7.4.б могут быть реализованы так, какэто изображено на рис.
7.6.оператор(0)(1)(2)(3)(4)(5)(14)(15)(16)(17)(18)(19)(14)(15)(16)(17)(18)(19)oparg1**+:=cbcb(15)arg2(14)a(16)(17)(18)Рис. 7.6При генерации объектного кода каждой переменной, как временной, так иопределенной в исходной программе, назначается память периодаисполнения, адрес которой обычно хранится в таблице генератора кода.При использовании четверок этот адрес легко получить через эту таблицу.Более существенно преимущество четверок проявляется воптимизирующих компиляторах, когда может возникнуть необходимостьперемещать операторы.
Если перемещается оператор, вычисляющий x, нетребуется изменений в операторе, использующем x. В записи же тройкамиперемещение оператора, определяющего временное значение, требуетизменения всех ссылок на этот оператор в массивах arg1 и arg2. Из-заэтого тройки трудно использовать в оптимизирующих компиляторах.В случае применения косвенных троек оператор может бытьперемещен переупорядочиванием списка операторов. При этом не надоменять указатели на op, arg1 и arg2. Этим косвенные тройки похожи начетверки. Кроме того, эти два способа требуют примерно одинаковойпамяти. Как и в случае простых троек, при использовании косвенныхтроек выделение памяти для временных значений может быть отложено наэтап генерации кода. По сравнению с четверками при использование105косвенных троек можно сэкономить память, если одно и то же временноезначение используется более одного раза.
Например, на рис. 7.6 можнообъединить строки (14) и (16), после чего можно объединить строки (15) и(17).7.3. Линеаризованные представленияВ качестве промежуточных представлений весьма распространенылинеаризованныепредставления.Линеаризованноепредставлениепозволяет относительно легко хранить промежуточное представление навнешней памяти и обрабатывать его в порядке чтения. Самаяраспространенная форма линеаризованного представления - это записьдерева либо в порядке его обхода снизу-вверх (постфиксная запись, илиобратной польской), либо в порядке обхода его сверху-вниз (префикснаязапись, или прямой польской).Таким образом, постфиксная запись (обратная польская) - это списоквершин дерева, в котором каждая вершина следует непосредственно засвоими потомками.
Дерево на рис. 7.1 в постфиксной записи может бытьпредставлено следующим образом:a b c - * b c * + :=В постфиксной записи вершины синтаксического дерева явно неприсутствуют. Они могут быть восстановлены из порядка, в которомследуют вершины и из числа операндов соответствующих операций.Восстановление вершин аналогично вычислению выражения впостфиксной записи с использованием стека.В префиксной записи сначала указывается операция, а затем ееоперанды. Например, для приведенного выше выражения имеем:= a + * b - c * b - cРассмотрим детальнее одну из реализаций префиксного представления Лидер [4].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
