Элементы компиляции программ
Можно предложить несколько способов организации таблицы идентификаторов. Самый простой и неэффективный – в виде массива указателей на списки переменной длины, элементы которого содержат символы идентификатора. Имена идентификаторов нужны лишь на этапе лексической свертки для выделения одинаковых идентификаторов. Важно понимать, что после выделения сканером идентификаторов и присвоения одинаковым из них ссылок на определенный элемент массива (таблицы) идентификаторов сами символьные имена уже не нужны. Если, конечно, не будет производиться формирование диагностических сообщений.
Впоследствии эти указатели можно переориентировать для ссылок на ячейки с другой информацией, например с адресом области памяти, которая будет выделена для данного идентификатора на этапе генерации кода. Аналогично можно организовать и таблицы констант, если в этом возникнет необходимость. Это самые простые варианты организации подобных таблиц. Но исходя из опыта, полученного при изучении материала данной книги, можно организовать таблицу символов более эффективно – в виде лексикографического дерева или используя методы хэширования. Если используется лексическое дерево, то каждый узел этого дерева может состоять из следующих полей:
- уникальный номер – номер, который на последующих этапах трансляции будет идентифицировать данное символьное имя;
- указатель на список, содержащий символы идентификатора;
- указатель на список с номерами строк, в которых встретился данный идентификатор.
Впоследствии, когда имена идентификаторов не будут нужны, можно на основе этого дерева построить хэш-таблицу, доступ к элементам которой будет осуществляться на основе уникальных номеров. Кстати, для повышения эффективности процесса распознавания стоит все терминальные символы – ключевые слова языка, разделители и т. п. (за исключением id, chint и ch_rea1) – также свести в отдельное лексикографическое дерево или организовать хеш-таблицу.
Можно поступить по-другому. Этот вариант, который можно использовать для анализа ввода в командной строке и т. д., работает в случае, если сканер вызывается из синтаксического анализатора. Суть его в том, что сканер вызывается из синтаксического анализатора, когда последнему нужна очередная лексема. Сканер выделяет ее во входном потоке и выдает синтаксическому анализатору кортеж из двух элементов: кода лексемы и строки, содержащей саму лексему.
А как организовать сам процесс распознавания лексем входной программы? Для этого попробуем сформулировать некий обобщенный алгоритм построения сканера.
- Выделить классы лексем.
- Определить классы литер.
- Определить условия выхода из сканера для каждого класса лексем.
- Для каждого класса лексем поставить в соответствие грамматику класса 3.
- Для каждой грамматики, построенной на шаге 4, построить конечный автомат, который будет распознавать лексему данного класса.
- Выполнить объединение ("склеивание") конечных автоматов для всех классов лексем.
- Составить матрицу переходов для "склеенного" конечного автомата.
- "Навесить" семантику на дуги "склеенного" конечного автомата.
- Выбрать коды лексической свертки для терминалов грамматики и формат таблицы идентификаторов.
- Разработать программу сканера.
Полностью реализовывать этот алгоритм для сканера транслятора упрощенного языка Паскаль мы не будем. Это не является предметом нашей книги. Нас интересуют прежде всего организация данных и возможности по работе с ними на ассемблере. Поэтому, для того чтобы пояснить подход к подобным задачам, мы остановим свое внимание на шагах 1-8 приведенного алгоритма.
Выделение классов лексем
Эффективность этапа лексического анализа не в последнюю очередь определяется правильностью разбиения лексем входной программы на классы. Причем эти классы не должны пересекаться. В ходе сканирования каждый входной терминальный символ (лексема) должен быть отнесен к одному из классов. Как мы уже отмечали выше, для грамматики псевдоязыка можно определить следующие классы лексем:
- идентификаторы – ID;
- ключевые слова – ПРОГРАММА, ПЕРЕМЕННЫЕ, НАЧ_ПРОГ, КОНПРОГ, НАЧ_БЛОК, КОН БЛОК, REAL, INTJYTE, INT_WORD, INT_DWORD, DIV, MOD, ЧИТАТЬ, ПИСАТЬ, ДЛЯ, ДОДЕЛАТЬ, ПОКА, ДОВНИЗ, ЕСЛИ, ЕСЛИ, ДО, ТО, ПЕРЕЙТИ_НА, ПОВТОРИТЬ;
- целые числа – CH_INT;
"Навешивание" семантики на дуги "склеенного" конечного автомата
В ходе распознавания (перехода по дугам) требуется выполнять различные действия, например поиск соответствия введенной лексемы ключевому слову в таблице ключевых слов, поиск идентификатора в таблице идентификаторов, преобразования чисел и т. д. Поэтому на этом шаге необходимо определить набор переменных и состав процедур, работающих во время переходов из состояния в состояние (на дугах).
Все… После этого можно программировать сканер. В главе 10, посвященной командам ММХ- и ХММ-расширений, нами будет выполнена практическая работа в этом направлении.