Курс Основы построения трансляторов


Лексический анализатор на основе конечного автомата - часть 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. Синтаксический анализ




Начало  Назад  Вперед



Книжный магазин