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

       

Лексический анализатор на основе конечного автомата


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

В программе определяется переменная - текущее состояние КА (ST);

Все множество входных символов разбивается на непересекающиеся множества - классы. Классы выбираются таким образом, чтобы обеспечивалось однозначное переключение КА, если анализируются не сами символы, а их классы. Например, если ЛА должен различать комментарии, идентификаторы, восьмеричные, десятичные и шестнадцатеричные и строковые константы, то множество символов необходимо разбить на следующие классы:

- цифра 0.

- цифры 1-7.

- цифры 8-9.

- буквы A-F,a-f.

- буква “x”.

- остальные буквы.

- символ “/”.

- символ “*”.

- символ “””.

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



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

int class(char c)

{ switch ( c)

      {

case      ‘*’:      return(7);

case      ‘”’:      return(8);

case      ‘/’:      return(6);

case      ‘0’:      return(0);

case      ‘8’:      return(2);

case      ‘9’:      return(2);

case      ‘x’:      return(3);

default:  if (isdigit(с)) return(1);

          if (isalpha(c))

                {if ((touppeк(с)>=’A’)&&(toupper(с)<=’F’))

                        return(4);

                return(5);

                }

          return(9); }}

Далее в программе необходимо определить матрицу переходов. Матрица переходов - это двумерный массив, который для каждой пары “состояние (строка) и класс символа (столбец)” определяет новое состояние, в которое он переводится. Номер этого состояния и находится в матрице. Матрица переходов строится по соответствующей диаграмме состояний-переходов и фактически определяет поведение КА.
Принцип заполнения матицы прост: если в состоянии 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. Синтаксический анализ


Содержание раздела