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

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

ABC...Z $ @ #

0123...9 Пробел

=+–*/(),.;:'&|><?%

В языках типа Паскаль и Си терминальных символов уже около 200.

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

1). В таких языках, как Паскаль или Си, цепочка, состоящая из одного или более пробелов, обычно рассматривается как один пробел.

2). Группа символов в Паскале, ограниченная символами { } или  , трактуется как комментарий.

3). В большинстве языков есть ключевые слова, такие как BEGIN, END, IF, THEN, ELSE, WHILE и т.д., каждое из которых можно считать одним элементом.

4). Каждая цепочка, представляющая числовую или текстовую константу рассматривается как один элемент текста.

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

Работа лексического анализатора состоит в том, чтобы сгруппировать определенные терминальные символы в единые синтаксические объекты, называемые лексемами. Какие объекты считать лексемами зависит от определения языка программирования. Лексема – это цепочка терминальных символов, с которой мы связываем лексическую структуру, состоящую из пары вида: тип лексемы, некоторые данные. Первой компонентой этой пары является лексическая категория, такая как “константа” или “идентификатор” или “терминал“ (ключевое слово или специальный символ языка), а второе – указатель: в ней указывается адрес области памяти (номер элемента таблицы), хранящей полную информацию об этой конкретной лексеме. Для данного языка число типов лексем предполагается конечным.

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

Сразу же возникает вопрос, почему лексический анализ нельзя объединить с синтаксическим. Действительно, можно, ведь лексические единицы можно описать традиционно в нормальной форме Бэкуса (БНФ), например:

<идентификатор> ::= буква {буквацифра}³¹.

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

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

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

Итак, лексический анализатор решает задачи грамматического разбора исходной программы на базовые элементы – лексемы, строит последовательность лексем, а также таблицы идентификаторов и констант.

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

<комплексная константа> ::= (<вещественное>,<вещественное>),

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

Обычно выделяют всего три типа лексем: идентификатор – IDN, константу – CON и терминал (ключевое слово или специальный символ) – TRM.

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

Символ

Класс

Приоритеты

Каждый элемент этой таблицы состоит из собственно терминального символа (или группы), указателя его классификации (операция, разделитель и т.п.) и его приоритетов, не только для операций, но и других терминалов языка (подробно об этом смотрите в разделе 6.4 о методе Замельсона – Бауэра для перевода в ПОЛИЗ).

Определим форматы остальных таблиц, формируемых сканером.

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

Значение константы

Тип

Другая информация

Адрес

Таблица идентификаторов – создается при лексическом анализе для того, чтобы описать все идентификаторы, имеющиеся в исходной программе. Каждому идентификатору соответствует отдельный элемент таблицы. Во время лексического анализа в этот элемент помещается имя идентификатора. Для того чтобы зафиксировать длину элементов таблицы идентификаторов и не резервировать лишней памяти, в таблицу идентификаторов целесообразнее заносить не сами имена, так как их длина может меняться от 1 до 31 и более символов а указатели на имя в таблице (списке, строке) имен переменной длины. Атрибуты и адрес для каждого идентификатора записываются последующими фазами. Элемент таблицы идентификаторов может выглядеть так:

Имя

Тип

Тип памяти

Границы массива

Объем

Положе­ние в структуре

Началь­ное значение

Адрес

Прочее

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

Тип таблицы

Индекс

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

Группа символов, лежащая между разделителями в простейшем сканере может быть лексемой типа TRM, IDN или CON.

Сначала все лексические единицы сравниваются с элементами таблицы терминалов. В случае совпадения лексическая единица классифицируется как терминальный символ и формируется лексема типа TRM, которая и помещается в таблицу лексем.

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

<идентификатор >::=<буква>{<буква><цифра>}

или

<идентификатор >::=<буква>< буква > < И1>

< И1>::=<буква><цифра>< буква > <И1><цифра> <И1>

После того, как лексическая единица классифицирована как идентификатор, опрашивается таблица идентификаторов. Если данного идентификатора в таблице нет, то создается новый элемент таблицы и в него заносится имя идентификатора. Независимо от того, был создан новый элемент или нет, создается лексема типа IDN и помещается в таблицу лексем.

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

