Построение лексического анализатора

2.1. Задачи лексического анализа

Лексический анализ (ЛА) является первой фазой процесса компиляции и включает в себя

· просмотр исходного текста программы и преобразование его в длинную строку;

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

· выделение в тексте лексических единиц (нахождение границ лексем);

· распознавание лексических единиц (типов лексем);

· преобразование лексем во внутреннюю форму представления (таблицу кодов лексем);

· формирование служебных таблиц (таблицы терминальных символов, таблицы констант, таблицы имен и.т.д.).

Перечень лексем, которые распознаются ЛА, определяются языком программирования и грамматикой этого языка.

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

Границы лексем (начало и конец лексемы) определяются обычно следующим образом:

- по терминальным символам (пробелы, знаки операций, символы комментариев, знаки пунктуации – точка, точка с запятой и т.п.); появление в цепочке символов терминального символа обычно означает конец текущей (формируемой) лексемы;

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

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

2.2. Служебные таблицы ЛА

2.2.1. Таблица терминальных символов

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

Номер поля

1 2 3 4 используется на следующих

№ Символ Тип Признак старшинства фазах

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

В первом поле записывается номер лексемы в таблице терминальных символов. Во втором поле записывается сама лексема, точнее, ее ASCII-представление. В третьем поле хранится код типа символа (лексемы), он определяет данный символ либо как ключевое слово, либо как разделитель, либо как знак операции. В четвертом поле указывается признак старшинства (для терминальных символов, имеющих тип «знак операции»). Этот признак используется на последующих этапах компиляции – синтаксической и семантической обработке.

2.2.2. Таблица констант

Следующей таблицей, которая в отличие от 1-й не является постоянной, а создается (строится) в процессе ЛА, является таблица констант. Она включает несколько записей следующей структуры

1 2 3 4 5 6

№ Константа Основание Тип Точность Адрес

заполняется на следующих фазах

Каждая константа, встречаемая (первый раз) в тексте анализируемой программы, записывается в таблицу констант. В первое поле помещается номер константы в таблице констант. Во второе поле помещается строковое представление константы. В третье поле записывается основание системы счисления (2, 8, 10, 16). В четвертое поле помещается тип константы (целая, вещественная, логическая, символьная, строковая). В пятое поле помещается точность представления константы в памяти (в виде числа байтов, отводимых для хранения). В шестое поле заносится адрес расположения константы в памяти.

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

Каждому идентификатору в этой таблице соответствует отдельная запись следующего вида:

1 2 3

Номер имени Имя Атрибуты

в таблице имен имени

заполняется в ходе

семантического анализа Вид Тип Класс памяти Величина

В качестве атрибутов имени обычно указываются следующие:

1) вид: имя простой переменной; имя массива; имя процедуры или функции; метка;

2) тип: вещественный; целый; логический; строковый; символьный;

3) класс памяти хранения: статическая память; автоматическая; динамическая; внешняя (extern);

4) величина (количественная характеристика имени): длина строковой переменной; количество граничных пар для массива (размерность); значение границ для переменной интервального типа (в Паскале, например, интервальный тип определяется в виде 1..10).

2.2.4. Таблица кодов лексем

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

№ лексемы в программе Код лексемы

Тип лексемы Номер лексемы

в соотв. таблице

лексем

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

Кодирование типов: I – для лексем-имен, C – для лексем-констант, T – для лексем-терминальных символов языка.

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

Пример построения таблиц лексического разбора для программы на Паскале

1. Program Arifm;

2. Var I, J, Sum: Integer;

3. Begin

4. Sum:=0;

5. For I:=1 To 100 Do

6. Begin

7. Read(J);

8. Sum:=Sum+J;

9. End;

10. Sum:=Sum Div 100;

11. Write(Sum);

12. End.

Таблица терминальных символов

№ символа	Символ	Тип
Разделитель	Знак операции	Ключевое слово
	;
	,
	:
	:=
	(
	)
	+
	Div
	Program
	Var
	Integer
	Begin
	For
	To
	Do
	End
	Read
	Write
	.
	-
	*

Таблица имен

№ имени	Имя	Адрес
	Arifm
	I
	J
	Sum

Таблица констант

№ константы	Константа	Основание	Тип	Ширина
			Целая	2 байта
			Целая	2 байта
			Целая	2 байта

Таблица кодов лексем

