spoPresentation2

Лексический анализ и регулярные грамматики

ЛА структурирует поступающий исходный текст

программы и устраняет избыточную

информацию, что упрощает структуру СА

для выделения и разбора лексем возможно

использовать простую и эффективную технику анализа, тогда как на этапе СА используются более сложные алгоритмы разбора

ЛА позволяет отстранить СА от работы с

исходным кодом, и при модификации лексики

входного языка позволяет достаточно быстро

перенастроить компилятор заменив ЛА и не

трогая СА

91

Лексический анализ и регулярные грамматики

конкретные функции ЛА и выделяемые им типы лексем определяют разработчики компилятора

устранение комментариев, незначащих пробелов и иных незначащих символов

выделение лексем

идентификаторы, константы, ключевые

слова, знаки операций и разделители

92

Лексический анализ и регулярные грамматики

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

Результат работы ЛА – поток образов лексем-дескрипторов и таблицы, в которых хранятся значения выделенных в программе лексем

93

Лексический анализ и регулярные грамматики

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

тип лексемы – это как правило числовой код класса лексемы

указатель – это либо начальный адрес области

памяти с адресом этой лексемы, либо номер

элемента таблицы соответствующих лексем

Классы лексем

конечные (ключевые слова, разделители)

бесконечные (идентификаторы,

константы, метки)

94

Лексический анализ и регулярные грамматики

Коды дескрипторов из конечных классов всегда одни и те же для данного компилятора независимо от исходной программы

Коды дескрипторов из бесконечных классов различны для разных программ

В процессе ЛА значения лексем бесконечных классов помещаются в таблицы соответствующих классов ( числовые константы при этом могут переводиться из символьного во внутреннее машинное представление

95

Лексический анализ и регулярные грамматики long factorial (long x)

{ if ( x == 1 ) return x; return factorial(x-1) * x; }

01 Ключ. cл.		02 Разделители		03 Идентификаторы
Код	Знач.	Код	Знач.	Код	Знач.
1	long	1	(	1	factorial
2	If	2	)	2	x
3	return	3	{
		4	==	04 Константы
		5	;	1	1
		6	-
		7	*
		8	}		96

Лексический анализ и регулярные грамматики

Выходной поток дескрипторов:

(01,1) (03,1) (02,1) (01,1) (03,2) (02,2)

(02,3) (01,2) (02,1) (03,2) (02,4) (04,1) (02,2) (01,3) (03,2) (02,5)

(01,3) (03,1) (02,1) (03,2) (02,6) (04,1) (02,2) (02,7) (03,2) (02,5)

(02,8)

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

КА определяет, принадлежит ли заданная входная цепочка символов языку, определяемому автоматом

97

Лексический анализ и регулярные грамматики

ЛА должен:

уметь определять границы лексем, которые в тексте явно не указаны

x+++y

(х++)+у

х+(++у)

сохранять информацию об обнаруженной лексеме (запись лексемы в поток (таблицу) лексем, поиск найденной лексемы в таблице идентификаторов, запись в таблицу идентификаторов)

98

Лексический анализ и регулярные грамматики

Выходной поток с ЛА поступает на вход СА

Организация связи ЛА и СА:

раздельно (последовательно)

проще в реализацииболее высокая скорость компиляции

неоднозначность при определении границ

лексем

нераздельно (параллельно). СА вызывает ЛА если ему требуется очередной образ лексемы

большие накладные расходы

99

Лексический анализ и регулярные грамматики

	Лексемы для
	помещения в
Исходный	таблицы
текст	ЛА	Таблицылексем
Очередная лексема	Обращение за лексемой
	СА

100