В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 28
Текст из файла (страница 28)
Организация таблиц символов7.5. Таблицы на деревьяхРассмотрим еще один способ организации таблиц символов — с использованием двоичных деревьев.Ориентированное дерево называется двоичным, если у него в каждуювершину, кроме одной (корня), входит одна дуга и из каждой вершинывыходит не более двух дуг. Ветвью дерева называется поддерево, состоящееиз некоторой дуги данного дерева, ее начальной и конечной вершин, а такжевсех вершин и дуг, лежащих на всех путях, выходящих из конечной вершиныэтой дуги. Высотой дерева называется максимальная длина пути в этомдереве от корня до листа.Пусть на множестве идентификаторов задан некоторый линейный (например, лексикографический) порядок ≺, т.
е. некоторое транзитивное, антисимметричное и антирефлексивное отношение. Таким образом, для произвольнойпары идентификаторов id1 и id2 либо id1 ≺ id2 , либо id2 ≺ id1 , либо id1совпадает с id2 .Каждой вершине двоичного дерева, представляющего таблицу символов,сопоставим идентификатор. При этом если вершина (которой сопоставлен id)имеет левого потомка (которому сопоставлен idL ), то idL ≺ id; если онаимеет правого потомка (idR ), то id ≺ idR . Элемент таблицы изображенна рис. 7.5.Рис.
7.5Узел дерева описывается как класс TreeElement:class TreeElement{String IdentP;TreeElement Left, Right;};Поиск в такой таблице может быть описан следующей функцией:TreeElement SearchTree(String Id,TreeElement TP){int comp;if (TP==null) return null;comp=IdComp(Id,TP.IdentP);if (comp<0) return(SearchTree(Id,TP.Left));if (comp>0) return(SearchTree(Id,TP.Right));return TP;}7.5.
Таблицы на деревьях145Занесение в таблицу осуществляется функциейvoid InsertTree(String Id,TreeElement TP){int comp=IdComp(Id,TP.IdentP);if (comp<0)if (TP.Left != null)InsertTree(Id,n.Leftt);else {n.Left = new TreeElement();n.Left.InentP = Id;n.Left.Left = null;n.Left.Right = null;}}else if (comp>0)if (TP.Right != null)InsertTree(Id,n.Right);else {n.Right = new TreeElement();n.Right.InentP = Id;n.Right.Left = null;n.Right.Right = null;}}}struct TreeElement * Fill(String Id,struct TreeElement * P,struct TreeElement ** FP){ if (P==NULL){P=alloc(sizeof(struct TreeElement));P->IdentP=Include(Id);P->Left=NULL;P->Right=NULL;*FP=P;return(P);}else return(InsertTree(Id,P));}Как показано в [10], среднее время поиска в таблице размера n, организованной в виде двоичного дерева, при равных вероятностях появления каждогообъекта равно (2 ln 2) log 2 n + O(1).
Однако на практике случай равных вероятностей появления объектов встречается довольно редко. Поэтому в деревепоявляются более длинные и более короткие ветви, и среднее время поискаувеличивается.Чтобы уменьшить среднее время поиска в двоичном дереве, можно в процессе построения дерева следить за тем, чтобы оно все время оставалось сбалансированным. А именно, назовем дерево сбалансированным, если ни длякакой вершины высота выходящей из нее правой ветви не отличается от высоты левой более чем на 1. Для того чтобы достичь сбалансированности,146Глава 7.
Организация таблиц символовРис. 7.6в процессе добавления новых вершин дерево можно слегка перестраиватьследующим образом [1].Определим для каждой вершины дерева характеристику, равную разностивысот выходящих из нее правой и левой ветвей. В сбалансированном деревехарактеристика вершины может быть равной −1, 0 или 1, для листьев онаравна 0.Пусть мы определили место новой вершины в дереве. Ее характеристикаравна 0.
Назовем путь, ведущий от корня к новой вершине, выделенным.При добавлении новой вершины могут измениться характеристики только техвершин, которые лежат на выделенном пути. Рассмотрим заключительныйотрезок выделенного пути — такой, что до добавления вершины характеристики всех вершин на нем были равны 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 — двуместная операция, например, операция плавающей или фиксированной арифметики, логическая или побитовая. В правуючасть может входить только один знак операции.Составные выражения должны быть разбиты на подвыражения, при этоммогут появиться временные имена (переменные).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
