Лексический анализатор на основе конечного автомата
Диаграмма состояний-переходов является наглядным средством неформального проектирования ЛА. На самом деле существует другой способ проектирования таких программ, основанный на более регулярном и естественном представлении КА, и, в частности, КА для лексического анализа.
В программе определяется переменная - текущее состояние КА (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. Синтаксический анализ
