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

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

Полный набор лексем языка определен множеством терминальных символов в его грамматике. Среди них можно выделить изменяемые и неизменяемые лексемы. Неизменяемые лексемы в любой программе пишутся одинаково. Для грам-

матики псевдоязыка это такие лексемы, как: ПРОГРАММА, ПЕРЕМЕННЫЕ, НАЧ_ПРОГ, КОН_ ПРОГ, НАЧ_БЛОК, КОН_БЛОК, «.», «;», «:», «/», REAL, INTBYTE, INT_WORD, INTDWORD, «,», «:=», «=», «+», «-», «*», DIV, MOD, «(», «)», «[», «]», «<», «>», «==», ЧИТАТЬ, ПИСАТЬ, ДЛЯ, ДОДЕЛАТЬ, ПОКА, ДОВНИЗ, ЕСЛИ, ЕСЛИ, ДО, ТО, ПЕРЕЙТИ_НА, ПОВТОРИТЬ. «За бортом» остались три терминальных символа — ID, CH_INT, CH_REAL. Эти терминальные символы соответствуют идентификаторам, целым и вещественным числам. Естественно, что даже в пределах одной программы они будут различны. Задачей сканера как раз и является распознавание изменяемых и неизменяемых терминальных символов. С позиции логики обработки сканером удобно все терминальные символы отнести к одному из следующих классов (применительно к нашей грамматике псевдоязыка):

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

ключевые слова - ПРОГРАММА, ПЕРЕМЕННЫЕ, НАЧПРОГ, КОН_ПРОГ, НАЧБЛОК, КОН_ БЛОК, REAL, INTJYTE, INTWORD, INT_DWORD, DIV, MOD, ЧИТАТЬ, ПИСАТЬ, ДЛЯ, ДОДЕЛАТЬ, ПОКА, ДОВНИЗ, ЕСЛИ, ЕСЛИ, ДО, ТО, ПЕРЕЙТИ_НА, ПОВТОРИТЬ;

целые числа — CHINT;

вещественные числа — CH_REAL;

однолитерные разделители — «.», «,», «;», «:<@187>, «+»,«-», «*»,«/», «(»,«)», «=», «[», «]», «<», «>»;

В двулитерные разделители — «:=», «=», «>=», «=<».

Задача сканера — построить для каждого терминального символа его внутреннее представление. Делается это для того, чтобы убрать лишнюю информацию, подаваемую на вход синтаксического анализатора. Проведем аналогию. Все знают о твердом порядке слов в английском предложении. При этом не оговариваются конкретные слова, которые должны стоять на месте подлежащего, сказуемого, дополнения. Главное, чтобы слово, которое стоит, например, на месте подлежащего, было существительным или местоимением, то есть относилось к определенному классу. Сканер как раз и выполняет классификацию лексем, подаваемых на его вход. Он распознает, например, что очередная лексема является ключевым словом begin, после чего присваивает ей определенное целое значение и передает его далее. Если же сканер распознал на своем входе некоторый идентификатор, то он производит не просто замещение, но и некоторые другие действия. Чтобы подробнее разобраться со всем этим, необходимо понять состав и назначение структур данных, определенных внутри сканера.

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

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

Лексема	Внутренний код	Лексема	Внутренний код
ПРОГРАММА	1	*	23
		:=	24
НАЧ БЛОК	3	)	25
КОН_БЛОК	4	НАЧ_ПРОГ	26
REAL	5	КОН_ПРОГ	27
INT_BYTE	6	/	28
DIV	7	INT_WORD	29
ЧИТАТЬ	8	INT_DWORD	30
ПИСАТЬ	9	=	31
ДЛЯ	10	MOD	32
ДЕЛАТЬ	11	[	33
(	12	]	34
ТО	13	<	35
ID	14	>	36
CHJNT	15	==	37
CH_REAL	16	>=	38
	17	=<	39
>	18	до	40
1	19	ПОКА	41
•	20	довниз	42
+	21	ЕСЛИ	43
-	22	до	44
		ПЕРЕЙТИ_НА*

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

d - цифра;

1 — буква;

b — литеры, которые игнорируются, к ним может относится, например, пробел;

s1 — одиночные разделители: «.», «:», «(«, «)», «*»;

s2 — особые одиночные разделители: «.», «+», «-»,«:», «=», «<», «>».

Последние разделители отличаются тем, что они могут быть как собственно одиночными разделителями, так и входить в состав литер лексем, состоящих из нескольких литер. Например, разделитель «:» является не только одиночным, но и первой литерой двухлитерного разделителя «:=», а литеры «.», «+» и «-» являются составной частью лексемы «вещественное число».

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

ПРОГРАММА progl (1M14, #progl) ПЕРЕМЕННЫЕ (2)

INTBYTE 1 (6) (14. #i)

НАЧ_ПРОГ (26)

ДЛЯ i := О ТО 9 ДЕЛАТЬ (10Н14, #i)(24)(15. 0)(13)(15. 9Н11) ПИСАТЬ (i) (9)(12)(14, #i)(25)

КОНПРОГ (27)

Приведенная программа выводит на экран целые числа от 0 до 9, хотя в контексте нашего обсуждения это и не важно. После обработки сканером исходный текст программы преобразуется во внутреннее представление, которое показано справа для каждой строки. Становится понятным значение термина «лексическая свертка» — программа как бы сворачивается в некоторую унифицированную форму, теряя при этом свою индивидуальность. Каждая лексема замещена своим кодом. Идентификаторы замещены кортежами, первый элемент которых является кодом лексемы-идентификатора, а второй элемент — ссылкой на элемент таблицы идентификаторов, где содержится более подробная информация о данном идентификаторе. Ссылка может быть адресом элемента в таблице, но может быть удобнее, чтобы это было просто число, представляющее собой индекс в этой таблице. Это же касается и лексемы «целое число». Здесь возможны разные варианты: во-первых, можно организовать таблицу констант, подобную таблице идентификаторов; во-вторых, для простых применений константу можно разместить прямо в кортеже. В нашем примере для констант выбран второй вариант.

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

уникальный номер — номер, который на последующих этапах трансляции

будет идентифицировать данное символьное имя;

указатель на список, содержащий символы идентификатора;

указатель на список с номерами строк, в которых встретился данный идентификатор.

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

тивности процесса распознавания стоит все терминальные символы — ключевые слова языка, разделители и т. п. (за исключением id, chint и ch_rea1) — также свести в отдельное лексикографическое дерево или организовать хеш-таблицу.

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

А как организовать сам процесс распознавания лексем входной программы? Для этого попробуем сформулировать некий обобщенный алгоритм построения сканера.

1. Выделить классы лексем.

2. Определить классы литер.

3. Определить условия выхода из сканера для каждого класса лексем.

4. Для каждого класса лексем поставить в соответствие грамматику класса 3.

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

6. Выполнить объединение («склеивание») конечных автоматов для всех классов лексем.

7. Составить матрицу переходов для «склеенного» конечного автомата.

8. «Навесить» семантику на дуги «склеенного» конечного автомата.

9. Выбрать коды лексической свертки для терминалов грамматики и формат таблицы идентификаторов.

10. Разработать программу сканера.

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

Содержание раздела