Атрибуты лексем

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

Пример. Рассмотрим следующий фрагмент программы на C#:

Последний оператор порождает следующую последовательность лексем и их атрибутов:

Будем считать, что у нас определен тип, соответствующий указателю в эту таблицу - ReprInd, и тип, служащий для представления позиции в исходном файле - FilePos. В этом случае мы можем полностью определить лексему следующим образом:

Таблица представлений

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

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

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

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