Задачи лексического анализа (стр. 2 )

ТЗ = О(N*log2N) + k*О(N2).

Здесь k — некоторый коэффициент, отражающий соотношение между времена­ми, затрачиваемыми компьютером на выполнение операции сравнения и опера­ции переноса данных.

В итоге при организации логарифмического поиска в таблице идентификаторов мы добиваемся существенного сокращения времени поиска нужного элемента за счет увеличения времени на помещение нового элемента в таблицу. Посколь­ку добавление новых элементов в таблицу идентификаторов происходит сущест­венно реже', чем обращение к ним, то этот метод следует признать более эффек­тивным, чем метод организации неупорядоченной таблицы.

Построение таблиц идентификаторов по методу бинарного дерева

Можно сократить время поиска искомого элемента в таблице идентификато­ров, не увеличивая значительно время, необходимое на ее заполнение. Для этого надо отказаться от организации таблицы в виде непрерывного массива данных.

Существует метод построения таблиц, при котором таблица имеет форму бинар­ного дерева. Каждый узел дерева представляет собой элемент таблицы, причем корневой узел является первым элементом, встреченным при заполнении табли­цы. Дерево называется бинарным, так как каждая вершина в нем может иметь не более двух ветвей (и, следовательно, не более двух нижележащих вершин). Для определенности будем называть две ветви «правая» и «левая».

Рассмотрим алгоритм заполнения бинарного дерева. Будем считать, что алго­ритм работает с потоком входных данных, содержащим идентификаторы (в ком­пиляторе этот поток данных порождается в процессе разбора текста исходной программы). Первый идентификатор, как уже было сказано, помещается в вер­шину дерева. Все дальнейшие идентификаторы попадают в дерево по следующе­му алгоритму.

Шаг 1. Выбрать очередной идентификатор из входного потока данных. Если оче­редного идентификатора нет, то построение дерева закончено.

Шаг 2. Сделать текущим узлом дерева корневую вершину.

Шаг 3. Сравнить очередной идентификатор с идентификатором, содержащемся в текущем узле дерева.

Шаг 4. Если очередной идентификатор меньше, то перейти к шагу 5, если ра­вен — сообщить об ошибке и прекратить выполнение алгоритма (двух одинако­вых идентификаторов быть не должно!), иначе — перейти к шагу 7.

Шаг 5. Если у текущего узла существует левая вершина, то сделать ее текущим узлом и вернуться к шагу 3, иначе — перейти к шагу 6.

Шаг 6. Создать новую вершину, поместить в нее очередной идентификатор, сде­лать эту новую вершину левой вершиной текущего узла и вернуться к шагу 1.

Шаг 7. Если у текущего узла существует правая вершина, то сделать ее текущим узлом и вернуться к шагу 3, иначе — перейти к шагу 8.

Шаг 8. Создать новую вершину, поместить в нее очередной идентификатор, сде­лать эту новую вершину правой вершиной текущего узла и вернуться к шагу 1.

Рассмотрим в качестве примера последовательность идентификаторов GA, Dl, M22, Е, А12, ВС, F. На рис. 13.2 проиллюстрирован весь процесс построения бинарного дерева для этой последовательности идентификаторов.

Поиск нужного элемента в дереве выполняется по алгоритму, схожему с алго­ритмом заполнения дерева.

Шаг 1. Сделать текущим узлом дерева корневую вершину.

Шаг 2. Сравнить искомый идентификатор с идентификатором, содержащемся в текущем узле дерева.

Шаг 4. Если идентификаторы совпадают, то искомый идентификатор найден, ал­горитм завершается, иначе — надо перейти к шагу 5.

Шаг 5. Если очередной идентификатор меньше, то перейти к шагу 6, иначе — пе­рейти к шагу 7.

Рис 13.2. Пошаговое заполнение бинарного дерева для последовательности идентификаторов GA, D1, M22, Е, А12, ВС, F

Шаг 6. Если у текущего узла существует левая вершина, то сделать ее текущим

узлом и вернуться к шагу 2, иначе искомый идентификатор не найден, алгоритм

завершается.

Шаг 7. Если у текущего узла существует правая вершина, то сделать ее текущим

узлом и вернуться к шагу 2, иначе искомый идентификатор не найден, алгоритм

завершается.

Например, произведем поиск в дереве, изображенном на рис. 13.2, идентифи­катора А12. Берем корневую вершину (она становится текущим узлом), сравни­ваем идентификаторы GA и А12. Искомый идентификатор меньше - текущим узлом становится левая вершина Dl. Опять сравниваем идентификаторы. Иско­мый идентификатор меньше - текущим узлом становится левая вершина А12. При следующем сравнении искомый идентификатор найден.

