В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 19
Текст из файла (страница 19)
Для того, чтобы достичь сба-7.5. ТАБЛИЦЫ НА ДЕРЕВЬЯХ119лансированности, в процессе добавления новых вершин дерево можнослегка перестраивать следующим образом [1].Определим для каждой вершины дерева характеристику, равную разности высот выходящих из нее правой и левой ветвей. В сбалансированном дереве характеристика вершины может быть равной −1, 0 и 1, длялистьев она равна 0.$Q&Q%Q(Q'Q(Q)Q$Q%Q'Q)Q*Q&Q*QGh\Zy\_jrbgZZ[Рис. 7.8:$%($%(Gh\Zy\_jrbgZZ[Рис.
7.9:Пусть мы определили место новой вершины в дереве. Ее характеристика равна 0. Назовем путь, ведущий от корня к новой вершине, выделенным. При добавлении новой вершины могут измениться характери-120ГЛАВА 7. ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВстики только тех вершин, которые лежат на выделенном пути. Рассмотрим заключительный отрезок выделенного пути, такой, что до добавления вершины характеристики всех вершин на нем были равны 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, б, мы добьемся сбалансированности (в скобках указаны характеристики вершин, где этосущественно, и соотношения высот после добавления).Если характеристика вершины B после добавления новой вершиныв E стала равна 1, то надо отдельно рассмотреть случаи, когда характеристика вершины E, следующей за B на выделенном пути, стала равна−1, 1 и 0 (в последнем случае вершина E – новая). Вид дерева до и послеперестройки для этих случаев показан соответственно на рис.
7.7, 7.8 и7.9.7.6Реализация блочной структурыС точки зрения структуры программы блоки (и/или процедуры) образуют дерево. Каждой вершине дерева этого представления, соответствующей блоку, можно сопоставить свою таблицу символов (и, возможно,одну общую таблицу идентификаторов). Работу с таблицами блоков можно организовать в магазинном режиме: при входе в блок создавать таблицу символов, при выходе – уничтожать.
При этом сами таблицы должны быть связаны в упорядоченный список, чтобы можно было просматривать их в порядке вложенности. Если таблицы организованы с помощью функций расстановки, это означает, что для каждой таблицыдолжна быть создана своя таблица расстановки.7.7. СРАВНЕНИЕ МЕТОДОВ РЕАЛИЗАЦИИ ТАБЛИЦ7.7121Сравнение методов реализации таблицРассмотрим преимущества и недостатки рассмотренных методов реализации таблиц с точки зрения техники использования памяти.Использование динамической памяти, как правило, довольно дорогая операция, поскольку механизмы поддержания работы с динамической памятью могут быть достаточно сложны.
Необходимо поддерживать списки свободной и занятой памяти, выбирать наиболее подходящий кусок памяти при запросе, включать освободившийся кусок в список свободной памяти и, возможно, склеивать куски свободной памятив списке.С другой стороны, использование массива требует отведения заранеедовольно большой памяти, а это означает, что значительная память вообще не будет использоваться. Кроме того, часто приходится заполнятьне все элементы массива (например, в таблице идентификаторов или втех случаях, когда в массиве фактически хранятся записи переменнойдлины, например, если в таблице символов записи для различных объектов имеют различный состав полей).
Обращение к элементам массиваможет означать использование операции умножения при вычислениииндексов, что может замедлить исполнение.Наилучшим, по-видимому, является механизм доступа по указателям и использование факта магазинной организации памяти в компиляторе. Для этого процедура выделения памяти выдает необходимыйкусок из подряд идущей памяти, а при выходе из процедуры вся память, связанная с этой процедурой, освобождается простой перестановкой указателя свободной памяти в состояние перед началом обработкипроцедуры. В чистом виде это не всегда, однако, возможно. Например,локальный модуль в Модуле-2 может экспортировать некоторые объекты наружу. При этом схему реализации приходится “подгонять” под механизм распределения памяти.
В данном случае, например, необходимо экспортированные объекты вынести в среду охватывающего блока исвернуть блок локального модуля.122ГЛАВА 7. ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВГлава 8Промежуточноепредставление программыВ процессе трансляции компилятор часто используют промежуточноепредставление (ПП) исходной программы, предназначенное прежде всего для удобства генерации кода и/или проведения различных оптимизаций. Сама форма ПП зависит от целей его использования.Наиболее часто используемыми формами ПП является ориентированный граф (в частности, абстрактное синтаксическое дерево, в томчисле атрибутированное), трехадресный код (в виде троек или четверок), префиксная и постфиксная запись.8.1Представление в виде ориентированного графаПростейшей формой промежуточного представления является синтаксическое дерево программы.
Ту же самую информацию о входной программе, но в более компактной форме дает ориентированный ациклический граф (ОАГ), в котором в одну вершину объединены вершины синтаксического дерева, представляющие общие подвыражения. Синтаксическое дерево и ОАГ для оператора присваиванияa := b ∗ −c + b ∗ −cприведены на рис. 8.1.На рис. 8.2 приведены два представления в памяти синтаксическогодерева на рис. 8.1, а. Каждая вершина кодируется записью с полем дляоперации и полями для указателей на потомков. На рис.
8.2, б, вершины размещены в массиве записей и индекс (или вход) вершины служитуказателем на нее.123124 ГЛАВА 8. ПРОМЕЖУТОЧНОЕ ПРЕДСТАВЛЕНИЕ ПРОГРАММЫDDE EFFEFZ[Рис. 8.1:LGEELGLGLGDLGLGFLGFZFELGELGFLGD[Рис. 8.2:8.2Трехадресный кодТрехадресный код – это последовательность операторов вида x := y op z,где x, y и z – имена, константы или сгенерированные компилятором временные объекты. Здесь op – двуместная операция, например операцияплавающей или фиксированной арифметики, логическая или побито-8.2. ТРЕХАДРЕСНЫЙ КОД125вая.
В правую часть может входить только один знак операции.Составные выражения должны быть разбиты на подвыражения, приэтом могут появиться временные имена (переменные). Смысл термина“трехадресный код” в том, что каждый оператор обычно имеет три адреса: два для операндов и один для результата. Трехадресный код – это линеаризованное представление синтаксического дерева или ОАГ, в котором временные имена соответствуют внутренним вершинам дерева илиграфа. Например, выражение 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 + t4a := t5аt1 := -ct2 := b * t1t5 := t2 + t2a := t5бРис.
8.3:Представления синтаксического дерева и графа рис. 8.1 в виде трехадресного кода дано на рис. 8.3, а, и 8.3, б, соответственно.126 ГЛАВА 8. ПРОМЕЖУТОЧНОЕ ПРЕДСТАВЛЕНИЕ ПРОГРАММЫТрехадресный код – это абстрактная форма промежуточного кода. Вреализации трехадресный код может быть представлен записями с полями для операции и операндов.
Рассмотрим три способа реализациитрехадресного кода: четверки, тройки и косвенные тройки.Четверка – это запись с четырьмя полями, которые будем называтьop, arg1, arg2 и result. Поле op содержит код операции. В операторах сунарными операциями типа x := −y или x := y поле arg2 не используется. В некоторых операциях (типа “передать параметр”) могут не использоваться ни arg2, ни result. Условные и безусловные переходы помещают в result метку перехода. На рис.
8.4, а, приведены четверки дляоператора присваивания a := b∗−c+b∗−c. Они получены из трехадресногокода на рис. 8.3, а.(0)(1)(2)(3)(4)(5)op**+:=arg1cbcbt2t5arg2t1t3t4resultt1t2t3t4t5aа) четверки(0)(1)(2)(3)(4)(5)op**+:=arg1cbcb(1)aarg2(0)(2)(3)(4)б ) тройкиРис.
8.4:Обычно содержимое полей arg1, arg2 и result – это указатели на входы таблицы символов для имен, представляемых этими полями. Временные имена вносятся в таблицу символов по мере их генерации.Чтобы избежать внесения новых имен в таблицу символов, на временное значение можно ссылаться, используя позицию вычисляющегоего оператора. В этом случае трехадресные операторы могут быть представлены записями только с тремя полями: op, arg1 и arg2, как это показано на рис. 8.3, б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
