В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 29
Текст из файла (страница 29)
Смысл термина «трехадресный код» в том, что каждый оператор обычно имеет три адреса: два дляоперандов и один для результата. Трехадресный код — это линеаризованноепредставление синтаксического дерева или ОАГ, в котором временные именасоответствуют внутренним вершинам дерева или графа. Например, выражение x + y ∗ z может быть протранслировано в последовательность операторовt1 := y * zt2 := x + t1где t1 и t2 — имена, сгенерированные компилятором.В виде трехадресного кода представляются не только двуместные операции, входящие в выражения. В таком же виде представляются операторыуправления программы и одноместные операции.
В этом случае некоторые изкомпонент трехадресного кода могут не использоваться. Например, условныйоператорif A > B then S1 else S21518.2. Трехадресный кодможет быть представлен следующим кодом:t := A - BJGT t, S2...Здесь JGT — двуместная операция условного перехода, не вырабатывающаярезультата.Разбиение арифметических выражений и операторов управления делаеттрехадресный код удобным при генерации машинного кода и оптимизации.Использование имен промежуточных значений, вычисляемых в программе,позволяет легко переупорядочивать трехадресный код.Представления синтаксического дерева и графа рис.
8.1 в виде трехадресного кода имеют следующий вид:Синтаксическое деревоt1 := -ct2 := b * t1t3 := -ct4 := b * t3t5 := t2 + t4a := t5Графt1 :=t2 :=t5 :=a :=-cb * t1t2 + t2t5Трехадресный код — это абстрактная форма промежуточного кода. В реализации трехадресный код может быть представлен записями с полями дляоперации и операндов. Рассмотрим три способа реализации трехадресногокода: четверки, тройки и косвенные тройки.Четверка — это запись с четырьмя полями, которые будем называтьop, arg 1, arg 2 и result.
Поле op содержит код операции. В операторахс унарными операциями типа x := −y или x := y поле arg 2 не используется. В некоторых операциях (типа «передать параметр») не используютсяни arg 2, ни result. Условные и безусловные переходы помещают в resultметку перехода. В табл. 8.1 приведены четверки для оператора присваиванияa := b ∗ −c + b ∗ −c. Они получены из трехадресного кода, приведенного выше.Обычно содержимое полей arg 1, arg 2 и result — это указатели на входытаблицы символов для имен, представляемых этими полями. Временные имена вносятся в таблицу символов по мере их генерации.Чтобы избежать внесения новых имен в таблицу символов, на временноезначение можно ссылаться, используя позицию вычисляющего его оператора.В этом случае трехадресные операторы могут быть представлены записямитолько с тремя полями: op, arg 1 и arg 2, как это показано в табл.
8.2.Поля arg 1 и arg 2 — это либо указатели на таблицу символов (для имен,определенных программистом, или констант), либо указатели на тройки(для временных значений). Такой способ представления трехадресного кода152Глава 8. Промежуточное представление программыТ а б л и ц а 8.1op arg 1 arg 2 result(0) -c(1) *b(2) -c(3) *bt3t4(4) +t2t4t5(5) :=t5t1t1t2t3aназывают тройками. Тройки соответствуют представлению синтаксическогодерева или ОАГ с помощью массива вершин.Т а б л и ц а 8.2op arg 1 arg 2(0) -c(1) *b(2) -c(3) *b(2)(4) +(1)(3)(5) :=a(4)(0)Числа в скобках — это указатели на тройки, а имена — это указателина таблицу символов. На практике информация, необходимая для интерпретации различного типа входов в поля arg 1 и arg 2, кодируется в поле op илидополнительных полях.
Тройки табл. 8.2 соответствуют четверкам табл. 8.1.Для представления тройками трехместной операции типа x[i] := y требуется два входа, как это показано в табл. 8.3, представление x := y[i] двумяоперациями показано в табл. 8.4.Т а б л и ц а 8.3oparg 1 arg 2(0) [ ]=xi(1) :=(0)yТрехадресный код может быть представлен не списком троек, а списком указателей на них. Такая реализация обычно называется косвеннымитройками. Например, тройки табл.
8.2 могут быть реализованы так, как этопредставлено в табл. 8.5.1538.2. Трехадресный кодТ а б л и ц а 8.4oparg 1 arg 2(0) =[ ]yi(1)x(0):=Т а б л и ц а 8.5оператор op arg 1 arg 2(0)(14)-c(1)(15)*b(2)(16)-c(3)(17)*b(16)(4)(18)+(15)(17)(5)(19):=a(18)(14)При генерации объектного кода каждой переменной, как временной, таки определенной в исходной программе, назначается память периода исполнения, адрес которой обычно хранится в таблице генератора кода. При использовании четверок этот адрес легко получить через эту таблицу.Более существенно преимущество четверок проявляется в оптимизирующих компиляторах, когда может возникнуть необходимость перемещатьоператоры. Если перемещается оператор, вычисляющий x, то не требуетсяизменений в операторе, использующем x. В записи же тройками перемещение оператора, определяющего временное значение, требует изменения всехссылок на этот оператор в массивах arg 1 и arg 2.
Из-за этого тройки трудноиспользовать в оптимизирующих компиляторах.В случае применения косвенных троек оператор может быть перемещенпереупорядочиванием списка операторов. При этом не надо менять указателина op, arg 1 и arg 2.
Этим косвенные тройки похожи на четверки. Крометого, эти два способа требуют примерно одинаковой памяти. Как и в случаепростых троек, при использовании косвенных троек выделение памяти длявременных значений может быть отложено на этап генерации кода. По сравнению с четверками при использовании косвенных троек можно сэкономитьпамять, если одно и то же временное значение используется более одногораза.
Например, в табл. 8.5 можно объединить строки (14) и (16), после чегоможно объединить строки (15) и (17).154Глава 8. Промежуточное представление программы8.3. Линеаризованные представленияВ качестве промежуточных представлений весьма распространены линеаризованные представления деревьев. Линеаризованное представление позволяет сравнительно легко хранить промежуточное представление во внешнейпамяти и обрабатывать его. Наиболее распространенной формой линеаризованного представления является польская запись — префиксная (прямая) илипостфиксная (обратная).Постфиксная запись — это список вершин дерева, в котором каждаявершина следует (при обходе снизу-вверх слева-направо) непосредственноза своими потомками.
Дерево на рис. 8.1, а в постфиксной записи может бытьпредставлено следующим образом:a b c - * b c - * + :=В постфиксной записи вершины синтаксического дерева не присутствуютявно. Они могут быть восстановлены из порядка, в котором следуют вершины,и из числа операндов соответствующих операций. Восстановление вершинаналогично вычислению выражения в постфиксной записи с использованиеммагазина.В префиксной записи сначала указывается операция, а затем ее операнды.Например, для приведенного выше выражения имеем:= a + * b - c * b - cРассмотрим детальнее одну из реализаций префиксного представления —Лидер [12].
Лидер — это аббревиатура от «ЛИнеаризованное ДЕРево». Этомашинно-независимая префиксная запись. В Лидере сохраняются все объявления и каждому из них присваивается свой уникальный номер, которыйиспользуется для ссылки на объявление. Рассмотрим пример:module M;var X,Y,Z: integer;procedure DIF(A,B:integer):integer;var R:integer;begin R:=A-B;return(R);end DIF;begin Z:=DIF(X,Y);end M.Этот фрагмент имеет следующий образ в Лидере:program ’M’var intvar intvar int8.3. Линеаризованные представленияprocbody proc int int end intvar intbegin assign var 1 7 endint int mi par 1 5 end par 1 6 endresult 0 int var 1 7 endreturnendbegin assign var 0 3 end inticall 0 4 int var 0 1 endint var 0 2 end endendРассмотрим его более детально:program ’M’var intvar intvar intprocbody procint int endintvar intbeginassignvar 1 7 endintint mipar 1 5 endpar 1 6 endresult 0intvar 1 7 endreturnИмя модуля нужно для редакторасвязей.Это образ переменных X, Y, Z;переменным X, Y, Z присваиваютсяномера 1, 2, 3 на уровне 0.Объявление процедуры с двумяцелыми параметрами, возвращающей целое.Процедура получает номер 4 науровне 0, и параметры имеют номера 5, 6 на уровне 1.Переменная R имеет номер 7 науровне 1.Начало тела процедуры.Оператор присваивания.Левая часть присваивания (R).Тип присваиваемого значения.Целое вычитание.Уменьшаемое (A).Вычитаемое (B).Результат процедуры уровня 0.Результат имеет целый тип.Результат — переменная R.Оператор возврата.155156endbeginassignvar 0 3inticall 0int varint varendendГлава 8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
