Лексический анализ

ЛАБОРАТОРНАЯ РАБОТА 3. ИЗУЧЕНИЕ ЭТАПА ЛЕКСИЧЕСКОГО АНАЛИЗА ТРАНСЛЯТОРОВ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

Цель работы: Изучить методы построения лексических сканеров на основе конечных автоматов и формальных грамматик.

Архитектура компилятора

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

- препроцессирование;

- лексический анализ;

- синтаксический анализ;

- генерация кода;

- оптимизация программы.

Рассмотрим более подробно этап лексического анализа. Программа, которая выполняет этот этап называется лексический анализатор или сканер. Сканер переводит текст исходной программы из последовательности символов или строк в последовательность лексем. Лексема - минимальный элемент языка программирования. Для заданного языка программирования число типов лексем предполагается конечным.

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

Лексический анализ

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

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

Числа, строки символов заключенные в кавычки и другие самоопределенные данные классифицируются как "литералы". Информация о них заносится в таблицу литералов. В отличие от идентификаторов литералы позволяют определить их атрибуты.

Рассмотрим пример построения описанных таблиц при компиляции следующей программы:

main()

{ int a;

char * b=".dat";

a=a+2;

}

Таблица терминальных символов(TRM). Таблица стандартных символов.

Таблица идентификаторов (IDN). Таблица литералов (LTR).

Рассмотренные выше таблицы демонстрируют основные правила построения. Таблица терминальных символов уже заложена в компиляторе и в данном случае ее содержимое построено конкретно для примера.

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

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

Таблица блоков.

Лексический сканер должен учитывать области видимости и кодировать их по-разному.

Содержание задания: Разработать программу лексического сканирования и анализа для заданных языка программирования и типов лексем. Программа должна построить заданные таблицы и на их основе преобразовать анализируемую программу, заменив искомые лексемы на мнемонические имена. Мнемонические имена должны генерироваться так, чтобы любая лексема заменялась уникальным именем, а имя отражало ее тип (например, I1 - первая лексема целого типа).