Реклама:

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

Проще всего реализовать таблицу символических имен в виде массива пар, где первый элемент является именем (или указателем на имя), а второй - значением (или указателем на него). Если нужно найти какой-нибудь символ, то таблица символических имен просто последовательно просматривается, пока не будет найдено соответствие. Такой метод довольно легко запрограммировать, но он медленно работает, поскольку при каждом поиске в среднем придется просматривать половину таблицы.

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

Предположим, что средний элемент таблицы не равен искомому символу. Мы уже знаем, в какой половине таблицы он находится. Алгоритм двоичного поиска можно применить к соответствующей половине. В результате мы либо получим совпадение, либо определим нужную четверть таблицы. Таким образом, в таблице из п элементов нужный символ можно найти примерно за \0g2n попыток. Очевидно, что такой алгоритм работает быстрее, чем просто последовательный просмотр таблицы, но при этом элементы таблицы нужно сохранять в алфавитном порядке.

Совершенно другой подход - хэширование. В этом случае используется хэш-функция, которая отображает символы (имена) на целые числа в промежутке от 0 до к - 1. Такой функцией может быть функция перемножения АЗСП-кодов всех символов в имени. Можно перемножить все АЗСП-коды символов с игнорированием переполнения, а затем взять значение по модулю к или разделить полученное значение на простое число. Фактически подойдет любая входная функция, которая дает равномерное распределение значений. Символические имена можно хранить в таблице, состоящей из к сегментов, от О до & - 1. Все пары (символическое имя, значение), в которых имя соответствует г, сохраняются в связном списке, на который указывает слот г в хэш-таблице. Если в хэш-таблице содержится п символических имен и к слотов, то в среднем длина списка будет п/к Если мы выберем к, приблизительно равное п, то на нахождение нужного символического имени в среднем потребуется всего один поиск. Путем корректировки & мы можем сократить размер таблицы, но при этом скорость поиска снизится. Процесс хэширования иллюстрирует рис. 7.1.

Andy

14025

Anton

31253

Cathy

65254

Dick

54185

Erik

47357

Frances

56445

Frank

14332

Gerrit

32334

Hans

44546

Henri

75544

Jan

17097

Jaco

64533

Maarten

23267

Reind

63453

Roel

76764

Willem

34544

Wiebern

34344

Таблица символов

Рис. 7.1, Хэширование: символические имена, значения и хэш-коды, образованные от символических имен (а); хэш-таблица из 8 элементов со связным списком символических имен и значений (б)

Второй проход || Оглавление || Компоновка и загрузка