формирование таблиц символов.
6.2.10 Формирование таблиц символов.
В качестве примера приложения бинарных деревьев сформулируем алгоритм ведения древовидно-структурированной таблицы символов.
Основной критерий, которому должна удовлетворять программа ведения таблицы символов, состоит в максимальной эффективности поиска в этой таблицы. Это требование возникает на этапе компиляции, когда осуществляется много ссылок на записи таблицы символов. Необходимо, чтобы над таблицей символов можно было бы проверить две операции - включение записей в таблицу и поиск их в ней. Причем, каждая из этих операций содержит операцию просмотра таблицы.
Древовидное представление таблицы выбирают по двум причинам:
1. Записи символов по мере их возникновения равномерно распределяются в соответствии с лексикографическим порядком, то при хранении записей в дереве в таком же порядке табличный просмотр становится почти эквивалентен двоичному просмотру.
2. В древовидной структуре легко поддерживать лексикографический порядок, т.к. при включении в нее новой записи необходимо изменить лишь несколько указателей.
Для простоты предположим, что при ведении таблицы символов используется достаточно развитая система записей, допускающая символьные строки переменной длины.
Кроме того, предположим, что подпрограмма ведения таблицы символов используется при создании дерева данного блока программы. Это предположение ведет к тому, что попытка повторного включения записи вызывает ошибку. В глобальном контексте повторные записи допустимы, если они соответствую разным уровням блочной структуры программы.
В некотором смысле таблица символов представляет собой множество деревьев - по одному для каждого уровня блочной структуры программы.
Вершины бинарного дерева таблицы символов имеют формат:
| LPTR | SYMBOLS | INFO | RPTR |
- SYMBOLS - поле символьной строки, задающей идентификатор или имя переменной ( для обеспечения фиксированной длины описания вершин здесь можно хранить не саму строку, а лишь ее описатель );
- INFO - некоторое множество полей, содержащих дополнительно информацию об этом идентификаторе, например его тип данных.
Новая вершина создается путем исполнения оператора P при этом ее адрес запоминается в переменной P.
Еще предлагается, что перед любым исполнением программы ведения таблицы символов на некотором чистом уровне блочной структуры уже имеется соответствующая головная вершина дерева, в поле SYMBOLS в которое занесено значение, лексикографически большее, чем любой допустимый идентификатор. Эта вершина адресуется указателем HEAD[n], где n означает номер уровня блочной структуры. Т.е. предполагается, что при входе в блок осуществляется обращение к основной переменной, управляющей созданием головных вершин деревьев.
Операции включения записи в таблицу и операция поиска в таблице содержат значительное количество одинаковых действий ( например, просмотр ), поэтому рассмотрим только алгоритм TABLE, а различать включение или поиск по переменной FLAG. Если FLAG - истинно - то включение глобальной переменной, если - ложно - поиск. DATA - содержит имя идентификатора и дополнительную информацию для него.
Если включение новой записи было выполнено успешно, то FLAG сохраняет свое первоначальное значение противоположное начальному, что указывает на ошибку, означающую, что искомый идентификатор уже присутствует в таблице данного уровня и выполняемый алгоритм завершается. Если FLAG = ложь, то надо выполнить операцию поиска записи. В этом случае переменная NAME содержит имя идентификатора, который необходимо найти, а значение переменной. При успешном поиске переменная DATA устанавливается на поле INFO соответствующее записи таблицы символов. FLAG сохраняет свое значение и осуществляет возврат к вызванной программе. При неудаче операции поиска, FLAG меняет свое значение и выходит из алгоритма. В этом случае основная программа должна осуществлять поиск записи в таблице, более низких уровней. Деревья с головными вершинами HEAD[n-1], HEAD[n-2] b т.д.
