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

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

В программе определяется переменная - текущее состояние КА (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); }}

Далее в программе необходимо определить матрицу переходов. Матрица переходов - это двумерный массив, который для каждой пары “состояние (строка) и класс символа (столбец)” определяет новое состояние, в которое он переводится. Номер этого состояния и находится в матрице. Матрица переходов строится по соответствующей диаграмме состояний-переходов и фактически определяет поведение КА.