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