№ п/п	Код	Лексема
	T10	Program
	T4	(пробел)
	I1	Arifm
	T1	;
	T11	Var
	T4	(пробел)
	I2	I
	T2	,
	I3	J
	T2	,
	I4	Sum
	T3	:
	T12	Integer
	T1	;
	T13	Begin
	T4	(пробел)
	I4	Sum
	T5	:=
	C1
	T1	;
	T14	For
	T4	(пробел)
	I2	I
	T5	:=
	C2
	T4	(пробел)
	T15	To
	T4	(пробел)
	C3
	T4	(пробел)
	T16	Do
	T4	(пробел)
	T13	Begin
	T4	(пробел)
	T18	Read
	T6	(
	I3	J
	T7	)
	T1	;
	I4	Sum
	T5	:=
	I4	Sum
	T8	+
	I3	J
	T1	;
	T17	End
	T1	;
	I4	Sum
	T5	:=
	I4	Sum
	T9	Div
	C3
	T1	;
	T19	Write
	T6	(
	I4	Sum
	T7	)
	T1	;
	T17	End
	T20	.

2.3. Обобщенный алгоритм лексической обработки

При рассмотрении далее обобщенного алгоритма функционирования лексического анализатора (ЛА) предполагается следующее:

- ЛА и синтаксический анализатор (СА) работают последовательно, а не параллельно, т.е. ЛА просматривает всю программу целиком и выделяет (формирует символ за символом из допустимых для лексемы символов входного потока) в ней все лексемы;

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

Обобщенный алгоритм работы ЛА можно описать следующим образом:

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

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

в) для выделенной лексемы (как строки символов) делается попытка ее распознавания (определения ее типа) в соответствии со следующим порядком распознавания типов (сверху вниз по убыванию старшинства):

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

· идентификатор (если лексема является правильным именем, но не является ключевым словом);

· константа (если лексема не является ни терминальным символов, ни именем);

г) при успешном распознавании информация о выделенной лексеме заносится в две таблицы:

· таблицу лексем соответствующего типа (соответствующая запись заносится только один - первый раз, т.е. когда данной лексемы в данной таблице еще не было);

· таблицу кодов лексем (заносится всегда, несмотря на повторения); при этом для лексемы-терминального символа формируется код лексемы типа Tnn (T - признак, nn – номер данной лексемы в таблице терминальных символов), для лексемы-идентификатора генерируется код лексемы типа Inn (I - тип, nn – номер данной лексемы в таблице имен), а для лексемы-константы генерируется код лексемы типа Cnn (C - тип, nn – номер данной лексемы в таблице констант).

д) при неуспешном распознавании фиксируется ошибка в лексеме;

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

2.4. Построение лексических распознавателей

Лексический анализатор имеет дело с такими объектами [числовые константы, имена (включая ключевые слова) и т.п.], которые обычно хорошо описываются с помощью так называемых регулярных выражений и регулярных грамматик. Распознавателями для регулярных языков (порождаемых регулярными грамматиками) являются конечные автоматы (КА). Построить КА можно:

- на базе регулярной грамматики (описывающей тот объект, который должен распознавать данный КА);

- прямо по описанию распознаваемого объекта (словесного описания или описания в виде регулярных выражений).

В общем случае КА задается пятеркой:

КА={K,V,M,S,Z},

где K - конечное множество возможных состояний автомата (алфавит состояний),

V - конечное множество допустимых входных символов (входной алфавит),

M - функция (матрица) переходов, значение каждого элемента которой [m(i,j) или m_ij] определяет состояние (имеется в виду номер состояния или его имя), в которое перейдет КА из состояния i при подаче на вход КА символа j (из алфавита),

S - начальное состояние, S K,

Z – множество заключительных состояний, Z K.

Наглядно КА представляется в виде диаграммы состояний. Здесь состояние автомата отождествляется с вершинами, а переходы из состояния в состояние - ориентированными дугами, соединяющими эти вершины. Дуги взвешиваются символами из входного алфавита V.

Для детерминированного КА в диаграмме все дуги, выходящие из произвольной вершины, помечены различными входными символами. Для недетерминированного КА из вершины могут выходить различные дуги, помеченные одним входным символом

Существуют правила перехода от описания распознаваемых объектов в виде автоматной грамматики к графу переходов КА.

При этом все продукции (правила) таких (автоматных) грамматик, как уже отмечалось ранее, имеют следующую форму:

А =>Ba, или А-> a,

где a Î Т; А, B Î N.

Переход от автоматной грамматики (заданной в форме БНФ) к графу (автомату), распознающему язык, порождаемый данной грамматикой, осуществляется по следующим правилам:

1) все нетерминальные (распознаваемые) символы автоматной грамматики будут представлять множество состояний автомата (узлы графа);

2) к множеству состояний автомата надо добавить начальное состояние (S);

