Разработка компиляторов

       

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


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

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

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

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



Содержание раздела