Особенности автоматов для лексического анализа

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

· достижение автоматом заключительного состояния рассматривается как факт обнаружения некоторой лексемы. Каждому заключительному состояния соответствует своя распознанная лексема. Это позволяет отказаться от выходных сигналов;

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

· при достижении конечного состояния КА принудительно сбрасывается в начальное состояние.

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

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

· рядом с каждым заключительным состоянием записывается количество возвращаемых символов;

· каждая дуга помечается только одним символом (или группой символов) перехода, выходных символов КА не продуцирует.

Вот так выглядит диаграмма состояний-переходов для десятичных констант, идентификаторов (в том числе, содержащих не менее 2 символов a), комментариев, отдельных символов / и *, а также строковых констант (вида ”…””……..”).

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

· цифры 0-9.

· буква a

· буквы b-z.

· символ “ / ”.

· ·символ “ * ”.

· символ “ ” ”.

· остальные символы.

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

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

Полученный КА включается в программу-распознаватель лексики в табличной форме, что позволяет сделать универсальным алгоритм работы КА, не зависящим от программируемой лексики, которая становится в программе компонентой данных. В архиве приведен простейшая реализация такой программы – (файл исходного текста lexan.cpp).

В программе определяется переменная - текущее состояние КА (переменная ST). Определением класса символа занимается отдельная функция. Функция возвращает номер класса символов, к которому относится ее входной символ, что соответствует номеру столбца матрицы переходов. Матрица переходов в программе - это двумерный массив, который для каждой пары «состояние (строка) и класс символа (столбец)» определяет новое состояние, в которое он переводится. Номер этого состояния и находится в матрице. Принцип заполнения матицы прост: если в состоянии S1 и входном символе L1 на диаграмме имеется дуга (переход) в состояние S2 то элемент массива D[S1][K1] должен быть инициализирован значением S2, где K1=class(L1). В рассматриваемом примере матрица будет выглядеть так:

.

int D[9][8]= {

{ 0, 2, 2, 1, 3, 0, 6, 0 },

{ -1, 1, 1, 1, -1, -1, -1, -1 },

……..

};

Цикл работы КА в программе выглядит так:

for (ST=0, i=0; S[i]! =0; i++) {CL=class(S[i]); ST=D[ST][CL]; }

Заключительные состояния нумеруются отрицательными числами, начиная с –1. Для последовательности заключительных состояний –1, -2, -3… в программе заведены два массива: имен лексем и числа возвращаемых символов:

int W[]={ 1, 1, 0, 0, 0 };

char *out[]={

" Ident", // Заключительное состояние –1

“Const” // -2

" Сomment", // -3

" String", // -4

" Error", // -5

};

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