Разработка компиляторов
Структура таблиц
Наша задача - разработать такую структуру таблицы идентификаторов, чтобы минимизировать поиск в ней. При этом следует помнить о том, что каждый идентификатор мы заносим в таблицу представлений, поэтому желательно иметь прямой доступ из таблицы представлений в таблицу идентификаторов для каждого идентификатора. Добавим к элементу таблицы представлений поле, которое будет содержать ссылку в таблицу идентификаторов, если находящаяся в этом элементе сущность является идентификатором. Элемент таблицы идентификаторов организуем так:
struct IdItem { ReprInd toRepr; /* ссылка в ReprTab на представление */ TypeInd toMode; /* тип идентификатора */ IdInd toId; /* ссылка на элемент таблицы идентификаторов с таким же значением поля toRepr */ }
Расширим структуру таблицы внешних представлений следующим образом:
struct ReprItem { HashInd toHash; /* значение hash-функции для лексемы */ unsigned short LexClass; /* лексический класс */ unsigned short LexMark; /* лексическая марка */ IdInd toId; /*ссылка в IdTab на доступное определение идентификатора */ }
Перейдем к формулировке алгоритма идентификации, который состоит из двух частей:
- первая часть алгоритма обрабатывает определяющие вхождения идентификаторов
- вторая часть алгоритма обрабатывает использующие вхождения идентификаторов
