Лекции по конструированию компиляторов. В.А. Серебряков (1134687), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

Пусть теперь характеристика A до перестраивания равна -1 и новая вершина добавлена к левому поддереву A (аналогично - для случая 1 и добавления к правому поддереву). Возможны следующие варианты.

A(-2,n+3) B(0,n+2)




B(-1,n+2)
C(n) D(n+1) A(0,n+1)

D(n+1) E(n)
E(n) C(n)



Новая вершина
(а) (б)

Рис. 6.7

A(-2,n+3)) E(0,n+2)



B(1,n+2) C(n)

D(n) B(0,n+1) A(1,n+1)
E(-1,n+1)

F(n) G(n-1) D(n) F(n)G(n-1) C(n)




Новая вершина
а) б)
Рис. 6.8

A(-2,n+3)) E(0,n+2)



B(1,n+2) C(n)

D(n) B(-1,n+1) A(0,n+1)
E(-1,n+1)


F(n-1) G(n) D(n) F(n-1) G(n) C(n)





Новая вершина
а) б)
Рис. 6.9

Рассмотрим вершину B - левого потомка A. Если характеристика B после добавления новой вершины в D стала равна -1, то дерево имеет структуру, изображенную на рис. 6.7(а). Перестроив дерево так, как это изображено на рис. 6.7(б), мы добьемся сбалансированности (в скобках указаны характеристики вершин, где это существенно, и соотношения высот после добавления).

A(-2,2) E(1,0)


B(1,1) B(0,0) A(0,0)


E(0,0)

Новая вершина

Рис. 6.10

Если характеристика вершины B после добавления новой вершины в E стала равна 1, то надо отдельно рассмотреть случаи, когда характеристика вершины E, следующей за B на выделенном пути, стала равна -1, 1 и 0 (в последнем случае вершина E - новая). Вид дерева до и после перестройки для этих случаев показан соответственно на рис. 6.8, 6.9 и 6.10.

6.6. Реализация блочной структуры

С точки зрения структуры программы блоки (и/или процедуры) образуют дерево. Каждой вершине дерева этого представления, соответствующей блоку, можно сопоставить свою таблицу объектов (и, возможно, одну общую таблицу идентификаторов). Работу с таблицами блоков можно организовать в магазинном режиме: при входе в блок создавать таблицу объектов, при выходе - уничтожать. При этом сами таблицы должны быть связаны в упорядоченный список, чтобы можно было просматривать их в порядке вложенности (рис. 6.11). Если таблицы организованы с помощью функций расстановки, это означает, что для каждой таблицы должна быть создана своя таблица расстановки.

T1 T2 Tn

Рис. 6.11

6.7. Сравнение различных методов реализации таблиц

Рассмотрим преимущества и недостатки тех или иных методов реализации таблиц с точки зрения техники использования памяти. Если таблица размещается в массиве, то, с одной стороны, отпадает необходимость использования динамической памяти, а с другой - появляется ряд осложнений. Использование динамической памяти, как правило, довольно дорогая операция, поскольку механизмы поддержания работы с динамической памятью довольно сложны. Необходимо поддерживать списки свободной и занятой памяти, выбирать наиболее подходящий кусок памяти при запросе, включать освободившийся кусок в список свободной памяти и, возможно, склеивать куски свободной памяти в списке. С другой стороны, использование массива требует отведения заранее довольно большой памяти, а это означает, что значительная память вообще не будет использоваться. Кроме того, часто приходится заполнять не все элементы массива (например, в таблице идентификаторов или в тех случаях, когда в массиве фактически хранятся записи переменной длины, например если в таблице символов записи для различных объектов имеют различный состав полей). Обращение к элементам массива может означать использование операции умножения при вычислении индексов, что может замедлить исполнение. Наилучшим, по-видимому, является механизм доступа по указателям и использование факта магазинной организации памяти в компиляторе. Для этого процедура выделения памяти выдает необходимый кусок из подряд идущей памяти, а при выходе из процедуры вся память, связанная с этой процедурой, освобождается простой перестановкой указателя свободной памяти в состояние перед началом обработки процедуры. В чистом виде это не всегда, однако, возможно. Например, локальный модуль в Модуле-2 может экспортировать некоторые объекты наружу. При этом схему реализации приходится "подгонять" под механизм распределения памяти. В данном случае, например, необходимо экспортированные объекты вынести в среду охватывающего блока и свернуть блок локального модуля.

Глава 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 - двуместная операция, например операция плавающей или фиксированной арифметики, логическая или побитовая. В правую часть может входить только один знак операции.

:= :=

/\ /\
/ \ / \
a + a +
/ \ / \
/ \ | |
* * \ /
/ \ / \ *
/ \ / \ / \
b - b - / \
| | b -
| | |
c c |
c
а) б)

Рис. 7.1

10 := 0 id b

1 id c
9 id a
2 - 1

3 * 0 2
7 +
4 id b

5 id c
3 * 8 *
6 - 5

0 id b 4 id b 7 + 3 8

8 * 4 6
2 - 6 -
9 id a

1 id c 5 id c 10 := 9 7

Рис. 7.2

Составные выражения должны быть разбиты на подвыражения, при этом могут появиться временные имена (переменные). Смысл термина "трехадресный код" в том, что каждый оператор обычно имеет три адреса: два для операндов и один для результата. Трехадресный код - это линеаризованное представление синтаксического дерева или ОАГ, в котором явные имена соответствуют внутренним вершинам дерева или графа. Например, выражение x+y*z может быть протранслировано в последовательность операторов

t1:=y*z
t2:=x+t1

где t1 и t2 - имена, сгенерированные компилятором.

В виде трехадресного кода представляются не только двуместные операции, входящие в выражения. В таком же виде представляются операторы управления программы и одноместные операции. В этом случае некоторые из компонент трехадресного кода могут не использоваться. Например, условный оператор

if A>B then S1 else S2

может быть представлен следующим кодом:

t:=A-B
JGT t,S2
.....

Здесь JGT - двуместная операция условного перехода, не вырабатывающая результата.

Разбиение арифметических выражений и операторов управления делает трехадресный код удобным при генерации машинного кода и оптимизации. Использование имен промежуточных значений, вычисляемых в программе, позволяет легко переупорядочивать трехадресный код.

t1 := -c t1 := -c
t2 := b * t1 t2 := b * t1
t3 := -c t5 := t2 + t2
t4 := b * t3 a := t5
t5 := t2 + t1
a := t5

а) б)

Рис. 7.3

Представления синтаксического дерева и графа рис. 7.1 в виде трехадресного кода дано на рис. 7.3.а) и 7.3.б), соответственно.

Трехадресный код - это абстрактная форма промежуточного кода. В реализации трехадресный код может быть представлен записями с полями для операции и операндов. Рассмотрим три реализации трехадресного кода: четверки, тройки и косвенные тройки.

Четверка - это запись с четырьмя полями, которые будем называть 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 - это либо указатели на таблицу символов (для имен, определенных программистом, или констант), либо указатели на тройки (для временных значений). Такой способ представления трехадресного кода называют тройками. Тройки соответствуют представлению синтаксического дерева или ОАГ с помощью массива вершин.

Характеристики

Список файлов лекций