В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 27
Текст из файла (страница 27)
Проверка контекстных условий}1A:{if (!first)if ((TypeRef != intRef) | (typeRefRef<1>.TER != typeRef))Error("Тип переменной в выражении должен быть integer");Telement typeRef = typeRefRef<1>.TER;first = false; }.RuleFactor ::= VariableSemantics{TypeRefRef<0> =TypeRefRef<1>; }.RuleFactor ::= ’(’ Expression ’)’Semantics{TypeRefRef<0> = TypeRefRef<2>;if (TypeRefRef<2>.TER != intRef)Error("Тип переменной в выражении должен быть integer");}.RuleFactor ::= IntegerSemantics{TypeRefRef<0>.TER = intRef;}.Глава 7ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВВ процессе работы компилятор хранит информацию об объектах программы в специальных таблицах символов. Как правило, информация о каждомобъекте состоит из двух основных элементов: имени объекта и описанияобъекта.
Информация об объектах программы должна быть организованатаким образом, чтобы поиск ее был по возможности быстрее, а требуемаяпамять по возможности меньше.Кроме того, со стороны языка программирования могут быть дополнительные требования к организации информации. Имена могут иметь определенную область видимости. Например, поле записи должно быть уникальнов пределах структуры (или уровня структуры), но может совпадать с именемобъекта вне записи (или другого уровня записи). В то же время имя поляможет открываться оператором присоединения, и тогда может возникнутьконфликт имен (или неоднозначность в трактовке имени).
Если язык имеетблочную структуру, то необходимо обеспечить такой способ хранения информации, чтобы, во-первых, поддерживать блочный механизм видимости,а во-вторых, эффективно освобождать память при выходе из блока. Некоторые языки (например, Ада) допускают одновременную (в одном блоке)видимость нескольких объектов с одним именем, в других такая ситуациянедопустима.Мы рассмотрим некоторые основные способы организации таблиц символов в компиляторе: таблицы идентификаторов, таблицы расстановки, двоичные деревья и реализацию блочной структуры.7.1. Таблицы идентификаторовКак уже было сказано, информацию об объекте обычно можно разделитьна две части: имя (идентификатор) и описание. Если длина идентификатораограничена (или имя идентифицируется по ограниченному числу первыхсимволов идентификатора), то таблица символов может быть организованав виде простого массива строк фиксированной длины, как это изображенона рис.
7.1. Некоторые входы могут быть заняты, некоторые — свободны.Ясно, что, во-первых, размер массива должен быть не меньше числа идентификаторов, которые могут реально появиться в программе (в противном138Глава 7. Организация таблиц символовРис. 7.1Рис. 7.2случае возникает переполнение таблицы); во-вторых, как правило, потенциальное число различных идентификаторов существенно больше размератаблицы.Заметим, что в большинстве языков программирования символьное представление идентификатора может иметь произвольную длину. Кроме того,различные объекты в одной или в разных областях видимости могут иметьодинаковые имена, и нет большого смысла занимать память для повторногохранения идентификатора.
Таким образом, удобно имя объекта и его описаниехранить по отдельности.В этом случае идентификаторы хранятся в отдельной таблице — таблицеидентификаторов. В таблице символов же хранится указатель на соответствующий вход в таблицу идентификаторов. Таблицу идентификаторовможно организовать, например, в виде сплошного массива. Идентификаторв массиве заканчивается каким-либо специальным символом EOS (рис. 7.2).Второй возможный вариант — в качестве первого символа идентификаторав массив заносится его длина.7.2.
Таблицы расстановки1397.2. Таблицы расстановкиОдним из эффективных способов организации таблицы символов являетсятаблица расстановки (или хеш-таблица). Поиск в такой таблице можетбыть организован методом повторной расстановки. Суть его заключаетсяв следующем.Таблица символов представляет собой массив фиксированного размера N .Идентификаторы могут храниться как в самой таблице символов, так и в отдельной таблице идентификаторов.Определим некоторую функцию h1 (первичную функцию расстановки),определенную на множестве идентификаторов и принимающую значения от0 до N − 1 (т. е. 0 6 h1 (id) 6 N − 1, где id — символьное представлениеидентификатора). Таким образом, функция расстановки сопоставляет идентификатору некоторый адрес в таблице символов.Пусть мы хотим найти в таблице идентификатор id.
Если элемент таблицыс номером h1 (id) не заполнен, то это означает, что идентификатора в таблиценет. Если же он занят, то это еще не означает, что идентификатор id в таблицу занесен, поскольку (вообще говоря) много идентификаторов могут иметьодно и то же значение функции расстановки. Для того чтобы определить,нашли ли мы нужный идентификатор, сравниваем id с элементом таблицыh1 (id).
Если они равны — идентификатор найден, если нет — надо продолжатьпоиск дальше.Для этого вычисляется вторичная функция расстановки h2 (h1 ) (значением которой опять-таки является некоторый адрес в таблице символов).Возможны четыре варианта:– элемент таблицы не заполнен (т. е.
идентификатора в таблице нет),– идентификатор элемента таблицы совпадает с искомым (т. е. идентификатор найден),– адрес элемента совпадает с уже просмотренным (т. е. таблица вся просмотрена, но идентификатора нет),– предыдущие варианты не выполняются, так что необходимо продолжатьпоиск.Для продолжения поиска применяется следующая функция расстановки:h3 (h2 ), h4 (h3 ) и т. д. Как правило, hi = h2 для i > 2. Аргументом функцииh2 является целое в диапазоне [0, N − 1], и она может быть быть устроенапо-разному. Приведем три варианта.1) h2 (i) = (i + 1) mod N .Берется следующий (циклически) элемент массива. Этот вариант плохтем, что занятые элементы «группируются», образуют последовательные140Глава 7.
Организация таблиц символовзанятые участки и в пределах этого участка поиск становится по существулинейным.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 [6].Поиск в таблице расстановки можно описать следующей функцией (здесьNULL некоторое выделенное значение типа int, например, −1):class BoolRef {boolean val;}class IntRef {int val;}void Search(String Id,BoolRef Yes,IntRef Point){int H0=h1(Id), H=H0;while (1){if (Empty(H)==NULL){Yes.val=false;Point.val=H;return;}else if (IdComp(H,Id)==0){Yes.val=true;Point.val=H;return;}else H=h2(H);if (H==H0){Yes.val=false;Point.val=NULL;return;}}}Функция IdComp(H,Id) сравнивает элемент таблицы на входе H с идентификатором и вырабатывает 0, если они равны.
Функция Empty(H) вырабатывает NULL, если вход H пуст. Функция Search присваивает параметрамYes и Pointer соответственно следующие значения :true, P — если найден требуемый идентификатор, где P — указательна вход в таблице, соответствующий этому идентификатору;false, NULL — если искомый идентификатор не найден, причем в таблиценет свободного места;7.3.
Таблицы расстановки со списками141false, P — если искомый идентификатор не найден, но в таблице естьсвободный вход P.Занесение элемента в таблицу можно осуществить следующей функцией:int Insert(String Id){BoolRef Yes;IntRef Point;Search(Id,Yes,Point);if (!Yes.val && (Point.val!=NULL)) InsertId(Point,Id);return(Point.val);}Здесь функция InsertId(Point,Id) заносит идентификатор Id для входа Point таблицы.7.3. Таблицы расстановки со спискамиТолько что описанная схема страдает одним недостатком — возможностьюпереполнения таблицы. Рассмотрим ее модификацию, когда все элементы,имеющие одинаковые значения (первичной) функции расстановки, связываются в список (при этом отпадает необходимость использования функций hiдля i > 2).
Таблица расстановки со списками — это массив указателей насписки элементов (рис. 7.3).Вначале таблица расстановки пуста (все элементы имеют значение NULL).При поиске идентификатора Id вычисляется функция расстановки h(Id)Рис. 7.3142Глава 7. Организация таблиц символови просматривается соответствующий линейный список. Поиск в таблице может быть описан следующей функцией:class Element{String IdentP;Element Next;};ArrayList T = new ArrayList(N);Element Search(String Id){ Element P;P=(Element)T.get(h(Id));while (1){if (P==null) return(null);else if (IdComp(P.IdentP,Id)==0) return(P);else P=P.Next;}}Занесение элемента в таблицу можно осуществить следующей функцией:Element Insert(String Id){ Element P,H;P=Search(Id);if (P!=null) return(P);else {H=H(Id);P=new Element();P.Next=(Element)T.get(h(Id));P.IdentP=Include(Id);T.add(H,P);}return(P);}Функция Include заносит идентификатор в таблицу идентификаторов.Алгоритм иллюстрируется рис.
7.4.Рис. 7.47.4. Функции расстановки1437.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. Переполнениепри выполнении арифметических операций можно игнорировать.Функция Hashpjw, приведенная ниже [3], вычисляется, начиная с H = 0(предполагается, что используются 32-битовые целые). Для каждого символасдвигаем биты H на 4 позиции влево и добавляем очередной символ. Есликакой-нибудь из четырех старших битов H равен 1, то сдвигаем эти 4 битана 24 разряда вправо, затем складываем по модулю 2 с H и устанавливаемв 0 каждый из четырех старших битов, равных 1:final int PRIME = 211;final int EOS = ’\0’;int Hashpjw(String s){char p;int H=0, g, i;int sLen = s.length();for (i=0; i<sLen; i++){H=(H<<4)+s.charAt(i);if ((g=H&0xf0000000)!=0){H=H^(g>>24);H=H^g;}}return H%PRIME; }144Глава 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
