В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1134643), страница 19
Текст из файла (страница 19)
Поиск в такой таблицеможет быть организован методом повторной расстановки. Суть его заключается в следующем.Таблица символов представляет собой массив фиксированного размера N . Идентификаторы могут храниться как в самой таблице символов, так и в отдельной таблице идентификаторов.Определим некоторую функцию h1 (первичную функцию расстановки), определенную на множестве идентификаторов и принимающую значения от 0 до N − 1 (т.е. 0 6 h1 (id) 6 N − 1, где id – символьное представление идентификатора). Таким образом, функция расстановки сопоставляет идентификатору некоторый адрес в таблице символов.Пусть мы хотим найти в таблице идентификатор id. Если элемент таблицы с номером h1 (id) не заполнен, то это означает, что идентификатора в таблице нет.
Если же занят, то это еще не означает, что идентификатор id в таблицу занесен, поскольку (вообще говоря) много идентификаторов могут иметь одно и то же значение функции расстановки. Длятого чтобы определить, нашли ли мы нужный идентификатор, сравниваем id с элементом таблицы h1 (id). Если они равны – идентификаторнайден, если нет – надо продолжать поиск дальше.Для этого вычисляется вторичная функция расстановки h2 (h) (значением которой опять таки является некоторый адрес в таблице символов). Возможны четыре варианта:– элемент таблицы не заполнен (т.е.
идентификатора в таблице нет),– идентификатор элемента таблицы совпадает с искомым (т.е. идентификатор найден),– адрес элемента совпадает с уже просмотренным (т.е. таблица всяпросмотрена и идентификатора нет)112ГЛАВА 7. ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВ– предыдущие варианты не выполняются, так что необходимо продолжать поиск.Для продолжения поиска применяется следующая функция расстановки h3 (h2 ), h4 (h3 ) и т.д.
Как правило, hi = h2 для i > 2. Аргументомфункции h2 является целое в диапазоне [0, N − 1] и она может быть бытьустроена по-разному. Приведем три варианта.1) h2 (i) = (i + 1) mod N .Берется следующий (циклически) элемент массива. Этот вариант плохтем, что занятые элементы “группируются”, образуют последовательные занятые участки и в пределах этого участка поиск становится посуществу линейным.2) h2 (i) = (i + k) mod N , где k и N взаимно просты.По-существу это предыдущий вариант, но элементы накапливаютсяне в последовательных элементах, а “разносятся”.3) h2 (i) = (a ∗ i + c) mod N – “псевдослучайная последовательность”.Здесь c и N должны быть взаимно просты, b = a − 1 кратно p длялюбого простого p, являщегося делителем N , b кратно 4, если N кратно4 [5].Поиск в таблице расстановки можно описать следующей функцией:void Search(String Id,boolean * Yes,int * Point){int H0=h1(Id), H=H0;while (1){if (Empty(H)==NULL){*Yes=false;*Point=H;return;}else if (IdComp(H,Id)==0){*Yes=true;*Point=H;return;}else H=h2(H);if (H==H0){*Yes=false;*Point=NULL;return;}}}Функция IdComp(H,Id) сравнивает элемент таблицы на входе H с идентификатором и вырабатывает 0, если они равны.
Функция Empty(H) вырабатывает NULL, если вход H пуст. Функция Search присваивает параметрам Yes и Pointer соответственно следующие значения :7.3. ТАБЛИЦЫ РАССТАНОВКИ СО СПИСКАМИ113true, P – если нашли требуемый идентификатор, где P – указатель насоответствующий этому идентификатору вход в таблице,false, NULL – если искомый идентификатор не найден, причем в таблице нет свободного места, иfalse, P – если искомый идентификатор не найден, но в таблице естьсвободный вход P.Занесение элемента в таблицу можно осуществить следующей функцией:int Insert(String Id){boolean Yes;int Point=-1;Search(Id,&Yes,&Point);if (!Yes && (Point!=NULL)) InsertId(Point,Id);return(Point);}Здесь функция InsertId(Point,Id) заносит идентификатор Id для входаPoint таблицы.7.3Таблицы расстановки со спискамиТолько что описанная схема страдает одним недостатком – возможностью переполнения таблицы.
Рассмотрим ее модификацию, когда всеэлементы, имеющие одинаковое значения (первичной) функции расстановки, связываются в список (при этом отпадает необходимость использования функций hi для i > 2). Таблица расстановки со списками – этомассив указателей на списки элементов (рис. 7.3).Вначале таблица расстановки пуста (все элементы имеют значениеNULL). При поиске идентификатора Id вычисляется функция расстановки h(Id) и просматривается соответствующий линейный список.
Поискв таблице может быть описан следующей функцией:struct Element{String IdentP;struct Element * Next;};struct Element * T[N];struct Element * Search(String Id){struct Element * P;P=T[h(Id)];while (1){if (P==NULL) return(NULL);else if (IdComp(P->IdentP,Id)==0) return(P);else P=P->Next;ГЛАВА 7. ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВ114}}1OmdZaZl_evgZ LGmdZaZl_evgZ LGmdZaZl_evgZ LGOOmdZaZl_evgZ LGmdZaZl_evgZ LGmdZaZl_evgZ LGРис. 7.3:+O3OРис. 7.4:7.4. ФУНКЦИИ РАССТАНОВКИ115Занесение элемента в таблицу можно осуществить следующей функцией:struct Element * Insert(String Id){struct Element * P,H;P=Search(Id);if (P!=NULL) return(P);else {H=H(Id);P=alloc(sizeof(struct Element));P->Next=T[H];T[H]=P;P->IdentP=Include(Id);}return(P);}Процедура Include заносит идентификатор в таблицу идентификаторов.
Алгоритм иллюстрируется рис. 7.4.7.4Функции расстановкиМного внимания исследователями было уделено тому, какой должнабыть (первичная) функция расстановки. Основные требования к ней очевидны: она должна легко вычисляться и распределять равномерно. Одиниз возможных подходов здесь заключается в следующем.1. По символам строки s определяем положительное целое H. Преобразование одиночных символов в целые обычно можно сделать средствами языка реализации. В Паскале для этого служит функция ord,в Си при выполнении арифметических операций символьные значениятрактуются как целые.2.
Преобразуем H, вычисленное выше, в номер элемента, т.е. целоемежду 0 и N − 1, где N – размер таблицы расстановки, например, взятием остатка при делении H на N .Функции расстановки, учитывающие все символы строки, распределяют лучше, чем функции, учитывающие только несколько символов, например, в конце или середине строки. Но такие функции требуютбольше вычислений.Простейший способ вычисления H – сложение кодов символов.
Перед сложением с очередным символом можно умножить старое значение H на константу q. Т.е. полагаем H0 = 0, Hi = q ∗ Hi−1 +ci для 1 6 i 6 k,k – длина строки. При q = 1 получаем простое сложение символов. Вместо сложения можно выполнять сложение ci и q ∗ Hj−1 по модулю 2. Переполнение при выполнении арифметических операций можно игнорировать.116ГЛАВА 7. ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВФункция Hashpjw, приведенная ниже [10], вычисляется, начиная сH = 0 (предполагается, что используются 32-битовые целые). Для каждого символа c сдвигаем биты H на 4 позиции влево и добавляем очередной символ. Если какой-нибудь из четырех старших бит H равен 1,сдвигаем эти 4 бита на 24 разряда вправо, затем складываем по модулю2 с H и устанавливаем в 0 каждый из четырех старших бит, равных 1.#define PRIME 211#define EOS ’\0’int Hashpjw(char *s){char *p;unsigned H=0, g;for (p=s; *p!=EOS; p=p+1){H=(H<<4)+(*p);if (g=H&0xf0000000){H=H^(g>>24);H=H^g;} }return H%PRIME;}7.5Таблицы на деревьяхРассмотрим еще один способ организации таблиц символов с использованием двоичных деревьев.Ориентированное дерево называется двоичным, если у него в каждую вершину, кроме одной (корня), входит одна дуга, и из каждой вершины выходит не более двух дуг.
Ветвью дерева называется поддерево,состоящее из некоторой дуги данного дерева, ее начальной и конечнойвершин, а также всех вершин и дуг, лежащих на всех путях, выходящих из конечной вершины этой дуги. Высотой дерева называется максимальная длина пути в этом дереве от корня до листа.Пусть на множестве идентификаторов задан некоторый линейный(например, лексикографический) порядок ≺, т.е. некоторое транзитивное, антисимметричное и антирефлексивное отношение. Таким образом,для произвольной пары идентификаторов id1 и id2 либо id1 ≺ id2 , либоid2 ≺ id1 , либо id1 совпадает с id2 .Каждой вершине двоичного дерева, представляющего таблицу символов, сопоставим идентификатор.
При этом, если вершина (которой сопоставлен id) имеет левого потомка (которому сопоставлен idL ), то idL ≺ id;если имеет правого потомка (idR ), то id ≺ idR . Элемент таблицы изображен на рис. 7.5.Поиск в такой таблице может быть описан следующей функцией:struct TreeElement * SearchTree(String Id, struct TreeElement * TP)7.5.
ТАБЛИЦЫ НА ДЕРЕВЬЯХ73117,GHQW3/HIW 5LJKWРис. 7.5:{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;}где структура для для элемента дерева имеет видstruct TreeElement{String IdentP;struct TreeElement * Left, * Right;};Занесение в таблицу осуществляется функциейstruct TreeElement * InsertTree(String Id, struct TreeElement * TP){int comp=IdComp(Id,TP->IdentP);if (comp<0) return(Fill(Id,TP->Left, &(TP->Left)));if (comp>0) return(Fill(Id,TP->Right, &(TP->Right)));return(TP);}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));}ГЛАВА 7.
ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВ118Как показано в работе [8], среднее время поиска в таблице размера n,организованной в виде двоичного дерева, при равной вероятности появления каждого объекта равно (2 ln 2) log 2 n + O(1). Однако, на практикеслучай равной вероятности появления объектов встречается довольноредко. Поэтому в дереве появляются более длинные и более короткиеветви, и среднее время поиска увеличивается.$Q&Q%Q'Q%Q(QGh\Zy\_jrbgZ$Q'Q(QZ&Q[Рис. 7.6:$Q&Q%Q(Q'Q)QGh\Zy\_jrbgZ(Q$Q%Q'Q)Q*Q&Q*QZ[Рис.
7.7:Чтобы уменьшить среднее время поиска в двоичном дереве, можно впроцессе построения дерева следить за тем, чтобы оно все время оставалось сбалансированным. А именно, назовем дерево сбалансированным,если ни для какой вершины высота выходящей из нее правой ветви неотличается от высоты левой более чем на 1. Для того, чтобы достичь сба-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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