Если лексическая единица не подходит ни под одну из этих категорий, выдается сообщение о лексической ошибке.

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

№	Имя	Разделитель
1	((пробел)	да
2	(	да
3	,	да
4	:	да
5	)	да
6	;	да
7	<	да
8	=	да

№	Имя	Разделитель
9	PROCEDURE	нет
10	VAR	нет
11	INTEGER	нет
12	BEGIN	нет
13	IF	нет
14	THEN	нет
15	END	нет

Таблица 2.1. Таблица терминалов

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

Таблица 2.2. Таблица идентификаторов

№	Имя	Атрибуты
1	MAX
2	А
3	В
4	С

№	Тип	Индекс	Лексема	№	Тип	Индекс	Лексема
1	TRM	9	PROCEDURE	21	IDN	3	B
2	IDN	1	MAX	22	TRM	14	THEN
3	TRM	2	(	23	IDN	4	C
4	TRM	10	VAR	24	TRM	4	:
5	IDN	2	A	25	TRM	8	=
6	TRM	3	,	26	IDN	2	A
7	IDN	3	B	27	TRM	6	;
8	TRM	4	:	28	IDN	2	A
9	TRM	11	INTEGER	29	TRM	4	:
10	TRM	5	)	30	TRM	8	=
11	TRM	6	;	31	IDN	3	B
12	TRM	10	VAR	32	TRM	6	;
13	IDN	4	C	33	IDN	3	B
14	TRM	4	:	34	TRM	4	:
15	TRM	11	INTEGER	35	TRM	8	=
16	TRM	6	;	36	IDN	4	C
17	TRM	12	BEGIN	37	TRM	15	END
18	TRM	13	IF	38	TRM	15	END
19	IDN	2	A	39	TRM	6	;
20	TRM	7	<

Таблица 2.3. Таблица лексем

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

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

В общем случае алгоритм синтаксического анализа может быть не таким простым, как определено выше. Например, рассмотрим, следующие правильные операторы Фортрана, где, напомним, пробелы игнорируются:

(1) DO 10 I=1.15

(2) DO 10 I=1,15

В операторе (1) цепочка DO 10 I – переменная и 1.15 – константа. В операторе (2) DO – ключевое слово, 10 – константа, I – переменная, 1 и 15 – константы.

Если сканер реализован, как сопрограмма и, находясь в начале одного из этих операторов, он выполняет процедуру “Найти очередную лексему”, то он до тех пор не мог бы определить, является ли лексемой DO или DO 10 I, пока не дошли бы до запятой или точки.

Таким образом, лексический анализатор иногда должен заглядывать вперед за интересующую его в данный момент лексему. Еще худший пример встречается в языке ПЛ/1, где ключевые слова могут быть переменными. Глядя на входную цепочку вида DECLARE (Х1,Х2, ... Хn), упомянутый выше лексический анализатор не знал бы, что ему сказать: то ли DECLARE – идентификатор функции или массива и Х1,Х2, ... Хn – аргументы этой функции (индексы массива), то ли DECLARE – ключевое слово, требующее, чтобы у идентификаторов Х1,Х2, ... Хn был атрибут (или атрибуты), расположенный справа от закрывающей скобки. Здесь классификация лексем должна осуществляться с помощью части текста, которая идет после правой скобки. Но так, как число n может быть сколь угодно большим, то работая с языком ПЛ/1, этот лексический анализатор должен заглядывать вперед сколь угодно далеко. Однако существует другой подход к лексическому анализу, менее удобный, но позволяющий избежать проблемы заглядывания вперед.

Определим два простейших подхода к лексическому анализу. Большинство известных способов основано на том или другом из них, а некоторые на их комбинации.

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

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

Для примера рассмотрим все тот же текст из Фортрана

DO 10 I=1,15

с указателем, расположенным на левом конце. Непрямой лексический анализатор ответит “да”, если его спросят о лексеме типа DO или о лексеме типа <идентификатор>, но в первом случае указатель передвинется на 2 символа, а в последнем – на пять символов.

Прямой лексический анализатор обследует текст, вплоть до запятой и сделает заключение, что очередная лексема должна быть типа DO. Указатель при этом передвинется только на 2 символа, хотя и было просмотрено больше.

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

Упражнение на программирование.

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