Лекция 15
Лексический анализ
Лексический анализ – первый этап работы любого компилятора. На этом этапе в исходном тексте программы выделяются основные лексические единицы (слова, или лексемы): идентификаторы, служебные слова, константы, метки и пр., которые заменяются условными кодами (дескрипторами). В результате формируется лексическая свертка исходной программы, представляющая собой последовательность дескрипторов лексем.
При проведении лексического анализа из текста программы исключаются комментарии, пробелы, символы табуляции и перевода строки. В ряде случаев также проверяется парность скобок.
Блок лексического анализа может быть организован в виде отдельной программы (как в трехпроходном компиляторе), либо в виде процедуры, которая вызывается по мере необходимости (как в одно- и двухпроходном компиляторе).
Уже отмечалось, что в лексической свертке каждая лексема заменяется дескриптором. Дескриптор имеет единый формат для всех типов лексем, и содержит два поля:
(<тип лексемы>, <указатель>)
<тип лексемы> – это, как правило, числовой код класса лексемы. Количество классов в языках программирования может быть различным. Наиболее распространенными классами являются:
идентификаторы (имена переменных, процедур, функций, меток и т.д);
служебные (ключевые) слова;
числовые константы (целые неотрицательные числа, состоят только из цифр). Лексическая свертка вещественного числа включает дескриптор целой части числа и дескриптор дробной части числа;
разделители (+ – * := ; пробел и т.д.).
Могут вводиться и другие классы. При этом предпочтительно разбивать множество слов языка программирования на такие классы, которые бы не пересекались между собой. Классы могут состоять из конечного числа лексем (разделители и служебные слова), либо из бесконечного или очень большого числа элементов (классы числовых констант и идентификаторов).
Лексемы собираются в таблицы – для каждого класса своя таблица. В поле дескриптора <указатель> содержится ссылка на строку соответствующей таблицы. Таблицы лексем для классов ключевых слов и разделителей встроены в компилятор, поэтому коды ключевых слов и разделителей всегда одни и те же в лексической свертке обрабатываемых текстов программ. Таблицы лексем для классов идентификаторов и числовых констант формируются на этапе лексического анализа. Поскольку тексты программ отличаются числом и именами переменных, количеством встречающихся числовых констант, коды идентификаторов и чисел различаются в лексической свертке различных программ. Конечность таблиц лексем объясняет ограничения, существующие в языках программирования на длину и количество различных используемых в программе идентификаторов.
Пример 1:
Вход лексического анализатора:
PROGRAM PRIMER;
VAR X,Y,Z : REAL;
BEGIN
X:=–3.14;
Y:=2;
Z:=X+Y;
END.
В качестве кодов классов лексем будем использовать числа: 10 – ключевое слово, 20 – разделитель, 30– идентификатор, 40 – числовая константа.
Внутренние таблицы лексического анализатора:
Таблица служебных слов (10)
№ п/п |
Служебное слово |
1 2 3 4 5 6 … |
PROGRAM BEGIN END VAR REAL INTEGER … |
Таблица разделителей (20)
№ п/п |
Разделитель |
1 2 3 4 5 6 7 8 9 … |
; : , . + – * \ = … |
Выходные таблицы лексического анализатора:
Таблица идентификаторов (30)
№ п/п |
Идентификатор |
1 2 3 4 |
PRIMER X Y Z |
Таблица констант (40)
№ п/п |
Значение |
1 2 3 |
3 14 2 |
Лексическая свертка исходного текста:
(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”. «Сборка» вещественной константы происходит на этапе синтаксического анализа (например, проверяется, чтобы дробная часть записывалась через точку, а не через запятую).