Если искать отсутствующий идентификатор - например, All, - то поиск опять пойдет от корневой вершины. Сравниваем идентификаторы GA и АН. Искомый идентификатор меньше - текущим узлом становится левая вершина Dl. Опять сравниваем идентификаторы. Искомый идентификатор меньше - текущим уз­лом становится левая вершина А12. Искомый идентификатор меньше, но левая вершина у узла А12 отсутствует, поэтому в данном случае искомый идентифика­тор не найден.

Для данного метода число требуемых сравнений и форма получившегося дерева во многом зависят от того порядка, в котором поступают идентификаторы. На­пример, если в рассмотренном выше примере вместо последовательности идентификаторов GA, 01, M22, E, A12, ВС, F взять последовательность А12, GA, D1, (22, E, ВС, F, то полученное дерево будет иметь иной вид. А если в качестве при­зера взять последовательность идентификаторов А, В, С, D, E, F, то дерево выродится в упорядоченный однонаправленный связный список. Эта особенность 1вляется недостатком данного метода организации таблиц идентификаторов. Другим недостатком является необходимость работы с динамическим выделением памяти при построении дерева.

Если предположить, что последовательность идентификаторов в исходной программе является статистически неупорядоченной (что в целом соответствует действительности), то можно считать, что построенное бинарное дерево будет невырожденным. Тогда среднее время на заполнение дерева (ТЗ) и на поиск элемента в нем (ТП) можно оценить следующим образом [6, т. 2]:

ТЗ = N*О(log2 N).

TП = О(log2 N).

В целом метод бинарного дерева является довольно удачным механизмом для организации таблиц идентификаторов. Он нашел свое применение в ряде компиляторов. Иногда компиляторы строят несколько различных деревьев для идентификаторов разных типов и разной длины [23, 74].

Хэш-функции и хэш-адресация. Принципы работы хэш-функций

Логарифмическая зависимость времени поиска и времени заполнения таблицы идентификаторов — это самый хороший результат, которого можно достичь за счет применения различных методов организации таблиц. Однако в реальных сходных программах количество идентификаторов столь велико, что даже логарифмическую зависимость времени поиска от их числа нельзя признать удовлетворительной. Необходимы более эффективные методы поиска информации таблице идентификаторов.

лучших результатов можно достичь, если применить методы, связанные с использованием хэш-функций и хэш-адресации.

Хэш-функцией F называется некоторое отображение множества входных элементов R на множество целых неотрицательных чисел Z: F(r) = n, rÎR, nÎZ. Сам термин «хэш-функция» происходит от английского термина «hash function» (hash — «мешать», «смешивать», «путать»). Вместо термина «хэширование» иногда используются термины «рандомизация», «переупорядочивание».

Множество допустимых входных элементов R называется областью определения хэш-функций. Множеством значений хэш-функций F называется подмножество М из множества целых неотрицательных чисел Z: MÎZ, содержащее все возможные значения, возвращаемые функцией F: "rÎR: F(r)ÎM. Процесс отображения области определения хэш-функций на множество значений называет-«хэшированием».

При работе с таблицей идентификаторов хэш-функция должна выполнять отображение имен идентификаторов на множество целых неотрицательных чисел.

Областью определения хэш-функций будет множество всех возможных имен идентификаторов.

Хэш-адресация заключается в использовании значения, возвращаемого хэш-функцией, в качестве адреса ячейки из некоторого массива данных. Тогда размер массива данных должен соответствовать области значений используемой хэш-функций. Следовательно, в реальном компиляторе область значений хэш-функ­ций никак не должна превышать размер доступного адресного пространства компьютера.

Метод организации таблиц идентификаторов, основанный на использовании хэш-адресации, заключается в размещении каждого элемента таблицы в ячейке, адрес которой возвращает хэш-функция, вычисленная для этого элемента. Тогда в иде­альном случае для размещения любого элемента в таблице идентификаторов достаточно только вычислить его хэш-функцию и обратиться к нужной ячейке массива данных. Для поиска элемента в таблице необходимо вычислить хэш-функцию для искомого элемента и проверить, не является ли заданная ею ячей­ка массива пустой (если она не пуста — элемент найден, если пуста — не най­ден).

На рис. 13.3 проиллюстрирован метод организации таблиц идентификаторов с использованием