В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 18
Текст из файла (страница 18)
Таким образом, функция расстановки сопоставляет идентификатору некоторый адрес в таблице символов.Пусть мы хотим найти в таблице идентификатор 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
