В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 28
Текст из файла (страница 28)
Рассмотрим заключительныйотрезок выделенного пути — такой, что до добавления вершины характеристики всех вершин на нем были равны 0. Если верхним концом этого отрезкаявляется сам корень, то дерево перестраивать не надо, достаточно лишьизменить характеристики вершин на этом пути на 1 или −1, в зависимостиот того, влево или вправо пристроена новая вершина.Пусть верхний конец заключительного отрезка — не корень. Рассмотримвершину A — «родителя» верхнего конца заключительного отрезка. Переддобавлением новой вершины характеристика A была равна ±1. Если A имелахарактеристику 1 (−1) и новая вершина добавляется в левую (правую) ветвь,то характеристика вершины A становится равной 0, а высота поддеревас корнем в A не меняется.
Так что и в этом случае дерево перестраиватьне надо.Пусть теперь характеристика A до перестроения была равна −1 и новаявершина добавлена к левой ветви A (аналогично — для случая 1 и добавленияк правой ветви). Рассмотрим вершину B — левого потомка A. Возможныследующие варианты.Если характеристика B после добавления новой вершины в D стала равна−1, то дерево имеет структуру, изображенную на рис.
7.6, а. Перестроив дерево так, как это изображено на рис. 7.6, б, мы добьемся сбалансированности7.5. Таблицы на деревьях147Рис. 7.7Рис. 7.8Рис. 7.9(в скобках указаны характеристики вершин, где это существенно, и соотношения высот после добавления).Если характеристика вершины B после добавления новой вершины в Eстала равна 1, то надо отдельно рассмотреть случаи, когда характеристикавершины E , следующей за B на выделенном пути, стала равна −1, 1 и 0(в последнем случае вершина E — новая). Вид дерева для этих случаев показан соответственно на рис.
7.7, 7.8 и 7.9 (а — до, б — после перестроения).148Глава 7. Организация таблиц символов7.6. Реализация блочной структурыС точки зрения структуры программы блоки (и/или процедуры) образуютдерево. Каждой вершине дерева этого представления, соответствующей блоку,можно сопоставить свою таблицу символов (и, возможно, одну общую таблицу идентификаторов). Работу с таблицами блоков можно организовать в магазинном режиме: при входе в блок создавать таблицу символов, при выходе —уничтожать. При этом сами таблицы должны быть связаны в упорядоченныйсписок, чтобы можно было просматривать их в порядке вложенности.
Еслитаблицы организованы с помощью функций расстановки, то это означает, чтодля каждой таблицы должна быть создана своя таблица расстановки.7.7. Сравнение методов реализации таблицРассмотрим преимущества и недостатки рассмотренных методов реализации таблиц с точки зрения техники использования памяти.Использование динамической памяти, как правило, — довольно дорогаяоперация, поскольку механизмы поддержания работы с динамической памятью могут быть достаточно сложны. Необходимо поддерживать спискисвободной и занятой памяти, выбирать наиболее подходящий кусок памятипри запросе, включать освободившийся кусок в список свободной памяти и,возможно, склеивать куски свободной памяти в списке.С другой стороны, использование массива требует предварительного отведения довольно большой памяти, а это означает, что значительная памятьвообще не будет использоваться.
Кроме того, часто приходится заполнятьне все элементы массива (например, в таблице идентификаторов или в техслучаях, когда в массиве фактически хранятся записи переменной длины,например, если в таблице символов записи для различных объектов имеютразличный состав полей). Обращение к элементам массива может означатьиспользование операции умножения при вычислении индексов, что можетзамедлить исполнение.Наилучшим, по-видимому, является механизм доступа по указателямс использованием факта магазинной организации памяти в компиляторе.
Дляэтого процедура выделения памяти выдает необходимый кусок из подрядидущей памяти, а при выходе из процедуры вся память, связанная с этойпроцедурой, освобождается простой перестановкой указателя свободной памяти в состояние перед началом обработки процедуры.
В чистом виде этоне всегда, однако, возможно. Например, локальный модуль в Модуле-2 можетэкспортировать некоторые объекты наружу. При этом схему реализации приходится «подгонять» под механизм распределения памяти. В данном случае,например, необходимо экспортированные объекты вынести в среду охватывающего блока и свернуть блок локального модуля.Глава 8ПРОМЕЖУТОЧНОЕ ПРЕДСТАВЛЕНИЕ ПРОГРАММЫВ процессе трансляции компилятор часто используют промежуточноепредставление (ПП) исходной программы, предназначенное прежде всего дляудобства генерации кода и/или проведения различных оптимизаций.
Самаформа ПП зависит от целей его использования.Наиболее часто используемыми формами ПП является ориентированныйграф (в частности, абстрактное синтаксическое дерево, в том числе атрибутированное), трехадресный код (в виде троек или четверок), префикснаяи постфиксная записи.8.1. Представление в виде ориентированного графаПростейшей формой промежуточного представления является синтаксическое дерево программы.
Ту же самую информацию о входной программе,но в более компактной форме дает ориентированный ациклический граф(ОАГ), в котором в одну вершину объединены вершины синтаксическогодерева, представляющие общие подвыражения. Синтаксическое дерево и ОАГдля оператора присваиванияa := b ∗ −c + b ∗ −cприведены на рис. 8.1.Рис.
8.1150Глава 8. Промежуточное представление программыРис. 8.2На рис. 8.2 приведены два представления в памяти синтаксического деревана рис. 8.1, а. Каждая вершина кодируется записью с полем для операциии полями для указателей на потомков. На рис. 8.2, б вершины размещеныв массиве записей и индекс (или вход) вершины служит указателем на нее.8.2. Трехадресный кодТрехадресный код — это последовательность операторов вида x := y op z ,где x, y и z — имена, константы или сгенерированные компилятором временные объекты. Здесь op — двуместная операция, например, операция плавающей или фиксированной арифметики, логическая или побитовая. В правуючасть может входить только один знак операции.Составные выражения должны быть разбиты на подвыражения, при этоммогут появиться временные имена (переменные).
Смысл термина «трехадресный код» в том, что каждый оператор обычно имеет три адреса: два дляоперандов и один для результата. Трехадресный код — это линеаризованноепредставление синтаксического дерева или ОАГ, в котором временные именасоответствуют внутренним вершинам дерева или графа. Например, выражение 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 илидополнительных полях. Тройки табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
