Лексический анализатор на основе конечного автомата - часть 2
Принцип заполнения матицы прост: если в состоянии S1 и входном символе L1 на диаграмме имеется дуга (переход) в состояние S2 то элемент массива D[S1][K1] должен быть инициализирован значением S2, где K1=class(L1). В рассматриваемом примере матрица будет выглядеть так:
.
int D[11][10]= {
{ 2, 5, 5, 1, 1, 1, 6,-8, 9,-9 },
{ 1, 1, 1, 1, 1, 1,-1,-1,-1,-1 },
{ 5, 4, 5, 3,-4,-4,-4,-4,-4,-4 },
{ 3, 3, 3,-2, 3,-2,-2,-2,-2,-2 },
{ 4, 4,-3,-3,-3,-3,-3,-3,-3,-3 },
{ 5, 5, 5,-4,-4,-4,-4,-4,-4,-4 },
{-5,-5,-5,-5,-5,-5,-5,
7,-5,-5 },
{ 7, 7, 7, 7, 7, 7, 7, 8, 7, 7 },
{ 7, 7, 7, 7, 7, 7,-6, 7, 7, 7 },
{ 9, 9, 9, 9, 9, 9, 9, 9,10, 9 },
{-7,-7,-7,-7,-7,-7,-7,-7,
9,-7 } };
Тогда поведение конечного автомата программируется в первом приближении таким простым циклом:
for (ST=0,i=0;S[i]!=0;i++) {CL=class(S[i]);ST=D[ST][CL];}
Специфика программирования КА применительно к лексическому анализу заключается только в действиях, производимых автоматом. Целью ЛА является распознавание и выделение лексемы (слова) - последовательности символов. Поэтому в КА вводится множество заключительных состояний, в которых завершается распознавание. Действия, связанные с распознаванием, практически одинаковы для всех типов лексем (слов), поэтому в КА вводится множество заключительных состояний, по одному на каждый тип лексемы. Они имеют отрицательное значение, и по их обнаружении программа выполняет следующие действия:
формирует цепочку из накопленных символов - значение лексемы;
устанавливает тип распознанной лексемы в соответствии с номером конечного состояния КА;
- возвращает КА в исходное (нулевое состояние);
- поскольку обнаружение лексемы иногда происходит в тот момент, когда КА обрабатывает символ, уже к ней не относящийся, то программа должна “вернуть” во входную последовательность заданное число символов для повторного просмотра. Например, любая десятичная константа распознается, когда уже прочитан следующий за ней символ - не цифра. Его то и необходимо вернуть. Для этого в программе определяется массив, в котором для каждого заключительного состояния указано количество возвращаемых символов.Естественно, что его содержимое определяется конкретной лексикой.
int W[]={ 1,1,1,1,1,0,1,0,0 };
if (ST < 0)
{ int j; ST = -ST-1; // тип лексемы
i=i-W[ST]; // вернуть символы
printf(“%s “,out[ST]); // вывести цепочку
for (j=FIX; j<i; j++) putchar(S[j]);
puts(“”);
ST=0; FIX=i; }
Для фиксации начала цепочки символов, образующих лексему (слово), в программе вводится переменная FIX, которая при любом переходе в начальное (нулевое) состояние запоминает расположение в строке текущего символа. Заготовка программы ЛА на основе конечного автомата находится в файле lexan.cpp.
3. Синтаксический анализ