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

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

При проведении лексического анализа из текста программы исключаются комментарии, пробелы, символы табуляции и перевода строки. В ряде случаев также проверяется парность скобок.

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

Уже отмечалось, что в лексической свертке каждая лексема заменяется дескриптором. Дескриптор имеет единый формат для всех типов лексем, и содержит два поля:

(<тип лексемы>, <указатель>)

<тип лексемы> – это, как правило, числовой код класса лексемы. Количество классов в языках программирования может быть различным. Наиболее распространенными классами являются:

· идентификаторы (имена переменных, процедур, функций, меток и т.д);

· служебные (ключевые) слова;

· числовые константы (целые неотрицательные числа, состоят только из цифр). Лексическая свертка вещественного числа включает дескриптор целой части числа и дескриптор дробной части числа;

· разделители (+ – * :=; пробел и т.д.).

Могут вводиться и другие классы. При этом предпочтительно разбивать множество слов языка программирования на такие классы, которые бы не пересекались между собой. Классы могут состоять из конечного числа лексем (разделители и служебные слова), либо из бесконечного или очень большого числа элементов (классы числовых констант и идентификаторов).

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

Пример 1:

Вход лексического анализатора:

PROGRAM PRIMER;

VAR X,Y,Z: REAL;

BEGIN

X:=–3.14;

Y:=2;

Z:=X+Y;

END.

В качестве кодов классов лексем будем использовать числа: 10 – ключевое слово, 20 – разделитель, 30– идентификатор, 40 – числовая константа.

Внутренние таблицы лексического анализатора:

Таблица служебных слов (10)

Таблица разделителей (20)

Выходные таблицы лексического анализатора:

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

Таблица констант (40)

Лексическая свертка исходного текста:

(10,1) (30,1) (20,1)

(10,4) (30,2) (20,3) (30,3) (20,3) (30,4) (20,2) (10,5) (20,1)

(10,2)

(30,2) (20,2) (20,9) (20,6) (40,1) (20,4) (40,2) (20,1)

(30,3) (20,2) (20,9) (40,3) (20,1)

(30,4) (20,2) (20,9) (30,2) (20,5) (30,3) (20,1)

(10,3) (20,4)

Обратите внимание, что число –3.14 кодируется четырьмя дескрипторами: “–“, “3”, “.”, “14”. «Сборка» вещественной константы происходит на этапе синтаксического анализа (например, проверяется, чтобы дробная часть записывалась через точку, а не через запятую).

Поиск по сайту: