3. Организация таблиц компилятора
Итак, уже на стадии лексического анализа мы столкнулись с необходимостью использования и формирования целого ряда таблиц. При работе компиляторов объем этих таблиц иногда бывает очень большим. Организация таблицы и алгоритмы их обработки должны быть такими, чтобы обеспечить:
быстрый поиск информации в таблице;
быстрое добавление новых элементов в таблицу.
В большинстве алгоритмов эти положения противоречивы и требуют компромиссных решений. Вспомним, а может быть, предложим новые для Вас способы организации таблиц и методы работы с ними.
3.1. Общий вид таблиц
Таблицы всех типов имеют общий вид, представленный на рис. 3.1, где слева перечисляются аргументы, а справа соответствующие значения.
Каждый элемент таблицы обычно занимает более одного машинного слова. Если элемент занимает K слов памяти и нужно хранить N элементов, то для организации таблицы необходимо иметь KN слов памяти. Расположить информацию можно двумя способами :
1. Каждый элемент поместить в K последовательных слов и иметь таблицу из KN слов.
2. Иметь K таблиц, с именами T1, T2, ...,Tk из N слов в каждой таблице. Весь i–ый элемент будет при этом находиться в словах T1 i, T2 i, ...,Tk i.
Вопрос выбора между этими двумя методами – это только вопрос удобства программирования.
В нашем случае аргументами таблицы являются символы или идентификаторы, а значениями их характеристики (атрибуты). Так как число символов в идентификаторе может быть самым разным, то как уже отмечалось, в аргументе, обычно, вместо самого идентификатора помещают указатель на идентификатор. Это сохраняет фиксированный размер аргумента. Сами же идентификаторы хранятся в специальном списке строк. Число литер в каждом идентификаторе может храниться как часть аргумента или в списке идентификаторов прямо перед ним. На рисунке 3.2 показаны оба эти способа на примере таблицы, содержащей элементы для идентификаторов I, max и J.
Если число элементов в поле значения переменно, то в этом поле таблицы также следует помещать указатель на эту информацию. Формат таблицы лучше оставлять фиксированным.
Рассмотрим существующие способы организации таблиц и оценим время требуемое на поиск элементов и их добавление.
3.2. Прямой доступ к таблице или метод индексов
Суть этого метода состоит в том, что по символам цепочки (идентификатора) вычисляется индекс, который обеспечивает прямой доступ к таблице (индекс массива). В качестве примера рассмотрим проблему идентификации переменных языка MINI–BASIC. Переменная в нем либо английская буква, либо буква, за которой следует цифра. Всего имеется 286 допустимых переменных MINI–BASIC. Так как это число невелико, то можно позволить себе завести по одному элементу таблицы для каждой допустимой переменной. Тогда проблема поиска переменной сводиться к простому преобразованию имени в индекс. Один из способов состоит в присваивание индексу значения от 1 до 26 для каждой входной буквы английского алфавита. Далее, если следующий символ – произвольная цифра d, то к индексу буквы прибавляется число 26(d+1). Это значит, что переменная Z получит номер 26, A0 – 27, а Z9–286.
Индексный метод можно эффективно применять при выполнении 3–х условий. Во–первых, число слов не должно быть слишком большим. Поэтому, такой метод нельзя применять даже для имен переменных ФОРТРАНа (не более шести символов), т.к. их более миллиарда. Во–вторых, индекс должен легко вычисляться. Это условие может исключить даже небольшое множество ключевых слов, так как хороший способ построения индекса по ним вряд ли удастся предложить. В–третьих, объем множества слов фиксируется при построении, так как изменение метода вычисления индекса во время компиляции требует реорганизации всей таблицы. Если учесть эти три условия, то становится очевидным, что рассматриваемым методом можно воспользоваться нечасто. Тем не менее, когда он применим, поиск и включение элемента (отметка что он включен) осуществляется с минимальными затратами времени.