3) каждое правило вида A --> Ba, где a Î Т; А, В Î N, представляется дугой вида

a,

а правило вида A --> a представляется дугой вида

a;

4) в качестве заключительного (конечного) состояния автомата берется начальный символ грамматики (для каждого класса лексем разрабатывается своя грамматика со своим начальным символом). Естественно, что начальный символ грамматики (например, <имя> для грамматики символических имен) и начальное состояние автомата (S) – это далеко не одно и то же.

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

Распознавание лексем с помощью такого автомата происходит следующим образом:

- в начальном состоянии КА находится в состоянии S;

- считывается очередной символ в анализируемой цепочке символов; если этим символом помечена одна из дуг, выходящая из текущего состояния, то КА переходит в новое состояние по этой дуге;

- действия из предыдущего пункта повторяются до тех пор, пока возможны переходы из одного состояния в другое.

КА завершает свою работу в одном из двух случаев:

1) исчерпаны все символы входной (распознаваемой) цепочки;

2) не удается найти дугу, по которой возможен переход в другое (не текущее) состояние.

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

Пример

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

Соответствующие правила автоматных грамматик для порождения этих лексем имеют вид:

1) <имя> --> (<буква>, ‘_’) | <имя><буква> | <имя><цифра> | <имя>’_’

2) <целая конст.> --> <цифра> | <знак><цифра>| <целая конст.><цифра>

3) <вещ. конст.> --> <целая конст.>’.’<цифра>| <вещ. конст.><цифра>

Указанным правилам соответствует следующий объединенный автомат для распознавания (и формирования из символов входного потока) трех видов лексем:

Буква, цифра или ‘_’

Буква Разделитель

з ‘_’

н Не разделитель, не буква, не цифра и не ‘_’

а Цифра Цифра

к

Разделитель

Цифра

т

о Не разделитель, не цифра и не ‘.’

ч

к

а

Разделитель

Цифра Не разделитель и не цифра

В этом автомате имеются следующие состояния (узлы):

S – начальное состояние,

1, 4 и 6 – продолжение формирования (из символов входного потока) соответственно идентификаторов, целых констант и вещественных констант,

2, 5 и 7 – конечные разрешенные состояния, попадание в которые означает правильное (без ошибок) завершение формирования (распознавание) соответственно идентификатора, целой константы и вещественной константы,

8, 9 и 10 - конечные неразрешенные состояния, попадание в которые означает неправильное (с ошибками) завершение формирования (распознавание) соответственно идентификатора, целой константы и вещественной константы.

Замечание. Здесь имеется отступление от указанного выше правила, что каждому нетерминальному символу грамматики должна соответствовать вершина (одна) графа. В приведенном графе каждому нетерминальному символу соответствует не одна, а три вершины – одна – состоянию продолжения формирования нетерминала, вторая – состоянию правильного завершения формирования нетерминала, а третья – состоянию неправильного завершения формирования нетерминала.

Соответствующая данному автомату матрица переходов имеет вид:

Вх. символы   Состояния	Знак	Цифра	Точка	Буква	Знак подч.	Разделитель	Прочие
S			-			-	-
	8 (Д1)		8 (Д1)				8 Д1 (если не разделитель, не буква, не цифра и не ‘_’)
	- (Д2)		- (Д2)	- (Д2)	- (Д2)	- (Д2)	- (Д2)
	9 (Д3)			9 (Д3)	9 (Д3)		9 Д3 (если не разделитель, не цифра и не ‘.’)
	10 (Д4)		10 (Д4)	10 (Д4)	10 (Д4)		10 Д4 (не разделитель и не цифра)

В этой матрице, как видно, определены не все элементы. Не определенные элементы матрицы соответствуют:

- переходам (точнее, отсутствию переходов) из конечных состояний (в приведенной матрице переходов – это строки 2, 5, 7, 8, 9, 10);

- ошибкам (не определенным пока) в анализируемом (сканером) тексте программы (в приведенной матрице переходов – это незаполненные ячейки в самой первой строке и строке, соответствующей переходам из состояния 3).

Чтобы не оставалось незаполненных ячеек, можно ввести дополнительные конечные неразрешенные состояния, например 11 (для неправильных переходов из состояния S) и 12 (для неправильные переходов из состояния 3).

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

Д1 – ошибка в записи имени,

Д2 – за знаком не следует цифра,

Д3 – за цифрой следует недопустимый символ,

Д4 – за точкой нет цифры.

и т.д.

Для удобства коды этих сообщений (Д1, Д2 и т.п.) приведены в круглых скобках в соответствующих (моментам их выдачи) ячейках матрицы переходов.