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

Выходами лексического анализа являются поток образов лексем-дескрип­торов и таблицы; в последних хранятся значения выделенных в программе лексем.

Дескриптор — это пара вида: (<тип лексемы>, <указатель>),

где <тип лексемы> — это, как правило, числовой код класса лексемы, кото­рый означает, что лексема принадлежит одному из конечного множества клас­сов слов, выделенных в языке программирования;

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

Количество классов лексем (т.е. различных видов слов) в языках програм­мирования может быть различным. Наиболее распространенными классами являются:

· идентификаторы;

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

· разделители;

· константы.

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

С этих позиций коды образов лексем (дескрипторов) из конечных классов всегда одни и те же в различных программах для данного компилятора. Коды же образов лексем из бесконечных классов различны для разных программ и формируются каждый раз на этапе лексического анализа.

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

Рассмотрим основные идеи, которые лежат в основе построения лексичес­кого анализатора, проблемы, возникающие при его работе, и подходы к их ус­транению.

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

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

Идентификация лексемы из конечного класса выполняется путем сравне­ния ее с эталонным значением. Основная проблема здесь — минимизация вре­мени поиска эталона. В общем случае может понадобиться полный перебор слов данного класса, в особенности для случая, когда выделенное для опозна­ния слово содержит ошибку. Уменьшить время поиска можно, используя раз­личные методы ускоренного поиска:

· метод линейного списка;

· метод упорядоченного списка;

· метод расстановки и другие.

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

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

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

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

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

Выходной поток с лексического анализатора в дальнейшем поступает на вход синтаксического анализатора. Имеется две возможности их связи:

раздельная связь, при которой выход лексического анализатора формируется полностью и затем передается синтаксическому ана­лизатору;

нераздельная связь, когда синтаксическому анализатору требуется очередной образ лексемы, он вызывает лексический анализатор, ко­торый генерирует требуемый дескриптор и возвращает управление синтаксическому анализатору.

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

10 — ключевое слово;

20 — разделитель;

30 — идентификатор;

40 — константа.

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

main()

{

 int x,y,z;

 x=5;

 y=5;

 z=x+y;

}

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

Таблица ключевых слов (код 10)

номер п/п	Ключевое слово
1 2 3 4 …	main int float for …

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

номер п/п	Разделитель
1 2 3 4 5 6 7 8 9 10 …	; { } , = ( ) . + - …

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

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

номер п/п	Идентификатор
1 2 3	X Y Z

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

№ п/п	Значение константы
1	5

Дескрипторный текст:

(10,1) (20,6) (20,7)

(20,2)

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

(30,1) (20,5) (40,1) (20,1)

(30,2) (20,5) (40,1) (20,1)

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

(20,3).