Лексический анализатор.

Лекция 11

Методы и основные этапы трансляции. Лексический анализ. Основные понятия.

Распознавание символов.

Лексический анализатор.

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

Лексемы — это цепочки литер. Текст программы — цепочка в алфавите лексем. Такая цепочка получила название лексической свертки программы.

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

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

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

Лексема состоит из класса и значения, которое представляется в виде ссылки на таблицу идентификаторов или литералов.

Входом в лексический анализатор является цепочка символов некоторого алфавита, причем некоторые комбинации символов часто рассматриваются как единые объекты:

1) Цепочки из нескольких пробелов рассматриваются как один пробел;

2) Ключевые слова (например, begin, end, do, integer и т.д.) считаются одним словом;

3) Цепочка, представляющая числовую константу, например, 12, 751, 51.78, рассматриваются как один элемент текста;

4) Идентификаторы тоже считаются лексическими единицами.

Выходом лексического анализатора является последовательность лексем. Этот выход является входом синтаксического анализатора.

Лексема – это цепочка терминальных символов. Ее структура имеет вид:

Тип лексемы – это константа, идентификатор, ключевое слово, название типа и т.д.

Данные – это указатель на адрес ячейки, хранящей информацию о данной конкретной лексеме. Для заданного языка число лексем предполагается конечным.

Пример.

На этапе лексического анализа в данной цепочке будет обнаружено, что COST, PRICE, TAX – это идентификаторы; знаки * и + сами являются лексемами; 0.98 – это константа.

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

Наш пример на выходе даст:

;

Символы + и * трактуются как лексемы, тип которых представлен ими самими, они не имеют связанных с ними данных, а, значит, не имеют указателей. В данном примере + и * не могут входить в идентификатор и поэтому мы легко отделяем идентификаторы. Однако бывают более сложные случаи. Например, правильные операторы на языке Fortran могут быть записаны:

(1)DO 10 I = 1.15

(2)DO 10 I = 1,15

В Fortran пробелы не учитываются, поэтому первую запись можно интерпретировать как DO10I = 1.15. Вторая запись означает, что мы выполняем цикл с I, изменяющимся от 1 до 15, то есть: DO 10 I = 1,15.

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

Эта таблица должна обеспечить:

§ Быстрое добавление новых идентификаторов и новых сведений о них;

§ Быстрый поиск информации, относящейся к данному идентификатору.

Выход лексического анализатора служит входом для следующих фаз компиляции — синтаксического анализа и интерпретации