Построение таблиц идентификаторов с использованием методов хеширования.
Использование бинарного дерева поиска для построения таблицы идентификаторов.
Организация таблицы идентификаторов в виде упорядоченного массива записей. Метод бинарного поиска.
Организация таблицы идентификаторов в виде неупорядоченного массива записей. Метод линейного поиска.
Способы организации таблиц идентификаторов
Выделение идентификаторов и других лексем происходит на фазе лексического анализа. Проверка правильности семантики и генерация кода требуют знания характеристик идентификаторов, используемых в программе на исходном языке. Эти характеристики определяются на фазах синтаксического и семантического анализа, а также при подготовке к генерации кода. Например, имена переменных могут быть выделены сканером, типы данных – определены синтаксическим анализатором, а адреса связанных с переменными областей памяти – только на фазе подготовки к генерации кода. Характеристики идентификаторов выясняются по их описаниям и по характеру использования в программе. Состав и методы определения характеристик идентификаторов связаны с семантикой языка программирования. Информация об используемых в программе идентификаторах накапливается в таблицах идентификаторов, которые еще иначе называют таблицами символов.
В конкретной реализации компилятора таблица идентификаторов может быть одна, или же таких таблиц может быть несколько (по числу видов идентификаторов). Конкретный состав набора видов идентификаторов определяется входным языком программирования. Обычно под идентификаторами подразумеваются константы, переменные, имена процедур и функций, формальные и фактические параметры. Таблица идентификаторов представляет собой совокупность записей, каждая из которых содержит полную информацию об одном идентификаторе программы. Конкретный состав хранимой информации об идентификаторах (набор полей записи) определяется реализацией компилятора. Роль ключевого поля для доступа к требуемой записи играет код идентификатора.
На различных фазах функционирования компилятор многократно обращается к таблице идентификаторов для записи или извлечения информации. При этом эффективность выполнения этих действий компилятором напрямую зависит от способа организации хранения информации в таблице идентификаторов. Таблицы идентификаторов могут храниться памяти компьютера не только в виде собственно «таблиц», то есть массивов записей, где индекс записи в массиве – это номер строки в таблице. Использование других структур данных (деревьев, связанных списков) и методов их организации (хеширование) позволяет существенно повлиять на скорость доступа к хранимым данным.
Таким образом, таблицы идентификаторов – это специальным образом организованные наборы данных, предназначенные для хранения информации об элементах исходной программы (идентификаторах) и использующиеся для дальнейшего порождения текста результирующей программы.
Рассмотрим несколько наиболее известных способов организации таблиц идентификаторов.
В этом случае добавление элементов в таблицу идентификаторов осуществляется в порядке их поступления. Поиск искомого элемента в такой таблице возможен только путем сравнения заданного значения идентификатора с идентификатором в каждой строке таблицы. Поиск прекращается, как только будет найден подходящий элемент, или будет достигнут конец таблицы. Для таблицы, содержащей n элементов, среднее ожидаемое число сравнений равно n/2, а максимальное число сравнений равно n. Время поиска Тп в неупорядоченной таблице линейно зависит от количества содержащихся в ней элементов:
Тп=О(n).
Отсюда происходит и название описанного метода – линейный поиск. Очевидно, что если количество элементов в таблице велико, то данный способ ее организации не является эффективным.
Помещение элементов в таблицу идентификаторов компилятором происходит значительно реже, чем поиск требуемого идентификатора в таблице. Более того, каждая операция добавления нового элемента в таблицу обычно влечет за собой не менее одной операции поиска на предмет проверки наличия такого же идентификатора в таблице, поскольку в большинстве языков программирования идентификатор не может быть описан более одного раза. Отсюда следует, что значительно повысить скорость работы компилятора можно за счет увеличения скорости поиска. Если элементы таблицы идентификаторов упорядочены по значению ключа (отсортированы), тогда возможно применить достаточно эффективный метод бинарного (логарифмического) поиска, сущность которого состоит в следующем. Пусть в таблице n элементов. Заданное значение ключа сравнивается с ключом элемента, располагающегося в середине таблицы (номер этого элемента - (n + 1)/2). Если они равны, то искомый элемент найден. В противном случае, повторяем алгоритм для элементов, расположенных выше или ниже серединного элемента в зависимости от того, меньше или больше искомое значение того, с которым его сравнили. Поиск прекращается, как только найден элемент с заданным значением ключа, или в рассматриваемом блоке элементов не останется ни одного элемента. Так как на каждом шаге число элементов, среди которых производится поиск, сокращается наполовину, то максимальное число сравнений равно 1+ log2 n. Так, при n = 128 бинарный поиск требует не больше 8 сравнений, а поиск в неупорядоченной таблице - в среднем 64 сравнения. При этом время поиска Тп логарифмически зависит от количества элементов в таблице идентификаторов:
Тп =О(log2 n).
Легко видеть, что при использовании метода бинарного поиска время поиска искомого элемента существенно сокращается по сравнению с методом линейного поиска. Однако время, затрачиваемое на помещение элемента в таблицу, увеличивается, поскольку таблица должна все время поддерживаться в упорядоченном состоянии. С этой целью для построения таблицы идентификаторов необходимо использовать стандартные алгоритмы организации упорядоченных массивов данных [10]. Если применять стандартные алгоритмы сортировки массивов данных, а поиск места включения идентификатора в таблицу осуществлять методом бинарного поиска, то среднее время Тз заполнения таблицы из n идентификаторов оценивается следующим образом:
Тз=О(n*log2 n)+k*О(n2),
где k - коэффициент, выражающий соотношение между временем выполнения компьютером операции сравнения и временем выполнения операции переноса данных.
Таким образом, использование метода бинарного поиска при работе с таблицей идентификаторов позволяет существенно сократить время поиска требуемого элемента за счет увеличения времени, затрачиваемого на помещение нового элемента в таблицу. Очевидно, что добавление новых идентификаторов в таблицу происходит значительно реже, чем последующее обращение к ним. Более того, каждая операция добавления нового элемента в таблицу идентификаторов требует, как правило, не менее одной операции поиска, поскольку в большинстве языков программирования идентификатор не может быть описан более одного раза. Поэтому рассмотренный метод организации таблицы идентификаторов следует признать более эффективным, чем метод организации неупорядоченной таблицы.
Дерево является одной из самых распространенных структур, используемых для представления данных в памяти компьютера. Известно много разновидностей этой структуры и детально изучены свойства каждой из них [10]. Мы ограничимся рассмотрением бинарных деревьев поиска, использование которых для построения таблиц идентификаторов позволяет сократить время поиска элемента в таблице, не увеличивая значительно времени заполнения таблицы.
Деревом называется конечное множество, состоящее из одного или более элементов, называемых узлами, таких, что:
1) между узлами имеет место отношение типа «исходный-порожденный»;
2) есть только один узел, не имеющий исходного, - он называется корнем;
3) все узлы, за исключением корня, имеют только один исходный;
4) каждый узел может иметь несколько порожденных;
5) отношение «исходный-порожденный» действует только в одном направлении, то есть ни один потомок некоторого узла никогда не может стать для него предком.
Число порожденных узлов отдельного узла называется степенью данного узла. Максимальное значение степени всех узлов дерева называется степенью дерева.
Дерево, все узлы которого имеют степень не больше 2, называется бинарным деревом.Бинарное дерево представляет собой конечное множество узлов, которое:
1) или пусто,
2) или состоит из одного корня и двух бинарных деревьев, называемых левым, и правым поддеревьями этого корня.
Из определения следует, что дерево, у которого корень имеет только левое поддерево, и дерево, у которого корень имеет только правое поддерево, считаются разными.
Если в дереве между порожденными узлами, имеющими общий исходный, считается существенным их порядок, то дерево называется упорядоченным. Очень важным является тот факт, что при поиске почти во всех случаях имеют дело с упорядоченными деревьями.
Бинарным деревом поиска называют такое бинарное дерево, в котором для каждого узла дерева все ключи в левом поддереве меньше, а в правом поддереве больше значения ключа данного узла.
Для того чтобы структуру произвольного бинарного дерева представить в памяти ЭВМ, необходимо как минимум следующее:
1) каждый узел должен содержать один ключ и два указателя на левое и правое поддеревья;
2) если узел не имеет левого и (или) правого поддеревьев, то указатель на соответствующее поддерево будет пустым (NULL);
3) чтобы сделать дерево доступным для обработки, необходимо задать указатель на корень root.
Вышеописанную структуру следует рассматривать не более как схему. Например, в узле могут храниться кроме ключа также и данные, если они имеют небольшой объем. При большом объеме таких данных их хранят обычно отдельно, а в узел включают соответствующий указатель. Часто бывает целесообразно хранить в каждом узле не только указатели на порожденные поддеревья, но и указатель на исходный узел. Кроме того, для упрощения поиска желательно иметь в каждом узле данные о числе узлов левого поддерева: (число узлов левого поддерева данного узла) + 1. Однако в связи с тем, что все эти расширения приводят не только к увеличению занимаемого пространства памяти, но и к усложнению операций обновления данных, необходимо очень тщательно анализировать все плюсы и минусы в зависимости от того, какие данные хранятся в узле и в каком виде, какие операции будут выполняться над деревьями, каковы объем памяти и вычислительные ресурсы компьютера, который будет использоваться.
Пример структуры бинарного дерева поиска и его отображения на память компьютера показан на рис. 3.3. В нашем случае каждый узел бинарного дерева поиска представляет собой элемент таблицы идентификаторов, к которому для организации связи добавлены два дополнительных поля – указатели на правое и левое поддеревья. Таким образом, бинарное дерево поиска легко реализуется в виде нелинейного двусвязного списка.
Алгоритм заполнения таблицы идентификаторов по методу бинарного дерева поиска, достаточно прост. В ходе лексического разбора исходного текста программы порождается входной поток данных, содержащий идентификаторы. Первый идентификатор считается корнем дерева. Все последующие идентификаторы помещаются в дерево в соответствии с нижеприведенным алгоритмом.
Шаг 1. Выбрать очередной идентификатор из входного потока данных. Если такового нет, то построение дерева закончено.
Шаг 2. Сделать текущим узлом корень дерева.
Шаг 3. Сравнить очередной идентификатор с ключом текущего узла дерева. Если очередной идентификатор меньше текущего ключа, то перейти к шагу 4; если равен – сообщить об ошибке (двух одинаковых идентификаторов быть не должно) и прекратить выполнение алгоритма; иначе - перейти к шагу 6.
Шаг 4. Если у текущего узла существует левое поддерево, то сделать его корень текущим узлом и перейти к шагу 3; иначе – перейти к шагу 5.
Шаг 5. Создать новый узел; поместить в него очередной идентификатор как значение ключа; в указатель на левое поддерево текущего узла записать адрес вновь созданного узла; вернуться к шагу 1.
Шаг 6. Если у текущего узла существует правое поддерево, то сделать его корень текущим узлом и перейти к шагу 3; иначе – перейти к шагу 7.
Шаг 7. Создать новый узел; поместить в него очередной идентификатор как значение ключа; в указатель на правое поддерево текущего узла записать адрес вновь созданного узла; вернуться к шагу 1.
Рассмотрим в качестве примера последовательность идентификаторов FUN, D1, KOL, A, J2, LL, J1. Процесс построения бинарного дерева поиска для
этой последовательности идентификаторов детально изображается на рис.3.4.
Алгоритм поиска элемента в таблице идентификаторов, построенной по методу бинарного дерева поиска.
Шаг 1. Сделать текущим узлом корень дерева.
Шаг 2. Сравнить аргумент поиска с ключом текущего узла дерева. Если они равны – искомый элемент найден, выполнение алгоритма прекращается; если аргумент поиска меньше значения ключа текущего узла - перейти к шагу 3; иначе – перейти к шагу 4.
Шаг 3. Если у текущего узла существует левое поддерево, то сделать его корень текущим узлом и перейти к шагу 2; иначе – искомый элемент не найден, выполнение алгоритма прекращается.
Шаг 4. Если у текущего узла существует правое поддерево, то сделать его корень текущим узлом и перейти к шагу 2; иначе – искомый элемент не найден, выполнение алгоритма прекращается.
Например, произведем поиск идентификатора J2 в бинарном дереве, изображенном на рис. 3.4.
Сначала текущим узлом является корень дерева. Сравниваем идентификаторы J2 и FUN – искомый идентификатор больше, поэтому переходим к рассмотрению правого поддерева текущего узла. Делаем текущим узлом корень этого поддерева и опять сравниваем идентификаторы: J2 меньше KOL, значит дальнейший поиск следует вести в левом поддереве текущего узла. Считаем теперь текущим узлом корень левого поддерева и осуществляем сравнение идентификаторов: J2 равно J2 – идентификатор найден.
Проследим теперь порядок поиска такого идентификатора, который отсутствует в рассматриваемом нами бинарном дереве. Пусть аргументом поиска является идентификатор D2. Начинаем поиск с корневого узла дерева. Поскольку D2 меньше FUN, делаем текущим узел D1 и производим очередное сравнение. Искомый идентификатор больше D1, но так как правое поддерево у текущего узла отсутствует – идентификатор не найден, и выполнение алгоритма прекращается.
Для данного метода число требуемых сравнений и форма бинарного дерева непосредственно зависят порядка поступления идентификаторов. В ряде случаев бинарное дерево вырождается в упорядоченный однонаправленный связный список (например, для последовательности идентификаторов А1, А2, А3, А4, А5). Высота такого бинарного дерева равна количеству идентификаторов n, в силу чего доступ к данным существенно замедляется. Чтобы этого избежать, задачу построения дерева необходимо несколько усложнить, так, чтобы на каждом уровне располагалось максимально возможное количество узлов, а высота дерева, соответственно, была минимальной.
Для решения подобной задачи вводится понятие сбалансированности дерева и выделяется класс сбалансированных деревьев, обладающих всеми преимуществами бинарных деревьев поиска и никогда не вырождающихся. Такие деревья часто называют АВЛ-деревьями по имени их открывателей (Андельсон-Вельский Г.М., Ландис Е.М.). Особенности и порядок построения АВЛ-деревьев подробно описываются в [10].
В общем случае последовательность идентификаторов в исходной программе является статистически неупорядоченной и, соответственно, построенное бинарное дерево является невырожденным. Тогда среднее время Тз заполнения бинарного дерева из n идентификаторов и среднее время Тп поиска в нем оценивается следующим образом:
Тз= О(n*log2 n),
Тп= О(log2 n)
Метод бинарного дерева в целом достаточно эффективен и используется в ряде компиляторов для организации таблиц идентификаторов. Некоторые компиляторы строят несколько различных деревьев для идентификаторов разных типов и разной длины.
Поскольку в реальных исходных текстах программ количество идентификаторов достаточно велико, то даже логарифмическую зависимость времени поиска заданного идентификатора от общего числа идентификаторов нельзя признать удовлетворительной. Сделать поиск информации в таблице идентификаторов более эффективным позволяет использование методов хеширования, которые практически всегда применяются в той или иной степени при построении таблиц идентификаторов в реальных компиляторах.
Сущность метода заключается в том, что индекс элемента в таблице идентификаторов получают путем "хеширования" идентификатора, а именно - применением к нему хеш-функции.
Хеш-функцией H называется некоторое отображение множества входных элементов R на множество целых неотрицательных чисел Z:
H(r)=n, где rÎR, nÎZ .
В нашем случае областью определения R хеш-функции H является множество всех возможных имен идентификаторов, а областью значений – некоторое подмножество М из множества целых неотрицательных чисел Z: MÌZ, состоящее из всех возможных значений, вырабатываемых функцией H, то есть "rÎR: H(r)ÎM.
Термин «хеш-функция» (hash function) происходит от английского hash – перемалывать, смешивать.
Процесс отображения области определения хеш-функции на множество ее значений называется хешированием.
В русскоязычной литературе метод хеширования часто называют методом преобразования ключей или просто «расстановкой», а хеш-функцию, соответственно, - функцией расстановки.
Хеш-адресация заключается в использовании значения, возвращаемого хеш-функцией, в качестве индекса (адреса) элемента в некотором массиве данных (в нашем случае – таблицы идентификаторов).
Очевидно, что размер массива данных должен соответствовать области значений используемой хеш-функции, откуда следует, что область значений хеш-функции не должна превышать размер доступного адресного пространства компьютера.
Таким образом, метод организации таблиц идентификаторов с использованием хеширования заключается в размещении каждого идентификатора в той строке таблицы, индекс которой получен путем вычисления хеш-функции для данного идентификатора.
В общем случае для размещения или поиска идентификатора в таблице необходимо вычислить его хеш-функцию и обратиться по полученному индексу к соответствующей строке таблицы.
Метод хеширования весьма эффективен, поскольку время размещения и время поиска идентификатора в таблице определяется только временем вычисления хеш-функции. Однако рассмотренный выше способ организации таблицы идентификаторов имеет и очевидные недостатки. Во-первых, память при такой организации хеш-таблицы используется неэффективно, поскольку размер массива для ее хранения должен соответствовать области значений хеш-функции, в то время как реально хранимых в таблице данных будет значительно меньше. Во-вторых, непростой задачей является разумный выбор хеш-функции. Хеш-функция должна вычисляться достаточно эффективно, то есть состоять из небольшого числа основных арифметических и логических операций, а также равномерно отображать значения идентификаторов на весь диапазон изменения индексов массива, в котором будут храниться идентификаторы.
Собственно хеш-функция представляет собой некоторый набор простых арифметических и логических действий, производимых над идентификатором. В качестве примера примитивной хеш-функции можно привести код внутреннего представления в ЭВМ первой литеры идентификатора.
Пока для двух различных элементов результаты хеширования различны, время поиска совпадает со временем, затраченным на хеширование. Однако возникает затруднение, когда результаты хеширования двух разных элементов совпадают. Это называется коллизией. В одну позицию таблицы может быть помещен только один из конфликтующих элементов. Удачная хеш-функция распределяет элементы в таблице равномерно, так что коллизии возникают не столь часто. Хеш-функция, предложенная выше, очевидно неудачна, так как все идентификаторы, начинающиеся с одной буквы, ссылаются на один и тот же адрес. Существует множество различных хеш-функций, но ни одна из них не позволяет полностью избавиться от коллизий. На практике при разработке алгоритма хеш-функции обычно стремятся максимально уменьшить количество возникающих коллизий для ограниченного набора идентификаторов, а именно, тех идентификаторов, которые наиболее часто встречаются в программах. С этой целью производится статистическая обработка данных для определенного множества типичных программ.
Для разрешения коллизий существует достаточно много способов. Одним из наиболее удачных является метод цепочек. Метод цепочек использует кроме таблицы идентификаторов дополнительную хеш-таблицу, которая должна быть пустой в начале работы алгоритма. Таблица идентификаторов формируется динамически по мере добавления в нее элементов и представляет собой совокупность однонаправленных списков (цепочек). Каждый элемент списка включает в себя кроме значения идентификатора дополнительное поле ссылки на следующий элемент списка. Адреса образующихся списков хранятся в хеш-таблице.
При добавлении идентификатора в таблицу для него вычисляется хеш-функция (адрес ячейки в хеш-таблице). Если ячейка в хеш-таблице по вычисленному адресу пустая, то динамически выделяется память под первый элемент списка, куда заносится значение идентификатора. Адрес первого элемента списка заносится в соответствующую ячейку хеш-таблицы. В противном случае происходит переход по ссылкам в конец списка, и туда добавляется еще один элемент (динамически выделяется память, в выделенную область памяти записывается значение идентификатора, а адрес выделенного участка памяти заносится в поле ссылки предыдущего элемента).
При поиске необходимого элемента цепочка просматривается до тех пор, пока не будет встречен нужный элемент или цепочка не закончится (тогда элемент не найден).
Интересным вариантом является комбинирование метода цепочек с другими вариантами организации таблиц символов: цепочка идентификаторов с одинаковым значением хеш-функции может представлять собой неупорядоченный или упорядоченный списки, либо, например, бинарное дерево. В зависимости от способа организации цепочки меняются соответственно и методы поиска.
Метод цепочек является очень эффективным средством организации таблиц идентификаторов. Среднее время на размещение или поиск элемента зависит только от среднего числа коллизий, возникающих при вычислении хеш-функции. Этот метод позволяет более экономно использовать память, но требует затрат на организацию работы с динамическими структурами данных.
В основе описания лексических конструкций языков программирования лежат регулярные языки. Существует несколько способов для задания регулярных языков, но наибольший интерес представляют два следующих формализма: регулярные (леволинейные и праволинейные) грамматики и конечные автоматы. Эти два способа задания регулярных языков эквивалентны. Существуют алгоритмы, которые позволяют для регулярного языка, заданного регулярной грамматикой, построить конечный автомат и наоборот.
Как уже было нами отмечено, классы леволинейных и праволинейных грамматик эквивалентны. Разница между леволинейными и праволинейными грамматиками заключается в основном в том, в каком порядке строятся предложения языка: слева направо или справа налево. Поскольку предложения языков программирования строятся обычно слева направо, то в дальнейшем, если особо не оговорено, под регулярной грамматикой будем понимать леволинейную грамматику.
Для простоты введем еще одно соглашение: будем считать, что анализируемая цепочка заканчивается специальным символом ^ -признаком конца цепочки.
Для регулярных грамматик существует алгоритм определения того, принадлежит ли анализируемая цепочка языку, порождаемому этой грамматикой (алгоритм разбора):
(1) первый символ исходной цепочки a1a2...an^ заменяем нетерминалом A, для которого в грамматике есть правило вывода A ® a1 (другими словами, производим "свертку" терминала a1 к нетерминалу A)
(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: полученный на предыдущем шаге нетерминал A и расположенный непосредственно справа от него очередной терминал ai исходной цепочки заменяем нетерминалом B, для которого в грамматике есть правило вывода B ® Aai (i = 2, 3,.., n);
Данный алгоритм эквивалентен алгоритму построения дерева разбора методом "снизу-вверх": на каждом шаге алгоритма строим один из уровней в дереве разбора, "поднимаясь" от листьев к корню.
При работе этого алгоритма возможны следующие ситуации:
1) прочитана вся цепочка; на каждом шаге находилась единственная нужная "свертка"; на последнем шаге свертка произошла к символу S. Это означает, что исходная цепочка a1a2...an^ Î L(G).
2) прочитана вся цепочка; на каждом шаге находилась единственная нужная "свертка"; на последнем шаге свертка произошла к символу, отличному от S. Это означает, что исходная цепочка a1a2...an^ Ï L(G).
3) на некотором шаге не нашлось нужной свертки, то есть для полученного на предыдущем шаге нетерминала A и расположенного непосредственно справа от него очередного терминала ai исходной цепочки не нашлось нетерминала B, для которого в грамматике было бы правило вывода B ® Aai. Это означает, что исходная цепочка a1a2...an^ Ï L(G).
4) на некотором шаге работы алгоритма оказалось, что есть более одной подходящей свертки, то есть в грамматике разные нетерминалы имеют правила вывода с одинаковыми правыми частями, и поэтому непонятно, к какому из них производить свертку. Это говорит онедетерминированности разбора. Анализ этой ситуации будет дан ниже.
